Left Up Right Ablaufsysteme

Blockierungsfreie und Nicht-sperrende Datenstrukturen

Definitionen

Wait-free Synchronisation
Blokierung wird vermieden, z.B. dadurch, daß ein Thread, der eine Resource hält, mit noch höhererer priorität abagarbeitet wird. Es gibt kein Aushungern. Kritische Sektionen dürfen nicht blockieren. (nach Hohmuth/Härtig)
Block Free Synchronisation
Arbeitet ohne Locks.
Kritische Codesequenzen werden vorbereitet und dann atomar in einen Ergebnispool eingetragen. Im Falle eines Konfiktes muß die Berechnung wiederholt werden.
Dies wird mit atomaren CAS-Instructions (Compare and swap) erreicht. (nach Hohmuth/Härtig)

Vorteile von Blockierungsfreien Koordinierungsstrategien

(nach Hohmuth/Härtig)

Vorteile block-free-Synchronisation

(nach Hohmuth/Härtig) Bei Echtzeitanforderungen besteht die Sorge, daß die Operation unbestimmt oft wiederholt wird.
Man hat aber bei Prioritätsbasierten Systemen Obergrenzen bestimmt.

Einfache Datenstrukturen

Laut [Hohmuth/Härtig] kann man mit CAS folgendes realisieren: Mit CAS2: Mit einem generellen Multiword-Compare-and-Swap (MWCAS) kann man beliebige compexe Datenstrukturen aufbauen. MWCAS kann auf CAS und CAS2 aufgebaut werden. Allerdings sind sie teuere als die herkömmlichen Lock-Basierten Operationen, damit werden sie uninteressant für das Kern Design.

Realisierungsmöglichkeiten

Nach [Shavit95] erfordern interessante Blocking-Free Algorithmen MWCAS (Multi Word Compare And Set), was auf den meisten heutigen Prozesserarchitekturen nicht verfügbar ist.
Folgende Realisierungsmöglichkeiten gibt es:

Literatur und Links

(die weiter ausgewertet werden will)
An introduction to Wait-Free and Lock-Free data structures
Kurzeinführung in das Thema von Eric.Schenk@dna.lth.se
Artikel in PDF
Valois: Lock-Free Linked Lists Using Compare-and-Swap 1995
Erratum
A read lock free linked list data structure
beschreibt eine Liste, in der die Leser nicht sperren müssen.
Wait-free Parallel Algorithms for the Union-Find Problem
hier gibt es mehrere Links auf papers
Implementing Wait Free Objects on Priority Based Systems
Fault-Tolerant Wait-Free Shared Objects
[PDF]Almost Wait-free Resizable Hashtables
]Efficient Almost Wait-free Parallel Accessible Dynamic Hashtables ...
Randomized two-process wait-free test-and-set
Wait-free Object-Sharing Schemes for Real-Time Uniprocessors and ...
A Wait-free Algorithm for Optimistic
RCU - Read Copy Update
ist ein koordinierungsmachenismus, der auch im Linux-Kern verwendet wird

Informatik- und Netzwerkverein Ravensburg e.V Rudolf Weber