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 !

[GMany]

Ca y est je suis de retour ^^

J'ai réfléchi pendant cette nuit... La question des masques, ils ne peuvent même pas être générés une seule fois pour un processus... Ils doivent être créés à la volée, à chaque vérification, puisqu'on a dit que F a une taille variable, il n'est pas possible de prévoir la dimension du masque...

Il serait possible de réaliser une classe masque hybride, qui contiendrait certaines informations, et qui rendrait possible la création d'un masque par processus une fois seulement.

Mais au final, c'est sûrement moins efficace que comparer 1000 éléments (les éléments de Ep - ordonnés - qui eux sont déjà alloués une fois pour toute) 200² fois, qui représenterait 40 millions de comparaisons, soit environ 50 fois moins d'opérations dans mon exemple. Et même avec 40 millions d'opérations, je suis assez réticent, puisque la limite à atteindre devrait être une constante multiplié par le nombre de processus à chaque instant multiplié par le nombre d'éléments d'une sous-famille, donc de l'ordre de 200 000 opérations.

Sauvegarder une FIFO par objet à verrouiller ne paraît pas correct (en partant du principe qu'un processus ne peut être dans la file de une et une seule instance à chaque instant au maximum) ?
Ca représente 4 octets de plus par instance d'objet (qui n'est rien en comparaison de la taille totale d'une instance), et peut être 20 octets par processus lorsqu'il se trouve dans une file...

[Mac LAK]

Ils doivent être créés à la volée, à chaque vérification, puisqu'on a dit que F a une taille variable, il n'est pas possible de prévoir la dimension du masque...

On peut majorer cette taille, par contre, en conservant une honnête marge de sécurité.

Il serait possible de réaliser une classe masque hybride, qui contiendrait certaines informations, et qui rendrait possible la création d'un masque par processus une fois seulement.

En fait, je pensais plus à la mise à 1 des bits adéquats lors du scan du vecteur de lock.

Et même avec 40 millions d'opérations, je suis assez réticent, puisque la limite à atteindre devrait être une constante multiplié par le nombre de processus à chaque instant multiplié par le nombre d'éléments d'une sous-famille, donc de l'ordre de 200 000 opérations.

Vu les chiffres en jeu, de toutes façons, rien ne sera simple ou trivial.

Sauvegarder une FIFO par objet à verrouiller ne paraît pas correct (en partant du principe qu'un processus ne peut être dans la file de une et une seule instance à chaque instant au maximum) ?

Le problème est que cela va demander de gérer un nombre assez hallucinant de FIFO, et surtout, de les synchroniser entre elles afin de conserver la notion de "vecteur"... Cela ne va pas être simple du tout, car (pour donner un exemple numérique) l'indice 0 de la FIFO peut correspondre à des centaines de processus différents !!
Donc, il va falloir effectuer des parcours intégraux de toutes les classes, et "chercher" dans les FIFO un PID particulier... Complexité O(M+N), donc, avec des comparaisons d'entiers 32 bits.
Il va falloir réfléchir un peu plus à cette problématique : le reste est cohérent et normalement pas très coûteux en temps CPU, seul ce point va conditionner réellement les performances.

[GMany]

Je t'avoue que j'ai un peu du mal à raisonner et comprendre ton approche des FIFO.

Je vais essayer de prendre chaque point que tu as soulevé, et tenter de comprendre.

Le problème est que cela va demander de gérer un nombre assez hallucinant de FIFO

Sur ce point je suis d'accord, sauf pour le fait que ça représente un problème. ^^
C'est tout autant le même problème que de gérer le nombre hallucinant d'instances, et de verrous par instance, on a le même nombre. Et une FIFO dans le meilleur des cas n'en est pas une, mais juste un pointeur NULL.

les synchroniser entre elles afin de conserver la notion de "vecteur"

C'est encore une fois tout autant le même problème que de synchroniser entre eux les verrous de chaque instance non ?

l'indice 0 de la FIFO peut correspondre à des centaines de processus différents

Là je ne comprend pas une seule seconde, cette phrase me laisse perplexe.

Donc, il va falloir effectuer des parcours intégraux de toutes les classes, et "chercher" dans les FIFO un PID particulier... Complexité O(M+N), donc, avec des comparaisons d'entiers 32 bits.

J'ai peut être omis quelque chose, mais il ne me semble pas qu'à un seul moment j'ai une opération qui a une telle complexité (si N est le nombre d'instances objets et M le nombre de processus ?)...

J'ai l'impression d'être très embêtant, et en soumettant ce problème, et dans la recherche de solution.

Si raisonner sur ce problème ne te prend pas trop de temps ou te motive, je peux peut être te montrer mes schémas type UML des classes que j'ai imaginé, peut être qu'on évoquerait plus concrètement les problèmes ?

En tout cas je te remercie d'avoir pris le temps de me répondre jusque là.

[screetch]

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.

un jour pour écrire du code rapide il faudra bien éviter ce genre d'approches avec des verrous, et arreter de dire "il faut des mutex".

Il existe quelques solutions "lock-free" qui permettent de s'en tirer pour peu qu'on y ait pensé en avances, grace a despoperations atomiques.
Et ce a quoi je pense immédiatement, c'est : est ce que chaque processus peut toucer a n'importe quel objet, ou est ce que tu pourrais restreindre l'acces des objets a un seul processus (en gros tu aurais un thread qui s'occuppent des objets 1 a 10, un autre 11 a 20, etc) et du coup pas de locks

