Programmation en temps partag� - communication entre processus

ArticleCategory:

AuthorImage:

TranslationInfo:

original in it: Leonardo Giordani

it to en: Leonardo Giordani

en to fr: Paul Delannoy

AboutTheAuthor:

Etudiant ing�nieur en t�l�communications � l'�cole Polytechnique de Milan, il travaille comme administrateur r�seau et s'int�resse � la programmation (surtout en Assembleur et en C/C++). Depuis 1999 il ne travaille que sous Linux/Unix.

Abstract:

Pour comprendre l'article il faudrait avoir :

• Une connaissance minimale du shell
• Une connaissance basique du langage C (syntaxe, boucles, biblioth�ques)

ArticleIllustration:

ArticleBody:

Introduction

Ce service offert par le syst�me est fondamental, c'est la 'supervision de processus' ; chaque processus est ex�cut� dans un environnement qui lui est d�di�. Le d�veloppeur, qui perd ainsi le contr�le du d�roulement de l'ex�cution, a donc un probl�me de synchronisation, qui se r�sume par la question : comment est-il possible de faire collaborer deux processus distincts ?

Ce probl�me est plus complexe qu'il ne semble : il ne suffit pas de synchroniser l'ex�cution des processus, mais aussi de partager des donn�es, � la fois en mode lecture ou �criture.

Parlons un peu des probl�mes classiques pos�s par l'acc�s concurrentiel � des donn�es ; si deux processus lisent le m�me ensemble de donn�es, il n'y a pas de probl�me majeur et l'ex�cution est dite CONSISTENTE. Mais si un des processus est autoris� � modifier ces donn�es, le second pourra renvoyer des r�sultats diff�rents selon l'instant o� il lira les donn�es, avant ou apr�s que le premier ait �crit ces donn�es modifi�es. Par exemple : deux processus "A" et "B" partagent un entier "d". Le processus A incr�mente d de 1, le processus B affiche sa valeur. Dans un meta-langage nous pourrions l'exprimer ainsi :

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

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

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

Nous avons abord� une premi�re forme de synchronisation de processus dans l'article pr�c�dent, avec la fonction waitpid(2), qui force un processus � attendre l'ach�vement d'un autre avant de poursuivre sa propre ex�cution. Ceci permet en fait de r�gler une partie des conflits provoqu�s par la lecture et l'�criture des donn�es : d�s que l'ensemble de donn�es sur lequel un processus P1 doit travailler a �t� d�fini, un processus P2 qui doit travailler sur le m�me ensemble ou sur un sous-ensemble doit attendre l'ach�vement de P1 avant de commencer lui-m�me � s'ex�cuter.

Si cette m�thode pr�sente une solution, il est clair qu'elle n'est pas la meilleure, car P2 va devoir attendre un temps ind�termin�, qui peut �tre long, que P1 termine son ex�cution, et cela m�me s'il n'y a plus aucun travail sur des donn�es partag�es. Nous devons donc augmenter la granularit� de notre contr�le, c'est-�-dire, r�genter l'acc�s � une seule donn�e ou un seul jeu de donn�es. La solution � ce probl�me est un ensemble de primitives de la biblioth�que standard connue sous le nom de SysV IPC (System V InterProcess Communication).

Les cl�s de SysV

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

S�maphores

Les s�maphores sont utilisables dans le contr�le d'acc�s � une ressource : la valeur du s�maphore repr�sente le nombre de processus qui peuvent acc�der � la ressource; chaque acc�s d'un processus � la ressource d�cr�mente la valeur, qui sera incr�ment�e � nouveau lorsque la ressource sera lib�r�e. Dans le cas d'une ressource exclusive (i.e. un seul processus peut y acc�der) la valeur initiale du s�maphore sera 1.

Une t�che diff�rente peut �tre accomplie par un s�maphore, c'est le compteur de ressource : sa valeur est dans ce cas le nombre de ressources disponibles (par exemple le nombre de plages m�moire libres).

Examinons un cas r�el dans lequel nous utiliserons des types de s�maphore : imaginons un tampon dans lequel plusieurs processus S1,..., Sn peuvent �crire mais dans lequel un seul processus L peut lire; de plus, les op�rations ne peuvent �tre simultan�es (i.e. un seul processus agit sur le tampon � un instant donn�). Bien s�r les processus S peuvent toujours �crire, sauf quand le tampon est plein, alors que L ne peut lire que si le tampon n'est pas vide. Donc nous allons utiliser trois s�maphores : un premier pour l'acc�s � la ressource, un second et un troisi�me pour compter les �l�ments pr�sents dans le tampon (nous verrons plus tard pourquoi deux s�maphores ne suffisent pas).

Comme le tampon est une ressource d'acc�s exclusif le premier s�maphore peut �tre binaire (sa valeur sera 0 ou 1), alors que les deux autres auront des valeurs li�es � la taille du tampon.

