Introducción y conceptos básicos

Problemas de sincronización entre procesos

• En un sistema concurrente pueden aparecer diferentes problemas de sincronización:

  • Competencia por recursos no compartibles e.g.: Una impresora.
  • Cooperación compartiendo información. La información se almacena en recursos no compartibles y puede dar lugar a fallos en la coherencia de datos
  • Cooperación mediante paso de mensajes: orden para el envío y recepción de mensajes.

• Necesitamos disponer de reglas de sincronización entre procesos

Tipos de sincronización

Existen dos tipos fundamentales de sincronización:

• Exclusión mutua
  • Garantiza que un recurso no compartible (sección crítica) solo pueda ser usado por un proceso a la vez.
• Serialización o Condición de sincronización:
  • Un proceso debe esperar a que otro modifique el estado de un recurso antes de continuar.

Además, estos mecanismos pueden implementarse de formas distintas:

• Basados en hardware (inhibición de interrupciones, instrucciones atómicas).
• Basados en memoria compartida (espera ocupada, semáforos, regiones críticas, monitores).
• Basados en memoria distribuida (paso de mensajes, RPC, invocaciones remotas).

Exclusión mutua

Definición

• La exclusión mutua es necesaria cuando varios procesos desean utilizar un recurso no compartible (recurso crítico).

• Cuando un proceso está accediendo a este tipo de recursos se dice que está en su sección crítica.

• Ejemplos:

  • Impresora
  • Acceso en modo escritura a una variable global compartida

• Sincronización necesaria cuando los procesos desean utilizar un recurso no compartible

• Cuando un proceso está accediendo a este tipo de recursos se dice que está en su sección crítica

• Ejemplos:

  • Acceso en modo escritura a una variable global compartida

    x = 0
    
    def proceso1():
        global x
        for i in range(1000):
            x = x + 1   # sección crítica
    
    def proceso2():
        global x
        for i in range(1000):
            x = x + 1   # sección crítica
    

  • Una impresora

Protocolos de entrada y salida

• Para garantizar la exclusión mutua, cada proceso debe seguir un protocolo de entrada (antes de acceder a la sección crítica) y un protocolo de salida (al terminar) mediante el cual se sincronice la entrada de los procesos a su sección crítica.

• Esquema general de procesos ejecutando su sección crítica sería:

  while True:
      ...
      cs_entry()          # preprotocolo
      critical_section()
      cs_exit()           # posprotocolo
      ...
  

• Los protocolos de entrada y salida deben ser rápidos y garantizar:

  1. Exclusión mutua: no pueden acceder dos procesos a la vez a la sección crítica
  2. Progreso en la ejecución: si varios procesos desean entrar a la sección crítica al menos uno de ellos debe poder hacerlo
  3. Espera limitada: cualquier proceso debe poder entrar a la sección crítica en un tiempo finito.

Requisitos de Dijkstra

Además, Dijkstra propuso que los protocolos de exclusión mutua deben cumplir:

1. Simetría: la solución debe ser la misma para todos los procesos.
2. Independencia de velocidades: no se pueden hacer suposiciones sobre la velocidad relativa de los procesos ni suponer que éstas son constantes.
3. No interferencia: un proceso que se detiene fuera de su sección crítica no debe bloquear a otros.
4. Decisión finita: La decisión sobre qué proceso debe entrar a la sección crítica debe tomarse en un número finito de pasos.

Variantes

Existen variantes a la exclusión mutua pura:

• Exclusión múltiple: como máximo n procesos pueden estar en su sección crítica a la vez.
• Exclusión mutua por categorías: sólo un tipo de proceso puede estar en la sección crítica a la vez.

  Ejemplo:

  problema lectores/escritores: la presencia de un escritor en la sección crítica excluye a otros escritores y a todos los lectores (la de un lector no excluye a otros lectores)

Problemas derivados

Si los protocolos de entrada y salida no cumplen los requisitos, pueden aparecer problemas típicos en la programación concurrente:

• Condiciones de carrera
  • Ocurren cuando dos o más procesos acceden y modifican un recurso compartido sin sincronización adecuada.
  • El resultado final depende del orden no determinista en el que se intercalen las instrucciones.
