Semáforos
Semáforos
Primitiva de Sincronización propuesta por Dijkstra en 1968
Como parte de sistema THE
Usados para exclusión mutua y planificación
De nivel más alto que locks
Variable atómica manipulada por dos operaciones
Wait(semaforo)
• Decrementa semáforo
• Bloquea hebra/proceso si el semáforo es menor que cero, sino
entonces permite a hebra/proceso continuar
• Operacion tambien llamada P(semaforo) o down(semaforo)
Signal(semáforo)
• Incrementa semáforo en uno y si hay algún proceso/hebra
esperando lo despierta
• También llamada V(semaforo) o up(semaforo)
Valor de semáforo puede ser mayor que 1
• Inicializado en 1 es como lock.
• Usado para exclusión mutua
• Inicializado en N
• Usado como contador atómico
Exclusión mutua vs planificación
Exclusión mutua
- Sólo una hebra a
lock
la vez en Sección Sección crítica
Critica. unlock
- Puede ser cualquier
hebra
Planificación
- Requerimiento de
orden en ejecución de
hebras.
tiempo
Ejemplo planificación
tiempo
H1. imprime A
sem S1 = 0, S2 = 0 H2. imprime B
H1: H2: H3:
print A; wait(S1); wait(S2); H3. imprime C
signal(S1); print B; print C;
signal(S2);
Tipos de Semáforos
Binarios (mutex)
Garantizan exclusión mutua a recurso
Sólo una hebra/proceso puede accesar sección crítica a
la vez
Contador de semáforo inicializado en 1
Contadores
Representan recursos con más de una unidad disponible
Permiten accesar recursos de acuerdo al número de
recursos disponibles
Contador es inicializado en N, donde N es la cantidad de
unidades disponibles del recurso
Ejemplos Clásicos de Sincronización
Problema Productor/Consumidor
Un buffer en memoria con N slots disponibles
• Necesita llevar cuenta de ítemes en buffer
Productor produce ítemes a ingresar al buffer
Consumidor consume ítemes del buffer
P C
Productor Consumidor
Agrega item Remueve item
usando puntero in usando puntero
out
out in
Cómo resolver problema?
Identificar restricciones inherentes al
problema
Estado compartido?
• contador (consumidores y productores)
• Buffer
• in ( productores) . Productores no pueden insertar en
buffer lleno
• out ( consumidores). Consumidores no pueden extraer
de buffer vacío
Posible resolver con locks? Si
Posible resolver con semáforos? Si
Cómo resolver problema?
Identificar estado compartido y
restricciones de problema
Buffer de tamaño limitado compartido entre productores
y consumidores
Productor escribe en buffer[in], in indica posición de
escritura en buffer
Consumidor extrae de buffer[out], out indica posición de
extracción de buffer
Contador indica el número de elementos actuales en el
buffer
Múltiples productores deben manipular in, buffer[in] y
contador atómicamente.
Múltiples consumidores deben manipular out, buffer[out]
y contador atómicamente
Múltiples consumidores y productores deben manejar
contador atómicamente
Solución a Productor/Consumidor
usando semáforos
Identificar estado compartido y restricciones de
problema
Ya presentadas
Especificar condiciones de espera y señalización
Cuando buffer está lleno productores deben esperar a que exista una
posición vacía (generada por un consumidor)
Cuando buffer esta vacío consumidores deben esperar a que exista un
elemento en el buffer (generado por un productor)
Acceso a buffer y contador debe realizarse atómicamente
Identificar semáforos para proveer sincronización
Mutex (inicializado en 1): para exclusión mutua de buffer, in, out y contador.
Full (inicializado en 0). Para indicar cuántas posiciones llenas hay en el buffer
Empty (inicializado en N). Para indicar cuantas posiciones vacías hay en el
buffer
Proporcionar algoritmos
Problema lectores/escritor
Caso base de datos
Varios lectores pueden accesar registro
datos simultaneamente
Sólo un escritor puede escribir
L
E
Registro BD
L
Cómo resolver problema?
Identificar estado compartido y restricciones de problema
Base de datos compartida
• Mientras haya un lector un escritor no puede accesar base de
datos
• Mientras exista un escritor en base de datos ningún otro escritor
o lector puede accesarla
Identificar condiciones de espera y señalización
Si existe un escritor en BD otro escritor o lector debe esperar
Cuando un escritor termina debe señalizar escritor o lector
que espera
Si podemos tener varios lectores debemos contarlos, para
saber cuando existe uno
• Si hay uno leyendo y llegan otros, otros tambien pueden leer
• Si solo hay uno y sale puede haber un escritor esperando
accesar BD
Qué semáforos necesitamos
Uno inicializado en 1 como mutex para manejar contador de
lectores
Uno tipo mutex para escritor y primer lector
Notas sobre Lectores/Escritores
Primer lector se bloquea si hay un escritor activo
cualquier otro escritor se bloquea también
Si un escritor espera porque existen lectores activos,
el último lector lo despierta cuando sale
pueden otros lectores entrar cuando el escritor está
esperando?
Cuando un escritor sale, si hay un escritor y un lector
esperando quien entra?
Otro ejemplo clásico
Problema de Filósofos comensales
Cada filósofo tiene su plato de arroz, con 5 palitos
5 filósofos se sientan a la mesa. Piensan por un rato
y cuando les da hambre comen
Hay sólo 5 palitos en la mesa (cada persona necesita
2 palitos para comer arroz a la manera china)
Para poder comer cada filósofo tiene que
obligatoriamente conseguir dos palitos
Problema es importante porque introduce
posibles problemas de Deadlock(bloqueo
mortal) y Starvation(inanición)
Problema de Filósofos comensales
Problemas que pueden surgir con
mala sincronización
Deadlock
Hebras/Procesos están en deadlock cuando
• 2 o más hebras o procesos están esperando por una
condición que sólo puede ser causada por una hebra que
tambien está esperando.
• Puede darse con 2 o más hebras en la lista de espera de
un mismo semáforo?
Starvation o espera indefinida
Hebras/Procesos esperan indefinidamente para poder
accesar un recurso.
• Ejemplo, una hebra en la lista de espera de un semáforo de
la cual están entrando y saliendo continuamente hebras y
la lista de espera de semáforo es LIFO
Problemas con Semáforos
A pesar que se pueden usar para resolver cualquier
problema de sincronización
Son variables globales por lo tanto pueden ser
accesadas de cualquier hebra directamente
• no es buena técnica de ingeniería de software
No hay conexión entre el semáforo y el recurso para el
cual se quiere controlar acceso
Usados como mutex (ingreso a sección crítica) y para
coordinación (planificación, elección quien tiene acceso
al recurso)
No se puede controlar su uso, no hay garantía que el
programador los use adecuadamente (fácil de cometer
errores)
Resumen
Semáforos primitivas de sincronización de
más alto nivel que locks
No relación entre semáforo y recurso que
controla
Fácil de cometer errores que pueden
producir deadlock y starvation
Importante entender bien problema antes de
utilizarlos
