Tema 4. Semáforos

• Problemas de la espera ocupada
  • La espera activa es ineficiente
    • Los procesos ocupan el procesador incluso aunque no puedan avanzar
• El uso de variables compartidas genera esquemas:
  • Demasiado complejos
  • Muy artificiales
  • Propensos a errores: No hay una separación entre las variables de los cómputos de los procesos y las utilizadas para sincronización.
  • Inadecuados para grandes esquemas de protección.
  • Fuertemente acoplados: los procesos deben de saber unos de otros.

• Los semáforos son señales simples que pueden obligar a un proceso a detenerse en una posición determinada.
• Con la estructura adecuada de señales podemos satisfacer cualquier requisito de coordinación.
• Los semáforos se usan como mecanismo de sincronización entre procesos.
• Los procesos se bloquean o ejecutan condicionados únicamente por el valor de una variable entera

struct Semaphore {
     unsigned value;
     Queue q;
}

• Es un TAD formado por un valor numérico y una cola de procesos bloqueados.
• Fueron inventados por Edsger Dijkstra (1965) y se usaron por primera vez en el sistema operativo THEOS (1974). En este otro enlace puedes ver un poco más de la intrahistoria de THEOS.
• Un semáforo bloquea un proceso cuando éste no puede realizar la operación deseada, en vez de desperdiciar tiempo de CPU.
• Pseudocódigo para inicializar a 1: Semaphore s = 1

Operaciones sobre semáforos

• P: del holandés "proberen te verlagen" (intentar decrementar). Si el contador es mayor que 0 lo decrementa, en caso contrario bloquea el proceso que lo llamó.

  Más conocida como wait, acquire o lock.

• V: del holandés "verhoog" (incrementar). Si hay algún proceso bloqueado en el semáforo, lo desbloquea, en caso contario, incrementa el valor de la variable.

  Más conocida como signal, release o post.

1: def wait(s):
2:    if s.value > 0:
3:      s.value -= 1                   (1)
4:    else:
5:         add(process, s.queue)
6:         block(process)              (2)

• En (1) si es mayor que 0, se decrementa el valor del semáforo
• En (2) si es 0, se bloquea el proceso que llamó a wait

1: def signal(s):
2:    if empty(s.queue):
3:      s.value += 1           (1)
4:    else:
5:      process = get(s.queue)
6:      sched(process)         (2)

• En (1) si no hay procesos bloqueados en la cola del semáforo, se incrementa su valor
• En (2), en caso contrario, se desbloquea a un proceso

• Otras operaciones que dependen de la implementación concreta:
  • Asignar un valor al semáforo
  • Obtener el valor del semáforo
  • Intentar wait sólo si no produce bloqueo del proceso (try_lock)
  • Elección de la política de desbloqueo de procesos
  • …

• La definición de un semáforo implica la exclusión mutua en la ejecución de las operaciones por él definidas

  Esta exclusión mutua se consigue mediante funciones proporcionadas por el sistema operativo (típicamente espera con bloqueo)

• Los semáforos son una herramienta para resolver problemas tanto de exclusión mutua como de sincronización.

  Exclusión mutua:

  sólo uno de los procesos debe estar en la sección crítica en un instante dado.

  Sincronización:

  un proceso debe esperar la ocurrencia de un evento para poder seguir ejecutándose.

1: Semaphore s = 1
2: ...
3: s.wait()
4: critical_section()
5: s.signal()
6: ...

• Cuando el primer proceso entre a la sección crítica decrementará su valor y continuará.
• Si otro proceso desea entrar, value será cero, por lo que se bloqueará hasta que el primero ejecute signal.
• Veamos los programas semaphore.c y semaphore.py
• En java también hay semáforos, pero no se suelen utilizar si no se está portando código de otros lenguajes.

Semáforos binarios optimizados para exclusión mutua

• Inicializados a 1 por defecto
• Sólo el proceso que hizo wait puede hacer signal. Esto es una diferencia fundamental con los semáforos.
• Algunos sistemas permiten que el mismo hilo haga varios wait, si ya es propietario del lock continúa su ejecución. Se denominan reentrantes.

1: Mutex mutex
2: ...
3: mutex.lock()
4: critical_section()
5: mutex.unlock()
6: ...

• En C los mutex están en la biblioteca POSIX Threads y no son reentrantes (mutex.c).
• En Python tenemos threading.Lock (no reentrante) y threading.Rlock (reentrante). Se pueden usar también con la cláusula with (programas lock.py y lock_with.py).
• En la biblioteca estándar de C++ tenemos mutex, thread, condition variable, etc…
• En D tenemos la parte de bajo nivel de su biblioteca estándar core.sync (mutex, semaphore, condition, etc…) y otros componentes de alto nivel como: std.parallelism o std.process.
• En Vala tenemos un API orientado a objetos sobre GLib (Mutex, Thread).
• En la biblioteca estándar de rust disponemos de hilos y primitivas de sincronización (mutex, condvar, etc…), pero no de semáforos. En éste último caso hemos de recurrir a bibliotecas externas.

