sincronización de procesos sebastián sánchez prieto
Post on 11-Apr-2015
120 Views
Preview:
TRANSCRIPT
Sincronización de procesos
Sebastián Sánchez Prieto
1999-2003 S2P, OGP & IGT Sincronización 2
Tipos de procesos
Independientes Cooperantes
Su 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”
1999-2003 S2P, OGP & IGT Sincronización 3
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
1999-2003 S2P, OGP & IGT Sincronización 4
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);
1999-2003 S2P, OGP & IGT Sincronización 5
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);
1999-2003 S2P, OGP & IGT Sincronización 6
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;
En lenguaje ensamblador:Productor Consumidor
load r0, contador load r0, contadoradd r0, 1 sub r0, 1store contador, r0 store contador, r0
Problema: la modificación del contador no es atómica Dependiendo de la ejecución relativa de las instrucciones
se puede llegar a diferentes resultados
1999-2003 S2P, OGP & IGT Sincronización 7
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
Típicamente la arquitectura proporciona operaciones específicas para lograr la atomicidad
Si el hardware no proporciona operaciones atómicas, éstas no pueden construirse por software
1999-2003 S2P, OGP & IGT Sincronización 8
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 ...
1999-2003 S2P, OGP & IGT Sincronización 9
¿Cuál es el problema planteado?
Alguien necesita leche, pero no tanta Definiciones:
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 sección crítica, ningún otro proceso puede estar en esa misma sección crítica
1999-2003 S2P, OGP & IGT Sincronización 10
Problema de la sección crítica
Toda solución debe cumplir tres condiciones Exclusión mutua Progreso Espera limitada
Solución general:
do {protocolo de entrada sección críticaprotocolo de salida resto de la sección} while (TRUE);
1999-2003 S2P, OGP & IGT Sincronización 11
Tipos de soluciones
Suposiciones: Todos los procesos se ejecutan a una velocidad distinta de
cero 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 sistema operativo Soluciones proporcionadas por el lenguaje, regiones
críticas y monitores
1999-2003 S2P, OGP & IGT Sincronización 12
Solución con variables de control
Válidas para varios procesadores Suposición: las instrucciones de carga y almacenamiento
son atómicasPrimer intento Ti y Tj comparten la variable turno
Thread Tido {
while (turno != i) haz_nada; sección críticaturno = j; resto de la sección
} while (TRUE);
1999-2003 S2P, OGP & IGT Sincronización 13
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);
1999-2003 S2P, OGP & IGT Sincronización 14
Tercer intento (Dekker)
Variables compartidas: int turno, flag[2]; flag[i] = flag[j] = FALSE;Thread Ti
do { 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);
1999-2003 S2P, OGP & IGT Sincronización 15
Sincronización hardware (tas)
int test_and_set (int *destino) {int aux; aux = *destino; *destino = TRUE; return (aux); }
Variable compartida cerrojo iniciada a FALSE
do {while (test_and_set (&cerrojo)) haz_nada; sección críticacerrojo = FALSE; resto de la sección} while (TRUE);
1999-2003 S2P, OGP & IGT Sincronización 16
Sincronización hardware (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);
1999-2003 S2P, OGP & IGT Sincronización 17
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 el semáforo sea positivo, en este momento lo decrementa en 1
V (semáforo) Operación atómica que incrementa el semáforo en 1
¿Cómo quedaría el problema de la sección crítica con semáforos?
P (exmut) Sección críticaV (exmut)
1999-2003 S2P, OGP & IGT Sincronización 18
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
1999-2003 S2P, OGP & IGT Sincronización 19
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
Valores iniciales: smf_llenos = 0smf_vacíos = número_de_buffersexmut = 1
1999-2003 S2P, OGP & IGT Sincronización 20
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?
1999-2003 S2P, OGP & IGT Sincronización 21
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
protegidas con un semáforo exmut Valores iniciales:
leer = escribir = 0exmut = 1LA = EA = LE = EE = 0
Además: Los escritores tienen prioridad sobre los lectores
1999-2003 S2P, OGP & IGT Sincronización 22
Lector EscritorP (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);
1999-2003 S2P, OGP & IGT Sincronización 23
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
1999-2003 S2P, OGP & IGT Sincronización 24
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;int contadorbajada = 0;
Semáforos:semaforo exmut_s, exmut_b, puente;
Valores iniciales: Los semáforos inicialmente deben valer 1
No se tratan los problemas de inanición
1999-2003 S2P, OGP & IGT Sincronización 25
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);
1999-2003 S2P, OGP & IGT Sincronización 26
Problema de los filósofos
1999-2003 S2P, OGP & IGT Sincronización 27
Problema de los filósofos
Variables compartidas:exmutsemaforo[N]
Código de cada filósofo:void filosofo (int i) { while (TRUE) { piensa(); toma_tenedores(i); come(); pon_tenedores(i); }} /* Fin de filosofo */
1999-2003 S2P, OGP & IGT Sincronización 28
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 */
1999-2003 S2P, OGP & IGT Sincronización 29
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?
1999-2003 S2P, OGP & IGT Sincronización 30
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
1999-2003 S2P, OGP & IGT Sincronización 31
Barbero Cliente
do
{
P(exmut); if (esperando < SILLAS) { esperando++; 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);
1999-2003 S2P, OGP & IGT Sincronización 32
Codificación los semáforos
Las primitivas P y V se realizan por software 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
1999-2003 S2P, OGP & IGT Sincronización 33
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;}
1999-2003 S2P, OGP & IGT Sincronización 34
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;}
1999-2003 S2P, OGP & IGT Sincronización 35
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;}
1999-2003 S2P, OGP & IGT Sincronización 36
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
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
1999-2003 S2P, OGP & IGT Sincronización 37
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);
1999-2003 S2P, OGP & IGT Sincronización 38
¿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
1999-2003 S2P, OGP & IGT Sincronización 39
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 (COW)
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
top related