Frage zum Dekker-Algorithmus
-
Den Peterson-Algorithmus hattest du ja auch erwähnt und den haben wir auch durchgesprochen und ich habe ihn mir mal nochmals angeschaut.
M. A. n. kann es dort zu einem Deadlock kommen, wenn in einem bestimmten Bereich Interrupts nicht abgeschaltet werden:Stell dir vor, Prozess 0 fängt an:
// globale Variablendeklaration boolean flag0 = false, flag1 = false; int turn; // Prozess #0 // ... flag0 = true; /* 1. HIER FINDET NUN EIN KONTEXTWECHSEL ZU PROZESS 1 STATT!!! Springe zu 2. in Prozess 1! */ /* 4. Kontextwechsel von Prozess 1 auf Prozess 0 */ turn = 1; /* Da nun flag1 von Prozess1 auf true gesetzt wurde, wartet Prozess 0 ebenfalls auf Prozess 1 --> Deadlock! */ while (flag1 && (turn == 1)) {} // busy waiting // <kritischer Abschnitt> flag0 = false; // ... // Prozess #1 // ... /* 2. Kontextwechsel von Prozess 0 auf Prozess 1... */ flag1 = true; turn = 0; /* 3. flag0 wurde ja von Prozess 0 auf true gesetzt, also wartet Prozess 1 auf Prozess 0... Irgendwann gibt es dann wieder einen Kontextwechsel auf Prozess 0*/ while (flag0 && (turn == 0)) {} // busy waiting // <kritischer Abschnitt> flag1 = false; // ...
-
*Sigh* Shared Memory ist ein Inter-Process-Communication Mittel.
-
Nein, Prozess1 warted nicht auf Prozess0, denn in Schritt 4 wird turn = 1 gesetzt, d.h. bei Prozess1 in Zeile 31 wird flag0 && (turn == 0) falsch, womit Prozess weitergehen und in die Critical Section eintreten kann.
Oder sehe ich das falsch?
-
Zeus schrieb:
*Sigh* Shared Memory ist ein Inter-Process-Communication Mittel.
Hmm... da hast du recht, habs gerade gegoogelt. Ich bin mir aber ziemlich sicher, dass mir in der Vorlesung gesagt wurde, dass Prozesse keinen gemeinsamen Speicher haben.
Kann es sein, dass es in C# so ist, dass Prozesse nicht ueber gemeinsamem Speicher kommunizieren koennen?
-
icarus2 schrieb:
Zeus schrieb:
*Sigh* Shared Memory ist ein Inter-Process-Communication Mittel.
Hmm... da hast du recht, habs gerade gegoogelt. Ich bin mir aber ziemlich sicher, dass mir in der Vorlesung gesagt wurde, dass Prozesse keinen gemeinsamen Speicher haben.
Generell stimmt das, aber man kann vom Kernel einen gemeinsamen Speicherbereich für Prozesse anfordern. Der Speicherbereich hat dann einen Schlüssel über den dann andere Prozesse zugreifen können.
-
Steffo schrieb:
icarus2 schrieb:
Zeus schrieb:
*Sigh* Shared Memory ist ein Inter-Process-Communication Mittel.
Hmm... da hast du recht, habs gerade gegoogelt. Ich bin mir aber ziemlich sicher, dass mir in der Vorlesung gesagt wurde, dass Prozesse keinen gemeinsamen Speicher haben.
Generell stimmt das, aber man kann vom Kernel einen gemeinsamen Speicherbereich für Prozesse anfordern. Der Speicherbereich hat dann einen Schlüssel über den dann andere Prozesse zugreifen können.
Achso, das wusste ich nicht, danke fuer die Info.
-
icarus2 schrieb:
Nein, Prozess1 warted nicht auf Prozess0, denn in Schritt 4 wird turn = 1 gesetzt, d.h. bei Prozess1 in Zeile 31 wird flag0 && (turn == 0) falsch, womit Prozess weitergehen und in die Critical Section eintreten kann.
Stimmt, das hatte ich übersehen!
-
icarus2 schrieb:
Steffo schrieb:
icarus2 schrieb:
Zeus schrieb:
*Sigh* Shared Memory ist ein Inter-Process-Communication Mittel.
Hmm... da hast du recht, habs gerade gegoogelt. Ich bin mir aber ziemlich sicher, dass mir in der Vorlesung gesagt wurde, dass Prozesse keinen gemeinsamen Speicher haben.
Generell stimmt das, aber man kann vom Kernel einen gemeinsamen Speicherbereich für Prozesse anfordern. Der Speicherbereich hat dann einen Schlüssel über den dann andere Prozesse zugreifen können.
Achso, das wusste ich nicht, danke fuer die Info.
Unter Linux gibt es da die Funktionen shmget() und shmat().
Naja, jedenfalls BTT: Wenn ein Prozess abschmiert, kann es bei IPCs übel aussehen, richtig?!
L. G.
Steffo
-
Nebenbei bemerkt: wenn der Besitzer einer Mutex abstürzt, dann hat man meist sowieso ein Problem.
Nämlich dann, wenn es gemeinsam verwendete Datenstrukturen gibt. Da man nicht weiss wo der Prozess abgeschmiert ist, kann man dann nämlich auch nicht wissen ob diese Datenstrukturen noch/wieder in einem konsistenten Zustand sind.
-> doof
-
Steffo schrieb:
Ja, aber was, wenn das Programm abstürzt, so dass man gar nichts mehr fangen kann?!
Wieso schreibt Wikipedia so einen Schund ("vollständige Lösung")? In meinen Vorlesungsfolien ist davon auch nicht die Rede, obwohl sonst immer darauf eingegangen wurde, wenn es Deadlocks geben kann, wenn ein Prozess im kritischen Bereich abstürzt...Wikipedia schreibt keinen Schund. Wikipedia kann nix dafür, dass du das "Mutual Exclusion Problem" anders als üblich definierst - wobei eben üblich ist die Behandlung von abgestürzten Prozessen aussen vor zu lassen.
Und unter dieser Definition löst der Dekker-Algorithmus das Problem vollständig.