ca ne resout sans doute pas ton probleme, je reagissais seulement a la petite phrase au milieu de ton post qui m'a fait un peu sursauter.

[GMany]

Il existe quelques solutions "lock-free" qui permettent de s'en tirer pour peu qu'on y ait pensé en avances, grace a despoperations atomiques.

Ben écoute si tu as une solution sans mutex je suis tout ouï
L'origine des mutex et sémaphore remonte aux années 1980, et a été la solution aux problèmes du dîner des philosophes par Dijkstra... Depuis, des chercheurs s'y sont mis, je ne crois pas qu'ils aient trouvé une autre solution...

Et ce a quoi je pense immédiatement, c'est : est ce que chaque processus peut toucer a n'importe quel objet, ou est ce que tu pourrais restreindre l'acces des objets a un seul processus (en gros tu aurais un thread qui s'occuppent des objets 1 a 10, un autre 11 a 20, etc) et du coup pas de locks

Oui, tous les processus peuvent toucher n'importe quel objet, c'est le principe de famille d'objets partagés. Typiquement, tous ces objets sont des tous instances d'une même classe. De plus, les threads peuvent être tous des instances d'une même classe, les opérations sont donc toutes les mêmes, mais avec à chaque fois un nombre et des instances différentes.

[Mac LAK]

Sur ce point je suis d'accord, sauf pour le fait que ça représente un problème. ^^
C'est tout autant le même problème que de gérer le nombre hallucinant d'instances, et de verrous par instance, on a le même nombre. Et une FIFO dans le meilleur des cas n'en est pas une, mais juste un pointeur NULL.

En effet, ce n'est pas un problème de "place" mémoire, mais de nombre... J'explique :

C'est encore une fois tout autant le même problème que de synchroniser entre eux les verrous de chaque instance non ?

Justement non. Un mutex, il est pris ou libre uniquement, on est d'accord là-dessus ? De plus, on se contrefiche de savoir par QUI la classe est verrouillée, si elle l'est... On sait que le processus qui la verrouille ne va pas la redemander sans la libérer, et ça suffit amplement comme info. C'est donc simple à gérer.

