Sémaphores.
Les sémaphores peuvent être utilisés pour fournir un accès exclusif à certaines ressources de la machine, ou pour limiter le nombre de processus qui utilisent en même temps une ressource. Les sémaphores permettent ainsi à plusieurs processus de se synchroniser (cf Aide).
Mémoire partagée.
Le partage de mémoire entre plusieurs processus est le moyen le plus rapide d'échange de données. Pour pouvoir partager de la mémoire, on doit utiliser les primitives suivantes :
- shmget construit le segment de mémoire partagée ;
- shmctl permet d'intervenir sur ce segment ;
- shmat permet à un processus de s'attacher ce segment ;
- shmdt permet à un processus de se détacher du segment.
Le but de ce TP est d'étudier la synchronisation inter-processus en utilisant les sémaphores et la mémoire partagée.
Exercice 1 - Lecteurs-Rédacteurs
Dans cet exercice, on considère la situation où une zone de mémoire partagée est accédée simultanément en lecture et en écriture. Il y a donc deux types de processus, d'une part des processus lecteurs et d'autre part des processus rédacteurs.
Deux objectifs doivent être atteints: le contenu de la zone de mémoire doit évidemment rester cohérent (donc les écritures ne doivent pas avoir lieu en même temps) et les lecteurs doivent lire une information stable (c'est-à-dire que les lecteurs ne doivent pas lire une information en cours de modification). Pour réaliser ces deux objectifs, il faut sur la zone de mémoire partagée : soit une seule écriture en cours, soit une ou plusieurs lectures en cours (les lectures simultanées ne gênant pas).
Un processus rédacteur accède toujours seul à la zone de mémoire (c'est-à-dire qu'il effectue des accès en exclusion mutuelle des autres rédacteurs et des lecteurs). Un lecteur exclut les rédacteurs mais pas les autres lecteurs (c'est-à-dire, seul le premier lecteur doit s'assurer qu'il n'y a pas d'accès en écriture en cours et seul le dernier lecteur doit réveiller un éventuel rédacteur). Il faut donc compter le nombre de lecteurs qui accèdent à la zone de mémoire partagée. Cette valeur doit rester cohérente (c'est-à-dire stockée dans une variable accédée en exclusion mutuelle).
Programmer un schéma lecteurs-rédacteur entre un processus père et ses deux fils pour l'accès à une variable commune. Le processus père modifie la variable commune en la multipliant par 10. Les processus fils lisent la valeur commune puis l'affiche.
L'approche décrite ci-dessus évite les interblocages mais malheureusement elle peut aboutir à un phénomène presque aussi grave : si un rédacteur tente d'accèder à la zone de mémoire partagée alors qu'un lecteur est dans la section critique, il peut attendre indéfiniment si un nouveau lecteur arrive avant que tous les lecteurs précédents ne partent. Modifier le programme précédent pour éviter ce phénomène de famine.
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/wait.h> #include <sys/ipc.h> #include <sys/shm.h> #include <sys/sem.h> int main () { int i,pid; int semid; struct sembuf operation; int shmid; int *mem,*NL; // allocation région de mémoire partagée if ((shmid = shmget(45,1024,0750|IPC_CREAT|IPC_EXCL)) == -1) perror ("Problème création mémoire partagée\n"); if ((mem=shmat(shmid,NULL,0)) == NULL) perror ("Problème shmat\n"); // création de deux sémaphores if ((semid = semget(12,2,IPC_CREAT|IPC_EXCL|0600)) == -1) perror ("Problème semget\n"); // Sémaphore MUTEX initialisé à 1 if ((semctl(semid,0,SETVAL,1)) == -1) perror ("Problème semctl\n"); // Sémaphore ACCES initialisé à 1 if ((semctl(semid,1,SETVAL,1)) == -1) perror ("Problème semctl\n"); NL=mem+1; pid=fork(); if (pid==0) { // Le fils 1 est lecteur : il lit la variable i { i=1; while(i<30) { // P(MUTEX) operation.sem_num=0; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *NL=*NL+1; if (*NL == 1) { // P(ACCES) operation.sem_num=1; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); } // V(MUTEX) operation.sem_num=0; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); printf("Lecteur 1 : variable = %d\n",*mem); // P(MUTEX) operation.sem_num=0; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *NL=*NL-1; if (*NL == 0) { // V(ACCES) operation.sem_num=1; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); } // V(MUTEX) operation.sem_num=0; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); i=i+1; } } exit(0); } else { pid=fork(); if (pid == 0) { // Le fils 2 est lecteur : il lit la variable i { i=1; while(i<30) { // P(MUTEX) operation.sem_num=0; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *NL=*NL+1; if (*NL == 1) { // P(ACCES) operation.sem_num=1; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); } // V(MUTEX) operation.sem_num=0; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); printf("Lecteur 2 : variable = %d\n",*mem); // P(MUTEX) operation.sem_num=0; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *NL=*NL-1; if (*NL == 0) { // V(ACCES) operation.sem_num=1; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); } // V(MUTEX) operation.sem_num=0; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); i=i+1; } } exit(0); } else { // Le père est rédacteur : il modifie la valeur i i=1; while(i<10) { // P(ACCES) operation.sem_num=1; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *mem=i*10; printf("Rédacteur : variable = %d\n",*mem); // V(ACCES) operation.sem_num=1; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); i=i+1; } } } wait(NULL);wait(NULL); shmdt(mem); shmctl(shmid,IPC_RMID,NULL); semctl(semid,0,IPC_RMID,0); return 0; }
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/wait.h> #include <sys/ipc.h> #include <sys/shm.h> #include <sys/sem.h> int main () { srandom(getpid()); int i,pid; int semid; struct sembuf operation; int shmid; int *mem,*NL; // allocation région de mémoire partagée if ((shmid = shmget(45,1024,0750|IPC_CREAT|IPC_EXCL)) == -1) perror ("Problème création mémoire partagée\n"); if ((mem=shmat(shmid,NULL,0)) == NULL) perror ("Problème shmat\n"); // création de trois sémaphores if ((semid = semget(12,3,IPC_CREAT|IPC_EXCL|0600)) == -1) perror ("Problème semget\n"); // Sémaphore MUTEX initialisé à 1 if ((semctl(semid,0,SETVAL,1)) == -1) perror ("Problème semctl\n"); // Sémaphore ACCES initialisé à 1 if ((semctl(semid,1,SETVAL,1)) == -1) perror ("Problème semctl\n"); // Sémaphore ONNENTREPLUS initialisé à 1 if ((semctl(semid,2,SETVAL,1)) == -1) perror ("Problème semctl\n"); NL=mem+1; pid=fork(); if (pid==0) { // Le fils 1 est lecteur : il lit la variable i { i=1; while(i<10) { sleep(random()%4); // P(ONNENTREPLUS) operation.sem_num=2; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); // V(ONNENTREPLUS) operation.sem_num=2; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); // P(MUTEX) operation.sem_num=0; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *NL=*NL+1; if (*NL == 1) { // P(ACCES) operation.sem_num=1; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); } // V(MUTEX) operation.sem_num=0; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); printf("Lecteur 1 : variable = %d\n",*mem); // P(MUTEX) operation.sem_num=0; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *NL=*NL-1; if (*NL == 0) { // V(ACCES) operation.sem_num=1; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); } // V(MUTEX) operation.sem_num=0; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); i=i+1; } } exit(0); } else { pid=fork(); if (pid == 0) { // Le fils 2 est lecteur : il lit la variable i { i=1; while(i<10) { sleep(random()%2); // P(ONNENTREPLUS) operation.sem_num=2; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); // V(ONNENTREPLUS) operation.sem_num=2; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); // P(MUTEX) operation.sem_num=0; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *NL=*NL+1; if (*NL == 1) { // P(ACCES) operation.sem_num=1; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); } // V(MUTEX) operation.sem_num=0; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); printf("Lecteur 2 : variable = %d\n",*mem); // P(MUTEX) operation.sem_num=0; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *NL=*NL-1; if (*NL == 0) { // V(ACCES) operation.sem_num=1; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); } // V(MUTEX) operation.sem_num=0; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); i=i+1; } } exit(0); } else { // Le père est rédacteur : il modifie la valeur i i=1; while(i<10) { sleep(random()%2); // P(ONNENTREPLUS) operation.sem_num=2; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); // P(ACCES) operation.sem_num=1; operation.sem_op=-1; operation.sem_flg=0; semop(semid,&operation,1); *mem=i*10; printf("Rédacteur : variable = %d\n",*mem); // V(ONNENTREPLUS) operation.sem_num=2; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); // V(ACCES) operation.sem_num=1; operation.sem_op=1; operation.sem_flg=0; semop(semid,&operation,1); i=i+1; } } } wait(NULL);wait(NULL); shmdt(mem); shmctl(shmid,IPC_RMID,NULL); semctl(semid,0,IPC_RMID,0); return 0; }
Exercice 2 - Le diner des philosophes
Ce problème est un grand classique des cours sur les systèmes d'exploitation : cinq philosophes sont réunis pour mener à bien deux activités majeures: "penser" et "manger". Chaque philosophe pense pendant un temps aléatoire, mange (si possible) pendant un temps aléatoire puis se remet à penser. Lorsqu'un philosophe demande à manger, un bol de riz l'attend. Les cinq bols sont disposés autour d'une table ronde. Pour qu'un philosophe puisse manger son riz, deux baguettes sont nécessaires : la sienne (celle de droite) et celle de son voisin de gauche. Naturellement, si l'un de ses voisins ou les deux voisins sont déjà en train de manger, le philosophe ne peut pas manger et doit patienter que l'une ou les deux baguettes occupées se libèrent.
La solution de ce problème doit être la plus optimisée possible : un philosophe voulant mais ne pouvant pas manger doit attendre son tour sans consommer de temps CPU inutilement. Chaque philosophe effectue plusieurs fois le cycle suivant :
- PENSE
- DEMANDE A MANGER
- MANGE
On doit naturellement constater que deux philosophes voisins ne mangent jamais en même temps, et qu'il ne risque pas d'avoir un interblocage.
-
Résoudre le problème du diner des philosophes en associant un sémaphore à chaque baguette. Chaque philosophe correspondra à un processus. (Le processus père lancera chaque philosophe et attendra).
-
Résoudre le problème du diner des philosophes en associant cette fois un sémaphore à chaque philosophe afin de profiter de sa file d'attente (un philosophe désirant manger mais ne le pouvant pas se placera dans la file d'attente de son sémaphore). Un tableau stockant l'état des philosophes ("PENSE", "DEMANDE A MANGER", "MANGE") sera stocké dans un segment de mémoire partagée (donc visible par les 5 processus). Ce segment de mémoire partagée devra être considéré comme une ressource critique (donc protégé par un sémaphore).
Solution "Diner à quatre"
#include <stdlib.h> #include <unistd.h> #include <sys/time.h> #include <sys/sem.h> #include <signal.h> #include <errno.h> #include <stdio.h> #include<sys/types.h> #include<sys/ipc.h> #include <sys/shm.h> #define NB_SEM 5 int sem; // Identifiant d'un ensemble de sémaphores int pidPere; // pid du processus père // Structure pour l'initialisation de l'ensemble des sémaphores typedef union { int valeur; struct semid_ds * buffer; unsigned short int * table; } semun_t; // Opération V ( +1 ) sur le i ème sémaphore de l'ensemble des sémaphores. void V( int i ) { struct sembuf buf; buf.sem_num = i; buf.sem_op = 1; buf.sem_flg = 0; semop( sem, &buf, 1 ); } // Opération P ( -1 ) sur le i ème sémaphore de l'ensemble des sémaphores. void P( int i ) { struct sembuf buf; buf.sem_num = i; buf.sem_op = -1; buf.sem_flg = 0; semop( sem, &buf, 1 ); } // Création et initialisation d'un nouvel ensemble de sémaphores void new_semaphore( void ) { int i, err; semun_t semun; unsigned short int table_sem[NB_SEM+1]; // Création de l'ensemble de sémaphores sem = semget( IPC_PRIVATE, NB_SEM+1, IPC_CREAT | IPC_EXCL | 0600 ); if ( sem == -1 ) { perror("Erreur semget"); exit(0); } for (i=0 ; i<NB_SEM ; i++) table_sem[i]=1; // 1 = nombre de ressources (baguettes) table_sem[NB_SEM]=NB_SEM-1; semun.table = table_sem; // Initialisation de l'ensemble de sémaphores err = semctl( sem, 0, SETALL, semun ); if ( err == -1 ) { perror( "ici semclt(SETALL)" ); exit(0); } } // Détruit l'ensemble de sémaphores identifié par sem. void kill_semaphore( void ) { semctl( sem, 0, IPC_RMID, NULL ); } // Traite le signal, tue le sémaphore et quitte le programme void handlerFin(int sig) { kill_semaphore(); exit(0); } // Affichage de l'état d'un processus sur stdout void printEtat(int num, int etat) { printf("%d %d\n",num+1,etat); fflush(stdout); } // Permet au philosophe de penser pendant une période de 0 à 5 sec. void penser(int num) { printEtat(num,100); sleep(rand()%5); } // Permet au philosophe numéro "num" de manger. void manger(int num) { printEtat(num,200); P(NB_SEM); // pas plus de 4 à table ! P(num); // prend sa baguette droite printEtat(num,201); P((num+NB_SEM-1) % NB_SEM); // prend sa baguette gauche printEtat(num,300); // obtient la baguette manquante et mange sleep(rand()%2); V(num); // libère sa baguette droite V((num+NB_SEM-1) % NB_SEM); // libère sa baguette gauche V(NB_SEM); } // Fonction permettant de penser et de manger void philosophe(int num) { while (1) { penser(num); manger(num); } } int main() { struct sigaction action; int i; // Pour quitter proprement action.sa_handler = handlerFin; sigaction(SIGINT, &action, NULL); sigaction(SIGQUIT, &action, NULL); pidPere = getpid(); // Pour rendre le temps de pensée aléatoire srand(pidPere); new_semaphore(); // Creation des processus fils (cad des 5 philosophes) for (i=0 ; i<NB_SEM ; i++) if (fork() == 0) { philosophe(i); } pause(); return(0); }
Solution "Diner latéralisé"
#include <stdlib.h> #include <unistd.h> #include <sys/time.h> #include <sys/sem.h> #include <signal.h> #include <errno.h> #include <stdio.h> #include<sys/types.h> #include<sys/ipc.h> #include <sys/shm.h> #define NB_SEM 5 int sem; // Identifiant d'un ensemble de sémaphores int pidPere; // pid du processus père // Structure pour l'initialisation de l'ensemble des sémaphores typedef union { int valeur; struct semid_ds * buffer; unsigned short int * table; } semun_t; // Opération V ( +1 ) sur le i ème sémaphore de l'ensemble des sémaphores. void V( int i ) { struct sembuf buf; buf.sem_num = i; buf.sem_op = 1; buf.sem_flg = 0; semop( sem, &buf, 1 ); } // Opération P ( -1 ) sur le i ème sémaphore de l'ensemble des sémaphores. void P( int i ) { struct sembuf buf; buf.sem_num = i; buf.sem_op = -1; buf.sem_flg = 0; semop( sem, &buf, 1 ); } // Création et initialisation d'un nouvel ensemble de sémaphores void new_semaphore( void ) { int i, err; semun_t semun; unsigned short int table_sem[NB_SEM]; // Création de l'ensemble de sémaphores sem = semget( IPC_PRIVATE, NB_SEM, IPC_CREAT | IPC_EXCL | 0600 ); if ( sem == -1 ) { perror("Erreur semget"); exit(0); } for (i=0 ; i<NB_SEM ; i++) table_sem[i]=1; // 1 = nombre de ressources (baguettes) semun.table = table_sem; // Initialisation de l'ensemble de sémaphores err = semctl( sem, 0, SETALL, semun ); if ( err == -1 ) { perror( "ici semclt(SETALL)" ); exit(0); } } // Détruit l'ensemble de sémaphores identifié par sem. void kill_semaphore( void ) { semctl( sem, 0, IPC_RMID, NULL ); } // Traite le signal, tue le sémaphore et quitte le programme void handlerFin(int sig) { kill_semaphore(); exit(0); } // Affichage de l'état d'un processus sur stdout void printEtat(int num, int etat) { printf("%d %d\n",num+1,etat); fflush(stdout); } // Permet au philosophe de penser pendant une période de 0 à 5 sec. void penser(int num) { printEtat(num,100); sleep(rand()%5); } // Permet au philosophe numéro "num" de manger. void manger(int num) { printEtat(num,200); if (num %2 == 0) { // Philosophe droitier P(num); // prend sa baguette droite printEtat(num,201); P((num+NB_SEM-1) % NB_SEM); // prend sa baguette gauche printEtat(num,300); // obtient la baguette manquante et mange } else { // Philosophe gaucher P((num+NB_SEM-1) % NB_SEM); // prend sa baguette gauche printEtat(num,210); P(num);// prend sa baguette droite printEtat(num,300); // obtient la baguette manquante et mange } sleep(rand()%2); if (num %2 == 0) { // Philosophe droitier V(num); // libère sa baguette droite V((num+NB_SEM-1) % NB_SEM); // libère sa baguette gauche } else { // Philosophe gaucher V((num+NB_SEM-1) % NB_SEM); // libère sa baguette gauche V(num % NB_SEM); // libère sa baguette droite } } // Fonction permettant de penser et de manger void philosophe(int num) { while (1) { penser(num); manger(num); } } int main() { struct sigaction action; int i; // Pour quitter proprement action.sa_handler = handlerFin; sigaction(SIGINT, &action, NULL); sigaction(SIGQUIT, &action, NULL); pidPere = getpid(); // Pour rendre le temps de pensée aléatoire srand(pidPere); new_semaphore(); // Creation des processus fils (cad des 5 philosophes) for (i=0 ; i<NB_SEM ; i++) if (fork() == 0) { philosophe(i); } pause(); return(0); }
Aide
semget
#include <sys/types.h> #include <sys/ipc.h> #include <sys/sem.h> int semget(key_t key, int nsems, int semflg);
semget crée un ensemble de sémaphores. L'entier retourné est le semid de l'ensemble de sémaphores ou -1 en cas d'erreur. semflag spécifie les priorités d'accès à l'ensemble de sémaphores. nsems désigne le nombre de sémaphores présents dans l'ensemble.
Exemple :
crée un ensemble de 4 sémaphores accessibles en lecture/écriture par tout processus.
semctl
#include <sys/types.h> #include <sys/ipc.h> #include <sys/sem.h> union semun { int val; struct semid_ds *buf; ushort *array } int semctl(int semid, int semnum, int cmd, semun arg);
semctl permet de réaliser des opérations de contrôle sur l'ensemble de sémaphores identifié par semid. semnum désigne le numéro du sémaphore de l'ensemble concerné par l'opération, arg un (ou des) argument(s) variant suivant la commande. Le type d'opération est spécifié par cmd :
- GETVAL : renvoie la valeur de semval du sémaphore semnum.
- SETVAL : affecte la valeur arg.val à semnum.
- IPC_RMID : détruit les sémaphores de l'ensemble, semid et semid_ds.
- ...
Exemples :
union semun arg; arg.val=1; semctl(semid,0,SETVAL,arg);
affecte la valeur 1 au premier sémaphore identifié par semid.
union semun arg; arg.val=0; semctl(semid,0,IPC_RMID,arg);
détruit l'ensemble des sémaphores désigné par semid.
semop
#include <sys/types.h> #include <sys/ipc.h> #include <sys/sem.h> int semop(int semid, struct sembuf *sops, size_t nsops);
semop effectue une série d'opérations définies par les nsops éléments de sops, qui sont du type sembuf.
struct sembuf { ushort_t sem_num; /* semaphore # */ short sem_op; /* semaphore operation */ short sem_flg; /* operation flags */ };
Trois types d'opérations sont permis :
- sem_op < 0 (correspond au "P" : Proberen ou Puis-je ?)
- Si (semval >= |sem_op|), alors semval = semval - |sem_op|.
-
Si (semval < |sem_op|), alors semncnt++ et le processus appelant est mis en attente jusqu'à ce que (semval >= |sem_op|). Ensuite, semncnt-- et semval=semval-|sem_op|.
- sem_op > 0 (correspond au "V" : Verhogen ou Vas-y !)
- semval = semval + sem_op.
- sem_op = 0
- Si (semval = 0), alors retour immédiat.
-
Si (semval != 0), alors semzcnt++ et le processus appelant est mis en attente jusqu'à ce que (semval=0). Ensuite, semznct--.
Exemples :
struct sembuf *sops; sops=(struct sembuf *)malloc(sizeof(struct sembuf)); sops[0].sem_num = 0; sops[0].sem_op = -1; sops[0].sem_flg = 0; semop(semid,sops,1)
correspond au "P" portant sur le premier sémaphore de l'ensemble de sémaphores identifié par semid.
struct sembuf *sops; sops=(struct sembuf *)malloc(sizeof(struct sembuf)); sops[0].sem_num = 0; sops[0].sem_op = 1; sops[0].sem_flg = 0; semop(semid,sops,1)
correspond au "V" portant sur le premier sémaphore de l'ensemble de sémaphores identifié par semid.
top