• Bloqueo (deadlock)
  • Puede suceder si no se garantiza el progreso: todos los procesos quedan esperando y ninguno entra en la sección crítica.
• Inanición
  • Aparece cuando no se cumple la espera limitada: un proceso puede quedar indefinidamente esperando porque siempre se da prioridad a otros.

Para evitar estos problemas debemos diseñar protocolos para la exclusión mutua

Ejercicio 1

A continuación, se describen varias situaciones. Indica qué requisito/s de Dijkstra se violan en cada caso.

• Dos procesos entran simultáneamente en la sección crítica porque leen una variable de control con valor False al mismo tiempo.
• Un proceso A quiere entrar en la sección crítica, pero debe esperar a que un proceso B lo haga primero; si B nunca quiere entrar, A queda bloqueado indefinidamente.
• Un proceso C quiere entrar en la sección crítica, pero siempre se da prioridad a otros procesos. Aunque C espera, nunca consigue entrar.
• Una solución de exclusión mutua solo funciona si los procesos ejecutan las instrucciones a la misma velocidad. Si uno es más rápido, el protocolo falla.

Serialización de Procesos

• Alguna bibliografía lo llama Condición de sincronización.

• No confundir con el concepto de serialización de datos.

• Consiste en imponer un orden lógico en la ejecución de procesos concurrentes, de modo que una operación solo pueda realizarse cuando el recurso compartido esté en el estado adecuado.

  • Mientras la condición no se cumpla, el proceso debe esperar.
  • Una vez otro proceso cambie el estado del recurso, el proceso bloqueado podrá continuar.

• A diferencia de la exclusión mutua, que evita accesos simultáneos, la serialización asegura que los accesos se produzcan en el momento oportuno.

Ejemplo:

Supongamos tres procesos concurrentes: lector, gestor e impresor.

• El lector deposita imágenes en un buffer de entrada.
  • Si el buffer está lleno, debe esperar antes de añadir más.
• El gestor toma imágenes del buffer y las pasa a una cola de impresión.
  • Si el buffer está vacío, debe esperar a que el lector lo llene.
• El impresor consume imágenes de la cola.
  • Si la cola está vacía, debe esperar a que el gestor la alimente.

Ejercicio 2:

Indica en cada caso si se requiere exclusión mutua, serialización, o ambas.

1. Dos hilos incrementan una variable compartida counter.
2. Varios usuarios intentan mandar documentos a la misma impresora.
3. Un productor quiere poner un ítem en un buffer, pero éste está lleno.
4. Un consumidor quiere leer de un buffer, pero éste está vacío.
5. Un sistema de base de datos permite que múltiples clientes lean la misma tabla, pero solo uno puede actualizarla.
6. Dos hilos acceden en lectura a una variable global que nunca se modifica.
7. Una aplicación de streaming debe reproducir un vídeo después de que el archivo haya sido descargado al buffer.
8. Un sistema de venta de tickets de cine donde se venden tickets para una misma sala en distintas taquillas.

Mecanismos y soluciones cláscias

Para resolver los problemas de concurrencia (exclusión mutua y condiciones de sincronización) se han propuesto diferentes mecanismos a lo largo del tiempo.

Se dividen en 3 categorías:

• Basada en el hardware:
  • Se apoyan en las características del procesador (e.g.: deshabilitar interrupciones, instrucciones atómicas).
  • Fueron de las primeras soluciones, pero presentan limitaciones importantes.
• Basadas en memoria compartida:
  • Utilizan variables y estructuras de datos accesibles por varios procesos.
  • Ejemplos:
    • Espera ocupada
    • Semáforos
    • Regiones críticas
    • Regiones críticas condicionales
    • Monitores
• Basadas en memoria distribuida:
  • Son necesarios cuando no existe memoria compartida.
  • Ejemplos:
    • Paso de mensajes y tuberías
    • Llamadas a procedimientos remotos
    • Invocaciones remotas

Soluciones basadas en el hardware (inhibición de interrupciones)

