"Implémenter" des moniteurs
Salut,
Avant tout, désolé de la taille du message, si vous connaissez déjà bien les moniteurs et sémaphores (de Dijkstra) et que vous n'avez pas besoin de rappel, vous pouvez sauter la première moitié du message. :P
Après avoir cherché à implémenter les sémaphores, je cherche comment implémenter les moniteurs, et si possible, uniquement à partir des sémaphores.
Cette fois-ci mon but n'est pas purement algorithmique, j'aimerais en faire une implémentation en C sous forme de macro préprocesseur.
Quelques rappels à propos des moniteurs (au cas où, ça fait pas de mal :)) :
Les moniteurs sont des objets un peu plus évolués que les sémaphores. Un moniteur est composé de plusieurs procédures ou fonctions et de variables locales.
Le moniteur doit être partagé entre tous les processus (en fait seul les variables ont besoin d'être partagées).
Quand un processus appelle une procédure ou fonction du moniteur, il empêche tous les autres d'appeler une fonction ou procédure du moniteur. Il ne peut y avoir qu'un seul processus à la fois dans le moniteur. Ceci peut être réalisé via un mutex qui est acquis à l'entrée des procédures/fonctions et relâché à la sortie.
Les variables locales au moniteur peuvent être de n'importe quel type (entier, chaine de caractère, etc...) mais elles peuvent aussi être du type condition. Ce type est introduit avec les moniteurs, les variables de ce type sont des objets assez similaires au sémaphores.
Une variable de type condition possède deux opérations : wait et signal.
wait : permet de mettre le processus en attente pour un temps indéterminé.
signal : permet de réveiller un des processus qui dort.
À noter qu'il existe plusieurs conventions à propos de l'opération signal, soit après un appel à signal le processus continue son exécution dans le moniteur, soit l'appel à signal fait sortir le processus du moniteur.
La deuxième étant nettement plus simple à gérer, je propose qu'on adopte celle-là.
Rappel sur les sémaphores (au sens de Dijkstra, hein ? :)) :
Ce sont des objets qui possèdent un compteur et une liste des processus. Trois opérations sont défini :
Init : donne sa valeur initiale au compteur du sémaphore
P : décrémente le compteur, puis si celui-ci est strictement négatif, rajoute le processus à la liste et met le processus en attente jusqu'à ce qu'une opération V le réveil.
V : Incrémente le compteur puis si le compteur est négatif ou nul, réveille un processus de la liste après l'avoir retiré de cette liste.
Chacune de ces trois opérations ne doit pas pouvoir être interrompue par une autre de ces opérations.
Si tout ceci est clair il devient trivial d'implémenter les sémaphores avec un moniteur :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| monitor Sémaphore {
entier : compteur;
condition : cond;
procedure Init (entier : max) {
compteur := max;
}
procedure P () {
compteur := compteur - 1;
if (compteur < 0) {
cond.wait;
}
}
procedure V () {
compteur := compteur + 1;
if (compteur <= 0) {
cond.signal;
}
}
} |
Voilà pour la petite intro aux moniteurs. :)
Maintenant, comment "implémenter" ça avec des sémaphores ?
Pour n'avoir qu'un seul processus à la fois dans le moniteur, on peut utiliser un sémaphore initialisé à 1.
Il faut donc, avant le début de chaque procédure et fonction effectuer un P(mutex_monitor); et à la fin V(mutex_monitor);.
Trivialement, on a envie de dire que les variables de type condition sont des sémaphores initialisés à 0 avec l'opération wait qui correspond au P et signal au V.
Mais ça ne marche pas car quand on va appeler le wait de la variable condition, on détient toujours le mutex du moniteur.
Petit exemple avec le "problème du parking".
Écrit sous forme de moniteur ça donne :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| Monitor parking {
entier : compteur := 20;
condition : entrée;
procedure entrer {
if (compteur = 0) {
entrée.wait;
}
compteur := compteur - 1;
}
procedure sortie {
compteur := compteur + 1;
entrée.signal;
}
} |
Réécrit en transformant le moniteur et les variables condition en sémaphore :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| sémaphore : mutex_monitor;
entier : compteur := 20;
sémaphore : entrée;
procedure entrer {
P(mutex_monitor); // entrée de la procédure
if (compteur = 0) {
P(entrée); // condition.wait
}
compteur := compteur - 1;
V(mutex_monitor); // sortie de la procédure
}
procedure sortie {
P(mutex_monitor);
compteur := compteur + 1;
V(entrée); // condition.signal
V(mutex_monitor); // condition.signal
return; // condition.signal
V(mutex_monitor);
}
début :
Init(mutex_monitor, 1);
Init(entrée, 0); |
J'ai mis les initialisations des sémaphores à la fin du code.
Notez les trois lignes pour que cond.signal soit la dernière instruction exécutée dans le moniteur.
J'espère que le problème apparaît assez clairement. Lorsqu'on fait cond.wait on risque d'attendre, mais on a pas rendu le mutex du moniteur.
Remplacer les cond.wait par
Code:
1
2
3
| V(mutex_monitor);
P(cond);
P(mutex_monitor); |
ça ne marche pas non plus car on risque de se faire préempter entre deux lignes.
Y'a t-il une autre solution que de décomposer le cond.wait ?
Parce que je vous avouerais que ça m'enchante pas vraiment de devoir réécrire une partir de l'opération P alors que c'est sûrement mieux fait dans la libc.
Désolé de la tartine mais je voulais être sûr de bien faire comprendre mon problème du premier coup. :P
