liste liée simultanée

J’essaie de concevoir une liste chaînée en c ++ permettant un access simultané. Il est clair que l’utilisation d’un verrou unique pour cette liste est extrêmement inefficace, car les zones disjointes peuvent être mises à jour en parallèle. Maintenant, quelles sont mes options autres que le stockage d’un verrou par nœud?

En outre, une version non bloquante serait-elle un meilleur choix dans ce cas? Des liens pertinents, quelqu’un?

EDIT : Merci pour les réponses des gens. Quelques choses que j’aimerais append:

  1. Que diriez-vous de stocker N verrous pour chaque M nœuds au lieu du ratio 1: 1 verrou: nœud? Certaines discussions pourraient attendre, mais c’est un peu un compromis. Qu’est-ce que tu penses?
  2. Si j’ai l’intention de trouver un nœud dans cette liste liée, tous les mutex doivent être verrouillés. C’est un problème, car le locking et le délocking de tous les mutex prennent beaucoup de temps. Est-ce que quelqu’un a une meilleure alternative?
  3. Je suis ouvert aux algorithmes non bloquants. Mais comment utiliser CAS dans le bon vieux C ++ sans utiliser l’assembly? J’ai entendu dire que gcc possède des atsortingbuts __sync qui effectuent un travail similaire mais pas sûr.
  4. Avec une approche non bloquante, comment effectuez-vous une recherche dans la liste liée?

Il est possible d’implémenter une liste à liens simples non bloquante à l’aide de fonctions inter-verrouillées:

Listes simples liées entre elles

Je ne pense pas qu’il soit possible d’implémenter une liste doublement chaînée non bloquante sans un système CAS (CAS) comparé et interchangeable, qui n’est pas largement disponible.

Les listes chaînées sont des structures de données séquentielles par nature. Quel que soit le type de machine que vous utilisez pour l’implémenter, l’interface et le comportement attendu impliquent une logique séquentielle.

Qu’essayez-vous de faire? Cela devrait déterminer la structure de données que vous utilisez et non la familiarité des structures de données avec lesquelles vous êtes déjà à l’aise.

Vous pouvez vous y prendre de différentes manières, en fonction de votre utilisation de la liste.

Premièrement, pour une liste, un verrou mutex unique n’est pas forcément un gros problème car les listes peuvent prendre en charge l’épissage. Supposons que vous avez une liste de caractères AF et une autre liste BCDE. Vous n’avez pas besoin de verrouiller le mutex, insérer B, le verrouiller à nouveau, insérer C, etc. Vous pouvez insérer BCDE en même temps entre A et F en définissant le prochain pointeur de A sur B et le prochain pointeur de E sur F, formant ABCDEF. Peu importe le nombre d’éléments que vous souhaitez insérer à la fois, vous n’avez besoin que d’un seul verrou. Cela est vrai même pour une liste doublement chaînée. Cela pourrait donc ne pas être un goulot d’étranglement dans votre application.

En supposant que ce soit un goulot d’étranglement, vous devez déterminer si vous allez avoir un ou plusieurs rédacteurs et un ou plusieurs lecteurs.

En supposant que vous ayez un seul rédacteur et plusieurs lecteurs, vous pouvez entièrement éviter les verrous mutex en utilisant des instructions atomiques, à condition qu’elles soient disponibles pour votre architecture. Celles-ci sont disponibles dans GCC via les fonctions intégrées __sync_ * et dans Visual C ++ via Interlocked *. Toutefois, si vous êtes bloqué avec un compilateur ne prenant pas en charge directement ces fonctionnalités, vous pouvez toujours les utiliser via un assemblage en ligne. Le rédacteur utilisera les instructions atomiques pour définir de manière atomique les prochains pointeurs afin de patcher les éléments entrant et sortant de la liste.

J’espère que cela vous permet de commencer. Pour obtenir une réponse profonde, je suggérerais de poser une autre question et notamment:

  1. Y a-t-il un / plusieurs lecteurs?
  2. Y a-t-il un / plusieurs écrivains?
  3. Liste simple ou double liste?
  4. Une certaine idée de votre cas d’utilisation.

Êtes-vous sûr que c’est un problème qui mérite d’être résolu? Serait-il peut-être plus utile d’encapsuler l’utilisation finale réelle dans une classe qui gère le locking d’une list normale et fournit une interface thread-safe? De cette façon, vous n’essayez pas de placer le locking à un niveau trop bas (ce qui, comme vous l’avez supposé, n’est pas un problème facile à résoudre).

Qu’en est-il des Skip Lists? Jetez un coup d’œil à l’implémentation de Java dans le paquet “concurrent”.