Discussion :

[Celelibi]

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.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[pseudocode]

Je ne vois pas bien ou est le probleme du Parking si on dispose deja d'un semaphore...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
sémaphore : parking;
 
début :
	Init(parking, 20);
 
procedure enter_parking {
	P(parking);
}
 
procedure exit_parking {
	V(parking);
}

Generalement c'est plutot l'inverse qu'on cherche a faire: on dispose d'un monitor et on veut en faire un semaphore.


Mais bon, pour répondre a ta question, je pense qu'on pourrait fusionner la condition et le montior comme ca:

(j'ai pas testé a fond, donc attention aux bugs )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
Semaphore monitor;
Semaphore condition;
 
début:
	Init(monitor, 1);
	Init(condition, 0);
 
 
procedure wait() {
	P(condition);	// attente de la condition (waiter)
	P(monitor);	// Pas plus d'un processus dans le monitor
}
 
procedure signal() {
	V(condition);	// declanche la condition -> libere un waiter
			// ou permet a un futur waiter de s'executer
}
 
procedure release() {
	V(monitor);	// libere le monitor.
			// Ne pas oublier d'appeler cette procedure apres un wait()
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
procedure enter_parking {
	mutex_enter();
	if (compteur>MAXIMUM) {
		mutex_exit();
		parking.wait();
		mutex_enter();
		compteur++;		
		parking.release();
	} else {
		compteur++;
	}
	mutex_exit();
}
 
procedure exit_parking {
	mutex_enter();
	compteur--;
	mutex_exit();
 
	parking.signal();
 
}

[Celelibi]

Je ne vois pas bien ou est le probleme du Parking si on dispose deja d'un semaphore...

Le but c'était juste de montrer un exemple d'utilisation des moniteurs. Bien entendu on pourrait le faire avec des sémaphores.


Sinon, je ne suis pas sûr de comprendre toute la sémantique de la solution que tu propose.
Dans ton implémentation des variables condition, à quoi correspond le sémaphore "monitor" ?
Et le mutex il protège quoi ?

J'ai l'impression que le mutex ne protège que l'accès à la variable compteur. Ceci est censé être garanti par l'accès exclusif au fonctions et procédures du moniteur.


Bien que je n'ai pas tout compris, il semble y avoir un bug si dans entrée_parking on se fait préempter entre mutex_exit(); et parking.wait(); et qu'il y a un exit_parking entre temps.

[pseudocode]

Et le mutex il protège quoi ?
J'ai l'impression que le mutex ne protège que l'accès à la variable compteur.

Oui, c'est exact.

Ceci est censé être garanti par l'accès exclusif au fonctions et procédures du moniteur.

Ca depend de la definition du monitor. Si le monitor ne contient que wait/signal comme tu le souhaites (= Hoare), alors tu dois toi meme verouiller l'accès a la ressource.

Si tu rajoutes acquire/release, le monitor peut tout faire (= Mesa). C'est l'implementation "standard" du monitor.

(http://en.wikipedia.org/wiki/Monitor_(synchronization)).

Le principe est de toujours faire un acquire() avant un wait(), et de toujours faire un release() a la fin.

(par exemple, en java: http://javasearch.developpez.com/j2s...ct.html#wait())

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
Semaphore monitor;
Semaphore condition;
 
début:
	Init(monitor, 1);
	Init(condition, 0);
 
 
procedure wait() {
	release();	// il faut avoir fait un acquire() avant le wait()
	P(condition);	// attente de la condition = attente de signal()
	acquire();	// Pas plus d'un processus dans le monitor
}
 
procedure signal() {
	V(condition);	// declanche la condition -> libere un waiter
			// ou permet a un futur waiter de s'executer
}
 
procedure acquire() {
	P(monitor);;	// verrouille le monitor.
}
 
procedure release() {
	V(monitor);	// libere le monitor.
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
procedure enter_parking {
	parking.acquire();
	if (compteur>MAXIMUM) {
		parking.wait();
	}
	compteur++;
	parking.release();
}
 
procedure exit_parking {
	parking.acquire();
	compteur--;
	parking.release();
	parking.signal();
}

en fait, il faudrait meme ecrire:

while (compteur>MAXIMUM) { parking.wait(); }

au cas ou quelqu'un envoie un signal sans decrementer le compteur.

Bien que je n'ai pas tout compris, il semble y avoir un bug si dans entrée_parking on se fait préempter entre mutex_exit(); et parking.wait(); et qu'il y a un exit_parking entre temps.

Normalement non.

Lorsque tu fais un "exit_parking", ca appelle parking.signal() qui "augmente" le semaphore condition de 1 grace au V(condition).

Au retour de la preemption, lors du parking.wait(), on fait un P(condition) qui sera donc non bloquant a cause du V(condition) précédent.

[Celelibi]

J'aurais dû approfondir un peu plus mes cherche un peu plus tôt. En effet bien que l'article français sur wikipedia à propos des moniteurs ne soit pas probant, celui en anglais est un peu plus complet et contient la réponse à ma question.

Donc je marque comme résolu, merci pseudocode.

[pseudocode]

de rien...

[Celelibi]

Juste histoire de voir si j'ai bien comris comment marchent les moniteurs Mesa :
Pour chaque moniteur la variable suivante est déclarée

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
sémaphore : mutex_monitor;
Init(mutex_monitor,  1);

Chaque fonction ou procédure du moniteur est entourée par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
P(mutex_monitor);
// le code de la procédure
V(mutex_monitor);

Pour chaque variable condition sont définis

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
sémaphore : cond;		// Pour la mise en attente
sémaphore : mutex_compteur;	// Pour éviter les races condition sur le compteur
entier : compteur := 0;		// Le compteur qui compte le nombre de processus en attente
 
Init(cond, 0);
Init(mutex_compteur, 1);

L'opération wait des variables condition est implémenté par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
procédure condition.wait {
	P(mutex_compteur);		// On verrouille l'accès au compteur
	compteur := compteur + 1;	// on va effectuer un P(cond), on sait pas dans combien de temps, mais on va le faire...
	V(mutex_compteur);		// On relâche le mutex du compteur
	V(mutex_monitor);		// On libère l'accès au moniteur
	P(cond);			// On met le processus en pause. Si entre temps il y a eut un condition.signal, cet appel n'est pas bloquant
	p(mutex_monitor);		// Pour continuer l'exécution il faut reprendre le mutex du du moniteur
}

Et l'opération signal

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
procédure condition.signal {
	P(mutex_compteur);		// On verrouille l'accès au compteur
	compteur := compteur - 1;	// Il y a un processus en moins qui attendra
	V(cond);			// On libère un processus qui attend
	V(mutex_compteur);		// On libère l'accès à la variable compteur
	V(mutex_moniteur);		// On se prépare à sortir du moniteur
	return;				// On sort du moniteur
}

Pour le moment j'ai tenté de suivre ce qui est indiqué sur la page wikipedia anglaise, mais j'ai quelques questions :
Est-ce que le mutex_compteur est obligatoire ? Normalement le mutex du moniteur devrait faire l'affaire non ?
Dans condition.signal, est-ce obligé de faire V(mutex_compteur) après V(cond) et pas avant ? Après tout on a déjà fini de manipuler compteur, et le mutex du moniteur empêche tout autre opération signal durant ce temps.

[pseudocode]

houla... il est tard mais je vais essayer de suivre.

Pour le moment j'ai tenté de suivre ce qui est indiqué sur la page wikipedia anglaise, mais j'ai quelques questions :
Est-ce que le mutex_compteur est obligatoire ? Normalement le mutex du moniteur devrait faire l'affaire non ?

Non, il n' y a pas besoin d'avoir 2 mutex. On peut reutiliser celui du monitor, si on y a accès (cf le code que j'avais donné).

Dans condition.signal, est-ce obligé de faire V(mutex_compteur) après V(cond) et pas avant ? Après tout on a déjà fini de manipuler compteur, et le mutex du moniteur empêche tout autre opération signal durant ce temps.

Oui on peut effectivement changer l'ordre... (cf le code que j'avais donné (2 le retour)).

Par contre je ne vois pas a quoi te sert le V(mutex_moniteur) dans signal() ?

[Celelibi]

Le V(mutex_moniteur) c'est parce que le "return" qui suit doit faire sortir du moniteur (pas uniquement de la "fonction" signal).

En fait dans ton code il manquait un compteur supplémentaire car il ne faudrait pas que l'opération signal effectue un V(cond) si il n'y a aucun processus à réveiller.
Donc je me disais que peut-être l'introduction de ce compteur introduisait de nouvelles race condition que je n'aurais pas vu.

Merci de ces éclaircissement.

Paf re-résolu.

[pseudocode]

En fait dans ton code il manquait un compteur supplémentaire car il ne faudrait pas que l'opération signal effectue un V(cond) si il n'y a aucun processus à réveiller.

Ah ok. C'est pour le cas ou tu veux attendre un "nouveau" signal, et pas prendre en compte un signal precedent.

Dans ce cas, au tout debut du wait(), je pense que tu peux remettre le semaphore "condition" a 0 s'il est strictement positif (c-a-d s'il y a deja des signaux empilés).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
procedure wait() {
	if (condition>0) Init(condition,0);
	release();
	...

Ca necessite de toujours faire un acquire/release pour envoyer un signal, pour ne pas perdre des signaux en cas de préemption dans le "if".
D'ailleur je crois que c'est comme ca que ca fonctionne en Java.

Merci de ces éclaircissement.

Paf re-résolu.