Programmation des Systèmes
Synchronisation de processus
Travaux Dirigés assurés par Philippe Décogné
21/12/2002
Processus concurrents
Quand plusieurs processus ont besoin d'accéder à une ressource, il faut synchroniser les processus de façon à ce que toute modification de la ressource par un processus soit prise en compte avant qu'un autre processus puisse la modifier à son tour.
Devant ce type de problème, il faut, pour le résoudre, se poser la question suivante:
Combien de processus peuvent accéder à la ressource ?
La réponse dépend, évidemment, du cas de figure particulier, mais, en règle générale, on a les correspondances suivantes :
- la ressource est une variable -> un seul processus peut y accéder,
- la ressource est un fichier -> plusieurs processus peuvent y accéder,
- la ressource est un disque -> un grand nombre de processus peuvent y accéder.
Moyens de synchronisation
Les différents moyens de synchronisation à disposition sont :
- les tubes,
- les files de messages,
- les signaux,
- la mémoire partagée,
- les sémaphores.
Dans une architecture producteur-consommateur, les tubes sont un moyen de synchronisation :
- un processus a besoin d'un signal,
- un autre le génère.
On peut aussi utiliser une variable booléenne pour autoriser l'accès à un fichier sur disque. Chaque processus, à son tour, met la variable booléenne à vrai si elle est fausse.
Dans certains cas, on peut se trouver dans une situation d'interblocage si deux processus mettent la variable booléenne à vrai, l'un juste avant de passer en sommeil, l'autre au réveil.
Sémaphores
Pour résoudre le problème de l'interblocage, on utilise des sémaphores.
Principe
Quand on crée un sémaphore, on définit un compteur. Une fois créé, on initialise le compteur à une valeur donnée. Ensuite, tout processus intéressé :
- "prend" le sémaphore à condition que la valeur du compteur ne soit pas nulle, auquel cas la ressource n'est plus disponible
- décrémente la valeur du compteur
- effectue une opération simple
- "rend" le sémaphore
- incrémente la valeur du compteur
Ainsi le sémaphore permet de tracer la disponibilité d'une ressource.
On regroupe souvent les sémaphores en jeu de sémaphores de façon à mobiliser plusieurs ressources en même temps et éviter ainsi des blocages intempestifs.
Primitives utilisées
Semget : int semget(key_t key, int nsmes, int semflg);
Création d'un jeu de nsems sémaphores si key est égal à IPC _PRIVATE ou qu'aucun jeu de sémaphores n'est associé à key et que le bit IPC_CREAT est positionné dans semflg.
Les sémaphores sont numérotés de 0 à nsems - 1.
semflg représente une combinaison par ou exclusif des constantes IPC_CREAT, IPC_EXCL et des droits d'accès au sémaphore.
Retourne l'identifiant du jeu de sémaphores en cas de succès, sinon retourne -1.
Si IPC_CREAT et IPC_EXCL sont tous les deux positionnés et que le jeu de sémaphores existe déjà, retourne une erreur.
Librairies à utiliser : sys/types.h pour la définition de key_t, sys/ipc.h et sys/sem.h pour celle de semget.
Man page : semget(2) - system calls
Semctl : int semctl(int semid, int semnum, int cmd, union semun arg);
Permet d'effectuer l'opération cmd sur un sémaphore identifié par semnum à l'intérieur d'un jeu de sémaphores identifié par semid. Pour effectuer l'opération cmd sur l'ensemble du jeu, mettre semnum à 0.
Les commandes possibles sont :
GETVAL, SETVAL, GETPID, GETNCNT, IPC_SET, IPC_RMID
Suivant la commande appelée, il peut être nécessaire de fournir l'argument arg (une union) défini comme suit :
- int val pour SETVAL
- struct semid_ds *buf pour IPC_STAT et IPC_SET
- u_short *array pour GETALL et SETALL
En cas de succès, retourne :
- le pid du dernier processus ayant utilisé le sémaphore pour GETPID
- la valeur du sémaphore pour GETVAL
- le nombre de processus en attente du sémaphore pour GETNCNT
- 0 pour les autres commandes
SETVAL positionne la valeur du sémaphore à arg.val
IPC_SET positionne les permissions définies dans arg.buf
IPC_RMID détruit le sémaphore et toutes les structures associées.
Retourne -1 en cas d'échec.
Librairies à utiliser : sys/types.h, sys/ipc.h et sys/sem.h.
Man page : semctl(2) - system calls
Semop : int semop(int semid, struct sembuf *sops, int nsops);
Permet d'effectuer les nsops opérations définies dans sops sur le jeu de sémaphores semid.
sops est un tableau dont chaque élément a la structure suivante :
u_short sem_num : numéro du sémaphore
short sem_op : opération à appliquer sur le sémaphore
short sem_flg : options affectant le déroulement de l'opération
Les opérations sont les suivantes :
sem_op < 0 => utilisé pour entrer dans une zone critique. Le processus actif est bloqué jusqu'à ce que la valeur du sémaphore atteigne ou dépasse |sem_op|. On retranche alors de la valeur du sémaphore |sem_op| et le processus appelant continue.
sem_op > 0 => utilisé pour sortir d'une zone critique. sem_op est ajouté à la valeur du sémaphore.
sem_op = 0 => utilisé pour notifier le manque de ressource. Le processus appelant est bloqué jusqu'à ce que le sémaphore atteigne 0.
Les options sont les suivantes :
0 => pas d'option
IPC_NOWAIT => empêche le blocage du processus appelant si l'opération sur le sémaphore ne peut être satisfaite.
SEM_UNDO => sert à empêcher le blocage d'un processus au cas où le processus qui a bloqué le sémaphore se terminerait brutalement dans une section critique. Ajoute une structure d'annulation pour le sémaphore si l'opération a réussi. De cette façon, on pourra restaurer les valeurs du sémaphore avant blocage à la sortie du programme.
Retourne 0 en cas de succès, sinon 1.
Librairies à utiliser : sys/types.h, sys/ipc.h et sys/sem.h.
Man page : semop(2) - system calls
On reprend le second programme du TD 3.
Le réécrire de façon à placer en exclusion mutuelle les incrémentations du thread principal et du thread secondaire.
Exclusion mutuelle
L'exclusion mutuelle est une forme simplifiée de sémaphore qui ne contient qu'une seule valeur 0 ou 1.
Solution
Ce programme ne fonctionne pas sous XDarwin, car la section critique est bloquée indéfiniment en attente du changement de la valeur du sémaphore. Le thread ne se réveille pas lors de l'envoi de la notification. Ce problème semble commun à toute implantation BSD.
On verra plus loin une variation utilisant l'extension Realtime POSIX qui fonctionne parfaitement sous XDarwin.
/* hellosemaphore.c
This programm creates a thread which performs an addition based on a counter.
The main thread operates also on the counter. The counter is a global variable.
Critical section is handled via semaphore (ie mutex)*/
/* includes */
#include <stdio.h>
#include <sys/types.h>
#include <pthread.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <stdlib.h>
/* Global variables */
int i; /*counter for the addition */
int semid; /* semaphore ID */
struct sembuf operation; /* structure for operation on semaphore */
union semun arg; /* values passed to semaphore */
/* Function declarations */
void addition(); /* function called by secondary thread */
void killsemaphore(); /* function for destroying semaphore
either on quitting or on exiting upon error */
int main()
{
/* Variables */
pthread_t thread_id; /* pointer to address of threads ids */
/* Initialization */
i = 0;
/* Create a semaphore with identifier 13, initialised to value 1
(ie. only one process can access the ressource),
with permissions read and write for all (owner, group, others)
exit on error if the identifier already exists
if ((semid = semget(13, 1, IPC_CREAT|IPC_EXCL|0666)) == -1)
{
perror("pb semget");
exit(EXIT_FAILURE);
}
/* Create a thread */
if (pthread_create(&thread_id, NULL,(void *(*)())addition, NULL) == -1)
{
perror("Unable to create the thread");
/* Destroy the semaphore before exiting
otherwise it will be left pending */
killsemaphore();
exit(EXIT_FAILURE);
}
/* Operation P
Enter the critical section
Apply the operation on semaphore number 0 (sem_num = 0)
Decrements the counter (sem_op = -1)
No option (sem_flg = 0)
*/
operation.sem_num = 0;
operation.sem_op = -1;
operation.sem_flg = 0; ;
/* Apply one operation (last argument = 1) on semaphore semid */
if ( semop(semid, &operation, 1) == -1)
{
perror("Operation P failed in first thread");
killsemaphore();
exit(EXIT_FAILURE);
}
/* Addition in the main thread */
i += 1000;
printf("Hello main thread, i is: %d\n", i);
i += 2000;
printf("Hello main thread, i is: %d\n", i);
/* Operation V
Exit the critical section
Apply the operation on semaphore number 0 (sem_num = 0)
Increments the counter (sem_op = 1)
No option (sem_flg = 0)
*/
operation.sem_num = 0;
operation.sem_op = 1;
operation.sem_flg = 0; ;
/* Apply one operation (last argument = 1) on semaphore semid */
if ( semop(semid, &operation, 1) == -1)
{
perror("Operation V failed in first thread");
killsemaphore();
exit(EXIT_FAILURE);
}
/* Wait for the secondary thread to terminate */
if (pthread_join(thread_id, NULL) == -1)
{
perror("pb with pthread_join");
killsemaphore();
exit(EXIT_FAILURE);
}
/* Destroy the semaphore */
killsemaphore();
return 0;
}
void addition()
{
/* Operation P */
operation.sem_num = 0;
operation.sem_op = -1;
operation.sem_flg = IPC_NOWAIT;
if ( semop(semid, &operation, 1) == -1)
{
perror("Operation P failed in second thread");
killsemaphore();
exit(EXIT_FAILURE);
}
i = i + 10;
printf("hello, thread fils %d\n", i);
i = i + 20;
printf("hello, thread fils %d\n", i);
/* Operation V */
operation.sem_num = 0;
operation.sem_op = 1;
operation.sem_flg = IPC_NOWAIT;
if ( semop(semid, &operation, 1) == -1)
{
perror("Operation V failed in second thread");
killsemaphore();
exit(EXIT_FAILURE);
}
}
void killsemaphore()
{
/* Destroy the semaphore */
arg.val = 0;
if (semctl(semid, 0, IPC_RMID, arg) == -1)
{
perror("semctl failed");
exit(EXIT_FAILURE);
}
}
Variation avec extension Realtime POSIX
Primitives utilisées
Sem_open : sem_t * sem_open(const char *name, int flags, mode_t mode, unsigned int value);
Création d'un sémaphore nommé name, avec les options flags, les permissions mode, et initialisé à la valeur value.
flags représente une combinaison par ou exclusif des constantes O_CREAT et O_EXCL.
Retourne l'identifiant du jeu de sémaphores en cas de succès, sinon retourne -1.
Si IPC_CREAT et IPC_EXCL sont tous les deux positionnés et que le jeu de sémaphores existe déjà, retourne une erreur.
Il n'y a pas d'entrée visible dans le système de gestion de fichiers pour le sémaphore créé.
Librairie à utiliser : semaphore.h.
Man page : sem_open(2) - system calls
Sem_wait : int sem_wait(sem_t *sem);
Permet de bloquer le sémaphore sem. Si la valeur du sémaphore est nulle lors de l'appel, le processus appelant est bloqué jusqu'à notification de la disponibilité de la ressource par le sémaphore ou jusqu'à ce qu'un signal interrompe l'appel.
Retourne 0 en cas de succès, sinon -1.
Librairie à utiliser : semaphore.h.
Man page : sem_wait(2) - system calls
Sem_post : int sem_post(sem_t *sem);
Permet de libérer le sémaphore sem. La valeur du sémaphore est incrémentée et tous les threads qui attendent le sémaphore sont réveillés.
Retourne 0 en cas de succès, sinon 1.
Librairies à utiliser : semaphore.h.
Man page : sem_post(2) - system calls
Sem_close : int sem_close(sem_t *sem);
Permet de désallouer les ressources associés au sémaphore sem et d'invalider le descripteur.
Retourne 0 en cas de succès, sinon 1.
Librairies à utiliser : semaphore.h.
Man page : sem_close(2) - system calls
Sem_unlink : int sem_unlink(const char *name);
Permet de supprimer le sémaphore name. Si le sémaphore est utilisé par d'autres processus, name est dissocié du sémaphore, mais le sémaphore lui-même n'est détruit que lorsque toutes ses références ont été closes.
Toute création de sémaphore nommé name après suppression, référencera ou créera un nouveau sémaphore nommé name.
Retourne 0 en cas de succès, sinon 1.
Librairies à utiliser : semaphore.h.
Man page : sem_unlink(2) - system calls
/* hellosem1.c
This programm creates a thread which performs an addition based on a counter.
The main thread operates also on the counter. The counter is a global variable.
Use the Realtime POSIX extension
*/
/* includes */
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <semaphore.h>
/* Global variables */
int i; /* counter for the addition */
sem_t semid; /* semaphore ID */
const char *sem_name; /* semaphore name */
/* Function declarations */
void addition();
void killsemaphore();
int main()
{
/* Variables */
pthread_t thread_id; /* pointer to address of threads ids */
/* Initialization */
i = 0;
sem_name = "myhellosem.lock";
/* Create a semaphore named sem_name, only if it does not already exist,
with read and write permissions for owner, group, and others
initialized to 1 */
if ((semid = (int)sem_open(sem_name, O_CREAT|O_EXCL, 0666, 1)) == SEM_FAILED)
{
perror("pb sem_open");
exit(EXIT_FAILURE);
}
/* Create a thread */
if (pthread_create(&thread_id, NULL,(void *(*)())addition, NULL) == -1)
{
perror("Unable to create the thread");
/* Destroy the semaphore before exiting
otherwise it will be left pending */
killsemaphore();
exit(EXIT_FAILURE);
}
/* Enter the critical section */
if (semwait(&semid) == -1)
{
perror("Unable to lock the semaphore in main thread");
killsemaphore();
exit(EXIT_FAILURE);
}
/* Addition in the main thread */
i += 1000;
printf("Hello main thread, i is: %d\n", i);
i += 2000;
printf("Hello main thread, i is: %d\n", i);
if (sem_post(&semid) == -1)
{
perror("Unable to unlock the semaphore in main thread");
killsemaphore();
exit(EXIT_FAILURE);
}
/* Wait for the secondary thread to terminate */
if (pthread_join(thread_id, NULL) == -1)
{
perror("pb with pthread_join");
killsemaphore();
exit(EXIT_FAILURE);
}
/* Destroy the semaphore */
killsemaphore();
return 0;
}
void addition()
{
if (sem_wait(&semid) == -1)
{
perror("sem_wait failed in secondary thread");
killsemaphore();
exit(EXIT_FAILURE);
}
i = i + 10;
printf("hello, thread fils %d\n", i);
i = i + 20;
printf("hello, thread fils %d\n", i);
if(sem_post(&semid) == -1)
{
perror("Unable to unlock the semaphore in secondary thread");
killsemaphore();
exit(EXIT_FAILURE);
}
}
void killsemaphore()
{
/* Destroy the semaphore */
sem_close(&semid);
sem_unlink(sem_name);
}
La RATP a écrit un programme qui simule le comportement des voyageurs aux portillons automatiques pour la sortie Maison des Examens en gare de Laplace, RER B et comptabilise ceux-ci, afin d'étudier les flux de voyageurs en vue de rajouter des portillons à cette sortie.
Les règles de ce programme sont les suivantes :
- Le nombre de voyageurs s'engageant vers la sortie Maison des Examens est géré par une variable Nb_Voyageurs qui est incrémentée dès qu'un voyageur s'engage dans l'un des escaliers des quais menant à cette sortie. Cette même variable est décrémentée dès que le voyageur a passé un portillon automatique et a quitté la station.
- Une autre variable Nb_Voyageurs_Total comptabilise le nombre total de voyageurs s'engageant vers la sortie Maison des Examens par jour.
- Pour sortir de la station, un voyageur doit passer son ticket par un portillon et un seul, et il doit être, à un instant donné, le seul à utiliser ce portillon. Il y a 5 portillons permettant de sortir par la sortie Maison des Examens.
Le pseudo-code d'un voyageur est le suivant :
Processus Voyageur Début Si (direction_prise par le voyageur == sortie Maison des examens) alors -- compter un voyageur de plus pour la sortie Maison des Examens pour cette journée Nb_Voyageurs_Total++; -- compter un voyageur de plus pour la sortie Maison des Examens Nb_Voyageurs++; -- attendre un portillon libre pour passer, puis passer Passer_Portillon(); -- compter un voyageur de moins pour la sortie Maison des Examens Nb_Voyageurs--; Sinon -- Autre sortie de la station, on ne fait rien Fsi Fin Processus
Complétez ce pseudo-code avec les opérations de synchronisation basées sur l'outil sémaphore que vous jugerez utiles.
Solution
Comportement d'un voyageur
1 - Fait un petit somme sur un banc (en reste-t-il encore ?), attend le prochain RER, remonte vite dans la rame car il s'est trompé de station.
2 - Ne va pas à la Maison des Examens, y va mais décide de passer par là parce qu'il y a trop de monde de l'autre côté.
3 - Incrémente les deux compteurs Nb_Voyageurs, Nb_Voyageurs_Total
4 - Se demande par quel portillon il va passer, il a le choix : 5 en tout, mais seuls 2 sont disponibles au moment où il les atteint.
5 - Décrémente le compteur Nb_Voyageurs.
Ressources critiques
Pour résoudre le problème, il faut rechercher quelles sont les ressources critiques du point de vue du voyageur.
Sémaphore binaire
Supposons que deux voyageurs A et B s'engagent en même temps dans l'escalier qui mène à la sortie Maison des Examens. On doit incrémenter les deux compteurs Nb_Voyageurs et Nb_Voyageurs_Total.
Si les variables ne sont pas protégées, alors il se peut que la modification concernant le voyageur A n'ait pas le temps d'être inscrite en mémoire centrale avant que la modification concernant le voyageur B n'ait lieu. Ainsi, au lieu de constater deux voyageurs en plus, on ne constatera qu'un voyageur en plus.
Il faut donc utiliser la technique de l'exclusion mutuelle pour ces deux variables. On aura deux sémaphores binaires initialisés à 1 :
- MUT_VT pour Nb_Voyageurs_Total
- MUT_V pour Nb_Voyageurs
Sémaphore à n accès
En ce qui concerne les portillons, ou bien au moins un portillon est disponible et le voyageur peut passer, ou bien il n'y a pas de portillon disponible et le voyageur doit attendre.
Il faut donc pouvoir connaître à tout instant le nombre de portillons disponibles et bloquer le processus voyageur lorsqu'aucun n'est disponible jusqu'à ce qu'au moins un portillon devienne disponible.
On aura donc un sémaphore initialisé à 5 :
- portillon
Technique
Il faut tout d'abord créer et initialiser les sémaphores. Cela se fera dans la partie initialisation des processus, en même temps que l'initialisation des variables Nb_Voyageurs et Nb_Voyageurs_Total :
INIT(1, MUT_VT);
INIT(1, MUT_V);
INIT(5, portillon);
Ensuite, chaque fois qu'on utilisera les variables Nb_Voyageurs et Nb_Voyageurs_Total, il faudra encadrer leur utilisation par le blocage des sémaphores MUT_V et MUT_VT avant modification des variables et leur déblocage après modification :
P(MUT_V);
...
V(MUT_V);
Pour le passage du portillon, il faut, de même, bloquer le sémaphore avant passage, le débloquer après passage :
P(portillon);
...
V(portillon);
Implémentation dans le pseudo-code
Initialisation des processus Nb_Voyageurs = 0; Nb_Voyageurs_Total = 0; INIT(1, MUT_VT); INIT(1, MUT_V); INIT(5, portillon); Processus Voyageur Début Si (direction_prise par le voyageur == sortie Maison des examens) alors -- compter un voyageur de plus pour la sortie Maison des Examens pour cette journée P(MUT_VT); Nb_Voyageurs_Total++; V(MUT_VT); -- compter un voyageur de plus pour la sortie Maison des Examens P(MUT_V); Nb_Voyageurs++; V(MUT_V); -- attendre un portillon libre pour passer, puis passer P(portillon); Passer_Portillon(); V(portillon); -- compter un voyageur de moins pour la sortie Maison des Examens P(MUT_V); Nb_Voyageurs--; V(MUT_V); Sinon -- Autre sortie de la station, on ne fait rien Fsi Fin Processus