• La CPU solo cambia de proceso en caso de interrupción.
• Idea: deshabilitar interrupciones al entrar en la sección crítica y habilitarlas al salir.
• Problemas:
  • ¿qué peligro tiene dejar que un proceso de usuario tenga poder de deshabilitar las interrupciones?
  • ¿qué pasa si hay dos o más CPU’s?

Soluciones basadas en memoria compartida

Espera ocupada por exclusión mutua (busy waiting)

• También se denomina espera activa.

• Consiste en que un proceso ocupa la CPU comprobando continuamente el valor de una variable compartida hasta que pueda entrar en su sección crítica.

• Aunque asegura sincronización, consume tiempo de CPU sin hacer trabajo útil.

• Tenemos dos tipos de soluciones:

  • Basadas en hardware: permiten operaciones atómicas más complejas, como intercambiar contenido de dos posiciones de memoria, leer, escribir, etc…
  • Basadas en software: se limitan a opearaciones atómicas simples: load y store.
    • Si dos de estas instrucciones coinciden simultáneamente el resultado sería equivalente a una ejecución secuencial pero en orden desconocido.

• Esquema general:

  # Inicialización de variables globales
  turn = 1
  estados = [0, 0]
  
  # Programa que ejecuta cada proceso
  while True:
      # resto del código
      entry_critical_section()
      critical_section()
      exit_critical_section()
      # resto del código
  

• Soluciones para 2 procesos:

  • Algoritmo de Dekker
  • Algoritmo de Peterson

• Soluciones para n procesos:

  • Algoritmo de Eisenberg-McGuire
  • Algoritmo de Lamport o algoritmo de la panadería
  • Algoritmo rápido de Lamport

• ¡Ojo! Problema con los sistemas multiprocesador modernos

Intentos básicos

Ahora se detallan ejemplos de protocolos fallidos que sirven para motivar algoritmos más correctos.

Primer intento

turn = 0

def proceso0():
    global turn

    while turn != 0:
        pass   # espera ocupada
    critical_section()

    turn = 1

def proceso1():
    global turn

    while turn != 1:
        pass   # espera ocupada
    critical_section()

    turn = 0

• Garantiza la exclusión mutua.
• Provoca que el derecho a usar la sección crítica sea alternativo para los dos procesos: $P_0$, $P_1$, $P_0$, etc.
• No se satisface la condición de progreso en la ejecución pues para que entre $P_0$ tiene que entrar antes $P_1$ y si $P_1$ no lo hace…
• Procesos demasiado acoplados, si uno de los procesos falla el otro se quedará detenido.

Segundo intento

states = [False, False]

def proceso0():
    while states[1]:
        pass

    states[0] = True
    critical_section()
    states[0] = False

def proceso1():
    while states[0]:
        pass

    states[1] = True
    critical_section()
    states[1] = False

• Problema fundamental: no asegura la exclusión mútua

  P0                        P1
  ¿states[1]? → False
                              ¿states[0]? → False
                              states[1] = True
                              ...
  states[0] = True
  ...
                  ## BOOM 💣 ##
  

• Si ambos procesos leen states a la vez y este resulta ser false, ambos entran en la sección crítica.

Tercer intento

states = [False, False]  # resto del codigo

def proceso0():
    states[0] = True
    while states[1]:
        pass

    critical_section()

    states[0] = False

def proceso1():
    states[1] = True
    while states[0]:
        pass

    critical_section()

    states[1] = False

Ejercicio 3

Mostrar una traza de ejecución del tercer intento y ver cómo se llega a un deadlock.

P0                        P1
states[0] = True
                            states[1] = True
                            ¿states[0]? → True
                            ...
¿states[1]? → True
...
                ## DEADLOCK! ☠️🔓 ##

Cuarto intento

states = [False, False]

def proceso0():
    states[0] = True
    while states[1]:
        states[0] = False
        states[0] = True

    critical_section()

    states[0] = False

def proceso1():
    states[1] = True
    while states[0]:
        states[1] = False
        states[1] = True

    critical_section()

    states[1] = False

• Garantiza la exclusión mutua
• No se produce espera ilimitada
• Pero no asegura que se pueda entrar en la sección crítica en un tiempo finito porque los procesos pueden estar continuamente cediéndose el paso para entrar.

