Introduction à la programmation concurrente
Moniteurs
Yann Thoma
Reconfigurable and Embedded Digital Systems Institute
Haute Ecole d’Ingénierie et de Gestion du Canton de Vaud
Mai 2012
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 1 / 22
Introduction
Introduction
Concept de moniteur
Proposé par Hoare en 1974
Permet de résoudre la synchronisation des tâches
Permet de regrouper des variables ainsi que les procédures
agissant sur ces variables
Assure l’exclusion mutuelle sur les procédures du moniteur
Synchronisation assurée par des primitives
wait()
signal()
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 2 / 22
Introduction
Structure d’un moniteur
monitor <nom>
<déclarations des variables rémanentes locales>;
<déclarations des variables conditions>;
procedure OpérationLocale(liste de paramètres)
<déclarations des variables locales>;
begin <code pour implémenter l’opération>;
end;
entry procedure OpérationVisible(liste de paramètres)
<déclarations des variables locales>;
begin <code pour implémenter l’opération>;
end;
begin <code pour initialiser les variables rémanentes>;
end;
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 3 / 22
Introduction
Variable condition
Synchronisation des tâches grâce aux variables conditions (VC)
Une VC offre 2 primitives:
attente
signale
Soit la VC cond déclarée par
condition cond;
[Link]
bloque inconditionnellement la tâche appelante
lui fait relâcher l’exclusion mutuelle sur le moniteur
la place dans une file associée à cond
[Link]
dépend de l’état de la file associée à cond
vide ⇒ la tâche appelante poursuit son exécution et l’opération n’a
aucun effet.
pas vide ⇒ une des tâches bloquées est réactivée et reprend
immédiatement son exécution
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 4 / 22
Introduction
Exemple: Verrou par moniteur
monitor VerrouMoniteur
var verrou: boolean;
var acces: condition;
entry procedure Verrouille
begin
if verrou then [Link];
verrou := true;
end Verrouille;
entry procedure Deverrouille
begin
verrou := false;
[Link];
end Deverrouille;
begin verrou := false;
end VerrouMoniteur;
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 5 / 22
Introduction
Exemple: Producteur-consommateur
monitor Tampons
var place: array [0..N-1] of ARTICLE;
var tete, queue, taille: integer;
var pasPlein, pasVide: condition;
entry procedure deposer(a: ARTICLE)
begin
if taille = N then [Link];
taille := taille + 1;
place[tete] := a;
tete := (tete + 1) mod N;
[Link];
end deposer;
entry procedure retirer(var a: ARTICLE)
begin
if taille = 0 then [Link];
a := place[queue];
taille := taille - 1;
queue := (queue + 1) mod N;
[Link];
end retirer;
begin taille := 0; queue := 0; tete := 0;
end Tampons;
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 6 / 22
Introduction
Moniteur Posix
Un moniteur Posix associe:
Un mutex, qui assure l’exclusion mutuelle
Une variable de condition, qui sert de point de signalisation
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 7 / 22
Introduction
Fonctions Posix
Fonction Description
int pthread_cond_init(pthread_cond_t *cond, Initialisation
const pthread_condattr_t *attr) d’une variable
condition
int pthread_cond_wait(pthread_cond_t *cond, Attente sur la
pthread_mutex_t *mutex) variable
int pthread_cond_timedwait(pthread_cond_t *cond,
pthread_mutex_t *mutex, Attente avec
échéance
const struct timespec *abstime)
pthread_cond_signal(pthread_cond_t *cond) Réveil poten-
tiel d’un thread
pthread_cond_broadcast(pthread_cond_t *cond) Réveil de tous
les threads en
attente
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 8 / 22
Introduction
Structure type d’un moniteur en POSIX
void uneFonction() {
pthread_mutex_lock(&mutex);
// Evaluer C
while(!C) {
pthread_cond_wait(&variableCond,&mutex);
// Réévaluer C si nécessaire
}
// Exécuter la fonction demandée
pthread_mutex_unlock(&mutex);
}
void uneAutreFonction() {
pthread_mutex_lock(&mutex);
// Faire quelque chose
// Modifier la condition C (passer à true)
pthread_cond_signal(&variableCond);
pthread_mutex_unlock(&mutex);
}
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 9 / 22
Introduction
Exemple de producteurs/consommateurs en POSIX
#include <pthread.h>
#include <string.h>
#include <stdlib.h>
static pthread_cond_t estLibre, estPlein;
static pthread_mutex_t protege;
static char *tampon = NULL;
/* Initialise le producteur/consommateur. */
void InitialiseTampon(void)
{
pthread_mutex_init(&protege,NULL);
pthread_cond_init(&estLibre,NULL);
pthread_cond_init(&estPlein,NULL);
} /* fin de InitialiseTampon */
void DetruitTampon(void) {
pthread_mutex_destroy(&protege);
pthread_cond_destroy(&estLibre);
pthread_cond_destroy(&estPlein);
if (tampon != NULL) {
free(tampon);
tampon = NULL;
}
} /* fin de DetruitTampon */
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 10 / 22
Introduction
Exemple de producteurs/consommateurs en POSIX
/* Depose le message msg (qui est dupliqué) et bloque tant que le
** tampon est plein. */
void Deposer(char *msg) {
pthread_mutex_lock(&protege);
while (tampon != NULL)
pthread_cond_wait(&estLibre,&protege);
if ((tampon = (char *)malloc(strlen(msg) + 1)) != NULL) {
strcpy(tampon,msg);
pthread_cond_signal(&estPlein);
}
pthread_mutex_unlock(&protege);
} /* fin de Deposer */
/* Renvoie le message du tampon et bloque tant que le tampon est vide.
** La libération de la mémoire contenant le message est à la charge de
** l’appelant. */
char *Prelever(void) {
char *resultat;
pthread_mutex_lock(&protege);
while (buffer == NULL)
pthread_cond_wait(&estPlein,&protege);
resultat = tampon;
tampon = NULL;
pthread_mutex_unlock(&protege);
pthread_cond_signal(&estLibre);
return resultat;
} /* fin de Prelever */
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 11 / 22
Introduction
Implémentation de moniteurs à partir de sémaphores
(1)
Etape 1: Pour chaque variable (instance) mon de type moniteur, créer
un enregistrement :
typedef struct {
sem_t mutex;
sem_t signale; //file bloquante des signaleurs
unsigned nbSignale; //tâches en attente dans signal
} T_Moniteur;
T_Moniteur mon;
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 12 / 22
Introduction
Implémentation de moniteurs à partir de sémaphores
(2)
Etape 2: Chaque procédure constituant un point d’entrée du moniteur
est encadré par :
sem_wait(&[Link]);
< code de la procédure>
if ([Link] > 0) sem_post(&[Link]);
else sem_post(&[Link]);
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 13 / 22
Introduction
Implémentation de moniteurs à partir de sémaphores
(3)
Etape 3: Pour chaque variable condition cond du moniteur, créer un
enregistrement:
typedef struct {
sem_t attente;
unsigned nbAttente; //tâches en attente
} T_Condition;
T_Condition cond;
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 14 / 22
Introduction
Implémentation de moniteurs à partir de sémaphores
(4)
Etape 4: Dans toutes les procédures du moniteur, substituer
[Link] par :
[Link] += 1;
if ([Link] > 0) sem_post(&[Link]);
else sem_post(&[Link]);
sem_wait(&[Link]);
[Link] -= 1;
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 15 / 22
Introduction
Implémentation de moniteurs à partir de sémaphores
(5)
Etape 5: Dans toutes les procédures du moniteur, substituer
[Link] par :
if ([Link] > 0) {
[Link] += 1;
sem_post(&[Link]);
sem_wait([Link]);
[Link] -= 1;
}
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 16 / 22
Introduction
Exemple: producteurs/consommateurs
monitor Tampons
var place: array [0..N-1] of ARTICLE; static T_Moniteur Tampons;
var tete, queue, taille: integer; static ARTICLE place[0..N-1];
var pasPlein, pasVide: condition;
begin taille := 0; queue := 0; tete := 0;
end Tampons;
⇒ static
static
int tete, queue, taille;
T_Condition pasPlein, pasVide;
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 17 / 22
Introduction
Exemple: producteurs/consommateurs
void deposer(ARTICLE a) {
sem_wait(&[Link]);
if (taille == N) {
[Link] += 1;
if ([Link] > 0)
sem_post(&[Link]);
else sem_post(&[Link]);
monitor Tampons sem_wait(&[Link]);
entry procedure deposer(a: ARTICLE) [Link] -= 1;
begin }
if taille = N then [Link]; taille += 1;
taille := taille + 1; place[tete] = a;
place[tete] := a;
tete := (tete + 1) mod N;
[Link];
end deposer;
⇒ tete = (tete + 1) % N;
if ([Link] > 0) {
[Link] += 1;
sem_post(&[Link]);
end Tampons; sem_wait([Link]);
[Link] -= 1;
}
if ([Link] > 0)
sem_post(&[Link]);
else
sem_post(&[Link]);
} /* fin de deposer */
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 18 / 22
Introduction
Exemple: producteurs/consommateurs
void retirer(ARTICLE *a) {
sem_wait(&[Link]);
if (taille == 0) {
[Link] += 1;
if ([Link] > 0)
sem_post(&[Link]);
else sem_post(&[Link]);
monitor Tampons sem_wait(&[Link]);
entry procedure retirer(var a: ARTICLE) [Link] -= 1;
begin }
if taille = 0 then [Link]; a = place[queue];
a := place[queue]; taille -= 1;
taille := taille - 1;
queue := (queue + 1) mod N;
[Link];
end retirer;
⇒ queue = (queue + 1) % N;
if ([Link] > 0) {
[Link] += 1;
sem_post(&[Link]);
end Tampons; sem_wait([Link]);
[Link] -= 1;
}
if ([Link] > 0)
sem_post(&[Link]);
else
sem_post(&[Link]);
} /* fin de retirer */
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 19 / 22
Introduction
Optimisation
void deposer(ARTICLE a) {
sem_wait(&[Link]);
if (taille == N) { void deposer(ARTICLE a) {
[Link] += 1; sem_wait(&[Link]);
if ([Link] > 0) if (taille == N) {
sem_post(&[Link]); [Link] += 1;
else sem_post(&[Link]); if ([Link] > 0)
sem_wait(&[Link]); sem_post(&[Link]);
[Link] -= 1; else sem_post(&[Link]);
} sem_wait(&[Link]);
taille += 1; [Link] -= 1;
place[tete] = a; }
tete = (tete + 1) % N;
if ([Link] > 0) {
[Link] += 1;
sem_post(&[Link]);
⇒ taille += 1;
place[tete] = a;
tete = (tete + 1) % N;
if ([Link] > 0)
sem_wait([Link]); sem_post(&[Link]);
[Link] -= 1; else if ([Link] > 0)
} sem_post(&[Link]);
if ([Link] > 0) else
sem_post(&[Link]); sem_post(&[Link]);
else } /* fin de deposer */
sem_post(&[Link]);
} /* fin de deposer */
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 20 / 22
Introduction
Optimisation (2)→solution
void deposer(ARTICLE a) { void retirer(ARTICLE *a) {
sem_wait(&[Link]); sem_wait(&[Link]);
if (taille == N) { if (taille == 0) {
[Link] += 1; [Link] += 1;
sem_post(&[Link]); sem_post(&[Link]);
sem_wait(&[Link]); sem_wait(&[Link]);
[Link] -= 1; [Link] -= 1;
} }
taille += 1; a = place[queue];
place[tete] = a; taille -= 1;
tete = (tete + 1) % N; queue = (queue + 1) % N;
if ([Link] > 0) if ([Link] > 0)
sem_post(&[Link]); sem_post(&[Link]);
else else
sem_post(&[Link]); sem_post(&[Link]);
} /* fin de deposer */ } /* fin de retirer */
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 21 / 22
Introduction
Remarques finales
Avantages des moniteurs
une protection associée au moniteur (exclusion mutuelle);
une souplesse d’utilisation des primitives attente et signale;
une efficacité de ces mécanismes.
Inconvénients des moniteurs
un risque de manque de lisibilité qui est partiellement dû à des
variations sémantiques des implémentations dans les divers
langages qui les supportent.
Dans le cas de pthread, il n’y a aucune garantie que les variables
partagées sont effectivement accédées uniquement depuis les points
d’entrée du moniteur qui devrait les protéger;
les variables condition sont de bas niveau;
l’impossibilité d’imposer un ordre total ou partiel dans l’exécution
des procédures ou fonctions exportées.
Yann Thoma (HES-SO / HEIG-VD / REDS) Introduction à la programmation concurrente Mai 2012 22 / 22
