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;
• ...
... etiq
• join;
• ...
join ...
• end;
• 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; Falla!!!
8 /* Aquí bandera=0 */ bandera es un
9 bandera = 1; /* Inicio de la sección crítica */ rec compartido y
su acceso no es
10 cuenta = cuenta + 1;
atómico
11 bandera = 0; /* Fin de la sección crítica */
• 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:
Falla!!!
Puede generar
1 int bandera; /* 0 => desocupada */
2
inanición si un
3 while (++bandera != 1) { proceso no
4 bandera--; /* Debe generar "INC" */ libera el recurso.
5 } También usa
6 /* Sección crítica */ "espera
7 cuenta = cuenta + 1;
ocupada"
8
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:
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.
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
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
• 3 mutex = threading.Semaphore(1) +1
• 4 cuarto_vacio = • 14 if lectores == 1:
threading.Semaphore(1)
• 15
• 5 P(cuarto_vacio)
• 6 def escritor(): • 16 V(mutex)
• 7 P(cuarto_vacio) • 17
• 8 escribe() • 18 lee()
• 9 V(cuarto_vacio) • 19
• 10 • 20 P(mutex)
• 21 lectores = lectores
-1
• 22 if lectores == 0:
Solución
• 1 import threading • 18 //Continúa
• 2 lectores = 0
• 3 mutex = threading.Semaphore(1)
• 19 P(mutex)
• 4 cuarto_vacio = • 20 lectores = lectores + 1
threading.Semaphore(1)
• 21 if lectores == 1:
• 5 torniquete =
threading.Semaphore(1) • 22 P(cuarto_vacio)
• 6 • 23 V(mutex)
• 7 def escritor():
• 24
• 8 P(Torniquete)
• 9 P(cuarto_vacio) • 25 lee()
• 10 escribe() • 26
• 11 V(cuarto_vacio)
• 27 P(mutex)
• 12 V(torniquete)
• 13 • 28 lectores = lectores - 1
• 14 def lector(): • 29 if lectores == 0:
• 15 global lectores • 30 V(cuarto_vacio)
• 16 P(torniquete)
• 17 V(torniquete)
• 31 V(mutex)
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
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.
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 sc.metodoSeguro(), 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
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)
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
Mailbox 1
Los mensajes sonsend
enviados a unrecive
buzón o mailbox y se retiran
del buzón
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
• 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:
1.Productor: Genera un conjunto de datos necesarios para la
ejecución de otro proceso.
2.Consumidor: 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
c()la cantidad de lugares
p()
ocupados que tiene el buffer, donde
{ N es el total de lugares
{
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
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
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
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.
