Das untenstehende Protokoll sollte relativ vollständig sein. Ich habe es „didaktisch komprimiert“, d.h. z.B. Hänger von mir ausgelassen.
Zwei Ereignisse nebenläufig, wenn keines Ursache oder Wirkung des anderen.
Betrachte Menge aller Ereignisse mit Halbordnung (partial order) „x ist Ursache von y“.
Unvergleichbare Elemente sind nebenläufig; wir können sie entweder sequentiell oder parallel zur Ausführung bringen.
Vergleichbare Elemente müssen zur Laufzeit zwingend sequentialisiert werden; dafür gibt es verschiedene Methoden.
Ja, beim Übersetzen nach tieferen Ebenen können vorher nebenläufige Ereignisse nun gekoppelt in Erscheinung treten.
Als Beispiel betrachte zwei Programme, deren Prozesse zur Laufzeit beide auf den Speicher zugreifen. Diese Zugriffe können dann durch den Bus sequentialisiert werden.
Prozesse geben Kontrolle über Geschehen ab; wechseln in Zustand „blockiert“.
* Beispiel 1: Programm nutzt BS-Primitiven (z. B. Sperren) um zu blockieren. ⇒ Zur Ausführung gibt der kernel-level Prozess (d.h. Prozess auf BS-Ebene) die Kontrolle ab; kernel-level Prozesszustand wechselt zu „blockiert“:
* Beispiel 2: Programm nutzt in Anwendungssoftware kodierte Umlaufsperren um zu blockieren. ⇒ Zur Ausführung gibt der Anwendungsprozess die Kontrolle ab, der kernel-level Prozess aber nicht.
Sperren, Semaphore, Mutexe
Mutexe sind Methoden zur Sicherstellung wechselseitigen Ausschlusses [siehe Anhang des Foliensatzes zu Mutexe zum Thema Mutexe vs. Mutexentitäten]. Mutexentitäten sind Objekte mit einer `acquire` und einer `release`, wobei `release` überprüft, ob der aufrufende Prozess auch der war, der `acquire` vorher vollendet hatte. Allgemeine Semaphore können für unilaterale Synchronisation eingesetzt werden, typischerweies innerhalb des Produzenten-Verbraucher-Musters. Hierbei kann der Produzent nach dem Produzieren neuer Daten das Signal, dass neue Daten verfügbar sind, absetzen, indem er `V` aufruft. Und der Konsument kann auf den Erhalt dieses Signals synchronisieren, indem er `P` aufruft. Spezialisiert mensch den allgemeinen Semaphor auf den Wertebereich `{0, 1}` zu einem binären Semaphor und fügt einen Autorisierungsprüfung um `V` herum hinzu, so erhält mensch eine Mutexentität.
* Verklemmungen möglich
* je nach Sofware sind Ein- und Austrittsprotokolle von Sperren unverhältnismäßig teuer im Vergleich zu dem kritischen Abschnitt, den sie schützen sollen
(i) Anforderung von Ressourcen mit wechselseitigem Ausschluss, (ii) iterative Anforderung dieser, (iii) keine Präemption dieser, (iv) zirkuläres Warten
Zur Laufzeit überprüfen wir bei jeder Ressourcenanforderung, ob damit ein unsicherer Zustand eingenommen werden würde – unter Ausnutzung von a priori Informationen über die Programmstruktur. Ein unsicherer Zustand ist ein Zustand, aus dem – egal mit welcher zukünftiger Planerstrategie – immer eine Verklemunng resultieren wird.
Solche Anforderungen lehnen wir ab oder führen den anfordernden Prozess dem long-term-scheduling zu.
Nur (iv) zirkuläres Warten.
Vorbeugung ist ein konstruktiver Ansatz, um eine der Bedingungen zu entkräften; Vermreidung ein analytischer Ansatz, um zur Laufzeit unsichere Zustände zu vermeiden.
Wir können die Flinte ins Korn werfen und Verklemmungserkennung betreiben – d.h. reagieren wenn es eigentlich schon zu spät ist.
Jede Ressourcenanforderung und -freigabe mitprotokollieren in einem Graphen. Dann regelmäßig (z. B. wenn Systemdurchsatz weniger wird oder soagr exzessiv bei jeder Ressourcenanforderung) überprüfen, ob dieser Graph einen Zyklus enthält.
Falls ja, hängt das ein bisschen vom BS ab, was wir tun können.
Bei spezialisierten BS können wir einen Rollback beteiligter Prozesse durchführen, wenn dieses es denn unterstützen.
Bei general-purpose BS können wir eigentlich nur Prozesse terminieren (unschön).
Ticketlock ist fair/verhungerungsfrei, da first-come-first-serve.
Außerdem weniger Bussperren.
Ticketlock hat im `lock()` genau eine (fetch-and-add zum Ziehen einer Wartemarke); TAS/CAS-basierte Locks haben unbegrenzt viele.
Ja, angenommen 100 Prozesse konkurrieren im Eintrittsprotokoll, der 101-te Prozess hält das Ticketlock und macht dann ein `unlock()`. Das führt dann im Extremfall zu 100 Cache update/invalidate Requests mit nachfolgenden 100 (ggf. sequentialisierten) Ladeanfragen über den Bus.
Wir haben den Zähler verallgemeinert zur einer Warteschlange. Jeder Prozess korrespondiert zu einem Eintrag in dieser Warteschlange und jeder Eintrag besitzt zwei Felder: einen next-Zeiger und eine boolsche Variable zum Spinnen.
Jeder Prozess spinnt nur auf der zu seinem Eintrag korrespondierenden Variable.
Und wenn ein Prozess `unlock()` ausführt (also Kopf der Warteschlange war), so invalidiert dieser nur die boolsche Variable desjenigen Prozesses, der nach ihm folgt (also nächster innerhalb der Warteschlang war).
Das Ticketlock ja u.a. deswegen schick ist, weil es zu keinen Buslock Bursts führt, so wie bei TAS/CAS-basierten Umlaufsperren.
Die würde mensch sich da wieder einholen.
Und mensch hätte wieder die Gefahr einer Verhungerung (eben in den Eintrittsprotokollen dieser Umlaufsperren) herbeigeführt.
(Hier wollte wosch das recht genau wissen, obige Antwort ist die Zusammenstellung dessen, was er und ich dann in der Prüfung „erarbeitet“ haben. Es lohnt sich wohl sich das nochmal anzusehen und womöglich präziser auszuformulieren.)
nichtblockierend, sogar wartefrei.
Ich glaube wir haben nur im `unlock()` ein CAS benutzt. Nichtdestrotrotz war unsere Implementierung nicht ABA-kritisch – gegeben durch das spezielle Zugriffsmuster, das wir hatten.
(Nicht sicher, ob das tatsächlich stimmt – aber wosch wollte nur darauf hinaus, dass Nutzung von CAS manchmal ABA-kritisch sein kann und manchmal es nicht ist.)
Getaggte Zeiger (aber unschön) oder – wenn die CPU das unterstützt – LoadLinked/Store Conditional (LL/SC).
(Wir waren schon am Ende der Prüfung, daher hat diese kurze Antwort gereicht.)