Hogar  |  Mapa  |  Indice  |  Busqueda

Convert to GutenPalm or to PalmDoc 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: Introducción SysV keys Semáforos Lecturas recomendadas Formulario de "talkback" para este artículo

Programación concurrente - comunicación entre procesos 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

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 }

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

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

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

key_t ftok(const char *pathname, int proj_id);

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.

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);

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;
}

int semctl(int semid, int semnum, int cmd, ...)

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 */
};

[...]

/* 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);

[...]

[...]

/* 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);

[...]

El semáforo se puede utilizar a través de la función semop(2)

int semop(int semid, struct sembuf *sops, unsigned nsops);

unsigned short sem_num; short sem_op; short sem_flg;

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.

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;
}

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};

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);

/* 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);

/* 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);

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

• Silberschatz, Galvin, Gagne, Operating System Concepts - Sixth Edition, Wiley&Sons, 2001
• Tanenbaum, WoodHull, Operating Systems: Design and Implementation - Second Edition, Prentice Hall, 2000
• Stallings, Operating Systems - Fourth Edition, Prentice Hall, 2002
• Bovet, Cesati, Understanding the Linux Kernel, O'Reilly, 2000
• The Linux Programmer's Guide: http://www.tldp.org/LDP/lpg/index.html
• Linux Kernel 2.4 Internals http://www.tldp.org/LDP/lki/lki-5.html

Formulario de "talkback" para este artículo

2003-04-25, generated by lfparser version 2.34

mirror server hosted at Truenetwork, Russian Federation.