Comunicación de procesos (IPC)

Con frecuencia, varios procesos deben comunicarse entre sí para pasar datos o coordinarse para hacer una tarea. Por ejemplo, en el Shell, se utilizan pipes para que la salida del primero sea la entrada del segundo.

Hasta el momento, se sabe que los procesos que trabajan en conjunto pueden compartir cierto espacio de almacenamiento compartido sobre el que leer y escribir:

• Archivos
• Memoria compartida (seguramente en una estructura de datos del kernel)
• Librerías adicionales
• Señales (solo sincronización)

En resumen, hay tres cuestiones a tratar:

1. Cómo un proceso puede pasar información a otro
2. Evitar interferencias: que no haya colisiones por dos procesos accediendo a lo mismo
3. Garantizar un orden correcto cuando hay dependencias de lectura y escritura

También es importante mencionar que estas cuestiones también se pueden aplicar sobre los hilos. Para pasar información, la forma más sencilla es aprovechar que los hilos comparten espacios de direcciones, pero para el resto, se pueden aplican las mismas soluciones que los procesos, dado que son los mismos problemas.

Carreras críticas

Pongamos un ejemplo de una cola de impresión o spooler de impresión. Cada vez que un proceso desee imprimir un archivo, deberá introducir su dirección en un directorio de spooler. Otro proceso, el demonio de impresión, comprobará de forma periódica si hay nuevos archivos, imprimirlos y luego eliminarlos del directorio.

Supongamos que el directorio tiene muchas ranuras numeradas ($0, 1, 2 \ldots$) que almacenan un nombre de archivo. Para implementar la cola, también son necesarias dos variables: salida, que apunta al siguiente archivo a imprimir; y entrada, que apunta a la siguiente ranura libre.

Pongamos ahora que entrada=7 y salida=4. De forma simultánea, los procesos $A$ y $B$ deciden imprimir un archivo.

El código en C de ambos procesos:

1buffer[entrada] = "fichero";
2entrada++;

Como dictamina la Ley de Murphy, es posible que suceda lo siguiente:

1. El proceso $A$ lee el valor de entrada=7 y guarda el valor en su memoria local (quizá un registro).
2. Justo en ese momento, se produce un cambio de contexto para que continue el proceso $B$.
3. $B$ lee entrada=7 y escribe allí el nombre del archivo que quiere imprimir.
4. Luego $B$ actualiza entrada a 8 y continua haciendo otras tareas.
5. Cuando $A$ recupere la CPU, utilizará el valor leido de antes, 7, y por tanto sobreescribirá el archivo escrito por $B$.
6. Luego $A$ actualizará entrada también a 8.

Cuando el demonio de impresión vaya a enviar trabajos a la impresora, el estado del directorio es consistente, pero el archivo del proceso $B$ nunca se imprimirá.

Nótese que viendo el código en C es difícil determinar si se puede dar una condición crítica o no. Esto se debe ver estudiando las instrucciones máquina reales que se están ejecutando:

1lw entrada, $1
2lw buffer, $2
3lw string, $3
4    ;; cambio de contexto aquí
5sw $3, 0($2)
6addi $1, $1, 1
7sw $1, 0(entrada)

Aquí ya es más evidente que, al darse al cambio de contexto, otro proceso podrá modificar los valores compartidos. Sin embargo, cuando continúe la ejecución de este proceso, se utilizarán los valores desactualizados que se habían cargado antes en registros.

1int suma = 0;
2void suma(int ni, int nf) {
3    for (int i = ni; i <= nf; i++) {
4        suma += i;
5    }
6}

1lw $1, j
2lw $2, suma
3    ;; cambio de contexto aquí
4add $2, $2, $1
5sw $2, suma

 1int suma = 0;
 2void sumar(int ni, int nf) {
 3    int suma_parcial = 0;
 4
 5    for (int i = ni; i <= nf; i++) {
 6        suma_parcial += i;
 7    }
 8
 9    // problemas aquí
10    suma += suma_parcial;
11}

Depurar estos programas no es nada divertido, porque las condiciones de carrera son bastante infrecuentes: en la mayoría de ejecuciones funcionará correctamente, pero en algún momento obtendremos resultados extraños y aparentemente inexplicables. Será muy difícil reproducir el problema.

