Semáforos
.png)
Cuaderno completo con este tema:
SEMAFOROS
Los semáforos son un instrumento de sincronización a bajo nivel.
Inventados por Dijkstra, son primitivas bloqueantes. Están directamente relacionadas con el Scheduller del SO, pasando al y volviendo del estado bloqueado.
En el estado bloqueado no se asigna procesador, con lo cual se optimiza.
Los semáforos tienen 3 operaciones fundamentales. INIT, P y V.
https://es.wikipedia.org/wiki/Sem%C3%A1foro_(inform%C3%A1tica)
Los semáforos son un TAD: un dominio y operaciones de manipulación.
- INIT hace un seteo de capacidad inicial, la cual puede después aumentar o disminuir.
Ejemplo
S:semáforo
init(s,4)
Sintaxis: init(s,valor)
En el problema de Alice & Bob el semáforo que arbitre el patio tendrá su seteo inicial en 1, siendo ésta la capacidad del patio. Va a dejar pasar de a un proceso por vez al patio, dada esta condición.
- P hace uso de la capacidad del semáforo, SI ESTA DISPONIBLE; si no, se bloquea.
- V devuelve capacidad del semáforo.
Un posible código explicativo para P(s)
If s=0
Then bloqueo asociado al semáforo s
Else s - -
End
Un posible código explicativo para V(s)
If (existe proceso esperando por s)
Then desbloquear uno cualquiera
Else s++
End
Las operaciones Init, P y V deben ejecutarse de forma INDIVISIBLE. No me pueden quitar el procesador a mitad de P o de V.
Ejercicio
Resolver el problema de la mutua exclusión con semáforos.
LO PRIMERO QUE DEBEMOS IDENTIFICAR SON LOS PROCESOS Y LOS RECURSOS. CUAL ES CUAL.
- Cuáles son los procesos?
Alice y Bob
- Cuáles son los recursos?
El patio, el cual es un RSR. Patio lo arbitraremos con un semáforo s, inicializado en 1, que es la capacidad del patio. Alice y Bob usarán el patio, para ello deben pedirlo, usarlo y devolverlo.
- Cuál es la sección crítica ?
Pasear al perro.
- Hay sección asincrónica?
Sí, el hacer otras tareas.
- Cuántos semáforos precisamos?
Uno por recurso (en principio, luego puliremos más este concepto), en este caso uno asociado al patio.
- En cuánto se inicializan?
En la capacidad del patio, o sea 1.
- Cuándo se hace P y cuándo V ?
Antes de salir al patio hacemos P y al devolver hacemos V.
Armar el código…
Ya no preciso más banderas ni carteles, pues el semáforo hace todo…
Un detalle del semáforo: nosotros pedimos pasar y si no se puede, nos bloquea… lo que no vale, es espiar el valor del semáforo para ver si pasar o no.
Proc Main
Variables
S: semáforo
Init(s,1) // aquí estoy seteando la capacidad del patio.
Cobegin
Alice
Bob
coend
end Main
Proc Alice
While true do
1 P(s)
2 Paseo perro Alice
3 V(s)
4 Otras_tareas_Alice
endwhile
End Alice
Proc Bob
While true do
1’ P(s)
2’ Paseo perro Bob
3’ V(s)
4’ Otras_tareas_Bob
endwhile
End Bob
Observaciones
- P y V están implementadas a nivel del núcleo del SO, ejecutan de forma indivisible, con una explicación del código tal como se puso más arriba.
- El bloqueo por semáforos y su correspondiente desbloqueo está atado directamente al scheduller.
- Se implementan en base a primitivas del estilo de fork/join que las vamos a estudiar dentro de un tiempo, o si no en base a primitivas de Assembler, del estilo del test_And_Set que es una instrucción que en forma indivisible analiza un valor y setea otro en función del primero.
- El semáforo, de algún modo, es una porción de memoria compartida, arbitrada muy estrictamente por el SO.
- El proceso que hace P(s) o bien se bloquea o bien pasa y le dan el recurso. No elije, obvio.
- El proceso a despertar entre los bloqueados, de acuerdo a la definición estricta del TAD, se selecciona al azar. Sin embargo el azar en informática es un problema… en lugar de eso casi siempre se usan filas comunes, lo cual es simple de implementar, barato respecto al consumo de recursos y garantiza que no habrá aplazamiento indefinido.
- Si hay un V(s) y ese semáforo tiene procesos asociados esperando, se despierta uno, y el semáforo continúa en 0.
- Cada semáforo tendrá una lista de procesos bloqueados asociados a él.
Un video con una ilustración de los números aleatorios y los números pseudo aleatorios nos muestra una primera arista del problema que hay detrás de decir “los números aleatorios son una complicación” y lo son… al punto de que en nuestros algoritmos a lo largo del curso, les huiremos…
Ejercicios extra
*** Modificar el código anterior para que sean Alice , Bob y Charlie… el patio tiene capacidad 1.
Charlie es análogo a Alice y Bob. Nada más que agregar al código.
*** Modificar el código anterior de modo que sean A&B&C pero el patio tiene capacidad 2.
Inicializamos el semáforo en 2 y nada más.
Init(s,2)
¿ Se imaginan lo difícil de modificar los algoritmos, cualquiera de ellos, basados en busy waiting, para esto ?...
En cambio con semáforos es extremadamente simple.
Detalles:
- Cada semáforo tiene SUS procesos bloqueados.
- Las operaciones son indivisibles.
- El INIT nos da la capacidad inicial del semáforo, que luego puede ser modificada.
- No hay forma de saber si hay capacidad o no, se procede de modo tal que si no hay capacidad me bloquea.
- No preguntamos, en general si hay capacidad. En lugar de eso pedimos capacidad y si hay pasamos y si no hay esperamos bloqueados.
Ejercicio:
Patio capacidad 1 y 2.
A B y C, tiran una moneda y si sale cara llevan su perro al patio 1, sino al patio 2.
Proc Main
Variables
s1, s2:semáforo
Begin
Init(s1,1)
Init(s2,2)
Cobegin
Alice
Bob
Charlie
Coend
Proc Alice //Bob & Charlie son ANALOGOS
While true do
If (Tiromoneda()=’Cara’
Then
P(S1)
PaseoperroAlicepatio1
V(S1)
Else
P(S2)
paseoperroAlicepatio2 síncrono
V(s2)
Endif
Otras_tareas_Alice asíncrono
endwhile
End Alice
Proc Bob…. ANALOGO
Proc Charlie …. ANALOGO
A los semáforos les analizaremos el poder expresivo.
Veremos más problemas clásicos: productor/consumidor, lectores y escritores, filósofos comensales.
Los semáforos los vemos en el LP (lenguaje de programación) por alguna clase semáforo que incorporamos.
Son parte del núcleo del SO. Es decir que ese código de las funciones o de las clases de la library de semáforos que incorporemos, va a interactuar directamente con el núcleo del sistema operativo.
Análisis del poder expresivo de cobegin/coend + semáforos.
Cobegin/coend + semáforos tiene el mismo poder expresivo que los grafos de precedencias.
Vamos a mostrarlo (no a demostrarlo), dando un método por medio del cual lleguemos, dado cualquier grafo de precedencias, a su expresión por medio de cobegin/coend + semáforos.
Hagamos un ejemplo.
- Identificamos las aristas a sincronizar.
Etiqueté de a a e.
- Asignamos 1 semáforo por cada arista, inicializando en 0.
- Armamos un cobegin coend con todo.
- En cada línea del cobegin coend, va un proceso, que tiene P de todas las aristas previas, ejecuta, y V de todas las aristas posteriores.
Por qué incializamos en cero ?
Dentro del cobegin / coend, no sabemos cómo será la secuencia de reparto de procesador. Entonces, no sabemos qué procesos llegarán primero.
Supongamos que llega primero el último, que tiene P(c), P(d) y F…. entonces, como los semáforos están en cero, están listos para bloquearlo.
A quién no bloquean ? A los que no tienen P, y por ahí comienza, y luego va liberando, ordenadamente, al irse ejecutando los V.
Con este método, cualquier grafo puede ser descripto en términos de cobegin/coend y semáforos. Entonces se ha logrado igualar el poder expresivo. Resultado muy importante. Pues nos garantiza completitud de la herramienta respecto a la cantidad de problemas abarcados.
Ejercicio.
Describir con Cobegin/coend y semáforos.
Si ponemos absolutamente todas las aristas, y un semáforo por cada una, el método funciona.
Pero buscaremos una forma más eficiente…
Variables
a,b,c,d,e,f,g: semáforo
init(a,0)
init(b,0)
…….
Init(f,0)
Init(g,0)
Cobegin
Begin K; L end
Begin A ; V(a) ; V(b) end
Begin P(a) ; B end
Begin P(b) ; P(c) ; C ; V(e) end
Begin D ; V(c) ; V(e) end
Begin P(d) ; E ; V(f) end
Begin P(e) ; P(f) ; P(g) ; F end
Begin G ; H ; I ; V(g) end
coend
Optimización (correcta) propuesta por Tadeo
Variables
b,c,d,e,f,g: semáforo
init(b,0)
init(c,0)
init(e,0)
Init(f,0)
Init(g,0)
Cobegin
Begin A ; V(b) ; B end //eliminó la arista A, y autorizó B ni bien terminó A.
Begin P(b) ; P(c) ; C ; V(e) end
Begin D ; V(c) ; E ; V(f) ;end
Begin P(e); P(f) ; P(g) ; F end
Begin G ; H ; I ; V(g) end
Begin K; L end
coend
También podría poner las 10 aristas, 10 semáforos y esto funciona perfecto.
Este método un poco “aplanadora”, en realidad es el más sencillo de generar automáticamente, así que tan malo no es…
Quedó probado (mostramos) que el poder expresivo de cobegin/coend y semáforos es lo que buscamos, ya que iguala el poder expresivo de los grafos de precedencias.
Otro ejemplo
a,b,c:semáforo
init(a,0)
init(b,0)
init(c,0)
cobegin
begin A; V(a) end
begin B; V(b) ; V(c) end
begin P(a);P(b);C end
begin P(c);D end
coend
Versión optimizada
a,b:semáforo
init(a,0)
init(b,0)
cobegin
begin A; V(a) end
begin B; V(b) ; D end
begin P(a);P(b);C end
coend
f es transitiva , no la precisamos, la eliminamos
JK quedó como bloque luego de eliminada f, así que k se va su semáforo
a,b se eliminaron por cobegin coend, se va su semáforo
g se eliminó por optimización, se va su semáforo
c, d, e se eliminaron por cobegin coend, se van sus semáforos
h,i,j:semáforo
init(h,0)
init(i,0)
Init(j,0)
Cobegin
Begin cobegin A;B coend F ;V(h);H end
Begin P(h); I ; V(i) end
Begin P(i);P(j);J;K end
Begin cobegin C;D;E coend G;V(j)
Coend
Problema del Productor Consumidor
Este problema ocurre todo el tiempo dentro del sistema operativo, en todo lo que involucre buffers.
Un buffer es un área de memoria intermedia, provisoria, usada durante un tiempo relativamente corto, para intercambiar información entre (en este caso) procesos.
Hay procesos que colocan datos en el buffer, y otros que extraen datos del buffer. Los procesos que colocan datos son los productores. Los procesos que extraen datos son los consumidores.
Hay varios detalles a tener en cuenta:
- El buffer tiene una capacidad finita.
- Pueden ser varios productores.
- Pueden ser varios consumidores.
- Al buffer se debe acceder bajo mutua exclusión.
- Se debe respetar un orden ------ el buffer es una cola, es decir, una fila, es decir First In First Out.
- No se puede insertar si buffer está lleno.
- No se puede extraer si el buffer está vacío.
Lo primero que analizaremos será una estructura para el buffer, la cual llamaremos COLA CIRCULAR, y es una implementación de cola muy útil cuando la cantidad de elementos de la misma está acotada.
Las operaciones prioritarias son las de cola: insertar al final de la fila, extraer el primero de la fila.
Usaremos un array, dos índices y una variable para guardar la cantidad de elementos insertados.
Para una cola de hasta N elementos de tipo T:
- Un array, llamado pool, de N elementos, indexados de 0..N-1
- Un índice indicando el próximo lugar libre, llamado p_a_i (próximo a insertar), variando entre 0 y N-1.
- Un índice indicando el próximo elemento para extraer (el primero de la fila), llamado p_a_e (próximo a extraer), variando entre 0 y N-1.
- Un indicador de cantidad de elementos, variando entre 0 y N.
- Este indicador no sería estrictamente necesario, bastaría con un Bool, pues los casos que se superponen son los de lleno y vacío.
Queda con el siguiente pseudocódigo:
Cola_circular es:
Estructura tupla, significa estructurado, struct, record, o sea una agrupación de las siguientes cosas:
Pool: array [0..N-1] de T
p_a_i, p_a_e : 0..N-1 inicializados en 0
cant : 0..N inicializado en 0
Fin estructura
Sus funciones de manejo son insertar_al_final y extraer_primero:
Insertar_al_final (in x:T)
Pre: La cola no está llena.
Pool [p_a_i]=x
p_a_i=(p_a_i+1) mod N // varía entre 0 y N-1
cant ++
fin Insertar
Extraer_primero (out x:T)
Pre: La cola no está vacía.
x=Pool [p_a_e]
p_a_e=(p_a_e+1) mod N // varía entre 0 y N-1
cant --
fin Extraer
Teniendo lista la estructura, discutamos ahora la resolución del problema del productor consumidor.
Cuáles son los procesos? Los productores y los consumidores.
Cuáles son los recursos? El buffer.
Cuáles son las condiciones de sincronización?
- Mutua exclusión
- Buffer lleno
- Buffer vacío
Usaremos 3 semáforos. Uno para cada condición de sincronización.
- Para mutua exclusión un semáforo s inicializado en 1
- Bloquea si el buffer está siendo usado por un P o por un C.
- Para lleno, un semáforo e inicializado en N
- Bloquea si el buffer está lleno.
- Para vacío, un semáforo n inicializado en 0
- Bloquea si el buffer está vacío. Arranca haciéndolo, ya que está inicializado en 0 (arranca vacío el buffer).
Esbozo del código del productor y el consumidor:
Productor
Repetir siempre:
Producir dejando en una variable x ---- ASINCRÓNICO
Insertar x en el buffer ------- SINCRÓNICO
Fin
Consumidor
Repetir siempre:
Extraer del buffer dejando el valor en una variable x ------- SINCRÓNICO
Consumir x ---- ASINCRÓNICO
Fin
Producir podría ser leer de teclado.
Consumir podría ser desplegar en una pantalla.
Hay varios ejemplos asimilables a este problema dentro del SO:
- Cuando vemos un video de youtube: el productor deja en un buffer, el consumidor manda al player.
- Cuando quemamos un DVD: el productor deja en el buffer, el consumidor toma de ahí y va quemando.
- Cuando imprimimos: el producto toma de la cola de impresión, el consumidor imprime en la impresora.
Seudocódigo:
Estructuras:
Cola_circular es:
Estructura record:
Pool: array [0..N-1] de T
p_a_i, p_a_e : 0..N-1 inicializados en 0
cant : 0..N inicializado en 0
Fin estructura
Insertar_al_final (in x:T)
Pre: La cola no está llena.
Pool [p_a_i]=x
p_a_i=(p_a_i+1) mod N // varía entre 0 y N-1
cant ++
fin Insertar
Extraer_primero (out x:T)
Pre: La cola no está vacía.
x=Pool [p_a_e]
p_a_e=(p_a_e+1) mod N // varía entre 0 y N-1
cant --
fin Extraer
Main
Variables:
Buffer: cola_circular
s,e,n:semáforo
init(s,1) //mutua exclusión
init(e,N) //lleno
init(n,0) //vacío
cobegin //podría ser más de un prod y más de un cons
Productor
Consumidor
coend
Productor
Variable:
x:t
While true do
Producir(x) //asincrónico, no precisa nada
P(e) //detenerse si lleno
//si llega acá es porque el buffer no está lleno
P(s) //solicitar mutua exclusión
// en este momento hay lugar, y tengo acceso exclusivo
Insertar_al_final(x)
V(s) //devolver mutua exclusión
V(n) //avisar que está un lugar menor vacío
End
Consumidor
While true do
P(n) //detenerse si vacío
P(s) //solicitar mutua exclusión
Extraer_primero(x) //sincrónico
V(s) //devolver mutua exclusión
V(e) //avisar que está un lugar menos lleno
Consumir(x) // asincrónico
End
Notar que los accesos a la inserción y extracción se hacen cumpliendo las precondiciones, pues el semáforo e detendría en caso de buffer lleno y el semáforo n detendría en caso de buffer vacío. Por otra parte está la mutua exclusión con el semáforo s.
La generalización es inmediata, pues basta replicar los P y los C.
Ejercicio
Sean dos buffers B1 y B2, de hasta 50 Enteros.
Y sean los siguientes procesos P1, P2, P3, P4, concurrentes, que interactúan con dichos buffers.
P1 lee de teclado (read) e inserta en B1.
P4 extrae de B2 e imprime (print).
P2 extrae de B1, eleva al cuadrado e inserta en B2.
P3 extrae de B1, extrae de B2, suma, y si da mayor que 50, inserta en B2.
Se pide armar el seudocódigo de todo esto con semáforos.
B1,B2 son los recursos, ámbos buffers.
P1,P2,P3,P4 son los procesos.
Estructuras:
N=50
Cola_circular es:
Estructura record:
Pool: array [0..N-1] de entero
p_a_i, p_a_e : 0..N-1 inicializados en 0
cant : 0..N inicializado en 0
Fin estructura
Insertar_al_final (in x:entero)
Pre: La cola no está llena.
Pool [p_a_i]=x
p_a_i=(p_a_i+1) mod N // varía entre 0 y N-1
cant ++
fin Insertar
Extraer_primero (out x:entero)
Pre: La cola no está vacía.
x=Pool [p_a_e]
p_a_e=(p_a_e+1) mod N // varía entre 0 y N-1
cant --
fin Extraer
Main
Variables:
B1,B2: cola_circular
s1,e1,n1,s2,e2,n2:semáforo
init(s1,1)
init(e1,N)
init(n1,0)
init(s2,1)
init(e2,N)
init(n2,0)
cobegin
P1
P2
P3
P4
coend
P1 //productor puro respecto a B1
Variable
x:entero
While true do
Read(x)
P(e1)
P(s1)
B1.insertar_al_final(x)
V(s1)
V(n1)
Fin
P2 //consumidor respecto a B1 y productor respecto a B2
Variables
x:entero
While true do
P(n1)
P(s1)
B1.extraer_primero(x)
V(s1)
V(e1)
x=x*x
P(e2)
P(s2)
B2.insertar_al_final(x)
V(s2)
V(n2)
Fin
- Las operaciones, son asincrónicas… deben hacerse fuera de la sección crítica para no sobrecargar las esperas…
- Si las hago en la sección crítica igual funciona, pero es ineficiente, sincroniza de más.
P3 //consumidor respecto a B1 y B2 y productor respecto a B2
Variables:
x1,x2:entero
While true do
P(n1)
P(s1)
B1.extraer_primero(x1)
V(s1)
V(e1)
P(n2)
P(s2)
B2.extraer_primero(x2)
V(s2)
V(e2)
x1=x1+x2
if x1>50
then
P(e2)
P(s2)
B2.insertar_al_final(x1)
V(s2)
V(n2)
finsi
Fin
Ejercicio
B es un buffer de hasta 50 enteros
X es una variable que debe ser tratada bajo mutua exclusión.
Estructura cola circular idéntica al ejercicio anterior.
B: cola_circular
s,e,n,mutex: semáforo // s,e,n son semáforos del buffer y mutex semáforo para la mutua exclusión sobre x.
Main
Init(s,1)
Init(e,N)
Init(n,0)
Init(mutex,1)
cobegin
p1
p2
p3
coend
p1
variables
x1:int
while true do
read(x1)
p(e)
p(s)
b.insertar_al_final(x1)
v(s)
v(n)
end
p2
variables
x1,x2:int
while true do
p(n)
p(s)
b.extraer_primero(x1)
v(s)
v(e)
p(mutex)
x2=x
v(mutex)
if x1>x2
then print(x1)
end
end
En la zona de mutua exclusión debemos trabajar lo menos posible, por un tema de eficiencia.
P3
Variables
x1,x2: int
While true do
P(n)
P(s)
b.extraer_primero(x1)
V(s)
V(e)
P(mutex)
x2=x
V(mutex)
x1+=x2
P(e)
P(s)
b.insertar_al_final(x1)
V(s)
V(n)
end
Problema de los lectores y escritores.
Otro problema clásico, que también ocurre dentro del sistema operativo. Es el problema de los LECTORES y ESCRITORES.
Existe un área compartida, que algunos procesos la acceden con la intención de leerla, son los LECTORES. Otros procesos la acceden con la intención de escribirla, son los ESCRITORES.
Leerla implica acceder a su contenido, pero NO MODIFICAR. Entonces se puede leer de a muchos en simultáneo.
Escribirla, implica modificar su contenido, por lo cual nadie más puede leer y nadie más puede escribir, mientras estamos escribiendo.
Esta asimetría define un muy interesante problema.
Este se da por ejemplo con los archivos compartidos. Herramientas como google docs e incluso Dropbox, deben tener recaudo de este problema.
Algunas vez vieron las “copias en conflicto” de Dropbox…
Este problema nos interesa resolverlo, es decir ARBITRARLO, con semáforos.
Vamos a utilizar un semáforo que llamaremos WRT, para arbitrar, primero que nada, la mutua exclusión entre los propios escritores. Ya que entre escritores, sin considerar los lectores, este queda un problema de mutua exclusión simple: pido recurso, uso recurso, devuelvo recurso.
Vamos a llevar la cuenta de la cantidad de lectores. Esto lo haremos con una variable read_cnt.
El primer lector, luego de incrementar read_cnt queda en 1, debe bloquear para que no entren escritores, pero si dejamos pasar más lectores.
El último lector, luego de decrementar read_cnt queda en 0, debe desbloquear para que sigan entrando todos.
Hay un problema más: nosotros manejamos las variables read_cnt incrementando y decrementando y con un if. Qué pasa si pierdo el procesador a mitad de ese if ? Se arma un lío bárbaro, el cual queremos evitar, se generan inconsistencias, etc.
Entonces los lectores, entre ellos, deben acceder bajo MUTUA EXCLUSION, a ese pedazo del código. Para ello creamos un semáforo mutex, de mutua exclusión.
Main
wrt, mutex: semáforo
read_cnt:int inicializada en 0
init(wrt,1)
init(mutex,1)
cobegin
lector
lector
…..
Escritor
Escritor
……
Coend
Proc Escritor
While true do
P(wrt)
Escribir //Sincrónico
V(wrt)
Tareas asincrónicas del escritor //Asincrónico
End while
End Escritor
Proc Lector
While true do
P(mutex)
Read_cnt ++
If Read_cnt=1
Then
P(wrt)
End if
V(mutex)
Leer
P(mutex)
Read_cnt - -
If Read_cnt=0
Then
V(wrt)
End if
V(mutex)
End while
End Lector
El semáforo mutex arbitra entre lectores.
El semáforo wrt arbitra entre escritores y entre lectores vs escritores.
El mutex evita que los lectores manipulen descontroladamente la variable read_cnt, pues podrían perder el procesador justo entre el ++ y el if, por ejemplo, o dentro de ellos. Con los semáforos no evito que pierda el procesador, pero sí evito que alguien pase a la vez, pues de intentar hacerlo, se frena.
En definitiva, serializamos accesos sobre read_cnt de parte de los lectores utilizando el semáforo mutex.
Pregunta: Esta solución es ecuánime o favorece a lectores o escritores ?
Tiene APLAZAMIENTO INDEFINIDO
Hay aplazamiento indefinido si UN LECTOR logra “colarse” a UN ESCRITOR que esté esperando.
Porque en tal caso, cualquier lector que venga detrás también se colará. Y el escritor quedará en aplazamiento indefinido.
Entonces atención con esta solución, que no es tan buena. Tiene aplazamiento indefinido.
En realidad tenemos un problema, y es que problema de los L y E, con su asimetría, es inherentemente tendencioso a un lado o a otro.
Vamos a hacer una mención al problema de los dos ejércitos… como para tener una idea de algunas asimetrías en este tipo de algoritmos. De nuevo es algo traído del mundo de las redes, de los protocolos de comunicación…
NO TIENE SOLUCION!
Todos estos problemas asimétricos… no tienen solución…
Entonces en el problema de los L y E, no tendremos una solución ecuánime, sino que habrá matices en los que favorezca a unos u otros.
Problema de los filósofos comensales
Por qué lo estudiamos? Porque es un caso de uso de múltiples recursos por parte de procesos. Estos recursos son idénticos, pero están preasignados para ser compartidos/competidos entre subconjuntos de procesos.
Tenemos 5 filósofos sentados a la mesa, y en ella, hay 5 palitos chinos para comer arroz.
Cada uno precisa 2 palitos.
Pero cada palito es compartido con el filósofo de al lado, tanto a la derecha como a la izquierda.
Su vida es pensar y comer , pensar y comer, etc. … repetidamente.
Los palitos se toman y devuelven estrictamente de a 1.
Queremos programarlos para que esto funcione.
Cuáles son los procesos ?
LOS 5 FILOSOFOS.
Cuáles son los recursos ?
LOS 5 PALITOS.
Cómo es la numeración de unos y otros ?
FILOSOFOS DE 0 A 4 Y PALITOS DE 0 A 4
DEPENDIENDO DEL FILOSOFO ES A QUE SEMÁFORO NOS VAMOS A REFERIR.
El filósofo 0 tiene a su izq el palito 0 y a su derecha el palito 1, y así sucesiva y circularmente…
Cuántos semáforos precisamos ?
UNO POR RECURSO, O SEA 5 SEMÁFOROS. LOS PONDREMOS EN UN ARRAY DE 0 A 4 OF SEMAFORO
LOS FILÓSOFOS LOS PODEMOS HACER PARAMETRICOS EN I:0..4, ES DECIR, LE PASO SU NÚMERO DE FILÓSOFO AL LANZARLO EN EL COBEGIN COEND.
LOS palitos ESTÁN EN EL ARRAY, DE 0..4
VAMOS A HACER ESTO:
EL FILOSOFO I_ESIMO, TENDRA A SU IZQUIERDA EL PALITO I_ESIMO, Y A SU DERECHA, EL PALITO (I+1)_ESIMO PERO OJO, ES CIRCULAR ASÍ QUE HAREMOS (I+1) MOD 5, PARA QUE EL DE LA DERECHA DEL 4, SEA EL 0 DE NUEVO.
IZQ FILO DER
0 0 1
1 1 2
2 2 3
3 3 4
4 4 0
Cómo se inicializan ?
ARRANCA DISPONIBLES, SE INICIALIZAN EN 1, problemas de mutua exclusión individuales y circulares.
Qué es lo sincrónico y qué lo asincrónico ?
LO SINCRÓNICO ES TOMAR LOS PALITOS, COMER Y DEVOLVERLOS. PARA COMER TENEMOS QUE TENER LOS PALITOS, O SEA QUE QUEDA ENTRE 2 ACCIONES DE SINCRONIZACIÓN.
LO ASINCRÓNICO ES PENSAR.
No podemos darle prioridad a nadie.
Sabemos que los palitos no alcanzan más que para dos a la vez.
Qué hace cada filósofo en su código?
While true do
Pensar // asincrónico
Pedir palito izq //incluye bloquearse a esperar si no está
Pedir palito derecho
Comer
Devolver palito der
Devolver palito izq
End
En base a esto, que aún no está detallado, tenemos un problema.
Qué pasa en el caso en que los 5 filósofos (a la vez o pseudo a la vez) toman el palito izquierdo?
Qué precisan además del izq? El derecho … y en ese caso… está ocupado, se bloquean.
Quedan los 5 bloqueados… es un deadlock. Que lo mencionamos al comienzo del curso.
Cómo evitamos este deadlock ?
No pueden comer más de 2 a la vez (4 palitos)
Pero en realidad no lo pensamos así. Lo pensamos del otro lado. Es decir: si tengo 5 palitos, tengo el caso de deadlock.
Pero si tengo 5 palitos a repartir entre 4, ya no tengo ese caso.
Entonces tengo que evitar que compitan por los palitos los 5 filósofos a la vez.
Puedo hacerlo repartiendo la posibilidad de los palitos entre los 4 que lleguen primero.
El 5º espera a que alguien coma, y en ese caso toma su lugar, y así sucesivamente.
No estamos perjudicando a ninguno en concreto, y por tanto no estamos sesgando la solución.
Preciso un semáforo extra, llamado comedor, para inicializarlo en 4.
Main
Palitos: array [0..4] of semáforo, inicializado en 1
Comedor: semáforo, inicializado en 4
k:0..4
For k en 0..4
Init (palitos [k],1)
endfor
Init(comedor,4)
Cobegin
Filosofo(0)
…
Filósofo(4)
Coend
End Main
Proc Filósofo(in i:0..4)
Izq=i
Der=(i+1) mod 5
While true do
Pensar //asincrónico
P(comedor)
//acá logró entrar al comedor
P(palitos[izq])
//logró hacerse del palito izq
P(palitos[der])
//logró hacerse del palito der
Comer //sincrónico
V(palitos[der])
V(palitos[izq])
V(Comedor)
End while
End Filósofo
Siempre compiten DE A 4 POR LOS PALITOS.
Sólo el que logra obtener los 2 palitos, come.
Pero el problema sigue teniendo una solución que no favorece a nadie especialmente, ni perjudica a nadie, eso está bien!
Variante del problema
Ahora los palitos están todos están todos en una caja, en el centro de la mesa.
Adaptar la solución para contemplar esta nueva situación.
Podemos usar un semáforo sólo, inicializado en 5, para la cantidad de palitos, ya que ahora no importa cual.
El caso de deadlock sigue pasando ? siiiiiiiiiiiiiiiiiii
Entonces el comedor sigue teniendo sentido.
Main
Palitos: semáforo, inicializado en 5
Comedor: semáforo, inicializado en 4
Init(palitos,5)
Init(comedor,4)
Cobegin
Filosofo
….
Filosofo
(total 5 filósofos)
Coend
End Main
Proc Filósofo
While true do
Pensar //asincrónico
P(comedor)
P(palitos)
P(palitos)
Comer //sincrónico
V(palitos)
V(palitos)
V(Comedor)
End while
End Filósofo
En la página http://sopa.dis.ulpgc.es/prog_c/IPC.HTM hay una descripción puntual detallado sobre los semáforos en el SO Unix.
Ventajas de los semáforos:
- Eficiencia, ya que van ligados al estado de bloqueo del scheduller.
- Completitud descriptiva, ya que tienen el mismo poder expresivo que los grafos de precedencias.
- Simplicidad en las soluciones.
Desventajas de los semáforos:
- Son de bajo nivel de abstracción.
- Generan código de difícil lectura. Las consecuencias son que es difícil de mantener, modificar y comunicar.
- Permiten un manejo equivocado: si me olvido de un P o un V no funciona nada.
- No sirven para redes, es decir, para sincronizar procesos que están sobre máquinas diferentes que se ven a través de la red. Esto porque son memoria compartida. Y esta memoria necesariamente tiene que estar en alguna de las máquinas.
- La migración a soluciones de red requiere de un servidor de semáforos. Es decir, un proceso que ofrezca el servicio de bloqueo y desbloqueo de los semáforos para toda la red.
- Su correctitud sintáctica no empuja hacia su correctitud semántica. Es decir cumplir con la sintaxis no nos acerca a la solución del problema. Esto es por ser de bajo nivel.
- Si bien las operaciones son INIT, P y V, en implementaciones concretas es posible “espiar” el valor del semáforo y en consecuencia, programar de una manera extremadamente desprolija. Al debuggear es usual imprimir el semáforo.
- Se manifiestan como variables globales. Con ello restan claridad al código.
- Si nos olvidamos de un P o un V se tranca todo.
- Deja abierta la posibilidad de, siendo sintácticamente correcto un código, usarlos mal.
Por todo esto vamos a trabajar con las primitivas de más alto nivel.
Para ello trabajaremos con primitivas a nivel del Lenguaje de Programación y no del sistema operativo.
Entonces lo que ocurrirá es que estas soluciones serán compiladas y generarán código que funciona en términos de semáforos.
Nos pasamos a un nivel superior, el LP, generando soluciones en función de semáforos, que están dentro del SO.
Lo que sigue son herramientas a nivel del lenguaje de programación:
- Regiones críticas
- Regiones críticas condicionales
- Monitores
- Lenguaje Ada
Regiones críticas
Son una construcción a nivel del LP. El compilador traducirá en términos de semáforos.
Aprovechan la idea de unir el P y el V en una sola operación, asociados a una región crítica, como por ejemplo el paseo_perro del problema de A&B.
Se declara una región crítica, como una variable especial, de un tipo shared:
v: shared T
y se utiliza la construcción region.
De la siguiente forma:
Region v do
S //conjunto de instrucciones
End Region
Donde S es un conjunto de operaciones que se realizarán bajo mutua exclusión en los diferentes procesos.
Region v do
S1
End
Y
Region v do
S2
End
En procesos diferentes, S1 y S2 se ejecutan bajo mutua exclusión.
Quién los vincula ? La región crítica llamada v
Por ejemplo, en el problema de A&B tendremos:
Proc Main
Patio:shared
Cobegin
Alice
Bob
coend
proc Alice
while true do
region patio do
paseo_perro_A //sincrónico
end region
otras_tareas_Alice // asincrónico
end while
end Alice
proc Bob
while true do
region patio do
paseo_perro_B //sincrónico
end region
otras_tareas_Bob // asincrónica
end while
end Alice
Si queremos que Sean Alice & Bob & Charlie, basta replicar el código. PERO si queremos dar al patio capacidad 2, ya no podemos.
Como siempre queremos mutuo excluir lo mínimo indispensable, entonces en la región crítica, adentro, va lo mínimo posible, a efectos de maximizar el paralelismo de mi solución.
El compilador, cada vez que encuentre un :
v: shared T
Declarara un semáforo SV: semáforo
Que es un semáforo asociado a la RC.
Y lo inicializa:
Init(SV,1)
y en la construcción region.
Cuando encuentre un:
Region v do
S
End Region
El compilador creará
…
P(SV)
S
V(SV)
Cuál es el problema que vemos ?
Cada vez que usamos un region, abrimos y cerramos el MISMO semáforo.
Entonces, cómo hacemos para modelar situaciones como en el P/C, donde teníamos:
P(e)
P(s)
Insertar
V(s)
V(n)
Lo verde puedo, pero lo rojo no puedo hacerlo con regiones críticas..
Entonces a las regiones críticas no les alcanza el………….. PODER EXPRESIVO!
Por ejemplo el problema del P/C no puede ser resuelto con Regiones críticas.
Por otra parte, si el patio tuviera capacidad 2, para repartir entre 3 o más procesos, no sería posible resolverlo tampoco…
En definitiva las RC, tal como están propuestas, son un nombre más simpático para los semáforos binarios (es decir los que por su funcionamiento varían entre 0 y 1).
Recurrimos a las Regiones Críticas Condicionales.
Éstas tienen dos enfoques:
- When
- Await
Regiones críticas condicionales con When
V: shared T
Region v (when B) do
S
endRegion
Igual que antes, pero intenta entrar en la región crítica SOLO SI B evalúa a True. En caso de que no, espera hasta que lo sea. (…)
Luego, si B es true, pasa, pero habrá que esperar a que no esté ocupada. Siempre rechequeando B.
Es decir que entra en le RC sólo si B es true y la RC está libre. En TODO OTRO CASO se bloquea (…) a esperar.
Resolver el problema de A & B & Charlie con patio de capacidad 2, con RCC
Variables
patio: shared
en_el_patio:int =0
Main
Cobegin
Alice
Bob
Charlie
Coend
End
Bob y Charlie son similares a Alice (el problema es totalmente simétrico)
Atención: como sólo puede entrar un proceso por vez a la RC, no podemos lograr dentro del patio que paseen los perros. Entonces hacemos un protocolo de entrada y salida.
La variable llamada En_el_patio controla la cantidad de perros paseando en el patio.
La manipulación de la variable en_el_patio no es atómica, entonces debemos protegerla bajo mutua exclusión.
Proc Alice
While true do
Region patio when (en_el_patio < 2) do //acá es donde bloquea y evita líos en el patio…
en_el_patio ++
End Region
Paseo_Perro_Alice //sincrónico, atrapado entre dos sincronías…
Region patio do
En_el_patio - -
End Region
Otras_tareas_Alice //asincrónico
End
El patio quedó como una región de mutua exclusión sobre la variable en_el_patio
Si bien vamos a resolver otras cosas con RCC, ya vayan sabiendo que no es posible implementarlas sin busy waiting.
Entonces hasta acá vamos teniendo soluciones de más alto nivel, las cuales nos gustan más por ser más claras y por lo tanto permitirnos atacar realidades más complejas…
Y como desventaja estamos advertidos de que todo esto no se podrá implementar sin busy waiting, lo cual es negativo.
Problema del productor/consumidor con regiones críticas condicionales con when
Procesos ------------ Productores y Consumidores.
Recursos ---------------- Buffer
Condiciones de sincronización ------------ mutua exclusión, lleno, vacío.
Cuántas regiones críticas condicionales usaremos ? UNA, asociada al recurso, es decir, el buffer, que proteja la estructura de cola.
Cómo garantizamos mutua exclusión ? Porque es una RC, entrará uno por vez.
Cómo garantizamos “no lleno” ? Con un when respecto a la cantidad de elementos del buffer.
Cómo garantizamos “no vacío” ? Con un when respecto a la cantidad de elementos del buffer.
La estructura y las funciones de manejo son exactamente las mismas. Las traemos de la solución con semáforos, y sustituimos la terna de semáforos por la RCC.
Trabajamos con un buffer de HASTA N elementos de tipo T
Constante
N=…
Tipos
Tbuffer = struct
Pool: array 0..N-1 de T
P_a_e, p_a_i: 0..N-1 = 0
Cant:0..N =0
End Tbuffer
Operaciones
Ins_ultimo (in x:T)
Pre: buffer no lleno
Pool [p_a_i]=x
P_a_i=(p_a_i+1) mod N
Cant ++
End Ins_Ultimo
Ext_primero(out x:T)
Pre: buffer no vacío
x=Pool [p_a_e]
p_a_e=(p_a_e+1) mod N
Cant - -
End Ext_primero
Variables
Buffer: shared TBuffer
Proc Main
Cobegin
Productor
…
Consumidor
...
Coend
End Main
Proc Productor
Variable x:T
While True do
Producir(x) // asincrónico
Region Buffer (When cant < N) do
Ins_ultimo(x) // sincrónico
End Region
End While
End Productor
Proc Consumidor
Variable x:T
While True do
Region Buffer (When cant >0) do
Ext_primero(x) //sincrónico
End Region
Consumir(x) // asincrónico
End While
End Consumidor
Ejercicio. Es una combinación del P/C con el problema de M/E.
B es un buffer de hasta 50 enteros.
X es una variable entera que puede cambiar en cualquier momento, y debe ser tratada bajo mutua exclusión.
P1 lee de teclado (read) e inserta en B.
P2 extrae de B y si es mayor a x imprime.
P3 extrae de B, suma x, y vuelve a insertar en B.
P1 , P2 y P3 estarán ejecutando a la vez, en loop infinito. En el caso de P2 y P3 van a competir entre sí por acceder a los elementos del buffer.
Constante
N=50
Tipos
Tbuffer = struct
Pool: array 0..N-1 de Int
P_a_e, p_a_i: 0..N-1 = 0
Cant:0..N =0
End Tbuffer
Operaciones
Ins_ultimo (in x:int)
Pre: buffer no lleno
Pool [p_a_i]=x
P_a_i=(p_a_i+1) mod N
Cant ++
End Ins_Ultimo
Ext_primero(out x:int)
Pre: buffer no vacío
x=Pool [p_a_e]
p_a_e=(p_a_e+1) mod N
Cant - -
End Ext_primero
Variables
Buffer: shared TBuffer
x:int //esta es la variable global a proteger por la región controlx
controlx: shared
Proc Main
Cobegin
P1
P2
P3
Coend
End Main
Proc P1
Variable x1:Int
While True do
Read(x1)
Region Buffer (when Cant <N) do
Ins_ultimo(x1)
End Region
End While
End P1
Proc P2
Variable x1,x2:int
While True do
Region Buffer (when Cant >0) do
Ext_primero(x1)
End Region
Region Controlx do
x2=x
End Region
If (x1>x2) then
Print(x1)
End if
End While
End P2
Proc P3
Variable x1,x2:int
While True do
Cobegin
begin
Region Buffer (when Cant >0) do
Ext_primero(x1)
End Region
End
begin
Region Controlx do
x2=x //siempre conviene sólo leerla
End Region
End
coend
x1=x1+x2
Region Buffer (When Cant<N) do
Ins_ultimo(x1)
End Region
End While
End P3
Implementación de RCC when usando busy waiting + semáforos
Region v (when B)
do
S
EndRegion
Se puede implementar como:
sv: semáforo
….
Init(sv,1)
.…
While (not B) do; // busy waiting, detiene hasta que se satisfaga la condición B
P(sv)
S
V(sv)
Esta implementación, que finalmente resulta ser la única posible, es ineficiente.
Y también es inevitable porque no puedo asociarla a un semáforo.
Razonemos esto: la expresión B puede contener de todo, por ejemplo:
Region v when (p+q = r+z**2)
Do
S
End
Esta condición (p+q = r+z**2)… si se cumple OK, si no se cumple, tengo que estar detenido hasta que se cumpla… cuando rechequear? A cada rato? Cuando se modifiquen p q r z ? cómo hago para saberlo ?
Ese when termina necesariamente en el busy waiting…
En cuanto al poder expresivo, las CCR tienen el mismo poder expresivo que los semáforos.
Puedo implementar unos con otros y otros con unos.
Sin embargo, su potencia expresiva se apoya en una sintaxis demasiado capciosa para los bloqueos, imposible de traducir sin busy waiting.
Otra variante para el enfoque de Regiones Críticas, son las RCC con await, cuya sintaxis es la siguiente:
v: shared T
…
Region v do
S1
Await(B)
S2
End region
Cuando encuentra el final de S1 y se topa con el await, se detiene, abandona la región, y espera hasta que B sea true. Luego ejecuta S2 dentro de la región.
Ejercicio, resolver el problema de A&B&C patio capacidad 2 con RCC/await.
Variables
patio: shared
en_el_patio:int =0
Main
Cobegin
Alice
Bob
Charlie
Coend
End
Bob y Charlie son similares a Alice (el problema es totalmente simétrico)
Proc Alice
While true do
Region patio do
await(en_el_patio < 2) //acá es donde bloquea y evita líos en el patio…
en_el_patio ++ //la manipulamos dentro de la RCC , asegurándonos de este modo la mutua exclusión.
End Region
Paseo_Perro_Alice // PARTE SINCRÓNICA
Region patio do
En_el_patio - -
End Region
Otras_tareas_Alice // PARTE ASINCRÓNICA
End
Escribir RCC/when en función de RCC/await y viceversa
RCC await en función de las de RCC/when
Region v do
S1
Await(B)
S2
End
Lo hago como:
Region v do
S1
end
Region v (when B) do
S2
end
RCC/when en función de RCC/await
Region v (when B) do
S
end
Lo hacemos como:
Region v do
Await(B)
S
End
Esto significa que son equivalentes.
Cómo expresamos las RCC con await en función de semáforos y B/W
Region v
do
S1
Await(B)
S2
EndRegion
Se puede implementar como:
sv: semáforo
….
Init(sv,1)
.…
P(sv)
S1
V(sv)
While (not B) do; // busy waiting
P(sv)
S2
V(sv)
Problema de los lectores y escritores con RCC/await
Variables
v:shared record
Nlect, Nescrit: int //para manejar entre L&E
Ocupado: bool // para manejar entre E
Main
Ocupado=False
Nlect=0
Nescrit=0
Cobegin
Lector
…
Lector
Escritor
…
Escritor
Coend
End Main
Un comentario es que los lectores y los escritores, en este caso, no tienen while true do, por lo cual ellos “nacen, leen o escriben, y desaparecen”. Sin embargo, podría todo esto estar dentro de un loop infinito y la sincronizazación es exactamente la misma.
Proc Lector
Region v do
Await(Nescrit=0)
Nlect ++
EndRegion
LEER
Region v do
Nlect - -
EndRegion
End Lector
Aclaración: si se bloquea con await en medio de la región, espera FUERA DE LA MISMA, otro puede entrar…
Proc Escritor
Region v do
Nescrit ++
Await (not(ocupado) && (Nlect=0))
Ocupado=True
EndRegion
Escribir
Region v do
Nescrit- -
Ocupado=False
EndRegion
End Escritor
Analizamos prioridades:
El Lector 2 no pudo entrar porque el E1 estaba esperando…
En definitiva no pudo colarse ningún Lector, vamos bien.
El E1 no pudo escribir, pues lo frenó el await(nescrit=0).
El L2 no pudo colarse, pues lo frenó el await((not ocupado) and (nlect=0))
Acá no aparecen fallas…
El escritor 2 logró colarse al lector 1.
Con lo cual existe potencial aplazamiento indefinido de los lectores a favor de los escritores.
La conclusión principal es que tenemos la comodidad del alto nivel, pero la ineficiencia inadmisible del Busy Waiting.
Trabajaremos con otra herramienta diferente, que tiene bloqueo y desbloqueo explícito: son los monitores.
Estamos sincronizando procesos.
Estamos estudiando alternativas de alto nivel que nos den más claridad y menos probabilidad de error que el uso de semáforos.
Descartamos las Regiones críticas por falta de expresividad.
Descartamos las Regiones críticas condicionales porque la única forma de implementarlas es en base a busy waiting y esto es inadmisible en cuanto al desperdicio de recursos.
Trabajaremos con MONITORES.
Los monitores son una construcción de alto nivel. Agrupan –al estilo de los TADs y de las clases- un dominio (que lo manifestamos por una estructura) y operaciones sobre él.
PERO las operaciones sobre el monitor se hacen BAJO MUTUA EXCLUSION.
Por ejemplo:
Monitor M
Variables
x,y: entero
proc incx
x+=10
end proc
proc incy
y+=20
end proc
Inicialización
x=0
y=50
End inicialización
End Monitor
Las variables x e y no son visibles desde fuera.
Lo que se ve desde fuera son los procedimientos del monitor. Los cuales se ejecutan bajo mutua exclusión.
No es posible hacer:
x=1
x++
M.x ++
Si es posible hacer:
M.incx
M.incy
En definitiva se nos está presentando una herramienta que permite encapsular estructuras, y lograr acceso a ellas bajo mutua exclusión.
Ejercicio
Resolver el problema de Alice&Bob con monitores
Quiénes son los procesos? Alice, Bob
Quiénes son los recursos? Patio
Cuáles son las partes sincrónicas y asincrónicas ? Sincrónico pasear_perro , asincrónico otras_tareas.
Qué monitores utilizo ? UN MONITOR PARA EL ACCESO AL PATIO
Cuáles son los procedimientos del monitor ? EN UNA PRIMERA VERSIÓN, PASEAR AL PERRO
Armo todo
VERSION 0
Monitor Patio
Proc Paseo_Perro
PASEAR_AL_PERRO
End Proc
End Monitor
Proc Main
Cobegin
Alice
Bob
Coend
End Proc
Proc Alice
While True do
Patio.Paseo_Perro //sincrónico, ligado al sincronizador que es el patio…
Otras_tareas_Alice // asincrónico
End While
End Proc
Proc Bob
While True do
Patio.Paseo_Perro
Otras_tareas_Bob
End While
End Proc
Esta solución tiene un pequeño defecto: LOS OBLIGA A PASEAR AL PERRO DE LA MISMA FORMA, CON EL MISMO CODIGO.
VERSION 1
Monitor Patio
Proc Paseo_Perro(in quien_soy:(A,B))
If quien_soy=A
Then PASEAR_AL_PERRO_ALICE
Else PASEAR_AL_PERRO_BOB
End
End Proc
End Monitor
Proc Main
Cobegin
Alice
Bob
Coend
End Proc
Proc Alice
While True do
Patio.Paseo_Perro(A)
Otras_tareas_Alice
End While
End Proc
Proc Bob
While True do
Patio.Paseo_Perro(B)
Otras_tareas_Bob
End While
End Proc
VERSION 2
Monitor Patio
Proc Paseo_Perro_Alice
PASEAR_AL_PERRO_ALICE
End Proc
Proc Paseo_Perro_Bob
PASEAR_AL_PERRO_BOB
End Proc
End Monitor
Proc Main
Cobegin
Alice
Bob
Coend
End Proc
Proc Alice
While True do
Patio.Paseo_Perro_Alice //SINCRONICO
Otras_tareas_Alice //ASINCRONICO
End While
End Proc
Proc Bob
While True do
Patio.Paseo_Perro_Bob
Otras_tareas_Bob
End While
End Proc
Qué pasa cuando tenemos por ejemplo A & B & C con patio de capacidad 2 ?
Ahora el paseo_perro no puede ser un procedimiento del monitor, pues deben usarlo a la vez en algunos momentos, y el monitor sólo permite pasar a uno.
Aquí podríamos recurrir a un protocolo:
Pedir patio
Pasear perro
Devolver Patio
Y pedir patio y devolver patio deberían ser procs del monitor.
Sin embargo pedir patio debería bloquear en función de la cantidad de personas en el patio. Y no tenemos forma de bloquear. No hay un when o un await…
Está faltando PODER EXPRESIVO…
Entonces a los monitores, les agregaremos unas variables, de tipo CONDITION, que tienen 2 operaciones: wait y signal.
Si tenemos x:condition: local al monitor…
Dentro de los procedimientos del monitor tendremos
x.wait lo que hará es bloquear a quien invoca a tal procedimiento
y desbloquearlo cuando alguien invoque a otra parte del monitor que contenga un x.signal.
Qué pasa si hacemos un x.signal sin haber ocurrido un x.wait ? Nada, se ignora. NO SE LO ACUERDA PARA DEPUÉS.
Si hay más de un wait, el signal desbloquea según fila.
A destacar: el x:condition no almacena nada, sólo bloquea/desbloquea, hay que usarlo en combinación con otras variables para guardar.
Cuando bloqueamos por un wait, se libera el monitor, obvio, así otro puede entrar…
¿Puede haber varios procesos a la vez en un monitor?
NO, siempre es de a uno.
Usemos un protocolo de pedir y devolver el patio.
VERSION 3 PATIO CON CAPACIDAD 1
Monitor Patio
Ocupado:Bool=FALSE // esta variable la usamos para guardar el estado
Detener:condition // esta condition la usamos para bloquear o desbloquear
Proc Pedir
If Ocupado
Then Detener.wait
End //notar que este if no lleva nunca else
//cuando llegamos acá es porque el semáforo está con capacidad
Ocupado=True
End
Proc Devolver
Ocupado=False
Detener.signal
End
End Monitor
Proc Main
Cobegin
Alice
Bob
Coend
End Proc
Proc Alice
While True do
Patio.Pedir
Paseo_Perro_Alice //SINCRONICO
Patio.Devolver
Otras_tareas_Alice //ASINCRONICO
End While
End Proc
Proc Bob
While True do
Patio.Pedir
Paseo_Perro_Bob //SINCRONICO
Patio.Devolver
Otras_tareas_Bob //ASINCRONICO
End While
End Proc
Una ventaja de esta solución, es que si son A&B&C&D&E… el monitor no lo tengo que cambiar para nada. El que sí cambia es el código de c/u. Esto es muy importante a efectos de la facilidad de generalización!
Ejercicio.
Resolver el problema de A&B&C con patio de capacidad 2.
Usemos un protocolo de pedir y devolver el patio, modificando la solución 3.
Monitor Patio
EnElPatio:Int=0
Detener:condition
Proc Pedir
If EnElPatio=2
Then Detener.wait
End //notar que este if no lleva nunca else
EnElPatio++
End
Proc Devolver
EnElPatio- -
Detener.signal //si había alguien bloqueado, lo desbloquea, y si no, no pasa nada
//desbloquea respetando la fila
End
End Monitor
Proc Main
Cobegin
Alice
Bob
Coend
End Proc
Proc Alice
While True do
Patio.Pedir
Paseo_Perro_Alice //SINCRONICO
Patio.Devolver
Otras_tareas_Alice //ASINCRONICO
End While
End Proc
Proc Bob
While True do
Patio.Pedir
Paseo_Perro_Bob //SINCRONICO
Patio.Devolver
Otras_tareas_Bob //ASINCRONICO
End While
End Proc
CHARLIE ES ANALOGO
De nuevo, A&B&C quedan inalterados, sólo modificamos el monitor del patio. Esto es una ventaja como forma de trabajo.
MONITOR PARA UN ASIGNADOR GENERICO DE RSR
No es más que una abstracción de la solución 3
Monitor Recurso
Ocupado:Bool=FALSE
Detener:condition
Proc Pedir
If Ocupado
Then Detener.wait
End //notar que este if no lleva nunca else
Ocupado=True
End
Proc Devolver
Ocupado=False
Detener.signal
End
End Monitor
Semáforos binarios con monitores
Monitor Semáforo
Ocupado:Bool=FALSE // es para controlar si el semáforo está para bloquear
Detener:condition // esta variable condition no guarda valores, sólo bloquea con wait, y desbloquea, con signal.
Proc P
If Ocupado //si el semáforo esta para bloquear
Then Detener.wait //bloqueo
End //notar que este if no lleva nunca else
// si llego hasta acá es porque o bien no estaba ocupado, o bien estaba ocupado y me bloqueó y luego me desbloqueó.
Ocupado=True
End
Proc V
Ocupado=False
Detener.signal //si no hubo un wait, entonces esto no tiene efecto
End
End Monitor
El monitor no es proceso. El monitor ejecuta en el ámbito de los procesos que invocan sus procedimientos.
En el cuerpo de inicialización podemos controlar la inicialización con init.
Ejercicio
Hacer un monitor que emule un SEMAFORO GENERICO con sus operaciones INIT, P y V.
Monitor Semaforo
Variables
n:int// notar que no está inicializado, es responsabilidad de quien usa, arrancar por init.
Bloqueo:condition
Proc Init(in v:int)
n=v
EndProc
Proc P
If n=0
Then
Bloqueo.wait
End
n- -
End Proc
Proc V
n++
Bloqueo.signal
End Proc
End Monitor
Concluimos que, pudiendo hacer los semáforos con monitores alcanzamos su poder expresivo.
Con lo cual, los monitores (incluidas las variables condition) tienen el poder expresivo adecuado.
Notar que el monitor NO ES PROCESO, él no se lanza en el cobegin coend. Sus procs son invocados desde los demás procesos y ejecutan en el ámbito de estos.
Problema del Productor Consumidor con Monitores.
Los procesos son los productores y los consumidores.
El recurso es el BUFFER.
Las condiciones de sincronización son lleno, vacío, mutua exclusión.
Usaremos un monitor para el buffer. Si insertar y extraer son procedimientos del monitor, entonces la mutua exclusión ya está garantizada.
Usaremos conditions para que, en función de la cantidad de elementos, filtremos los casos de lleno y vacío, deteniendo cuando corresponda.
Monitor Buffer Finito
No_lleno, no_vacio:condition
Buffer=record
Pool:array 0..N-1 de T
P_a_e, P_a_i:0..N-1=0
Cant:0..N=0
EndBuffer
Proc ins_al_final(in x:T)
If Cant=N
then no_lleno.wait
EndIf
//cuando llego acá es porque no está lleno, hay lugar
Pool[P_a_i]=x
P_a_i=(P_a_i+1) mod N
Cant ++
no_vacio.signal
End
Proc ext_primero(out x:T)
If Cant=0
Then no_vacio.wait
Endif
// cuando llego acá es que hay al menos un elemento
x=pool [P_a_e]
P_a_e=(P_a_e+1) mod N
Cant - -
no_lleno.signal
End
End Monitor
Proc Main
Cobegin
Productor
…..
Productor
Consumidor
…..
Consumidor
Coend
End Main
Proc Productor
Variables
x:T
While True do
Producir(x) //asincrónica
Buffer_Finito.Ins_al_final(x) //sincrónica
End While
End Productor
Proc Consumidor
Variables
x:T
While True do
Buffer_Finito.Ext_primero(x) //sincrónica
Consumir(x) //asincrónica
End While
End Consumidor
Ejercicio
Sean dos buffers B1 y B2, de hasta 50 Enteros.
Y sean los siguientes procesos P1, P2, P3, P4, concurrentes, que interactúan con dichos buffers.
P1 lee de teclado (read) e inserta en B1.
P4 extrae de B2 e imprime (print).
P2 extrae de B1, eleva al cuadrado e inserta en B2.
P3 extrae de B1, extrae de B2, suma, y si da mayor que 50, inserta en B2.
Se pide armar el seudocódigo de todo esto con monitores.
Constantes
N=50
Monitor Buffer1
No_lleno, no_vacio:condition
Buffer=record
Pool:array 0..N-1 de Int
P_a_e, P_a_i:0..N-1=0
Cant:0..N=0
EndBuffer
Proc ins_al_final(in x:Int)
If Cant=N
then no_lleno.wait
EndIf
//cuando llego acá es porque no está lleno, hay lugar
Pool[P_a_i]=x
P_a_i=(P_a_i+1) mod N
Cant ++
no_vacio.signal
End
Proc ext_primero(out x:Int)
If Cant=0
Then no_vacio.wait
Endif
// cuando llego acá es que hay al menos un elemento
x=pool [P_a_e]
P_a_e=(P_a_e+1) mod N
Cant - -
no_lleno.signal
End
End Monitor
Los dos monitores son iguales, pero debo presentarlo dos veces. La herramienta no permite una instanciación de monitores de igual estructura sobre un monitor más genérico.
Es una limitación de la herramienta.
Monitor Buffer2
No_lleno, no_vacio:condition
Buffer=record
Pool:array 0..N-1 de T
P_a_e, P_a_i:0..N-1=0
Cant:0..N=0
EndBuffer
Proc ins_al_final(in x:Int)
If Cant=N
then no_lleno.wait
EndIf
//cuando llego acá es porque no está lleno, hay lugar
Pool[P_a_i]=x
P_a_i=(P_a_i+1) mod N
Cant ++
no_vacio.signal
End
Proc ext_primero(out x:Int)
If Cant=0
Then no_vacio.wait
Endif
// cuando llego acá es que hay al menos un elemento
x=pool [P_a_e]
P_a_e=(P_a_e+1) mod N
Cant - -
no_lleno.signal
End
Proc Main
Cobegin
P1
P2
P3
P4
Coend
End Main
Proc P1
Variables
x:Int
While True do
Read(x)
Buffer1.Ins_al_final(x)
End While
End P1
Proc P4
Variables
x:Int
While True do
Buffer2.Ext_primero(x)
Print(x)
End While
End P4
Proc P2
Variables
x:Int
While True do
Buffer1.Ext_primero(x)
x=x*x
Buffer2.Ins_al_final(x)
End While
End P2
Proc P3
Variables
x1,x2:Int
While True do
cobegin
Buffer1.Ext_primero(x1)
Buffer2.Ext_primero(x2)
coend
x1+=x2
if x1 > 50
then Buffer2.Ins_al_final(x1)
end If
End While
End P3
Comentarios:
- Nunca se pregunta por el valor de las variables condition. Sólo se usan para bloquear y desbloquear. Por tanto siempre van acompañadas de variables que permiten guardar el status de lo que sea que use para bloquear/desbloquear.
- Siempre mutuo excluir lo mínimo indispensable. Porque durante la mutex estamos limitando la concurrencia.
Problema de los lectores y escritores con Monitores
Monitor LectEsc
Variables
CantLec, CantEsc:int=0
NoLec,NoEsc:condition
Proc ComenzarLeer
If CantEsc > 0
Then NoEsc.wait
Endif //NUNCA LLEVAN ELSE
// al llegar aquí, sabemos que no hay escritores
CantLec++
EndComenzarLeer
Proc FinLeer
CantLec- -
If CantLec=0
Then NoLec.signal
Endif
End FinLeer
Proc ComenzarEscribir
CantEsc++
If CantEsc>1
Then NoEsc.wait
EndIf
//no hay escritores
If CantLec>0
Then NoLec.wait
End
//no hay ni lectores ni escritores
End ComenzarEscribir
Proc FinEscribir
CantEsc- -
NoEsc.signal
End FinEscribir
Fin LecEsc
Main
Cobegin
Lector
…
Lector
Escritor
…
Escritor
Coend
End Main
Proc Lector
While true do
LectEsc.ComenzarLeer
LEER
LectEsc.FinLeer
OtrasTareasLector
EndWhile
End Lector
Proc Escritor
While true do
LectEsc.ComenzarEscribir
ESCRIBIR
LectEsc.FinEscribir
OtrasTareasEscritor
EndWhile
End Escritor
Vamos a hacer un análisis de prioridades…
Caso 1
Lector intenta colarse a escritor que espera…
Anduvo perfecto.
Caso 2
Escritor intenta colarse a lector que espera…
El E2, escritor 2, queda bloqueado, esperando un No_Esc.signal…. la solución equivocadamente, tiró un NoLec.signal.
No está trancado, no está en deadlock. Pero está esperando una señal que no le voy a mandar.
Cuándo se va a destrancar ? Cuando alguien mande un noEsc.signal, aunque no será para él.
Estos típicos problemas de desfasaje de sincronización nos pueden volver locos en las etapas de debugging.
Esto pasa mucho al programar sobre redes soluciones distribuidas, etc.
Si bajamos en el código el CantEsc++ y lo ponemos luego de los ifs, en comenzarEscribir, entonces tenemos una solución sin estos problemas, en principio, PERO que favorece “descaradamente” a los lectores.
En esta solución el monitor de alguna forma falló, permitió un uso muy desprolijo de las condiciones y elementos de sincronización y terminó fallando y de una forma poco previsible.
Esto pone de manifiesto las carencias de esta herramienta, las cuales son producto de un muy robusto y prolijo sistema de sincronización a alto nivel (el monitor) pero mezclado con elementos de bajo nivel como las condition. Esto nos iba a dar problemas.
NECESITAMOS OTRAS HERRAMIENTAS!
El lenguaje Ada será la solución.
Estamos listos para comenzar Ada, que es la alternativa siguiente a Monitores, y donde encontraremos un ambiente de desarrollo orientado a la sincronización de procesos concurrentes.
Previamente, veremos Fork&Join
Son primitivas de sincronización de bajo nivel, con las que podríamos explicar el desarrollo del cobegin/coend, semáforos, etc.
Quit ----- corta la ejecución y finaliza el proceso.
Goto label ---- salta incondicionalmente a una etiqueta que identifica una línea de código.
Es igual al jmp de assembler.
Fork label ---- Crea un nuevo proceso, referido sobre el mismo código. El código, a bajo nivel, está en algún lugar de la memoria y más nada… El proceso original pasa a la línea siguiente y el nuevo arranca desde label.
Join contador, label
La lógica es:
Contador - -
If contador =0 then goto label
Entonces el join va a recibir contador – 1 procesos y los va a dejar pasar. Al último, lo pasará a label.
PERO join se usa siempre con un quit debajo. Entonces, lo que join deja pasar, quit lo mata. En consecuencia, la pareja join quit lo que hace es matar los primeros contador-1 procesos. Luego el último lo salta y lo deja en el label del join.
El join es indivisible! Nadie nos puede quitar la CPU en medio de su ejecución. Ocurre exactamente lo mismo para el fork.
Debajo de cada join va un quit. De otro modo, no funciona.
Fork y Join tienen el mismo poder expresivo que los Grafos de Precedencias. Por tanto es lo que podemos usar para implementar a bajo nivel semáforos y cobegin/coend.
Al ser de bajo nivel, resulta muy difícil implementar los problemas clásicos.
Lenguaje ADA – Introducción
Algunos comentarios iniciales.
https://es.wikipedia.org/wiki/Ada_(lenguaje_de_programaci%C3%B3n)#:~:text=Ada%20es%20un%20lenguaje%20de,Defensa%20de%20los%20Estados%20Unidos.
Ada (lenguaje de programación)
| Ada | |
| Desarrollador(es) | |
| Jean Ichbiah y Tucker Taft http://www.adaic.org/ | |
| Información general | |
| Extensiones comunes | .adb, .ads |
| Paradigma | Orientado a objetos, imperativo |
| Apareció en | 1980 |
| Diseñado por | Jean Ichbiah y S. Tucker Taft |
| Última versión estable | Ada 2012 (1 de febrero de 2016 (4 años, 8 meses y 11 días)) |
| Sistema de tipos | Fuerte, estático, seguro y nominativo |
| Implementaciones | AdaCore GNAT, Green Hills Software |
| Dialectos | SPARK, Perfil de Ravenscar |
| Influido por | ALGOL 68, Pascal, C++ (Ada 95), Smalltalk (Ada 95), Java (Ada 2005) |
| Ha influido a | C++, Eiffel, PL/SQL, VHDL, Ruby, Java |
| Sistema operativo | Multiplataforma |
En Ada el foco es………………………. La concurrencia y sincronización……… El elemento central son las TASKS, o procesos. La sincronización de tasks se logra mediante citas. El lenguaje está lleno de controles estáticos y dinámicos, y en consecuencia es fuertemente tipado. Fuertemente tipado significa que debo declarar los tipos. El compilador, en función de las expresiones, deduce los tipos. En los lenguajes débilmente tipados, se asume el tipo. En los fuertemente tipados se obliga a declarar, y luego se compara lo inferido vs lo declarado. a=b+4 y b es : Int Entonces infiero que a:int Voy a buscar a su declaración, y chequeo que efectivamente sea así. En el sentido opuesto del tipado fuerte, van los casteos automáticos de C…. c:int d:char c+d y si lo guardo en un int el le suma a c el ascii de d y sigue adelante. Y si lo asigno a un char, el suma los dos asciis y se fija en la tabla. Incluso esto hace al lenguaje C tan críptico, que se organizan concursos de quién desarrolla algo con la menor cantidad de caracteres. Y se aprovecha toda clase de trucos… para no declarar, etc. Ada tiene un origen militar. Ahí se necesitaba un lenguaje que permitiera la programación segura. Segura por safety más que por security. El foco entonces son los sistemas de tiempo real.
Este tipo de cosas es lo que se tiene en mente al aparecer Ada. Ada es un lenguaje de programación orientado a objetos y fuertemente tipado de forma estática que fue diseñado por Jean Ichbiah de CII Honeywell Bull por encargo del Departamento de Defensa de los Estados Unidos. Es un lenguaje multipropósito, orientado a objetos y concurrente, pudiendo llegar desde la facilidad de Pascal hasta la flexibilidad de C++. Fue diseñado con la seguridad en mente y con una filosofía orientada a la reducción de errores comunes y difíciles de descubrir. Para ello se basa en un tipado muy fuerte y en chequeos en tiempo de ejecución (desactivables en beneficio del rendimiento). La sincronización de tareas se realiza mediante la primitiva rendezvous. Estas citas las estudiaremos en detalle. Ada se usa principalmente en entornos en los que se necesita una gran seguridad y fiabilidad como la defensa, la aeronáutica (Boeing o Airbus), la gestión del tráfico aéreo (como Indra en España) y la industria aeroespacial entre otros. Continuamos con el lenguaje Ada. Es un lenguaje:
Aspectos sintácticos: Task tareauno is Entry entrada1 Entry entrada2(in a,b:T, out c:T’) End Task Task body tareauno is ….. …... Accept entrada1 Código de la cita llamada entrada1 //SINCRONICA End ………. ……….. Accept entrada2(in a,b:T, out c:T’) Código de la cita llamada entrada2 //SINCRONICA End End Task Desde otra task haremos… tareauno.entrada1 … tareauno.entrada2(4,5,mivariable) El que llega primero a la cita, espera. Esto es, si el que acepta la cita, ejecuta el accept antes de que alguien la pida, se bloquea a esperar que lo hagan. Si por el contrario, el que pide la cita, lo hace antes de que la acepten, entonces se bloquea a esperar que la acepten. Esto es lo medular en la sincronización por medio de citas. La propia mecánica de las citas garantiza la mutua exclusión ya que no hay forma de que ejecuten dos a la vez. Cómo procedemos ante cada problema ? En ADA tendremos tareas para los procesos y tareas para los recursos. Se sincronizan por medio de las citas. Problema de la Mutua Exclusión en Ada. Cuáles son los procesos ? Alice y Bob…………. Serán tasks Cuáles son los recursos ? Patio …………….. Será task Cuál es la forma de acceder a los servicios del recurso ? ……Pasear Perro…. Será una cita Armamos la solución VERSION 0 Task Alice is End //que esté vacío significa que NADIE PIDE CITAS A ALICE Task body Alice is Loop Patio.paseo_perro //sincrónica Otras_Tareas_Alice //asincrónica EndLoop End task Task Bob is End Task body Bob is Loop Patio.paseo_perro Otras_Tareas_Bob EndLoop End task Task patio is Entry paseo_perro End patio Task body patio is Loop Accept paseo_perro Código de pasear al perro //sincrónica End paseo_perro EndLoop EndTask Alice se va a citar con el patio para pasear al perro, también Bob, y por tanto eventualemente esperarán si el patio está ocupado. En el main, que ni lo ponemos, se lanzan todas las tasks. Esta versión 0 pasea los dos perros de la misma forma… Versión 1 con el nombre del dueño del perro como parámetro… VERSION 1 Task Alice is End Task body Alice is Loop Patio.paseo_perro(A) //SINC Otras_Tareas_Alice //ASINC EndLoop End task Task Bob is End Task body Bob is Loop Patio.paseo_perro(B) Otras_Tareas_Bob EndLoop End task Task patio is Entry paseo_perro(in Q_S:A,B) End patio Task body patio is Loop Accept paseo_perro(in Q_S:A,B) If Q_S=A then Código de pasear al perro Alice Else Código de pasear al perro Bob End End paseo_perro EndLoop EndTask Cómo armamos una Versión 2 con 2 citas diferentes ? El patio debería aceptar una cita entre 2 posibles. No sabemos! Falta sintaxis! Select Accept cita1 …… Or Accept cita2 …. … End Esto acepta una cita entre varias. Cuál ? La que llegue primero. Ahora las citas son: p_p_a y p_p_b Versión 2 Task Alice is End Task body Alice is Loop Patio.paseo_perro_alice //sinc Otras_Tareas_Alice //asinc EndLoop End task Task Bob is End Task body Bob is Loop Patio.paseo_perro_bob //sinc Otras_Tareas_Bob EndLoop End task Task patio is Entry paseo_perro_a Entry paseo_perro_b End patio Task body patio is Loop Select Accept paseo_perro_a Código de pasear al perro //sinc End paseo_perro Or Accept paseo_perro_b Código de pasear al perro //sinc End paseo_perro End Select EndLoop EndTask Supongamos que queremos generalizar a 3 personajes,… tan sólo deberíamos agregar una task C y la entry correspondiente al patio. Si ahora el patio tiene capacidad 2 y son 3. Nos falta sintaxis! Select When B1 Accept cita1 …… Or When B2 Accept cita2 …. … End B1 y B2 son booleanos. No hay busy waiting porque se evalúan y los que den true, participa la cita correspondiente, los que den False, la cita no participa. Ejercicio: adaptar la solución a 3 personajes y patio capacidad 2 ATENCION NO ANDA: Task Alice is End Task body Alice is Loop Patio.paseo_perro_alice Otras_Tareas_Alice EndLoop End task Task Bob is End Task body Bob is Loop Patio.paseo_perro_bob Otras_Tareas_Bob EndLoop End task Task body Charlie is Loop Patio.paseo_perro_Charlie Otras_Tareas_Charlie EndLoop End task Task patio is Entry paseo_perro_a Entry paseo_perro_b Entry paseo_perro_c End patio Task body patio is En_el_patio:int=0 Loop Select When (en_el_patio<2) Accept paseo_perro_a En_el_patio++ Código de pasear al perro En_el_patio- - End paseo_perro Or When (en_el_patio<2) Accept paseo_perro_b En_el_patio++ Código de pasear al perro En_el_patio- - End paseo_perro Or When (en_el_patio<2) Accept paseo_perro_c En_el_patio++ Código de pasear al perro En_el_patio- - End paseo_perro End Select EndLoop EndTask Funciona mal, NO DEJA PASEAR a 2 PERROS. Los obliga a pasear dentro de la cita y esto es uno a la vez. Continuamos con una versión con el protocolo PEDIR PATIO, DEVOLVER PATIO. Ejercicio: Resolver el problema de la mutua exclusión, pero usando un protocolo de pedir / devolver . Patio capacidad 1. Estamos “sufriendo” la sintaxis nueva, pero el lenguaje ayuda a no cometer errores, a resolver. VERSION 3 Task patio is Entry pedir Entry devolver End patio Task body patio is Loop Accept pedir Accept devolver End loop End task Task Alice is End task Task body Alice is Loop Patio.pedir P_p_a //sincrónico Patio.devolver O_t_a //asincrónico End Loop End task Task Bob is End task Task body Bob is Loop Patio.pedir P_p_b Patio.devolver O_t_b End Loop End task El patio, hasta que no acepta pedir, no acepta devolver, y así sucesivamente. Pedir y devolver son citas NULAS. Se dicen de sincronización. Ejercicio: modificar el código anterior para que el patio tenga capacidad 2 y sean 3 los personajes. Task patio is Entry pedir Entry devolver End patio Task body patio is Var En_el_patio:int=0 Loop Select When (en_el_patio<2) Accept pedir End En_el_patio++ //el que pidió la cita ya se fue pero aún estamos sincronizados de este lado Or Accept devolver End devolver En_el_patio- - End select End loop End task Task Alice is End task Task body Alice is Loop Patio.pedir P_p_a Patio.devolver O_t_a End Loop End task Task Bob is End task Task body Bob is Loop Patio.pedir P_p_b Patio.devolver O_t_b End Loop End task Task Charlie is End task Task body Charlie is Loop Patio.pedir P_p_c Patio.devolver O_t_c End Loop End task Ejercicio: Hacer una task de Ada que emule un semáforo binario. Las tasks se van combinando como piezas de una solución. Este semáforo será, dentro de un par de clases, el palito del filósofo por ejemplo. Task semáforobinario is Entry P Entry V End semáforobinario Task Body semáforobinario is Loop Accept P Accept V endloop End Task Ahí está inicializado en…………………………1 si quisiera inicializarlo en 0……invierto el orden de los accept. Ejercicio: Hacer una task de Ada que emule un semáforo común. Task Semáforo is Entry Init(in x:int) Entry P Entry V End Task Task body Semáforo is Var S:int Accept init(in x:int) S=x End Accept Loop Select When S>0 accept P end S- - Or Accept V End S++ EndSelect Endloop End task Un resultado muy importante: hemos logrado escribir los semáforos en función de Ada. Con lo cual, si bien no es una demostración formal, estamos mostrando que el poder expresivo es el mismo que el de cobegin/coend y semáforos; y por tanto el mismo que los grafos de precedencias, y por tanto el buscado. Entonces nos interesa continuar explorando esta herramienta en los demás problemas clásicos. Task type permite definir tasks que luego son instanciadas. Podemos poner: Task type Semáforo is Entry Init(in x:int) Entry P Entry V End Task Task body Semáforo is ……….. SIGUE IDENTICO Y entonces luego podemos instanciar esta tarea genérica que acabamos de crear: A,B,C: semáforo (en el main) A.init(6) A.P B.V R:array 1..8 of semáforo R[6].P … Y podemos usarlas de forma muy cómoda al instanciar sobre tasks genéricas. Ejercicio Volvemos al factorial concurrente. n!= (productoria desde i=1 a piso (n/2) (i) ) * (productoria desde (piso(n/2)+1) a n (i)) Vamos a tener una task productoria a la cual la pasamos i y j y devuelve productoria de x= i a x= j de x. El pasaje de los límites de la productoria lo haremos por medio de una cita. Y el pasaje del resultado también. Hagamos dicha task Task type productoria is Entry datos(in i,j:int) Entrt res(out r:int) End productoria Task body productoria is Var i1,j1,acum,k:int Accept datos(in i,j:int) i1=i j1=j end datos acum=1 for k in i1..j1 loop acum=acum*k end loop Accept res(out r:int) r=acum end End task A,B:productoria Task factorial End Task body factorial is Var n,r1,r2:int read(n) A.datos(1,piso(n/2)) B.datos(piso(n/2)+1,n) //la idea es que A y B trabajen concurrentemente … A.res(r1) B.res(r2) write(r1*r2) end task Ejercicio Productor consumidor buffer tamaño 1. Es decir que el buffer es 1 variable. Precisamos tasks: Productor… consumidor… y Buffer… El buffer no es un array sino una variable!
Task type productor is End task Task body productor is Var x:T Loop Producir(x) //asincrónico Buffer.insertar(x) //sincrónico End loop End task Task type consumidor is End task Task body consumidor is Var x:T loop Buffer.extraer(x) //sincrónico Consumir(x) //código de consumir o lo llamo como función //asinc End loop End task p1,p2,p3….,pn:productor c1,c2,c3…,cm:consumidor task buffer is insertar(in x:T) extraer(out x:T) end task body buffer is var buffer:T loop accept insertar(in x:T) buffer=x end accept accept extraer(out x:T) x=buffer end accept endloop end task end task Ejercicio Hay un array de N elementos de tipo T Viene una task productor que lo carga, los N, de una sola vez. Vienen tasks consumidor, que se llevan los N elementos de a 1. Cuando se vacía, el productor coloca otra vez N. Task type productor is End task Task body productor is Var x: array 0..N-1 of T Loop Producir(x) Buffer.insertar(x) End loop End task Task type consumidor is End task Task body consumidor is Var x:T loop Buffer.extraer(x) Consumir(x) //código de consumir o lo llamo como función End loop End task p1,p2,p3….,pn:productor c1,c2,c3…,cm:consumidor task buffer is insertar(in x:array 0..N-1 of T) extraer(out x:T) end task body buffer is var buffer:array 0..N-1 of T k:0..N-1 loop accept insertar(in x:array 0..N-1 of T) //buffer=x for k in 0..N-1 loop buffer [k]=x[k] end loop end accept for k in 0..N-1 loop accept extraer(out x:T) x=buffer [k] end accept end loop endloop end task Problema del Productor Consumidor en Ada. La capacidad del buffer será N (constante). Cuáles son los procesos ? Los productores y los consumidores. Vamos a hacer productor y consumidor genéricos (con task type) y los instanciaremos varias veces a cada uno, para modelar los diversos productores y consumidores, todos iguales entre sí. Cuáles son los recursos ? EL BUFFER. Es uno sólo. Va a ser una task. Y va a tener local a él la estructura. Cuáles son las actividades sincrónicas? Insertar y extraer. Bajo mutua exclusión, controlando no lleno y controlando no vacío. Van a ser las citas de la task buffer. El control de no lleno y no vacío será en correspondientes whens. Cuáles son las actividades asincrónicas ? Producir y consumir. El buffer será un buffer circular. Con los datos (array) el próximo a insertar yel próximo a extraer (índices) y la cantidad (contador). task type productor is end task task body productor is var x:T loop producir(x) //ASINCRONICA buffer.insertar_al_final(x) //SINCRONICA end loop end task p1,p2,…,pn:productor task type consumidor is end task task body consumidor is var x:T loop buffer.extraer_primero(x) //SINCRONICA consumir(x) //ASINCRONICA end loop end task c1,c1,…, cm:consumidor task buffer is entry insertar_al_final(in x:T) entry extraer_primero(out x:T) end task task body buffer is const N=… var datos:array 0..N-1 of T p_a_i,p_a_e:0..N-1=0 cant:0..N=0 loop select when (cant < N) accept insertar_al_final(in x:T) //no lleno datos[p_a_i]=x end accept //zona de semisincronización //ya se liberó al productor //antes de aceptar la próxima cita //dejamos la estructura ordenada p_a_i=(p_a_i+1) mod N cant ++ or when (cant >0) accept extraer_primero(x:T) //no vacío x=datos[p_a_e] end accept p_a_e=(p_a_e+1) mod N cant - - end select end loop end task Ejercicio Sean dos buffers B1 y B2, de hasta 50 Enteros. Y sean los siguientes procesos P1, P2, P3, P4, concurrentes, que interactúan con dichos buffers, en ciclo infinito. Observación: hay 6 tasks. P1 lee de teclado (read) e inserta en B1. PRODUCTOR PURO P4 extrae de B2 e imprime (print). CONSUMIDOR PURO. P2 extrae de B1, eleva al cuadrado e inserta en B2. MIXTO. P3 extrae de B1, extrae de B2, suma, y si da mayor que 50, inserta en B2. MIXTO. Se pide armar el seudocódigo de todo esto con Ada.  | |
task P1 is //P1 SE COMPORTA COMO UN PRODUCTOR PURO
end task
task body P1 is
var
x:int
loop
read(x) //ASINCRONICA, HACE LAS VECES DE PRODUCIR
B1.insertar_al_final(x) //SINCRONICA
end loop
end task
task P2 is //es productor respecto a B2 y consumidor respecto a B1.
end task
task body P2 is
var
x:int
loop
B1.extraer_primero(x) //ESTA LÍNEA HACE LAS VECES DE PRODUCIR RESPECTO A B2
B2.insertar_al_final(x*x) // ESTA LÍNEA HACE LAS VECES DE CONSUMIR RESPECTO A B1
end loop
end task
task P3 is //Es productor respecto a B1 y consumidor respecto a B1 y B2
end task
task body P3 is
var
x1,x2:int
loop
B1.extraer_primero(x1)
B2.extraer_primero(x2)
x1=x1+x2
if x1>50
then B2.insertar_al_final(x1)
end
end loop
end task
task P4 is //consumidor puro respecto a B2
end task
task body P4 is
var
x:int
loop
B2.extraer_primero(x) //SINCRONICA
Print(x) //ASINCRONICA, hace las veces de consumir
end loop
end task
task type buffer is
entry insertar_al_final(in x:int)
entry extraer_primero(out x:int)
end task
task body buffer is
const
N=50
var
datos:array 0..N-1 of int
p_a_i,p_a_e:0..N-1=0
cant:0..N=0
loop
select
when (cant < N) accept insertar_al_final(in x:int)
datos[p_a_i]=x
end accept
p_a_i=(p_a_i+1) mod N
cant ++
or
when (cant >0) accept extraer_primero(x:int)
x=datos[p_a_e]
end accept
p_a_e=(p_a_e+1) mod N
cant - -
end select
end loop
end task
B1,B2:buffer
Ejercicio. Es una combinación del P/C con el problema de M/E.
B es un buffer de hasta 50 enteros.
X es una variable entera que puede cambiar en cualquier momento, y debe ser tratada bajo mutua exclusión.
P1 lee de teclado (read) e inserta en B.
P2 extrae de B y si es mayor a x imprime.
P3 extrae de B, suma x, y vuelve a insertar en B.
P1 , P2 y P3 estarán ejecutando a la vez, en loop infinito. En el caso de P2 y P3 van a competir entre sí por acceder a los elementos del buffer y a la variable x, la cual varía constantemente.
task buffer is
entry insertar_al_final(in x:int)
entry extraer_primero(out x:int)
end task
task body buffer is
const
N=50
var
datos:array 0..N-1 of int
p_a_i,p_a_e:0..N-1=0
cant:0..N=0
loop
select
when (cant < N) accept insertar_al_final(in x:int)
datos[p_a_i]=x
end accept
p_a_i=(p_a_i+1) mod N
cant ++
or
when (cant >0) accept extraer_primero(x:int)
x=datos[p_a_e]
end accept
p_a_e=(p_a_e+1) mod N
cant - -
end select
end loop
end task
Para x trabajamos como mutua exclusión:
task controlx is
entry pedir
entry devolver
end
task body control xis
loop
accept pedir
accept devolver
end loop
end task
x estará global al main.
También se podía haber trabajado x con un leer / escribir, con un select.
task P1 is //P1 SE COMPORTA COMO UN PRODUCTOR PURO
end task
task body P1 is
var
x:int
loop
read(x) //ASINCRONICA
Buffer.insertar_al_final(x) //SINCRONICA
end loop
end task
task P2 is //consumidor puro respecto al buffer
end task
task body P2 is
var
x1,x2:int
loop
buffer.extraer_primero(x1) //SINCRONICA
controlx.pedir
x2=x
controlx.devolver
if x1>x2
then
Print(x1) //ASINCRONICA, hace las veces de consumir
End if
end loop
end task
task P3 is
end task
task body P3 is
var
x1,x2:int
loop
buffer.extraer_primero(x1) //SINCRONICA
controlx.pedir
x2=x
controlx.devolver
x1=x1+x2
buffer.insertar_al_final(x1)
end loop
end task
OTRA FORMA, DONDE LA TAREA DE CONTROL DE X LA HACEMOS MÁS AL ESTILO DEL P/C BUFFER TAMAÑO 1
task buffer is
entry insertar_al_final(in x:int)
entry extraer_primero(out x:int)
end task
task body buffer is
const
N=50
var
datos:array 0..N-1 of int
p_a_i,p_a_e:0..N-1=0
cant:0..N=0
loop
select
when (cant < N) accept insertar_al_final(in x:int)
datos[p_a_i]=x
end accept
p_a_i=(p_a_i+1) mod N
cant ++
or
when (cant >0) accept extraer_primero(x:int)
x=datos[p_a_e]
end accept
p_a_e=(p_a_e+1) mod N
cant - -
end select
end loop
end task
task controlx is
entry readx(out y:int)
entry writex(in y:int) //esta la tendría pero para este ejercicio no se usa
end
task body control xis
var
x:int //ACA ESTA LA VARIABLE x a GESTIONAR
//la dejo que se inicialice con basura
loop
select
accept readx(out y:int)
y=x
end accept
or
accept writex(in y:int)´
x=y
end accept
end loop
end task
task P1 is //P1 SE COMPORTA COMO UN PRODUCTOR PURO
end task
task body P1 is
var
x:int
loop
read(x) //ASINCRONICA
Buffer.insertar_al_final(x) //SINCRONICA
end loop
end task
task P2 is //consumidor puro respecto
end task
task body P2 is
var
x1,x2:int
loop
buffer.extraer_primero(x1) //SINCRONICA
controlx.readx(x2)
if (x1>x2)
then
Print(x1) //ASINCRONICA, hace las veces de consumir
End if
end loop
end task
task P3 is
end task
task body P3 is
var
x1,x2:int
loop
buffer.extraer_primero(x1) //SINCRONICA
controlx.readx(x2)
x1=x1+x2
buffer.insertar_al_final(x1)
end loop
end task
Algunos problemas de sincronización extra y su relación con Ada.
Una task S debe coordinar la ejecución de dos porciones de código, que se encuentran en otras tareas. Sean A y B. Y estos son requeridos desde otra tarea externa.
- Queremos ejecutar primero A y luego B
Cómo los sincronizamos por medio de citas?
Accept A
Accept B
- Queremos ejecutar A o B, el que llegue primero, y seguir.
Select
Accept A
Or
Accept B
EndSelect
- Queremos atender todas las llamadas pendientes de A y luego seguir.
loop
Select
Accept A
Else //este else se activa cuando no hay llamadas de A
Exit //este exit corta el loop
End
End
B es un buffer de hasta 50 enteros.
X es una variable entera que puede cambiar en cualquier momento, y debe ser tratada bajo mutua exclusión.
P1 lee de teclado (read) e inserta en B.
P2 extrae de B y si es mayor a x imprime.
P3 extrae de B, suma x, y vuelve a insertar en B.
P1 , P2 y P3 estarán ejecutando a la vez, en loop infinito. En el caso de P2 y P3 van a competir entre sí por acceder a los elementos del buffer y a la variable x, la cual varía constantemente.
task buffer is
entry insertar_al_final(in x:int)
entry extraer_primero(out x:int)
end task
task body buffer is
const
N=50
var
datos:array 0..N-1 of int
p_a_i,p_a_e:0..N-1=0
cant:0..N=0
loop
select
when (cant < N) accept insertar_al_final(in x:int)
datos[p_a_i]=x
end accept
p_a_i=(p_a_i+1) mod N
cant ++
or
when (cant >0) accept extraer_primero(x:int)
x=datos[p_a_e]
end accept
p_a_e=(p_a_e+1) mod N
cant - -
end select
end loop
end task
Para x trabajamos como mutua exclusión:
task controlx is
entry pedir
entry devolver
end
task body control xis
loop
accept pedir
accept devolver
end loop
end task
x estará global al main.
También se podía haber trabajado x con un leer / escribir, con un select.
task P1 is //P1 SE COMPORTA COMO UN PRODUCTOR PURO
end task
task body P1 is
var
x:int
loop
read(x) //ASINCRONICA
Buffer.insertar_al_final(x) //SINCRONICA
end loop
end task
task P2 is //consumidor puro respecto al buffer
end task
task body P2 is
var
x1,x2:int
loop
buffer.extraer_primero(x1) //SINCRONICA
controlx.pedir
x2=x
controlx.devolver
if x1>x2
then
Print(x1) //ASINCRONICA, hace las veces de consumir
End if
end loop
end task
task P3 is
end task
task body P3 is
var
x1,x2:int
loop
buffer.extraer_primero(x1) //SINCRONICA
controlx.pedir
x2=x
controlx.devolver
x1=x1+x2
buffer.insertar_al_final(x1)
end loop
end task
OTRA FORMA, DONDE LA TAREA DE CONTROL DE X LA HACEMOS MÁS AL ESTILO DEL P/C BUFFER TAMAÑO 1
task buffer is
entry insertar_al_final(in x:int)
entry extraer_primero(out x:int)
end task
task body buffer is
const
N=50
var
datos:array 0..N-1 of int
p_a_i,p_a_e:0..N-1=0
cant:0..N=0
loop
select
when (cant < N) accept insertar_al_final(in x:int)
datos[p_a_i]=x
end accept
p_a_i=(p_a_i+1) mod N
cant ++
or
when (cant >0) accept extraer_primero(x:int)
x=datos[p_a_e]
end accept
p_a_e=(p_a_e+1) mod N
cant - -
end select
end loop
end task
task controlx is
entry readx(out y:int)
entry writex(in y:int) //esta la tendría pero para este ejercicio no se usa
end
task body control xis
var
x:int //ACA ESTA LA VARIABLE x a GESTIONAR
//la dejo que se inicialice con basura
loop
select
accept readx(out y:int)
y=x
end accept
or
accept writex(in y:int)´
x=y
end accept
end loop
end task
task P1 is //P1 SE COMPORTA COMO UN PRODUCTOR PURO
end task
task body P1 is
var
x:int
loop
read(x) //ASINCRONICA
Buffer.insertar_al_final(x) //SINCRONICA
end loop
end task
task P2 is //consumidor puro respecto
end task
task body P2 is
var
x1,x2:int
loop
buffer.extraer_primero(x1) //SINCRONICA
controlx.readx(x2)
if (x1>x2)
then
Print(x1) //ASINCRONICA, hace las veces de consumir
End if
end loop
end task
task P3 is
end task
task body P3 is
var
x1,x2:int
loop
buffer.extraer_primero(x1) //SINCRONICA
controlx.readx(x2)
x1=x1+x2
buffer.insertar_al_final(x1)
end loop
end task
Algunos problemas de sincronización extra y su relación con Ada.
Una task S debe coordinar la ejecución de dos porciones de código, que se encuentran en otras tareas. Sean A y B. Y estos son requeridos desde otra tarea externa.
- Queremos ejecutar primero A y luego B
Cómo los sincronizamos por medio de citas?
Accept A
Accept B
- Queremos ejecutar A o B, el que llegue primero, y seguir.
Select
Accept A
Or
Accept B
EndSelect
- Queremos atender todas las llamadas pendientes de A y luego seguir.
loop
Select
Accept A
Else //este else se activa cuando no hay llamadas de A
Exit //este exit corta el loop
End
End
Se ejecutan todas las llamadas a cita A hasta que no queda ninguna pendiente, y ahí se continúa.
Select
Accept A
Or
Accept B
Or
Accept C
Else
D
End
Este código ejecuta A o B o C, el que llegue primero. Pero si no llega ninguno, no se bloquea a esperar, ejecuta D.
Select
When Ba Accept A
Or
When Bb Accept B
Or
When Bc Accept C
Else
D
End
Entra por el else cuanto todos los when dan Falso o cuando no hay llamadas entre las citas asociadas a los when que dieron true.
Se usa para no trancarse al aceptar citas.
Select del lado del que llama
Select
Tarea1.uno //intenta ejecutar esta cita y si no lo logra va a la siguiente.
Or
Tarea2.dos
Or
Tarea3.tres
Else Salida
End
Hay que revisar la implementación. Lo más consistente sería que hagan por orden de llegada. Pero podría haber implementaciones que lo hagan por orden de cómo está escrito.
Otros comandos:
Delay(x) espera x segundos. Hay que ver si ejecuta otras cosas en esos 10 segundos.
Pragma prioridad(x)…………… altera la prioridad del proceso.
Abort tarea1,tarea2,… tareaN mata los procesos incluso desde otro proceso.
Problema de los lectores y escritores en Ada.
El objeto global a leer y escribir, que motiva el problema, es decir, que lo queremos administrar, es una variable de tipo T.
Agregamos un procedimiento.
La diferencia entre procedimiento y task es que la task es un proceso. El procedimiento, si lo ejecuto, será desde alguna task (tal vez main).
Podemos escribir de a muchos ? NO. Siempre de a uno. Entonces la escritura va perfecto adentro de una cita.
Podemos leer de a muchos ? SI. NO PUEDE ir la lectura dentro de una cita. Debemos usar un protocolo de comenzar lectura, terminar lectura.
Nos queda garantizar que la cita comenzar_lectura y la cita lectura_terminada se solicitan en ESE orden y no al revés, lo cual sería caótico. Lo haremos con un procedimiento.
Notar que los parámetros del procedimiento lector y la CITA escritor, son similares.
Var
var_compartida:T; //este es el “tesoro” a administrar, esta variable es la que se quiere leer y escribir. Va global.
Task lectores_y_escritores is
//esta task será una especie de driver de dicha variable que puede leerse y escribirse
procedure lector(valor_leido:out T);
//es solamente para garantizar el orden de las llamadas a las entry, es decir, primero comenzar y después terminar.
entry escritor(valor_escrito:in T); //como sólo puede leer y escribir uno por vez, entonces el que esté en una entry me va a garantizar esa mutua exclusión.
entry comenzar_lectura; //el leer, no puede estar en una entry porque pueden pasar muchos a leer. Notar que comienza lectura, pero no lee. Porque leer pueden leer de a muchos. Eso tiene que ir fuera de la cita.
entry lectura_terminada;
End task
Procedure lector(valor_leido:out T) is
Begin
Lectores_y_escritores.comenzar_lectura;
valor_leido:=var_compartida; //esta var_compartida es global y es la que estamos administrando
Lectores_y_escritores.lectura_terminada
End
task body lectores_y_escritores is
var
lectores:integer:=0;
Begin
//la variable compartida, el tesoro, al comienzo, tiene basura, por lo cual necesitamos, antes de leerla, escribirla.
accept escritor(valor_escrito:in T) do
var_compartida:=valor_escrito
end;
loop //acá está el “core” de la sincronización en el manejo del recurso
select
accept comenzar_lectura
end accept
lectores:=lectores+1
or accept lectura_terminada
end accept
lectores_=lectores-1
or when (lectores=0)
accept escritor (valor_escrito: in T) do
var_compartida:=valor_escrito;
end accept
end select
end loop
End lectores_y_escritores;
Task type task_lector is
End task
Task body task_lector is
Var
x:T
Loop //podía hacerlo sin loop
Lectores_y_escritores.lector(x)
Procesar(x) //sería lo asincrónico que hago con lo leído…
End loop
End task
Task type task_escritor is
End task
Task body task_escritor is
Var
x:T
Loop //podía hacerlo sin loop
Obtener(x) //sería lo asincrónico de donde saco lo escrito…
Lectores_y_Escritores.escritor(x)
End Loop
End Task
l1,l2,…ln:task_Lector
e1,e2,…em:task_escritor
Análisis de prioridades
Hay claramente un favoritismo para los lectores. Por tanto hay aplazamiento indefinido de los escritores a favor de los lectores.
Nadie se cuela a nadie en este caso. Pero está la otra posposición indefinida marcada cuando el lector se cuela.
Versión 2
Un detalle nuevo del lenguaje:
Si tenemos nombre_de_una_entry’count nos da la cantidad de tasks bloqueadas esperando el accept de esa cita.
Este manejo de bajo nivel no es del todo elegante.
var_compartida:T; //ESTE ES EL TESORO A PROTEGER
Task type task_lector is
End task
Task body task_lector is
Var
x:T
Loop //podía hacerlo sin loop
Lectores_y_escritores.lector(x)
Procesar(x) //sería lo asincrónico que hago con lo leído…
End loop
End task
Task type task_escritor is
End task
Task body task_escritor is
Var
x:T
Loop //podía hacerlo sin loop
Obtener(x) //sería lo asincrónico de donde saco lo escrito…
Lectores_y_Escritores.escritor(x)
End Loop
End Task
l1,l2,…ln:trask_Lector
e1,e2,…em:task_escritor
Task lectores_y_escritores is
procedure lector(valor_leido:out T);
entry escritor(valor_escrito:in T);
entry comenzar_lectura;
entry lectura_terminada;
End task
Procedure lector(valor_leido:out T) is
Begin
Lectores_y_escritores.comenzar_lectura;
valor_leido:=var_compartida;
lectores_y_escritores.lectura_terminada
End
Task body lectores_y_escritores is
lectores:integer:=0;
Begin
accept escritor(valor_escrito:in T) do
var_compartida:=valor_escrito
end;
//hasta acá es idéntico a la anterior
loop
select
when escritor’count=0 //cuando no hay escritores esperando
// esto inclina la balanza a favor de los escritores
accept comenzar_lectura;
end accept
lectores:=lectores+1
or accept lectura_terminada;
end accept
lectores_=lectores-1;
or when (lectores=0)
accept escritor (valor_escrito: in T) do
var_compartida:=valor_escrito;
end;
loop //este loop atiende a todos los lectores pendientes
select
accept comenzar_lectura
end accept
lectores:=lectores+1
else exit
end select
end loop
end select
end loop
End lectores_y_escritores;
Análisis de prioridades
Lector intenta colarse a escritor y no lo logra
Escritor intenta colarse a lector:
Como era de esperar encontramos un caso, una familia de casos, donde la solución favorece en este caso a los lectores, permitiendo aplazamiento indefinido de los escritores.
En la medida que no se intercalen de esa forma, será improbable este caso y será buena la solución.
Problema de los Filósofos comensales en Ada.
Cuáles son los procesos?
FILOSOFOS….. del 0 al 4
Cuáles son los recursos ?
PALITOS…….. del 0 al 4, es como un semáforo binario
Qué recurso agrego para evitar deadlock?
Comedor… capacidad 4, es como un semáforo
Cuáles son las actividades asincrónicas ? PENSAR
Cuáles son las actividades sincrónicas? COMER… que en realidad va a ir entre las de obtener los palitos, que son claramente sincrónicas.
Cuáles serán las tasks?
Filosofos…. Array 0..4
Palitos----- Array 0..4
Comedor
Cuáles serán las citas?
Pedir palito
Devolver palito
Entrar comedor
Salir comedor
Cómo sabemos a qué filósofo le corresponde qué palitos?
Al filósofo i, le corresponde, a su izquierda, el palito i, y a su derecha el palito (i+1) mod 4
Pero……… cómo sabe el filósofo cuál es su número? Antes, con semáforos, se lo pasábamos como parámetro. Acá no… cada filósofo tiene que saber su número al comenzar…
Vamos a usar una task auxiliar llamada NUMERADOR que asignará números a los filósofos, por orden de llegada inicial, de 0 a 4.
Esa task va a tener una cita dmn que indicará el número al filósofo.
Esto porque no tenemos en Ada, una especie de Me,quiensoyenelarray…
Task numerador is
Entry dmn(out x:int)
End
Task body numerador is
Var
K:0..4
For k in 0..4 loop
Accept dmn(outx:int)
x=k
end accept
end loop
End
Task type filosofo
End task
Task body filosofo
Var
Izq,der:0..4
Numerador.dmn(izq)
Der=(izq+1)mod 5
Loop
Pensar
Comedor.entrar
Palitos[izq].pedir
Palitos[der].pedir
COMER
Palitos[der].devolver
Palitos[izq].Devolver
Comedor.salir
End loop
End task
Filósofos:array 0..4 of filosofo
Task type palito is //semáforo binario
Entry pedir
Entry devolver
End task
Task body palito is
Loop
Accept pedir
Accept devolver
End loop
End task
Palitos:array 0..4 of palito
Task comedor is //semáforo común
Entry entrar
Entry salir
End comedor
Task body comedor is
Var
enelComedor:0..4=0
Loop
Select
When (enelComedor<4)
Accept entrar
End Accept
EnelComedor++
Or
Accept salir
End Accept
enelComedor- -
end select
End loop
End task
Variante del Problema de los Filósofos.
Ahora los palitos están los 5 en una caja en el centro de la mesa. Toman y sacan de ahí.
El caso de deadlock persiste, porque es cuando cado uno toma un palito a la izquierda.
Task type filosofo
End task
Task body filosofo
Loop
PENSAR //asincrónico
Comedor.entrar
Palitos.pedir
Palitos.pedir
COMER //queda sincronizado
Palitos.devolver
Palitos.Devolver
Comedor.salir
End loop
End task
Filósofos:array 0..4 of filosofo
Task palitos is
Entry pedir
Entry devolver
End task
Task body palitos is
Var
Otorgados:0..5=0
Loop
Select
When otorgados<=4
Accept pedir
End Accept
Otorgados++
Or
Accept devolver
End
Otorgados- -
End Select
End loop
End task
Task comedor is
Entry entrar
Entry salir
End comedor
Task body comedor is
Var
enelComedor:0..4=0
Loop
Select
When (enelComedor<4)
Accept entrar
End Accept
EnelCOmedor++
Or
Accept salir
End
enelComedor- -
end select
End loop
End task
El lenguaje Ada es la mejor opción a nivel de sincronización de procesos en el lenguaje de programación, es decir a alto nivel.
Semáforos lo es a bajo nivel.
Fin Ada. Fin Sincronización de procesos.
.png)
.png)
No hay comentarios.:
Publicar un comentario
Nota: sólo los miembros de este blog pueden publicar comentarios.