2.4.2.1 Mecanismo de semáforos.

Semáforos
Son una herramienta de sincronización. Es una variable protegida que solo puede ser modificada por la rutina de inicialización y por otras dos operaciones atómicas:
P( ) <- wait
V( ) <- signal
Las operaciones a las cuales se puede acceder son:
Inicialización: Crea un nuevo semáforo asignándole un valor inicial
P(s): while (s=0) do no_op ATÓMICA
s:=s-1
V(s): s:=s+1 ATÓMICA
Existen básicamente dos tipos de semáforos:

·         Semáforos contadores: Toman valores positivos mayores o iguales a 0. Se utilizan para sincronización de procesos.

·         Semáforos binarios: Toman los valores 0 ó 1 y se utilizan para exclusión mutua.

A continuación se presenta una solución mediante semáforos del problema productor/consumidor.
#define N 100
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void productor(void)
{int item;
while(1){
produce_item(item);
down(empty);
down(mutex);
enter_item(item);
up(mutex);
up(full);}
}
void consumidor(void)
{ int item;
while(1){
down(full);
down(mutex);
remove_item(&item);
up(mutex);
up(empty);
consume_item(item);}
}
En este caso tenemos la utilización de 3 semáforos, uno destinado al control de la exclusión mutua y los otros dos destinados a la sincronización de los procesos para el control de buffer lleno y vacío.
Podríamos utilizar semáforos para un algoritmo de espera ocupada con n procesos, pero los n procesos que están ejecutando el while de la función P(s) van a la cola de ready en un instante de tiempo reduciendo la performance general del equipo.
Para evitar la espera ocupada se crea un semáforo que sea un registro de un nuevo tipo:
Semáforo = Record
Valor:Integer
L:Lista_de_Procesos
End
P(s) {
s.Valor:= s.valor - 1
if s.Valor < 0 then agregar este proceso a s.L
bloquear;
end}
V(s){
s.Valor:=s.Valor + 1
if s.Valor £ 0 then quitar un proceso y a s.L
despertar(y) }

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, por ejemplo, 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 se puede implementar varias formas que se destinguen en sus grados de justicia, por ejemplo con un simple sistema tipo FIFO.

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, por ejemplo, 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