Además, como hemos visto, a partir del código en C es poco evidente de qué forma puedan surgir estas situaciones.

Este problema es particularmente relevante para el kernel, porque es un recurso compartido entre todos los procesos: siempre está en memoria principal y todos ellos pueden realizar operaciones de forma concurrente realizando llamadas al sistema.

Exclusión mutua y regiones críticas

El problema del ejemplo del apartado anterior se habría solucionado si $B$ no pudiese ejecutarse en ese momento, o al menos no poder acceder al directorio de impresión. Es decir, se necesita algún mecanismo que garantice la exclusión mutua.

Sin embargo, parte del tiempo, un proceso está ocupado haciendo cálculos internos y otras cosas que no producen condiciones carrera. Solo en algunas ocasiones, donde necesita acceder a memoria compartida o archivos compartidos, podrán aparecer problemas. No sería demasiado sensato aplicarlo sobre todo, ya que se pierden los beneficios de ejecutar procesos en paralelo: es necesario definir claramente qué secciones necesitan exclusión mutua.

Nótese que algunas veces puede ser difícil definir las regiones críticas con precisión, ya que el compilador reordena las instrucciones máquina resultantes. También puede causar que la regiones críticas sean más grandes.

Si se pudiesen ordenar las intrucciones de cada proceso de forma que dos procesos nunca estuviesen en sus regiones críticas al mismo tiempo, se podrían evitar las carreras.

Sin embargo, este requerimiento no es suficiente para los procesos en paralelo cooperen de forma correcta y eficiente al usar datos compartidos. Es necesario cumplir las 4 condiciones siguientes para obtener una buena solución:

1. Exclusión mutua: No puede haber dos procesos operando en la región crítica.
2. No puedo hacer suposiciones sobre velocidades o CPUs.
3. No puede haber un proceso que sin estar en la región crítica impida que otro entre.
4. Evitar inanición: No puede haber ningún proceso esperando indefinidamente para entrar en la región crítica. Se debe garantizar que podrá entrar en algún momento.

Y para mejorar el rendimiento (no es estrictamente necesario):

5. No hay espera activa: el proceso deberá ceder la CPU cuando no puede entrar en la región crítica, en lugar de estar chequeando constantemente si puede entrar.

Exclusión mutua con espera ocupada

En este apartado se discutirán varias soluciones para lograr la exclusión mutua.

    0 -- Región crítica libre   ==> Candado abierto (cierra cuando entres)
    1 -- Región crítica ocupada ==> Candado cerrado

1while (TRUE) {
2    while (turno != TURNO_ESTE_PROCESO); // espera activa
3    region_critica();
4    turno = (turno+1) % TOTAL_TURNOS;
5    region_nocritica();
6}

A partir de aquí, se discuten buenas soluciones que cumplen las 4 primeras condiciones.

 1int turno;
 2int interesado[N];
 3
 4void entrar_region(int proceso) {
 5    int otro = 1 - proceso;
 6
 7    // IMPORTANTE: deja de funcionar si se intercambian estas dos líneas.
 8    interesado[proceso] = TRUE;
 9    turno = proceso;
10
11    while (turno == proceso && interesado[otro] == TRUE);
12}
13
14void salir_region(int proceso) {
15    interesado[proceso] = FALSE;
16}

1tsl reg, LOCK

1entrar_region:
2    tsl reg, LOCK     ;; Copiar el LOCK a reg y ponerlo a 1
3    cmp reg, 0        ;; ¿Era LOCK == 0?
4    jne entrar_region ;; Si no, loop (espera activa)
5    ret               ;; Volver => Entrar región
6
7salir_region:
8    mov LOCK, 0       ;; poner a 0 el lock
9    ret

 1entrar_region:
 2    mov reg, 1        ;; Coloca 1 en el registro
 3    xchg reg, LOCK    ;; Intercambia el registro y LOCK
 4    cmp reg, 0        ;; ¿Era LOCK == 0?
 5    jne entrar_region ;; Si no, loop (espera activa)
 6    ret               ;; Volver => Entrar región
 7
 8salir_region:
 9    mov LOCK, 0       ;; poner a 0 el lock