Or, ta FIFO "unitaire", elle, va devoir contenir un objet (quelconque, un PID ou un pointeur vers une structure de données) permettant d'identifier le processus demandeur.
Le problème, c'est que si pour la classe à verrouiller N, par exemple, ton processus A est en position 0, il peut être en position 2 pour la classe N+1, en position 1 pour la classe N+2, etc.
Bref, tu n'as pas d'indice "global" te permettant de retrouver facilement la position du processus dans chaque FIFO individuelle... Ce qui va rendre la recherche assez gênante, voire longue.
C'est en ce sens que la synchronisation entre une multitude de FIFO individuelles va être relativement pénible, bien plus que de faire une FIFO globale qui contient le vecteur de lock lui-même...

Ce ne serait pas un problème si tu pouvais locker une partie du vecteur seulement (= répondre "au mieux"), mais ta contrainte de verrouiller toutes les instances demandées ou aucune est très gênante pour les performances et la simplicité d'implémentation.

Là je ne comprend pas une seule seconde, cette phrase me laisse perplexe.

Peut-être est-ce plus clair avec l'explication ci dessus ?
Le rang 0 des FIFO unitaires (= le prochain à être dépilé) peut correspondre à n'importe quel processus, car c'est simplement le premier qui a demandé qui sera à cet indice.
Et un de tes processus demandeur peut donc être en première position pour une instance donnée à verrouiller, être en 10ème position pour une autre, voire en 100ème position pour encore une autre.
Bref, pour un processus demandeur donné, il n'existe pas "un seul" indice dans les FIFO unitaires qui lui correspond, la recherche doit donc se faire séquentiellement dans chaque FIFO unitaire.

J'ai peut être omis quelque chose, mais il ne me semble pas qu'à un seul moment j'ai une opération qui a une telle complexité (si N est le nombre d'instances objets et M le nombre de processus ?)...

Si, la recherche dans les FIFO unitaires justement... Opération que tu évites via une (ou deux) FIFO globales.

J'ai l'impression d'être très embêtant, et en soumettant ce problème, et dans la recherche de solution.

Bah, on est là pour en discuter aussi, hein...

Si raisonner sur ce problème ne te prend pas trop de temps ou te motive, je peux peut être te montrer mes schémas type UML des classes que j'ai imaginé, peut être qu'on évoquerait plus concrètement les problèmes ?

Pas forcément, j'ai constaté par expérience qu'un mécanisme de lock complexe mais efficace possède très rarement un diagramme UML "propre"... Souvent, le diagramme est même plutôt infect.
La trop grande simplicité d'un verrou complexe en représentation UML est souvent (pas obligatoirement, mais SOUVENT) une cause de baisse de performances assez lourde.

Le but est surtout de trouver une architecture compatible avec tes contraintes de base, qui ne sont pas spécialement négligeables... Comme je te l'ai dit, ton plus gros nid à emmerdes est ce lock vectorisé "manichéen", on pourrait trouver des méthodes nettement plus performantes via des locks partiels.

Il existe quelques solutions "lock-free" qui permettent de s'en tirer pour peu qu'on y ait pensé en avances, grace a despoperations atomiques.

Ce qui est en général dépendant de l'implémentation, et/ou du compilateur, et/ou de la cible matérielle... Tous les compilateurs / plate-formes ne possèdent pas l'équivalent des fonctions Interlocked* disponibles sous Windows, par exemple.

De plus, les solutions lock-free peuvent poser le problème, justement, de ne PAS verrouiller l'appelant... Ce qui l'oblige soit à redemander sans cesse la même opération (polling), très inefficace, soit à utiliser moult signaux / sémaphores / messages pour assurer une gestion asynchrone.

[GMany]

Le problème, c'est que si pour la classe à verrouiller N, par exemple, ton processus A est en position 0, il peut être en position 2 pour la classe N+1, en position 1 pour la classe N+2, etc.

