Est-ce un verrou (attente) gratuit doublement chaînées liste possible?

Question

Poser cette question avec étiquette C #, mais s'il est possible, il devrait être possible dans toutes les langues.

Est-il possible de mettre en œuvre une liste doublement chaînée en utilisant des opérations Interlocked de fournir sans attendre verrouillage? Je voudrais insérer, ajouter et supprimer, clair et sans attendre.

Answer 1

Une simple recherche google révélera de nombreux articles de la liste doublement chaînées sans blocage.

Cependant, ils sont basés sur CAS atomique (comparer et swap).

Je ne sais pas comment les opérations atomiques en C # sont, mais selon ce site

http://www.albahari.com/threading/part4.aspx

opérations C # sont garanties à être atomique pour la lecture et l'écriture d'un champ de 32 bits. Aucune mention de CAS.

Answer 2

Oui, il est possible, voici ma mise en œuvre d'un STL comme Lock-gratuit Liste-doublement liés en C ++.

exemple de code qui génère des fils pour effectuer de façon aléatoire ops sur un liste

Il faut une comparaison et-swap de 64 bits pour fonctionner sans problèmes de l'ABA. Cette liste est uniquement possible en raison d'un verrouillage sans gestionnaire de mémoire .

Consultez la page noreferrer repères à la page 12 . Performance de la liste varie linéairement avec le nombre de threads que l'augmentation de contention. L'algorithme prend en charge le parallélisme pour des accès disjoints, de sorte que la taille de la liste augmente contention peut diminuer.

Answer 3

Voici une papier qui discribes une serrure sans liste liée doublly.

  

Nous présentons un moyen efficace et pratique   verrouillage sans mise en œuvre d'un   deque concurrente qui est   disjoint parallèle accessible et utilisations   primitives atomiques qui sont disponibles   dans les systèmes informatiques modernes. Précédemment   connus algorithmes de Deques sans verrouillage   qui sont basés soit sur la non-disponible   primitives de synchronisation atomique,   ne mettre en œuvre un sous-ensemble de la   fonctionnalité, ou ne sont pas conçus pour   disjoint accède. Notre algorithme est   sur la base d'une liste doublement chaînée, et   ne nécessite un seul mot   comparer et-swap ...

Ross Bencina a des liens très bien que je viens de trouver avec des papiers numerious et le code source pour Citons comme exemples "

Je ne crois pas que ce soit possible, puisque vous devoir définir plusieurs références en un seul coup, et les opérations emboîtés sont limitées dans leur puissance.

Par exemple, prenez l'opération d'ajout - si vous noeud B insérer entre A et C, vous devez définir B> suivante, B> prev, A> suivante et C> prev dans un atomique opération. Interverrouillage ne peut pas gérer. Prérégler les éléments de B ne permet même pas, parce qu'un autre thread pourrait décider de faire un insert pendant que vous vous préparez « B ».

Je me concentrerais davantage sur l'obtention du verrouillage à grains fins que possible dans ce cas, ne pas essayer de l'éliminer.

Lire la note - ils ont l'intention de tirer ConcurrentLinkedList de 4,0 avant la version finale de VS2010

Eh bien, vous ne l'avez pas fait demandé comment le faire. Mais, à condition que vous pouvez faire une CAS atomique dans c # il est tout à fait possible.

En fait, je travaille juste à travers une mise en œuvre d'une liste d'attente gratuit doublement lié en C ++ en ce moment.

Voici papier décrire. http://www.cse.chalmers.se/~tsigas/papers /Haakan-Thesis.pdf

Et une présentation qui peut également vous fournir quelques indices. http://www.ida.liu.se/ ~ chrke / cours / MULTI / diapositives / Lock-Free_DoublyLinkedList.pdf

Il est possible d'écrire des algorithmes gratuits pour verrouiller tous structures de données copiables sur la plupart des architectures [1]. Mais il est difficile d'écrire les efficaces.

J'ai écrit un du sans verrouillage liste doublement chaînée par Håkan Sundell et Philippas Tsigas pour .Net. Notez qu'il ne supporte pas PopLeft atomique en raison du concept.