10    ret

El problema del productor-consumidor

Se tienen dos procesos que operan sobre un buffer compartido:

• Productor: coloca información en el buffer.
• Consumidor: retira esa información y la procesa.

Se puede generalizar a $n$ productores y $n$ consumidores, pero empezaremos por algo simple.

El buffer compartido es una pila FIFO (First In, First Out), por lo que se necesita una variable cuenta que indica la última posición. También es posible utilizar una cola LIFO.

Los problemas aparecen cuando el productor desea insertar un nuevo elemento pero el buffer está lleno, o cuando el consumidor desea extraer algo y este está vacío. Cuando ocurra eso, lo mejor es enviar el proceso a dormir y hacer que el otro lo despierte cuando pueda continuar su trabajo.

De esta forma evitamos las esperas activas, pero no se solucionan las carreras críticas: el acceso a cuenta no está restringido.

1. Supongamos que inicialmente el buffer está vacío y comienza ejecutándose el consumidor.
2. El consumidor lee el valor de cuenta, que es 0.
3. Antes de que pueda hacer el sleep, se produce un cambio de contexto al productor.
4. El productor inserta el ítem y realiza el wakeup(consumidor). Como el consumidor nunca realizó su sleep, esta llamada se pierde.
5. Cuando el consumidor recupere la CPU, ejecutará sleep autobloqueándose.
6. Ahora debe continuar el productor, que seguirá insertando ítems hasta que el buffer se llene y entonces realizará su sleep.

Como ya el productor realizó un wakeup, no lo volverá a hacer (cuenta no volverá a ser 1) y ambos procesos quedarán bloqueados de forma indefinida.

 1#define N 100
 2int buffer[N];
 3int cuenta = 0;
 4
 5void productor() {
 6    while (TRUE) {
 7        int item = producir_item();
 8
 9        // Si está lleno, no puedo producir.
10        // Me duermo hasta que haya elementos.
11        if (count == N)
12            sleep();
13
14        // Región crítica
15        insertar_item(item);
16        cuenta++;
17
18        // Si acabo de añadir el primer item,
19        // despertar al consumidor
20        if (count == 1)
21            wakeup(consumidor);
22    }
23}
24
25void consumidor() {
26    while (TRUE) {
27        // Si no hay elementos que consumir,
28        // no puedo continuar. Me duermo.
29        if (cuenta == 0)
30            sleep();
31
32        // Región crítica
33        int item = extraer_item();
34        cuenta--;
35
36        // Si acabo de consumir el último item,
37        // despertar al productor.
38        if (cuenta == N-1)
39            wakeup(productor);
40
41        consumir_item(item);
42    }
43}

Las funciones utilizadas:

• productor: función principal del proceso productor.
• consumidor: función principal del proceso consumidor.
• producir_item: genera y devuelve un nuevo item a insertar.
• insertar_item: inserta el item en la posición cuenta del buffer compartido.
• extraer_item: devuelve el ítem en la posición cuenta-1.
• consumir_item: toma un item y realiza su procesamiento.

Semáforos

También hay llamadas al sistema para crear y destruir semáforos. Es importante borrarlos explícitamente, sino seguirán el en kernel hasta que se apage el computador. Y al volver a ejecutar el programa, usará el valor ya existente, por lo que se puede dar comportamientos inesperados.

Recuerde es posible leer y escribir el valor del semáforo directamente, sin utilizar esta librería de funciones. Sin embargo, se pierde su uso: no estará protegido contra carreras críticas.

Nótese también que down y up son generalizaciones de sleep y wakeup.

A modo de ejemplo, resolvamos el problema del productor-consumidor con semáforos. Para ello necesitamos tres:

• lleno: lleva la cuenta de cúantos elementos hay en el buffer.
• vacio: lleva la cuenta de cúantos huecos hay en el buffer.
• mutex: se trata de un semáforo binario. Se utilizará a modo de candado para la exclusión mutua (MUTual EXclusion) de la región crítica, 0 para candado cerrado (región crítica ocupada) y 1 para candado abierto (región crítica libre).

