Tema 6: Concurrencia - ULPGCsopa.dis.ulpgc.es › so › teoria › pdf › Old ›...
Transcript of Tema 6: Concurrencia - ULPGCsopa.dis.ulpgc.es › so › teoria › pdf › Old ›...
Sistemas OperativosTema 6. Concurrencia
1
© 1998-2008 José Miguel Santos – Alexis Quesada – Francisco Santana
Bibliografía
Fundamentos de Sistemas Operativos S. Candela, C.R. García, A. Quesada, F.J. Santana, J.M. Santos.
Thomson, 2007 Capítulo 3
Programación Concurrente J.T. Palma, M.C. Garrido, F. Sánchez, A. Quesada Capítulos 1, 2, 3, 4, 5 y 6
Principles of Concurrent and Distributed Programming M. Ben-Ari. Prentice Hall, 1990
Concurrent Programming A. Burns, G. Davies. Addison-Wesley, 1993
3
Modelo del sistema
Conjunto de procesos cooperativos Red de cajeros automáticos Sistema de reserva de billetes Servidor de impresión ...
5
¿Qué es concurrencia?
Definición de diccionario: coincidir en el espacio o en el tiempo dos o más personas o cosas.
En Informática, se habla de concurrencia cuando hay unaexistencia simultánea de varios procesos en ejecución.
Ojo, concurrencia existencia simultánea no implica ejecución simultánea.
6
Paralelismo y concurrencia
El paralelismo es un caso particular de la concurrencia.
Se habla de paralelismo cuando ocurre la ejecución simultánea de instrucciones.
7
Procesos cooperativos
Necesidades de sincronización y comunicación
Los procesos concurrentes tendrán necesidad de comunicarse información
Además, será necesario en ocasiones detener a un proceso hasta que se produzca un determinado evento o se den ciertas condiciones sincronización
8
Técnicas de sincronización
Basadas en memoria compartida Inhibición de Interrupciones Espera activa Semáforos Regiones críticas Monitores
Basadas en el paso de mensajes Canales Buzones
9
Ejemplo 1: modificación concurrente de una variable
procedureEjemplo1is
x:integer;
procedureP1isbegin x:=x+10;endP1;
procedureP2isbeginifx>100then Put_Line(x);else Put_Line(x‐50);endif;endP2;
beginx:=100; COBEGIN P1; P2; COEND;endEjemplo1;
10
Ejemplo 2: bucles infinitos concurrentesprocedureEjemplo2iscontador:integer;
procedureCuentaisbegin loop …esperaaquepaseuncoche… contador:=contador+1; endloop;endCuenta;
procedureImprime;begin loop esperaunahora Put(“Cochesquehanpasado:“);Put(contador); contador:=0 endloop;
begincontador:=0; COBEGIN Cuenta; Imprime; COEND;endEjemplo2;
11
Ejemplo 3: búfer limitado
loopproducir_algo(elem);loop exitwhencontador<N;endloop;buffer(entra):=elem;entra:=entra+1;contador:=contador+1;endloop;
N:constantinteger:=...;typeelementois...;buffer:array(0..N‐1)ofelemento;entra,sale:modN:=0;contador:integerrange0..N:=0;
looploop exitwhencontador>0;endloop;elem:=buffer(sale);sale:=sale+1;contador:=contador‐1;consumir(elem);endloop;
Productor Consumidor
12
Problema al modificar datos compartidos
Ambas rutinas son correctas si se ejecutan por separado pero podrían NO funcionar si se ejecutan de manera concurrente
Supongamos que contador contiene en un momento dado el valor 5 y que las instrucciones “contador=contador+1” y “contador=contador-1” se ejecutan de forma concurrente (¡contador podría ser 4, 5 o 6!)
contador = contador + 1 contador=contador-1 registro1 := contador; registro2 := contador; registro1 := registro1 +1; registro2 := registro2 -1; contador : registro1; contador := registro2;
T0: productor registro1 := contador (registro1= 5)T1: productor registro1 := registro1+1 (registro1 = 6)T2: consumidor registro2 := contador (registro2 = 5)T3: consumidor registro2 := registro2 -1 (registro2 = 4)T4: productor contador := registro1 (contador = 6)T5: consumidor contador := registro2 (contador = 4)
13
Sección crítica: modelo del sistema N procesos intentan acceder a un recurso
compartido en un bucle infinito:loopSección_No_Crítica(SNC);Pre_Protocolo;Sección_Crítica(SC);Post_Protocolo;endloop;
Sección crítica: segmento de código donde se accede a datos compartidos con otros procesos
15
Sección crítica: modelo del sistema (2) Nunca puede haber más de un proceso en la
sección crítica (exclusión mutua) Los pre y post protocolos serán algoritmos para
garantizar que se cumple la exclusión mutua
16
Requisitos de la solución
Exclusión mutua Progreso: si ningún proceso está en sección
crítica y hay procesos que desean entrar en su s.c., sólo estos últimos participarán en la decisión y ésta se tomará en un tiempo finito.
Espera limitada: hay un límite para el número de veces que otros procesos pueden adelantarse a un proceso que quiere entrar en s.c.
17
Importante
Suponemos que cada proceso se ejecuta a una velocidad distinta de cero
No podemos hacer suposiciones acerca de las velocidades relativas de los procesos
18
Solución trivial: cortar la multiprogramación Si suspendemos la multiprogramación,
desaparece el problema de acceso a los datos compartidos…
…pero perdemos todas las ventajas de la multiprogramación
Hay que buscar una solución menos radical
19
Solución del hardware:inhibir las interrupciones Antes de que un proceso entre en su sección
crítica, se inhiben las interrupciones Así es imposible que el proceso sea
expulsado de la CPU mientras está accediendo al dato compartido
Al salir de la SC, se rehabilitan las interrupciones
20
Inhibir las interrupciones: problemas Mientras un proceso está en SC, se
suspende toda la concurrencia en el sistema no se le da oportunidad a otros procesos que no están accediendo al recurso compartido
Esta técnica no se puede implementar en un multiprocesador
21
Soluciones con espera activa
La sincronización se basa en que un proceso espera mediante la comprobación continua de una variable, manteniendo ocupada la CPU.
Soluciones Software Soluciones Hardware
22
Intento ingenuo:usar un indicador de disponibilidad
23
‐‐variableglobal‐‐indicasilaseccióncríticaestálibrelibre:boolean:=true;
‐‐códigoqueejecutacadaprocesoloop…secciónnocrítica…loopexitwhenlibre;endloop;libre:=false;…seccióncrítica…libre:=true;endloop;
loopSNC2;loopexitwhenturno=2;
endloop;SC2;turno:=1;endloop;
loopSNC1;loopexitwhenturno=1;endloop;SC1;turno:=2;endloop;
Primer intento serio:variable turno
turno:positiverange1..2:=1;
24
(solución para dos procesos)
proceso 1 proceso 2
loopSNC1;loopexitwhenlibre2;endloop;libre1:=false;SC1;libre1:=true;endloop;
loopSNC2;loopexitwhenlibre1;endloop;libre2:=false;SC2;libre2:=true;endloop;
Segundo intento: avisadores
libre1,libre2:boolean:=true;
26
proceso 1 proceso 2
Tercer intento
loopSNC1;libre1:=false;loopexitwhenlibre2;endloop;SC1;libre1:=true;endloop;
loopSNC2;libre2:=false;loopexitwhenlibre1;endloop;SC2;libre2:=true;endloop;
libre1,libre2:boolean:=true;
27
proceso 1 proceso 2
loopSNC1;libre1:=false;turno:=2;loopexitwhenlibre2or turno=1;endloop;SC1;libre1:=true;endloop;
loopSNC2;libre2:=false;turno:=1;loopexitwhenlibre1or turno=2;endloop;SC2;libre2:=true;endloop;
Algoritmo de Peterson - ¡¡FUNCIONA!! libre1,libre2:boolean:=true; turno:positiverange1..2:=1;
28
loop–‐códigodelproceso“i”Secciónnocrítica(i);cogiendonumero(i):=true;num(i):=1+MAX(num(1)...num(n));cogiendonumero(i):=false;forjin1..Nlooploopexitwhennotcogiendonumero(j);endloop;loopexitwheni=jornum(j)=0ornum(j)>num(i)or(num(j)=num(i)andj>i);endloop;endloop;Seccióncrítica(i);numero(i):=0;endloop;
Solución para N procesos: Algoritmo de la panadería (Lamport)
cogiendonumero:array(1..N)ofboolean:=(others=>false);num:array(1..N)ofnatural:=(others=>0);
29
Soluciones hardware
Inhibir interrupciones (muy drástico)
Instrucciones atómicas test-and-set o SWAP.
30
Instrucciones atómicas
Inventadas en los años 60. Permiten evaluar y asignar un valor a una
variable de forma atómica. test-and-set(B): Pone B a true y devuelve el antiguo
valor de B. (Evaluar-y-Asignar(B)) SWAP(A,B): Intercambia los valores de A y B.
(Intercambiar(A,B)) Si disponemos de estas instrucciones, se
simplifica muchísimo el problema de la sección crítica.
31
Ejemplos de algoritmos
loopSecciónnocrítica;loopexitwhenTest_and_Set(llave)=false;endloop;Seccióncrítica;llave:=false;endloop;
loopSecciónnocrítica;aux:=true;‐‐¡variablelocal!loopSwap(llave,aux);exitwhenaux=false;endloop;Seccióncrítica;llave:=false;endloop;
32
usando test-and-set
usando swap
Solución completa (test-and-set)
j:modN;llave:boolean;loopSNCi;esperando(i):=true;llave:=true;whileesperando(i)andllaveloopllave:=Test_and_Set(cerradura);endloop;esperando(i):=false;
SCi;j:=i+1;while(j/=i)andnotesperando(j)loopj:=j+1;endloop;ifj=ithencerradura:=false;elseesperando(j):=false;endif;endloop;
esperando:array(0..N‐1)ofboolean:=(others=>false); cerradura:boolean:=false;
33
Semáforos
Edsger Dijkstra, 1965 Objetivo: herramienta universal para
sincronizar procesos, que sirva como componente básico para construir algoritmos concurrentes
35
Concepto de semáforo
Dijkstra lo definió como una variable entera S con dos operaciones atómicas:
P(S): esperar a que S>0; S:=S-1;
V(S): S:=S+1;
NOTA: el semáforo no puede adquirir valores negativos
36
Semáforos: otras notaciones
P(s) = wait(s) = espera (s) V(s) = signal(s) = señal (s)
(se utilizan varias notaciones para las operaciones de los semáforos, pero significan lo mismo)
37
Ejemplo: sección crítica resuelta con semáforos Usamos un único semáforo inicializado a
uno.beginSecciónnocríticawait(s)Seccióncríticasignal(s)end;
38
Semáforos: esperar por eventos y condiciones Se asocia un semáforo, inicializado a cero, al evento
por el que queremos esperar. Cuando un proceso ha hecho que se cumpla una determinada condición, lo indica ejecutando un signal(c). Un proceso esperará a que la condición sea cierta mediante un wait(c).
P1beginS1;signal(c); S2;end;
P2beginR1;wait(c); R2;end;
39
Semáforos: ejercicios
Ejercicios a.-) Resolver el problema de la sección crítica con n
procesos b.-) Resolver diversos problemas de sincronización
b.1.-) Sean P1 y P2 dos procesos concurrentes. Modificar el código de ambos procesos de forma que el conjunto de sentencias R2 del proceso 2 se ejecute después de que se
P1beginS1;S2;end;
P2beginR1;R2;end;
40
Semáforos: ejercicios b.2.-) Realizar un pequeño programa que se
ajuste al siguiente diagrama (o grafo) de precedencia (suponiendo que disponemos de las herramientas siguientes: sentencia concurrente cobegin/coend )
A
B
C
D
41
Semáforos: ejercicios
b.3.-) Realizar un pequeño programa que se ajuste al siguiente diagrama (o grafo) de precedencia (suponiendo que disponemos de las herramientas siguientes: sentencia concurrente cobegin/coend y semáforos)
A
B
C
D
42
Semáforos:implementación con espera activa
wait(s):whiles<=0donada;s:=s‐1;
signal(s):s:=s+1;
43
También llamados spinlocks
Semáforos:implementación sin espera activa Suponemos que el SO proporciona unas operaciones
para bloquear y desbloquear procesos
typeSemáforoisrecord valor:integer; L:Lista<Proceso>;endrecord;
signal(s): s.valor:=s.valor+1;ifs.valor<=0thenL.extraer(proceso);despertar(proceso);endif;
wait(s):s.valor:=s.valor‐1;ifs.valor<0thenL.insertar(procesoActual);bloquear(procesoActual);endif;
44
Semáforos: la implementación debe garantizar atomicidad Es crítico que las operaciones se ejecuten
de forma atómica Entorno uniprocesador:
Inhibir interrupciones Entorno multiprocesador:
Instrucciones hardware especiales Aplicar un algoritmo de sección crítica con
espera activa
45
Semáforos binarios
Los semáforos vistos reciben el nombre de semáforo general o semáforo de conteo
Un semáforo que sólo puede tomar los valores 0 y 1 recibe el nombre de semáforo binario
46
Problemas clásicos de sincronización Problema del búfer limitado Problema de los lectores y escritores
1er problema: prioridad para los lectores 2º problema: prioridad para los escritores
Problema de los filósofos comensales
48
Búfer limitado
loop...producirunelementoelem...espera(vacio);espera(cerradura);buffer(entra):=elem;entra:=entra+1;señal(cerradura);señal(lleno);endloop;
N:constantinteger:=...;typeelementois...;buffer:array(0..N‐1)ofelemento;entra,sale:modN:=0;lleno:semaforo:=0;vacio:semaforo:=N;cerradura:semaforo:=1;
loopespera(lleno);espera(cerradura);elem:=buffer(sale);sale:=sale+1;señal(cerradura);señal(vacio);...consumirelementoelem...endloop;
Productor Consumidor
49
Lectores y escritores
Esquema útil para gestionar el acceso a una base de datos: Puede haber varios lectores accediendo a la BD
de forma concurrente Sólo puede haber un escritor trabajando No puede haber lectores y escritores al mismo
tiempo … y si se puede, que no haya inanición
50
Lectores y escritores:dos variantes Primera variante: prioridad para los lectores
Si un escritor está esperando, se le pueden adelantar otros lectores
Ojo, riesgo de inanición para los escritores Segunda variante: prioridad para los
escritores Si hay escritores esperando por la BD, los
lectores que van llegando nuevos se deben esperar hasta que todos los escritores finalicen
Ahora hay riesgo de inanición para los lectores
51
Lectores y escritores: 1ª variante
loopespera(cerradura);nlectores:=nlectores+1;ifnlectores=1thenespera(escritura);señal(cerradura);LEERDELABD;espera(cerradura);nlectores:=nlectores‐1;ifnlectores=0thenseñal(escritura);señal(cerradura);endloop;
cerradura:semaforo:=1;escritura:semaforo:=1;nlectores:natural:=0;
loopespera(escritura);ESCRIBIRENLABD;señal(escritura);endloop;
Lector Escritor
52
Lectores y escritores: 2ª variante
53
espera(cerrojo);whileescribiendoornesc>0loopseñal(cerrojo);espera(cerrojo);endloop;nlec:=nlec+1;señal(cerrojo);…leerdelaBD…espera(cerrojo);nlec:=nlec–1;señal(cerrojo);
cerrojo:Semáforo:=1;escribiendo:boolean:=false;nlec,nesc:natural:=0;
espera(cerrojo);nesc:=nesc+1;whileescribiendoornlec>0loopseñal(cerrojo);espera(cerrojo);endloop;nesc:=nesc‐1;escribiendo:=true;señal(cerrojo);…escribirenlaBD…espera(cerrojo);escribiendo:=false;señal(cerrojo);
LectorEscritor
Los filósofos: modelo simple
loopespera(palillo(i));espera(palillo(i+1mod5));...COMER;...señal(palillo(i));señal(palillo(i+1mod5);...PENSAR;...endloop;
palillo:array(0..4)ofsemaforo:=(others=>1);
55
Filósofos: ojo al interbloqueo
La solución anterior puede entrar en un estado de bloqueo mutuo entre todos los filósofos interbloqueo
Posibles soluciones: Algoritmo asimétrico filósofos pares/impares Impedir a más de cuatro filósofos entrar a pedir
los palillos Coger los dos palillos de forma atómica (o coges
los dos, o no coges ninguno)
56
Los semáforos ayudan, pero tienen limitaciones…
Los semáforos son una herramienta de bajo nivel, que requiere un uso disciplinado y cuidadoso.
Es muy fácil cometer errores de uso con semáforos.
Veamos algunos ejemplos…
57
¿dónde está el fallo?
Sem=1
voidrutina_en_exclusion_mutua(){P(Sem)…códigodeseccióncríticaif(error)return;…máscódigodeseccióncríticaV(sem)}
59
Más problemas…
Proceso 1P (impresora)P ( disco ) … usar disco e impresoraV (disco)V (impresora)
Proceso 2P (disco)P ( impresora ) … usar disco e impresora
V (impresora)V (disco)
60
Dos procesos que acceden a recursos compartidos:¿qué ocurre al ejecutarlos al mismo tiempo?
Herramientas de alto nivel
Objetivo: introducir en el lenguaje de programación herramientas de sincronización que sean más seguras que los semáforos
Ejemplos: Regiones críticas Monitores y variables condición
61
Regiones críticas condicionales
Abstracción de un bloque de código que accede a recursos compartidos.
Garantiza exclusión mutua. El código sólo se ejecuta si la condición
asociada a la región crítica es cierta. Ejemplo:
regionBúferwhenNelementos>0{//estecódigoseejecutaenexclusiónmutua//ysóloseejecutasiNelementos>0…consumirunelementodelbúfer…Nelementos=Nelementos–1;}
62
Regiones críticas condicionales
Se plantearon en 1972 (Brinch Hansen, Pascal Concurrente)
Gran fuerza expresiva, el código queda mucho más legible y compacto
Problema: implementación muy costosa, comparada con el código escrito a mano con semáforos
Por ese motivo, nunca llegaron a prosperar como herramienta de uso común
63
Monitor
Propuesto por Hoare (1972) Tipo abstracto de datos
Estructura de datos privada Operaciones públicas
+ Exclusión mutua Sincronización (variables condición)
65
Monitor: ejemplo básico
66
monitorContador{//operacionespúblicaspublicContador(){valor=0;}publicvoidincrementa(){valor++;}publicintactual(){returnvalor;}
intvalor;//variableinternaprivada};
Contador.incrementa();V=Contador.actual();
Si varios procesos intentan manipular el monitor almismo tiempo, van entrando de uno en uno: no puedehaber más de un proceso trabajando con el monitor encada momento.
Variables condición
Una variable condición sirve para gestionar una cola de espera por el monitor
Dos operaciones x.wait bloquea al proceso y lo mete en la cola “x”
x.signal desbloquea a un proceso de la cola “x”; si no hay procesos en “x”, no hace nada
68
Variables condición: ejemplo
69
monitorContador{Conditioncola;publicContador(){valor=0;}
publicvoidBloqueaHastaQueValgaDiez(){if(valor<10){cola.wait();}}
publicvoidIncrementa(){valor++;if(valor==10){cola.signal();}}
intvalor;};
Monitor con variables condición
código de inicialización
xy
datos compartidos
colas asociadas a las variables condición x e y
cola de ingreso
...
operaciones
70
Qué ocurre tras un “signal”
¿ Qué ocurre cuando un proceso P realiza una operación signal sobre una variable condición x y existe un proceso suspendido Q asociado a dicha variable?
Estilo Hoare se reanuda Q inmediatamente Estilo Mesa Q se desbloquea, pero espera a que
P abandone el monitor El estilo Mesa es el más utilizado en los
lenguajes de programación actuales
71
Qué ocurre tras un “signal” (2)
Si varios procesos están suspendidos por la condición x y algún proceso ejecuta x.signal, ¿ qué proceso se reanuda? FIFO desbloqueamos al más antiguo Por prioridades conveniente en sistemas de
tiempo real
72
Ejemplo: un semáforo implementado con un monitor
73
monitorSemáforo{intvalor;Conditioncola;
publicSemáforo(intval){valor=val;}
publicvoidP(){while(valor==0){cola.wait();}valor‐‐;}
publicvoidV(){valor++;cola.signal();}};
Ejemplo: búfer limitado
74
monitorBúfer{ConditionhayHuecos,hayItems;intnitems=0;constintN=…;
publicvoidinsertar(Itemx){while(nitems==N){hayHuecos.wait();}…introducirxenelbúfer…nitems++;hayItems.signal();}
publicItemextraer(){while(nitems==0){hayItems.wait();}Itemx=…extraealgo…nitems‐‐;hayHuecos.signal();returnx;}};
Cómo se implementa un monitor
75
monitorMiMonitor{publicvoidoper1(…){…}publicvoidoper2(…){…}};
classMiMonitor{Semáforocerrojo=1;publicvoidoper1(…){cerrojo.P();…cuerpodeoper1…cerrojo.V();}publicvoidoper2(…){cerrojo.P();…cuerpodeoper2…cerrojo.V();}};
El compilador generaun código parecido a este:
El cerrojo garantiza que nopuede haber más de un procesodentro del monitor
Cómo se implementa un monitor:variables condición
76
monitorMiMonitor{Conditionc;…c.wait();…c.signal();…};
monitorMiMonitor{Semáforocerrojo=1;
Semáforoc_queue=0;intc_count=0;
c_count++;cerrojo.V();//1.liberoelmonitorc_queue.P();//2.mebloqueoenlacolacerrojo.P();//3.cuandomedesbloqueen//deborecuperarelmonitor
if(c_count>0){//sihayalguienesperandoc_count‐‐;//lodesmarcoc_queue.V();//ylodesbloqueo}
Lectores y escritores (1)
78
monitorBaseDatos{publicEmpiezaLectura(){…}publicTerminaLectura(){…}publicEmpiezaEscritura(){…}publicTerminaEscritura(){…}};
voidLeer(){//LoquedebeejecutarunlectorBaseDatos.EmpiezaLectura();…leerdelaBD…BaseDatos.TerminaLectura();}
voidEscribir(){//LoquedebeejecutarunescritorBaseDatos.EmpiezaEscritura();…escribirenlaBD…BaseDatos.TerminaEscritura();}
Lectores y escritores (2)
79
monitorBaseDatos{Conditionleer,escribir;intnlec=0,lecesperan=0;boolescribiendo=false;
publicEmpiezaLectura(){while(escribiendo){lecesperan++;leer.wait();lecesperan‐‐;}nlec++;leer.signal();//desbloqueaencadenaalresto}
publicTerminaLectura(){nlec‐‐;if(nlec==0){escribir.signal();}}
Lectores y escritores (y 3)
80
publicEmpiezaEscritura(){while(nlec>0||escribiendo){escribir.wait();}escribiendo=true;}
publicTerminaEscritura(){escribiendo=false;if(lecesperan>0){leer.signal();}else{escribir.signal();}}
};
Filósofos (1): especificación del monitor
81
monitorMesaFilósofos{
//estadointernodelsistemaconstintN=5;ConditionpuedeComer[N];enumEstado{pensando,hambriento,comiendo};Estadoestado[N]={others=>pensando};
//operacionespúblicas(versiguientespáginas)publicCogePalillos(intfilosofo){…}publicSueltaPalillos(intfilosofo){…}
//operaciónauxiliarinternaprivatecompruebaQuePuedeComer(intfilosofo){…}};
Filósofos (2): ejemplo de uso
82
voidVidaDelFilósofo(intunFilosofo){
loop{piensaUnPoco();MesaFilósofos.CogePalillos(unFilosofo);comeArroz();MesaFilósofos.SueltaPalillos(unFilosofo);}}
Filósofos (3): rutina auxiliar
83
//operaciónprivadadentrodelmonitorMesaFilósofos
privatecompruebaQuePuedeComer(intfilosofo){
intvecinoDerecha=(filosofo+1)%N;intvecinoIzquierda=(filosofo‐1+N)%N;if(estado[vecinoIzquierda]!=comiendo&&estado[vecinoDerecha]!=comiendo){estado[filosofo]=comiendo;puedeComer[filosofo].signal();}}
Filósofos (y 4): operaciones públicas del monitor
84
publicCogerPalillos(intfilosofo){estado[filosofo]=hambriento;compruebaQuePuedeComer(filosofo);if(estado[filosofo]!=comiendo){puedeComer[filosofo].wait();}}
publicSoltarPalillos(intfilosofo){estado[filosofo]=pensando;intvecinoDerecha=(filosofo+1)%N;intvecinoIzquierda=(filosofo‐1+N)%N;compruebaQuePuedeComer(vecinoDerecha);compruebaQuePuedeComer(vecinoIzquierda);}