Synchronisation de l'accès à une liste à double lien

Question

J'essaie d'implémenter une liste (d'un type particulier) doublement liée en C, dans un environnement pthreads mais en utilisant uniquement des instructions de synchronisation enveloppées en C comme les CAS atomiques, etc. plutôt que des primitives pthreads. (Les éléments de la liste sont des morceaux de mémoire de taille fixe et ne peuvent certainement pas tenir dans la mémoire de l'utilisateur). pthread_mutex_t etc. à l'intérieur de celles-ci). En fait, je n'ai pas besoin de méthodes complètes et arbitraires de listes doublement liées, seulement :

• insertion à la fin de la liste
• suppression du début de la liste
• suppression à des points arbitraires de la liste sur la base d'un pointeur vers le membre à supprimer, qui a été obtenu à partir d'une source autre que le parcours de la liste.

Ainsi, une meilleure façon de décrire cette structure de données serait peut-être une file d'attente/fifo avec la possibilité de supprimer des éléments au milieu de la file d'attente.

Existe-t-il une approche standard de la synchronisation ? Je suis bloqué par d'éventuels problèmes de blocage, dont certains sont probablement inhérents aux algorithmes concernés et d'autres peuvent provenir du fait que j'essaie de travailler dans un espace restreint avec d'autres contraintes sur ce que je peux faire.

Modifier : En particulier, je suis bloqué sur ce qu'il faut faire si des objets adjacents doivent être retirés simultanément. Vraisemblablement, lors de la suppression d'un objet, vous devez obtenir des verrous sur les objets précédent et suivant dans la liste et mettre à jour leurs pointeurs next/prev pour qu'ils pointent les uns sur les autres. Mais si l'un des voisins est déjà verrouillé, cela entraînerait un blocage. J'ai essayé de trouver un moyen pour que toutes les suppressions en cours puissent parcourir la partie verrouillée de la liste et déterminer la sous-liste maximale qui est actuellement en cours de suppression, puis verrouiller les nœuds adjacents à cette sous-liste afin que la sous-liste entière soit supprimée dans son ensemble, mais je commence à avoir mal à la tête :-P

Conclusion( ?) : Pour poursuivre, j'ai un peu de code que je veux faire fonctionner, mais je suis aussi intéressé par le problème théorique. Les réponses de tout le monde ont été très utiles, et combinées avec des détails sur les contraintes en dehors de ce que j'ai exprimé ici (vous vraiment ne veulent pas savoir d'où vient le pointeur vers l'élément à supprimer et la synchronisation que cela implique !) J'ai décidé d'abandonner le code local-lock pour le moment et de me concentrer sur :

• en utilisant un plus grand nombre de petites listes qui ont chacune des verrous individuels.
• minimiser le nombre d'instructions sur lesquelles des verrous sont maintenus et fouiller dans la mémoire (de manière sûre) avant d'acquérir un verrou afin de réduire la possibilité de défauts de page et de manques dans le cache pendant qu'un verrou est maintenu.
• mesurer la contention sous une charge artificiellement élevée et évaluer si cette approche est satisfaisante.

Merci encore à tous ceux qui ont donné des réponses. Si mon expérience ne se passe pas bien, je pourrais revenir aux approches décrites (en particulier celle de Vlad) et essayer à nouveau.

Answer 1

Pourquoi ne pas simplement appliquer un verrou à gros grain ? Il suffit de verrouiller l'ensemble de la file d'attente.

Une solution plus élaborée (mais pas nécessairement plus efficace, cela dépend de votre modèle d'utilisation) consisterait à utiliser un verrou de lecture-écriture, pour la lecture et l'écriture, respectivement.

---

L'utilisation d'opérations sans verrou ne me semble pas être une très bonne idée dans votre cas. Imaginez qu'un thread traverse votre file d'attente, et qu'au même moment, l'élément "courant" est supprimé. Peu importe le nombre de liens supplémentaires que votre algorithme de traversée contient, tous ces éléments peuvent être supprimés, de sorte que votre code n'aurait aucune chance de terminer la traversée.

---

Un autre problème lié à la comparaison et à l'échange est qu'avec les pointeurs, on ne sait jamais si l'on pointe vraiment vers la même ancienne structure, ou si l'ancienne structure a été libérée et qu'une nouvelle structure est allouée à la même adresse. Cela peut ou non être un problème pour vos algorithmes.

---

Dans le cas d'un verrouillage "local" (c'est-à-dire la possibilité de verrouiller chaque élément de la liste séparément), une idée serait de faire en sorte que les verrous soient ordonnés. Le fait d'ordonner les verrous garantit l'impossibilité d'un blocage. Donc vos opérations sont comme ça :

Suppression par le pointeur p de la précédent article :

