Discussion :

[GMany]

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 :



Ici des pseudos-codes d'implémentation des opérations :

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

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

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

[Mac LAK]

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.

Aucun souci là-dessus.

On dispose également d'un nombre indéfini de processus (threads) concourrants.

Processus, donc il faut prendre des éléments accessibles à tous les éléments du système... Le plus simple serait encore tout simplement d'avoir une mémoire partagée contenant les structures des mutex en question, dans un tableau suffisamment dimensionné pour les besoins du programme. Au pire, prévoir une classe singleton (par processus) d'encapsulation de cette mémoire partagée et mutex, avec une gestion par pages pour obtenir une taille virtuellement illimitée.

Chacun de ces processus agit (en lecture ou écriture) sur une sous-famille E d'objets de F.

Tu ne précises pas si les processus en question peuvent avoir un accès lecture multiple (c'est à dire que plusieurs processus simultanément peuvent, ou pas, lire une classe donnée). Ceci conditionne assez fortement le type de mutex à utiliser, ainsi que les performances du système. Un mutex lecteurs/rédacteur par exemple peut sévèrement améliorer les performances d'un système où l'écriture/modification est "rare", et la lecture très fréquente...

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.

L'ajout ne pose souvent aucun problème, étant donné qu'en général on ne va pas tenter d'utiliser une classe inexistante. Au pire, cela peut être vu comme une demande de lock d'un sous-ensemble réduit à un seul élément...
La suppression peut se régler sans mutex : il suffit de mettre un attribut à tes classes "Destruction demandée", qui sera traité dès la sortie de la section critique et mettra donc l'instance à la destruction. Si cette technique n'est pas possible, alors il faudra utiliser un sous-ensemble réduit à un seul élément, comme pour la création.

Il peut exister un processus souhaitant agir sur un objet n'existant pas dans F.

Là, c'est plus complexe : quel doit être le comportement exactement ? Refus ? Attente d'existence ? On ignore simplement l'objet en question ?
De plus : l'absence de cet objet serait lié à quoi ? Destruction par un autre processus, ou création "en retard" ?


Par rapport à ton problème général, j'aurais tendance à privilégier une classe de gestion à laquelle on demande un certain nombre de "locks".

J'explique : on demande les locks de façon vectorielle, en demandant TOUS les locks simultanément. Chaque processus envoie sa demande à la classe de gestion au travers d'une FIFO, et se retrouve bloqué jusqu'à traitement de la demande.
La classe de gestion prends le premier vecteur de locks, et tente de l'honorer au mieux : le résultat est donc soit positif (les objets demandés sont verrouillés), soit négatif (des objets manquent, par exemple). Dans tous les cas, elle libère le processus demandeur.
Ensuite, elle prends la demande suivante : il faut alors vérifier si elle est disjointe des éléments déjà verrouillés. Si oui, elle est honorée immédiatement (elle n'entre pas en conflit avec le lock courant), le processus demandeur étant libéré. Si non, elle est mise en attente, le processus demandeur restant bloqué.
On traite ensuite la troisième demande : la vérification de disjonction doit se faire bien sûr avec les locks en cours, mais aussi avec toutes les demandes en attente. Si c'est disjoint, on honore immédiatement, sinon on ajoute à la file des demandes en attente.

Si tu définis une granularité suffisante pour tes demandes, tu peux obtenir une occupation maximale de tes processus facilement. De plus, tu conserves un principe de "premier arrivé, premier servi" dans la mesure du possible, tout en laissant passer les demandes non-interférantes lorsque cela est possible.

Là où ça peut devenir un peu plus chaud, c'est avec des mutex lecteurs/rédacteur : dans ce cas, seules les demandes en écriture sont de "vrais" locks, les accès en lecture étant systématiquement autorisés SAUF si un accès écriture est en cours. Mais cela reste assez simple malgré tout, il suffit de savoir si le lock est en écriture, en lecture ou non-locké, donc trois états possibles pour chaque objet.

Reste ensuite la problématique de rendre tout ça global au système : c'est plutôt simple à faire si l'on n'a que des threads, c'est un peu plus complexe avec des processus (notamment par rapport à l'existence d'un singleton "système" de la classe de gestion des locks). Toutefois, rien d'insurmontable à ça, il faut et il suffit d'avoir un processus maître et de la mémoire partagée pour résoudre ça de façon absolue.


Est-ce que cela t'aide un peu ? As-tu besoin d'explications supplémentaires ?

[GMany]

Salut, merci beaucoup de m'avoir lu et d'avoir pris le temps de répondre.

Tu ne précises pas si les processus en question peuvent avoir un accès lecture multiple (c'est à dire que plusieurs processus simultanément peuvent, ou pas, lire une classe donnée). Ceci conditionne assez fortement le type de mutex à utiliser, ainsi que les performances du système. Un mutex lecteurs/rédacteur par exemple peut sévèrement améliorer les performances d'un système où l'écriture/modification est "rare", et la lecture très fréquente...

Pour une instance d'objet donnée, il n'y a qu'un et un seul processus en lecture ou écriture. La lecture n'est pas l'opération majoritaire. Dans la plupart des cas, il s'agira d'une écriture, car dans mon exemple d'application précis, la lecture d'une instance entraîne sa modification par le processus lecteur (modification qui est en réalité une actualisation de l'instance).

Il peut exister un processus souhaitant agir sur un objet n'existant pas dans F.
Là, c'est plus complexe : quel doit être le comportement exactement ? Refus ? Attente d'existence ? On ignore simplement l'objet en question ?
De plus : l'absence de cet objet serait lié à quoi ? Destruction par un autre processus, ou création "en retard" ?

L'absence d'une instance peut être causée de plusieurs façons. Un processus peut décider de supprimer l'instance, alors qu'un autre était en attente de consultation. Il est également possible qu'un processus effectue une requête sur une instance qui n'a jamais existé. On peut par exemple prendre le cas d'un serveur d'objets, où des clients via un client tcp/ip peuvent manipuler ces objets, et à chaque requête serait créé un processus.

Quand un processus tente d'accéder à une instance qui n'existe pas, la réponse à apporter est un refus du processus.

En ce qui concerne la taille de F. On n'a aucune idée du nombre d'éléments qu'elle contient. On peut au mieux majorer le nombre d'objets présents à chaque instant, mais on peut supposer que la famille vive un temps indéfini, et on verrait alors passer une infinité d'instances différentes tout au long de la vie de la famille.

Voilà pour les explications supplémentaires.
J'ai également lu la solution que tu propose, et elle semble similaire à celle que j'ai esquissé dans le 1er message.

J'explique : on demande les locks de façon vectorielle, en demandant TOUS les locks simultanément.

Je pars effectivement sur des verrouillages par vecteurs, puisqu'il faut absolument que la sous-famille à traiter E soit connue de tous ses éléments. En effet, si tel n'est pas le cas, on ne peut pas garantir qu'il n'y aura pas de deadlocks, les verrouillages doivent se passer toujours dans le même ordre des éléments à verrouiller, et donc cela suppose que l'ensemble des éléments à verrouiller soit connu.

Par contre, la suite ne me semble pas judicieuse au niveau du nombre de calculs à réaliser.

On traite ensuite la troisième demande : la vérification de disjonction doit se faire bien sûr avec les locks en cours, mais aussi avec toutes les demandes en attente. Si c'est disjoint, on honore immédiatement, sinon on ajoute à la file des demandes en attente.

Ici, si la file d'attente est très élevée, on atteint un nombre impressionnant de calculs, des calculs qui ne sont pas encore en rapport avec le travail à effectuer. Même si la granularité est élevée, il se peut que le nombre de processus soit très grand, et qu'il y en ai beaucoup en attente, et si un processus se voit accepté parce que toutes les instances dont il souhaite prendre le contrôle sont libres, il faut qu'il regarde si quelqu'un ne passe pas avant lui, et ces quelqu'un sont très nombreux...

Pour tout dire, le principe de premier arrivé premier servi n'est pas fondamental dans l'utilisation que j'aurais à en faire. Mais il n'est pas interdit que je rencontre un cas où ce principe devra être respecté. Auquel cas je pense que adopter une liste d'attente pour chaque instance peut être judicieux, un processus ne pouvant être dans la liste d'attente que d'une et une seule instance à la fois au maximum (dès lors qu'on rencontre un échec de verrouillage, on ne peut pas demander le verrouillage de la ressource suivante, car l'ordre est obligatoire pour éviter les deadlocks, donc dès que la classe manager rencontre un échec, le processus serait mis en attente pour la ressource souhaitée uniquement). Dès lors qu'un ressource est libérée, elle regarde sa file d'attente et donne la main au thread en début de sa file de priorité. Mais là j'avoue que le respect de ce principe n'est pas primordial.

Je me suis encore repenché sur ma solution, qui s'apparente beaucoup à la tienne, et si on omet le principe FIFO, je pense qu'elle peut être satisfaisante.

• Un processus P prend connaissance de Ep, sous-famille de F qu'il souhaite prendre en main.
• Il demande à la classe manager M de les verrouiller.
• Pour cela, la classe manager, si elle n'est pas verrouillée, se verrouille pour ce processus P.
• Pour chaque instance de Ep qu'il reste à verrouiller pour le processus en question, la classe manager vérifie leur existence et les verrouille pour P.
• Dès qu'elle trouve une ressource qui n'existe pas, elle demande au processus P de déverouiller toutes les instances qui sont en sa possession et de stopper son traitement, et la classe manager se déverouille.
• Dès qu'elle tombe sur une ressource qui est déjà verrouillé par un autre processus, elle s'arrête, et se déverouille, le verrouillage pour ce processus P reprendra plus tard.

Je ne sais pas si cette solution est satisfaisante au niveau des performances. Peut être que beaucoup de processus peuvent tourner dans le vide, et nuire aux performances des autres processus qui travaillent, auquel cas il faudrait peut être quand même adopter le système de file d'attente pour chaque ressource, et faire dormir les processus dont on sait qu'ils sont en attente de déverrouillage...

En tout cas oui merci ta solution m'invite à persévérer vers la même solution, et tu m'es d'une bonne aide.

[Mac LAK]

Pour une instance d'objet donnée, il n'y a qu'un et un seul processus en lecture ou écriture.

Bon, donc, mutex simples, pas le choix.

Quand un processus tente d'accéder à une instance qui n'existe pas, la réponse à apporter est un refus du processus.

Oui, mais ce n'est pas assez précis : refus pour tout le vecteur de lock, ou juste pour l'objet manquant ?

Ici, si la file d'attente est très élevée, on atteint un nombre impressionnant de calculs

Meuh non !
En fait, il faut et il suffit de gérer tes classes comme faisant partie d'un tableau, à base zéro et pouvant contenir des "trous". La taille maximale importe peu, tu vas comprendre.

Si à chaque cellule (=objet) tu associe un bit, tu peux alors ranger ces bits dans un entier, OK ? Ainsi, en archi 32 bits, tu vas donc avoir un vecteur d'entiers 32 bits qui va représenter, bit à bit, le tableau des objets à verrouiller.
Calculer la disjonction, l'union, etc. se fait via de simples (et très rapides !!) opérations AND, OR et surtout, XOR (pour la disjonction). Les calculs sont au contraire ridiculement rapides.

Pour ceci, il te faudra simplement bidouiller une petite classe "Entiers binaires super longs" afin de contenir ces données. C'est fait en une ou deux heures normalement, pas plus, avec les surcharges d'opérateur bien entendu. Il n'est pas nécessaire à priori d'utiliser des librairies d'entiers longs : dans ton cas, tu n'as pas besoin des propagations de retenues, et tu peux méchamment optimiser les assignations de bits. On en reparlera au besoin, ce serait un peu long à expliquer quand même.

Pour tout dire, le principe de premier arrivé premier servi n'est pas fondamental dans l'utilisation que j'aurais à en faire.

En fait, si, mais à cause d'un effet de bord. C'est pour éviter tout simplement une situation de famine, qui provoquerait le blocage quasi-définitif d'un processus.

Je me suis encore repenché sur ma solution, qui s'apparente beaucoup à la tienne, et si on omet le principe FIFO, je pense qu'elle peut être satisfaisante.

L'avantage de la mienne, avec sa double FIFO, c'est que tu peux (via les masques binaires que j'ai explicité ci-dessus) obtenir d'excellentes performances, tout en évitant toute situation de famine.

De plus, elle est facilement adaptable pour permettre, par exemple, des verrouillages "au mieux" si jamais ton algorithme doit être modifié en ce sens lors de la demande de lock d'un vecteur au moins un objet qui n'existe plus...

Je ne sais pas si cette solution est satisfaisante au niveau des performances.

Je pense que non, car tu vas avoir sûrement beaucoup d'échecs de verrouillage, et donc une perte de temps CPU à redemander un nouveau lock... Qui risque d'échouer tout autant si un autre processus s'est inséré entre temps !
C'est pour ceci que je ne fais jamais d'algos de locks aussi complexes sans utiliser une ou plusieurs FIFO, afin d'assurer le service sans famines ni sur-demandes.
Ceci s'inscrit aussi dans la démarche d'avoir des pré/post conditions extrêmement simples pour tes fonctions de lock. En l'occurrence, la FIFO te permet de garantir que l'on ne revient de la demande que dans deux cas :

• On a obtenu le lock demandé,
• Un (ou plusieurs) des objets demandés sont détruits.

Et encore, le deuxième point peut être adapté en "Certains objets n'ont pu être verrouillés, on retourne la liste des éléments réellement lockés"...

En tout cas oui merci ta solution m'invite à persévérer vers la même solution, et tu m'es d'une bonne aide.

Tu n'es déjà pas loin d'une solution viable, en tout cas. Déjà, tu es sur la bonne piste, je pense, et c'est déjà un pas énorme !

Après, réfléchis un peu sur les FIFO et les masques binaires pour calculer les intersections / unions / disjonctions des vecteurs. N'oublie pas l'évolutivité aussi : ce genre de classe de gestion est assez difficile à mettre au point. Si tu penses avoir besoin de plusieurs comportements, autant les coder d'entrée de jeu (ou au moins les prévoir...) afin de ne pas être obligé de tout casser en cas d'évolution... Quitte à laisser des paramètres inutilisés dans les fonctions/méthodes pour assurer l'évolutivité.

[GMany]

Pour donner un ordre de grandeur :

Le nombre d'éléments à chaque instant dans la famille F avoisine 2 millions.
Le nombre de processus en activité à chaque instant est d'environ 200.
Le nombre d'éléments d'une sous-famille à verrouiller peut atteindre le millier.

En somme, on peut se dire qu'il y a à chaque instant 1/10e seulement des éléments qui sont demandés à être verrouillés. Mais ce n'est pas une loi de répartition équi-répartie ni aléatoire. Des éléments sont très représentés, d'autres beaucoup moins, et plus un élément est demandé, plus il le sera pour les futurs processus, cela donne des effets empiriques, avec une limite maximum.

Créer un masque de 2 millions d'éléments revient à allouer pour chaque processus en attente 250 Ko, dans un cas de crise on peut atteindre 50 Mo, avec un ordre de 200² comparaisons de masques, soit 200² * 62500 cycles processeurs, soit 1 seconde avec un ordinateur correct...

Je vais tâcher d'étudier ta solution plus en profondeur, mais plus maintenant, parce que j'ai veillé toute la nuit, maintenant je suis fatigué.

[Mac LAK]

Le nombre d'éléments à chaque instant dans la famille F avoisine 2 millions.
Le nombre de processus en activité à chaque instant est d'environ 200.
Le nombre d'éléments d'une sous-famille à verrouiller peut atteindre le millier.

OK, là, c'est nettement plus "parlant" côté dimensionnement. Je comprends mieux certaines de tes questions / problèmes également.

Créer un masque de 2 millions d'éléments revient à allouer pour chaque processus en attente 250 Ko, dans un cas de crise on peut atteindre 50 Mo, avec un ordre de 200² comparaisons de masques, soit 200² * 62500 cycles processeurs, soit 1 seconde avec un ordinateur correct...

Effectivement, ce n'est pas possible avec des tableaux "brutaux" vu les tailles envisagées.
Il faudrait impérativement se limiter à des sous-ensembles optimisés contenant le minimum possible de champs de bits, soit au maximum 1000 entiers ne contenant qu'un seul bit "utile" chacun. Ce n'est pas impossible à faire, mais ça va prendre plus de temps... Peut-être via des vecteurs indexés, c'est à dire des maps faites à la main ? Chaque "case" contient l'index d'origine, plus l'entier correspondant au masque binaire...

Je vais tâcher d'étudier ta solution plus en profondeur, mais plus maintenant, parce que j'ai veillé toute la nuit, maintenant je suis fatigué.

Bonne nuit !