Algoritmo de Dekker (1963)

cs_ready = [False, False]
turn = 0
    
def proceso0():
    cs_ready[0] = True
    while cs_ready[1]:
        if turn == 1:
            cs_ready[0] = False
            while turn != 0:
                pass
            cs_ready[0] = True
        
    critical_section()
        
    cs_ready[0] = False
    turn = 1

def proceso1():
    cs_ready[1] = True
    while cs_ready[0]:
        if turn == 0:
            cs_ready[1] = False
            while turn != 1:
                pass
            cs_ready[1] = True
        
    critical_section()
        
    cs_ready[1] = False
    turn = 0

• Mientras el otro proceso también quiera entrar, gana quien tenga el turno; el otro retira su intención y espera a que le llegue su turno.

• Es correcto ya que:

  • Asegura la exclusión mutua: Si ambos quieren entrar, solo entra el que tenga el turno; el otro deja cs_ready en False y espera.
  • Cumple la condición de progreso en la ejecución: si uno no quiere entrar, el otro entra sin bloqueo; y si ambos quieren, el turno resuelve el empate.
  • Satisface la limitación de espera. Al salir se cede el turno al otro, evitando inanición.

• Tiene algunas limitaciones:

• Está orientado a entornos centralizados por la variable turn y a dos procesos

• Es complejo y difícil de escalar para más de dos procesos

Ejercicio 4

Haz una traza para cada caso aplicando el algoritmo de Dekker:

• El proceso 0 está listo para acceder, tiene el turno el proceso 0 y el proceso 1 no está listo para acceder.
• El proceso 0 está no listo para acceder, tiene el turno el proceso 0 y el proceso 1 está listo para acceder.
• El proceso 0 está listo para acceder, tiene el turno el proceso 1 y el proceso 1 no está listo para acceder.
• El proceso 0 está listo para acceder, tiene el turno el proceso 1 y el proceso 1 está listo para acceder.

Ejercicio 5

¿Por qué el algoritmo de Dekker no se puede aplicar a más de dos procesos?

Algoritmo de Peterson (1981)

• Simplifica el de Dekker.
• Mismas variables, cambia el orden de las instrucciones.
• Ahorra unos ciclos de proceso.
• Da por hecho que:
  • Las lecturas concurrentes de una variable son siempre correctas.
  • Si dos procesos P y Q escriben una variable, una de las dos escrituras es correcta que suele ser la última que se llevó a cabo.
  • Si un proceso escribe y otro lee concurrentemente una variable, se lee el valor escrito o el valor previo a la escritura, pero no una mezcla de ambos.

cs_ready = [False, False]

def proceso0():
    cs_ready[0] = True
    turn = 1  # (1)
    while cs_ready[1] and turn == 1:  # (2)
        pass
    
    critical_section()
    
    cs_ready[0] = False

def proceso1():
    cs_ready[1] = True
    turn = 0  # (1)
    while cs_ready[0] and turn == 0:  # (2)
        pass
    
    critical_section()
    
    cs_ready[1] = False

• (1) Cede el turno al otro proceso
• (2) Espera mientras el otro quiera entrar y sea su turno.

Es correcto porque:

• Verifica la exclusión mutua
• Verifica la condición de progreso en la ejecución
• La espera es limitada

Es una solución más sencilla y elegante que Dekker

Ejercicio 6

Haz una traza aplicando el algoritmo de Peterson para un programa en el que dos procesos modifican una variable concurrentemente.

Algoritmo incorrecto de Hyman

states = [False, False]
turn = 0  # 0 ó 1 , es indiferente

def proceso0():
    states[0] = True
    while turn != 0:
        while states[1]:
            pass
        turn = 0

    critical_section()
    
    states[0] = False

def proceso1():
    states[1] = True
    while turn != 1:
        while states[0]:
            pass
        turn = 1

    critical_section()
    
    states[1] = False

• Intuición:

  • Si no es mi turno (turn != 0), miro si el otro quiere entrar (states[1]).
  • Si el otro quiere, espero.
  • Si no, me doy el turno a mí mismo (turn = 0) e intento de nuevo.

