Behinderungsfrei/Sperrfrei/Wartefrei nochmal erklären

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Behinderungsfrei/Sperrfrei/Wartefrei nochmal erklären
Hallo,

könnte jemand oben genannte Begriffe nochmal in eigenen Worten erklären?

Mein “Verständnis”:
behinderungsfrei: Allein kommt der Prozess voran, aber er könnte auch, weil er doof programmiert wurde, gar nicht vorankommen wenn bestimmte andere Prozesse ihn behindern, ihm alle Ressourcen wegnehmen?

sperrfrei: behinderungsfrei + Jeder Schritt leistet etwas (Auch wenn Prozess schläft?), Programm (aus mehreren Prozessen) ist irgendwann mal fertig, allerdings können einige Prozesse vom Scheduler stark benachteiligt werden (hungern)

wartefrei: behinderungsfrei + sperrfrei + frei von Aushungerung?

Das fühlt sich nicht so ganz richtig an :-/
Kann mir jemand helfen?


Von der stärksten zur schwächsten Eigenschaft der nichtblockierenden Synchronisation (es gilt ja, laut Foliensatz obstruction-free ⊂ lock-free ⊂ wait-free


Wartefrei (engl. wait-free): Soll es in der Praxis seltener geben, da es aufwendiger (aber oft möglich) ist solche Algorithmen umzusetzen. Für echt-zeit Systeme ist es aber interessant, oder in hoch-parallelen Situationen wie ray-tracing. Die geläufige Definition die man immer sieht ist if each operation is guaranteed to complete within a finite number of steps (siehe). Was wichtig ist zu verstehen, ist das a finite number of steps bedeuten soll, dass es unabhängig ist von dessen Umgebung (ie. anderen neben-läufigen Prozessen). Es ist egal was andere Prozesse machen, dieser kommt vorran, ie. kein Aushungern.

Man wir in einem wartefreiem Algorithmus, keine Operationen wie [m]compare_and_swap[/m] benutzen, da diese (meist) in Schleifen benutzt werden, wie bei [i]jbuffer[/i]. Stattdessen weicht man aus auf (zumindest laut [url=http://www.1024cores.net/home/lock-free-algorithms/introduction]dieser Seite[/url]) Sachen wie "atomic_exchange" oder "atomic_fetch_add", die ja "atomar" eine Sache abfertigen.

Vielleicht ist es interessant festzustellen, dass [i]wait-free[/i] nicht immer schneller heißen muss: 

Sperrfrei (engl. lock-free): Soll zunächst bedeuten das wir keine „Locks“ (wie im englischem Namen klar wird) benutzt werden. Du meintest „Jeder Schritt leistet etwas (Auch wenn Prozess schläft?)“, und das Stimmt nur hinsichtlich dem Gesammtzustand des Prozesses. hier (2.1.1.) wird gesagt:

d.h. die Frage mit dem „Schlafen“ hat sich erübrigt: wenn es schläft, kommt ja nichts voran, es wurde ja vom Scheduler zurückgesetzt. Diese bedeutet auch das Prioritätsinversion (wichtigeres wird vom weniger wichtigerem Verdränkt, da bspw. eine einen dazu zwingt seine Zeitscheibe abzugeben).

Laut dieser Seite werden hierfür (scheinbar) immer Operationen wie [m]CAS[/m] oder [m]LL/SC[/m] benutzt. Das ist ein entscheidender Unterschied zu Wartefreien Algorithmen, wo ja das [m]CAS[/m]-Schleifen contra der benötigten Eigenschaft ist.

Sperrfreiheit soll die populärste nicht-blockierende Methode sein, und nimmt allgemein den, wie in der Vorlesung erwähnten Optimistischen Ansatz (dh. wir gehen davon aus dass es zu einen Synchro. Fehlern kommt, aber wenn ja kommen wir damit klar).


Zuletzt, Behinderungsfrei (engl. obstruction-free): Um gleich mit einem Zitat anzufangen :

wir sorgen also selbst dafür das nicht blockiert wird, anstatt dieses aus den Eigenschaften der Operationen „abzuleiten“ (wie bisher). Scheinbar können aber oft Sperrfreie Algorithmen auf Behinderungsfreien Algorithmen hergeleitet werden, wenn man noch zusätzliche „Hillfen“ einbaut (nur nebenbei).

Hier noch was wichtiges (s. 19):

was (mich zumindest) an die Eigenschaft von oben mit Wartefreiheit erinnert. Wenn aber zwei Prozesse aufeinander Treffen, und beide (lediglich) Behinderungsfrei sind, kann (und tut es (s. 1)) es zu einem live-lock kommen. Das hängt auch zunächst nicht davon ab ob es „doof programmiert wurde“ wurde oder nicht. Kurz wird fertig, wenn nicht gestört. Wenn man das vergleicht mit dem davor, ist klar zu erkennen wieso dieses die schwächste Eigenschaft ist.

Wir sehen auch: Alle, also Behinderungs-, Sperr- und Wartefrei werden irgendwann halten (ie. haben die Terminierungseigenschaft).


Hoffe das macht Sinn, ich habe jedenfalls etwas dazugelernt beim schreiben ^^

1 „Gefällt mir“

Vielen Dank!!! :slight_smile:


Danke zge, dein Beitrag war hilfreich, auch nach 2 Jahren!
Ansonsten kann ich auch noch den Eintrag „Fortschrittsgarantie“ in woschs Glossar empfehlen: https://www4.cs.fau.de/DE/~wosch/glossar.pdf

Zwei Fragen:

  • Habt ihr ein einfaches Beispiel für einen nebenläufigen behinderungsfreien (aber nicht sperrfreien) Algorithmus?
    (Für sperrfrei nehme irgendeinen transaktionalen nichtblockierenden Algorithmus, etwa push und pop aus der Vorlesung „Nebenläufige Systeme“ von wosch. Für wartefrei nehme fetch-and-add realisiert via atomaren Instruktionen der Befehlssatzebene.)

  • Warum heißt sperrfrei sperrfrei? siehe unten. Folgender Algorithmus nutzt Sperren, sollte aber trotzdem eine sperrfreie Fortschrittsgarantie haben falsch, siehe unten:

pthread_mutex_t m;
volatile int i = 0;

void algorithm(void) {
  pthread_mutex_lock(&m);
  i++;
  pthread_mutex_unlock(&m);
}

Laut woschs Glossar (oben verlinkt) bedeutet sperrfrei, dass irgendein Prozess (in einem System von Prozessen in einer Konkurrenzsituation) eine bestimmte Operation in einer endlichen Anzahl von Schritten vollenden kann, ohne Rücksicht auf die relativen Geschwindigkeiten der anderen Prozesse.
Der Prozess, der als erstes [m]pthread_mutex_lock[/m] aufruft, kann doch in einer endlichen Anzahl von Schritten vollenden. Denn derjenige Prozess muss nur [m]i++[/m] und [m]pthread_mutex_unlock[/m] vollenden und das ist in endlicher Zeit möglich, ohne Rücksicht auf andere Prozesse.

EDIT: Ich denke, entweder lese ich zu wenig aus woschs Glossareintrag heraus oder er ist tatsächlich unzureichend.

Denn Wikipedia sagt zu lock-freedom:

[quote=Wikipedia]Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes progress (for some sensible definition of progress). […]

In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)[/quote]

Und An Introduction to Lock-Free Programming sagt:

[quote=preshing]In this sense, the lock in lock-free does not refer directly to mutexes, but rather to the possibility of “locking up” the entire application in some way, whether it’s deadlock, livelock – or even due to hypothetical thread scheduling decisions made by your worst enemy.

[…]

One important consequence of lock-free programming is that if you suspend a single thread, it will never prevent other threads from making progress, as a group, through their own lock-free operations.[/quote]

Der Technical Report „Practical lock-freedom“ von Keir Fraser (Technical Report Number 579, ISSN 1476-2986, University of Cambridge, UCAM-CL-TR-579), der von zge auch oben schon zitiert wurde, bringt es auf den Punkt:

Ich hatte woschs Glossareintrag so verstanden, dass die endlichen Schritte für einen Prozess gelten sollen. Anscheinend stimmt das nicht.

BEISPIEL

Betrachte folgende Stackimplementierung aus woschs VL „Nebenläufige Systeme“:

[code=c]typedef struct chain_t {
chain_t *link;
} chain_t;

void push(chain_t *this, chain_t *item) {
do {
item->link = this->link;
} while(!CAS(&this->link, item->link, item));
}[/code]
(Beachte, dass wir hier des Beispiels wegen von pop absehen und damit auch kein ABA-Problem haben.)

Behauptung: push hat eine sperrfreie Fortschrittsgarantie (i. S. v. Fraser K., Practical lock-freedom).

Beweis: Sei irgendein System von Prozessen gegeben, die alle push ausführen. Sei n die Anzahl an Befehlssatzinstruktionen innerhalb der Schleife. Die Befehlssatzebene garantiert eine Totalordnung aller CASes. Nach Programmvorschrift vollendet derjenige Prozess definitiv, der das erste CAS überhaupt ausführt. Und nach pn systemweiten Schritten gibt es mindestens einen CAS-Aufruf. (Denn bei pn systemweiten Schritten, muss es mindestens einen Prozess mit >= n Schritten gegeben haben [sonst hätten alle Prozesse < n Schritte und wir hätten ingesamt < pn systemweite Schritte].) D.h. nach pn systemweiten Schritten hat mindestens ein Prozess vollendet.


Zusammenfassung (so wie ich das aktuell verstehe, nehme gerne Korrekturwünsche an)

  • behinderungsfrei
    ** jeder in Isolation stattfindende Prozess kann die Operation in einer endlichen Anzahl von systemweiten=prozessweiten Schritten vollenden
    ** garantiert prozessweiten Fortschritt durch prozessweite und isolierte Schrittausführung

  • sperrfrei

** nach einer endlichen Anzahl von systemweiten Schritten hat mindestens ein Prozess die Operation vollendet, ohne Rücksicht auf die relativen Geschwindigkeiten der anderen Prozesse.
** garantiert systemweiten Fortschritt durch systemweite Schrittausführung
** impliziert behinderungsfrei, wenn systemweit nur Schritte in einem ausgewählten Prozess ausgeführt werden

  • wartefrei
    ** jeder Prozess kann die Operation in einer endlichen Anzahl von prozessweiten Schritten vollenden, ohne Rücksicht auf die relativen Geschwindigkeiten der anderen
    ** garantiert prozessweiten Fortschritt durch prozessweite Schrittausführung
    ** impliziert sperrfrei, denn jede prozessweite Schrittausführung ist auch eine systemweite Schrittausführung

Verbesserte Zusammenfassung

Ich habe die Garantie von Behinderungsfreiheit noch ähnlicher zu den anderen Garantien formuliert.

  • behinderungsfrei: garantiert prozessweiten Fortschritt durch systemweite Schrittausführung beschränkt auf einen Prozess
    ** jeder in Isolation stattfindende Prozess kann die Operation in einer endlichen Anzahl von systemweiten=prozessweiten Schritten vollenden

  • sperrfrei: garantiert systemweiten Fortschritt durch systemweite Schrittausführung
    ** nach einer endlichen Anzahl von systemweiten Schritten hat mindestens ein Prozess die Operation vollendet, ohne Rücksicht auf die relativen Geschwindigkeiten der anderen Prozesse.
    ** impliziert behinderungsfrei, wenn systemweit nur Schritte in einem ausgewählten Prozess ausgeführt werden

  • wartefrei: garantiert prozessweiten Fortschritt durch prozessweite Schrittausführung
    ** jeder Prozess kann die Operation in einer endlichen Anzahl von prozessweiten Schritten vollenden, ohne Rücksicht auf die relativen Geschwindigkeiten der anderen
    ** impliziert sperrfrei, denn jede prozessweite Schrittausführung ist auch eine systemweite Schrittausführung


Die Reformulierungen erlauben möglicherweise auch Verallgemeinerungen. Was passiert, wenn wir die Definition von Wartefreiheit leicht abändern zu “garantiert prozessweiten Fortschritt durch systemweite Schrittausführung”? Das wäre stärker als Wartefreiheit. Prozesse könnten die Arbeit anderer Prozesse in einer präemptiven Weise abnehmen.

Auch habe ich jetzt Lust bekommen diese Konzepte in einem Theorembeweiser zu formalisieren!