Je pensais, est-il possible d'avoir une file d'attente sans verrouillage sans verrouillage lorsque
6 Réponses :
Vous n'avez pas spécifiquement besoin d'une serrure, mais d'une manière atomique de supprimer les choses de la file d'attente. Ceci est également possible sans verrou et avec un atomique Test-and-Set instruction.
Est-ce une seule instruction CPU?
avec .NET 4.0, il y a Concurrentquue (T) Classe .
Selon C # 4.0 en un mot, il s'agit d'une mise en œuvre gratuite de verrouillage. Voir aussi ceci Entrée de blog .
Il existe plusieurs algorithmes disponibles, j'ai fini par mettre en œuvre le une approche optimiste des files d'attente FIFO sans verrouillage , qui évite le problème ABA via le marquage du pointeur (nécessite le Néanmoins, pour être vraiment sans verrouillage, vous auriez également besoin d'un allocator mémoire sans verrou - voir Allocation de mémoire dynamique sans verrouillage évolutive (implémentées dans Bloc de construction simultané ) ou NBMALLALC (mais jusqu'à présent, je n'ai pas eu d'utiliser l'un d'entre eux).
Vous voudrez peut-être aussi regarder des réponses pour files d'attente FIFO gratuite optimistes. CMPXCHG8B Instruction sur x86 ), et il fonctionne bien dans une application de production (écrit dans Delphi). ( Une autre version, avec code Java )
Je n'ai pas compris CAS avant d'avoir lu l'instruction CMPXCHG. L'instruction CMPXCHG a l'air cool, alors je le prends si c'est un succès, il définira le drapeau Z? Maintenant, après des minutes de confusion avec CAS jusqu'à lire CMPXCHG CAS ressemble à CAS (DST, OldValue, Newval); Où DST est la destination d'adresse et les deux autres sont des valeurs? retourner true si dst était une valeur ancienne et a été remplacé par NewValue? (Je sais que j'ai dit beaucoup, mais je pense que j'ai eu ce droit, cela semble très juste).
Savez-vous s'il existe des implémentations existantes C ++ 11 de votre papier? On dirait que cela nécessite des soins à mettre en œuvre et, bien que je puisse vraiment utiliser cela, je vais aller pour une implémentation de verrouillage plus facile à comprendre et à analyser.
Désolé, le papier commence à devenir assez vieilli et je ne cherchais aucune implémentation actuelle, car il est possible de mettre en œuvre et de déboguer l'algorithme basé sur le pseudo-code.
@ ACIDEZOMBIE24: Je trouve curieux que le CAS soit "comparer et échanger" lorsque son comportement réel semble être "comparer et stocker [conditionnel]". CAS représente l'intersection de deux paradigmes: lié à la charge / stockage-conditionnel et compare-échange. Un système qui implémente le conditionnel lié à la charge / stockage contient une instruction spéciale "lecture" qui définit un drapeau et entraîne la surveillance de l'adresse de destination. Si quelque chose arrive que pourrait perturber perturber cette adresse, le drapeau sera effacé. Store conditionné effectue un magasin si le drapeau est toujours défini et définit un registre pour indiquer ...
Après boost 1.53, une bibliothèque est nommée LockFree. IT FOURNITURE BOOST :: LOCKFREE :: Queue Sorcière Descriptif "Une file d'attente multi-consommation / multi-consommation sans verrouillage", profitez-en.
Il y a une file d'attente gratuite de verrouillage dynamique dans l'omnithreadlibrary de Primoz Gabrijelcic (The Delphi Geek): http://www.thedelphigeek.com/2010/02/Mnithreadlibrary-105.html
La mise en œuvre de Java d'une file d'attente sans verrouillage permet de lire et écrivez. Ce travail est effectué avec une opération de comparaison et de définition (qui est une seule instruction CPU).
Le ConcurrentLinkedQueue utilise une méthode dans laquelle les threads s'aident à lire (ou à sonder) des objets de la file d'attente. Comme il est lié, la tête de la file d'attente peut accepter écris pendant que la queue de la file d'attente peut accepter des lectures (en supposant suffisamment de place). Tout cela peut être fait en parallèle et est complètement sûr.