En este post estudiaremos 4 problemas clásicos de sincronización por software, los cuales son:

• Problema de lectores y escritores
• Problema de productor consumidor
• Problema de los filósofos comensales
• Problema del babero dormilón

Cabe decir que estos problemas fueron diseñados para poder abstraer problemas de la vida real, y si los tomamos literalmente puede que no le encontremos ningún uso practico pero, como todo en la vida, es cuestión de interpretación.

Consideremos que para todas las soluciones usaremos semáforos cuyos métodos (en pseudocodigo) son:

//Inicializar el semaforo "s" a un valor "m"
IS(s, m) {
   S = m;
}

//down, también conocido como wait
//el metodo bloquear procesos, impide el acceso a la región critica de memoria.
DOWN(s) {
   if(s > 0) {
     s = s - 1
   } else {
     bloquear_procesos();
   }
}

//UP tambien conocido como notify o signal vuelve a liberar la región critica
UP(s) {
  if(hay_procesos_dormidos()){
     despertar_un_proceso();
  } else {
     s = s + 1;
  }
}

Problema de lectores y escritores

Consiste de dos procesos que acceden el mismo bloque de memoria compartida al mismo tiempo tomando en cuenta la restricción de que dos acciones no pueden ser llevadas a cabo sobre el mismo bloque de memoria al mismo tiempo, es decir, si un proceso esta escribiendo un bloque, este no puede ser escrito ni leído por ningún otro proceso manteniendo así la exclusión mutua sobre una región critica.

Solución:

semaphore mutex = 1;                 // controla el acceso al contador de procesos leidos
semaphore rc = 1;                    // controla el acceso a la región critica
int reader_count;                    // el numero de procesos lectores que acceden la región critica

