3.3 Bloqueo Mutuo

Los sistema de las computadoras tienen muchos recursos que a su vez solo pueden ser utilizados por un proceso a la vez.

Un proceso necesita permiso exclusivo para varios recursos no a un solo recurso específico.

Los bloqueos mutuos pueden ocurrir de muchas maneras, principalmente cuando se le otorga a los procesos acceso a dispositivos E/S de uso exclusivo.

Un bloqueo mutuo también es conocido como interbloqueo es el bloqueo permanente de uno o varios procesos de ejecución donde compiten por un recurso del sistema.

Recursos

Un recurso puede ser un dispositivo de hardware o algún elemento de información. Un recurso solo puede ser usado por un proceso durante un instante cuando el recurso esté disponible.

Los recursos pueden ser de dos tipos: el primero es el expropiable y el otro es el No expropiable. El recurso expropiable es aquel que se le puede quitar al proceso poseedor el recurso que tiene en su poder sin que ocurran cambios.

Un recurso no expropiable no se le puede quitar a su poseedor actual, es decir, al proceso que lo tiene.

La secuencia de eventos que se requiere para poder usar un recurso es la siguiente:

1. Solicitar el recurso

2. Usar el recurso

3. Liberar el recurso

Si el recurso no está disponible cuando se lo solicita:

• El proceso solicitante debe esperar.
• En algunos SO el proceso se bloquea automáticamente y se despierta cuando dicho recurso está disponible.
• En otros SO la solicitud falla y el proceso debe esperar para luego intentar nuevamente.

Principios del bloqueo mutuo

El bloqueo mutuo puede definirse de la siguiente manera:

Un conjunto de procesos se encuentra en bloqueo mutuo, si cada conjunto del proceso se encuentra esperando un evento que solo otro proceso del conjunto puede causar.

Condiciones para el bloqueo mutuo.
- Exclusión mutua: solo un proceso por vez puede usar el recurso.
- Retención y espera: debe existir un proceso que esté reteniendo por lo menos un recurso y esté esperando adquirir recursos adicionales que en ese momento estén siendo retenidos por otro proceso.
- No apropiación: un recurso solo puede ser liberado voluntariamente por el proceso que lo está reteniendo, una vez que dicho proceso ha completado su tarea.
- Espera circular: debe existir 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.

Son cuatros las estrategias que se usan para controlar el bloqueo mutuo:

1. Hacer caso del problema

2. Detección y recuperación

3. Evitarlos dinámicamente mediante una cuidadosa asignación de recursos.

4. Prevención mediante la negación estructural de una de las cuatro condiciones necesarias.

El algoritmo del avestruz

El punto de vista más simple es pretender que no existe el problema

Esta estrategia puede generar distintas reacciones:

• Matemáticamente es inaceptable, considerándose que los bloqueos deben evitarse a toda costa.
• Desde la ingeniería de software podría considerarse cuál es la frecuencia esperada del problema, cuáles son sus consecuencias esperadas, cuáles son las frecuencias esperadas de fallas de otro tipo, etc.

Algunos SO soportan potencialmente bloqueos que ni siquiera se detectan, ya que se rompen automáticamente.

Los SO. que ignoran el problema de los bloqueos asumen la siguiente hipótesis:

• La mayoría de los usuarios preferiría un bloqueo ocasional, en vez de una regla que restringiera a todos los usuarios en el uso de los distintos tipos de recursos.

El problema es que se debe pagar un cierto precio para encarar el problema del bloqueo:

• En restricciones para los procesos.
• En el uso de recursos.

Se presenta una contradicción entre la conveniencia y lo que es correcto.

Es muy difícil encontrar teóricamente soluciones prácticas de orden general aplicables a todos los tipos de SO.

Un criterio de orden general utilizado por los SO que no hacen tratamiento específico del bloqueo consiste en:

• Intentar acceder al recurso compartido.
• De no ser factible el acceso:
• Esperar un tiempo aleatorio.
• Reintentar nuevamente.

Detección y recuperación

En esta segunda estrategia, el sistema no realiza otra cosa que no sea vigilar las peticiones y liberar los recursos.

El SO no intenta evitar los bloqueos:

• Intenta detectar cuando han ocurrido.
• Acciona para recuperarse después del hecho.

La detección del bloqueo es el proceso de:

• Determinar si de hecho existe o no un bloqueo.
• Identificar cuáles son los procesos y recursos implicados en el bloqueo.

Los algoritmos de detección de bloqueos implican cierta sobrecarga en tiempo de ejecución.

Prevención de Bloqueos

Si se puede garantizar que al menos una de las cuatro condiciones de Coffman para el bloqueo nunca se satisface, entonces los bloqueos serán imposibles por razones estructurales.

Havender sugirió las siguientes estrategias para evitar varias de las condiciones de bloqueo:

• Cada proceso:
• Deberá pedir todos sus recursos requeridos de una sola vez.
• No podrá proceder hasta que le hayan sido asignados.
• Si a un proceso que mantiene ciertos recursos se le niega una nueva petición, este proceso deberá:
• Liberar sus recursos originales.
• En caso necesario, pedirlos de nuevo junto con los recursos adicionales.
• Se impondrá la ordenación lineal de los tipos de recursos en todos los procesos:
• Si a un proceso le han sido asignados recursos de un tipo dado, en lo sucesivo solo podrá pedir aquellos recursos de los tipos que siguen en el ordenamiento.

Havender no presenta una estrategia contra el uso exclusivo de recursos por parte de los procesos, pues se desea permitir el uso de recursos dedicados.

Prevención de la Condición de Exclusión Mutua

