Los mensajes de nSystem son un mecanismo para sincronizar procesos. Existen otros mecanismos que veremos a partir de esta sección, algunos radicalmente distintos, otros también basados en mensaje pero con una semántica distinta, es decir el funcionamiento de los mensajes es distinto.
Un semáforo es un distribuidor de tickets y sirve para acotar el número de tareas que pasan por una determinada instrucción. Para ello un semáforo S dispone de una cierta cantidad de tickets a repartir.
Las operaciones que acepta un semáforo son:
: Pide un ticket al semáforo. Si el semáforo no
tiene tickets disponibles, el proceso se bloquea hasta que otro
proceso aporte tickets a ese mismo semáforo.
: Aporta un ticket al semáforo. Si había algún
proceso esperando un ticket, se desbloquea. Si había más procesos
esperando tickets, se desbloquea el primero que llegó pidiendo
tickets.
En nSystem los semáforos se crean con:
nSem sem= nMakeSem(inittickets);
En donde inittickets es la cantidad inicial de tickets. Las operaciones Wait y Signal se llaman nWaitSem y nSignalSem respectivamente. Además un semáforo se destruye con nDestroySem.
Uno de los usos de los semáforos es la implementación de secciones críticas. Por ejemplo el problema del conteo de pfib se puede resolver con:
int count= 0;
nSem sem= nMakeSem(1);
int pfib(int n)
{
nWaitSem(sem);
count++;
nSignalSem(sem);
...
}
El semáforo contiene inicialmente un solo ticket. La primera tarea que llega a la sección crítica pide el único ticket, de modo que ninguna otra tarea puede entrar a la sección crítica. Al salir la tarea devuelve el ticket para que otra tarea pueda entrar a la sección crítica.
Un proceso productor produce ítemes depositándolos en un buffer. Los ítemes son extraídos del buffer por un proceso consumidor. El buffer puede contener hasta un máximo de N ítemes. El productor y consumidor trabajan concurrentemente.
El buffer se mantiene en un arreglo de N ítemes de tipo
Item. La variable nexempty indica el índice en el arreglo en
donde hay que depositar el próximo ítem producido. La variable
nextfull indica el índice en el arreglo de donde hay que extraer el
próximo ítem por consumir. Esta estructura se aprecia en la
figura 
.
Figure: El problema del productor/consumidor
El problema está en lograr que cuando el consumidor trata de extraer un ítem cuando el buffer está vacío, el consumidor se bloquee hasta que el productor deposite un ítem. Del mismo modo, cuando el productor intenta depositar un ítem cuando el buffer ya tiene el máximo de N ítemes, el productor se debe bloquear hasta que el consumidor extraiga un ítem.
Veamos una solución de este problema usando dos semáforos. Un semáforo mantendrá el número de posiciones disponibles para depositar ítemes en el buffer. Cuando el productor deposita un ítem resta un ticket con Wait, dado que hay un posición menos en el buffer. Si el buffer está lleno, el productor se bloqueará ya que no hay más tickets en el semáforo. Cuando el consumidor extrae un elemento agrega un ticket con Signal, porque ahora hay una nueva posición disponible.
El segundo semáforo sirve para mantener el número de ítemes dispobibles en el buffer. El productor agrega tickets con Signal y el consumidor quita tickets --si hay disponibles-- con Wait.
La siguiente es una implementación del productor y consumidor.
Inicialmente se tiene:
void Productor()
{
for(;;) /* Ciclo infinito */
{
Item x= Produce();
/* Listo, ya tenemos un item */
Wait(empty);
buff[nextempty]= x;
nextempty= (nextempty+1)%N;
Signal(full);
} }
Consumidor()
{
for(;;) /* Ciclo infinito */
{
Item x;
Wait(full);
x= buff[nextfull];
nextfull=(nextfull+1)%N;
Signal(empty);
Consume(x);
/* Listo, ya consumimos el item */
} }
Observe que las modificaciones de las variables nextempty y nextfull no son secciones críticas, puesto que cada variable es modificada por un solo proceso. Sin embargo si generalizamos el problema a varios productores y consumidores, las modificaciones sí serán secciones críticas.
Ejercicio: Modifique esta solución para que funcione en el caso de varios productores y consumidores.
5 filósofos pasan sus días pensando y comiendo. Cada filósofo tiene
su puesto asignado en una mesa con 5 sillas. En la mesa hay 5 tenedores
como se muestra en la figura .
Figure: El problema de los filósofos comiendo.
Cuando un filósofo piensa no interactúa con el resto de sus colegas. Pero de vez en cuando necesita comer y por lo tanto se sienta en su silla. Para poder comer necesita los dos tenedores que están a ambos lados de su plato. Entonces debe intentar tomar un tenedor primero y después el otro. Si alguno de estos tenedores está en poder de su vecino, el filosófo no puede comer. Debe esperar a que los dos tenedores estén libres. Si logró tomar uno de los tenedores, el filósofo puede mantenerlo mientras espera el otro, como también puede soltarlo para que su otro vecino pueda comer.
Este es el más clásico de los problemas de sincronización debido a que es muy usual encontrar problemas equivalentes en los sistemas concurrentes y distribuidos. Lamentablemente no siempre es sencillo detectar su presencia, por lo que también se le atribuye muchas de las caídas de este tipo de sistemas.
Cada filósofo es un proceso. El uso de cada tenedor es una sección crítica, ya que dos filósofos no pueden estar usando el mismo tenedor en un instante dado. El acceso a los tenedores se controla en un arreglo de 5 semáforos con un ticket cada uno. Para poder comer, el filósofo i debe pedir el ticket del semáforo i y el del semáforo (i+1)%5.
Inicialmente se tiene:
Folosofo(int i)
{
for(;;)
{
Wait(tenedor[i]);
Wait(tenedor[(i+1)%5]);
Comer();
Signal(tenedor[i]);
Signal(tenedor[(i+1)%5]);
Pensar();
} }
Observe que en esta solución, cuando un filósofo tomó un tenedor no lo suelta a pesar de que tiene que esperar por el próximo tenedor.
Esta solución es errónea porque los filósofos pueden llegar a una situación de bloqueo eterno, o en inglés dead-lock. Esta situación se produce cuando cada filósofo está en poder de un tenedor y espera a que el otro se desocupe, lo que nunca ocurrirá. En estas condiciones los filósofos morirán de hambre.
Se tiene especial cuidado al tomar los tenedores, de modo que siempre se tome primero el tenedor con menor índice en el arreglo de semáforos. El código para tomar los tenedores queda:
j=min(i,(i+1)%5); k=max(i,(i+1)%5); Wait(tenedor[j]); Wait(tenedor[k]);
Con este orden es imposible la situación de dead-lock en que cada proceso tenga un tenedor y espere el otro, puesto que el último tenedor (índice 4) siempre se pide en segundo lugar. Por lo tanto se garantiza que al menos uno de los filósofos podrá tomar este tenedor y comer. En el peor de los casos tendrán que comer secuencialmente.
Permitir un máximo de 4 filósofos en la mesa. Para lograr esto se necesita un nuevo semáforo ( sala) que parte inicialmente con 4 tickets.
Folosofo(int i)
{
for(;;)
{
Wait(sala);
Wait(tenedor[i]);
Wait(tenedor[(i+1)%5]);
Comer();
Signal(tenedor[i]);
Signal(tenedor[(i+1)%5]);
Signal(sala);
Pensar();
} }
Con esta restricción también se garantiza que al menos un filósofo podrá comer. Al resto tarde o temprano le llegará su turno.