Etudions comment mettre en oeuvre ces s�maphores en C gr�ce aux primitives de SysV. La fonction qui cr�e un s�maphore se nomme semget(2)

int semget(key_t key, int nsems, int semflg);

Cr�ons notre premier s�maphore

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

  /* create a semaphore set with only 1 semaphore: */
  semid = semget(key, 1, 0666 | IPC_CREAT);

  return 0;
}

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

union semun {
 int val;                  /* value for SETVAL */
 struct semid_ds *buf;     /* buffer for IPC_STAT, IPC_SET */
 unsigned short *array;    /* array for GETALL, SETALL */
                           /* Linux specific part: */
 struct seminfo *__buf;    /* buffer for IPC_INFO */
};

[...]

  /* create a semaphore set with only 1 semaphore */
  semid = semget(key, 1, 0666 | IPC_CREAT);

  /* set value of semaphore number 0 to 1 */
  arg.val = 1;
  semctl(semid, 0, SETVAL, arg);

[...]

[...]

   /* set value of semaphore number 0 to 1 */
  arg.val = 1;
  semctl(semid, 0, SETVAL, arg);

  /* deallocate semaphore */
  semctl(semid, 0, IPC_RMID);

[...]

Le s�maphore peut maintenant �tre utilis� avec la fonction 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 la valeur absolue du s�maphore est plus grande ou �gale � celle de sem_op l'op�ration est effectu�e et sem_op est ajout�e � la valeur du s�maphore (en fait elle est soustraite puisque sem_op est n�gatif). Si la valeur absolue de sem_op est inf�rieure � la valeur du s�maphore le processus se met en sommeil jusqu'� ce que la quantit� de ressources requise soit disponible.
2. sem_op = 0
   Le processus est en sommeil jusqu'� ce que la valeur du s�maphore atteigne 0.
3. sem_op > 0
   La valeur de sem_op est ajout�e � celle du s�maphore, lib�rant les ressources utilis�es jusqu'alors.

Ces lectures et �critures sont virtuelles : en effet, comme nous l'avons vu dans l'article pr�c�dent, chaque processus dispose de son propre espace m�moire et ne peut acc�der � celui d'un autre processus. Cela emp�che la gestion correcte du tampon par 5 processus, puisque chacun voit sa propre copie du tampon. Pour l'instant nous devons renoncer au v�ritable �change de donn�es jusqu'� ce que nous abordions la m�moire partag�e.

Pourquoi faut-il 3 s�maphores ? Le premier (num�ro 0) agit comme verrou d'acc�s au tampon et poss�de une valeur maximale de 1, alors que les deux autres g�rent les conditions de d�bordement par le haut (overflow) ou par le bas (underflow). Un seul s�maphore ne peut pas g�rer les deux situations, puisque semop n'agit que dans un sens.

Soyons encore plus clairs : avec un seul s�maphore (nomm� O), dont la valeur repr�sente le nombre d'emplacements libres dans le tampon. Chaque fois qu'un processus S �crit quelque chose dans le tampon il d�cr�mente de un la valeur du s�maphore, jusqu'� ce qu'elle atteigne z�ro, i.e. que le tampon soit plein. Ce s�maphore ne peut g�rer la condition d'underflow : le processus R peut augmenter sa valeur sans limite. Il nous faut donc un s�maphore sp�cial (nomm� U), dont la valeur repr�sente le nombre d'�l�ments dans le tampon. Chaque fois qu'un processus W �crit un �l�ment dans le tampon il incr�mente la valeur du s�maphore U et d�cr�mente celle du s�maphore O. A l'inverse, le processus R d�cr�mente la valeur du s�maphore U et incr�mente celle du s�maphore O.

La condition d'overflow est ainsi identifi�e par l'impossibilit� de d�cr�menter le s�maphore O et la condition d'underflow par l'impossibilit� de d�cr�menter le s�maphore 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 [dimension]\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 'elements 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};

Les actions push et pop sont plus particuli�res. Ce sont des tableaux de 2 actions, la premi�re sur le s�maphore num�ro 1 et la seconde sur le s�maphore num�ro 2; lorsque la valeur du premier est incr�ment�e la valeur du second est d�cr�ment�e et vice versa, mais le comportement n'est plus l'attente : IPC_NOWAIT force le processus � continuer son ex�cution si la ressource est occup�e.

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

Nous parlerons dans le prochain article des files d'attente de messages, qui constituent une autre structure de l'IPC (InterProcess Communication) et de la synchronisation. Comme d'habitude si vous �crivez quelque chose de simple � partir de ce que vous avez appris ici, envoyez-le moi, avec votre nom et votre adresse mail, je serai heureux de le lire. Bon travail !

Lectures recommand�es

• 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