Sistemas Operativos: 3. Sistemas Operativos. Concurrencia y sincronización de procesos.

CONCURRENCIA Y SINCRONIZACIÓN DE PROCESOS

Cuaderno completo con este tema:

https://notebooklm.google.com/notebook/b7fd7bb1-441e-4d07-92c6-f05aae407793

Los procesos concurrentes son aquellos que existen simultáneamente en un sistema informático. Como el SO es el manejador de los procesos, se encargará de administrarlos.

Los procesos concurrentes que ejecuten en procesadores o núcleos diferentes, se dirán PARALELOS (multiprocesamiento). Los que no, se dirá que utilizan pseudoparalelismo o concurrencia simulada (multitarea).

El problema es ejecutar un conjunto de (muchos) procesos concurrentes a partir de unos pocos procesadores o núcleos, o en general, de uno sólo. Ya vimos que el multinúcleo es un asunto aparte que se controla en el nivel de programación.

El pseudoparalelismo se implementa en el scheduller del sistema operativo, en base por ejemplo a Round Robin con un quantum de tiempo. Esto es, ejecuta un poco de cada uno y pasa el CPU al siguiente.

Un primer ejemplo. Factorial.

Definición de factorial.

! : N --> N

0!=1

(n+1)!=(n+1)*n!

Propiedad

n!= 1.2.3.4.5…….n = Productoria(i=1 a i=n) (i)

Propongo una nueva forma de considerar el factorial y es así:

