Semáforos y exclusión mutua en sistemas operativos: interbloqueo y recursos

Semáforos en Sistemas Operativos

Exclusión Mutua con Semáforos

Wait(s)

{

S = s - 1

If (s < 0)

Bloquear el proceso;

}

Signal(s)

{

S = s + 1

If (s <= 0)

Desbloquear a un proceso bloqueado en la operación wait;

}

1. Un semáforo puede inicializarse con un valor no negativo.
2. La operación wait decrementa el valor del semáforo. Si el valor se hace negativo, el proceso que ejecuta el wait se bloquea.
3. La operación signal incrementa el valor del semáforo. Si el valor no es positivo, se desbloquea a un proceso bloqueado por una operación wait.

El semáforo se inicializa a 1. De este modo, el primer proceso que ejecute un wait podrá entrar inmediatamente en la sección crítica, poniendo el valor de s a 0. Cualquier otro proceso que intente entrar en la sección crítica la encontrará ocupada y se bloqueará, poniendo el valor de s a -1. Cualquier número de procesos puede intentar entrar; cada uno de estos intentos infructuosos origina un nuevo decremento del valor de s.

Cuando el proceso que entró al principio en su sección crítica salga, se incrementará s y se eliminará uno de los procesos bloqueados (si los hay) de la cola de procesos asociada al semáforo, poniéndolo en el estado listo. Cuando sea planificado de nuevo por el sistema operativo, podrá entrar en la sección crítica.

program exclusion_mutua;
const n = …; (* número de procesos *);
var s: semáforo (:= 1);
procedure P(i: entero);
begin
repeat
wait(s);
(* Sección crítica *)
signal(s);
forever
end;
begin (* programa principal *)
parbegin
  P(1);
  P(2);
  P(n);
parend
end.

Interbloqueo

El interbloqueo es el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros.

Todos los interbloqueos suponen demandas contradictorias de recursos por parte de dos o más procesos. Supóngase que existe un punto en la ejecución de cada proceso en el que se requiere el uso exclusivo de ambos recursos, R1 y R2, para continuar. Llega un punto en el que el proceso P1 ha adquirido el recurso R1 y el proceso P2 ha adquirido el recurso R2 y cada proceso necesita el otro recurso. Este es el punto de interbloqueo.

Recursos Reutilizables

Se pueden distinguir dos categorías generales de recursos: reutilizables y consumibles. Un recurso reutilizable es aquél que puede ser usado con seguridad por un proceso y no se agota con el uso. Los procesos obtienen unidades de recursos que liberan posteriormente para que otros procesos las reutilicen. Como ejemplos de recursos reutilizables se tienen los procesadores, canales de E/S, memoria principal y secundaria, dispositivos y estructuras de datos tales como archivos, bases de datos y semáforos.

Como ejemplo de interbloqueo con recursos reutilizables, considérense dos procesos que compiten por el acceso exclusivo a un archivo D del disco y a una unidad de cinta T.

El interbloqueo se produce si cada proceso retiene un recurso y solicita el otro. Una posible estrategia para resolver estos interbloqueos es imponer restricciones en el diseño del sistema sobre el orden en el que se solicitan los recursos.

Otro ejemplo de interbloqueo con un recurso reutilizable tiene que ver con las peticiones a memoria principal. Supóngase que el espacio disponible es de 200KB y se origina la siguiente secuencia de peticiones:

P1                               P2
Solicitar 80K bytes;       Solicitar 70 K bytes;
Solicitar 60 K bytes;      Solicitar 80K bytes;

Se produce un interbloqueo si ambos procesos avanzan hasta su segunda petición. Si la cantidad de memoria que van a solicitar no se conoce con antelación, resulta difícil enfrentarse a este tipo de interbloqueo por medio de restricciones en el diseño del sistema. La mejor forma de resolver este problema en particular es, de hecho, eliminar la posibilidad, por medio de la memoria virtual.

Recursos Consumibles

Un recurso consumible es aquél que puede ser creado (producido) y destruido (consumido). Normalmente, no hay límite en el número de recursos consumibles de un tipo en particular. Un proceso productor que no está bloqueado puede liberar cualquier número de recursos consumibles. Cuando un proceso adquiere un recurso, éste deja de existir. Como ejemplos de recursos consumibles están las interrupciones, señales, mensajes, e información en buffers de E/S.

Como ejemplo de interbloqueo con recursos consumibles, considérese el siguiente par de procesos:

P1                               P2
Recibir (P2, M);              Recibir (P1, Q);
Enviar (P2, N);               Enviar (P1, R);

El interbloqueo se produce si el receptor se bloquea. De nuevo, la causa del interbloqueo es un error de diseño. Estos errores pueden ser bastante sutiles y difíciles de detectar. Es más, puede darse una combinación de sucesos poco habitual que origine el interbloqueo; así pues, un programa puede funcionar durante un periodo de tiempo considerable, incluso años, antes de que el problema se manifieste.