sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · arco...
TRANSCRIPT
![Page 1: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/1.jpg)
Sincronización de procesos
ARCO
![Page 2: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/2.jpg)
ARCO Sincronización
Contenido
Procesos concurrentes.
El problema de la seccion critica
Problemas clásicos de comunicación y
sincronización.
Mecanismos de comunicación y
sincronización.
![Page 3: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/3.jpg)
ARCO Sincronización
Procesos concurrentes
Los procesos llevan a cabo tareas para lograr un objetivo comun.
Interaccionan entre ellos para:Competir por recursos
Compartir recursos
ES NECESARIA LA COMUNICACION y
LA SINCRONIZACION (orden) ENTRE
ELLOS
![Page 4: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/4.jpg)
ARCO Sincronización
Procesos concurrentes
El método mas sencillo de comunicación entre los procesos de un programa concurrente, es el uso común de unas variables de datos.
Sin embargo el uso de este mecanismo
puede hacer que la ejecución de un proceso
interfiera en las acciones del otro.
![Page 5: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/5.jpg)
ARCO Sincronización
Ejemplo
![Page 6: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/6.jpg)
ARCO Sincronización
Productor-consumidor
Un proceso produce datos que son posteriormente procesados por otro proceso
i.e.: el manejador de teclado y el programa
que recoge los caracteres de un buffer
Lo más cómodo es emplear un buffer circular
![Page 7: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/7.jpg)
ARCO Sincronización
Código del productor
El productor no puede escribir en el buffer si está lleno
Comparte con el consumidor: el buffer y el contador
do {
...
produce un nuevo elemento (elemento_p)
...
while (contador == MAX_ELEMENTOS) haz_nada;
buffer[indice_p] = elemento_p;
indice_p = (indice_p + 1) % MAX_ELEMENTOS;
contador = contador + 1;
} while (TRUE);
![Page 8: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/8.jpg)
ARCO Sincronización
Código del consumidor
El productor no puede leer del buffer si está vacío
Comparte con el consumidor: el buffer y el contadordo {
while (contador == 0) haz_nada;
elemento_c = buffer[indice_c];
indice_c = (indice_c + 1) % MAX_ELEMENTOS;
contador = contador - 1;
...
consume el elemento (elemento_c)
...
} while (TRUE);
![Page 9: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/9.jpg)
ARCO Sincronización
Condiciones de carrera
El código anterior no funciona por existir condiciones de carrera al actualizar el contador
Veamos qué ocurre al ejecutar la sentencia: contador = contador + 1;
ProductorConsumidor
load r0, contador load r0, contador
add r0, 1 sub r0, 1
store contador, r0 store contador, r0
Problema: la modificación del contador no es
atómica
![Page 10: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/10.jpg)
ARCO Sincronización
Atomicidad
Una operación se dice que es atómica (en un sistema uniprocesador) cuando se ejecuta con las interrupciones deshabilitadas
Las referencias y las asignaciones son
atómicas en la mayoría de los sistemas.
Esto no es siempre cierto para matrices,
estructuras o números en coma flotante
Si el HW no proporciona operaciones
atómicas, éstas no pueden construirse por
SW
![Page 11: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/11.jpg)
ARCO Sincronización
Sincronización
Persona A Persona B
3:00 Mira en la nevera. No hay leche
3:05 Va a la tienda
3:10 Llega a la tienda
3:15 Deja la tienda
3:20 Llega a casa y guarda la leche
3:25
3:30
Mira en la nevera. No hay leche
Va a la tienda
Llega a la tienda
Deja la tienda
Llega a casa y ...
![Page 12: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/12.jpg)
ARCO Sincronización
¿Cuál es el problema planteado?
Alguien necesita leche, pero no tanta
Exclusión mutua: es el mecanismo que asegura
que sólo un proceso está haciendo algo en un
instante determinado
Sección crítica: es la sección de código, o
colección de operaciones, en el que se actualizan
variables comunes o se ejecuta código común.
Cuando un proceso está ejecutando código de su SC, ningún otro proceso puede estar en su SC
![Page 13: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/13.jpg)
ARCO Sincronización
Seccion Critica
Para evitar este tipo de errores, hay que identificar las regiones de los procesos en donde se acceden a recursos compartidos y dotarlas de la posibilidad de ejecucion como si fueran
una única instruccion
![Page 14: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/14.jpg)
ARCO Sincronización
Seccion Critica
Seccion Critica: Aquellas partes de los procesos concurrentes que no pueden ejecutarse de forma concurrente.
Los procesos deben de acceder en
Exclusion Mutua
![Page 15: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/15.jpg)
ARCO Sincronización
Problema de la Sección Critica
Sistema compuesto por n procesos
Cada uno tiene un (mismo) fragmento de
código:
sección crítica
Sólo uno de los procesos en cada instante
puede ejecutar en la sección crítica
Cuando un proceso está ejecutando en la
sección crítica, ningún otro puede hacerlo
![Page 16: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/16.jpg)
ARCO Sincronización
Para conseguir dicha exclusión mutua se deben de implementar protocolos software o hardware que impidan o bloqueen el acceso a una SC mientras está siendo utilizada por otro proceso.
Solución general:do {
protocolo de entrada
sección crítica
protocolo de salida
resto de la sección
} while (TRUE);
Problema de la Sección Critica
![Page 17: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/17.jpg)
ARCO Sincronización
Problema de la sección crítica
Toda solución debe cumplir tres condiciones
Exclusión mutua
Progreso
Espera limitada
![Page 18: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/18.jpg)
ARCO Sincronización
Tipos de soluciones
Soluciones soft. basadas en variables de control (DecKer,Peterson,..)
Soluciones hw. basadas en instrucciones máquina específicas (test-and-set o
swap)
Soluciones basadas en primitivas del SO
Soluciones basadas en regiones críticas y
monitores
![Page 19: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/19.jpg)
ARCO Sincronización
Problemas clásicos de comunicacióny sincronización
El problema del productor-consumidor
El problema de los lectores-escritores
Comunicación cliente-servidor
![Page 20: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/20.jpg)
ARCO Sincronización
Problema del productor-consumidor
![Page 21: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/21.jpg)
ARCO Sincronización
El problema de los lectores-escritores
![Page 22: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/22.jpg)
ARCO Sincronización
Comunicación cliente-servidor
![Page 23: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/23.jpg)
Primitivas del SO para comunicación y sincronizacion
![Page 24: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/24.jpg)
ARCO Sincronización
Primitivas del SO
Mecanismos de comunicaciónTuberías (pipes, FIFOS)
Paso de mensajes
Mecanismos de sincronizacionServicios del sistema operativo:
Señales (asincronismo)
Tuberías (pipes, FIFOS)
Semáforos
Paso de mensajes
Las operaciones de sincronización deben ser
atómicas
![Page 25: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/25.jpg)
ARCO Sincronización
Semáforos
Introducidos por Dijkstra en los años 60
Es un tipo especial de variable que sólo puede ser
accedida por dos primitivas P y V
P (semáforo): operación atómica que espera hasta que la variable
semáforo sea positiva, en este momento la
decrementa en 1
V (semáforo): operación atómica que incrementa la variable semáforo
en 1
¿Cómo quedaría el problema de la sección crítica
con semáforos?
![Page 26: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/26.jpg)
ARCO Sincronización
Operaciones sobre Semáforos
Wait(s) {
s = s - 1;
if (s < 0) {
<Bloquear al proceso>
}
}
signal(s) {
s = s + 1;
if (s <= 0)
<Desbloquear a un proceso bloqueado por la
operacion wait>
}
}
![Page 27: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/27.jpg)
ARCO Sincronización
Características de los semáforos
Son independientes de la máquina
Son simples
Pueden trabajar con varios procesos
Doble uso de los semáforos:
Exclusión mutua
Sincronización
![Page 28: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/28.jpg)
ARCO Sincronización
Secciones críticas con semáforos
Wait(s); /* P(s) entrada en la seccion critica */
< seccion critica >
signal(s); /* V(S) salida de la seccion critica */
El semáforo debe tener valor inicial 1
![Page 29: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/29.jpg)
ARCO Sincronización
EJEMPLO USO SEMAFOROS
P0
Valor del
semáforo (s)
wait(s)
signal(s)
signal(s)
signal(s)
wait(s)
desbloquea
Desbloquea
wait(s)
1
1
0
-1
-2
-1
0
P1
P2
Ejecutando código de la sección crítica
Proceso bloqueado en el semáforo
![Page 30: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/30.jpg)
ARCO Sincronización
Productor-consumidor
Restricciones:
El consumidor espera a que haya datos en el buffer
El productor espera a que haya buffers vacíos
Sólo un único proceso puede manipular el buffer a la vez
Semáforos:
smf_llenos, smf_vacíos y exmut
Inicialización:
smf_llenos = 0
smf_vacíos = número_de_buffers
exmut = 1
![Page 31: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/31.jpg)
ARCO Sincronización
ProductorConsumidor
P (smf_vacíos);
P (exmut);
Produce un dato;
V (exmut);
V (smf_llenos);
P (smf_llenos);
P (exmut);
Consume el dato;
V (exmut);
V (smf_vacíos);
¿Por qué el productor hace P(smf_vacíos) y V(smf_llenos)?
¿Es importante el orden en que se ejecutan las
primitivas P y V?
¿Cómo podemos extender el problema si hay dos
consumidores?
![Page 32: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/32.jpg)
ARCO Sincronización
Lectores-escritores
Descripción:
Los escritores acceden a la BBDD cuando no haya
ningún otro escritor y ningún lector. Semáforo escribir
Los lectores acceden cuando no haya ningún escritor
accediendo o esperando. Semáforo leer
Variables compartidas: LA, LE, EA, EE. A estas variables
accederemos en exclusión mutua. Semáforo exmut
![Page 33: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/33.jpg)
ARCO Sincronización
Iniciación
leer = escribir = 0
exmut = 1
LA = EA = LE = EE = 0
Además:
Los escritores tienen prioridad sobre los lectores
![Page 34: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/34.jpg)
ARCO Sincronización
LectorEscritor
P (exmut);
if ((EA + EE) == 0) {
V (leer);
LA = LA + 1;
} else {
LE = LE + 1;
}
V (exmut);
P (leer);
Leemos los datos;
P (exmut);
LA = LA - 1;
if (LA == 0 && EE > 0) {
V (escribir);
EA = EA + 1;
EE = EE - 1;
}
P (exmut);if (( EA + LA + EE) ==
0){V (escribir);EA = EA + 1;
} else {EE = EE + 1;
}V (exmut);P (escribir);Escribimos los datos;P (exmut);EA = EA - 1;if (EE > 0) {
V (escribir);EA = EA + 1;EE = EE - 1;
} else while (LE > 0) {V (leer);LA = LA + 1;LE = LE - 1;
}V (exmut);
![Page 35: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/35.jpg)
ARCO Sincronización
Problema del barbero dormilón
Problema: 1 barbero y N sillas de espera
Si un cliente entra y no hay sillas, se va
Semáforos:clientes: número de clientes en espera sin contar el que
está en la silla del peluquero
barberos: número de barberos inactivos
exmut: exclusión mutua
Variable compartida:esperando: número de clientes esperando
Inicialmente:clientes=0 barberos=0 exmut=1 esperando=0
![Page 36: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/36.jpg)
ARCO Sincronización
Barbero Cliente
do {
P(exmut);
if (esperando < SILLAS) {
esperando=esperando + 1;
V(clientes);
V(exmut);
P(barberos);
/* Se corta el pelo */
} else {
V(exmut);
}
} while (PELOLARGO);
do {
P(clientes);
P(exmut);
esperando=esperando-
1;
V(barberos);
V(exmut);
/* Corta el pelo */
} while (TRUE);
![Page 37: Sincronización de procesosumh2269.edu.umh.es/wp-content/uploads/sites/1051/... · ARCO Sincronización Procesos concurrentes El método mas sencillo de comunicación entre los procesos](https://reader030.vdocumento.com/reader030/viewer/2022040904/5e77c09514beaf149c4d477c/html5/thumbnails/37.jpg)
ARCO Sincronización
Problema del puente estrecho
Por un puente sólo pueden pasar o coches que suben o coches que bajan.
Solución:
Variables compartidas:int contadorsubida = 0, contadorbajada = 0;
semaforo exmut_s, exmut_b, puente;
Iniciación:
Los semáforos inicialmente deben valer 1
No se tratan los problemas de inanición