Bloqueos_Mutuos

PROBLEMAS CLÁSICOS DE SINCRONIZACIÓN Y COMUNICACIÓN

Filósofos Comensales ( Dijkstra, 1965 )

• Cinco filósofos pasan la vida pensando y comiendo

• Cuando un filósofo piensa, no interactúa con sus colegas

• Cuando tiene hambre, toma los dos palillos al mismo tiempo y come sin soltarlos

• Cuando termina de comer, coloca los dos palillos sobre la mesa y comienza a pensar



• Necesidad de asignar varios recursos entre varios procesos sin que haya bloqueos mutuos ni inanición

Primera Solución

• Representar cada palillo con un semáforo

• Un filósofo trata de tomar un palillo ejecutando una operación espera con ese semáforo, y suelta sus palillos ejecutando la operación señal con los semáforos apropiados.

var palillo: array [0..4] of semáforo;

• Inicialmente todos los elementos de palillo están en 1



Primera Solución

• Garantiza que dos vecinos no estarán comiendo simultáneamente

• Posibilidad de bloqueo mutuo

•Suponga que los cinco filósofos sienten hambre simultáneamente y cada uno toma su palillo izquierdo



Posibles soluciones al problema de bloqueos

Permitir que como máximo filósofos se sienten a la mesa cuatro filósofos

Sólo permitir que un filósofo tome sus palillos si ambos están disponibles ( dentro de la sección crítica )

Solución asimétrica Un filósofo impar toma primero su palillo izquierdo y luego el derecho, mientras que un filósofo par toma primero su palillo derecho y luego el izquierdo.



Cualquier solución satisfactoria deberá evitar la posibilidad que uno de los filósofos muera de hambre.

Una solución libre de bloqueos mutuos no elimina necesariamente la posibilidad de inanición

Solución por monitores

Distinguir entre los tres estados en los que podría estar un filósofo Pensando, hambriento y comiendo

Definir el estado del mismo filósofo


Lectores y Escritores ( Courtois et al., 1971)

Lector Lector Escritor Lector Escritor

Recurso

Existe un determinado objeto que se va a ser utilizado y compartido por una serie de procesos concurrentes.



• Un objeto se va a compartir entre varios usuarios, algunos solo quieren leer el contenido ( lectores ), otros quieren actualizarlo (escritores)

Restricciones

• Sólo se permite que un escritor tenga acceso al objeto al mismo tiempo. Mientras el escritor esté accediendo al objeto, ningún otro proceso lector ni escritor podrá acceder a él.

• Se permite que múltiples lectores tengan acceso al objeto, ya que ellos nunca van a modificar el contenido del mismo



•Primer Problema : No se debe tener a ningún lector en espera a menos que el escritor tenga el permiso del uso del objeto

• Segundo Problema : Si un escritor está esperando acceder al objeto, ningún otro lector puede comenzar a leer.

Sol/ Definir prioridades a lectores y escritores

• Utilizado para probrar las primitivas de sincronización nuevas


Productor – Consumidor ( Buffer limitado )

ProcesoProductor

ProcesoConsumidor

Flujo de datos

Mecanismo de Comunicación

Uno o más procesos, que se denominan productores, generan cierto tipo de datos que son utilizados por otros procesos que se denominan consumidores



Mecanismo de Comunicación

• Cuando se llene Productor bloqueado

• Cuando esté vacío Consumidor bloqueado

• Buffer

• Solución Semáforos

Valor máximo Tamaño del buffer

Valor mínimo Cero



int N = 100; /*Número máximo en el buffer*/

int count = 0; /*Número de elementos en el buffer*/

void productor( ){

if (buffer == lleno) then dormir();

else {

añadir nuevo elemento a la lista;

incrementar count;

verificar estado consumidor;

}

}


Productor -- Consumidor ( Buffer limitado )

void consumidor( ){

if (buffer == vacío) then dormir();

else {

eliminar elemento de la lista;

decrementar count;

verificar estado productor;

}

}


Barbero Dormilón

La peluquería tiene :

• Un barbero

• Una silla de barbero

• n sillas para los clientes


Barbero Dormilón

No hay clientes presentes El barbero se sienta en la silla de barbero y se duerme

Cuando llega un cliente, debe despertar al barbero

Si llegan más clientes mientras el barbero está atendiendo a un cliente, se sientan (si hay sillas vacías), o bien, salen de la peluquería (si todas las sillas está ocupadas)