• Parece correcto, pero:

  • Hay intercalados donde ambos procesos pueden entrar a la sección crítica a la vez. La razón es que cada uno puede regalarse el turno después de haber comprobado que el otro (en ese instante) no declaraba intención, y ambos pueden reevaluar la condición con su turno propio.

  P0                        P1
                              turn = 1
  turn = 0
                              states[1] = True
                              ¿turn != 1? → True
                              ¿states[0]? → False
  states[0] = True
  ¿turn == 0? → True
                              turn = 1
                              ...
                  ## BOOM! ##
  

• El algoritmo viola el requisito de exclusión mutua. Además, la estrategia de “regalarse” el turno puede producir injusticia (riesgo de inanición) en ciertos intercalados.

Algoritmo de Lamport

• Este algoritmo es adecuado para ejecutarse en entornos distribuidos

• Verifica la exclusión mutua, el progreso de ejecución y no hay espera ilimitada

• También se conoce como Algoritmo de la Panadería

Estructuras de datos utilizadas:

• choosing: Array de valores booleanos.

• choosing[i] = True: Indica que el proceso $P_i$ esta cogiendo numero.

• choosing[i] = False: Indica que el proceso $P_i$ ha terminado de cogerlo.

  Inicialmente todos los choosing[i] = False.

• number: Array de enteros. Cada elemento indica el número que ha cogido el proceso. Inicialmente todas las componentes valen 0.

• El par (choosing[i], number[i]): Pertenece al proceso $P_i$

  choosing = [False, ..., False]  #(1)
  number = [0, ..., 0]
  N = len(number)
  
  def proceso_i(i):
      choosing[i] = True              #(2)
      number[i] = 1 + max(number)
      choosing[i] = False             #(3)
      for j in range(0, N):
          while choosing[j]:            #(4)
              pass
          while ((number[j] > 0) and
              (number[j] < number[i]) or
              (number[j] == number[i]) and (j < i)):
              pass
  
      critical_section()
  
      number[i] = 0
  

• En (1) el array tiene la misma dimensión que number.

• En (2) se indica que está por entrar a la sección de selección de número.

• En (3) se indica que ya acabó la selección.

• En (4) si el proceso j está cogiendo número se le espera porque podría corresponderle el turno.

Nos garantiza que:

• Exclusión mutua: Ya que cuando un proceso $P_i$ está en su sección crítica, éste ha pasado por el segundo while al poseer el número menor o el menor identificador entre los de menor número, y si otro proceso intenta pasar a su sección crítica tendría que cumplir lo mismo, lo que no es posible debido a que el número que extraiga será siempre mayor que el que posee el proceso que está dentro de la sección crítica.

• Progreso en la ejecución: Según el orden en que se toma el número.

• Limitación en la espera: Por la entrada a la sección crítica según el orden.

• Tiene un inconveniente: Los números que cogen los procesos pueden aumentar a lo largo de la ejecución superando la capacidad de cualquier tipo de datos.

Ejercicio 7

¿Por qué crees que el algoritmo de Lamport es apto para entornos distribuídos?

Instrucciones atómicas complejas

Dekker y Peterson son correctos en teoría pero poco prácticos en multiprocesadores modernos: no tienne soporte de memoria en multicore y sufrén de ineficiencia por busy waiting.

En la práctica se emplean primitivas atómicas del hardware y abstracciones de alto nivel implementadas sobre estas.

Un spinlock (candado de espera activa) es un mecanismo de exclusión mutua muy simple en el que un hilo gira (spin) en un bucle comprobando repetidamente si el candado está libre para adquirirlo, en lugar de bloquearse y ceder la CPU. Estos se construyen con primitivas atómicas de hardware

Las operaciones atómicas RMW (read–modify–write) permiten implementar exclusión mutua eficiente en multicore sin recurrir a protocolos frágiles de solo load/store. En CPUs reales existen como instrucciones (p. ej., xchg, lock xchg, cmpxchg en x86) o primitivas del lenguaje (C11 <stdatomic.h>, intrínsecos del compilador).

Primitivas atómicas

