El problema es más complejo de lo que parece: no es únicamente una cuestión de sincronización de la ejecución de los procesos, sino también de compartición de datos, tanto en modo lectura como en escritura.
Hablemos sobre algunos problemas clásicos de acceso concurrente de datos; si dos procesos leen el mismo conjunto de datos esto obviamente no es un problema, y la ejecución es CONSISTENTE. Ahora si dejamos a uno de los dos procesos modificar el conjunto de datos: el otro devolverá resultados diferentes de acuerdo al momento en el cual lee el conjunto de datos, antes o después de la escritura por parte del primer proceso.
Entendemos inmediatamente cómo es de importante gestionar correctamente estas situaciones: el riesgo de INCONSISTENCIA de datos es grande e inaceptable. Intentemos pensar que los conjuntos de datos representan nuestra cuenta bancaria y nunca subestimaremos este problema.
La solución a este problema viene dada por un conjunto de primitivas de la librería estándar conocida como SysV IPC (System V InterProcess Communication).
Llaves SysV
Antes de encarar los argumentos estrictamente relacionados con la teoría de la concurrencia y su implementación introduciremos una estructura SysV típica: las llaves IPCS. Una llave IPC es un número utilizado para identificar unívocamente una estructura de control IPC (descrita más adelante), pero también puede ser utilizada para generar identificadores genéricos, p.e. para organizar estructuras no IPC. Una clave se puede crear con la función ftok()
key_t ftok(const char *pathname, int proj_id);
que utiliza el nombre de un fichero existente (pathname) y un entero. No se puede asegurar que la clave sea única, porque los parámetros tomados del fichero (número de i-nodo y número de dispositivo) pueden dar lugar a combinaciones idénticas. Una buena solución consiste en crear una pequeña librería que revise las claves asignadas y evite los duplicados.
Semáforos
Los semáforos pueden utilizarse para controlar el acceso a recursos: el valor del semáforo representa el número de procesos que pueden acceder al recurso; cada vez que un proceso accede al recurso el valor del semáforo debe ser decrementado e incrementado de nuevo cuando el recurso sea liberado. Si el recurso es exclusivo (p.e. sólo un proceso puede acceder) el valor inicial del semáforo será 1.
Consideremos un caso práctico, en el que el se utilizará el tipo del semáforo: imaginemos que tenemos un buffer en el cual varios procesos S1,…,Sn pueden escribir pero del cual únicamente un proceso L puede leer; además, las operaciones no se pueden realizar al mismo tiempo (i.e. en un momento dado sólo un proceso está operando con el buffer). Obviamente los procesos S pueden escribir siempre excepto cuando el buffer está lleno, mientras que el proceso L puede leer sólo si el buffer no está vacío. Así, necesitamos tres semáforos: el primero gestionará el acceso al recurso, el segundo y el tercero seguirá la pista de cuántos elementos hay en el buffer (veremos más adelante por qué dos semáforos no son suficientes).
Considerando que el acceso al buffer es exclusivo el primer semáforo será uno binario (su valor será 0 o 1), mientras que el segundo y el tercero reflejará valores relacionados a la dimensión del buffer.
Aprendamos cómo se implementan los semáforos en C utilizando las primitivas SysV. La función que crea un semáforo es semget()
int semget(key_t key, int nsems, int semflg);
donde key es la clave IPC, nsems es el número de semáforos que queremos crear y semflg es el control de acceso implemenado con 12 bits, los 3 primeros relacionados con las políticas de creación y los otros 9 con los accesos de lectura y escritura del usuario, grupo y otros (nótese la similitud con el sistema de ficheros Unix).Tal y como notamos SysV gestiona conjuntos de semáforos en vez de semáforos únicos, resultando un código más compacto.
Creemos nuestro primer semáforo
#include "stdio.h"
#include "stdlib.h"
#include "linux/types.h"
#include "linux/ipc.h"
#include "linux/sem.h"
int main(void){
key_t key;
int semid;
key = ftok("/etc/fstab", getpid());
/* creamos un conjunto de semaforos con un solo semaforo: */
semid = semget(key, 1, 0666 | IPC_CREAT);
return 0;
}
Avanzando un poco más, tenemos que aprender cómo gestionar y eliminar semáforos; la gestión del semáforo se realiza mediante la primitiva semctl()
int semctl(int semid, int semnum, int cmd, ...)
que realiza la operación identificada por cmd en el conjunto semid y (si la acción lo requiere) en el semáforo semnum. Introduciremos algunas opciones cuando las necesitemos, pero en la página del man se puede encontrar una lista completa. Dependiendo de la acción cmd puede ser necesario especificar otro argumento para la función, cuyo tipo es
union semun {
int val; /* valor para SETVAL */
struct semid_ds *buf; /* buffer para IPC_STAT, IPC_SET */
unsigned short *array; /* array para GETALL, SETALL */
/* parte especifica Linux: */
struct seminfo *__buf; /* buffer para IPC_INFO */
};
Para establecer el valor del semáforo se debe utilizar la directiva SETVAL y el valor se tiene que especificar en la union semun; modifiquemos el programa anterior estableciendo el valor del semáforo a 1
[...] /* creamos un conjunto de semaforos con un solo semaforo: */ semid = semget(key, 1, 0666 | IPC_CREAT); /* establecemos el valor del semaforo de 0 a 1 */ arg.val = 1; semctl(semid, 0, SETVAL, arg); [...]
Entonces tenemos que liberar el semáforo liberando las estructuras utilizadas para su gestión; esta tarea se realiza con la directiva IPC_RMID de semctl. Esta directiva elimina el semáforo y envía un mensaje a todos los procesos esperando para conseguir el acceso al recurso. Una última modificación al programa es
[...] /* establecemos el valor del semaforo de 0 a 1 */ arg.val = 1; semctl(semid, 0, SETVAL, arg); /* liberamos el semaforo */ semctl(semid, 0, IPC_RMID); [...]
Tal y como hemos visto antes, cear y gestionar una estructura para controlar una ejecución concurrente no es difíl; cuando introduzcamos gestión de errores las cosas se volverán más complicadas, pero sólo desde el punto de vista de la complejidad del código.
El semáforo se puede utilizar a través de la función semop()
int semop(int semid, struct sembuf *sops, unsigned nsops);
donde semid es el identificador del conjunto, sops un array que contiene las operaciones a realizar y nsops el número de estas operaciones. Cada operación está representada por una estructura sembuf.
unsigned short sem_num; short sem_op; short sem_flg;
i.e. por el número de semáforo en el conjunto (sem_num), la operación (sem_op) y un flag estableciendo la política de espera; por ahora dejemos sem_flg a 0. Las operaciones que podemos especificar son números enteros y siguen estas reglas:
1. sem_op < 0
Si el valor absoluto del semáforo es mayor o igual que el de sem_op la operación continúa y se añade sem_op al valor del semáforo (realmente se resta, número negativo). Si el valor absoluto de sem_op es menor que el valor del semáforo el proceso se duerme hasta que esté disponible tal número de recursos.
2. sem_op = 0
El proceso se duerme hasta que el valor del semáforo alcance 0.
3. sem_op > 0
El valor de sem_op se añade al valor del semáforo, liberando los recursos obtenidos previamente.
El siguiente programa intenta mostrar cómo utilizar semáforos implementando el ejemplo del buffer anterior: crearemos 5 procesos denominados W (escritores) y un proceso R (lector). Cada proceso W intenta obtener el control del recurso (el buffer) bloqueándolo a través de un semáforo y, si el buffer no está vacío, inserta un elemento en él y libera el recurso. El proceso R intenta bloquear el recurso, toma un elemento del buffer si no está vacío y desbloquea el recurso.
La lectura y escritura del buffer es sólo virtual: esto sucede porque, tal y como se vió en el artículo anterior, cada proceso tiene su propio espacio de memoria y no puede acceder al de otro proceso. Esto hace imposible la correcta gestión del buffer con 5 procesos, porque cada uno verá su propia copia del buffer. Esto cambiará cuando hablemos sobre la memoria compartida, pero mejor aprendamos las cosas paso a paso.
¿Por qué necesitamos 3 semáforos? El primero (número 0) actúa como un bloqueo de acceso al buffer, y tiene un valor máximo de 1, mientras que los otros dos gestionan las condiciones de desbordamiento, tanto por arriba como por abajo. Un único semáforo no puede gestionar ambas situaciones, debido a que semop actúa en un único sentido.
Aclaremos un poco esto: con un semáforo (llamado O), cuyo valor representa el número de espacios vacíos en el buffer. Cada vez que un proceso W inserta algo en el buffer, decrementa el valor del samáforo en una unidad, hasta que el valor llegue a 0, i.e. el buffer esté lleno. Este semáforo no puede gestionar la condición de desbordamiento por abajo: el proceso R, de hecho, puede incrementar su valor sin límites. Necesitamos, por tanto, un semáforo especial (llamado U), cuyo valor represente el número de elementos en el buffer. Cada vez que un proceso W inserte un elemento en el buffer también incrementará el valor del semáforo U y decrementará el del semáforo O. Por el contrario, el proceso R decrementará el valor del semáforo U e incrementará el del semáforo O.
Así, la condición de desbordamiento por arriba estará identificada por la imposibilidad de decrementar el semáforo O, y la condición de desbordamiento por abajo por la imposibilidad de decrementar el semáforo U.
#include "stdio.h"
#include "stdlib.h"
#include "errno.h"
#include "linux/types.h"
#include "linux/ipc.h"
#include "linux/sem.h"
int main(int argc, char *argv[])
{
/* IPC */
pid_t pid;
key_t key;
int semid;
union semun arg;
struct sembuf lock_res = {0, -1, 0};
struct sembuf rel_res = {0, 1, 0};
struct sembuf push[2] = {1, -1, IPC_NOWAIT, 2, 1, IPC_NOWAIT};
struct sembuf pop[2] = {1, 1, IPC_NOWAIT, 2, -1, IPC_NOWAIT};
/* Other */
int i;
if(argc < 2){
printf("Usage: bufdemo [dimensione]n");
exit(0);
}
/* Semaphores */
key = ftok("/etc/fstab", getpid());
/* Create a semaphore set with 3 semaphore */
semid = semget(key, 3, 0666 | IPC_CREAT);
/* Initialize semaphore #0 to 1 - Resource controller */
arg.val = 1;
semctl(semid, 0, SETVAL, arg);
/* Initialize semaphore #1 to buf_length - Overflow controller */
/* Sem value is 'free space in buffer' */
arg.val = atol(argv[1]);
semctl(semid, 1, SETVAL, arg);
/* Initialize semaphore #2 to buf_length - Underflow controller */
/* Sem value is élements in buffer' */
arg.val = 0;
semctl(semid, 2, SETVAL, arg);
/* Fork */
for (i = 0; i < 5; i++){
pid = fork();
if (!pid){
for (i = 0; i < 20; i++){
sleep(rand()%6);
/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Lock a free space - sem #1 / Put an element - sem #2*/
if (semop(semid, &push, 2) != -1){
printf("---> Process:%dn”, getpid());
}
else{
printf(”—> Process:%d BUFFER FULLn”, getpid());
}
/* Release resource */
semop(semid, &rel_res, 1);
}
exit(0);
}
}
for (i = 0;i < 100; i++){
sleep(rand()%3);
/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Unlock a free space - sem #1 / Get an element - sem #2 */
if (semop(semid, &pop, 2) != -1){
printf("<--- Process:%dn", getpid());
}
else printf("<--- Process:%d BUFFER EMPTYn", getpid());
/* Release resource */
semop(semid, &rel_res, 1);
}
/* Destroy semaphores */
semctl(semid, 0, IPC_RMID);
return 0;
}
Comentemos las partes más interesantes del código:
struct sembuf lock_res = {0, -1, 0};
struct sembuf rel_res = {0, 1, 0};
struct sembuf push[2] = {1, -1, IPC_NOWAIT, 2, 1, IPC_NOWAIT};
struct sembuf pop[2] = {1, 1, IPC_NOWAIT, 2, -1, IPC_NOWAIT};
Estas 4 líneas son las acciones que podemos realizar en nuestro conjunto de semáforos: las dos primeras son acciones individuales, mientras que las otras son dobles. La primera acción, lock_res, intenta bloquear el recurso: decrementa el valor del primer semáforo (número 0) en una unidad (si el valor no es cero) y la política adoptada si el recurso está ocupado es ninguna (i.e. el proceso espera). La acción rel_res es idéntica a lock_res, pero el recurso se libera (el valor es positivo).
Las acciones push y pop son un poco especiales. Son arrays de dos acciones, la primera sobre el semáforo número 1 y la segunda sobre el semáforo número 2; mientras que el primero se incrementa el segundo se decrementa y viceversa, pero la política ya no es de espera: IPC_NOWAIT fuerza al proceso a continuar la ejecución si el recurso está ocupado.
/* Initialize semaphore #0 to 1 - Resource controller */ arg.val = 1; semctl(semid, 0, SETVAL, arg); /* Initialize semaphore #1 to buf_length - Overflow controller */ /* Sem value is 'free space in buffer' */ arg.val = atol(argv[1]); semctl(semid, 1, SETVAL, arg); /* Initialize semaphore #2 to buf_length - Underflow controller */ /* Sem value is élements in buffer' */ arg.val = 0; semctl(semid, 2, SETVAL, arg);
Aquí inicializamos el valor de los semáforos: el primero a 1 porque controla el acceso en exclusiva a un recurso, el segundo a la longitud del buffer (dado en la línea de comando) y el tercero a 0, tal y como comentamos antes acerca del desbordamiento por arriba y por abajo.
/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Lock a free space - sem #1 / Put an element - sem #2*/
if (semop(semid, &push, 2) != -1){
printf("---> Process:%dn", getpid());
}
else{
printf("---> Process:%d BUFFER FULLn", getpid());
}
/* Release resource */
semop(semid, &rel_res, 1);
El proceso W intenta bloquear el recurso a través de la acción lock_res; una vez hecho esto, realiza un push y lo avisa por la salida estándar: si la operación no se puede realizar avisa de que el buffer está lleno. Después de esto libera el recurso.
/* Try to lock resource - sem #0 */
if (semop(semid, &lock_res, 1) == -1){
perror("semop:lock_res");
}
/* Unlock a free space - sem #1 / Get an element - sem #2 */
if (semop(semid, &pop, 2) != -1){
printf("<--- Process:%dn", getpid());
}
else printf("<--- Process:%d BUFFER EMPTYn", getpid());
/* Release resource */
semop(semid, &rel_res, 1);
El proceso R actúa más o menos como el proceso W: bloquea el recurso, realiza un pop y libera el recurso.