Lector()
{
  while (true) {                            // loop infinito
     down(&mutex);                          // acceder reader_count
     reader_count = reader_count + 1;       // incrementar reader_count
     if (reader_count == 1)
         down(&rc);                         // si es el primer proceso en leer la reión critica,
                                            // se bloquea la misma con un down para prevenir 
                                            // que esta sea accesada por otro proceso
     up(&mutex);                            // permitir a otros procesos acceder a reader_count
     leer_rc();                             // leer la region critica
     down(&mutex);                          // acceder reader_count
     reader_count = reader_count - 1;       // decrementar reader_count
     if (reader_count == 0)
         up(&rc);                           // si ya no hay procesos leyendo 
                                            // la region critica, permitir que el proceso escritor funcione
     up(&mutex);                            // permitir a otros procesos acceder el lector
}

Escritor()
{
  while (TRUE) {                            // loop infinito
     crear_datos();                         // preparar datos para escribir en la rc
     down(&rc);                             // acceder a la región critica
     write_db();                            // escribir datos
     up(&rc);                               // liberar el acceso exclusivo a la rc
}

 Problema de productores consumidores

Este problema describe dos procesos que acceden a un buffer de tamaño fijo al mismo tiempo y lo utilizan como una cola.

El proceso productor produce, valga la redundancia, un recurso o dato y lo almacena en la cola, mientras que por su parte el proceso consumidor consume los datos que el productor va produciendo, siempre que existan datos o recursos que consumir.

semaphore lleno = 0; // items produced
semaphore vacio = BUFFER_SIZE; // remaining space

proceso producer() {
    while (true) {
        item = producir();      //produce un item
        down(vacio);            //reduce la cuenta de vacio, si esta lleno espera
            push(item);         //coloca el item en la cola
        up(lleno);              //aumenta el semaforo de cola llena
    }
}

proceso consumidor() {
    while (true) {
        down(lleno);            //quita un elemento del semaforo lleno (permite que se vuelva a producir)
            item = pop();       //obtenemos el elemento
        up(vacio);              //aumenta uno a la cuenta de vacio
        consumir(item);         //consume el elemento
    }
}

 Problema de los filósofos comensales

El enunciado dice así:

5 filósofos comensales se sientan en una mesa redonda con un plato de espaguetti en el centro, y un tenedor es colocado en medio de cada par de filósofos. Cada filosofo pasa su vida pensando y comiendo, pero necesita dos tenedores para poder comer. Cada tenedor puede ser usado por un solo filosofo a la vez y cuando un filosofo termina de comer debe poner los tenedores de vuelta en su lugar.

Siendo que el espaguetti es infinito y que cada filosofo no sabe cuando los otros quieren comer o pensar, el problema reside en diseñar un algoritmo concurrente tal que ninguno de los filósofos morirá de hambre.

Para esta solución consideremos las siguientes variables:

• pensar (p)
• comer  (c)
• hambriento (h)
• dormir (d)

y un arreglo de 5 semáforos, y un semáforo de exclusión mutua.

Semaphore Em                            //semaforo de exclusion mutua
Semaphore[] sems = new Semaphore[5];    //arreglo de semaforos
Status = ['p', 'p', 'p', 'p', 'p'];     //que esta haciendo cada filosofo en determinado momento
is(em, 1);                              //inicializar exclusión mutua

//inicializar el arreglo de semaforos (uno por filosofo)
for(i=0; i<sems.length; i++) {
    is(sems[i]);
}

//proceso del i-esimo filosofo
filosofo(i) {
    pensar();
    tomar_tenedores(i);
    comer();
    dejar_tenedores(i);
    dormir(i);
}

//tomar tenedor del i-esimo filosofo
tomar_tenedores(i){
    down(em);        //bloquear los recursos de rc
    status[i] = 'h'; //indicar que esta hambriento
    test(i);         //intentar comer   
    up(em);          //bloquear los recursos de rc
    down(sems[i]);   //bajar el semaforo de este filosofo
}

//intentar comer para el i-esimo filosofo
test(i) {
    if(
        Status[i+1 % 5] != 'c' && // el filosofo de la derecha no esta comiendo
        Status[i-1 % 5] != 'c' && // el filosofo de la derecha no esta comiendo
        Status[i] = 'h' //este filosofo tiene hambre
    ) {
        Status[i]  = 'c';   //como hay tenedores podemos comer
        up(sems[i]);        //bloqueamos la región critica
    }
}

dejar_tenedores(i) {
    down(em);
    Status[i] = 'd';
    test( (i-1) % 5 ); //dejar tenedor izquierdo
    test( (i+1) % 5 ); //dejar teedor derecho
}

Problema del barbero dormilón

El problema consiste en un barbero que debe atender a sus clientes como van llegando, cuando un cliente llega se sienta en la sala de espera y notifica al barbero, que en dado caso no tenga clientes esta dormido, el barbero despierta y corta el pelo, cuando termina de cortar el pelo revisa si tiene mas clientes para seguir cortando el pelo, o bien seguir durmiendo.

Semaphore barberoListo = 0
Semaphore accessarSillas = 1     # si es 1 los asientos en la sala de sepera pueden aumentar a disminuir
Semaphore clienteList = 0          # cantidad de clientes esperando ser atendidos
int asientosLibres = N      # numero de asientos en la sala de espera

def Barbero():
  while true:                   # loop infinito
    down(clienteList)             # tratar de atendender un cliente, si no hay clientes dormir
    down(accessWRSeats)         # intentar accesar para modificar el numero de asientos libres, si no dormir
    asientosLibres += 1         # Una silla en la sala de espera esta libre
    up(barberoListo)            # el barbero esta listo para cortar
    up(accessarSillas)          # desbloquear la silla
    # (cortar_pelo)

def Cliente():
  while true:                   # loop infinito
    down(accessWRSeats)         # tratar de acceder a las sillas en la sala de espera
    if asientosLibres > 0:      # si hay sillas libres:
      asientosLibres -= 1       #   sentarse en la silla
      up(clienteList)           #   despertar al barbero dormilon
      up(accessarSillas)        #   desbloquear la silla
      down(barberoListo)        #   esperar a que el barbero este listo
      # (cortarse el pelo)
    else:                       # no hay asientos libres en la sala de espera
      up(accessarSillas)        #  liberar el bloqueo en las sillas
      # (abandonar sin cortarse el pelo)