SEMÁFOROS BINARIOS

Definición y operaciones de los semáforos.
Los semáforos fueron enunciados por Dijkstra en 1965. Un semáforo es una variable S, que puede tomar valores enteros positivos, sobre la cual solo se pueden hacer tres operaciones que son:
S : semaforo;
A) Inicialización(S): asignarle cierto valor
B) wait(S), Down(S) ó P(S): si S > 0
entonces S <-- S-1
en otro caso "bloquear" el proceso hasta que S>0
C) signal(S), Up(S) ó V(S): si hay procesos bloqueados
entonces despertar uno de esos procesos
en otro caso S <-- S+1

Estas operaciones deben ser consideran indivisibles, de tal forma que si un proceso está ejecutando una de ellas, ningún otro proceso puede estar ejecutando cualquiera de ellas sobre el mismo semáforo. Esta propiedad es fundamental para poder demostrar que, por medio de semáforos, se cumplen las propiedades de seguridad de los sistemas concurrentes. A cada semáforo se le supone asociada una cola de procesos, donde estarán los procesos que esperan a que el valor del mismo no sea cero. Normalmente, la planificación de esta cola de procesos es normalmente de tipo FIFO (First-in First-out). En la mayoría de los casos, éstas decisiones se toman en el proceso de diseño del Sistema Operativo, ya que los semáforos son un mecanismo de bajo nivel, gestionado por el sistema operativo. Para resolver la vivacidad, se establece la "propiedad de corrección de los semáforos", que dice lo siguiente:
"Si un proceso está esperando en la cola del semáforo S y S alcanza valores mayores que
cero infinitamente a menudo, el proceso eventualmente despertará".
Es función del sistema operativo que se verifique esta propiedad, aunque podemos ver
que para que se cumpla, basta con que la cola de procesos sea de tipo FIFO.
Se distinguen dos tipos de semáforos, los semáforos binarios y los semáforos contadores
(generales). Los semáforos binarios sólo pueden tomar los valores 0 y 1, mientras que los
semáforos contadores pueden tomar cualquier valor entero no negativo

Aplicaciones de los semáforos.

Se va a usar la instrucción concurrente COBEGIN-COEND para lanzar de forma concurrente la ejecución de todos los programas que se encuentran dentro de dicha instrucción.

Problema de la Exclusión Mutua.

Se tiene dos programas donde cada uno posee su propia sección crítica sobre el mismo recurso no compartido, por lo tanto se pretende obtener exclusión mutua en el uso de dicho recurso. Para ello se usa el semáforo mutex inicializado a 1 para que el recurso solo sea asignado a uno de los procesos en cada momento. Para probar el buen funcionamiento del semáforo, los programas tienen un ciclo infinito (repeat ...... until false;), o sea, se están repitiendo continuamente.

var mutex:semaforo;
procedure EXCL1; procedure EXCL2;
begin begin
Repeat Repeat
{Código} {Código}
wait(mutex); wait(mutex);
{Sección crítica 1} {Sección crítica 2}
signal (mutex); signal(mutex)
{Resto código} {Resto código}
until false; until false;
end; end;

begin
mutex:= 1;
COBEGIN EXCL1,EXCL2 COEND;
end.
Como se puede comprobar, si el proceso P2 fuese más rápido que el P1, no se produciría
ninguna interrupción (tal y como debería ser). Sin embargo, como el semáforo está inicializado a
cero, si el proceso P1 va más rápido, al llegar al punto P se espera a que lo libere el proceso P2
cuando llega al punto S (tal y como queríamos).

Problema del Productor-Consumidor.
El problema del productor-consumidor es un problema concurrente clásico. Se tiene una serie de procesos productores y una serie de procesos consumidores que se comunican a través de un buffer (en principio de tamaño ilimitado), donde los procesos productores van colocando elementos y los consumidores van sacando elementos. Si se considera a n la variable que contiene el número de elementos del buffer en cada momento, las operaciones sobre esa variable n son un recurso crítico del sistema. Aparte se debe tener en cuenta que el proceso consumidor no puede tomar elementos si el buffer está vacío (tiene que esperar a que algún productor coloque algún elemento). Por lo tanto en este problema se debe resolver cuestiones de exclusión mutua y sincronización. A continuación se presenta una solución mediante semáforos:

var mutex,seguir: semaforo;
procedure ProdN; procedure ConsN;
begin begin
wait(mutex); wait(seguir);
n <-- n+1; wait(mutex);
añadir; n <-- n-1;
signal(mutex); consumir;
signal(seguir); signal(mutex);
end; end;
begin
mutex:= 1;
seguir:= 0;
n:= 0;
COBEGIN Prod1,Prod2, . ,ProdN,Cons1,Cons2, . ,ConsN COEND
end.

Se debe notar que el orden de las operaciones wait en el proceso consumidor es muy importante, ya que, por ejemplo, si se cambia el orden de dichas operaciones se puede producir un deadlock si entra primero un proceso consumidor, ya que se quedaría esperando por un semáforo (seguir) al que ningún proceso productor va a hacer un signal, ya que el proceso que ejecuta dicho signal (el productor) está esperando por otro semáforo (mutex) que tampoco nadie va a liberar, por que el encargado de hacerlo era el proceso consumidor. En esta versión del problema se ha considerado que el buffer es infinito y por tanto, los procesos productores pueden producir ininterrumpidamente. Hay una versión del problema con un buffer de tamaño limitado que se verá cuando se estudie el mecanismo de los monitores.

Referencias: www.ei.uvigo.es/~nrufino/so/semaforo.pdf