IIC 2332 -- Sistemas Operativos
Apuntes 07
1er Semestre 1996

Noticias

• La primera tarea está disponible con Erika. El plazo vence 15.04.1996, 11:30.
• Grupos de trabajo.
• Solicita cuentas de <mda@ing.puc.cl>.
• Ayudantía: Variables de condición

Deadlock

• Un S.O. tiene un número limitado de recursos y procesos que solicitan los recursos.
• ¶Como diseñador de un sistema operativo, ¿cuál es el problema para ti si algunos procesos un tu sistema están en deadlock esperando recursos?
• Los recursos retenidos por los procesos en deadlock no están disponibles para otros procesos, y los procesos en deadlock no pueden avanzar (es mal para los dueños de los procesos).
• Muchos SS.OO. modernos no tienen apoyo especial para prevenir deadlock (porque cuesta), pero es común en programación de sistemas en general (e.g., en programación distribuida).

Características de deadlock

• El sistema tiene recursos de varios tipos: memoria, archivos, grabadores, impresoras, etc. Podemos tener más de un ejemplar de un tipo de recurso (e.g., tres impresoras). Cada uno de los ejemplares pueden satisfacer un solicitud de un proceso para el recurso.
• Los recursos son compartibles y permiten acceso a muchos procesos (e.g., los archivos de sólo lectura) o no compartibles (e.g., un grabador).
• Ejemplo: Tres procesos en un sistema con tres grabadores, cada proceso tiene un grabador y cada uno necesita uno más.
• Condiciones necesarias de deadlock:
  • ¶ Exclusión mutua. Por lo menos un recurso debe retenerse no compartido. ¿Por qué?
  • Retención y espera. Debe haber un proceso que retenga por lo menos un recurso y espere adquirir más recursos retenidos por otros.
  • No apropiación. Los recursos no se pueden expropiar. Los procesos liberan recursos sólo voluntariamente.
  • Espera circular. Debe haber un conjunto {$P$₀, $P$₁, ..., $P$_n} de procesos en espera tales que $P$₀ espere un recurso de $P$₁, $P$₁ un recurso de $P$₂, ..., y $P$_n un recurso de $P$₀.
• Podemos usar un grafo de asignación de recursos para describir deadlock. Tenemos procesos (círculos), recursos (rectángulos con un punto para cada ejemplar), aristas de solicitud y de asignación (cambio instantáneamente).
• Un grafo sin ciclos implica que no hay deadlock. Si hay un ciclo, es posible que exista deadlock. Un ciclo es una condición necesaria pero no suficiente para deadlock.

Prevención de deadlock

• ¶ Deadlock no puede occurir a menos que tenemos todas las cuatro condiciones. Si aseguramos que no puede occurir por lo menos una de las condiciones, no podemos tener deadlock.
• ¶ Exclusión mutua. En general, no podemos eliminar esta condición. Hay recursos como impresoras que no son compartibles.
• ¶ Retención y espera. Para no occurir esta condición, cuando un proceso solicita recursos, no puede retener otros. Protocolos:
  • Un proceso puede solicitar recursos solamente si no tiene ningunos.
  • Un proceso tiene que solicitar todos los recursos antes de la ejecución.
  ¶ Problemas:
  • La utilización de recursos puede ser baja.
  • Starvation (bloqueo indefinido) si se necesitan algunos recursos populares.
• No apropiación. Si un proceso retiene varios recursos y solicita otro que no está disponible, se le expropian todos los recursos que retiene. El proceso tiene que recuperar todos los recursos antes de ejecutar otra vez.

  Pero en general no podemos exproprian recursos como impresoras y grabadores.

• Espera circular. Hacemos una ordenación de los tipos de recursos en el sistema ($R$₁, $R$₂, ...). Un proceso tiene que solicitar sus recursos en orden (y todos los ejemplares de un tipo al mismo tiempo). Si necesita un tipo de recurso más baja en la ordenación, tiene que liberar los otros que retiene.
• Problemas con la prevención de deadlock: Utilización baja de recursos y reducción de la productividad del sistema.