[1]: Maurice Herlihy: résultats et universalité Impossibility pour attentisme freesynchronization (1988)

FWIW, .NET 4.0 ajoute une ConcurrentLinkedList, une liste threadsafe liée doublement dans l'espace de noms System.Collections.Concurrent. Vous pouvez lire le ou blog décrire.

Je dirais que la réponse est très profondément qualifié « oui, il est possible , mais difficile ». Pour mettre en œuvre ce que vous demandez, vous auriez essentiellement besoin de quelque chose qui compilerait les opérations ensemble pour assurer qu'aucune collision; en tant que tel, il serait très difficile de créer une mise en œuvre générale à cet effet, et il aurait encore des limites importantes. Il serait probablement plus simple de créer une implémentation spécifique adaptée aux besoins précis, et même alors, il ne serait pas « simple » par tout moyen.

Answer 4

Answer 5

Answer 6

Je ne crois pas que ce soit possible, puisque vous devoir définir plusieurs références en un seul coup, et les opérations emboîtés sont limitées dans leur puissance.

Par exemple, prenez l'opération d'ajout - si vous noeud B insérer entre A et C, vous devez définir B> suivante, B> prev, A> suivante et C> prev dans un atomique opération. Interverrouillage ne peut pas gérer. Prérégler les éléments de B ne permet même pas, parce qu'un autre thread pourrait décider de faire un insert pendant que vous vous préparez « B ».

Je me concentrerais davantage sur l'obtention du verrouillage à grains fins que possible dans ce cas, ne pas essayer de l'éliminer.

Answer 7

Lire la note - ils ont l'intention de tirer ConcurrentLinkedList de 4,0 avant la version finale de VS2010

Answer 8

Lire la note - ils ont l'intention de tirer ConcurrentLinkedList de 4,0 avant la version finale de VS2010

Answer 9

Eh bien, vous ne l'avez pas fait demandé comment le faire. Mais, à condition que vous pouvez faire une CAS atomique dans c # il est tout à fait possible.

En fait, je travaille juste à travers une mise en œuvre d'une liste d'attente gratuit doublement lié en C ++ en ce moment.

Voici papier décrire. http://www.cse.chalmers.se/~tsigas/papers /Haakan-Thesis.pdf

Et une présentation qui peut également vous fournir quelques indices. http://www.ida.liu.se/ ~ chrke / cours / MULTI / diapositives / Lock-Free_DoublyLinkedList.pdf

Answer 10

Answer 11

Eh bien, vous ne l'avez pas fait demandé comment le faire. Mais, à condition que vous pouvez faire une CAS atomique dans c # il est tout à fait possible.

En fait, je travaille juste à travers une mise en œuvre d'une liste d'attente gratuit doublement lié en C ++ en ce moment.

Answer 12

Voici papier décrire.

Answer 13

Il est possible d'écrire des algorithmes gratuits pour verrouiller tous structures de données copiables sur la plupart des architectures [1]. Mais il est difficile d'écrire les efficaces.

J'ai écrit un du sans verrouillage liste doublement chaînée par Håkan Sundell et Philippas Tsigas pour .Net. Notez qu'il ne supporte pas PopLeft atomique en raison du concept.

[1]: Maurice Herlihy: résultats et universalité Impossibility pour attentisme freesynchronization (1988)

Answer 14

FWIW, .NET 4.0 ajoute une ConcurrentLinkedList, une liste threadsafe liée doublement dans l'espace de noms System.Collections.Concurrent. Vous pouvez lire le ou blog décrire.

Answer 15

Je dirais que la réponse est très profondément qualifié « oui, il est possible , mais difficile ». Pour mettre en œuvre ce que vous demandez, vous auriez essentiellement besoin de quelque chose qui compilerait les opérations ensemble pour assurer qu'aucune collision; en tant que tel, il serait très difficile de créer une mise en œuvre générale à cet effet, et il aurait encore des limites importantes. Il serait probablement plus simple de créer une implémentation spécifique adaptée aux besoins précis, et même alors, il ne serait pas « simple » par tout moyen.