Los dos primeros se utilizarán por la funcionalidad de sleep y wakeup para la sincronización de los procesos: cuando el buffer esté lleno, vacio será 0, por lo que al hacer un down(&vacio), el productor se bloqueará hasta que haya un hueco. Lo mismo sucede para lleno.

Esta solución funciona perfectamente porque los semáforos resuelven el problema de que se pierdan wakeups.

 1#define N 100
 2int buffer[N];
 3int cuenta = 0;
 4
 5semaforo lleno = 0; // num de elementos en el buffer
 6semaforo vacio = N; // num huecos en el buffer
 7semaforo mutex = 1; // controla el acceso a la región crítica
 8
 9void productor() {
10    while (TRUE) {
11        int item = generar_item();
12
13        // Me bloqueo si el buffer esta lleno.
14        down(&vacio);
15
16        // Entrar a la región crítica.
17        // - 0: región crítica ocupada, me bloqueo.
18        // - 1: región crítica libre, sigo.
19        down(&mutex);
20
21        insertar_item(item);
22        cuenta++;
23
24        // Salgo de la región crítica, despierto al
25        // consumidor por si quería entrar.
26        up(&mutex);
27
28        // Despierto al consumidor por si estaba
29        // el buffer vacío.
30        up(&lleno);
31    }
32}
33
34void consumidor() {
35    while (TRUE) {
36        // Me bloqueo si el buffer esta vacio.
37        down(&lleno);
38
39        // Entro en la región crítica como antes.
40        down(&mutex);
41        int item = extraer_item();
42        cuenta--;
43
44        // Salgo de la región crítica.
45        up(&mutex);
46
47        // Despierto al productor por si estaba
48        // el buffer lleno.
49        up(&vacias);
50
51        consumir_item(item);
52    }
53}

 1#include <semaphore.h>
 2
 3// Abre un semáforo nuevo o ya existente
 4sem_t* sem_open(const char* name, int oflag);
 5sem_t* sem_open(const char* name, int oflag, mode_t mode, unsigned int value);
 6// Cierra el semáforo en el proceso actual
 7sem_t* sem_close(sem_t* sem);
 8// Borra los semáforos del kernel
 9int sem_unlink(const char* name);
10
11// Operación DOWN
12int sem_wait(sem_t* sem);
13// Operación DOWN, en lugar de bloquearse, lanza el error EAGAIN
14int sem_trywait(sem_t* sem);
15// Operación UP
16int sem_post(sem_t* sem);

Mutexes

Cuando no se necesita la habilidad de un semáforo de contar, habitualmente se implementa una versión simplificada, el mutex. Se implementan con facilidad y eficiencia, lo que hace que sean especialmente útiles para la administración de una región crítica y garantizar la exclusión mutua.

Se llama a mutex_lock cuando un proceso o hilo necesita acceder a una región crítica, y a mutex_unlock para indicar que ha terminado con ella. Recuerde que estas operaciones deben ser atómicas.

Esta idea es bastante simple, por lo que son bastante sencillos de implementar cuando hay disponible una instrucción como tsl o xchg.

 1mutex_lock:
 2    tsl reg, MUTEX ;; Copiar MUTEX a reg y poner MUTEX a 1
 3    cmp reg, 0     ;; return si reg == 0
 4    jze ok
 5    call thread_yield ;; sino, ceder la CPU
 6    jmp mutex_lock    ;; volver a probar cuando regrese
 7ok: ret
 8
 9mutex_unlock:
10   move MUTEX, 0 ;; Poner MUTEX a 0 (abierto)
11   ret

Con hilos, todo esto se puede implementar en el espacio de usuario, lo que no requiere llamadas al kernel. Como consecuencia, realizar un mutex_lock es muy rápido.

Nótese la diferencia con el código del ejemplo de uso de la instrucción TSL: cuando no se puede entrar en la región crítica se hace una llamada a thread_yield para dejar la CPU libre, esencialmente realizando una espera activa cediendo la CPU. En una implementación más realista, se debería marcar como bloqueado. Cuando se opera con hilos en espacio de usuario esto es casi obligatorio: no hay un reloj que genere cambios de contexto, por lo que la espera activa de un hilo será indefinida.