Problema : Programar al barbero y a los clientes sin caer en condiciones de competencia


Barbero Dormilón

Semáforo wait signal

max_capacidad El cliente espera hasta que haya sitio para entrar en la peluquería

El cliente que sale avisa a un cliente que está esperando para entrar

sillas El cliente espera una silla vacía

El cliente que abandona la silla avisa a un cliente que espera silla

silla_barbero El cliente espera hasta que la silla del barbero esté vacía

El barbero avisa cuando su silla queda vacía

cliente_listo El barbero espera hasta que el cliente esté en la silla

El cliente avisa al barbero que ya está en la silla


Barbero Dormilón

Semáforo wait signal

terminado El cliente espera a que el corte de cabello esté completo

El barbero avisa cuando termina el corte de cabello a un cliente

dejar_silla_v El barbero espera hasta que el cliente se levante de la silla

El cliente avisa al barbero cuando se levanta de la silla

BLOQUEOS MUTUOS

Entorno multiprogramación Varios procesos pueden competir por un número finito de recursos

Proceso solicita un recurso

• No está disponible Espera

• Puede que no cambie de estado Los recursos solicitados están en manos de otros procesos que también están en espera

Interbloqueo

Problema similar Inanición, aplazamiento indefinido o bloqueo indefinido

BLOQUEOS MUTUOSModelado del Sistema

Un sistema se componen de un conjunto finito de recursos (unidades de cinta, impresoras, CPU, etc..)

Procesos compiten por los recursos

Si el sistema tiene por dos CPU, se dice que tiene dos ejemplares

Todos los S.O deben otorgar a un proceso (en forma temporal) acceso exclusivo a ciertos recursos.

BLOQUEOS MUTUOSEjemplo

Suponga que dos procesos quieren quemar un documento digitalizado en un CD.

Proceso A solicita autorización para usar el escáner y se le concede.

Proceso B solicita primero el quemador de CD y también se le concede.

Ahora A, pide el quemador de CD, pero se le niega porque B no lo ha liberado

B solicita el escáner, pero sin liberar el quemador de CD.

PROCESOS A Y B ESTÁN BLOQUEADOS

• Solicitud

• Uso Llamadas al Sistema

• Liberación

El recurso no está disponible cuando se solicita

• El proceso solicitante debe esperar

• En algunos S.O el proceso se bloquea automáticamente y despierta cuando dicho recurso esté disponible

• La solicitud falla y el proceso debe esperar para pedir el recurso.

BLOQUEOS MUTUOSSecuencia de uso de recursos

1. Exclusión Mutua

Sólo un proceso podrá usar el recurso

2. Retener y esperar

Los procesos que tienen recursos previamente otorgados pueden solicitar otros recursos.

3. No apropiación

Un recurso no puede ser arrebatado a otro proceso

BLOQUEOS MUTUOSCondiciones para el bloqueo mutuo

4. Espera circular

Debe existir un conjunto {P0,P1..,Pn} de procesos en espera tal que P0 está esperando un recurso que fué adquirido por P1, P1 está esperando un recurso que fué adquirido por P2,….., Pn-1 está esperando un proceso que fué adquirido por Pn y Pn está esperando un recurso que fué adquirido por P0

BLOQUEOS MUTUOSCondiciones para el bloqueo mutuo

BLOQUEOS MUTUOSModelación de Bloqueos

Grafos de Asignación de Recursos

Nodos Procesos y RecursosArcos De un proceso a un recurso Solicitud De un recurso a un proceso Asignación Ciclos Indica la existencia de un bloqueo

BLOQUEOS MUTUOSModelación de Bloqueos

Ejemplo

Procesos A, B, C Recursos R, S, T

Asignaciones Solicitudes

R asignado a A A solicita a S

S asignado a B B solicita a T

T asignado a C C solicita a R

Pregunta. ¿Está bloqueado este sistema y, en tal caso, cuáles son los procesos bloqueados?.

BLOQUEOS MUTUOSEstrategias para enfrentar los Bloqueos

• Ignorar todo el problema : Quizá si nos olvidamos de él, él se olvidará de nosotros

Algoritmo del Avestruz

•Detectar y recuperarse del bloqueo : Dejar que se presenten bloqueos mutuos, detectarlos y tomar medidas

•Prevenir el bloqueo : Anular una de las cuatro condiciones necesarias para que haya un bloqueo mutuo

