C 2 Semaphoren und zwei Prozesse

[cikidanomikidan]

Hallo liebe Gemeinde,

ich habe folgendes Problem. Ich habe diesen Programmiercode gegeben:

Prozess P1
S1.acquire();
while (! S2.testAcquire()) {
S1.release();
sleep(1);
S1.acquire();
}
// kritischer Abschnitt
S2.release();
S1.release();

und

Prozess P2
S2.aqcuire();
while (! S1.testAcquire()) {
S2.release();
sleep(1);
S2.aqcuire();
}
// kritischer Abschnitt
S1.release();
S2.release();

Beide Prozesse versuchen zwei binäre Semaphore S1 und S2 zu bekommen. Die atomare Funktion testAquire() versucht, das Semaphore zu bekommen, falls es frei ist. Wenn ja, gibt s ein true zurück, wenn nein, ein false.

Dieser Code kann einen Livelock verursachen, aber ich weiß einfach nicht, wieso.


Grundsätzlich braucht P1 doch gar nicht S2, also muss gar nicht in die While-Schleife eintreten, um in den kritischen Abschnitt zu gelangen. Das selbe gilt für P2 anders rum. Also wie soll ein Livelock entsehen, bei dem der Prozesszustand READY oder RUNNING ist, ohne Fortschritt?

Hat jemand Rat?

 

[RalphS]

Du meinst abgesehen davon, daß die sich gegenseitig die sems wegnehmen?

vielleicht übersehe ich aber auch was. So nesting ist immer eklig.

 

[cikidanomikidan]

"
Ein Livelock ist eine Form der Blockierung mehrerer Prozesse, die im Unterschied zum
Deadlock nicht in einem Zustand verharren, sondern ständig zwischen mehreren
Zuständen wechseln, aus denen sie nicht mehr entkommen können.
Definition: Livelock"

Das ist die Definition eines Livelocks. Und ich weiß, dass da als Lösung rauskommt, dass da ein Livelock auftreten kann. Warum, weiß ich aber nicht.

Die Semaphore sind doch für den wechselseitigen Ausschluss da, oder nicht? Bzw. in diesem Fall, hängt es davon ab, ob der jeweilige Prozess für ne Sekunde schläft, falls er den Semaphor bekommt.

 

[Tornhoof]

Das ist irgendeine Uni Aufgabe oder?
Ggf. solltest du ein Petrinetz (wenn wir schon von Uni reden) aufmalen und es durchspielen
Sobald du von wechselseitiger Ausschluss redest bist du eigentlich bei Mutexen.

 

[cikidanomikidan]

Ja, ist es. Ich habe es verstanden!
Jeweils P1 oder P2 brauchen BEIDE Semaphore, um in den kritischen Abschnitt einzutreten. Daher testet man mit der while Schleife, ob das jeweilige andere Semaphor frei ist. Wenn nein, dann gibt man sein eigenes Semaphor frei und wartet so lange, damit der andere Prozess die Möglichkeit hat, beide Semaphore zu bekommen. Und das gleiche Problem kann bei dem anderen Prozess auftreten, immer abwechselnd, und das ist dann ein sogenannter Livelock. Da kein Prozess jemals beide Semaphore bekommt.