• Si nuestra aplicación se compone de un sólo proceso con múltiples hilos, la biblioteca pthread.h proporciona mutex (semáforos binarios para hilos).

   1: #include<pthread.h>
   2: 
   3: pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
   4: 
   5: // inicializar con los atributos por defecto
   6: int pthread_mutex_init (...)    // para otras inicializaciones
   7: int pthread_mutex_destroy(...)  // destruir el candado
   8: int pthread_mutex_lock(...)     // bloquear candado o espera si bloqueado
   9: int pthread_mutex_trylock(...); // bloquear candado y no espera si bloqueado
  10: int pthread_mutex_unlock(...)   // desbloquear candado
  11: ...
  12: 
  13: // Declaración de los datos compartidos y del candado que los protege
  14: 
  15: struct datos_compartidos {
  16:    declaración de los datos
  17:    pthread_mutex_t candado;
  18: } datos;
  19: ...
  20: void codigo_hilo(void *arg){
  21:    ...
  22:    pthread_mutex_lock(&datos.candado);
  23:    // seccion critica
  24:    pthread_mutex_unlock(&datos.candado);
  25:    ...
  26: }
  27: 
  28: void main(){
  29:    pthread_t hilo_1, hilo_2;
  30:    int error;
  31:    ...
  32:    // Inicializacion del candado
  33:    error = pthread_mutex_init (&datos.candado, NULL);
  34:    //pthread_mutex_t datos.candado = PTHREAD_MUTEX_INITIALIZER;
  35:    if (error)
  36:       // tratamiento del error
  37: 
  38:    // Creación de los hilos
  39:    error = pthread_create(&hilo_1, NULL, codigo_hilo, NULL);
  40:    if (error)
  41:       // tratamiento del error
  42:    error = pthread_create(&hilo_1, NULL, codigo_hilo, NULL);
  43:    if (error)
  44:       // tratamiento del error
  45:    ...
  46: }
  

• El valor del semáforo puede interpretarse como un indicador del número de recursos disponibles (permits).
• Indica el número de llamadas que se pueden hacer a wait sin provocar bloqueo.
• En exclusión mutua debe ser 1. En este caso reciben el nombre de semáforos binarios.
• Mecanismos más complejos requieren otros valores (por ejemplo, un número máximo de procesos, de impresoras, de procesadores, … ). Se denominan multiplexes.

• Sirve para simular semáforos generales con semáforos binarios

 1:   BinarySemaphore mutex = 1
 2:   BinarySemaphore gate = 1
 3:   value = k
 4: 
 5:   def generalWait():
 6:        gate.wait()       # si no es el primero debe esperar
 7:        mutex.wait()
 8:        value -= 1
 9:        if value > 0:
10:           gate.signal()  # permite que entre otro si el valor es positivo
11:        mutex.signal()
12: 
13:   def generalSignal():
14:        mutex.wait()
15:        value += 1
16:        if value == 1:
17:           gate.signal()  # antes estaba en cero, permite que entre otro
18:        mutex.signal()

• Se asocia un semáforo general a cada condición.
• Un proceso espera a que una condición se cumpla ejecutando -en principio- una operación wait.
• Cuando un proceso ha hecho que se cumpla una determinada condición, lo indica ejecutando un signal sobre dicho semáforo.

• Ejemplo de 2 procesos concurrentes donde Q no puede ejecutar Q₂ hasta que P haya ejecutado P₁. ¿Qué haríais?
  • ¿Cuántos semáforos utilizaríais y a qué los inicializaríais?

  • ¿Dónde pondríais las operaciones wait() y signal() de cada semáforo?

    P             Q
    ...           ...
    P1            Q1
    P2            Q2
    ...           ...
    

La solución usando un semáforo con valor inicial 0

   Semaphore sync = 0
P                Q
...              ...
P1               Q1
sync.signal()    sync.wait()
P2               Q2
...              ...

• Ejemplo de 2 procesos concurrentes donde ambos procesos deben esperarse en el punto 1
  • ¿Cuántos semáforos utilizaríais y a qué los inicializaríais?

  • ¿Dónde pondríais las operaciones wait() y signal() de cada semáforo?

    P             Q
    ...           ...
    P1            Q1
    (1)           (1)
    P2            Q2
    ...           ...
    

La solución usando dos semáforos s y t con valores iniciales 0

   Semaphore s = 0
   Semaphore t = 0
P                Q
...              ...
P1               Q1
s.signal()       t.signal()
t.wait()         s.wait()
P2               Q2
...              ...

• Ejemplo de 3 procesos concurrentes donde Q solo puede pasar a ejecutar Q2 si R ha ejecutado R1 o P ha ejecutado P1

  P             Q             R
  ...           ...           ...
  P1            Q1            R1
  P2            Q2            R2
  ...           ...           ...
  

