La complexité des verrous
Bonjour, je reviens vers vous sur mon forum d'entraide C++ favori, pour une situation de conception, qui concerne le partage de ressources entre plusieurs processus.
Voici l'énoncé de mon problème auquel il faut que je trouve une conception.
- On dispose d'une famille variable F d'objets (instance d'une classe), c'est à dire qu'on peut ajouter ou retirer autant d'objets que l'on souhaite à la famille.
- On dispose également d'un nombre indéfini de processus (threads) concourrants.
- Chacun de ces processus agit (en lecture ou écriture) sur une sous-famille E d'objets de F.
- Il peut exister un processus souhaitant créer un objet et l'ajouter dans F, ou un processus souhaitant supprimer un objet déjà existant de F.
- Il peut exister un processus souhaitant agir sur un objet n'existant pas dans F.
J'utilise le langage C++ et la POSIX Threads library (<pthread.h>) pour réaliser toute programmation parallèle.
Etant donné mon problème, et dès lors qu'on parle de programmation parallèle, il est clair qu'il faut introduire les notions de verrous.
Les mutex de la librairie pthread sont des interrupteurs, que tout le monde peut tenter d'allumer, d'éteindre, et même de créer / supprimer. Ils n'ont aucun contexte ni signification particulière, si ce n'est celui que l'on souhaite leur donner par une implémentation appropriée.
Etant donné mon problème, je souhaite utiliser les mutex pour leur fournir le comportement de verrou sur des objets partagés, donc simuler les verrous sur les adresses mémoires, tel le fonctionnement synchronized en JAVA...
Ici la notion de famille n'a pas trop d'importance, il n'est pas nécessaire de la représenter par une classe, ni d'ordonner les instances d'objets. Pourtant, cette classe semble s'imposer, puisqu'on souhaite, pour un processus donné, connaître si les objets existent ou non dans la famille avant d'être utilisés.
J'ai bien sûr réfléchi, et longuement sur mon sujet, et je propose deux solutions, mais sans qu'elles me paraissent satisfaisantes, la raison pour laquelle je viens vous demander conseil et si quelqu'un pouvait me faire part de son expérience dans un problème similaire préalablement rencontré.
Une première idée, naïve, consiste à ce que la classe objet possède un membre mutex, dont chaque instance aurait le sien qui lui est propre. Mais cette solution est incorrecte, essentiellement à cause de l'opération supprimer instance que peut réaliser un processus.
Une première vraie solution est qu'il faille écrire la famille F comme une classe type manager, qui fait correspondre à une instance d'objet un verrou particulier. Toutes les consultations d'existence ou de demande de verrou pour un processus passe par la classe manager, qui possède son propre verrou.
En schéma grossier ici :
http://img27.imageshack.us/img27/6157/79672835.png
Ici des pseudos-codes d'implémentation des opérations :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| Thread.demander_lock(E)
continu = locked //condition de boucle
/*
locked -> objet ou manager déjà verrouillé
locké -> les objets demandés ont étés verrouillés
else -> un objet est absent de la famille
*/
TANT QUE (continu = locked)
FAIRE continu = manager.lock(E, this)
SI continu = locké
ALORS traitement sur E
délocker E
SINON
erreur : au moins un élément de E est absent |
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
| Manager.lock(E, Thread)
résultat = locké //valeur de retour à la demande de verrou des objets
//si le manager est libre
SI (!pthread_mutex_lock(mutex manager)) //cf : 2
G = ensemble vide //Ensemble des objets qu'on réussit à verrouiller
/*
Parcours de tous les éléments à être verrouillé
Ici, le sens du parcours importe beaucoup, pour garantir qu'il n'y aura
pas de deadlock.
Les instances devant être verrouillées doivent donc être ordonnées
selon toujours la même relation d'ordre
cf : 1
*/
POUR CHAQUE x de E //Pour chaque objet
SI x existe
//Si on arrive à verrouiller l'objet, cf : 2
ALORS SI (!pthread_mutex_lock(x))
ALORS G = G U {x}
SINON
//objet déjà verrouillé
résultat = locked
déverouiller(G)
SINON
//objet non existant
résultat = objet_inconnu //(else)
déverouiller(G)
déverouiller(mutex manager)
retourner résultat |
En somme, cette solution dit une chose, si on arrive à verrouiller tous les objets d'un seul coup, on réalise le traitement. Si on a rencontré un objet qui n'existe pas, on est averti et on peut arrêter le traitement.
Mais si on a rencontré un objet qui est déjà verrouillé par autre processus, on déverrouille tous les objets qu'on a déjà sous la main, et on recommencera l'opération quand on reprendra la main, entre deux recommencements, on peut espérer que l'objet qui nous faisait défaut sera déverouillé, et qu'il n'y aura pas un autre objet verrouillé la prochaine fois.
Le problème bien sûr est que plus la famille E devient grande, et plus le nombre de processus augmente, plus on a de probabilité de rencontrer un objet déjà verrouillé, et donc de se confronter a des échecs qui ralentissent énormément le programme.
Une amélioration de cette solution, est que si un thread se confronte, toujours en gardant la classe manager, a un objet bloqué, il conserve les objets qu'il a déjà en main, en conservant un indice qui lui permet d'identifier dans E le prochain objet à demander de verrouiller, et personne ne peut les atteindre lorsqu'il est en attente des futurs objets qui doivent se libérer. La difficulté réside essentiellement à libérer le verrou manager, car pour pouvoir supprimer ou ajouter un élément, il faut absolument pouvoir verrouiller la classe, pour ne pas la corrompre.
Auquel cas le code devient :
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
30
| Manager.lock(E, Thread)
résultat = locké //valeur de retour à la demande de verrou des objets
//si le manager est libre
SI (!pthread_mutex_lock(mutex manager)) //cf : 2
//G = ensemble vide
//Ensemble des objets qu'on réussit à verrouiller
/*
Parcours de tous les éléments à être verrouillé
Ici, le sens du parcours importe beaucoup, pour garantir qu'il n'y aura
pas de deadlock.
Les instances devant être verrouillées doivent donc être ordonnées
selon toujours la même relation d'ordre
cf : 1
*/
POUR CHAQUE x de E //Pour chaque objet
SI x existe
//Si on arrive à verrouiller l'objet, cf : 2
ALORS SI (!pthread_mutex_lock(x))
ALORS //G = G U {x}
SINON
//objet déjà verrouillé
résultat = locked
//déverouiller(G)
SINON
//objet non existant
résultat = objet_inconnu //(else)
//déverouiller(G)
déverouiller(mutex manager)
retourner résultat |
Voilà, donc je vous demande conseil quand à mon problème de conception. Merci de m'avoir lu, et peut être de me répondre...
Mes sources :
1 : Des deadlocks
2 : pthread
