MODULO 4

SINCRONIZACIÓN Y
COMUNICACIÓN ENTRE
PROCESOS
 Sincronización y comunicación
entre procesos

➢En los sistemas operativos, en general, los procesos que trabajan

juntos comparten con frecuencia un espacio común para
almacenamiento, en el que cada uno puede leer o escribir, o
también comparten un recurso.

➢El acceso a estos recursos compartidos generan problemas de uso

y de comunicación entre los procesos.

➢Para resolver estos problemas de competencia entre procesos, se

utilizan dos mecanismos: la sincronización y la comunicación.
 Definimos a ambos términos como:

➢SINCRONIZACIÓN ENTRE PROCESOS: Ordenamiento de las

operaciones en el tiempo debido a las condiciones de carrera
(acceder a los diversos recursos asincrónicamente).

➢COMUNICACIÓN ENTRE PROCESOS: Intercambio de Datos.

La comunicación permite que los procesos cooperen entre sí en
la ejecución de un objetivo global, mientras que la sincronización
permite que un proceso continúe su ejecución después de la
ocurrencia de un determinado evento.
 Problemas Concurrentes:
Los programas pueden ser clasificados en secuenciales y en concurrentes.

Un programa secuencial especifica una secuencia de instrucciones que se

ejecutan sobre un procesador que definimos como proceso o tarea.
Un programa concurrente especifica dos o más procesos secuenciales que
pueden ejecutarse concurrentemente como tareas paralelas.

Un proceso secuencial se caracteriza por no ser dependiente de la velocidad

de ejecución y de producir el mismo resultado para un mismo conjunto de
datos de entrada, mientras que en un proceso concurrente (o lógicamente
paralelo) las actividades están superpuestas en el tiempo (una operación
puede ser comenzada en función de la ocurrencia de algún evento, antes de
que termine la operación que se estaba ejecutando).

La programación concurrente requiere de mecanismos de sincronización y

comunicación entre los procesos.
 Concurrencia
• Desde un punto de vista formal, la concurrencia no se
refiere a dos o más eventos que ocurren a la vez sino a dos
o más eventos cuyo orden es no determinista, esto es,
eventos acerca de los cuales no se puede predecir el orden
relativo en que ocurrirán.

• Si bien dos procesos (o también dos hilos) completamente

independientes entre sí ejecutándose simultáneamente
son concurrentes, nos ocuparemos principalmente de
procesos cuya ejecución está vinculada de alguna manera.
 Algunos conceptos de concurrencia
Operación atómica: Manipulación de datos que requiere la garantía de que se ejecutará como una
sola unidad de ejecución, o fallará completamente, sin resultados o estados parciales
observables por otros procesos o el entorno. Esto no necesariamente implica que el sistema no
retirará el flujo de ejecución en medio de la operación, sino que el efecto de que se le retire el
flujo no llevará a un comportamiento inconsistente

Race condition: Situación en la cual el resultado de la ejecución de 2 o más

procesos interactuantes depende del orden de ejecución de los mismos.

Sección (o región) crítica : Es la fase o etapa en la vida de ese proceso concurrente en la cual
accede a un recurso crítico para modificarlo o alterarlo El área de código que requiere ser
protegida de accesos simultáneos donde se realiza la modificación de datos compartidos.

Recurso compartido: Un recurso al que se puede tener acceso desde más de un

proceso. En muchos escenarios esto es un variable en memoria (como cuenta en el jardín
ornamental), pero podrían ser archivos, periféricos, etcétera.

Mutua exclusión: sólo un proceso a la vez puede estar ejecutando en su región crítica (lo accede y
lo usa).
• Es función del programador asegurar la atomicidad
de forma explícita, mediante la sincronización de
los procesos.

• El sistema no debe permitir la ejecución de parte

de esa área en dos procesos de forma simultánea
(sólo puede haber un proceso en la sección crítica
en un momento dado).
 Especificaciones concurrentes:

Instrucciones FORK - JOIN

La instrucción fork (tenedor, horqueta, separador) indica el

comienzo de la concurrencia

join recombina (junta) la concurrencia en una sola instrucción

indicando que ha concluido la concurrencia.

La instrucción fork etiq produce dos ejecuciones concurrentes en

un programa.
• sent1;
• sent2;
• fork etiq;
fork etiq
• ...
• join; ... etiq
• ...
• end; join ...

• etiq: sent1; quit

