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

• Erika tiene Cap. 7 y una copia del código de Nachos.

Evitación de deadlock

• En esta estrategia usamos información sobre cuantos recursos los procesos pueden necesitar. Con esta información podemos asegurar que el sistema nunca entrará en un estado de deadlock.
• Requerimos que cada proceso especifique el número máximo de recursos que pueda necesitar. Entonces revisamos cada solicitud y determinamos si el sistema pudiera entrar en deadlock.
• Estado seguro. Un estado del sistema es seguro si el sistema puede asignar recursos a cada proceso (hasta su máximo) en alguna ordenación y aún evita deadlock.

  Es decir, un estado es seguro sólo si existe una secuencia segura. Tenemos una secuencia de procesos ₁, $P$₂,...,$P$_n> donde, para cada $P$_i, los recursos que $P$_i aún puede solicitar puede satisfacerse con los recursos disponibles y los recursos retenidos por $P$₁ hasta $P$_i-1.

  Con una secuencia segura, $P$_i puede esperar para obtener sus recursos hasta que $P$₁ hasta $P$_i-1 terminen.

• Un estado seguro no es un estado de deadlock, pero un estado inseguro no es necesariamente un estado de deadlock.
• Ejemplo: 12 grabadores, 3 libres.

  	max	tiene
  $P$0	10	5
  $P$1	4	2
  $P$2	9	2

  • ¶ ¿Es este estado seguro? ₁,$P$₀,$P$₂>
  • ¶ ¿Que pasa si damos un grabador más a $P$₂? Estado inseguro. ¿Tenemos deadlock?
• En los algoritmos de evitación de deadlock damos recursos a procesos solamente si las asignaciones dejan el sistema en un estado seguro.

Algoritmo de banquero

• Para cada proceso $P$ tenemos un array max de ₁,$m$₂,...$>$ y un array tiene de ₁,$t$₂,...$>$ (los índices son tipos de recursos).
• Tenemos también el array libre de ₁,$f$₂,...$>$.
• Si $P$ tiene una solicitud, examinamos la situación donde libre es disminuido por la solicitud. Si existe un proceso donde la diferencia entre max y tiene es menos o igual que libre (para todos los recursos), él puede terminar.
• Añadimos su tiene a libre y chequeamos todos los procesos otra vez. Continuamos hasta que mostramos que todos los procesos pueden terminar. Entonces, este estado es seguro. De otro modo, el estado es inseguro.
• Ejemplo:

  libre	max				tiene				max$-$tiene
  	A	B	C	D	A	B	C	D	A	B	C	D
  1	3	6	3	4	1	5	2	0	2	1	1	4
  1	2	1	1	2	0	1	1	0	2	0	0	2
  2	2	3	4	2	0	1	1	2	2	2	3	0

  ¶ $P$_B solicita un $R$₁ y un $R$₃. ¿Es el nuevo estado seguro? Una posibilidad es _B,$P$_A,$P$_C,$P$_D>.