Sintáxis en pseudocódigo

monitor <nombre>:
    # Estado interno (privado)
    variables locales

    # API pública
    export proc1, proc2, ...

    procedure proc1(parámetros):
        # código

    procedure proc2(parámetros):
        # código

Ejemplo mínimo

• Supongamos que varios procesos deben incrementar el valor de una variable compartida (en exclusión mutua) y poder examinar su valor en cualquier momento. Para ello definiremos un monitor que encapsulará dicha variable compartida.

  monitor incremento:
     integer counter = 0
     export add, value;
  
     procedure add:
          counter = counter + 1
  
     procedure value:
          return counter
     ...
  
  incremento.add()
  ...
  v = incremento.value()
  

• Los procesos, cuando desean comunicarse o sincronizarse utilizan los recurso privados del Monitor mediante invocación de los procedimientos públicos (exportados).

• Casos:

  • Monitor libre: Si un proceso invoca un procedimiento de un monitor y nadie posee el monitor, éste proceso bloquea y ocupa el monitor, (ejecuta el procedimiento)

  • Monitor ocupado: Si un proceso invoca algún procedimiento del monitor y éste está ocupado entonces el proceso queda bloqueado en una cola asociada al monitor. Cuando el proceso poseedor del monitor finaliza la ejecución de un procedimiento del monitor, se libera el primer proceso bloqueado en ella.

  • Exclusión Mutua: Está garantizada por la propia definición del monitor

  • Sincronización: Se consigue mediante el uso de Variables de condición declaradas dentro del propio monitor.

    Cada una de estas variables dipone de una cola de bloqueo de procesos (aparte de la del monitor)

  

  Figure 3: Funcionamiento del monitor.

Variables de condición: Operaciones

Las variables de condición habilitan la sincronización dentro del monitor. Cada condición mantiene su cola de bloqueo (independiente de la cola de entrada al monitor). Usaremos tres operaciones:

• delay(c) (bloqueo de procesos): coloca al proceso al final de la cola de c y libera el monitor antes de bloquearse.
• resume(c) (desbloqueo de procesos): si la cola de c no está vacía, selecciona al primer proceso y lo prepara para continuar (si está vacía, es nula).
• empty(c) (consulta de cola): devuelve si la cola de c está vacía.

Funcionamiento interno

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

Políticas de reanudación

Distinguir qué proceso continúa inmediatamente tras un resume(c) depende de la política elegida por el lenguaje/implementación. Las tres variantes más habituales:

1. IRR (Immediate Resumption Requirement). Reanudación inmediata del desbloqueado:

   • El que señaliza (S) cede el monitor y se bloquea; entra el esperando en condición (W).
   • Prioridad: E < S < W (E = entrada, S = señalizador, W = despertado).

2. Salida del señalizador primero. S termina y sale; luego pasan W y, por último, E.

   • Prioridad: E < W < S.

3. Opción “Java”. No se distingue entre E y W: ambos compiten cuando S sale.

   • Prioridad: E = W < S.

Ejercicio 1:

Realiza una traza del orden de ejecución bajo IRR y bajo la política de Java de la siguiente secuencia de instrucciones:

• S1 entra en el monitor y hace delay(c).
• S2 entra en el el monitor y hace delay(c).
• S3 entra en el monitor, ejecuta una operación y hace resume(c)
• Inmediatamente después, S4 intenta entrar en el monitor.

Para realizar la traza, completa la siguiente tabla:

Paso	Acción	Dentro del monitor	Cola de entrada al monitor	Cola de condición c
1	S1 entra	S1	-	-

Ejercicio 2

• Una cuenta de ahorros: es compartida entre distintas personas (procesos).

  • Cada persona puede depositar o sacar dinero de la cuenta.
  • El balance actual de la cuenta es la suma de los depósitos menos la suma de las cantidades sacadas.
  • El balance nunca puede ser negativo.

• Se pide: construir un monitor en pseudocódigo para resolver este problema con las operaciones depositar(cantidad) y sacar(cantidad).

• El cliente que deposita debe despertar a los clientes que están esperando para sacar.

• El cliente que llega para sacar dinero lo saca si existe saldo, independientemente de que haya algún otro proceso esperando porque no hay suficiente dinero para él.

• Variante: implementad el mismo problema suponiendo que ningún cliente puede colarse para sacar dinero.

Patrones y ejemplos clásicos

Barreras

mutex = threading.Lock()
allArrived = threading.Condition(mutex)
arrived = 0

def barrier(n):
    with mutex:
        arrived += 1
        if arrived == n:
            arrived = 0
            allArrived.notify_all()
        else:
            allArrived.wait()

• Código completo: barrier.py

Productor-Consumidor

# Productor

