Tema 6. Monitores

• Basada en los trabajos de investigación de Per Brinch Hansen aparece la idea de Monitor como una entidad que resuelve las pegas anteriores.
• Los Monitores formaron parte de un proyecto más complejo que fue el desarrollo de un lenguaje de programación pensado para la Programación Concurrente. Este lenguaje se llama Concurrent Pascal.
• En Concurrent Pascal se incluyen los tipos de datos de clase, monitor y proceso.

• Las clases y los monitores son parecidos:
  • Ambos empaquetan variables privadas y procedimientos con procedimientos públicos (llamados entradas de procedimiento).
  • Una instancia de clase solo puede ser utilizada por un proceso.
  • Una instancia de monitor puede ser compartida por varios procesos.
• Los monitores proporcionan el único mecanismo para la comunicación entre procesos
• Hoy en día podríamos comparar los Monitores con una clase con métodos sincronizados de Java.

• Semáforos:
  • Recursos globales
  • Código disperso por los procesos
  • Las operaciones sobre los recursos no están restringidas
• Monitores:
  • Recursos locales
  • Código concentrado
  • Los procesos invocan los procedimientos públicos

• Delay(c) → Bloqueo de procesos:
  • Bloquea el proceso que realiza la llamada al final de la cola asociada a la variable condición c
  • Libera la exclusión mutua antes de bloquearse
• Resume(c) → Desbloqueo de procesos:
  • Extrae el proceso que se encuentra en la cabeza de la cola y lo prepara para su ejecución
  • Cola vacía: operación nula (null)
• Empty(c) → Comprobación de la cola:
  • Devuelve un valor booleano indicando si la cola de la variable condición está vacía o no

Variables de condición

• Si un proceso ejecutando un procedimiento de un monitor invoca una operación delay(c), libera el monitor y se bloquea en la cola asociada a esa variable de condición.
• Cuando un proceso ejecutando un procedimiento de un monitor invoca una operación resume(c), se analiza la cola asociada a esa variable de condición, seleccionando al primer proceso bloqueado en ella. Si no hubiese procesos bloqueados la operación no tendrá efecto.
• ¿Qué pasa si se desbloquea a un proceso? ¿Hay entonces 2 procesos ejecutando en el monitor?: Distintos lenguajes implementan distintos comportamientos (políticas) para la función resume.

Hay tres alternativas habituales:

• Requerimiento de reanudación inmediata (IRR): el proceso bloqueado en la variable condición se debe reanudar inmediatamente:
  • El proceso que señaliza (S) se bloquea inmediatamente y cede el monitor
  • La mayor prioridad la tiene el proceso bloqueado en la condición señalizada (W)
  • Los bloqueados en la entrada del monitor (E) deben esperar
  • Abreviadamente: E \(<\) S \(<\) W
• El proceso S acaba y sale del monitor, luego los procesos bloqueados en la condición (W) y finalmente los procesos de la entrada (E):
  • Abreviadamente: E \(<\) W \(<\) S
• La "opción Java":
  • Abreviadamente: E = W \(<\) S

• Monitores con Python:

 1:     mutex = threading.Lock()
 2:     allArrived = threading.Condition(mutex)
 3:     arrived = 0
 4: 
 5:     def barrier(n):
 6:          with mutex:
 7:               arrived += 1
 8:               if arrived == n:
 9:                    arrived = 0
10:                    allArrived.notify_all()
11:               else:
12:                    allArrived.wait()

• Código completo: barrier.py

• Código completo: producer-consumer.py

   1:     # Productor
   2: 
   3:     def append(self, data):
   4:          with mutex:
   5:               while len(buffer) == buffer.maxlen:
   6:                    untilNotFull.wait()     # condición buffer no lleno
   7:               buffer.append(data)
   8:               whileEmpty.notify()
   9: 
  10:     # Consumidor
  11: 
  12:     def take(self):
  13:          with mutex:
  14:               while not buffer:
  15:                    whileEmpty.wait()    # condición buffer no vacío
  16:               data = buffer.popleft() # extrae el primero de la lista
  17:               untilNotFull.notify()
  18:               return data
  

