Tema 3. Primeras aproximaciones a la Programación Concurrente

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

• Garantizar la exclusión mutua en la ejecución de secciones críticas consiste en diseñar un protocolo de entrada y uno de salida mediante el cual se sincronice la entrada de los procesos a su sección crítica.
• Los protocolos de E/S en la sección crítica deben cumplir:
  • En la exclusión mutua pura sólo un proceso puede estar en un determinado momento en su sección crítica
  • Cuando un proceso sale de la sección crítica debe permitir pasar a otro proceso que estaba esperando para acceder a la misma
  • Por tanto cuando un proceso quiera entrar en su sección crítica y ésta esté libre, podrá hacerlo

• Un esquema de procesos ejecutando su sección crítica sería:

1: while forever:
2:   # resto del codigo
3:   cs_entry()          # preprotocolo
4:   critical_section()
5:   cs_exit()           # posprotocolo
6:   # resto del codigo

• 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

• Además son deseables los cuatro requisitos de Dijkstra:
  1. La solución debe ser simétrica, la misma para todos los procesos.
  2. No se deben hacer suposiciones sobre la velocidad relativa de los procesos ni suponer que éstas son constantes.
  3. Entrada inmediata o no interferencia, si un proceso se interrumpe en el resto del código no debe bloquear a otros procesos.
  4. La decisión sobre qué proceso debe entrar a la sección crítica debe tomarse en un número finito de pasos

• Existen variantes a la exclusión mutua ‘pura’:

  Exclusión múltiple:

  como mucho n procesos pueden estar en su sección crítica a la vez

  Exclusión mutua por categorías:

  en un momento determinado sólo un tipo de proceso puede estar en la sección crítica p.e. 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)

• Alguna bibliografía lo llama: Condición de sincronización.
• Se produce cuando un objeto de datos compartido está en un estado inapropiado para ejecutar una operación determinada.
• Cualquier proceso que intente ejecutar esta operación debe ser retrasado hasta que el estado del dato cambie porque otro proceso haya emprendido una acción determinada
• Ejemplo: procesos lector, gestor e impresor.
  • El lector no podrá depositar una imagen en el buffer de entrada compartido si este está lleno.
  • El gestor no podrá tomar una imagen si el buffer está vacío, etc.

• Tenemos que garantizar la indivisibilidad de una secuencia de acciones
• Como la CPU sólo pasa de un proceso a otro como resultado de una interrupción (de reloj u otras) podemos deshabilitarlas antes de entrar en la sección crítica y habilitarlas al salir de la misma
• 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?

• El proceso espera mediante la comprobación continua del valor de una variable compartida, manteniendo ocupada la CPU.
• Podemos tener 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: las únicas operaciones atómicas son load y store para leer y escribir en direcciones de memoria. Si dos de estas instrucciones coinciden simultáneamente el resultado sería equivalente a una ejecución secuencial pero en orden desconocido.

• El esquema general de esta solución sería el siguiente:

  • Inicialización de variables globales

    turn = 1
    estados = [0, 0]
    

  • Programa que ejecuta cada proceso

    1: while True:
    2:   # resto del código
    3:   #
    4:   entry_critical_section()
    5:   critical_section()
    6:   exit_critical_section()
    7:   #
    8:   # resto del código
    

• Soluciones para 2 procesos:
  • Primeros intentos
  • 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

1: turn = 0
2: 
3: # Busy waiting ... SpinLocks
4: while turn != 0:
5:   pass
6: 
7: critical_section()
8: 
9: turn = 1

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

1: states = [False, False] # is_in[False, False]
2: 
3: while states[1]:
4:   pass
5: states[0] = True
6: 
7: critical_section()
8: 
9: states[0] = 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 ##

1: states = [False, False]  # resto del codigo
2: 
3: states[0] = True
4: while states[1]:
5:   pass
6: 
7: critical_section()
8: 
9: states[0] = False

• Problema: posible interbloqueo

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

 1: states = [False, False]  # resto del codigo
 2: 
 3: states[0] = True
 4: while states[1]:
 5:   states[0] = False
 6:   states[0] = True
 7: 
 8: critical_section()
 9: 
10: states[0] = 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.

 1:   cs_ready = [False, False]
 2:   turn = 0                # 0 ó 1 , es indiferente
 3: 
 4:   cs_ready[0] = True
 5:   while cs_ready[1]:
 6:     if turn == 1:
 7:       cs_ready[0] = False
 8:       while turn != 0:  # (1)
 9:         pass
10:       cs_ready[0] = True
11: 
12:   critical_section()
13: 
14:   cs_ready[0] = False
15:   turn = 1              # (2)

• En (1) P₀ espera si no es su turno, su estado se mantendrá en falso y P₁ podrá entrar a la sección crítica
• En (2) cuando un proceso sale de su sección crítica cede el turno al otro

• Es correcto ya que:
  • Asegura la exclusión mutua
  • Cumple la condición de progreso en la ejecución
  • Satisface la limitación de espera
• Está orientado a entornos centralizados por la variable turn y a dos procesos
• Problema: es complejo y difícil de seguir para más de dos procesos

• Simplifica el de Dekker, más sencillo de entender.
• 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.

 1:   cs_ready = [False, False]
 2: 
 3:   cs_ready[i] = True
 4:   turn = j                          # (1)
 5:   while cs_ready[j] and turn == j:  # (2)
 6:     pass
 7: 
 8:   critical_section()
 9: 
10:   cs_ready[i] = False
11: 
12:   # Resto del codigo

• En (1) cede el turno al otro proceso
• En (2) espera si el estado del otro es True y es su turno

• Verifica la exclusión mutua
• Verifica la condición de progreso en la ejecución
• La espera es limitada
• Solución más sencilla y elegante que Dekker

 1: states = [False, False]
 2: turn = 0    # 0 ó 1 , es indiferente
 3: 
 4: states[0] = True
 5: while turn != 0:
 6:   while states[1]:
 7:     pass
 8:   turn = 0
 9: 
10: critical_section()
11: 
12: states[0] = False

• Parece correcto, pero fíjate:

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

• 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

 1: choosing = [False, ..., False]  #(1)
 2: number = [0, ..., 0]
 3: choosing[i] = True              #(2)
 4: number[i] = 1 + max(number)
 5: choosing[i] = False             #(3)
 6: for j in range(0,N):
 7:   while choosing[j]:            #(4)
 8:      pass
 9:   while ((number[j] > 0) and
10:          (number[j] < number[i]) or
11:          (number[j] == number[i]) and (j < i)):
12:      pass
13: 
14: critical_section()
15: 
16: 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.