• Evitar el bloqueo : Asignación cuidadosa de recursos

BLOQUEOS MUTUOSAlgoritmo para detectar un Bloqueo

Algoritmo aplicable a cada nodo “N” de la gráfica:

1. Se considera a “N” como nodo inicial.

2. Se inicializan:

La estructura de datos “L”como una lista vacía.

Todos los arcos como no marcados.

3. Se añade el nodo activo al final de “L” y se verifica si el nodo aparece en “L” dos veces:

Si aparece dos veces existe un ciclo y el algoritmo termina.

4. Desde el nodo dado se verifica si existen arcos que salgan de dicho nodo y no estén marcados:

En caso afirmativo se va al paso 5.

En caso negativo se va al paso 6.


…Continuación Algoritmo

5. Se elige al azar un arco de salida no marcado y se le marca:

Luego se sigue este arco hasta el nuevo nodo activo y se regresa al paso 3.

6. Se ha llegado a un punto donde no se puede continuar:

Se regresa al nodo anterior, es decir al que estaba activo antes del actual.

Se señala de nuevo como nodo activo.

Se va al paso 3.

Si este nodo era el nodo inicial, la gráfica no contiene ciclos y el algoritmo termina.


Ejemplo: Sistema con 7 (siete) procesos (“A” a “G”) y 6 (seis) recursos (“R” a “W”):

La posesión de los recursos es la siguiente:

El proceso A posee a R y desea a S.

El proceso B no posee recurso alguno y desea a T.

El proceso C no posee recurso alguno y desea a S.

El proceso D posee a U y desea a S y a T.

El proceso E posee a T y desea a V.

El proceso F posee a W y desea a S.

El proceso G posee a V y desea a U.

Pregunta : ¿Está bloqueado este sistema y, en tal caso, cuáles son los procesos bloqueados?.

BLOQUEOS MUTUOSCómo recuperarse de un Bloqueo

Estrategias -- Apropiación de Recursos

Arrebatar de manera temporal un recurso a su actual poseedor y dárselo a otro proceso.

Manualmente

La selección del proceso a suspender depende de qué procesos tienen recursos que pueden quitarse con facilidad

BLOQUEOS MUTUOSCómo recuperarse de un Bloqueo

Estrategias – Eliminación de recursos

Escoger como víctima un proceso que no se encuentre en el ciclo, a fin de liberar recursos.

Eliminar sucesivamente los procesos bloqueados

Liberar todos los procesos y recursos

BLOQUEOS MUTUOSPrevenir el Bloqueo

Diseñar un sistema donde quede excluida la posibilidad de bloqueo

Anular una de las cuatro condiciones necesarias para que haya un bloqueo mutuo

Exclusión Mutua

Jamás asignar un recurso en forma exclusiva a un solo proceso.

Inconveniente El S.O debe soportar la exclusión mutua. Ejemplo: Escribir en un archivo.


Retener y esperar

Hacer que los procesos soliciten todos sus recursos antes de comenzar a ejecutarse

Inconveniente Muchos procesos no saben, antes de iniciar se ejecución, cuántos recursos van a necesitar.

No hará uso óptimo de los recursos

S/ Exigir a un proceso que solicita un recurso que primero libere en forma temporal todos los que tiene.


No apropiación

Si a un proceso se le niega el uso de un recurso liberar todos los recursos

Espera circular

Todo proceso tiene derecho a utilizar un recurso en todo momento. Si necesita un segundo recurso, deberá liberar el primero


Espera circular

Asignar prioridades a los recursos

Ejemplo.

1. Impresora

2. Escáner

3. Graficador

4. Unidad de cinta

5. Unidad de CD

Imposible llegar a un ordenamiento que satisfaga a todos

BLOQUEOS MUTUOSTécnicas para Evitar Bloqueos

Bloqueo Mutuo Cuando un proceso pide recursos, en algún momento pedirá mas.

El sistema debe tener la capacidad de distinguir si se puede otorgar sin peligro un recurso o no, y solo efecttuar la asignación si no hay peligro.

¿Hay algún algoritmo que siempre pueda evitar los bloqueos mutuos tomando la decisión correcta todo el tiempo?


Obligar a cada proceso a definir el número máximo de recursos que podría necesitar

Revisar dinámicamente el estado de asignación de recursos

– Número de recursos disponibles y asignados

