Not logged in. · Lost password · Register

Tobs40
Member since Oct 2017
42 posts
Subject: 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?
zge
(〜 ̄▽ ̄)〜
Avatar
Member since Nov 2017
184 posts
+1 Marcel[Inf]
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 compare_and_swap benutzen, da diese (meist) in Schleifen benutzt werden, wie bei jbuffer. Stattdessen weicht man aus auf (zumindest laut dieser Seite) Sachen wie "atomic_exchange" oder "atomic_fetch_add", die ja "atomar" eine Sache abfertigen.

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

We have presented a relatively fast, O(log n) time, wait-free algorithm for n-process approximate agreement. This shows that wait-free algorithms for approximate agreement can be fast, but not as fast as the best non-wait-free algorithms for this problem: we have shown that log n is a lower bound on the time complexity of any wait-free approximate agreement algorithm, while there exists an O(1) time non-wait-free algorithm. (source)

-----

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:

A data structure is lock-free if and only if some operation completes after a finite number of steps system-wide have been executed on the structure

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 CAS oder LL/SC benutzt. Das ist ein entscheidender Unterschied zu Wartefreien Algorithmen, wo ja das CAS-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 ->:

The  most  radical  way  in  which  our  approach  of  implementing  obstruction-free  algorithms  differs  from  the usual approach of implementing their lock-free and wait-free  counterparts  is  that  we  think  that  ensuring  progress should be considered a problem of engineering, not of mathematics.

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):

If all other threads are paused [bspw. durch den Scheuleder] then any given thread will complete its operation in a bounded number of steps.

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 ^^
;;
This post was edited on 2019-02-19, 09:17 by zge.
Tobs40
Member since Oct 2017
42 posts
Vielen Dank!!! :)
Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
624 posts
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:

  1. pthread_mutex_t m;
  2. volatile int i = 0;
  3.  
  4. void algorithm(void) {
  5.   pthread_mutex_lock(&m);
  6.   i++;
  7.   pthread_mutex_unlock(&m);
  8. }

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 pthread_mutex_lock aufruft, kann doch in einer endlichen Anzahl von Schritten vollenden. Denn derjenige Prozess muss nur i++ und pthread_mutex_unlock 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 by 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.)

Und https://preshing.com/20120612/an-introduction-to-lock-free… sagt:
Quote by 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.

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:
Quote by Fraser K., Practical lock-freedom, p. 14:
A data structure is lock-free if and only if some operation completes after a finite number of steps system-wide have been executed on the structure.

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":
  1. typedef struct chain_t {
  2.   chain_t *link;
  3. } chain_t;
  4.  
  5. void push(chain_t *this, chain_t *item) {
  6.  do {
  7.     item->link = this->link;
  8.  } while(!CAS(&this->link, item->link, item));
  9. }
(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 p*n systemweiten Schritten gibt es mindestens einen CAS-Aufruf. (Denn bei p*n systemweiten Schritten, muss es mindestens einen Prozess mit >= n Schritten gegeben haben [sonst hätten alle Prozesse < n Schritte und wir hätten ingesamt < p*n systemweite Schritte].) D.h. nach p*n systemweiten Schritten hat mindestens ein Prozess vollendet.
This post was edited 6 times, last on 2021-03-17, 17:30 by Marcel[Inf].
Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
624 posts
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
This post was edited on 2021-03-17, 17:55 by Marcel[Inf].
Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
624 posts
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!
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen