Semáforos: definición, tipos, patrones y errores

Dijkstra (1965) propuso el semáforo: un entero al que solo se accede con tres operaciones atómicas. Resuelve lo que un mutex no puede, que es ordenar eventos entre procesos y contar recursos, y además evita la espera activa.

Definición (notación de Stallings)

struct semaphore { int count; queueType queue; };

void semWait(semaphore s) {          // P (proberen, «probar»), wait, down, sem_wait
    s.count--;
    if (s.count < 0) { poner este proceso en s.queue; bloquearlo; }
}
void semSignal(semaphore s) {        // V (verhogen, «incrementar»), signal, up, sem_post
    s.count++;
    if (s.count <= 0) { sacar un proceso P de s.queue; ponerlo en la cola de listos; }
}

1. Se inicializa con un entero ≥ 0.
2. semWait decrementa; si el valor queda negativo, el proceso se bloquea.
3. semSignal incrementa; si el valor queda ≤ 0, desbloquea a uno.

Invariantes: si count ≥ 0, es el número de semWait que pueden pasar sin bloquearse. Si count < 0, |count| es el número de procesos en la cola. (En la versión con busy wait de las diapositivas, wait gira mientras S ≤ 0 y el valor nunca baja de 0.)

Tres consecuencias sutiles (Stallings, típicas de verdadero/falso)

1. No se puede saber antes de hacer semWait si el proceso se bloqueará.
2. Tras un semSignal que despierta a alguien, ambos siguen de forma concurrente; no se sabe cuál corre primero.
3. Al hacer semSignal, no se sabe si había alguien esperando: se despiertan 0 o 1 procesos.

Terminología oficial (tabla 5.3)

Término	Definición
Semáforo (contador o general)	entero con 3 operaciones atómicas: inicializar, decrementar e incrementar
Semáforo binario	solo toma 0 o 1
Mutex	como un binario, pero quien lo bloquea debe desbloquearlo: tiene dueño
Condition variable	bloquea un proceso o hilo hasta que una condición sea verdadera
Monitor	construcción de lenguaje: variables + procedimientos + inicialización, con un solo proceso activo a la vez
Event flags	una palabra de memoria donde cada bit representa un evento
Mailboxes / mensajes	intercambio de información que también sirve para sincronizar
Spinlock	exclusión mutua con espera activa en un bucle

Binario formal:

void semWaitB(bsem s)   { if (s.value == 1) s.value = 0; else { encolar; bloquear; } }
void semSignalB(bsem s) { if (cola vacía) s.value = 1; else { desencolar P; ready(P); } }

El binario tiene la misma potencia que el general: uno se puede implementar con el otro (ver el E1 2025-2 P4 más abajo). Un semSignalB sobre un semáforo que ya vale 1 no acumula.

Fuerte vs débil

• Fuerte: la cola es FIFO. Garantiza que no haya starvation y es lo que implementan los SO reales. Stallings supone semáforos fuertes por defecto.
• Débil: el orden en que se sacan los procesos de la cola no está especificado, así que puede haber starvation. Con semáforos débiles hace falta un algoritmo como Morris.

Las diapositivas 39–40 muestran un semáforo fuerte paso a paso: los procesos A, B, C y D pasan entre la cola de listos y la de bloqueados mientras s baja a valores negativos y vuelve a subir.

Implementación sin busy wait

wait y signal son, a su vez, una sección crítica (sobre value y la cola). Se protegen con algo corto: en una sola CPU, deshabilitando interrupciones; en multicore, con un spinlock o TAS (ver la versión con TAS). El busy wait no desaparece del todo, pero queda reducido a unas pocas instrucciones.

Patrones

Patrón	Inicialización	Código
Exclusión mutua	mutex = 1	wait(mutex); SC; signal(mutex);
Recurso con k unidades (multiplex)	s = k	igual; hasta k dentro. Ejemplo de clase: 10 autos y 3 carriles
Señalización / orden (S1 antes que S2)	synch = 0	P1: S1; signal(synch); · P2: wait(synch); S2;
Rendezvous (esperarse mutuamente)	a = 0, b = 0	A: signal(a); wait(b); · B: signal(b); wait(a);
Turnstile (torniquete)	t = 1	wait(t); signal(t);. Si alguien retiene t, nadie pasa
Lightswitch (el primero enciende, el último apaga)	contador + mutex	primero: wait(recurso); último: signal(recurso)
Barrera (N se esperan)	count = 0, mutex = 1, barrier = 0	el N-ésimo hace signal(barrier) y cada uno pasa el testigo con wait(barrier); signal(barrier);

Regla de oro del productor–consumidor: usar un semáforo por restricción (llenos, vacíos, mutex) y hacer primero el wait de conteo y después el de mutex.

Errores típicos

• signal(mutex) … wait(mutex) (orden invertido): varios procesos pueden entrar a la vez.
• wait(mutex) … wait(mutex): el proceso se bloquea a sí mismo, y hay deadlock.
• Omitir un wait o un signal: se pierde la exclusión mutua o hay deadlock.
• Deadlock con dos semáforos (S = Q = 1): P0 hace wait(S); wait(Q); y P1 hace wait(Q); wait(S); → espera circular.
• Starvation: con semáforos débiles, o cuando la cola se atiende en orden LIFO.
• Inversión de prioridad: L (prioridad baja) tiene el recurso, H (alta) lo espera, y M (media) expropia a L una y otra vez, así que H espera indefinidamente. Se soluciona con herencia de prioridad: L hereda la prioridad de H mientras tiene el recurso.

API POSIX

sem_t s;
sem_init(&s, pshared, valor);   // pshared = 0: entre hilos; ≠ 0: entre procesos (en memoria compartida)
sem_wait(&s);                   // P: bloquea si el valor es 0
sem_trywait(&s);                // no bloquea: falla con EAGAIN
sem_timedwait(&s, &abstime);    // con timeout
sem_post(&s);                   // V
sem_getvalue(&s, &v);           // para depurar
sem_destroy(&s);

pthread_barrier_t b;
pthread_barrier_init(&b, NULL, N);  // N hilos deben llegar
pthread_barrier_wait(&b);           // el último libera a todos; uno recibe PTHREAD_BARRIER_SERIAL_THREAD

Los semáforos con nombre (sem_open, para sincronizar procesos), los errores (EAGAIN, EINTR), por qué sem_getvalue nunca da negativo en Linux, y la comparación mutex vs semáforo binario (el mutex tiene dueño) están en Mutex POSIX y futex.

Preguntas de la diapositiva sobre barreras (Sem05)

1. pthread_barrier_init prepara la barrera para que se liberen N hilos cuando lleguen todos.
2. Si N = NUM_THREADS, la barrera se abre cuando llega el último hilo.
3. ¿Qué pasa al llamar a pthread_barrier_wait? El hilo se bloquea hasta que llegan los N; entonces se liberan todos a la vez.
4. Sin barrera, las fases se mezclan: algunos hilos empiezan la fase 2 mientras otros siguen en la 1.
5. Con barrera se garantiza que ningún hilo empieza la fase 2 antes de que todos terminen la fase 1. No hay garantía de orden dentro de cada fase.
6. Si un hilo tarda mucho en la fase 1, todos los demás lo esperan: la barrera avanza al ritmo del más lento.
7. Si un hilo nunca llega, los demás quedan bloqueados para siempre.
8. Si la barrera espera 5 hilos pero solo se crean 4, ninguno pasa nunca.
9. Si espera menos hilos de los que se crean, se abre antes de tiempo y los que llegan después forman una nueva «ronda» que quizá nunca se complete.

E1 2025-2 · Pregunta 4 (4 pts): semáforo general con binarios

void semWait(semaphore s) {
    semWaitB(mutex);
    s--;
    if (s < 0) {
        semSignalB(mutex);
        semWaitB(delay);
    } else semSignalB(mutex);
}
void semSignal(semaphore s) {
    semWaitB(mutex);
    s++;
    if (s <= 0) semSignalB(delay);
    semSignalB(mutex);
}

Solución propia (basada en Stallings, problema 5.x)

1) ¿Es una implementación correcta? No. Parece correcta, pero entre semSignalB(mutex) y semWaitB(delay) hay una ventana. Como delay es binario, dos semSignalB(delay) seguidos dejan delay = 1, no 2, y se pierde un despertar.

(Detalle menor: semaphore s se pasa por valor, así que s-- modifica una copia. Debería ser semaphore *s.)

2) Traza con s = 0, delay = 0:

#	Proceso	Acción	s	delay
1	A	semWait: s = -1, suelta mutex, se desaloja antes de semWaitB(delay)	-1	0
2	B	semWait: s = -2, suelta mutex, se desaloja igual	-2	0
3	C	semSignal: s = -1 ≤ 0 → semSignalB(delay)	-1	1
4	D	semSignal: s = 0 ≤ 0 → semSignalB(delay) → se pierde	0	1
5	A	semWaitB(delay) → pasa	0	0
6	B	semWaitB(delay) → bloqueado para siempre, aunque s = 0 dice que no debería esperar	0	0

• La exclusión mutua sobre la variable s sí está garantizada, porque mutex la protege.
• Pero B queda bloqueado indefinidamente sin que nadie vaya a despertarlo: es starvation, o deadlock si todos terminan esperando.

3) Corrección: paso de testigo (baton passing). Quien despierta a otro no suelta mutex; se lo «pasa» al despertado, que lo libera. Así nadie puede ejecutar un segundo semSignalB(delay) antes de que el primero se consuma.

void semWait(semaphore *s) {
    semWaitB(&mutex);
    s->count--;
    if (s->count < 0) {
        semSignalB(&mutex);
        semWaitB(&delay);
        semSignalB(&mutex);      // (nuevo) el despertado libera el mutex heredado
    } else
        semSignalB(&mutex);
}
void semSignal(semaphore *s) {
    semWaitB(&mutex);
    s->count++;
    if (s->count <= 0)
        semSignalB(&delay);      // (cambio) NO libera mutex: lo hereda el despertado
    else
        semSignalB(&mutex);
}

Rehaciendo la traza: en el paso 4, D se bloquea en semWaitB(&mutex) porque C todavía tiene el testigo. A consume delay y libera mutex; D continúa y hace su semSignalB(delay), que ahora B sí consume. Esto funciona porque el semáforo binario, a diferencia de un mutex, puede ser liberado por un proceso distinto al que lo tomó.

Autoevaluación

0/8 correctas · 0 respondidas Reiniciar

1. Un semáforo con count = -3 significa…

a) un errorb) 3 procesos bloqueados en su colac) 3 recursos libresd) que se hicieron 3 signal de más

2. ¿Qué garantiza un semáforo fuerte que uno débil no?

a) Exclusión mutuab) Ausencia de deadlockc) Orden FIFO, así que sin starvationd) Atomicidad

3. Semáforo binario en 1. Se hacen dos semSignalB seguidos. Valor final:

a) 3b) 2c) 1 (el segundo no acumula)d) 0

4. Para que B siempre ejecute y() después de que A ejecute x():

a) s = 1; A: wait(s); x(); B: y(); signal(s)b) s = 0; A: x(); signal(s); B: wait(s); y()c) s = 0; A: wait(s); x(); B: signal(s); y()d) Un mutex basta

5. Mutex vs semáforo binario:

a) Son idénticosb) El mutex tiene dueño: solo quien lo bloqueó puede desbloquearloc) El semáforo binario es más rápidod) El mutex puede valer 2

6. ¿Cuál es FALSA sobre semáforos (según Stallings)?

a) No se sabe antes de semWait si el proceso se bloquearáb) Tras semSignal, el que señala siempre corre primeroc) Al hacer semSignal no se sabe si alguien esperabad) Se inicializan con un valor ≥ 0

7. P0: wait(S); wait(Q). P1: wait(Q); wait(S). S = Q = 1. Puede haber…

a) livelockb) deadlockc) false sharingd) nada

8. La solución a la inversión de prioridad es…

a) deshabilitar interrupcionesb) herencia de prioridadc) más núcleosd) semáforos débiles

Fuente ·Stallings §5.4 (tabla 5.3, figs. 5.6–5.8) · lab2/Sem4_04-OST-Mutex mechanisms.pdf → Resumenes/02 · lab2/07-OSL-Mutex_Locks_Semaphores.pdf → Resumenes/07 · lab2/Sem05_05-OST-Mutex mechanisms monitors.pdf (barreras) · código del curso so/sem4/07_mutex/mutex_sema.c · for_partial/E1_OS_20252.pdf (P4)