Post on 20-Jan-2016
Sincronización de procesos
Mariano Gómez Plaza
Sincronización de procesos 2
2002-2003 Mariano Gómez Plaza
Tipos de procesos
Independientes CooperantesSu estado no es compartido Su estado es compartido
Son deterministas Su funcionamiento no es determinista
Son reproducibles Su funcionamiento puede ser irreproducible
Pueden ser detenidos y rearrancados sin ningún efecto negativo
Ejemplo: un programa que calcula 1000 cifras decimales de pi
Si son detenidos y posteriormenterearrancados puede que se produzcan efectos negativos
Ejemplo: un proceso que escribeen el terminal la cadena “abc” yotro la cadena “cba”
Sincronización de procesos 3
2002-2003 Mariano Gómez Plaza
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
Productor Consumidor
Escribe Lee
Sincronización de procesos 4
2002-2003 Mariano Gómez Plaza
Código del productor
El productor no puede escribir en el buffer si está lleno
Comparte con el consumidor: el buffer y el contadordo {
...
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);
Sincronización de procesos 5
2002-2003 Mariano Gómez Plaza
Código del consumidor
El productor no puede leer del buffer si está vacío Comparte con el consumidor: el buffer y el contador
do {
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);
Sincronización de procesos 6
2002-2003 Mariano Gómez Plaza
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;
Productor Consumidor
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
Sincronización de procesos 7
2002-2003 Mariano Gómez Plaza
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
Sincronización de procesos 8
2002-2003 Mariano Gómez Plaza
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 ...
Sincronización de procesos 9
2002-2003 Mariano Gómez Plaza
¿Cuál es el problema planteado?
Alguien necesita leche, pero no tanta Exclusión mutua: es el mecanismo que asegura
que sólo una persona o proceso está haciendo algo en un instante determinado (los otros están excluidos).
Sección crítica: es la sección de código, o colección de operaciones, en el que se actualizan variables comunes. Cuando un proceso está ejecutando código de su SC, ningún otro proceso puede estar en su SC
Sincronización de procesos 10
2002-2003 Mariano Gómez Plaza
Problema de la sección crítica
Toda solución debe cumplir tres condicionesExclusión mutua
Progreso
Espera limitada
Solución general:do {
protocolo de entrada
sección crítica
protocolo de salida
resto de la sección
} while (TRUE);
Sincronización de procesos 11
2002-2003 Mariano Gómez Plaza
Tipos de soluciones
Suposiciones: Los procesos se ejecutan a una velocidad 0 Su velocidad relativa no influye
Soluciones basadas en variables de control Soluciones 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
Sincronización de procesos 12
2002-2003 Mariano Gómez Plaza
Solución con variables de control
Válidas para varios procesadores Suposición: las instrucciones de carga y almacenamiento
son atómicas
Primer intento Ti y Tj comparten la variable turno
Thread Tido {
while (turno != i) haz_nada;
sección crítica
turno = j;
resto de la sección
} while (TRUE);
Sincronización de procesos 13
2002-2003 Mariano Gómez Plaza
Segundo intento
Variables compartidas:flag[i] = FALSE;
flag[j] = FALSE;
Estas variables indican la intención de los hilos de entrar en sección crítica
Thread Tido { flag[i] = TRUE; while (flag[j]) haz_nada; sección crítica flag[i] = FALSE; resto de la sección} while (TRUE);
Sincronización de procesos 14
2002-2003 Mariano Gómez Plaza
Tercer intento (Dekker)
Variables compartidas:int turno, flag[2];
flag[i] = flag[j] = FALSE;
Thread Tido {
flag[i] = TRUE;
turno = j;
while (flag[j] && (turno == j)) haz_nada;
sección crítica
flag[i] = FALSE;
resto de la sección
} while (TRUE);
Sincronización de procesos 15
2002-2003 Mariano Gómez Plaza
Sincronización hardware
int test_and_set (int *destino) {
int aux;
aux = *destino;
*destino = TRUE;
return (aux); }
Variable compartida cerrojo iniciada a FALSEdo {
while (test_and_set (&cerrojo)) haz_nada;
sección crítica
cerrojo = FALSE;
resto de la sección
} while (TRUE);
Sincronización de procesos 16
2002-2003 Mariano Gómez Plaza
Instrucción swap
void swap (int *a, int *b) {int aux; aux = *a; *a = *b; *b = aux; }
Variable compartida cerrojo iniciada a FALSEdo { llave = TRUE; do { swap (cerrojo, llave); } while (llave != FALSE); sección crítica cerrojo = FALSE; resto de la sección} while (TRUE);
Sincronización de procesos 17
2002-2003 Mariano Gómez Plaza
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?
Sincronización de procesos 18
2002-2003 Mariano Gómez Plaza
Características de los semáforos
Son independientes de la máquina Son simples Pueden trabajar con varios procesos Pueden permitir que varios procesos entren en la
sección crítica al mismo tiempo en caso de necesitarse esta posibilidad
Doble uso de los semáforos: Exclusión mutua Sincronización
Sincronización de procesos 19
2002-2003 Mariano Gómez Plaza
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
Sincronización de procesos 20
2002-2003 Mariano Gómez Plaza
Productor Consumidor
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?
Sincronización de procesos 21
2002-2003 Mariano Gómez Plaza
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
Sincronización de procesos 22
2002-2003 Mariano Gómez Plaza
Iniciación
leer = escribir = 0 exmut = 1 LA = EA = LE = EE = 0 Además:
Los escritores tienen prioridad sobre los lectores
Sincronización de procesos 23
2002-2003 Mariano Gómez Plaza
Lector Escritor
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);
Sincronización de procesos 24
2002-2003 Mariano Gómez Plaza
Casos particulares
Un lector entra y deja el sistema Un escritor entra y deja el sistema Entran dos lectores al sistema Un escritor entra y debe esperar Un lector entra y debe esperar Los lectores abandonan el sistema y el escritor
continúa Los escritores abandonan el sistema, y el último
lector continúa y abandona
Sincronización de procesos 25
2002-2003 Mariano Gómez Plaza
Problema de los filósofos
Variables compartidas:exmut
semaforo[N]
void filosofo (int i) {
while (TRUE) {
piensa();
toma_tenedores(i);
come();
pon_tenedores(i);
}
} /* Fin de filosofo */
Sincronización de procesos 26
2002-2003 Mariano Gómez Plaza
Problema de los filósofos
void toma_tenedores(int i) { P(exmut); estado[i] = HAMBRIENTO; comprueba(i); V(exmut); P(semaforo[i]);} /* Fin de toma_tenedores */
void pon_tenedores(int i) { P(exmut); estado[i] = PENSANDO; comprueba((i-1)%N); comprueba((i+1)%N); V(exmut);} /* Fin de pon_tenedores */
Sincronización de procesos 27
2002-2003 Mariano Gómez Plaza
Problema de los filósofos
void comprueba(int i) { if (estado[i] == HAMBRIENTO && estado[(i-1)%N] != COMIENDO && estado[(i+1)%N] != COMIENDO) { estado[i] = COMIENDO; V(semaforo[i]); }} /* Fin de comprueba */
¿A qué valores se deben iniciar los semáforos? ¿Por qué la función comprueba siempre se invoca
desde una sección crítica?
Sincronización de procesos 28
2002-2003 Mariano Gómez Plaza
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
Sincronización de procesos 29
2002-2003 Mariano Gómez Plaza
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);
Sincronización de procesos 30
2002-2003 Mariano Gómez Plaza
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
Sincronización de procesos 31
2002-2003 Mariano Gómez Plaza
Código subida Código bajada
P(exmut_s);
contadorsubida++;
if (contadorsubida == 1)
P(puente);
V(exmut_s);
... Se sube el puente ...
P(exmut_s);
contadorsubida--;
if (contadorsubida == 0)
V(puente);
V(exmut_s);
P(exmut_b);
contadorbajada++;
if (contadorbajada == 1)
P(puente);
V(exmut_b);
... Se baja el puente ...
P(exmut_b);
contadorbajada--;
if (contadorbajada == 0)
V(puente);
V(exmut_b);
Sincronización de procesos 32
2002-2003 Mariano Gómez Plaza
Codificación los semáforos
Las primitivas P y V se realizan por SW Razón: P y V se ven implicados en aspectos de
planificación Partimos de la siguiente declaración:
typedef struct {
int contador;
(cola q;)
int t; /* Para multiprocesadores */
} SEMAFORO;
En el caso de los semáforos con espera activa el código entre paréntesis sobra
Sincronización de procesos 33
2002-2003 Mariano Gómez Plaza
P y V en spin locks (espera activa)
P (SEMAFORO *s) {
while (1) {
cli;
if (s->contador > 0) {
s->contador- = 1;
sti;
return;
}
sti;
} /* fin del while */
}
V (SEMAFORO *s) {
cli;
s->contador+ = 1;
sti;
}
Sincronización de procesos 34
2002-2003 Mariano Gómez Plaza
P y V en sistemas uniprocesador
P (SEMAFORO *s) {
cli;
if (s->contador > 0) {
s->contador- = 1;
sti;
return;
}
Añadimos proc. a s->q
sti;
Planificación
}
V (SEMAFORO *s) {
cli;
if (s->q == vacía) {
s->contador+ = 1;
} else {
Sacar proceso de s->q
Despertarlo
}
sti;
}
Sincronización de procesos 35
2002-2003 Mariano Gómez Plaza
P y V en sistemas multiprocesador
P (SEMAFORO *s) {
while (TAS(s->t) != 0);
if (s->contador > 0) {
s->contador- = 1;
s->t = 0;
return;
}
Añadimos proc. a s->q
s->t = 0;
Planificación
}
V (SEMAFORO *s) {
while (TAS(s->t) != 0);
if (s->q vacía) {
s->contador+ = 1;
} else {
Sacar proceso de s->q;
Despertarlo;
}
s->t = 0;
}
Sincronización de procesos 36
2002-2003 Mariano Gómez Plaza
Comunicación con mensajes
Válido para comunicación intermáquina Definición:
Mensaje: parte de información que es pasada de un proceso a otro
Buzón: lugar donde se depositan los mensajes desde el envío a la recepción
Operaciones sobre mensajes: Enviar Recibir
Sincronización de procesos 37
2002-2003 Mariano Gómez Plaza
Métodos de comunicación
Comunicación en un único sentido: los mensajes fluyen en un único sentido Ejemplos: Tuberías de UNIX, productor-
consumidor y streams Comunicación bidireccional: los mensajes fluyen en
ambos sentidos Ejemplos: Llamadas a procedimientos remotos
(RPC´s) o el modelo cliente-servidor
Sincronización de procesos 38
2002-2003 Mariano Gómez Plaza
Ejemplos
Productor:
int mensaje1[1000];
while (1) {
--Preparamos el mensaje1--
enviar (mensaje1, buzón);
} Cliente:char resp[1000];
envia(“leer vax”, buzon1);
recibir (resp, buzon2);
Consumidor:
int mensaje2[1000];
while (1) {
recibir (mensaje2, buzón);
--Procesamos el mensaje2--
} Servidor:char orden[100];
char resp[1000];
recibir (orden, buzon1);
enviar (resp, buzon2);
Sincronización de procesos 39
2002-2003 Mariano Gómez Plaza
¿Por qué utilizar mensajes?
Muchas aplicaciones responden a este esquema Las partes que se comunican pueden ser
completamente independientes. Ventajas:
Es más difícil que se produzcan errores Permite que los procesos no confíen entre sí Las aplicaciones pueden ser escritas por
programadores y en tiempos diferentes Los procesos pueden correr en diferentes
procesadores, conectados a través de una red
Sincronización de procesos 40
2002-2003 Mariano Gómez Plaza
Implementación de los mensajes
Nombres Comunicación simétrica Comunicación asimétrica
Copiado Paso por valor: es lento y obligatorio en sistemas
sin memoria compartida Paso por referencia: es rápido pero hay
problemas con su modificación Híbrido: copy-on-write
Sincronización de procesos 41
2002-2003 Mariano Gómez Plaza
Implementación de los mensajes
Bloqueo versus no bloqueo enviar y recibir pueden ser bloqueantes o no Formas de espera en un buzón:
Varios procesos pueden esperar en un buzón
Un proceso puede esperar en varios buzones
Longitud Mensajes de longitud fija Mensajes de longitud variable