– Demandas máximas de los procesos


Estados Seguros e inseguros

El sistema puede asignar recursos a cada proceso Secuencia segura

Bloqueo mutuo Estado inseguro

Algoritmo del Banquero Dijkstra

Cuando un proceso nuevo entra en el sistema, debe declarar el número máximo de recursos que podría necesitar


Estructuras para implementar el algoritmo

n Número de procesos del Sistema

m Número de recursos

Disponible : Vector de longitud m

Disponible( j ) = k;

Máx: Matriz de n*m Demanda máxima de cada proceso

Máx[ i, j ] = k

Asignación : Matriz de n*m Número de recursos que se han asignado a cada proceso

Asignación [ i, j ] = k


Estructuras para implementar el algoritmo

Necesidad: Matriz de n*m Recursos que todavia le faltan a cada proceso

Necesidad[ i ,j ] = k

Necesidad[ i, j ] = Máx[ i, j ] - Asignación [ i, j ] = k


Algoritmo de Seguridad – Un sistema está en estado seguro???

1. Sean Trabajo y Fin vectores con longitud m y n. Asignar los valores iniciales

Trabajo = Disponible y Fin[i]=false para i = 1, 2, ...,n

2. Buscar un i tal que

a. Fin[i] = false, y

b. Necesidadi <= Trabajo

Si no existe tal i, continuar con el paso 4


3. Trabajo = Trabajo + Asignacióni

Fin[i] = true

Ir al paso 2

4. Si Fin[i] = true para todo i, el sistema está en un estado seguro


Algoritmo de Solicitud de Recursos

Sea Solicitudi el vector de solicitudes del proceso Pi.

Si Solicitudi [ j ] = k, el proceso Pi quiere k recursos de Rj.

Cuando Pi solicita recursos, se hace lo siguiente:

1. Si Solicitudi <= Necesidadi, ir al paso 2. En caso contrario,

indicar una condición de error, pues el proceso ha excedido

su reserva máxima


Algoritmo de Solicitud de Recursos

2. Si Solicitudi <= Disponible, ir a paso 3. En caso contrario, Pi

deberá esperar, ya que los recursos no están disponibles

3. Hacer que el sistema simule haber asignado al proceso Pi

los recursos que solicitó modificando el estado como sigue:

Disponible = Disponible – Solicitudi;

Asignacióni = Asignacióni + Solicitudi;

Necesidadi = Necesidadi - Solicitudi


Ejemplo

Considere un sistema con cinco procesos, P0 a P4 y tres tipos de recursos A, B y C. El tipo de recursos de A tiene 10 ejemplares, B tiene 5 ejemplares y C tiene 7 ejemplares

Asignación Máx Disponible

A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2

P1 2 0 0 3 2 2

P2 3 0 2 9 0 2

P3 2 1 1 2 2 2

P4 0 0 2 4 3 3


Ejemplo

Suponga que, en el instante T0, se tomó la siguiente instantánea del sistema:

Necesidad = Máx - Asignación

Necesidad

A B C

P0 7 4 3

P1 1 2 2

P2 6 0 0

P3 0 1 1

P4 4 3 1

•El sistema está en un estado seguro?

•Qué pasa si llega la siguiente solicitud. Solicitud1 = (1,0,2)

Busque una secuencia de procesosque satisfaga los criterios de seguridad.


Ejemplo

Aplicar el algoritmo de solicitud de recursos

Asignación Necesidad Disponible

A B C A B C A B C

P0 0 1 0 7 4 3 2 3 0

P1 3 0 2 0 2 0

P2 3 0 2 6 0 0

P3 2 1 1 0 1 1

P4 0 0 2 4 3 1

Aplicar el algoritmo de seguridad

• Qué sucede si llega una solicitud de P4 con (3,3,0)??

• Qué sucede si llega una solicitud de P2 con (0,2,0)??


Ventajas del Algorimo del Banquero

• Ofrece una forma de asignar recursos

• Permite la ejecución de tareas que tendrían que esperar en una situación de prevención del bloqueo mutuo

Desventajas

Requiere un número fijo de recursos asignables

No es posible contar que será siempre constante el número de recursos


Desventajas

Requiere una población de usuarios constante

Multiprogramación

El algoritmo necesita que los usuarios declaren por anticipado sus necesidades

Asignación de recursos dinámica

Documents

Bloqueos_Mutuos