(Plus) verrouillage efficace lors de la rotation des noeuds dans l'arbre binaire fileté

Question

Alors, je suis venu avec ce système pour les noeuds de blocage lors de la rotation dans un arbre binaire que plusieurs threads ont à la fois en lecture et écriture au même temps, ce qui implique le verrouillage de quatre nœuds par rotation, ce qui semble être terriblement? Je pensais que d'une façon plus intelligente, alors j'avais trouvé un moyen de réduire le verrouillage nécessaire, mais Google ne s'est pas montré beaucoup (j'utilise probablement la mauvaise terminologie de toute façon). Ceci est mon schéma actuel, les nœuds orange et rouge sont soit déplacés ou modifiés par la rotation et doivent être verrouillés et les nœuds verts sont adjacents à tout nœud qui est affecté par la rotation, mais ne sont pas affectés par eux-mêmes.

binary tree rotation

je me suis dit qu'il doit y avoir une meilleure façon de faire, une idée que j'ai est de prendre un instantané des quatre nœuds concernés, les faire pivoter dans l'instantané, puis remplacer les noeuds de courant avec le les instantanés (en supposant que rien n'a changé pendant que je faisais les rotations) - cela me permettrait d'être presque libre mais je fermerai crains que la surcharge de la mémoire pourrait être de beaucoup, étant donné que la rotation est une opération assez rapide (re- assigner trois pointeurs)?

Je suppose que je suis à la recherche pour les pointeurs (sans jeu de mots) sur la façon de le faire efficacement.

Answer 1

Jetez un coup d'œil aux arbres binaires immuables. Vous devez changer un peu plus de nœuds (chaque nœud à la racine), mais cela ne change pas la complexité d'un insert qui est log n dans les deux sens. En effet, cela peut même améliorer les performances car vous n'avez besoin d'aucun code de synchronisation.

Par exemple, Eric Lippert a écrit quelques articles sur AVL immuables en C#. Le dernier était: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

Answer 2

Il y aurait habituellement un verrou pour la structure entière de données, étant donné qu'un verrou lui-même prend habituellement de sérieuses ressources. Je devine étant donné que vous essayez d'éviter cela, ce doit être un scénario très spécialisé où vous avez beaucoup de threads de travail intensifs CPU mettant constamment à jour l'arbre?

Vous pouvez obtenir un équilibre en faisant en sorte que chaque nœud N partage un verrou. Lorsque vous entrez une opération de rotation, recherchez l'ensemble des verrous uniques utilisés par les nœuds concernés. La plupart du temps, ce ne sera qu'une seule serrure.

Answer 3

La meilleure solution dépend de votre application. Mais si vous avez comme une base de données en mémoire et que vous voulez faire des mises à jour simultanées ET que vous voulez avoir un verrouillage très fin, vous pouvez aussi regarder les arbres B qui ne nécessitent pas la rotation des nœuds aussi souvent que les arbres binaires . Ils sont également automatiquement équilibrés, contrairement aux arbres binaires, qui nécessitent plus de rotations pour maintenir l'équilibrage (par exemple, les arbres Splay ou AVL).

Si vous voulez avoir des modifications transactionnelles aux arbres, au lieu, vous pouvez utiliser B arbres fonctionnels (qui Thomas Danecker appelle des arbres immuables). Ce sont des arbres binaires de type «copy-on-write», et la seule chose que vous devez verrouiller est le nœud racine. Vous n'avez donc besoin que d'un seul verrou. Et les opérations ont en pratique la même complexité que pour les arbres binaires, car toutes les opérations sur les arbres binaires fonctionnels sont O (log n) et vous passez le même temps logarithmique chaque fois que vous descendez dans un arbre.

Avoir un verrou par noeud n'est probablement pas la bonne solution.

Answer 4

John Valois paper décrit brièvement une approche de mise en œuvre d'un arbre de recherche binaire en utilisant des noeuds AUXILIAIRES. J'utilise l'approche de nœud auxiliaire dans mon design d'un LinkedHashMap concurrent.Vous pouvez probablement trouver beaucoup d'autres articles sur les arbres concurrents sur CiteSeerX (une ressource inestimable). Je m'éloignerais de l'utilisation des arbres comme une collecte de données simultanée à moins que ce ne soit vraiment nécessaire, car ils ont tendance à avoir de mauvaises caractéristiques de concurrence en raison du rééquilibrage. Souvent, les approches plus pragmatiques, comme les listes de sauts, fonctionnent mieux.

Answer 5

Je jouais à faire des arbres binaires lisible sans verrouillage en utilisant une copie partielle à l'écriture. J'ai posté une implémentation incomplète ici http://groups.google.com/group/comp.programming.threads/msg/6c0775e9882516a2?hl=en&

Answer 6

Les algorithmes sans verrouillage, autant que je peux voir, manquent de comptes de référence, ce qui rend leur utilisation générale problématique; vous ne pouvez pas savoir si le pointeur que vous avez sur un élément est valide - cet élément a peut-être disparu.

Valois 'contourne cela avec un arrangement d'allocation de mémoire exotique qui n'est pas utile en pratique. La seule façon que je peux voir pour faire des arbres équilibrés sans verrouillage est d'utiliser un MCAS modifié, où vous pouvez également faire incrémenter/décrémenter, ainsi vous pouvez maintenir un nombre de référence. Je n'ai pas cherché à voir si MCAS peut être modifié de cette manière.