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.
