Ich dachte, ist es möglich, eine blocklose Warteschlange zu haben, wenn mehr als ein Thread liest oder schreibt? Ich habe eine Implementierung mit einer blocklosen Warteschlange gesehen, die mit einem Lese- und einem Schreib-Thread arbeitete, aber nie mehr als eins für beide. Ist es möglich? Ich glaube nicht. Kann / will es jemand beweisen?
Es gibt mehrere Algorithmen, die ich implementiert habe. Ein optimistischer Ansatz für blockierungsfreie FIFO-Warteschlangen , der das ABA-Problem durch Zeiger-Tagging vermeidet (benötigt die Anweisung CMPXCHG8B auf x86 ) und läuft in einer Produktions-App gut ( in Delphi geschrieben). ( Eine andere Version mit Java-Code )
Um wirklich, wirklich, ohne Sperre zu sein, benötigen Sie auch einen sperrfreien Speicherzuordner - siehe Skalierbare blockierungsfreie dynamische Speicherzuweisung (implementiert in Concurrent Building Block ) oder NBMalloc (aber bisher konnte ich keinen von diese).
Vielleicht möchten Sie auch Antworten auf optimistische blockierungsfreie FIFO-Warteschlangen impl?
Die Implementierung einer Lockless Queue durch Java ermöglicht sowohl Lese- als auch Schreibvorgänge. Diese Arbeit wird mit einer Vergleichs- und Setzoperation ausgeführt (was eine Einzel-CPU-Anweisung ist).
ConcurrentLinkedQueue verwendet eine Methode, bei der sich Threads beim Lesen (oder Abfragen) von Objekten aus der Warteschlange gegenseitig helfen. Da es verbunden ist, kann der Kopf der Warteschlange Schreibvorgänge akzeptieren, während das Ende der Warteschlange Lesevorgänge akzeptieren kann (vorausgesetzt, es ist ausreichend Platz vorhanden). All dies kann parallel durchgeführt werden und ist vollständig Thread-sicher.
Mit .NET 4.0 gibt es die ConcurrentQueue (T) -Klasse .
Laut C # 4.0 ist dies eine lockfreie Implementierung. Siehe auch diese Blogeintrag .
Sie brauchen nicht unbedingt eine Sperre, sondern eine atomare Möglichkeit, Dinge aus der Warteschlange zu löschen. Dies ist auch ohne eine Sperre und mit einer atomaren test-and-set Anweisung möglich.
In der OmniThreadLibrary von Primoz Gabrijelcic (dem Delphi Geek) gibt es eine dynamische Warteschlange ohne Sperren: Ссылка
Tags und Links multithreading queue lockless