Bloqueo mutuo

Los recursos del sistema son particionados en varios tipos (Espacio de memoria, ciclos de CPU, archivos, dispositivos de E/S), cada uno necesita instancias idénticas.

Cuando un proceso requiere de una instancia de un tipo de recurso, se le asigna cualquier instancia para poder satisfacer este requerimiento.

Cuando un proceso solicita una instancia que no está disponible entonces pasa a un estado de espera.

Un proceso puede esperar por un recurso y nunca cambiar de estado porque el recurso está retenido por otro proceso que se encuentra en espera. Esta situación es llamada bloqueo mutuo.

Condiciones necesarias para la existencia de bloqueos mutuos.

· Exclusión mutua: Es un mecanismo empleado para evitar los problemas de competencia por recursos, se basa en definir una zona o región crítica la cual está marcada por las instrucciones que hacen uso del recurso en competencia

· Retención y espera: Siempre que un proceso requiere un recurso, no tiene otro retenido.

Ø Pueden usarse dos protocolos:

· Cada proceso debe requerir y recibir todos sus recursos antes de comenzar su ejecución.

· Cada proceso puede requerir algunos recursos y usarlos, pero cuando requiere otro recurso adicional, ANTES debe liberar los ya asignados.

Estos protocolos producen baja utilización de los recursos.

Puede ocasionar inanición de algunos procesos.

· No apropiación:

Ø Alternativa 1:

- Si un proceso que está reteniendo algunos recursos, requiere otro recurso que no se le puede asignar inmediatamente, entonces todos los recursos que tiene retenidos le son apropiados.

- Los recursos apropiados son agregados a la lista de recursos que el proceso está esperando.

- El proceso se reinicia sólo cuando recupera sus viejos recursos junto con los nuevos que está requiriendo.

Ø Alternativa 2:

- Si un proceso requiere recursos, primero chequea si están disponibles.

- Si están, entonces asignarlos.

- Si no están, chequear si están asignados a algún otro proceso que esté esperando recursos adicionales.

· Espera circular:

- Imponer un orden a todos los tipos de recursos del sistema

- Cada proceso debe requerir recursos en un orden creciente de enumeración.

- Implementación:

- Asignar a cada tipo de recurso un número entero único

- Formalmente se define una función F: R→ N con R={R1,R2,...,Rm}

- La función F debe ser definida de acuerdo al orden de utilización normal de los recursos en el sistema

Estas condiciones deben darse simultáneamente

Algoritmo del grafo de asignación de recursos

Si para cada tipo de recurso existe sólo una instancia, una variante del grafo de asignación de recursos puede ser usada para la evitación del bloqueo.

La seguridad del sistema se chequea mediante un algoritmo que detecta ciclos en el grafo.

Mecanismos para prevenir bloqueos mutuos.

· Se requiere información adicional acerca de cómo van a ser solicitados los recursos.

· Con el conocimiento de la secuencia completa de requerimientos y liberaciones para cada proceso, el sistema, ante cada requerimiento, considera:

Ø Los recursos actualmente disponibles

Ø Los recursos actualmente asignados a cada proceso

Ø Los requerimientos y liberaciones futuras de cada proceso y decide si el requerimiento puede ser satisfecho, o el proceso debe esperar para evitar un posible bloqueo en el futuro.

· Los algoritmos para evitar el bloqueo difieren en la cantidad y tipo de información que requieren.

· El modelo más simple y útil requiere que cada proceso declare el máximo número de recursos de cada tipo que puede necesitar.

· Con esta información el algoritmo asegura que el sistema nunca entrará en un estado de bloqueo.

· Un algoritmo para evitar el bloqueo examina dinámicamente el estado de asignación de recursos para asegurar de que nunca puede hacer una condición de espera circular.

· El estado de asignación de los recursos está definido por el número de recursos disponibles y asignados, y la máxima demanda de los procesos.

Detección de bloqueos mutuos.

•

Si un sistema no emplea un algoritmo de prevención o para evitar el bloqueo, entonces puede ocurrir una situación de bloqueo. Por ello, estos sistemas deben proveer:

- Un algoritmo que examine el estado del sistema para determinar si ha ocurrido un bloqueo.

- Un algoritmo para recuperarse del bloqueo

Los esquemas de detección y recuperación tienen un alto overhead.

Sistemas con única instancia por cada tipo de recurso

- Para estos sistemas se puede definir un algoritmo de detección de bloqueo que usa una variante del grafo de asignación de recursos llamado grafo wait-for.

- Existirá un bloqueo en el sistema si el grafo wait-for contiene un ciclo.

- Para detectar bloqueos, el sistema necesita mantener el grafow a i t - f o r e invocar periódicamente un algoritmo que busca ciclos en el grafo.

Sistemas con varias instancias por cada tipo de recurso

- En estos sistemas no es aplicable el esquema del grafo wait-for.

- Para estos sistemas se emplea un algoritmo similar al algoritmo del banquero

Algoritmo del banquero.

- Algoritmo del grafo de asignación de recursos no es aplicable a un sistema designación de recursos con múltiples instancias para cada tipo de recurso.

- En estos casos, para evitar el bloqueo se aplica un algoritmo conocido como el algoritmo del banquero.

- Cuando un proceso entra al sistema, debe declarar el máximo número de instancias de cada tipo de recurso que pueda necesitar.

- Cuando un proceso solicita un conjunto de recursos, el sistema debe determinar si la asignación de esos recursos dejará al sistema en un estado seguro.

Estado seguro

- Un sistema está en un estado seguro sólo si existe una secuencia segura.

- Una secuencia de procesos es segura si por cada Pi, los recursos que Pi puede aún requerir, pueden ser satisfechos por los recursos actuales disponibles más los recursos retenidos por todos los Pj con j

- Si la secuencia no existe, entonces se dice que el estado del sistema es inseguro.

- No todos los estados inseguros son bloqueos. Un estado inseguro puede conducir a un bloqueo.

- Mientras el estado sea seguro, el S.O. puede evitar estados inseguros.

Recuperación del bloqueo

Cuando un algoritmo de detección determina que existe un bloqueo, el paso siguiente puede ser:

- Informar al operador del bloqueo para que lo trate manualmente

- Dejar que el sistema se recupere del bloqueo automáticamente

Hay dos opciones para romper un bloqueo:

- Abortar uno o más procesos para romper la espera circular

- Apropiar algunos recursos de uno o más procesos bloqueados

Terminación de procesos•

- Hay dos métodos para eliminar bloqueos abortando procesos:

§ Abortar todos los procesos bloqueados

§ Abortar un proceso por vez hasta eliminar el ciclo del bloqueo

Algoritmo del banquero

1. Si Solicitudi <= Necesidadi, pasar a punto 2. Sino ERROR.

2. Si Solicitudi <= Disponiblei, pasar a punto 3. Sino Pi debe esperar.

3. El S.O. asigna los recursos solicitados:

Disponiblei=Disponiblei – Solicitudi

Asignacióni=Asignacióni+Solicitudi

Necesidadi= Necesidadi – Solicitudi

1. Si estado seguro, entonces asignación satisfecha. Sino Pi espera.

Algoritmo de Seguridad

1. Sean Trabajo=Disponible y Fin[i]=Falso.

2. Encontrar un i tal que: (Fin[i]==falso) y Necesidadi<=Trabajoi. Si no existe, pasar a paso 4

3.Trabajo=Trabajo + Asignación

Fin[i]=Verdadero

Volver a paso 2.

1. Si Fin[i] = Verdadero para todo i, entonces ESTADO SEGURO.