Semaforo no-binario usando binarios

Semaforo no-binario usando binarios

de Hernan Esteves Rosano -
Número de respuestas: 3

Hola. En un material que tengo plantean 4 soluciones para implementar esto. Una de ellas es supuestamente incorrecta, el problema es que no logro ver por qué. La plantea asi:

var
	mutex=1: binary-semaphore;
	delay=0: binary-semaphore;
	C={initvalue}: integer;
Procedure Wait()
begin
	wait(mutex);
	C:=C-1;
	if C<0 then begin
		signal(mutex);
		wait(delay);
		end
	else
		signal(mutex);
end
Procedure Signal()
begin
	wait(mutex);
	C:=C+1;
	if C <= 0 then
		signal(delay)
	signal(mutex)
end

Agradezco si alguien puede ayudarme a ver cual es el error.

En respuesta a Hernan Esteves Rosano

Re: Semaforo no-binario usando binarios

de Diego Barreiro Indart - 
if C<0 then begin
                signal(mutex); (* A *)
                wait(delay);   (* B *)
                end
        else
                signal(mutex);

El wait(delay) en Wait() debería estar antes del signal(mutex). Se supone que si P1 llama a Wait() antes que P2, entonces P1 debería ser habilitado antes que P2 para entrar a la sección crítica. Imaginate la situación siguiente:

C ← 1

P0 llama Wait(S)
P1 llama Wait(S) y ejecuta hasta A
P2 llama Wait(S) y llega hasta B, duerme
P1 continúa y llega a B, duerme
P0 llama Signal(S) y despierta a P2 en lugar de despertar a P1

Le estuve dando vueltas y no veo posposición indefinida ni deadlocks. Pero igual no debería pasar esto tampoco. Se supone que el semáforo no asegura un orden para procesos que llegan al mismo tiempo, pero sí para procesos que llegan en un orden bien definido. De hecho el mutex en Wait() queda parcialmente inútil con el código como está (c podría llegar a valer cualquier valor negativo, cuando es claro que la intención del que hizo el código era que no pudiera bajar de -1. En este escenario es un detalle menor, en otros casos podría ser grave).

Saludos

En respuesta a Diego Barreiro Indart

Re: Semaforo no-binario usando binarios

de Nicolas Tabare Tomeo Raspino -

Me parece que lo que planteas vos no implica error, por lo menos yo había entendido que dependía de la implementación por lo que se debía suponer que el Signal despierta un proceso al azar.
Si existe deadlock.
Ejemplo:
Supongo tres procesos que corren concurrentemente P1,P2,P3.
C inicializado en 0.
P1 ejecuta Wait() hasta el signal (mutex) includio. C vale -1, mutex 1, delay 0.
P2 ejecuta Wait() hasta el signal(mutex) incluido. C vale -2,mutex 1,delay 0.
P3 ejecuta dos veces Signal() completo. C vale 0,mutex 1, delay 1.
P1 ejecuta lo que le faltaba. C vale 0, mutex 1, delay 0.
P2 se bloquea en el wait(delay).

Esto no debería suceder dado que al estar implementando semáforos no binarios el ejecutar mas de un Signal() seguido por mas de que no se ejecuten Wait() debería aumentar la cantidad de permisos disponibles.