Structures de données d'arborescence concurrentes sans mise à jour et à temps constant?

20

J'ai lu un peu de littérature récemment et j'ai trouvé des structures de données plutôt intéressantes.

J'ai recherché différentes méthodes pour réduire le temps de mise à jour au temps de mise à jour du pire cas [1-7].O(1)

Récemment, j'ai commencé à chercher des structures de données sans verrouillage, pour prendre en charge un accès simultané efficace.

L'une de ces techniques de mise à jour dans le pire des cas a -t-elle été utilisée dans la mise en œuvre de structures de données sans verrouillage?O(1)

Je demande parce que; elles me semblent être l'extension pratique évidente de cette "amélioration théorique".

  1. Tarjan, Robert Endre. «Mise à jour d'un arbre de recherche équilibré dans les rotations O (1)». Information Processing Letters 16, no. 5 (1983): 253 - 257.

  2. Driscoll, JR, N Sarnak, DD Sleator et RE Tarjan. «Rendre les structures de données persistantes». Dans les actes du dix-huitième symposium annuel de l'ACM sur la théorie de l'informatique, 109-121. STOC '86. New York, NY, USA: ACM, 1986.

  3. Levcopoulos, C. et Mark H. Overmars. «Un arbre de recherche équilibré avec O (1) pire temps de mise à jour.» Acta Inf. 26, non. 3 (novembre 1988): 269-277.

  4. Fleischer, Rudolf. Un arbre de recherche équilibré simple avec O (1) temps de mise à jour le plus défavorable

  5. Dietz, Paul F et Rajeev Raman. «Un arbre de recherche de doigt à temps de mise à jour constant». Lettres de traitement de l'information 52, no. 3 (1994): 147 - 154.

  6. Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas et Kostas Tsichlas. «Nouveaux arbres de recherche équilibrés dynamiques avec temps de mise à jour constant dans le pire des cas.» J. Autom. Lang. Peigne. 8, non. 4 (juillet 2003): 607–632.

  7. Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis et Kostas Tsichlas. "Arbres de recherche de doigts optimaux dans la machine à pointeurs." J. Comput. Syst. Sci. 67, non. 2 (septembre 2003): 381–418.

reference-request data-structures time-complexity concurrency search-trees À
la source
2
Veuillez envisager d'ajouter des liens vers les articles par courtoisie aux personnes qui souhaitent enquêter sur votre problème.
Raphael
3
D'accord, ajouté dans les liens vers les articles respectifs.
AU
1
Je suggère de republier sur cstheory.SE (avec un lien ici) si vous n'obtenez pas rapidement une réponse utile.
JeffE
1
Merci pour la suggestion. J'ai republié: des structures de données d'arborescence concurrentes sans verrouillage et à temps de mise à jour constant?
AU
J'ai utilisé la bibliothèque de structures de données sans verrouillage pratique auparavant. Ils prennent en charge les structures de données d'arbre sans verrouillage. Peut-être avez-vous ce que vous cherchez.
Reza

Réponses:

4

O(1)

Cela signifie que si vous modifiez la structure de données, la caractéristique importante est que vous pouvez effectuer tous les mods sur une structure de données privée, puis échanger les modifications dans une seule instruction atomique.

La liberté de verrouillage est généralement plus facile lorsque vos structures de données sont immuables ( purement fonctionnelles ). Vous gardez simplement un pointeur global vers la version actuelle de la structure de données. Les lecteurs n'ont pas besoin de verrouiller quoi que ce soit. Les modifications de la structure des données sont effectuées en échangeant le pointeur global sur une structure de données immuable à une autre.

Par exemple: si vous avez un arbre équilibré purement fonctionnel, vous:

  1. Enregistrez le pointeur global actuel sur la racine de l'arborescence.
  2. Créez une nouvelle arborescence qui insère ou supprime un nœud. (Ceci est logarithmique en temps et en espace dans le nombre de nœuds actuellement dans l'arborescence, et implique de créer de nouveaux nœuds du point de modification jusqu'à la racine, et de simplement pointer tout ce qui est nouveau vers les anciennes parties de la version précédente de la structure de données. )
  3. Comparez et échangez atomiquement le pointeur global à la racine. (Notez que cela peut échouer si une autre modification s'est produite entre le moment où vous avez enregistré l'ancien pointeur racine et maintenant. Si cela se produit, vous revenez à l'étape 1 et réessayez. Il s'agit du "contrôle de concurrence optimiste".)

Notez que la partie la plus importante est ce que j'ai dit ci-dessus à propos de la nécessité de maintenir des invariants de représentation. Il n'est généralement pas suffisant d'avoir un algorithme qui effectue atomiquement un changement au milieu de l'arbre. Pourquoi? Par exemple: vous pourriez avoir un thread de lecture qui est en train d'effectuer une traversée en précommande de l'arborescence. Si vous modifiez un nœud qui est un ancêtre du nœud qu'ils lisent actuellement, vous allez invalider les conditions préalables qu'ils pensaient avoir appliquées. Le lecteur doit être en mesure de travailler avec la structure de données exactement comme elle était avant d'effectuer votre modification, ou exactement comme elle le sera après avoir effectué votre modification. Pas quelque chose entre les deux.

O(log(N))O(N)

Logique errante
la source
Je pense que les techniques d'attente active, par exemple avec comparaison et échange, sont généralement appelées «sans verrouillage», donc il existe des moyens de sortir, même dans le cadre mutable.
Raphael
Je ne connais pas le terme d' attente active (et Google n'aide pas). (Si vous parlez du travail de Kogan et Petrank, cela montre comment transformer des algorithmes sans verrouillage en attente.) J'ai ajouté une modification sur la façon dont vous pouvez gérer la mutabilité de la liberté de verrouillage en général.
Wandering Logic
Par "attente active", je veux dire quelque chose comme while ( !P ) { noOp(); } doWork();où noOppeut être un sleepou similaire.
Raphael
Dans la partie Modifier , vous avez mentionné la technique pour rendre les structures de données mutables sans verrouillage. Comme indiqué, nous copions l'intégralité de la structure de données, faisons des mods sur la copie, puis utilisons la primitive CAS. Cependant, comment rendre l' Copyétape atomique? Cela semble être un autre problème difficile de atomic snapshot.
hengxin
@hengxin: considérez la primitive CAS comme un opérateur de "publication". Avant que la structure de données ne soit publiée, seul le thread effectuant les modifications y a accès. Une fois la structure des données publiée, elle est immuable. L'étape de copie n'a pas besoin d'être atomique car la seule chose qu'un thread pourrait copier est une version publiée, qui est immuable. Si deux threads tentent simultanément de muter, ils copient tous les deux la même structure de données immuable, modifient leurs copies locales, puis l'une des opérations CAS réussit et l'autre échoue. Celui qui échoue doit être recopié et mis à jour.
Wandering Logic du