def append(self, data):
    with mutex:
        while len(buffer) == buffer.maxlen:
            untilNotFull.wait()     # condición buffer no lleno
        buffer.append(data)
        whileEmpty.notify()

# Consumidor

def take(self):
    with mutex:
        while not buffer:
            whileEmpty.wait()    # condición buffer no vacío
        data = buffer.popleft() # extrae el primero de la lista
        untilNotFull.notify()
        return data

• Código completo: producer-consumer.py

Lectores-Escritores (prioridad Lectores)

# Lectores
def reader_lock():
    with mutex:
        while writing:
            canRead.wait()    # condición hay escritores
        readers += 1
        canRead.notify()       # pueden entrar otros lectores

def reader_unlock():
    with mutex:
        readers -= 1
        if not readers:
            canWrite.notify() # desbloquea escritor si eres el último

# Escritores
def writer_lock():
    with mutex:
        while writing or readers:
            canWrite.wait()  # condición hay lectores o escritores
        writing = True

def writer_unlock():
    with mutex:
        writers = False
        canRead.notify()  # desbloquea a lectores
        canWrite.notify()  # y escritores

• Código completo: rw_lock.py

Lectores-Escritores (prioridad 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):

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

Comida de filósofos

def pick():
    with mutex:
        while picks[i] != 2:
            canEat[i].wait()
        picks[left] -= 1
        picks[right] -= 1

def release():
    with mutex:
        picks[left] += 1
        picks[right] += 1
        if picks[left] == 2:        # sólo desbloquean vecinos con ...
            canEat[left].notify()
        if picks[right] == 2:       # ... los dos palillos libres
            canEat[right].notify()

• Código completo: philosophers.py

Implementación

Posix

• Variables condición: la cabecera pthread.h proporciona el tipo pthread_cond_t.

• Para hacer un uso sencillo disponemos de:

  • PTHREAD_COND_INITIALIZER
  • int pthread_cond_wait (pthread_cond_t *cond, pthread_mutex_t *mutex)
  • int pthread_cond_signal (pthread_cond_t *cond)

• Existen funciones para inicializar con otro tipo de atributos y para destruir las condiciones:

  • int pthread_cond_init (...)

• También disponemos de:

  • int pthread_cond_timedwait (...)
  • int pthread_cond_broadcast (...)

• Veamos un uso habitual de estas funciones para simular monitores:

  pthread_mutex_t crj = PTHREAD_MUTEX_INITIALIZER;
  pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
  ...
  tipoOperacion nombreOperacion(argumentos){
     ...
     pthread_mutex_lock(&crj);
     while(predicado)
          pthread_cond_wait(&cond,&crj);
  
     // Inicio sección crítica
       ...
     // Señalar condiciones si las hubiera
     // Fin de la sección crítica
  
     pthread_mutex_unlock (&crj);
     ...
     return valorDevuelto;  // de tipoOperacion
  }
  

Mediante semáforos

• Elementos del monitor:

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

• Esqueleto de cada procedimiento exportado por el monitor:

  wait(m_mutex)
  #  cuerpo_procedimiento
  if m_next_count > 0:
      # Al salir, desbloquear primero la cola de cortesía (si la hay)
      signal(m_next)
      # No se hace signal(m_mutex): la exclusión se cede al que viene de m_next
      # Las llamadas a wait y signal han de estar equilibradas.
  else:
      signal(m_mutex)
  

• Operaciones de sincronización sobre variables de condición:

  empty (m_x):
      if m_x_count == 0:
          return (True)
      else:
          return (False)
  
  resume(m_x):
      if m_x_count != 0:
          m_next_count = m_next_count + 1
  
          signal(m_x_sem) # Libera al siguiente proceso en la cola de la
          wait(m_next)    # variable de condición y se bloquea en la cola
                          # de cortesía
  
          m_next_count = m_next_count - 1
  
  delay(m_x):
      m_x_count = m_x_count + 1
  
      # Alguien puede ocupar el monitor: puede ser de la cola de cortesía
      # primero o de la entrada normal al monitor
      if m_next_count != 0:
          signal(m_next)
          # Libera al siguiente proceso: tienen
          # preferencia los de la cola de cortesía
      else:
          signal(m_mutex)
  
      wait(m_x_sem)     # Se bloquea en la variable de condición m_x
      m_x_count = m_x_count - 1
  

Ejercicio 3

• Implementa el problema de la tribu con monitores:
  • Los miembros de la tribu cenan en comunidad de una gran olla que contiene M misioneros.
  • Cuando un miembro de la tribu quiere comer, él mismo se sirve de la olla, a menos que esté vacía.
  • Si la olla está vacía, entonces despierta al cocinero y espera a que éste llene la olla.
  • Sólo se debe despertar al cocinero cuando la olla está vacía.