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)
- können jederzeit verdrängt werden (preemptability), multi-CPU-fähig
- vermeiden PrioritätsInversion, da keine Blockierung stattfindet
Vorteile block-free-Synchronisation
(nach Hohmuth/Härtig)
- keine Deadlocks
- Isolation von gechrashen Threads
- höhere Robustheit und Fehlertoleranz
- nebenläufig (multiprocessing save)
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:
- Zähler
- Bitfelder
- Stacks
- FIFO
- Einfach verkettete Listen (zur größten Not)
Mit CAS2:
- Einfach verkettete Listen
- Doppelt verkette Listen
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
-
- Definition der Begriffe concurrent objekt, lock free, wait free, ...
- Diskussion Primitive CompareAndSwap und andere
- Algorithmen für verkettete Listen, Suchbäume
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