1#include <pthread.h> // Compilar con -lpthreads
2
3int pthread_mutex_init(pthread_mutex_t* mutex);
4// Solo se puede destruir si está abierto
5int pthread_mutex_destroy(pthread_mutex_t* mutex);
6
7int pthread_mutex_lock(pthread_mutex_t *mutex);
8int pthread_mutex_trylock(pthread_mutex_t *mutex);
9int pthread_mutex_unlock(pthread_mutex_t *mutex);

Variables de condición

1pthread_mutex_lock(&mutex);
2    while (condición) {
3        pthread_cond_wait(&cond, &mutex);
4    }
5
6    // ~~~ Región crítica ~~~
7
8    pthread_cond_signal(&cond, &mutex);
9pthread_mutex_unlock(&mutex);

1#include <pthreads.h> // Compilar con -lpthreads
2int pthread_cond_init(pthread_cond_t* cond, const pthread_condattr_t* attr);
3int pthread_cond_destroy(pthread_cond_t* cond);

Funciones de creación y borrado de variables de condición. El parámetro attr permite pasar más opciones opciones de creación, pero se puede dejar a NULL. Recuerde que borrar una variable de condición cuando hay hilos bloqueados es undefined behaviour.

Es importante recalcar que estas funciones devuelven un código de error en caso de que algo vaya mal, de lo contrario devuelven 0.

1int pthread_cond_wait(pthread_cond_t* cond, pthread_mutex_t* mutex);

Esta función bloquea el hilo actual y libera el mutex de forma atómica. Es importante que el mutex esté cerrado, sino se dará undefined behaviour.

El hilo se desbloqueará cuando otro lo avise, pero hay que tener en cuenta que cuando se bloqueó seguía en la región crítica. Esto podría causar problemas si dos hilos se despiertan y continuan: ¡nos hemos cargado la exclusión mutua!

Por eso, cuando esta función termine, se debe haber adquerido el mutex para poder continuar.

Como esta función cierra y abre el mutex, es necesario pasarlo por parámetro. En lugar de especificarlo en la hora de creación, es mejor realizarlo en la propia función por si hay mutexes anidados.

1int pthread_cond_signal(pthread_cond_t* cond);
2int pthread_cond_broadcast(pthread_cond_t* cond);

La función signal avisa a un único hilo bloqueado por wait escogido aleatoriamente para que se desbloquee. Como ambos hilos están dentro de la región crítica, se debe volver a evaluar el mutex, y es imposible predecir quién continuará.

Como consecuencia, el código no puede asumir que un hilo u otro continuará con la ejecución. Por ese motivo, es mejor usar estas funciones al final de la región crítica.

Si se lanza un signal pero no hay nadie bloqueado, esta llamada se perderá.

Por otro lado, broadcast despierta a todos los hilos que estén bloqueados por esta variable de condición. Como antes, solo uno de ellos podrá readquerir el mutex y continuar, pero no están bloqueados esperando por el signal.

En la siguiente figura se muestra el funcionamiento de las variables de condición y mutexes:

1. El hilo de la izquierda realiza un lock del mutex y entra en la región crítica.
2. Un poco después, el hilo de la derecha desea hacer lo mismo, pero debe bloquearse. Se queda esperando a que se libere la región crítica.
3. Luego, el hilo de la izquierda realiza un wait, lo que implica liberar el mutex. Este se autobloquea hasta que reciba un signal.
4. Como la región crítica está libre, ahora el hilo de la derecha puede entrar.
5. Este realiza la llamada a signal para despertar al hilo de la izquierda.
6. El hilo de la izquierda se vuelve a bloquear porque necesita acceso a la región crítica: espera a que se libere el mutex.
7. El hilo de la derecha sale de la región crítica, por lo que ahora el hilo de la izquierda puede continuar.

Fíjese en que en el hilo de la izquierda, se espera por dos motivos completamente diferentes. Entender eso es clave para comprender el funcionamiento de las variables de condición.

