[LinuxFocus-icon]
Hogar  |  Mapa  |  Indice  |  Busqueda

Noticias | Arca | Enlaces | Sobre LF
convert to palmConvert to GutenPalm
or to PalmDoc

[Leonardo]
por Leonardo Giordani
<leo.giordani(at)libero.it>

Sobre el autor:

Estudiante en la Facultad de Ingeniería de Telecomunicaciones en la Politecnica de Milán, trabaja como administrador de redes y está interesado en la programación (mayormente en ensamblador y C/C++). Desde 1999 trabaja casi únicamente con Linux/Unix.

Taducido al español por:
Miguel Alfageme Sánchez <malfageme(at)terra.es>

Contenidos:


 

Programación concurrente - comunicación entre procesos

[run in paralell]

Resumen:

Esta serie de artículos tiene el propósito de introducir al lector al concepto de multitarea y a sus implementaciones en el sistema operativo Linux. Empezando por los conceptos teóricos que componen la base de la multitarea, terminaremos escribiendo una aplicación completa demostrando la comunicación entre procesos, con un protocolo de comunicaciones simple pero eficiente

Los prerrequisitos para la comprensión del artículo son:

  • Un mínimo conocimiento de la shell
  • Un conocimiento básico del lenguaje C (sintaxis, bucles, librerías)
Se debería leer el primer artículo de esta serie porque se trata de una base para este: Noviembre 2002, artículo 272.
_________________ _________________ _________________

 

Introducción

Aquí nos encontramos de nuevo lidiando con la multitarea en Linux. Tal y como vimos en el artículo anterior, dividir la ejecución de un programa necesita únicamente unas pocas líneas de código, porque el sistema operativo se encarga de la inicialización, gestión y temporización de los procesos que creamos.

Este servicio proporcionado por el sistema operativo es fundamentel, es la ejecución de la 'supervisión de los procesos'; así, los procesos son ejecutados en un entorno dedicado. El hecho de perder el control de la ejecución de los procesos le conlleva al desarrollador un problema de sincronización, resumido en esta pregunta: ¿cómo es posible hacer que dos procesos independientes trabajen juntos?

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. Por ejemplo: tenemos dos procesos "A" y "B" y un entero "d". El proceso A encrementa d en 1, el proceso B lo muestra. Escribiéndolo con un metalenguaje, podemos expresarlo de esta forma

A { d->d+1 } & B { d->salida }

donde el "&" identifica una ejecución concurrente. Una primera posible ejecución es

(-) d = 5 (A) d = 6 (B) salida = 6

Pero si el proceso B es ejecutado primero, obtendremos

(-) d = 5 (B) salida = 5 (A) d = 6

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.

En el artículo precedente ya hemos hablado sobre la primera forma de sincronización a través del uso de la función waitpid(2), que permite a un proceso esperar la finalización de otro antes de continuar. De hecho, esto nos permite solucionar algunos de los conflictos producidos por la lectura y escritura: una vez que el conjunto de datos en el cual trabajará un proceso P1 ha sido definido, un proceso P2 que trabaja en el mismo conjunto de datos o en un subconjunto de él deberá esperar por la finalizació de P1 antes de que pueda proceder con su propia ejecució.

Claramente este método representa una primera solución, pero está muy lejos de la mejor, porque P2 tiene que permanecer inactivo durante un tiempo que puede ser muy largo, esperando que P1 termine su ejecución, incluso si no va a haber ya más procesamiento con los datos comunes. Así, debemos incrementar la granularidad de nuestro control, i.e. regular el aceso a los datos individuales o al conjunto. 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).  

SysV keys

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 claves IPCS. Una clave 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(3)

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

La idea de un semáforo para el contro del tráfico de coches se puede emplear sin grandes modificaciones para el control de acceso a datos. Un semáforo es una estructura particular que contiene un valor mayor o igual a cera y que maneja una cola de procesos esperando por unas condiciones particulares en el propio semáforo. Aunque parezcan sencillos, los semáforos son muy potentes, lo que incrementa consecuentemente las complicaciones. Empecemos (como siempre) dejando fuera el control de errores: lo meteremos en nuestro código cuando encaremos un programa más complejo.

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.

Con un semáforo se puede realizar una tarea diferente, el contador de recursos: el valor que tiene representa, en este caso, el número de recursos disponibles (por ejemplo el número de celdas de memoria disponibles).

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(2)

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); para una descripción completa léase la página del manual ipc(5). 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(2)

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(2)

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:%d\n", getpid());
}
else{
printf("---> Process:%d  BUFFER FULL\n", 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:%d\n", getpid());
}
else printf("<--- Process:%d  BUFFER EMPTY\n", 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:%d\n", getpid());
}
else{
printf("---> Process:%d  BUFFER FULL\n", 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:%d\n", getpid());
}
else printf("<--- Process:%d  BUFFER EMPTY\n", 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.

En el siguiente artículo hablaremos acerca de las colas de mensajes, otra estructura para la comunicación entre procesos (InterProcess Communication) y sincronización. Como siempre, si escribe algo sencillo utilizando lo que ha aprendido de aquí envíemelo junto con su nombre y su dirección de e-mail. Estaré encantado de leerlo. ¡Buen trabajo!  

Lecturas recomendadas

 

Formulario de "talkback" para este artículo

Cada artículo tiene su propia página de "talkback". A través de esa página puedes enviar un comentario o consultar los comentarios de otros lectores
 Ir a la página de "talkback" 

Contactar con el equipo de LinuFocus
© Leonardo Giordani, FDL
LinuxFocus.org
Información sobre la traducción:
it --> -- : Leonardo Giordani <leo.giordani(at)libero.it>
it --> en: Leonardo Giordani <leo.giordani(at)libero.it>
en --> es: Miguel Alfageme Sánchez <malfageme(at)terra.es>

2003-04-25, generated by lfparser version 2.34