Si ningún recurso se asignara de manera exclusiva a un solo proceso, nunca tendríamos bloqueos, pero esto es imposible de aplicar, en especial en relación a ciertos tipos de recursos, que en un momento dado no pueden ser compartidos (ej.: impresoras).

Se debe:

• Evitar la asignación de un recurso cuando no sea absolutamente necesario.
• Intentar asegurarse de que los menos procesos posibles puedan pedir el recurso.

Prevención de la Condición “detenerse y esperar” o “espera por”

Si se puede evitar que los procesos que conservan recursos esperen más recursos, se pueden eliminar los bloqueos.

Una forma es exigir a todos los procesos que soliciten todos los recursos antes de iniciar su ejecución; si un proceso no puede disponer de todos los recursos, deberá esperar, pero sin retener recursos afectados.

Un problema es que muchos procesos no saben el número de recursos necesarios hasta iniciar su ejecución.

Otro problema es que puede significar desperdicio de recursos, dado que todos los recursos necesarios para un proceso están afectados al mismo desde su inicio hasta su finalización.

Otro criterio aplicable consiste en:

• Exigir a un proceso que solicita un recurso que libere en forma temporal los demás recursos que mantiene en ese momento.
• Hacer que el proceso intente luego recuperar todo al mismo tiempo.

Prevención de la Condición de “no apropiación”

Una de las estrategias de Havender requiere que cuando a un proceso que mantiene recursos le es negada una petición de recursos adicionales; deberá liberar sus recursos y si es necesario pedirlos de nuevo junto con los recursos adicionales.

La implementación de esta estrategia niega la condición de “no apropiación” y los recursos pueden ser retirados de los procesos que los retienen antes de la terminación de los procesos.

El problema consiste en que el retiro de ciertos recursos de un proceso puede significar:

• La pérdida del trabajo efectuado hasta ese punto.
• La necesidad de repetirlo luego.

Una consecuencia seria es la posible postergación indefinida de un proceso.

Prevención de la Condición de “espera circular”

Una forma es que un proceso solo está autorizado a utilizar un recurso en cada momento:

• Si necesita otros recursos, debe liberar el primero.
• Esto resulta inaceptable para muchos procesos.

Otra forma es la siguiente:

• Todos los recursos se numeran globalmente.
• Los procesos pueden solicitar los recursos en cualquier momento:
• Las solicitudes se deben hacer según un cierto orden numérico (creciente) de recurso; debido a lo cual la gráfica de asignación de recursos no tendrá ciclos.
• En cada instante uno de los recursos asignados tendrá el número más grande:
• El proceso que lo posea no pedirá un recurso ya asignado.
• El proceso terminará o solicitará recursos con números mayores , que estarán disponibles:
• Al concluir liberará sus recursos.
• Otro proceso tendrá el recurso con el número mayor y también podrá terminar.
• Todos los procesos podrán terminar y no habrá bloqueo.

Una variante consiste en eliminar el requisito de adquisición de recursos en orden creciente:

• Ningún proceso debe solicitar un recurso con número menor al que posee en el momento.

El problema es que en casos reales podría resultar imposible encontrar un orden que satisfaga a todos los procesos.

Evitar los bloqueos mutuos

En este análisis se supone implícitamente que si un proceso solicita recursos, los solicita todos al mismo tiempo:

• En la mayoría de los sistemas los recursos se solicitan uno a la vez.
• El SO debe poder:
• Decidir si el otorgamiento de un recurso es seguro o no.
• Asignarlo solo en caso de que sea seguro.

El objetivo es evitar el bloqueo haciendo la elección correcta todo el tiempo, pero para evitar los bloqueos se requiere de cierta información de antemano.

El Algoritmo del Banquero para solo un recurso

Es un algoritmo de planificación que puede evitar los bloqueos.

En la analogía:

• Los clientes son los procesos, las unidades de crédito son los recursos del sistema y el banquero es el SO.
• El banquero sabe que no todos los clientes necesitaran su crédito máximo otorgado en forma inmediata, por ello reserva menos unidades (recursos) de las totales necesarias para dar servicio a los clientes.

Un estado inseguro no tiene que llevar a un bloqueo.

El algoritmo del banquero consiste en:

• Estudiar cada solicitud al ocurrir ésta.
• Ver si su otorgamiento conduce a un estado seguro:
• En caso positivo, se otorga la solicitud.
• En caso negativo, se la pospone.
• Para ver si un estado es seguro:
• Verifica si tiene los recursos suficientes para satisfacer a otro cliente:
• En caso afirmativo, se supone que los préstamos se pagarán.
• Se verifica al siguiente cliente cercano al límite y así sucesivamente.
• Si en cierto momento se vuelven a pagar todos los créditos, el estado es seguro y la solicitud original debe ser aprobada.

Trayectorias de Recursos

Los principales algoritmos para evitar los bloqueos se basan en el concepto de estados seguros

El Algoritmo del Banquero para varios recursos

Acá también los procesos deben establecer sus necesidades totales de recursos antes de su ejecución y dada una matriz de recursos asignados, el S. O. debe poder calcular en cualquier momento la matriz de recursos necesarios.

El algoritmo para determinar si un estado es seguro o no es el siguiente:

1. Se busca un renglón “R” cuyas necesidades de recursos no satisfechas sean menores o iguales que “A”:

o Si no existe tal renglón, el sistema se bloqueará en algún momento y ningún proceso podrá concluirse.

2. Supongamos que el proceso del renglón elegido solicita todos los recursos que necesita y concluye:

o Se señala el proceso como concluido y se añaden sus recursos al vector “A”.

3. Se repiten los pasos 1 y 2:

o Hasta que todos los procesos queden señalados como concluidos, en cuyo caso, el estado inicial era seguro, o

o Hasta que ocurra un bloqueo, en cuyo caso, no lo era.