Concurrencia en Sistemas Operativos: Semáforos, Monitores y Problemas Clásicos de Sincronización

semaforoBinario mutex=1
proceso(){
  while(true){ //SNC
    wait(mutex) //SC
    signal(mutex)
  }
}

semaforoBinario mutex=1
semaforo elementos=0
semaforo espacios=TAMBUF

productor(){
  while(true){
    item=producir()
    wait(espacios)
    wait(mutex)
    guardarBuffer(item)
    signal(mutex)
    signal(elementos)
  }
}

consumidor(){
  while(true){
    wait(elementos)
    wait(mutex)
    item=quitarBuffer()
    signal(mutex)
    signal(espacios)
    consumir(item)
  }
}

semaforoBinario mutex=1, escritura=1
int lectores=0

lector(){
  while(true){
    wait(mutex)
    lectores++
    if(lectores==1) wait(escritura)
    signal(mutex) //LEER
    wait(mutex)
    lectores--
    if(lectores==0) signal(escritura)
    signal(mutex)
  }
}

escritor(){
  while(true){
    wait(escritura) //ESCRIBIR
    signal(escritura)
  }
}

semaforoBinario mutex=1
semaforo cliente=0, barbero=0
int sillas=NUMSILLAS

barbero(){
  while(true){
    wait(cliente)
    wait(mutex)
    sillas++
    signal(barbero)
    signal(mutex) //CORTAR PELO
  }
}

cliente(){
  while(true){
    wait(mutex)
    if(sillas>0){
      sillas--
      signal(cliente)
      signal(mutex)
      wait(barbero) //PELARSE
    } else {
      signal(mutex) //se va
    }
  }
}

semaforo tenedor[5]={1,1,1,1,1}

filosofo(i){
  while(true){
    pensar()
    wait(tenedor[i])
    wait(tenedor[(i+1)%5])
    comer()
    signal(tenedor[i])
    signal(tenedor[(i+1)%5])
  }
}

semaforo tenedor[5]={1,1,1,1,1}
semaforo camarero=4 //máximo 4 compitiendo

filosofo(i){
  while(true){
    pensar()
    wait(camarero)
    wait(tenedor[i])
    wait(tenedor[(i+1)%5])
    comer()
    signal(tenedor[i])
    signal(tenedor[(i+1)%5])
    signal(camarero)
  }
}

Un monitor ofrece exclusión mutua automática (no hace falta un mutex manual). Dispone de variables de condición con waitC() y signalC(), y empty(c) comprueba si la cola de la condición está vacía.

Nota sobre if/while: en esta notación clásica se usa if. En Java con notifyAll es obligatorio while, para volver a comprobar la condición al despertar.

monitor PC
  bufferType buffer<-empty
  condition notEmpty, notFull

  operation append(v)
    if buffer is full: waitC(notFull)
    append(v,buffer)
    signalC(notEmpty)

  operation take()
    if buffer is empty: waitC(notEmpty)
    w<-head(buffer)
    signalC(notFull)
    return w

producer: loop{d<-produce; PC.append(d)}
consumer: loop{d<-PC.take; consume(d)}

monitor RW
  int readers<-0, writers<-0
  condition OKtoRead, OKtoWrite

  op iniciarLectura
    if writers!=0 or not empty(OKtoWrite): waitC(OKtoRead)
    readers<-readers+1
    signalC(OKtoRead) //cascada siguiente lector

  op terminarLectura
    readers<-readers-1
    if readers=0: signalC(OKtoWrite)

  op iniciarEscritura
    if writers!=0 or readers!=0: waitC(OKtoWrite)
    writers<-writers+1

  op terminarEscritura
    writers<-writers-1
    if empty(OKtoRead) then signalC(OKtoWrite) else signalC(OKtoRead)

fork[i] indica los tenedores libres del filósofo i (2 significa que puede comer).

monitor ForkMonitor
  int array[0..4] fork<-[2,2,2,2,2]
  condition array[0..4] OKtoEat

  op takeForks(i)
    if fork[i]!=2: waitC(OKtoEat[i])
    fork[i+1]<-fork[i+1]-1
    fork[i-1]<-fork[i-1]-1

  op releaseForks(i)
    fork[i+1]<-fork[i+1]+1
    fork[i-1]<-fork[i-1]+1
    if fork[i+1]=2: signalC(OKtoEat[i+1])
    if fork[i-1]=2: signalC(OKtoEat[i-1])

filosofo(i): loop{think; takeForks(i); eat; releaseForks(i)}

Hilos: se crean extendiendo Thread o implementando Runnable; el código va en run() y el hilo arranca con start().

Monitor en Java: exclusión mutua con synchronized sobre el mismo objeto. No hay variables condición (existe una única cola), así que se usa while(!cond) wait(); seguido de notifyAll(). wait() siempre debe ir dentro de try/catch(InterruptedException). notify() despierta un hilo aleatorio (posible inanición); notifyAll() despierta a todos.

Estructura: synchronized m1(){while(!cond) wait();} y synchronized m2(){notifyAll();}

class PCMonitor{
  final int N=5
  int Oldest=0,Newest=0
  volatile int Count=0
  int Buffer[]=new int[N]