A modo de ejemplo, resolvamos como antes el problema del productor-consumidor en varios hilos utilizando mutexes y variables de condición:

 1#include <pthread.h>
 2
 3#define NUM_ITEMS 10000
 4#define N 100
 5int buffer[N];
 6int cuenta = 0;
 7
 8pthread_mutex_t mutex; // Mutex que controla el acceso a la región crítica
 9pthread_condc_t cond_cons; // Para bloquear el consumidor si el buffer está vacío
10pthread_condc_t cond_prod; // Para bloquear el productor si el buffer está lleno
11
12void* productor(void* param) {
13    for (int i = 0; i < NUM_ITEMS; i++) {
14        int item = generar_item();
15
16        pthread_mutex_lock(&mutex);
17        while (cuenta >= N) {
18            pthread_cond_wait(&cond_prod, &mutex);
19        }
20
21        insertar_item(item);
22        cuenta++;
23
24        pthread_cond_signal(&cond_cons, &mutex);
25        pthread_mutex_unlock(&mutex);
26    }
27
28    pthread_exit(0);
29}
30
31void* consumidor(void* param) {
32    for (int i = 0; i < NUM_ITEMS; i++) {
33        pthread_mutex_lock(&mutex);
34        while (cuenta <= 0) {
35            pthread_cond_wait(&cond_cons, &mutex);
36        }
37
38        int item = extraer_item();
39        cuenta--;
40
41        pthread_cond_signal(&cond_prod, &mutex);
42        pthread_mutex_unlock(&mutex);
43
44        consumir_item(item);
45    }
46
47    pthread_exit(0);
48}

Monitores

Los ejemplos que se han discutido aquí son bastante sencillos, pero en programas más grandes deja de ser tan claro y un pequeño error puede causar grandes estragos.

Se trata de un concepto del lenguaje (recuerda a una Clase de la Programación Orientada a Objetos), y C no los tiene. El compilador debe estar al tanto de su existencia para poder incluir los bloqueos y desbloqueos de los mutexes o semáforos binarios. Un ejemplo de un lenguaje que soporta los monitores es Java: con la palabra clave syncronized el método se ejecutará de forma exclusiva.

Esta estructura es conceptualmente igual que un mutex, con la ventaja de que da muchos menos errores de programación debido a que el compilador inserta los bloqueos automáticamente.

Como desventaja es que los monitores están diseñados para gestionar memoria compartida. En sistemas distribuidos de varias CPUs, cada uno con su propia memoria y conectadas a través de una red estas primitivas no see pueden utilizar.

 1// Clase principal
 2class ProductorConsumidor {
 3    public static void main(String[] args) {
 4        Monitor m = new Monitor(100);
 5
 6        Productor p = new Productor(m);
 7        Consumidor c = new Consumidor(m);
 8
 9        p.start();
10        c.start();
11    }
12}
13
14// Código del Productor
15class Productor extends Thread {
16    private final Monitor m;
17    public Productor(Monitor m) {
18        this.m = m;
19    }
20
21    // Función principal del hilo
22    public void run() {
23        while (true) {
24            int item = producir_item();
25            m.insertar_item(item);
26        }
27    }
28
29    private int producir_item() {
30        // ...
31    }
32}
33
34// Código del Consumidor
35class Consumidor extends Thread {
36    private final Monitor m;
37    public Consumidor(Monitor m) {
38        this.m = m;
39    }
40
41    // Función principal del hilo
42    public void run() {
43        while (true) {
44            int item = m.extraer_item();
45            consumir_item(item);
46        }
47    }
48
49    private void consumir_item(int item) {
50        // ...
51    }
52}
53
54// Clase Monitor
55class Monitor {
56    // Datos compartidos
57    private int buffer[];
58    private int cuenta;
59    private final int N;
60
61    public Monitor(int N) {
62        this.N = N;
63        buffer = new int[N];
64        int cuenta = 0;
65    }
66
67    // Esto se ejecuta en de forma exclusiva
68    public synchronized void insertar_item(int item) {
69        if (cuenta == N)
70            inactivo();
71
72        buffer[cuenta] = item;
73        cuenta++;
74
75        if (cuenta == 1)
76            notify();
77    }
78
79    // Esto se ejecuta en de forma exclusiva
80    public synchronized int extraer_item() {
81        if (cuenta == 0)
82            inactivo();
83
84        cuenta--;
85        int item = buffer[cuenta];
86
87        if (cuenta == N-1)
88            notify();
89
90        return item;
91    }
92
93    private void inactivo() {
94        try {
95            wait();
96        } catch (InterruptedException e) {
97        }
98    }
99}