• sent2;
• ...
• sentn;
• quit;
 Resumen de fork y join
➢fork es, en esencia, un goto que simultáneamente bifurca y
continúa la ejecución.

➢quit y join permiten que dos ramas de actividad vuelvan a

juntarse.

➢quit: Lo ejecuta el proceso hijo cuando terminó su tarea.

➢join: Lo ejecuta el proceso padre para esperar a que termine el

hijo.

No es estructurado por su estructura de control.

 Grafos de precedencia
Un grafo de precedencia es un grafo sin ciclos donde cada nodo
representa una única sentencia o un conjunto secuencial de
instrucciones
Condiciones de concurrencia (Bernstein)
• Definición: Dos sentencias cualesquiera Si y Sj pueden
ejecutarse concurrentemente produciendo el mismo
resultado que si se ejecutaran secuencialmente sí sólo sí se
cumplen las siguientes condiciones:

• 1. R (Si)  W (Sj) = (ø )
• 2. W(Si)  R (Sj) = (ø )
• 3. W(Si)  W (Sj) = (ø )

• Si las tres condiciones producen conjunto vacío, podemos

asegurar que no hay dependencia entre las sentencias.
➢Conjunto de Lectura: R (Si) = ( a1, a2,... , am)
El conjunto de lectura de la sentencia Si es aquel formado por
todas las variables que son referenciadas por la sentencia Si
durante su ejecución sin sufrir cambios.

➢Conjunto de escritura: W (Si) = (b1, b2,... , bn)

El conjunto de escritura de la sentencia Si es aquel formado por
todas las variables cuyos valores son modificados durante la
ejecución de Si.
Problema del jardín ornamental
 Problema del jardín ornamental

Lo esperable es que el valor de la variable cuenta termine

en 40, pero no siempre ocurre. ¿Cuál es la razón?

La instrucción cuenta = cuenta + 1 se descompone en

las siguientes instrucciones (en arquitecturas Intel x86):
LEER Leer cuenta desde la memoria (mov $cuenta,%rax).
INC Incrementar el registro (add $1,%rax).
GUARDAR Guardar el resultado nuevamente en memoria (mov%rax,$cuenta).

Supongamos que en medio de estas operaciones ocurre un

process-switch … ¿Qué ocurre con el valor de cuenta?
Las soluciones comunes al problema de
mutua exclusión siguen un protocolo de
tres pasos.

Protocolo de negociación (de entrada

a la Región Critica)
Mutua exclusión (RC)
• {
Uso de la Región Critica
• entradaRC();
• usarRecurso();
• salidaRC(); Protocolo de Liberación (salida de la
Región critica)
}
 Posibles soluciones al problema del
Jardín ornamental
Problema: cuenta = cuenta + 1 Debe ser atómica!

• Intento 1: No utilizar multitarea

En este sencillo ejemplo una posible solución es utilizar únicamente

una entrada (o torniquete). Esto podría ser una solución en tanto que
no haya mucha gente que haga cola para entrar.
Sin embargo, en un sistema análogo de reserva de pasajes aéreos no
parece tener mucho sentido que todos los pasajeros deban ir a Japón
a sacar su pasaje. Por otro lado, ya deberían ser claras las ventajas de
la multitarea y el poseer distintos núcleos.
! Costoso
• Intento 2: Suspender la multitarea durante la sección
crítica

Una versión más relajada de la alternativa anterior es

suspender la multitarea durante la ejecución de la sección
crítica. Así, un torniquete deberá hacer:

• 1 disable(); /* Suspender temporal las interrupciones */

• 2 cuenta = cuenta + 1;
• 3 enable(); /* Habilitar nuevamente las interrupciones */

• ! Inviable en multiusuarios:
• Deshabilitar en forma indefinida y capturar el CPU
• No funciona en multicore ya que solo se deshabilitan interrupciones por procesador
• Posibles errores de dispositivos si el tiempo en la sección crítica es muy largo
• Intento 3: Utilizar una bandera

Utilizar una bandera parece ser una solución muy sencilla: mediante
una variable de bandera se indica si hay un proceso en la región
crítica:

1 int bandera = 0; /* 0 => región crítica libre, 1 => ocupada */

2 int cuenta = 0;
3 /* ... */
4
5 /* Torniquete1 */
6 /* ... */
7 if (bandera) wait;
8 /* Aquí bandera=0 */ Falla!!!
9 bandera = 1; /* Inicio de la sección crítica */ bandera es un
10 cuenta = cuenta + 1; rec compartido y
11 bandera = 0; /* Fin de la sección crítica */ su acceso no es
atómico
• Intento 4: Manejar la bandera con instrucciones
atómicas