• Código completo: rw_lock.py

   1:     # Lectores
   2: 
   3:     def reader_lock():
   4:          with mutex:
   5:               while writing:
   6:                    canRead.wait()    # condición hay escritores
   7:               readers += 1
   8:               canRead.notify()       # pueden entrar otros lectores
   9: 
  10:     def reader_unlock():
  11:          with mutex:
  12:               readers -= 1
  13:               if not readers:
  14:                    canWrite.notify() # desbloquea escritor si eres el último
  15: 
  16:     # Escritores
  17: 
  18:     def writer_lock():
  19:          with mutex:
  20:               while writing or readers:
  21:                    canWrite.wait()  # condición hay lectores o escritores
  22:               writing = True
  23: 
  24:     def writer_unlock():
  25:          with mutex:
  26:               writers = False
  27:               canRead.notify()  # desbloquea a lectores
  28:               canWrite.notify()  # y escritores
  

• El problema anterior presenta un problema de inanición → los escritores podrían no entrar nunca a la sección crítica

• Una posible solución es dar preferencia al escritor que esté bloqueado (la función empty habría que definirla usando, por ejemplo, un contador para los escritores en espera):

  1:     def reader_lock():
  2:      with mutex:
  3:           while writing or not empty(canWrite):
  4:                canRead.wait() # condición hay escritores
  5:           readers += 1
  6:           canRead.notify()    # pueden entrar otros lectores
  

 1:   def pick():
 2:      with mutex:
 3:           while picks[i] != 2:
 4:                canEat[i].wait()
 5:           picks[left] -= 1
 6:           picks[right] -= 1
 7: 
 8:   def release():
 9:        with mutex:
10:             picks[left] += 1
11:             picks[right] += 1
12:             if picks[left] == 2:        # sólo desbloquean vecinos con ...
13:                  canEat[left].notify()
14:             if picks[right] == 2:       # ... los dos palillos libres
15:                  canEat[right].notify()

• Código completo: philosophers.py
• Una solución similiar en Java: PhilosopherConditions.java

Elementos :

son los siguientes

• Para cada monitor:

  semáforo m_mutex :

  inicializado a 1 para la entrada al monitor.

  semáforo m_next :

  para la cola de cortesía inicializado a 0.

  entero m_next_count :

  número de procesos bloqueados en la cola de cortesía (0 inicialmente)

• Para cada variable de condición (m_x):

  semáforo m_x_sem :

  para la cola de la variable de condición inicializado a 0.

  entero m_x_count :

  número de procesos bloqueados en la variable de condición (0 inicialmente)

Procedimientos exportados por el monitor:

Cada uno de ellos seguirá este patrón:

 1:       wait(m_mutex)
 2:       #  cuerpo_procedimiento
 3:       if m_next_count > 0:
 4:         # Al salir del monitor se debe desbloquear en primer lugar a los
 5:         # procesos de la cola de cortesía si los hay.
 6:         signal(m_next)
 7:         # Fijate que no hay signal(m_mutex) aquí porque hay cesión de la
 8:         # exclusión mutua del proceso que sale al proceso que entra desde la
 9:         # cola de cortesía. Dicho de otro modo, las llamadas a wait y signal
10:         # han de estar equilibradas.
11:       else:
12:         signal(m_mutex)
13: 

• Operaciones de sincronización (sobre variables de condición)

   1:     empty (m_x):
   2:       if m_x_count == 0:
   3:         return (True)
   4:       else:
   5:         return (False)
   6: 
   7:     resume(m_x):
   8:       if m_x_count != 0:
   9:         m_next_count = m_next_count + 1
  10: 
  11:         signal(m_x_sem) # Libera al siguiente proceso en la cola de la
  12:         wait(m_next)    # variable de condición y se bloquea en la cola
  13:                         # de cortesía
  14: 
  15:         m_next_count = m_next_count - 1
  16: 
  17:     delay(m_x):
  18:       m_x_count = m_x_count + 1
  19: 
  20:       # Alguien puede ocupar el monitor: puede ser de la cola de cortesía
  21:       # primero o de la entrada normal al monitor
  22:       if m_next_count != 0:
  23:          signal(m_next)
  24:          # Libera al siguiente proceso: tienen
  25:          # preferencia los de la cola de cortesía
  26:       else:
  27:         signal(m_mutex)
  28: 
  29:       wait(m_x_sem)     # Se bloquea en la variable de condición m_x
  30:       m_x_count = m_x_count - 1