Frage zu drei Anforderungen unter Berücksichtigung des Problems des kritischen Abschnitts

Question

Kürzlich lese ich das Buch Betriebssystem-Konzepte In Kapitel VI über das Problem des kritischen Abschnitts, in Abschnitt 6.2, wissen wir, dass ein Algorithmus zur Lösung des Synchronisationsproblems drei Anforderungen erfüllen muss: 1. Gegenseitiger Ausschluss 2.Fortschritt 3.Begrenzte Wartezeit. Wenn ein Algorithmus die zweite Bedingung (Fortschritt) erfüllt, bedeutet dies natürlich nicht unbedingt, dass dieser Algorithmus auch die Bedingung des begrenzten Wartens erfüllt, da die Geschwindigkeit des Prozesses oder die Terminplanung eine Rolle spielen.

Meine Frage ist jedoch: Wenn ein Algorithmus die Anforderung "Bounded Waiting" erfüllt, können wir daraus schließen, dass dieser Algorithmus auch die Anforderung "Progress" erfüllt? Wenn nein, wie lautet die Bedingung? Wenn ja, warum erheben wir nicht NUR die dritte Anforderung und streichen die zweite, da die dritte die zweite implizieren kann. Kann mir jemand den Zusammenhang (und die Unterschiede) zwischen der zweiten und der dritten Anforderung erklären?

Answer 1

Die Konzepte des Fortschritts und des begrenzten Wartens sind völlig unterschiedlich.

Begrenztes Warten bedeutet, dass ein Prozess irgendwann die Sperre/den Mutex erhalten kann. Während die Fortschrittsbedingung bedeutet, dass der Prozess seine Ausführung abschließen kann. Es gibt einen Umstand, der als Live-Lock bezeichnet wird (entspricht dem Deadlock), bei dem zwei oder mehr Prozesse als Prozessgruppe organisiert sind, alle Prozesse können eine Sperre erhalten oder freigeben, was die Bedingung des begrenzten Wartens erfüllt, aber die Prozessgruppe kann nicht fortschreiten (oder warum wir es Live-Lock nennen. :-)).

Viel Glück und viele Grüße

Answer 2

Die erste Voraussetzung ist glasklar, denn das Hauptziel des gegenseitigen Ausschlusses ist ... Hm, sich gegenseitig auszuschließen, richtig?

Die zweite Anforderung (Fortschritt) ist in gewissem Sinne eine falsche Bezeichnung. Nehmen wir an, dass in einem bestimmten System eine Reihe von Prozessen gleichzeitig ablaufen, z. B. P1, P2, P3, P4 und P5, und keiner von ihnen führt den kritischen Abschnitt (CS) aus. Irgendwann, zu einem bestimmten Zeitpunkt, interessieren sich die Prozesse P1, P2 und P3 für die gleichzeitige Ausführung des CS. In dieser Situation besagt die Fortschrittsbedingung, dass nur P1, P2 und P3 das Recht haben, selbst zu entscheiden, wer in den CS eintritt (P4 und P5 dürfen diese Entscheidung auf keinen Fall beeinflussen). Nebenbei bemerkt, legt diese Anforderung auch fest, dass eine solche Entscheidung nicht ewig dauern kann, daher ihr Name ("Fortschrittsanforderung"). Ich denke, dass dies ein nicht beschreibender Begriff ist; "Abschlussanforderung" passt besser, da nur die interessierten Prozesse das Recht haben, zu entscheiden, wer den CS ausführen wird). Meines Erachtens zielt diese Anforderung darauf ab, Live-Locks zu verhindern (bei denen alle Prozesse zueinander sagen: "Bitte, führen Sie aus, Sie sind dran").

Die dritte Anforderung (Bounded Waiting) ist eng mit der zweiten verbunden. Während die Fortschrittsanforderung besagt, dass die interessierten Prozesse innerhalb einer endlichen Zeit eine Entscheidung treffen müssen, besagt die Bedingung Bounded Waiting, dass kein Prozess unendlich lange warten muss, um ein Aushungern zu verhindern: Nachdem Pn einen Antrag auf Eintritt in den CS gestellt hat, kann nur eine begrenzte Anzahl von Prozessen Pn umgehen. Aufgrund ihrer Definition und im Gegensatz zur zweiten Bedingung trägt diese Anforderung den bezeichnenden Namen "Bounded Waiting" oder manchmal auch "Bounded Bypass". aquí ). Für den Fall, dass Sie Portugiesisch verstehen, hier die Definition, die ich gefunden habe aquí :

Die erste Anforderung ist offensichtlich, denn sie ist das Hauptziel der Lösung. Die zweite besagt, dass wenn sich kein Prozess in der kritischen Region befindet und es Prozesse gibt, die sich anschließen möchten, dann wird nur der Prozesse, die teilnehmen möchten, entscheiden mit, wer teilnimmt, und diese Entscheidung ist nicht auf unbestimmte Zeit verschoben. Die dritte Anforderung besagt, dass ein Prozess, der in den Die kritische Region darf nicht unendlich lange warten, bis sie an der Reihe ist, d. h., wenn es einen Prozess gibt warten, muss es eine Begrenzung der Anzahl der Ein- und Austritte anderer Prozesse in ihre kritischen Bereiche geben. aus ihren kritischen Regionen.