Algunas arquitecturas de computadoras permiten

realizar determinadas operaciones sencillas (como
actualizar una bandera) de forma atómica (p. ej.: VAX tiene
la instrucción test_and_set y el i386 tiene la instrucción INC.
Usando esto, la solución es:

1 int bandera; /* 0 => desocupada */

Falla!!!
2
Puede generar
3 while (++bandera != 1) { inanición si un
4 bandera--; /* Debe generar "INC" */ proceso no libera
5 } el recurso.
6 /* Sección crítica */ También usa
7 cuenta = cuenta + 1;
"espera
8
ocupada"
9 bandera--;
• Intento 5: Utilizar turnos

Una alternativa para evitar el problema de la actualización múltiple a una

bandera es emplear una variable adicional que indique a qué proceso
corresponde avanzar en todo momento, esto es, utilizar turnos:

Asumimos la existencia de dos procesos 0 y 1.

• 1 while (turno != i) {
• 2 esperar(); /* ¿Otro proceso? */
• 3}
• 4 /* Sección crítica */
• 5 cuenta = cuenta + 1;
• 6 turno = 1-i;

Si turno = 0 y P1 está listo para entrar entonces debe esperar, aunque P0

no esté en Región Critica.
 Semáforos

• Edsger Dijkstra, en 1968, propuso los semáforos

Un semáforo es una herramienta genérica de sincronización de

procesos, o sea, permite el ordenamiento de las operaciones que
realizan los procesos en el tiempo.

Un semáforo es una variable de tipo entero que tiene definida la

siguiente interfaz:
• Inicialización Se puede inicializar el semáforo a cualquier valor
entero, pero después de esto, su valor no puede ya ser leído. Un
semáforo es una estructura abstracta, y su valor es tomado
como opaco (invisible) al programador.
• Decrementar Cuando un hilo decrementa el semáforo, si el
valor es negativo, el hilo se bloquea y no puede continuar hasta
que otro hilo incremente el semáforo. Según la
implementación, esta operación puede denominarse wait,
down, acquire o incluso P (por ser la inicial de proberen te
verlagen, intentar decrementar en holandés, del planteamiento
original en el artículo de Djkstra).
• Incrementar Cuando un hilo incrementa el semáforo, si hay
hilos esperando, uno de ellos es despertado. Los nombres que
recibe esta operación son signal, up, release, post o V (de
verhogen, incrementar).

• La característica fundamental de estos operadores:

Su ejecución es indivisible o sea atómica
Un semáforo permite la implementación de varios patrones,
entre los cuales se mencionarán los siguientes:

Señalizar

Un hilo debe informar a otro que cierta condición está ya

cumplida
—por ejemplo, un hilo prepara una conexión en red mientras
que otro calcula lo que tiene que enviar. No se puede arriesgar a
comenzar a enviar antes de que la conexión esté lista. Se
inicializa el semáforo a 0, y:
• 1 # Antes de lanzar los hilos
• 2 from threading import Semaphore
• 3 senal = Semaphore(0)
• 4
• 5 def envia_datos():
• 6 calcula_datos()
• 7 P(senal)
• 8 envia_por_red()
• 9
• 10 def prepara_conexion():
• 11 crea_conexion()
• 12 V(senal)
 Rendezvous

Así se denomina en francés (y ha sido adoptado al inglés) a

quedar en una cita. Este patrón busca que dos hilos se esperen
mutuamente en cierto punto para continuar en conjunto —por
ejemplo, en una aplicación GUI, un hilo prepara la interfaz gráfica
y actualiza sus eventos mientras otro efectúa cálculos para
mostrar. Se desea presentar al usuario la simulación desde el
principio, así que no debe empezar a calcular antes de que el GUI
esté listo, pero preparar los datos del cálculo toma tiempo, y no
se quiere esperar doblemente. Para esto, se implementan dos
semáforos señalizándose mutuamente:
• 1 from threading import Semaphore, Thread
• 2 guiListo = Semaphore(0)
• 3 calculoListo = Semaphore(0)
• 4
• 5 Thread(target=maneja_gui, args=[ ]).start()
• 6 Thread(target=maneja_calculo, args=[ ]).start()
• 7
• 8 def maneja_gui():
• 9 inicializa_gui()
• 10 V(guiListo)
• 11 P(calculoListo)
• 12 recibe_eventos()
• 13
• 14 def maneja_calculo():
• 15 inicializa_datos()
• 16 V(calculoListo)
• 17 P(guiListo)
• 18 procesa_calculo()
 Mutex

El uso de un semáforo inicializado a uno puede implementar

fácilmente un mutex

• 1 mutex = Semaphore(1)
• 2 # ...Inicializar estado y lanzar hilos
• 3 P(mutex)
• 4 # Aquí se está en la region de exclusión mutua
• 5x=x+1
• 6 V(mutex)
• 7 # Continúa la ejecucion paralelaex. En Python:
 Multiplex

Permite la entrada de no más de n procesos a la región

crítica. Si se lo ve como una generalización del mutex, basta
con inicializar al semáforo al número máximo de procesos
deseado. Su construcción es idéntica a la de un mutex, pero
es inicializado al número de procesos que se quiere permitir
que ejecuten de forma simultánea.
 Monitores

• Los monitores son estructuras provistas por el lenguaje o

entorno de desarrollo que encapsulan tanto los datos como
las funciones que los pueden manipular, impidiendo el
acceso directo a las funciones potencialmente peligrosas.

• En otras palabras, son tipos de datos abstractos (Abstract

Data Types, ADT), clases de objetos, y exponen una serie de
métodos públicos, además de poseer métodos
privados que emplean internamente.
Como ejemplo, el lenguaje de programación Java implementa
sincronización vía monitores entre hilos como una propiedad de la
declaración de método, y lo hace directamente en la JVM. Si se
declara un método de la siguiente manera:
1 public class SimpleClass {
2 // . . .
3 public synchronized void metodoSeguro() {
4 /* Implementación de metodoSeguro() */
5 // . . .
6 }
7 }
Y se inicializa a un SimpleClass sc =new SimpleClass(), cuando se
llame a [Link](), la máquina virtual verificará si ningún
otro proceso está ejecutando metodoseguro(); en caso de que no
sea así, le permitirá la ejecución obteniendo el candado, y en caso
de sí haberlo, el hilo se bloqueará hasta que el candado sea
liberado.
 Comunicaciones entre procesos
(IPC – Inter Process Communication)
La comunicación entre dos procesos puede ser realizada de dos
maneras:
1. Comunicación a través de un área común de memoria.
2. Comunicación mediante el intercambio de mensajes.
El propósito es permitir que dos procesos se
sincronicen o simplemente se envíen datos mediante un
mecanismo explícito
Definimos como mensaje a una porción discreta de datos
(generalmente compuesto por un conjunto de bits)
Los mensajes tienen una cabecera (header) y un cuerpo. El header
tiene el identificador del transmisor, el identificador del receptor,
la longitud, y el tipo
 Existen dos tipos de comunicaciones entre procesos:

Comunicación directa
Los procesos envían y reciben los mensajes entre sí. Dependen de las
velocidades relativas entre sí (si son distintas requieren un buffer de
mensajes para su sincronización).

Comunicación indirecta
Los mensajes son enviados a un buzón o mailbox y se retiran del buzón
Mailbox 1
recive
send

Proceso A Proceso B

recive
send
Mailbox 2

Mailbox: interfase entre procesos y S.O.. Se crea y quita facilmente.

Procesos: A Pide un mailbox y envía MSG, B se activa y recibe MSG
 Tipos de sincronizaciones mediante mensajes directos
• Comunicación Sincrónica
El proceso emisor es bloqueado hasta que el receptor esté listo para recibir el
mensaje. Cuando el proceso receptor ejecuta el receive y el mensaje no se
encuentra disponible queda bloqueado hasta la llegada del mismo. Una vez
que se ha producido el intercambio de mensajes ambos procesos continúan su
ejecución concurrentemente.

• Comunicación Asincrónica
Las primitivas de este tipo de comunicación se caracterizan por no bloquear a
los procesos que las ejecutan. Así cada uno sigue su ejecución. Esto es
importante en el caso del receptor ya que sigue ejecutando aunque no le
llegue ningún mensaje. Depende de la implementación si los mensajes
siguientes serán atendidos o no.

• Comunicación semi-sincrónica.
Se usa un send no bloqueante y receive bloqueantes. Esto es riesgoso pues se
pueden acumular una gran cantidad de mensajes en colas.
 Modelo productor-consumidor

Usado para describir dos procesos ejecutando en forma concurrente:

[Link]: Genera un conjunto de datos necesarios para la ejecución de otro
proceso.
[Link]: Toma los datos generados por el productor y los utiliza para su
procesamiento.

Actividades
p producir( ) Secuencia de mensajes (FIFO)

depositar( )
Asumimos que no se pierde, ni
Cola se modifica ningún bit del MSG
FIFO Buffer
Los datos son transmitidos entre
recuperar( ) ellos en porciones discretas que
llamaremos MENSAJES (MSG)
consumir( )
c

Capacidad del Buffer = MAX

• Productor: Genera elementos mediante producir() y los ingresa en el
buffer mediante depositar().

• Buffer: Zona de memoria utilizada para amortiguar las diferencias de velocidad

entre dos procesos. Almacena temporalmente los elementos generados por p.

• Consumidor: Retira los elementos del buffer mediante recuperar() y los

consume con consumir().

• Ejemplos:

• 1. ls | more

2. El spooler del SO y los procesos que quieren imprimir.

 Algunos algoritmos para el modelo productor-consumidor

A. Con sleep() & wakeup()

sleep(): Llamada al sistema que bloquea al proceso solicitante.
wakeup(): tiene como parámetro el PID del proceso a desbloquear.
Usa una variable cont que indica la cantidad de lugares ocupados que
tiene el buffer, donde N es el total de lugares
p() c()
{ {
while (1) while (1)
{
{
if (cont == 0)
x = producir();
sleep();
if (cont == N) x = sacar();
sleep(); cont--;
cont++; if (cont == N - 1)
ingresar(x); wakeup(p);
if (cont == 1) consumir(x);
wakeup(c); }
} }
}
Presenta al menos una condición de concurso. El
algoritmo falla.

La condición de concurso está dada cuando el buffer está

vacío y el consumidor acaba de leer cont para verificar si es
0. Ahí, lo interrumpen y pasa al productor; éste ingresa un
elemento en el buffer por lo que razonando que cont era 0,
despierta al consumidor, pero esa señal se pierde por lo
que el consumidor probará el viejo valor de cont y se
bloqueará.
 B. Con Contadores de eventos
Un contador de eventos e es una variable especial que tiene 3 operaciones
definidas en las siguientes primitivas:
1. read(e): Devuelve el valor de e.
2. advance(e): Incrementa atómicamente el valor de e en 1.
3. await(e, v): Espera hasta que e >= v.
• Solo incrementan el valor, nunca lo disminuye.
• Siempre se inician en cero.
Ejemplo para productor y consumidor:

p() c()
{ {
int prod; int sec;
while (1) while (1)
{ {
x = producir(); sec++;
prod++; await(ing, sec);
await(N,prod - sacados); x = sacar();
ingresar(x); advance(sacados);
advance(ing); consumir(x);
} }
} }

ing: Cuenta el número acumulativo de elementos que el productor colocó en el buffer.

sacados: Cuenta el número acumulativo de elementos que el consumidor retiró del buffer .
 C. Con Semáforos
Usa tres semáforos:
semáforo mutex = 1, vacío = N, lleno = 0;

p() c()
{ {
while (1) while(1)
{ {
x = producir(); P(lleno);
P(vacío); P(mutex);
P(mutex); x = sacar()
ingresar(x); V(mutex);
V(mutex); V(vacío);
V(lleno); consumir(x);
} }
} }

Cualesquiera de estos algoritmos propuestos sincronizan el modelo de productor-consumidor

que se presentan en múltiples situaciones dentro de un computador. Por ejemplo la CPU
produciendo mensajes para un módulo de E/S o viceversa.
 Algunos mecanismos de IPC

• Pipes y fifos
• Señales
• Memoria compartida
• Sockets
• RPC / RMI
 Bloqueos mutuos e inanición

Bloqueo mutuo (o interbloqueo; en inglés, deadlock):

Situación que ocurre cuando dos o más procesos poseen
determinados recursos, y cada uno queda detenido, a la espera
de alguno de los que tiene el otro. El sistema puede seguir
operando normalmente, pero ninguno de los procesos
involucrados podrán avanzar.

Inanición (resource starvation): Situación en que un proceso no

puede avanzar en su ejecución dado que necesita recursos que
están (alternativamente) asignados a otros procesos.
Un deadlock puede darse por dos motivos:

• Comunicación entre procesos

• Petición de Recursos

Observemos que el deadlock se debe fundamentalmente por

el uso de recursos. Se pueden distinguir dos categorías
generales de recursos: reutilizables y consumibles.
• Recursos reutilizables

Un recurso reutilizable es aquel que puede ser usado por un proceso y

no se agota con el uso. Los procesos obtienen unidades de recursos que
liberan posteriormente para que otros procesos las reutilicen. Como
ejemplos se tienen los procesadores, canales de E/S, memoria principal
y secundaria, dispositivos y estructuras de datos tales como archivos,
bases de datos y semáforos.

• Recursos consumibles
Un recurso consumible es aquel que puede ser creado (producido) y
destruido (consumido).
Normalmente, no hay límite en el número de recursos consumibles de
un tipo en particular. Un proceso productor que no esta bloqueado
puede liberar cualquier numero de recursos consumibles. Cuando un
proceso adquiere un recurso este deja de existir. Como ejemplos están
las interrupciones, señales, mensajes, e información en buffer de E/S.
 Condiciones necesarias y suficientes
Para que se produzca un estado de deadlock las cuatro
condiciones de Coffman deben producirse simultáneamente. Estas
condiciones son las siguientes:

• 1. Mutua exclusión: Los procesos reclaman control exclusivo de los

recursos que piden
• 2. Retener y esperar Los procesos mantienen los recursos que ya les
han sido asignados mientras esperan por recursos adicionales
• 3. No expropiación Los recursos no pueden ser extraídos de los
procesos que los tienen hasta su completa utilización
• 4. Espera circular: Hay una cadena circular de procesos en la que
cada uno mantiene a uno o más recursos que son requeridos por el
siguiente proceso de la cadena
 Grafo de asignación de recursos
Otra manera de definir deadlocks es a través de grafos. Estos grafos están formados
básicamente por dos elementos:
• Un conjunto de vértices formado por los procesos y los recursos del sistema;
• Un conjunto de arcos que representan la asignación o solicitud de recursos.

Para ilustrar la situación (ver figura 4.13) se utiliza un grafo dirigido llamado Resource
Allocation Graph (Grafo de Asignación de Recursos). En él se representan :
• 1. Conjunto de vértices V con los procesos (Px) y los recursos (Ry) del sistema
P = {P1, P2, ..., Pn} Procesos
R = {R1, R2, ..., Rn} Recursos
• 2. Conjunto de arcos A que unen los procesos con los recursos.
• A continuación podemos ver tres grafos de asignación de recursos. Los
recursos fueron representados con cuadrados y los procesos con
círculos. Un arco de Pi a Rj significa que el proceso Pi solicito el recurso
Rj. Un arco de Rj a Pi significa que el recurso Rj esta asignado al
proceso Pi .

P1 A
P1 R1 P2

A A A
A
P1 A
R2
R1
R1 Fig. 4.13c
Fig. 4.13a
Fig. 4.13b
Un arco dirigido de P1 a R1 indica que P1 pidió el recurso R1 y está esperando. (Fig 4.13a)
Un arco dirigido de R1 a P1 indica que P1 pidió el recurso R1 y R1 está asignado a P1. (Fig 4.13b)
Un conjunto de arcos como se indica en la Fig 4.13c indica que está en deadlock
 Estrategias para tratar deadlocks
• Hay 3 estrategias:

➢Ignorarlos y pensar que en el sistema nunca ocurrirán.

La mayoría de los sistemas operativos utilizan esta
técnica, incluyendo UNIX.

➢Por medio de la prevención o evasión se asegura que

el sistema nunca entrará en estado de deadlock.

➢Permitir que ocurra un estado de deadlock y luego

recuperarlo
Detalle de estrategias para tratar
deadlocks
 Ignorarlo
• Es la forma más simple para tratarlo

• Algunas veces el costo de ignorarlo es mucho menor al

costo que implicaría prevenirlo o detectarlo y recuperarlo

• Tanenbaum propone como “algoritmo del avestruz” y dice

“Si los deadlocks no son frecuentes entonces puede ser
más conveniente esconder la cabeza bajo la arena”.
 Prevención
• Siendo las cuatro condiciones necesarias para que ocurra un
Deadlock basta con asegurarnos que una de ellas no ocurrirá
• Mutua Exclusión: Las soluciones para aquellos recursos que no
pueden ser compartidos son diversas, pero todas se basan en que
un proceso no quede esperando en caso de la falta de
disponibilidad de dicho recurso
• Control y espera (Hold & Wait): Para solucionar este problema, se
trata de garantizar que cuando un proceso tenga un recurso
asignado no pueda solicitar otro. Hay dos caminos para lograrlo:
• 1 - Los procesos solicitan todos los recursos en el momento previo a comenzar la
ejecución, de no poder ser entregados el proceso queda bloqueado.
• Asignación estática completa de todos los recursos que necesita para su
ejecución (caso COBOL).
• 2 - Un proceso primero debe liberar aquellos recursos que posee y luego recién
podrá solicitar otros, es decir solo está en condiciones de solicitar un recurso
cuando no tiene ninguno asignado.
No expropiación (No Preemption): Para ésta
condición también existen dos métodos:

1. Si un proceso solicita un recurso que no está disponible, éste

debe devolver todos aquellos recursos que tenía previamente
asignados.

2. Si un proceso pide un recurso que tiene otro proceso, el Sistema

Operativo puede obligar a liberar los recursos al otro proceso.

El primer método es viable sólo en aquellos procesos cuyos estados

pueden ser fácilmente grabados y restaurados. El segundo método
presenta el inconveniente del estado de inanición (Starvation), en
caso
de que a un proceso siempre le quiten los recursos y nunca pueda
finalizar su tarea.
Espera circular: Consiste en imponer un orden lineal de ejecución
que evite las esperas circulares

• Este problema puede ser resuelto de la siguiente manera:

1. Estableciendo un orden lineal de los recursos:

Si tenemos una lista de recursos R1, R2,......Rn, un proceso que
solicitó Rh, sólo puede pedir aquellos recursos Rk, con k > h. Esto
evita que se forme un círculo .

2. Otra forma de resolverlo es lo propuesto en Hold & Wait: un

proceso sólo está en condiciones de solicitar un recurso cuando no
tiene ninguno asignado.

El problema del orden lineal es que también es en cierto grado ineficiente ya que
estaría negando recursos a procesos, innecesariamente .
 Detectar y recuperar
• Consiste en abortar un proceso cuando se detecta o se presupone
que puede ocurrir el deadlock.

• La ventaja de esta táctica es que no limita el acceso a los recursos

• Presenta ciertos inconvenientes como el de decidir la frecuencia

con que se llevará a cabo el algoritmo de detección.

• El algoritmo podría ser ejecutado cada vez que se solicita un

recurso, a cada hora, etc.
Hay varios métodos para recuperar a los procesos y a los
recursos una vez detectada la situación:

➢Abortar todos los procesos involucrados

➢Abortar los procesos uno a uno, hasta que el deadlock

desaparezca.

➢Hacer un backup de cada proceso en un punto anterior: ChekPoint.

A este proceso de reinicio se lo llama Rollback. Consiste en llevar el
proceso a un punto anterior al de haberle sido asignado el recurso
causante del Deadlock.

➢Quitar un recurso a un proceso y entregárselo a otro que lo haya

solicitado. También hay que ejecutar el algoritmo de detección
luego de que se quitó algún recurso.
Patrones de sincronización
 Torniquete
Una construcción que por sí sola no hace mucho, pero resulta útil para patrones
posteriores. Esta construcción garantiza que un grupo de hilos o procesos pasa
por un punto determinado de uno en uno (incluso en un ambiente
multiprocesador):

• 1 torniquete = Semaphore(0)
• 2 # (...)
• 3 if alguna_condicion():
• 4 V(torniquete)
• 5 # (...)
• 6 P(torniquete)
• 7 V(torniquete)

En este caso, se ve primero una señalización que hace que todos los procesos
esperen frente al torniquete hasta que alguno marque que alguna_condicion()
se ha cumplido y libere el paso. Posteriormente, los procesos que esperan
pasarán ordenadamente por el torniquete. El torniquete por sí solo no es tan
útil, pero su función se hará clara a continuación.
 Apagador

Cuando se tiene una situación de exclusión categórica

(basada en categorías y no en procesos individuales —varios
procesos de la misma categoría pueden entrar a la sección
crítica, pero procesos de dos categorías distintas deben
tenerlo prohibido), un apagador permite evitar la inanición
de una de las categorías ante un flujo constante de procesos
de la otra.
El apagador usa, como uno de sus componentes, un
torniquete. Para ver una implementación ejemplo de un
apagador, referirse a la solución presentada para el
problema de los lectores y los escritores
 Problema de los lectores y los escritores
Primera aproximación
• 11 def lector():
• 1 import threading
• 12 P(mutex)
• 2 lectores = 0
• 13 lectores = lectores + 1
• 3 mutex = [Link](1)
• 14 if lectores == 1:
• 4 cuarto_vacio = [Link](1)
• 15 P(cuarto_vacio)
• 5
• 16 V(mutex)
• 6 def escritor():
• 17
• 7 P(cuarto_vacio)
• 18 lee()
• 8 escribe()
• 19
• 9 V(cuarto_vacio)
• 20 P(mutex)
• 10
• 21 lectores = lectores - 1
• 22 if lectores == 0:
• 23 V(cuarto_vacio)
• 24 V(mutex)
 Solución
• 1 import threading • 18 //Continúa
• 2 lectores = 0 • 19 P(mutex)
• 3 mutex = [Link](1) • 20 lectores = lectores + 1
• 4 cuarto_vacio = [Link](1) • 21 if lectores == 1:
• 5 torniquete = [Link](1) • 22 P(cuarto_vacio)
• 6 • 23 V(mutex)
• 7 def escritor(): • 24
• 8 P(Torniquete) • 25 lee()
• 9 P(cuarto_vacio) • 26
• 10 escribe() • 27 P(mutex)
• 11 V(cuarto_vacio) • 28 lectores = lectores - 1
• 12 V(torniquete) • 29 if lectores == 0:
• 13 • 30 V(cuarto_vacio)
• 14 def lector(): • 31 V(mutex)
• 15 global lectores
• 16 P(torniquete)
• 17 V(torniquete)
 Barrera
Una barrera es una generalización de rendezvous que permite la
sincronización entre varios hilos (no sólo dos), y no requiere que el
papel de cada uno de los hilos sea distinto.
Esta construcción busca que ninguno de los hilos continúe
ejecutando hasta que todos hayan llegado a un punto dado.
Para implementar una barrera, es necesario que ésta guarde algo de
información adicional además del semáforo, particularmente, el
número de hilos que se han lanzado (para esperarlos a todos). Esta
será una variable compartida y, por tanto, requiere de un mutex. La
inicialización (que se ejecuta antes de iniciar los hilos) será:

• 1 num_hilos = 10
• 2 cuenta = 0
• 3 mutex = Semaphore(1)
• 4 barrera = Semaphore(0)
Ahora, suponiendo que todos los hilos tienen que realizar, por
separado, la inicialización de su estado, y ninguno de ellos debe
comenzar el procesamiento hasta que todos hayan efectuado su
inicialización:

• 1 inicializa_estado()
• 2
• 3 P(mutex)
• 4 cuenta = cuenta + 1
• 5 V(mmutex)
• 6
• 7 if cuenta == num_hilos:
• 8 V(barrera)
• 9
• 10 P(barrera)
• 11 V(barrera)
• 12
• 13 procesamiento()
Las barreras son una construcción suficientemente útil como
para que sea común encontrarlas “prefabricadas”. En los
hilos POSIX (pthreads), por ejemplo, la interfaz básica es:

• 1 int pthread_barrier_init(pthread_barrier_t *barrier,

• 2 const pthread_barrierattr_t
• *restrict attr,
• 3 unsigned count);
• 4 int pthread_barrier_wait(pthread_barrier_t *barrier);
• 5 int pthread_barrier_destroy(pthread_barrier_t *barrier);
 Cola

Se emplea cuando se tienen dos clases de hilos que deben

proceder en pares. Este patrón es a veces referido como
baile de salón: para que una pareja baile, hace falta que haya
un líder y un seguidor. Cuando llega una persona al salón,
verifica si hay uno de la otra clase esperando bailar.
En caso de haberlo, bailan, y en caso contrario, espera a que
llegue su contraparte.
El código para implementar esto es muy simple:
1 colaLideres = Semaphore(0)
2 colaSeguidores = Semaphore(0)
3 # (...)
4 def lider():
5 V(colaSeguidores)
6 P(colaLideres)
7 baila()
8 def seguidor():
9 V(colaLideres)
10 P(colaSeguidores)
11 baila()

El patrón debe resultar ya familiar: es un rendezvous. La distinción

es meramente semántica: en el rendezvous se necesitan dos hilos
explícitamente, aquí se habla de dos clases de hilos.