  synchronized void Append(int V){
    while(Count==N) try{wait();}catch(InterruptedException e){}
    Buffer[Newest]=V
    Newest=(Newest+1)%N
    Count=Count+1
    notifyAll()}

  synchronized int Take(){
    int temp
    while(Count==0) try{wait();}catch(InterruptedException e){}
    temp=Buffer[Oldest]
    Oldest=(Oldest+1)%N
    Count=Count-1
    notifyAll()
    return temp}}

Hilos: class Productor extends Thread{PCMonitor m; run(){while(true){m.Append(producir());}}}
       class Consumidor extends Thread{PCMonitor m; run(){while(true){consumir(m.Take());}}}

class RWMonitor{
  volatile int readers=0
  volatile boolean writing=false

  synchronized void StartRead(){
    while(writing) try{wait();}catch(InterruptedException e){}
    readers=readers+1
    notifyAll()}

  synchronized void EndRead(){
    readers=readers-1
    if(readers==0) notifyAll()}

  synchronized void StartWrite(){
    while(writing||(readers!=0)) try{wait();}catch(InterruptedException e){}
    writing=true}

  synchronized void EndWrite(){
    writing=false
    notifyAll()}}

Una cita es una invocación remota, directa y asimétrica. El servidor es una task con entry.

Select general:

select
  when guarda1 => accept E1(...) do --cita CORTA--
  end E1; --actualizar fuera del do--
or when guarda2 => accept E2(...) do ... end E2;
or delay 5.0; --opcional
or terminate; --opcional
else ... --opcional, no con delay/terminate
end select

Semántica: solo se consideran las guardas abiertas. Si varias tienen llamada pendiente, la elección es indeterminista. Si ninguna tiene llamada y existe else, se ejecuta el else. Si ninguna tiene llamada y no hay else, la tarea se suspende. Si todas las guardas están cerradas, se produce un error.

task Buffer is
  entry Leer(x:out ITEM)
  entry Escribir(x:in ITEM)
end Buffer;

task body Buffer is
  N:constant:=10
  B:array(1..N) of ITEM
  Inicio,Fin:INTEGER range 1..N:=1
  Cont:INTEGER range 0..N:=0
begin
  loop
    select
      when Cont<N =>
        accept Escribir(x:in ITEM) do B(Fin):=x end
        Fin:=Fin mod N+1; Cont:=Cont+1
    or when Cont>0 => --OJO: >0 no >1
        accept Leer(x:out ITEM) do x:=B(Inicio) end
        Inicio:=Inicio mod N+1; Cont:=Cont-1
    end select
  end loop
end Buffer;

protected type Buffer_Type is
  entry Put(X:in Item)
  entry Get(X:out Item)
private
  Box:Store
  First,Last:Index:=Index'First
  Number:Count:=0
end Buffer_Type;

protected body Buffer_Type is
  entry Put(X:in Item) when Number<Size is
  begin Box(Last):=X; Last:=Last+1; Number:=Number+1 end Put;

  entry Get(X:out Item) when Number>0 is
  begin X:=Box(First); First:=First+1; Number:=Number-1 end Get;
end Buffer_Type;

• Seguridad: "nunca pasa algo malo" (exclusión mutua, ausencia de interbloqueo, corrección parcial).
• Vivacidad: "algo bueno pasa" (terminación, equidad y ausencia de inanición; dependen del planificador).

Debe cumplir: exclusión mutua, ausencia de interbloqueo, ausencia de inanición y ausencia de retrasos innecesarios. Dekker resuelve el caso de 2 procesos; Panadería, el de N procesos.

• Espera activa: puede provocar inanición; no es débilmente equitativo.
• Cola de bloqueo: no provoca inanición; es fuertemente equitativo.
• Conjunto de bloqueo: provoca inanición si hay más de 2 procesos.

• wait: en un semáforo puede bloquear o no; en un monitor siempre bloquea.
• signal: en un semáforo siempre tiene efecto; en un monitor puede no tener efecto si la cola está vacía.
• Despierta a: en un semáforo, cualquier proceso; en un monitor, el primero de la cola.
• Tras signal: en un semáforo, el proceso despertado sigue ya; en un monitor, espera a que el que hizo el signal salga del monitor.

Tienen exclusión mutua por definición y sincronización mediante variables condición. Existen varias semánticas de signal (signal-and-wait, urgent, continue). En Java, al no haber variables condición, se emplea while con notifyAll.

La solución con semáforos provoca inanición de escritores.

• Citas: remotas, directas y asimétricas.
• Select: guardas más indeterminismo (else, delay, terminate).
• Objeto protegido: función concurrente, procedimiento exclusivo y entry con barrera. Las barreras tienen preferencia y no admiten bloqueantes dentro; una barrera sin parámetros provoca requeue.

• Confusión de propósito.
• Escasa capacidad semántica.
• Propensión a errores (un cambio de orden puede causar interbloqueo).
• Acoplamiento innecesario.
• Difíciles de manejar con muchos procesos.

Memoria compartida: variables con exclusión mutua o mensajes en buffers FIFO. Red débilmente acoplada: paso de mensajes, modelo cliente-servidor. Canal síncrono (bloqueante) frente a asíncrono (con buffer). En el modelo cliente-servidor, el servidor queda bloqueado esperando peticiones; el cliente multihilo crea un hilo por petición y vuelve a bloquearse.