1. verrouiller p, vérifier (en utilisant peut-être un drapeau spécial dans l'élément) que l'élément est toujours dans la liste
2. verrouiller p->next, vérifier qu'il n'est pas nul et dans la liste ; de cette façon, vous vous assurez que le p->next->next ne sera pas supprimé entre-temps
3. verrouiller p->next->next
4. mettre un drapeau dans p->next indiquant qu'il n'est pas dans la liste
5. (p->next->next->prev, p->next->prev) = (p, null) ; (p->next, p->next->next) = (p->next->next, null)
6. libérer les serrures

Insérer au début :

1. tête de verrouillage
2. mettre le drapeau dans le nouvel élément indiquant qu'il est dans la liste
3. verrouiller le nouvel élément
4. verrouiller la tête->suivant
5. (tête->suivant->prév, nouveau->prév) = (nouveau, tête) ; (nouveau->suivant, tête) = (tête, nouveau)
6. libérer les serrures

Cela semble correct, je n'ai cependant pas essayé cette idée.

Essentiellement, cela fait fonctionner la liste à double lien comme si elle était une liste à simple lien.

---

Si vous n'avez pas le pointeur vers l'élément de liste précédent (ce qui est bien sûr généralement le cas, car il est pratiquement impossible de conserver un tel pointeur dans un état cohérent), vous pouvez faire ce qui suit :

Suppression par le pointeur c sur l'élément à supprimer :

1. verrouiller c, vérifier s'il fait toujours partie de la liste (cela doit être un drapeau dans l'élément de la liste), sinon l'opération échoue.
2. obtenir le pointeur p = c->prev
3. déverrouiller c (maintenant, c peut être déplacé ou supprimé par un autre thread, p peut être déplacé ou supprimé de la liste également) [afin d'éviter la désallocation de c, vous devez avoir quelque chose comme un pointeur partagé ou au moins une sorte de refcounting pour les éléments de la liste ici].
4. verrouiller p
5. vérifier si p fait partie de la liste (il pourrait être supprimé après l'étape 3) ; si ce n'est pas le cas, déverrouiller p et recommencer depuis le début
6. vérifiez si p->suivant est égal à c, si non, déverrouillez p et recommencez depuis le début [ici nous pouvons peut-être optimiser le redémarrage, pas sûr de l'ATM].
7. verrouiller p->next ; ici vous pouvez être sûr que p->next==c et n'est pas supprimé, car la suppression de c aurait nécessité le verrouillage de p
8. lock p->next->next ; maintenant tous les verrous sont pris, donc nous pouvons procéder
9. mettre l'indicateur que c ne fait pas partie de la liste
10. effectuer l'habituel (p->next, c->next, c->prev, c->next->prev) = (c->next, null, null, p)
11. libérer tous les verrous

Notez que le simple fait d'avoir un pointeur sur un élément de la liste ne peut pas garantir que l'élément ne sera pas désalloué, vous aurez donc besoin d'une sorte de refcounting, afin que l'élément ne soit pas détruit au moment même où vous essayez de le verrouiller.

---

Notez que dans le dernier algorithme, le nombre de tentatives est limité. En effet, les nouveaux éléments ne peuvent pas apparaître à gauche de c (l'insertion se fait à la position la plus à droite). Si l'étape 5 échoue et qu'une nouvelle tentative est nécessaire, cela ne peut être dû qu'au fait que p a été retiré de la liste entre-temps. Un tel retrait ne peut se produire plus de N-1 fois, où N est la position initiale de c dans la liste. Bien sûr, ce cas le plus défavorable a peu de chances de se produire.

Answer 2

Ne prenez pas cette réponse durement, mais ne faites pas ça.

Vous vous retrouverez presque certainement avec des bogues, et des bogues très difficiles à trouver en plus. Utilisez les primitives de verrouillage de pthreads. Elles sont vos amies, et ont été écrites par des personnes qui comprennent profondément le modèle de mémoire fourni par le processeur de votre choix. Si vous essayez de faire la même chose avec CAS et l'incrémentation atomique et autres, vous ferez presque certainement une erreur subtile que vous ne découvrirez que lorsqu'il sera beaucoup trop tard.

Voici un petit exemple de code pour illustrer le propos. Quel est le problème avec cette serrure ?

volatile int lockTaken = 0;

void EnterSpinLock() {
  while (!__sync_bool_compare_and_swap(&lockTaken, 0, 1) { /* wait */ }
}

void LeaveSpinLock() {
  lockTaken = 0;
}

La réponse est la suivante : il n'y a pas de barrière mémoire lors de la libération du verrou, ce qui signifie que certaines des opérations d'écriture exécutées dans le verrou peuvent ne pas avoir eu lieu avant que le prochain thread n'entre dans le verrou. Oups ! (Il y a probablement beaucoup d'autres bogues aussi, par exemple, la fonction ne fait pas le rendement approprié à la plate-forme à l'intérieur de la boucle de rotation et donc gaspille énormément de cycles CPU. &c.)

Si vous implémentez votre liste à double lien comme une liste circulaire avec un nœud sentinelle, vous n'avez besoin d'effectuer que deux affectations de pointeur pour retirer un élément de la liste et quatre pour en ajouter un. Je suis sûr que vous pouvez vous permettre de détenir un verrou exclusif bien écrit sur ces affectations de pointeurs.

Notez que je suppose que vous ne faites pas partie des quelques personnes qui comprennent profondément les modèles de mémoire uniquement parce qu'il y en a très peu dans le monde. Si vous êtes l'une de ces personnes, le fait que même vous ne puissiez pas le comprendre devrait être une indication de la difficulté du problème.)

Je suppose également que vous posez cette question parce que vous avez un code que vous aimeriez vraiment faire fonctionner. S'il s'agit simplement d'un exercice académique pour en savoir plus sur le threading (peut-être comme une étape pour devenir un expert en concurrence de bas niveau), alors ignorez-moi et faites vos recherches sur les détails du modèle de mémoire de la plate-forme que vous visez :)

Answer 3

Vous pouvez éviter les blocages si vous maintenez une hiérarchie stricte des verrous : si vous verrouillez plusieurs nœuds, verrouillez toujours en premier ceux qui sont les plus proches de la tête de la liste. Ainsi, pour supprimer un élément, verrouillez d'abord le prédécesseur du nœud, puis verrouillez le nœud, puis verrouillez le successeur du nœud, déverrouillez le nœud, puis libérez les verrous dans l'ordre inverse.

De cette façon, si plusieurs threads essaient de supprimer des nœuds adjacents simultanément (disons, les nœuds B et C dans la chaîne A-B-C-D), alors le premier thread qui obtient le verrou du nœud B sera celui qui déverrouillera en premier. Le fil d'exécution 1 verrouillera A, puis B, puis C, et le fil d'exécution 2 verrouillera B, puis C, puis D. Il n'y a que de la concurrence pour B, et il n'y a aucun moyen pour le fil d'exécution 1 de conserver un verrou en attendant un verrou détenu par le fil d'exécution 2 et pendant que le fil d'exécution 2 attend le verrou détenu par le fil d'exécution 1 (c'est-à-dire un deadlock).

Answer 4

Vous ne pouvez pas vous passer d'une serrure pour toute la liste. Voici pourquoi :

Insertion dans une liste vide

Les fils A et B veulent insérer un objet.

Le fil A examine la liste et la trouve vide.

Un changement de contexte se produit.

Le fil B examine la liste, la trouve vide et met à jour la tête et la queue pour qu'elles pointent vers son objet.

Un changement de contexte se produit

Le fil A met à jour la tête et la queue pour pointer vers son objet. L'objet de Thread B a été perdu.

Supprimer un élément au milieu de la liste

Le thread A veut supprimer le noeud X. Pour cela, il doit d'abord verrouiller le prédécesseur de X, X lui-même et le successeur de X puisque tous ces noeuds seront affectés par l'opération. Pour verrouiller le prédécesseur de X, vous devez faire quelque chose comme

spin_lock(&(X->prev->lockFlag));

Même si j'ai utilisé la syntaxe d'appel de fonction, si spin_lock est une fonction, vous êtes mort dans l'eau car cela implique au moins trois opérations avant que vous n'ayez réellement le verrou :

• placer l'adresse du drapeau de verrouillage sur la pile (ou dans un registre)
• appeler la fonction
• faire le test atomique et mettre

Il y a deux endroits où le fil A peut être échangé et où un autre fil peut entrer et supprimer le prédécesseur de X sans que le fil A sache que le prédécesseur de X a changé. Il faut donc implémenter le spin lock lui-même de manière atomique, c'est-à-dire qu'il faut ajouter un offset à X pour obtenir x->prev puis le déréférencer pour obtenir *(x->prev) et ajouter un offset à cela pour obtenir lockFlag et ensuite faire une opération atomique, le tout dans une unité atomique. Sinon, il y a toujours la possibilité que quelque chose se glisse après que vous vous soyez engagé à verrouiller un nœud particulier mais avant que vous ne l'ayez effectivement verrouillé.

Answer 5

Je note que la seule raison pour laquelle vous avez besoin d'une liste doublement liée ici est l'obligation de supprimer les nœuds du milieu de la liste, qui ont été obtenus sans parcourir la liste. Un FIFO simple peut évidemment être implémenté avec une liste à lien simple (avec des pointeurs de tête et de queue).

Vous pourriez éviter le cas de la suppression au milieu en introduisant une autre couche d'indirection - si les nœuds de la liste contiennent simplement une balise next et un pointeur payload avec les données réelles pointées ailleurs (vous dites que l'allocation de mémoire n'est pas possible au point d'insertion, donc vous devrez simplement allouer la structure de nœud de liste au même moment que vous allouez la charge utile elle-même).

Dans le cas de la suppression de l'intermédiaire, il suffit de définir l'élément payload pointeur vers NULL et laisser le nœud orphelin dans la liste. Si l'opération de pop FIFO rencontre un tel nœud vide, elle le libère simplement et réessaie. Ce report vous permet d'utiliser une liste à lien unique, et une implémentation de liste à lien unique sans verrou est beaucoup plus facile à réaliser.

Bien sûr, il y a toujours une course essentielle autour de la suppression d'un nœud au milieu de la file d'attente - rien ne semble empêcher ce nœud d'arriver en tête de la file d'attente et d'être supprimé par un autre thread avant que le thread qui a décidé de le supprimer ait réellement la possibilité de le faire. Cette course semble être en dehors de la portée des détails fournis dans votre question.