La solución utilizando un semáforo con valor inicial 0

   Semaphore sync = 0
P                Q             R
...              ...           ...
P1               Q1            R1
sync.signal()    sync.wait()   sync.signal()
P2               Q2            R2
...              ...           ...

• Ejemplo de 3 procesos concurrentes donde Q solo ejecuta Q2 si R ha ejecutado R1 y P ha ejecutado P1

  P             Q             R
  ...           ...           ...
  P1            Q1            R1
  P2            Q2            R2
  ...           ...           ...
  

Solución 1: ¿Es correcta?

   Semaphore sync = 0
P                Q             R
...              ...           ...
P1               Q1            R1
sync.signal()    sync.wait()   sync.signal()
P2               sync.wait()   R2
...              Q2            ...
                 ...

Solución 2: Usar dos semáforos s y t con valor inicial 0

• Implica dos sincronizaciones: de P y Q por un lado y Q y R por otro.

     Semaphore s = 0
     Semaphore t = 0
  P                Q             R
  ...              ...           ...
  P1               Q1            R1
  s.signal()       s.wait()      t.signal()
  P2               t.wait()      R2
  ...              Q2            ...
                   ...
  

• Los casos anteriores son ejemplos de barreras de sincronización, los programas concurrentes se sincronizan por fases: todos los procesos deben esperar que termine la fase actual para comenzar simultáneamente la siguiente.
• Cuando el número de procesos es pequeño basta con utilizar un semáforo por cada punto de espera
• Cuando aumenta el número de procesos esta solución es altamente ineficiente por el coste de los semáforos

• El problema general se puede representar mediante sincronizaciones cíclicas del tipo:

  1:     while True:
  2:        do_phase()
  3:        barrier(n)
  

• Y se puede solucionar con dos semáforos y un contador con actualización atómica
• Si no se dispone de este tipo de contador se necesita además un candado
• Algunos lenguajes implementan, o están en proceso de implementar, este tipo de barreras.

 1: Semaphore arrival = 1
 2: Semaphore departure = 0
 3: counter = 0
 4: 
 5: def barrier(n):
 6:        arrival.wait()
 7:        getAndAdd(counter, 1)
 8:        if counter < n:
 9:            arrival.signal()   (1)
10:        else:
11:            departure.signal() (2)
12: 
13:        departure.wait()       (3)
14: 
15:        getAndAdd(counter, -1)
16:        if counter > 0:
17:            departure.signal() (4)
18:        else:
19:            arrival.signal()   (5)

• En (1) si no llegaron todos los procesos, permite la llegada de otro
• En (2) si llegaron todos, autoriza la salida de un proceso
• En (3) espera la autorización para continuar
• En (4) si no salieron todos, autoriza la salida del siguiente
• En (5) si llegaron todos, comienza nuevamente el ciclo de llegadas
• Veamos cómo queda el código completo (barrier.py)

Fuertes:

la cola de procesos sigue una política FIFO estricta

Débiles:

si los procesos se seleccionan aleatoriamente

• Se compone de los siguientes elementos:
  • El valor del semáforo
  • El identificador del último proceso que lo manipuló
  • El número de procesos que hay esperando a que el valor del semáforo se incremente
  • El número de procesos que hay esperando a que el semáforo tome el valor 0
• Ejemplos de código sem-1.c y sinSem-1.c

• Debemos incluir la cabecera semaphore.h
• Estándar relativamente reciente (1993)
• Utiliza funciones clásicas sobre semáforos
• El tipo del semáforo es sem_t y almacena toda la información relativa al semáforo
• Dos tipos:

  Semáforos nominales :

  para sincronizar procesos no relacionados. Tienen asociado un nombre en la jerarquía del sistema de ficheros

  Semáforos anónimos :

  para sincronizar procesos de una misma jerarquía o hilos de un mismo proceso

• Veamos el código de semPosix.c y de buffer-circular-hilos.c

• Si los semáforos residen en la memoria compartida y por tanto hay que acceder a ellos en exclusión mutua, ¿no es la pescadilla que se muerde la cola?
• En algún momento habrá que recurrir a mecanismos de más bajo nivel…
• ¿Cuál pensáis entonces que es la ventaja fundamental de los semáforos?

Espera ocupada :

protocolo entrada espera ocupada
Sección Crítica (código usuario, duración no definida)
protocolo salida espera ocupada

Semáforo :

protocolo entrada espera ocupada
sección crítica wait (corta)
protocolo salida espera ocupada

sección crítica (código usuario)

protocolo entrada espera ocupada
sección crítica signal(corta)
protocolo salida espera ocupada

• Productor-consumidor
• Lectores-escritores
• Comida de los filósofos

• En ningún caso estas transparencias son la bibliografía de la asignatura, por lo tanto debes estudiar, aclarar y ampliar los conceptos que en ellas encuentres empleando los enlaces web y bibliografía recomendada que puedes consultar en la página web de la ficha de la asignatura y en la web propia de la asignatura.