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...