• Exchange: Intercambia el contenido de dos posiciones de memoria de forma atómica

  • Spinlock:

    // 0 = libre; 1 = ocupado
    while (xchg(&lock, 1) == 1) { /* spin */ }
    /* --- sección crítica --- */
    xchg(&lock, 0);
    

• Test And Set (TAS): Guarda 1 o true en el parámetro que tiene y devuelve el valor que tenía este parámetro originalmente:

  bool test_and_set(bool* p) {
      bool old_p = *p;
      *p = true;
      return *old_p;
  }
  

  • Spinlock:

    // lock == 1 significa que NO podemos entrar en la s.c.
    //         el candado esta cerrado.
    while (test_and_set(&lock));
        critical_section();
    lock = false;
    

• CompareAndSwap: Compara el contenido de una posición de memoria con un valor dado y, sólo si es el mismo, modifica el valor de la memoria por un nuevo valor dado

  bool compare_and_swap(int* value, int expected, int new_v) {
      int tmp = *value;
  
      if (*value == expected)
          *value = new_v;
  
      return tmp;
  }
  

  • Spinlock:

    // lock == 0 significa que SI podemos entrar en la s.c.
    //         el candado esta abierto.
    while (compare_and_swap(&lock, 0, 1) != 0);
        critical_section();
    lock = 0;
    

Conclusiones

• La solución basada en espera activa satisface la exclusión mutua, junto con las condiciones de no inanición y progreso de la ejecución.

• Sin embargo, 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.
  • No funcionan en los sistemas multiprocesador modernos (los modelos eficientes de consistencia de memoria no garantizan el reordenamiento adecuado de los accesos a memoria)
  • Para tratar estos problemas se puede recurrir a las barreras de memoria o al uso de primitivas hardware (instrucciones específicas para tratar la concurrencia en ensamblador)

Anexo: memoria compartida en Unix/System V

• Con pseudocódigo utilizar variables compartidas es tan sencillo como declararlas como variables globales.
• En general, con procesos, en la vida real, las cosas no son tan sencillas…

Ejemplos en Unix

• Veamos el código de los programas:
  • indeterminismo.c (System V)
  • Dekker_con_procesos.c (System V)
  • counter_peterson.c (barreras gcc)
  • exchange.c (ensamblador e hilos posix)
• En GNU/Linux se puede simular un sistema monoprocesador con la instrucción taskset (man taskset)

Ejercicio:

Contesta las siguientes cuestiones:

• Indicar las condiciones exigidas por los protocolos de E/S a una correcta solución al problema de la exclusión mutua.
• Formular varios problemas donde se requieran condiciones de sincronización.
• ¿A qué hace referencia el término espera ocupada?
• ¿Cuál es el principal inconveniente de las soluciones basadas en espera ocupada?
• Explicar por qué el algoritmo de Lamport no presenta espera ilimitada.

Ejercicio:

Discute la corrección del algoritmo de exclusión mutua siguiente (si es incorrecto encuentra una traza que viole la exclusión mutua, si es correcto pruébalo):

states = [1, 1]
   
states[0] = 1 - states[1]
while states[1] != 0:
    states[0] = 1 - states[1]
    
critical_section()
    
states[0] = 1

Lo mismo con el algoritmo:

states = [1, 1]

states[0] = 0
while states[1] == 0:
    states[0] = 1
    while states[1] == 0:
        pass
    states[0] = 0

critical_section()

states[0] = 1

Ejercicio

Adapta al código del programa counter.py del tema 2 de modo que satisfaga la exclusión mutua en el acceso a la variable compartida counter mediante el algoritmo de Peterson

import threading

THREADS = 2
MAX_COUNT = 10000000

counter = 0

def thread():
  global counter

  print("Thread {}".format(threading.current_thread().name))

  for i in range(MAX_COUNT//THREADS):
    counter += 1

def main():
  threads = []

  print("Starting...")

  for i in range(THREADS):
    # Create new threads
    t = threading.Thread(target=thread)
    threads.append(t)
    t.start() # start the thread

  # Wait for all threads to complete
  for t in threads:
    t.join()

  print("Counter value: {} Expected: {}\n".format(counter, MAX_COUNT))

if __name__ == "__main__":
  main()

Aclaraciones

• 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.