Semáforos

Un semáforo es un tipo de datos abstracto que permite el uso de un recurso de manera exclusiva cuando varios procesos están compitiendo.

El tipo de datos abstracto cumple la siguiente semántica:

• El estado interno del semáforo cuenta cuantos procesos todavía pueden utilizar el recurso. Se puede realizar, p.e., con un número entero que nunca llega a ser negativo.
• Exiten tres operaciones con un semáforo: init(), wait(), y signal() que realizan lo siguiente:

  init()

  : Inicializa el semáforo antes de que cualquier proceso haya ejecutado ni una operación wait() ni una operación signal() al límite de número de procesos que tengan derecho a acceder el recurso. Si se inicializa con 1, se ha contruido un semáforo binario.

  wait()

  : Si el estado indica cero, el proceso se queda atrapado en el semáforo hasta que sea despertado por otro proceso. Si el estado indica que un proceso más puede acceder el recurso se decrementa el contador y la operación termina con exito.

  La operación wait() tiene que estár implementada como una instrucción atómica. Sin embargo, en muchas implementaciones la operación wait() puede ser interrumpida. Normalmente existe una forma de comprobar si la salida del wait() es debido a una interrupción o porque se ha dado acceso al semáforo.

  signal()

  : Una vez se ha terminado el uso del recurso, el proceso lo señaliza al semáforo. Si queda algún proceso bloqueado en el semáforo uno de ellos sea despertado, sino se incrementa el contador.

  La operación signal() también tiene que estár implementada como instrucción atómica. En algunás implementaciones es posible comprobar si se haya despertado un proceso con exito en caso que hubiera alguno bloqueado.

  Para despertar los procesos existen varias formas que se destinguen en sus grados de justicia:

  • FIFO que garantiza que no se produzca inanicón de ningún proceso estando bloqueado en el semáforo
  • aleatorio que puede resultar en inanición
  • ...

El acceso mutuo a regiones críticas se arregla con un semáforo que permita el acceso a un sólo proceso

S.init(1)

P1                         P2
a: loop                        loop
b:   S.wait()                    S.wait()
c:   critical region             critical region
d:   S.signal()                  S.signal()
e:   non-critical region         non-critical region
f: endloop                     endloop

Observamos los siguiente detalles:

• Si algún proceso no libera el semáforo, se puede provocar un bloqueo.
• No hace falta que un proceso libere su propio recurso, es decir, la operación signal() puede sea ejecutada por otro proceso.
• Con simples semáforos no se puede imponer un orden en los procesos accediendo a diferentes recursos.

Si existen en un entorno solamente semáforos binarios, se puede simular un semáforo general usando dos semáforos binarios y un contador, p.e., con las variables delay, mutex y count.

La operación init() inicializa el contador al número máximo permitido. El semáforo mutex asegura acceso mutuamente exclusivo al contador. El semáforo delay atrapa a los procesos que superan el número máximo permitido.

La operación wait() se implementa de la siguiente manera:

  delay.wait()
  mutex.wait()
  decrement count
  if count greater 0 then delay.signal()
  mutex.signal()

y la operación signal() se implementa de la siguiente manera:

  mutex.wait()
  increment count
  if count equal 1 then delay.signal()
  mutex.signal()

Unas principales desventajas de semáforos son:

• no se puede imponer el uso correcto de los wait()s y signal()s
• no existe una asociación entre el semáforo y el recurso
• entre wait() y signal() el usuario puede realizar cualquier operación con el recurso