Paso de mensajes

Hasta ahora se han tratado con recursos compartidos (principalmente memoria). En la práctica, es posible que dos procesos no puedan compartir memoria por no estar en el mismo computador. Pero gracias al paso de mensajes, es posible utilizar la red para resolver problemas como el del Productor-Consumidor.

Se hace uso de las siguientes primitivas:

• send: envía un mensaje a un destino especificado.
• receive: recibe un mensaje de un origen concreto o cualquiera. Si no hay un mensaje, el proceso se puede bloquear.

Es una relación 1:1, cada send tiene su receive.

Problemas:

• Mensajes perdidos: enviar de vuelta un acuse de recibo o acknowledgement.
• Acuses de recibo perdidos: numerar cada mensaje, y descartar aquellos que tengan el mismo número.
• Autenticación: ¿cómo saber que no me estoy comunicando con un impostor?
• Eficiencia (dentro del mismo computador): es difícil que sea más rápido que usar un semáforo y escribir en memoria. Se ha investigado mucho acerca de esto.

Como siempre, veamos el como resolver el problema del productor-consumidor con paso de mensajes sin usar memoria compartida. Esta solución emplea un total de $N$ mensajes.

1. El consumidor envía $N$ mensajes vacios al productor a modo de petición.
2. Cada vez que el productor reciba un mensaje vacío, enviará uno lleno.
3. A continuación, el consumidor recibe un elemento del productor.
4. Luego el consumidor enviará otro mensaje vacío.

 1#define N 100
 2
 3void productor() {
 4    while (TRUE) {
 5        int item = generar_item();
 6
 7        // Esperar a una peticion (mensaje vacio)
 8        mensaje m;
 9        receive(consumidor, &m);
10
11        crear_mensaje(&m, item);
12        send(consumidor, &m);
13    }
14}
15
16void consumidor() {
17    mensaje m;
18    for (int i = 0; i < N; i++)
19        send(productor, &m); // N mensajes vacios
20
21    while (TRUE) {
22        receive(productor, &m);
23
24        // Extraer el item del mensaje
25        int item = extraer_item(&m);
26
27        // Enviar la peticion de vuelta
28        limpiar(&m)
29        send(produtor, &m);
30
31        consumir_item(item);
32    }
33}

Al igual que en apartados anteriores, cuando se intenta enviar un mensaje a un buzón lleno, el proceso se suspende. Lo mismo cuando se intenta recibir de un buzón vacío.

Para el problema del productor-consumidor, esto permite eliminar completamente los buffers que nosotros habíamos creado.

Barreras de sincronización

Se utiliza solo para sincronizar procesos y hacer que vayan al mismo ritmo. Esto es particularmente útil para la resolución de problemas científicos o de ingeniería. Suelen tener el siguiente formato, por ejemplo, una computación para la predicción meteorológica:

 1// Iteración del algoritmo
 2for (t = 0; t < tmax; t++) {
 3    // Computación por cada dimensión espacial
 4    for (x ...)
 5    for (y ...)
 6    for (z ...) {
 7        // Cálculos complejos
 8    }
 9
10    barrera();
11}

En la siguiente figura:

1. Los procesos realizan su cálculo antes de llegar a la barrera.
2. Todos menos $C$ han llegado a la barrera, por lo que quedan a la espera.
3. Una vez que $C$ llega a la barrera, todos pueden continuar.

Problemas clásicos

A la hora de presentar nuevas soluciones para comunicar y sincronizar procesos, habitualmente se ponen a prueba con alguno de estos problemas. De esta forma se pueden comparar de forma sencilla y ver las ventajas y desventajas de cada uno. Hasta el momento hemos discutido el problema del Productor-Consumidor, pero también existen otros.

Nosotros podemos usar estos problemas para comprender mejor el uso de las primitivas planteadas en este artículo.

El problema de los filósofos hambrientos