Dans ta proposition, tu continues à verrouiller la sous-famille d'un processus malgré que tu aie rencontré un échec. Moi je m'arrête dès qu'il y a un échec de verrou, ce qui fait qu'un processus ne peut être dans la FIFO que d'une et une seule instance d'objet à la fois. En aucun cas il ne peut se trouver dans 2 FIFO différentes.

Quand un processus libère un verrou, le thread premier sorti pour l'attente de cet objet est réveillé, et ce processus retente de verrouiller les objets qu'il lui reste à verrouiller, toujours dans le même ordre de la sous-famille. Cet ordre qui d'ailleurs est le même quelque soit la sous-famille.

[Mac LAK]

Dans ta proposition, tu continues à verrouiller la sous-famille d'un processus malgré que tu aie rencontré un échec. Moi je m'arrête dès qu'il y a un échec de verrou, ce qui fait qu'un processus ne peut être dans la FIFO que d'une et une seule instance d'objet à la fois. En aucun cas il ne peut se trouver dans 2 FIFO différentes.

Alors c'est qu'on s'est mal compris sur le terme "sous-famille"... Pour moi, cela représente un vecteur de lock parmi les instances d'objets verrouillables, chacun d'eux possédant sa propre FIFO unitaire. Le processus demandeur doit donc s'inscrire, s'il demande un vecteur de K classes, dans K FIFO.

Si ce n'est pas ça, j'avoue ne pas voir à quel niveau (entre les FIFO unitaires et une seule et unique FIFO globale) où se situent les FIFO de sous-famille dont tu parles... Ni surtout à quoi elles servent, vu qu'apparemment, seuls des processus ayant demandé exactement le même lock (chose rare !) pourraient bénéficier de la mise en file... J'entends d'un point de vue soit de fonctionnement, soit de vitesse d'exécution.

Si tes processus tentent de verrouiller au maximum possible, puis attendent sur LA instance bloquante en FIFO (en ayant donc déjà verrouillé d'autres classes), tu es pile poil dans une situation de deadlock potentielle. S'il tente à chaque fois de tout verrouiller (donc sans bloquer une seule classe entre deux essais), alors tu risques la situation de famine.

[screetch]

Il y aurait un autre type de solution qui consisterait a avoir une copie des données (c'est sans doute utopique vu la taille de tes données, mais une partie copiée peut etre)

chaque thread fait ses opérations sur la copie, en lecture seule, et envoie le resultat a un thread "serialiseur" qui se charge de tenmpes en temps de copier les données. Il est possible que quelques threads entrent du coup en collision, et on peut demander au deuxieme de refaire ses operations. C'est en general tres efficace si il y a peu de collisions statistiquement.

[GMany]

Je pense avoir trouvé la solution, fonctionnelle et adaptée. Le problème de ce sujet est en fait un sous-problème d'un problème bien plus important que je peux énoncer si vous le souhaitez.

Pour ce sous-problème, ma solution peut être décrite comme une utilisation adaptée des pattern singleton, factory et pool.

[Mac LAK]

Effectivement, exposer le problème d'origine serait peut-être préférable...

[GMany]

Voilà l'exposé, on a le même en modèle lecteur / rédacteur...

[Mac LAK]

Le moins que l'on puisse dire, c'est que l'énoncé n'est pas un modèle de clarté...

Bon, ceci étant dit, il y a des portes de sorties par rapport aux contraintes (sur la famine notamment), et à part "nombre d'opérations minimal", je ne vois pas de contraintes particulières sur les performances.

C'est quoi, à la base ? Un sujet d'exercice ? De stage ? Doit-on réellement réaliser ce système de locks, ou simplement le concevoir ?

[GMany]

Le but c'est de proposer un modèle quelque soit la classe U, donc d'en faire un pré-requis à toute programmation parallèle. Et donc d'automatiser le verrouillage de n'importe quel objet dans un projet, sans deadlock garanti et chien de garde intégré pour les processus qui ont attendu un peu trop longtemps.

Ce n'est ni un exercice ni un stage, c'est une étape dans ma todolist ^^