n!= 1.2.3.4.5…….n = (1.2.3.4…..n/2)((n/2+1)….n=

=(1.2.3.4…….piso(n/2))*((piso(n/2)+1)……….(n-1).n)=

=productoria(i=1 a i=piso(n/2))(i) * productoria(i=piso(n/2)+1,n)(i)

En definitiva, partimos a la mitad los productos.

Y nos proponemos realizar, en forma concurrente dichos productos.

Por qué ?

Tal vez para ganar tiempo si es que hay más de un núcleo o más de una CPU en la arquitectura subyacente.

A partir de aquí, usaremos pseudocódigo.

Factorial_comun (in n:N , out Factorial:N)

Variables

Acum,i: N

Inicio

Acum=1

For i de 1 a n

Acum=Acum*i

Fin For

Factorial = Acum

Fin

Productoria_de_i (in i,j: N; out Productoria: N)

Variables

Acum,k:N

Comienzo

Acum=1

For k de i a j

Acum=Acum*k

Fin

Productoria=Acum

Fin

Factorial_concurrente (in n:N , out Factorial:N)

Variables

A,B: N

Inicio

Productoria(1,piso(n/2),A)

Productoria(piso(n/2)+1,n,B)

Factorial= A*B

Fin

Este código es correcto en cuanto a que calcula el factorial, PERO TIENE CERO CONCURRENCIA, es secuencial.

Dónde indico que podría llegar a ir a núcleos diferentes ??

Nos falta enriquecer nuestro pseudocódigo para así describir concurrencia!!!!!!!!!!!

Lo haremos introduciendo cobegin / coend (en los libros puede ser parbegin parend también).

Va a funcionar así.

Todo lo que está dentro del cobegin/coend se ejecuta en forma CONCURRENTE.

Por ejemplo:

Cobegin

Coend

Lanza concurrententemente A, B y C, y no ejecuta D hasta que no terminen los tres A, B y C.

A, B y C se van a integrar al resto de procesos que se estuvieran ejecutando concurrentemente. Capaz les tocan núcleos diferentes o procesadores diferentes o simplemente les toca pseudoparalelismo, o un poco de cada cosa. Lo importante es que al programador esto no le importa.

El programador sólo especifica que A, B y C ejecutan concurrentes y sólo cuando los tres terminen, se ejecuta D.

Volviendo al código anterior:

Factorial_concurrente (in n:N , out factorial:N)

Variables

A,B: N

Inicio

COBEGIN

Productoria(1,piso(n/2),A)

Productoria(piso(n/2)+1,n,B)

COEND

Factorial= A*B

Fin

Ahora sí tiene concurrencia. No sabemos si la misma es paralelismo, o pseudoparalelismo y no nos importa al programar. Desde este rol nosotros cumplimos en darle la máxima concurrencia desde el pseudocódigo.

Cuál factorial funciona más rápido ? El común o el concurrente ?

Vamos a plantear varios escenarios donde comparamos el factorial común con el factorial concurrente.

Escenario 1

Único núcleo y con ningún otro proceso además del factorial:

El factorial concurrente no optimiza nada, pues hay que hacer pseudo paralelismo, y encima tenemos un overhead por ejecutar ambos procesos concurrentemente pero en forma totalmente pseudo. Con lo cual el factorial concurrente funciona un poco más lento.

Atención acá: dimos por ganador al primero, porque en realidad el factorial es un caso atípico, pues es todo cuentas, no hace E/S. Recordemos que al hacer E/S la CPU pasa a otro proceso, y por lo tanto si los procesos concurrentes involucraran entrada salida (que en este caso no, insisto) la mezcla concurrente también daría optimizaciones incluso sobre 1 sólo núcleo.

Si hubiera entrada/salida también en este escenario la solución concurrente sería competitiva.

Escenario 2

Único núcleo pero el sistema con otra carga de otros procesos:

Entonces los procesos del factorial concurrente, o el proceso del factorial común, deben competir en el round robin con otros procesos.

Aunque parezca extraño, el factorial común, ejecuta en cada vuelta 1 vez (1 multiplicación o grupo de mult) entre N+1 procesos y el factorial concurrente ejecuta en cada vuelta 2 veces (2 multiplicaciones o grupos de mult) entre N+2 procesos. Con lo cual el factorial concurrente a pesar del overhead, debería salir ganador.

Escenario 3

Hay al menos dos núcleos libres para las productorias:

Si n es suficientemente grande, el factorial concurrente debería ejecutar aproximadamente en la mitad de tiempo que el factorial común.

En conclusión, en todos los escenarios tenemos cosas para ganar con la concurrencia.

Por otra parte, el hecho de ejecutar múltiples procesos a la vez, nos da la posibilidad de modelar situaciones que hasta el momento no podíamos.

Por ejemplo: sensores de velocidad en las ruedas de un auto. Existen los 4 a la vez, necesito consultarlos concurrentemente.

Cuando en la realidad tenemos cosas que existen a la vez es más natural, más claro, modelarlas con procesos que existen a la vez. Y esto, que es importantísimo, nos justifica hablar de concurrencia (y sincronización de lo concurrente) como venimos haciendo, en el nivel de programación.

En definitiva la posibilidad de programar y ejecutar concurrentemente, va a traer ganancias en la mayor parte de los escenarios comunes.

Ejercicio.

Cuál es la concurrencia óptima para este código ??:

a=x+1

b=y+1

c=a-b

d=c/2

cobegin

a=x+1

b=y+1

coend

c=a-b

d=c/2

Ejercicio

Haciendo una sola operación por vez y usando variables temporales… evaluar con máxima eficiencia:

X=(-b+- sqrt(b**2-4.a.c))/2.a

Una posibilidad (más adelante estudiaremos cómo encarar esto de una forma más prolija):

Cobegin

T1=2.a

T2=-b

T3=-4.a

T4=b**2

Coend

T5=T3.c

T6=T4+T5

T7=sqrt(T6) (la suponemos simple la raíz…)

Cobegin

T8=T2+T7

T9=T2-T7

Coend

Cobegin

R1=T8/T1

R2=T9/T1

Coend

En conclusión, cuando tenemos código que podría tener partes concurrentes, debemos evaluar exhaustivamente las precedencias. No se puede paralelizar a lo loco!

Las instrucciones asincrónicas pueden ser evaluadas dentro del cobegin/coend.

Si son sincrónicas no, pues deben esperarse.

Si no marcamos las precedencias al ejecutar código concurrente, todo queda librado a la suerte.

Existe una herramienta, llamada GRAFOS DE PRECEDENCIAS, que permiten modelar estas esperas.

Para dar un grafo, damos los nodos y las aristas.

Def.: Grafo de Precedencias

Nodos: porciones de código a ejecutar.

Existe arista de P1 a P2 sii El proceso asociado a P1, debe ejecutarse antes que el proceso asociado a P2.

El grafo se corresponde con este código:

Cobegin

a=x+y

b=z+1

Coend

c=a-b

w=c+1

Entonces tenemos dos herramientas para describir situaciones de concurrencia y sincronización: grafos de precedencias (QUÉ) y pseudocódigo (CÓMO).

Cuál será más expresiva?

Vamos a estudiar, que el Grafo como herramienta describe mucho más que cobegin coend.

Ejemplo

Notar que usamos begin/end como constructor de un bloque que, a efectos del cobegin/coend, se comporta como una unidad.

Un ejemplo

Un detalle: los grafos deben ser acíclicos, pues de serlo, queda inimplementable.

Las aristas “dobles” no tienen sentido y se tachan.

Las aristas transitivas es posibles tacharlas, no agregan nada.

Las aristas no importa su forma, obvio.

La distribución espacial de los nodos, en este grafo, no me dice nada, así que puedo reubicar.

Encontramos un grafo, de los infinitos que hay, que NO SE PUEDE HACER con cobegin/coend.

Con los cual estamos mostrando que el poder expresivo de cobegin/coend es menor que el de los grafos de precedencia.

DESAFIO

Cuál es el grafo más simple que no se puede hacer con cobegin/coend:

No se puede hacer con cobegin/coend.

Los grafos de precedencias nos dicen qué tipo de problemas nos interesa modelar al hablar de concurrencia y sincronización.

El cobegin/coend viene siendo la herramienta descriptiva que tenemos a nivel de código.

Estamos viendo que los grafos de precedencias tienen mayor poder expresivo que el cobegin/coend.

La conclusión entonces es que nos falta algo en el lenguaje de programación para modelar casos interesantes…

Es decir… Necesitamos otras herramientas!!!

Estudiaremos mecanismos más finos de sincronización, que nos permita más control.

Un primer mecanismo de control será el basado en BUSY WAITING o espera activa.

La espera activa implica poner whiles que detienen la ejecución hasta que se cumpla cierta condición.

Por ejemplo:

Situación de pedido de recurso, y aún no lo tengo

While (recurso ocupado) do ; //esto me hace esperar hasta que el recurso esté disponible.

Situación de pedido de recurso y ahora sí lo tengo.

Esos while presentan un grave problema de desperdicio de ciclos de reloj. Decimos que queman ciclos.

De todos modos analizaremos en profundidad todo esto con el mutua exclusión y por medio de herramientas de análisis de la ejecución concurrente como ser los entrelazados.

Comunicamos procesos porque queremos implementar soluciones que se modelan con múltiples procesos concurrentes accediendo a recursos… Hay varias formas de resolver dicha comunicación.

Por qué mecanismo intercambiarán datos: red? Mensajes? Conexión dedicada, etc

Cómo podremos arbitrar el acceso de los procesos a los diferentes recursos compartidos.

Cómo frenarlos si es necesario.

Cómo especificamos en el código, que queremos trabajar con concurrencia (paralelismo o pseudo paralelismo).

Lo que ponemos dentro del parbegin parend se ejecuta concurrentemente.

El SO no paraleliza automáticamente.

El parbegin/parend es un modelo de concurrencia que nos llega desde la programación. Vamos a usar esto para programar procesos concurrentes.

Tenemos otro enfoque, que es el de los grafos de precedencia.

Esto es, dar un grafo que modele la forma de impementar el paralelismo para un código dado.

GRAFOS DE PRECEDENCIAS:

Código equivalente con parbegin/parend:

P1=x+y

Parbegin

P2=p1+1

P3=p1+3

Parend

P4=p2+p3

Este código modela exactamente lo mismo que el grafo.

Ejercicio

Cómo modelamos este grafo de precedencias con parbegin parend?

Una propuesta:

Parbegin

Par End

Parbegin

Par End

Esta propuesta no modela el grafo de más arriba, si bien lo implementa de una forma aproximada.

Mostremos el código exacto:

Parbegin

Begin

End

Begin

Parbegin

Parend

End

Parend

El orden dentro del paralelismo da igual, ejemplo P5 con P6 o el bloque verde con el amarillo.

Este código NO MODELA el grafo, hace uno parecido, pero no el mismo.

Este grafo NO PUEDE SER modelado con parbegin parend.

Acá nos damos cuenta que una de las herramientas, los grafos, tienen un poder expresivo mayor que la otra, que es el lenguaje de programación.

La arista que une P4 con P6, está uniendo, es decir, está pidiendo que se esperen, parte de un hilo con otro… lo cual no se puede modelar con parbegin parend.

Acá el nudo está en P6àP9 y en P7àP9. No se puede escribir con parbegin/parend.

La herramienta de programación no alcanza en su poder descriptivo para abarcare todos los grafos de precedencias. Esto nos sugiere algo bastante obvio y es que con parbegin parend solamente, no vamos a poder programar la sincronización de procesos.

Vamos a ver en breve que con semáforos esto es posible.

ESTUDIO DEL ANÁLISIS DE EJECUCIÓN CONCURRENTE POR MEDIO DE “ENTRELAZADOS”

Esta técnica es una forma de inspeccionar en detalle, qué está ocurriendo exactamente en la ejecución de un código. Es una extensión bidimensional, de la prueba de escritorio de los programas.

Ejemplo

Tenemos P1 y P2 que ejecutan concurrentemente, teniendo como variables compartidas a a y b.

a y b se inicializan en 1

a=a+b

b=0

a++

b=a+b

Estas son todas las formas posibles de ejecutar concurrentemente P1 y P2.

Notemos que según como se intercalen las instrucciones en el procesador, podemos obtener 3 resultados diferentes.

Se dice que un código de este tipo es inconsistente.

En este caso da lo mismo para cualquier combinación de caminos…

NO VAMOS A DECIR QUE ES CONSISTENTE.

Diremos que no emergió inconsistencias.

Para probar consistencia habría que analizar el código a nivel de Assembler, y salvando el contexto al perder la CPU, cosa que no haremos.

Ejemplo con While

Estamos trabajando sobre el sistema operativo, buscando explicar qué pasa DENTRO del sistema operativo.

Problemas como el de la mutua exclusión, ocurren dentro del sistema operativo, pero los analizamos trabajando a nivel de programación, sobre un sistema que resuelve en forma transparente para nosotros, el schedulling, multinúcleo, interrupciones, etc.

Características que pediremos a los programas que involucren concurrencia y sincronización

Correctitud… hacer lo especificado. Acepto confiabilidad.
Consistencia… resultados únicos. Acepto “no emerge inconsistencias”.
Ausencia de Deadlocks …. No se tranque. Acepto “no emergen deadlocks”.
Ausencia de Posposición (=aplazamiento) Indefinida …. No deje a nadie para lo último indefinidamente. Acepto “no se observa posposición indefinida”.

Primera cosa, estos 4 pedidos son DEMASIADO AMBICIOSOS.

Por qué ?

Porque son imposibles de probar. Igualmente vivimos con ello.

En los lenguajes imperativos, demostrar que el código hace lo que la especificación pide, es un sueño, es algo tremendamente inocente, es imposible de demostrar. DIJKSTRA.

Nosotros no entregamos software correcto, entregamos software confiable, que es mucho menos que correcto… se testeó rigurosamente…

En los lenguajes declarativos (Haskell, Prolog…) se pueden ensayar pruebas de correctitud.

Vimos con los entrelazados, que decíamos “no emerge inconsistencias “ en lugar de decir “es consistente”. Esto es porque un análisis a nivel de Assembler, es muy costoso, es imposible.

Deadlocks. Dos o más procesos están en deadlock, cuando cada uno espera por otro proceso del conjunto, y todos están bloqueados.

Aplazamiento indefinido. Ocurre cuando a algún proceso sistemáticamente se le niega la posibilidad de avanzar en la ejecución, sin estar bloqueado (se le cuelan, por prioridades mal manejadas).

Primer problema a estudiar.

Problema de la MUTUA EXCLUSION.

RSR= Recursos Serialmente Reusables. Son recursos que podemos reutilizar infinitas veces, pero UN PROCESO POR VEZ.

Por ejemplo una impresora, una variable global, un archivo, etc.

Cuando lo tengo, no debemos permitir que ningún proceso se entrometa hasta que lo devuelva.

Problema típico: saldo del banco. Cuando lo voy a modificar, por ejemplo porque el cliente sacó plata por el cajero automático, debo asegurarme que nadie lo está modificando. Y bloquear modificaciones.

El problema de la mutua exclusión implica:

VARIOS PROCESOS CONCURRENTES QUIEREN ACCEDER AL MISMO R.S.R. HAY QUE ORGANIZAR UNA FILA DE ESPERA.

Solución bruta: HAGAN una sola y única FILA por el recurso, y listo.

Es inaceptable. Queremos concurrencia, es un beneficio derivado de las tecnologías que tenemos!

Vamos a aceptar la concurrencia, y vamos a controlar que se acceda uno por vez, y esto implicará un acceso en orden, en fila en última instancia, pero cada proceso desde su concurrencia.

Vamos a trabajar con un problema de mutua exclusión que nos permita discutir cosas tangibles: ALICE & BOB.

ALICE & BOB, en el problema de la mutua exclusión:

Son vecinos, en dos casas que comparten el patio. Cada uno tiene un perro. Los perros cada tanto desean salir al patio. Debemos sincronizarlos para que saquen a los perros cuando estos lo soliciten, pero NO DEBEN ENCONTRARSE EN EL PATIO.

A & B son los dos procesos concurrentes. El patio es el RSR. Y la acción llamada sección crítica, es pasear al perro.

Hay que programarlos para lograr esto!

Algoritmo 1

A & B tienen un cartel. El cartel indica quién puede sacar al perro. Cada uno que pasea al perro deja el nombre del otro en el cartel.

Proc Main

Variables

Turno: {1,2}=1

Cobegin

Alice

Bob

Coend

Proc Alice

While true do

While Turno!=1 do; // mientras turno sea distinto de 1, espera ahí, sin avanzar.

Pasear_Perro_Alice //notar que está debajo del while, y no dentro!!!!!!

Turno=2

Otras_tareas_Alice_asíncrono

EndWhile

End Alice

Proc Bob

While true do

While Turno!=2 do;

Pasear_Perro_Bob

Turno=1

Otras_tareas_Bob_asíncrono

EndWhile

End Bob

Primer discusión: “si alguno de los dos pasea mucho rato, tranca al otro”. Esto es inherente a los recursos compartidos. Si el que, estando dentro del turno que esperó y le tocó, luego se demora… está en su derecho… va a demorar a todos, pero es parte del haber aceptado compartir el recurso.

Segunda discusión: “ si le cae un rayo y se muere en el patio”… esto es lo que pasa cuando se rompe la impresora, cuando se tranca el cajero automático y somos 40 en la fila, etc etc

Tercera discusión: “si se loopea en el uso del recurso”… ahí estamos fritos.

Todos los tres escenarios, son producto de compartir recursos.

El while true nunca termina, se quedan así. Es habitual modelar servicios en el SO de esa forma.

Vamos a hacer el estudio de la ejecución por medio de entrelazados

Proc Alice

While true do

1 While Turno!=1 do;

2 Pasear_Perro_Alice

3 Turno=2

4 Otras_tareas_Alice_asíncrono

EndWhile

End Alice

Proc Bob

While true do

1’ While Turno!=2 do;

2’ Pasear_Perro_Bob

3’ Turno=1

4’ Otras_tareas_Bob_asíncrono

EndWhile

End Bob

No se observan inconsistencias, ni deadlocks ni aplazamiento indefinido.

Tampoco se cae en la zona prohibida (el círculo) así que la solución va bien.

Hagamos los while true do de más afuera.

No emergió deadlocks.

No emergió aplazamiento indefinido.

Emergió una inconsistencia, pero es explicable en términos de que primero pasea A y luego B y en ese caso queda favoreciendo a A. Y del otro lado, si primero pasea B y luego A, quedará favoreciendo a B. Lo cual es coherente. Que el cartel quede para un lado o para otro, no nos molesta, diremos que es una inconsistencia aceptable.

Una cosa muy importante: NO CAEN EN LA ZONA DE MUTUA EXCLUSION, o sea que no pasea a los perros a la vez.

Un problema…

Hay algo que A & B no pueden hacer, y que la letra no lo prohíbe… PASEAR AL PERRO DOS VECES SEGUIDAS!

Observación:

Pasear al perro es sincrónico.
Hacer otras tareas es asincrónico.

Entonces esta solución plantea un secuenciamiento no previsto en la letra.

Si uno de los dos se cae, tanto en la zona sincrónica (tranca el recurso) como en la asincrónica (tranca el algoritmo estando libre el recurso!), ya nadie puede pasear al perro.

Si los perros son tales que uno necesita salir al patio a cada rato y el otro no… el primero lo va a pasar muy mal.

Esta solución es inaceptable!

Algoritmo 2

Alice & Bob acuerdan usar una bandera cada uno.

La bandera indicará si el patio está reservado por uno de ellos.

De la siguiente forma, informal: cuando el perro quiere salir, miro que no esté la bandera del otro (y si estuviera espero), levanto la bandera, y saco el perro a pasear, entro el perro, bajo la bandera, cierro bien rápido la puerta por las dudas, y hago otras tareas hasta que el perro me pida de nuevo para salir.

Parece solucionar lo anterior.

Proc Main

Variables

Alice_solicita, Bob_solicita: Bool = F

Cobegin

Alice

Bob

Coend

Proc Alice

While true do

While Bob_Solicita do;

Alice_Solicita=T

Pasear_Perro_Alice

Alice_Solicita=F

Otras_tareas_Alice_asíncrono

EndWhile

End Alice

Proc Bob

While true do

While Alice_Solicita do;

Bob_Solicita=T

Pasear_Perro_Bob

Bob_Solicita=F

Otras_tareas_Bob_asíncrono

EndWhile

End Bob

Vamos a hacer el entrelazado:

Proc Alice

While true do

1 While Bob_Solicita do;

2 Alice_Solicita=T

3 Pasear_Perro_Alice

4 Alice_Solicita=F

5 Otras_tareas_Alice_asíncrono

EndWhile

End Alice

Proc Bob

While true do

1’ While Alice_Solicita do;

2’ Bob_Solicita=T

3’ Pasear_Perro_Bob

4’ Bob_Solicita=F

5’ Otras_tareas_Bob_asíncrono

EndWhile

End Bob

Observaciones:

Ambos pueden sacar al perro cuando quieren. Se solucionó el problema del algoritmo 1.

No emerge deadlock ni aplazamiento indefinido.

No emerge inconsistencias.

PERO se viola la mutua exclusión.

Siempre ? NO, en una familia de secuencias desafortunadas:

Una de ellas:

A mira y decide pasar, pierde el procesador; B mira y decide pasar, pierde el procesador; A levanta la bandera, pierde el procesador; B levanta la bandera, pierde el procesador; A pasea perro a la vez que B y todos se pelean.

Otra forma de verlo, en el multinúcleo. A y B, los dos a la vez, miran y ven que el otro no tiene levantada la bandera; luego ambos a la vez levantan la bandera; luego ambos a la vez salen y todos se pelean.

Esto hace que esta solución sea inaceptable.

Algoritmo 3

Si el problema es que miran y luego levantan la bandera… por qué no levantar la bandera primero y después mirar ?

Proc Main

Variables

Alice_solicita, Bob_solicita: Bool = F

Cobegin

Alice

Bob

Coend

Proc Alice

While true do

Alice_Solicita=T

While Bob_Solicita do;

Pasear_Perro_Alice

Alice_Solicita=F

Otras_tareas_Alice_asíncrono

EndWhile

End Alice

Proc Bob

While true do

Bob_Solicita=T

While Alice_Solicita do;

Pasear_Perro_Bob

Bob_Solicita=F

Otras_tareas_Bob_asíncrono

EndWhile

End Bob

Vamos a hacer el entrelazado:

Proc Alice

While true do

1 Alice_Solicita=T

2 While Bob_Solicita do;

3 Pasear_Perro_Alice

4 Alice_Solicita=F

EndWhile

End Alice

5 Otras_tareas_Alice_asíncrono

Proc Bob

While true do

1’ Bob_Solicita=T

2’ While Alice_Solicita do;

3’ Pasear_Perro_Bob

4’ Bob_Solicita=F

5’ Otras_tareas_Bob_asíncrono

EndWhile

End Bob

Aparece una secuencia desafortunada, en la cual A y B quedan ambos con la bandera levantada, esperando a que el otro la baje, cosa que no hará, es un deadlock.

Más adelante, cuando estudiemos el tema deadlocks en detalle veremos que esto no es precisamente un deadlock, pero ambos quedan trancados y es una situación asimilable a un deadlock.

Obviamente que si no caemos en la secuencia desafortunada, hay muchas secuencias que funcionan OK, como pasaba en el versión 2.

Pero con que una secuencia tranque todo, ya invalida la solución.

Por supuesto que no se puede tentar la suerte, y esta solución es inaceptable.

El entrelazado sirvió como herramienta para analizar qué está pasando.

Veremos una versión 4, adaptada de la 3, que funciona. Algoritmo de Dekker y Peterson, que funcionan.

Algoritmo 4

Cuando en la versión 3 quedan los dos con la bandera levantada, se sorteará un tiempo aleatorio de bajada de la bandera.

Proc Main

Variables

Alice_solicita, Bob_solicita: Bool = F

Cobegin

Alice

Bob

Coend

Proc Alice

While true do

Alice_Solicita=T

While Bob_Solicita do

Alice_solicita=F

Esperar un tiempo aleatorio

Alice_solicita=T

Fin While

Pasear_Perro_Alice

Alice_Solicita=F

Otras_tareas_Alice_asíncrono

EndWhile

End Alice

Proc Bob

While true do

Bob_Solicita=T

While Alice_Solicita do

Bob_Solicita=F

Esperar un tiempo aleatorio

Bob_solicita=T

endWhile

Pasear_Perro_Bob

Bob_Solicita=F

Otras_tareas_Bob_asíncrono

EndWhile

End Bob

No podemos hacer el entrelazado porque involucra un random.

Los tiempos aleatorios se pueden acotar…

Cuando no funcionaría? Cuando ambos sortean a la vez el mismo tiempo aleatorio…

En tal caso, sortearían de nuevo.

Y esto no funcionaría, cuando de nuevo sortearon lo mismo.

Y así sucesivamente.

Sin embargo, la probabilidad de esa conjunción es bajísima.

P(igual sorteo 1 E igual sorteo 2 E igual sorteo3….)=P(igual sorteo 1).P(igual sorteo 2)….

Las probabilidades son números entre 0 y 1, y encima son pequeños, pues son casos de borde.

Por tanto la probabilidad de que coincidan es MUY BAJA. Y damos por buena la solución.

Convivimos con muchísimos algoritmos así.

Por ejemplo en las redes.

El IEEE 802.3, … y todos los 802.x se basan en el protocolo Ethernet… que se basa en el protocolo CSMA/CD, que se basa en el protocolo ALOHA.

https://es.wikipedia.org/wiki/ALOHAnet#:~:text=El%20protocolo%20ALOHA%20es%20un,transmisi%C3%B3n%2C%20intenta%20reenviarlos%20m%C3%A1s%20tarde.

Algoritmo 5.

Algoritmo de Dekker.

Este algoritmo NO usa un random.

Utiliza 2 banderas, como en la versión 3, y un cartel, para evitar el caso de deadlock.

Variables

proceso_favorecido: (primero, segundo)=primero; // cartel

p1_desea_entrar, p2_desea_entrar: Bool= FALSE; //banderas

Proc Main

cobegin

proceso_uno;

proceso_dos

coend

End Main

Proc proceso_uno

while True do

1 p1_desea_entrar=true; //levanta la bandera

2 while p2_desea_entrar do //mientras el otro también esté con la bandera levantada

3 if proceso_favorecido=segundo then //el cartel favorece al otro

4 p1_desea_entrar=false //bajo la bandera

5 while proceso_favorecido= segundo do; //busy waiting

6 p1_desea_entrar=true //levanto de nuevo la bandera

endif

endwhile

7 seccion_critica_1 //paseo perro

8 proceso_favorecido=segundo //cartel apuntando al otro

9 p1_desea_entrar=false //bajo la bandera

otras_tareas_uno //asincrónico

endwhile

End proceso_uno

Proc proceso_dos

while true do

1’ p2_desea_entrar=true

2’ while p1_desea_entrar do

3’ if proceso_favorecido=primero then

4’ p2_desea_entrar=false

5’ while proceso_favorecido= primero do;

6’ p2_desea_entrar=true

endif

endwhile

7’ seccion_critica_2

8’ proceso_favorecido=primero

9’ p2_desea_entrar=false

otras_tareas_dos

endwhile

End proceso_dos

Vamos a hacer el entrelazado de este código.

No emergió deadlock, ni aplazamiento indefinido.

La inconsistencia que aparece es totalmente explicable, en cuanto a que es el cartel que queda favoreciendo a uno u otro según el orden.

Las líneas 4 y 5 NO HAN SIDO EJECUTADAS!?

Explicación:

Con la condición inicial 1FF, no son alcanzables, pero con 2FF si. Y este 2FF aparece luego de los while del while true do.

4’ y 5’ son alcanzables con la ejecución favoreciendo al proceso 1.

Entonces 4 y 5 lo serán con la ejecución favoreciendo al proceso 2.

Y qué pasa con los whiles de afuera ?

Como vemos en el diagrama de más arriba, se completaría un nuevo entrelazado empezando en 2FF y combinando valores con el actual.

Acá está cómo queda:

Algoritmo 6

Algoritmo de Peterson

No es más que una reescritura astuta de Dekker.

Variables

proceso_favorecido: (primero, segundo)=primero;

p1_desea_entrar, p2_desea_entrar: Bool= FALSE;

Proc Main

cobegin

proceso_uno;

proceso_dos

coend

End Main

Proc proceso_uno

while True do

1 p1_desea_entrar=true //levanta la bandera

2 proceso_favorecido=segundo //cede la preferencia al otro

3 while (p2_desea_entrar and (proceso_favorecido=segundo)) do; //mientras el otro también esté con la bandera levantada y él conserve la preferencia, hacemos el Busy Waiting

4 seccion_critica_1 //paseo perro

5 p1_desea_entrar=false //bajo la bandera

otras_tareas_uno //asincrónico

endwhile

End proceso_uno

Proc proceso_dos

while True do

1’ p2_desea_entrar=true //levanta la bandera

2’ proceso_favorecido=primero //cede la preferencia al otro

3’ while (p1_desea_entrar and (proceso_favorecido=primero)) do; //mientras el otro también esté con la bandera levantada y él conserve la preferencia, hacemos el Busy Waiting

4’ seccion_critica_2 //paseo perro

5’ p2_desea_entrar=false //bajo la bandera

otras_tareas_dos //asincrónico

endwhile

End proceso_dos

Vamos a hacer el entrelazado de este código.

Faltan los whiles de afuera.

Concluimos lo mismo que con Dekker. Es decir, no emergen problemas.

Estas versiones 4, 5 y 6 resuelven el problema de la mutua exclusión.

No hay deadlocks, aplazamiento indefinido, violaciones a la mutua exclusión, cambios de la letra, ni inconsistencias intolerables.

Por todo lo anterior los damos por buenos.

SIN EMBARGO, el problema de que la sincronización que aquí se propone se basa en el BUSY WAITING es demasiado grave para dejarlo pasar.

Esta primera forma de sincronización funciona pero no es aceptable por ineficiente.

Trabajaremos con primitivas de bajo nivel, bloqueantes (que cuando se espere se esté en estado bloqueado) que son los SEMAFOROS.

Estos algoritmos tienen dos problemas:

BUSY WAITING, que es una forma de espera que desperdicia ciclos de reloj, y por tanto es inaceptable.
DIFICULTAD DE GENERALIZACIÓN, qué pasa si en vez de ser A y B son, A B y C ? qué pasa si además de ser A B y C, dos perros en el patio están OK pero 3 no.

Con los semáforos, vamos a conseguir soluciones que para esperar BLOQUEEN (y esto será más eficiente, ya no se desperdician ciclos) y además serán soluciones más sencillas y por tanto más fáciles de generalizar.

Un enfoque y material complementario para el problema de la mutua exclusión:

Problema de la mutua exclusión

Condiciones de carrera

Dos procesos concurrentes tratan de acceder a la vez a una variable compartida… Esto va a ocasionar problemas.

Vamos a definir como sección crítica a la parte del código de los procesos que queremos ejecutar en forma exclusiva sobre un recurso. Para ello debemos bloquear al acceder.

Cuando tenemos dos procesos a la vez y los mismos tratan de acceder a la vez a la región crítica,

Entonces el segundo se bloquea hasta que el primero termina.

No pueden estar ambos a la vez en la región crítica. El SO gestiona esas cosas.

Por ejemplo dos procesos intentan imprimir a la vez, porque ambos ven la misma impresora o bien en la misma computadora o bien a través de la red. Si ambos imprimen a la vez, es un caos. No se puede.

Otro ejemplo. Si dos procesos acceden a la vez a un registro en una base de datos. Por ejemplo, tratamos de extraer dinero del cajero automático y exactamente en el mismo instante tratamos de hacer un giro tratando de vaciar la cuenta dos veces! Esto sería catastrófico. Quien lo evita? Nuevamente el sistema operativo (en realidad también interviene el nivel de BD en este ejemplo, etc).

Y ahí, en estos desafíos, toman sentido herramientas como los semáforos por ejemplo, que estudiaremos.

Adelantando un poco…

S: semáforo

Proc extraer por cajero

Blablablablabla

Bloquear S

Entregar dinero solicitado sea X

Saldo=Saldo-X

Repercutir Saldo

Desbloquear S

Blablablablabla

Fin

Proc hacergiro

Blablablablabla

Bloquear S

Girar X

Saldo=Saldo-X

Repercutir Saldo

Desbloquear S

Blablablabal

Fin

El que bloquea segundo espera

Adelantando un poco 2

Ponemos en cada arista un semáforo. Y los inicializamos apagados.

Para ejecutar cada nodo.

Esperar por (aristas entrantes)

Ejecuto

Liberar (aristas salientes)

De esta forma, subdividiendo en 7 hilos y con semáforos sale muy sencillo.

Volviendo al problema de la mutua exclusión.

Este es un primer problema de sincronización de procesos.

Hay varios enfoques…

Exclusión mutua con espera ocupada:

Primer familia de soluciones: basadas en espera activa o busy waiting.

La espera activa quema ciclos de reloj para sincronizar, o sea, desperdicia CPU haciendo nada, hasta que es su turno.

Tenemos dos procesos concurrentes (podrían ser hilos).

Ambos deben acceder a lo que llamaremos su sección crítica. Al acceder deben hacerlo en forma exclusiva. O sea que si uno entra el otro espera.

Tenemos un primer código, que utiliza una variable llamada número_proceso, que sincroniza ambos procesos.

Versión 1

La sección crítica está DESPUÉS DEL WHILE DE BUSY WAITING, NO DENTRO.

FUNCIONA ? NO. Los obliga a alternarse. Y eso no estaba en la letra.

Versión 2

Ahora sí alternan.

Pero hay un problemita…

Si cada uno mira la bandera del otro y la ve en false, entonces ambos acceden a la vez y chocan.

DESCARTADA.

Esta solución a veces funciona, pero hay una secuencia desafortunada que conduce al deadlock.

Cuarta versión

Esta versión funciona.

Hay dos banderas, y si había situación de discusión se espera un tiempo aleatorio.

Nos hace un ruido lo del aleatorio, pero funciona!!

Funciona.

Utiliza dos banderas y un cartel.

Si hay situación de discusión, se consulta el cartel.

Este algoritmo podría ser más simple (y menos claro), lo veremos en Peterson.

Algoritmo de Peterson

Es igual de Dekker pero con código más corto.

Tenemos varias soluciones (las últimas son las mejores) al problema de la mutua exclusión, pero en base a técnicas de busy waiting.

Esto es inaceptable, pues queman ciclos de reloj sin ejecutar nada cada vez que hay que esperar.

Nosotros que estamos analizando el nivel de SO, donde las soluciones impactarán en el desempeño del sistema todo, no podemos tolerar ese tipo de ineficiencias.

Pensemos que este arbitraje de recursos se da constantemente en el sistema operativo.

Necesitamos otro tipo de soluciones. VAMOS HACIA LOS SEMAFOROS.

Una primera versión rudimentaria del problema del productor consumidor

Defectos:

No sabemos si hay busy waiting, porque no sabemos cómo está implementado sleep.

No está claro que no se choquen múltiples productores con múltiples consumidores, y el código colapse.

Y el sleep es un gran misterio… supongamos que funciona bien.

Sistemas Operativos

3. Sistemas Operativos. Concurrencia y sincronización de procesos.

No hay comentarios.:

Publicar un comentario

Sistemas Operativos.

Denunciar abuso