La solución obvia es la siguiente:

 1#define N 5 // número de filósofos
 2
 3// i es el número del filósofo
 4void filosofo(int i) {
 5    while (true) {
 6        pensar();
 7
 8        tomar_tenedor(i);
 9        tomar_tenedor((i+1) % N);
10            comer();
11        poner_tenedor(i);
12        poner_tenedor((i+1) % N);
13    }
14}

Pero esta solución está mal: ¿qué sucede si todos los filósofos tienen hambre y desean comer? Tomarán todos a la vez su tenedor izquierdo, pero ninguno de ellos podrá continuar. Este es un caso de interbloqueo: nadie podrá progresar y los filófosos morirán de hambre (inanición).

Si los filósofos esperan un tiempo aleatorio es cierto que se reduciría la probabilidad de interbloqueo, pero eso no soluciona totalmente el problema.

La solución correcta sin interbloqueos y máximo paralelismo es la siguiente:

 1// Por conveniencia
 2#define N   5
 3#define IZQ (i + N-1) % N
 4#define DER   (i + 1) % N
 5
 6// Estado del filósofo
 7#define PENSANDO   0  // El filósofo piensa
 8#define HAMBRIENTO 1  // El filósofo quiere comer
 9#define COMIENDO   2  // El filósofo come
10
11int estado[N]; // Estados de los N filósofos
12semaforo s[N]; // Se usa para bloquear a cada filósofo
13semaforo mutex = 1;
14
15void filosofo(int i) {
16    while (TRUE) {
17        pensar();
18        tomar_tenedores(i);
19        comer();
20        poner_tenedores(i);
21    }
22}
23
24void tomar_tenedores(int i) {
25    // Entrar en región crítica:
26    // acceder al estado de forma exclusiva
27    down(&mutex);
28
29    // Cambiar el estado
30    estado[i] = HAMBRIENTO;
31    // Trata de adquirir los 2 tenedores
32    probar(i);
33
34    // Salir de región crítica
35    up(&mutex);
36    // Bloquear si no se consiguieron los tenedores
37    down(&s[i]);
38}
39
40void poner_tenedores(int i) {
41    down(&mutex);
42    estado[i] = PENSANDO;
43
44    // Acabo de dejar los tenedores:
45    // ¿pueden mis compañeros comer ahora?
46    probar(IZQ);
47    probar(DER);
48
49    up(&mutex);
50}
51
52void probar(int i) {
53    int hambriento  = estado[i] == HAMBRIENTO;
54    int izq_no_come = estado[IZQ] != COMIENDO;
55    int der_no_come = estado[DER] != COMIENDO;
56
57    if (hambriento && izq_no_come && der_no_come) {
58        estado[i] = COMIENDO;
59
60        // Estoy comiendo, por tanto no me bloqueo cuando vuelva
61        // a tomar_tenedores
62        up(&s[i]);
63    }
64}

El problema de los lectores y escritores

 1semaforo mutex = 1;   // controla el acceso a num_lectores
 2semaforo bd = 1;      // controla el acceso a la BD
 3int num_lectores = 0; // Núm de procesos que leen o quieren leer
 4
 5void lector() {
 6    while (TRUE) {
 7        down(&mutex);
 8            num_lectores++;
 9
10            // Si es el primer lector, bloquea la BD contra escrituras
11            if (num_lectores == 1)
12                down(&bd);
13        up(&mutex);
14
15        leer_bd();
16
17        down(&mutex);
18            num_lectores--;
19
20            // Si es el ultimo lector, liberar la BD para escrituras
21            if (num_lectores == 0)
22                up(&bd);
23        up(&mutex);
24
25        usar_datos_leidos();
26    }
27}
28
29void escritor() {
30    while (TRUE) {
31        pensar_datos();
32
33        down(&bd);
34        escribir_bd();
35        up(&bd);
36    }
37}

El mayor peligro de este problema es la inanición: si el escritor espera a que todos los lectores terminen para actualizar un dato, es muy probable que nunca pueda llegar a hacerlo. Esta solución sobre de esto.

Un posible apaño sería evitar añadir nuevos lectores si hay un escritor que desee terminar su trabajo.