Wenn der gegenseitige Ausschluss garantiert ist, sagen wir mit Semaphoren, ist ein Programm Deadlock-frei?

Question

I definieren mutual exclusion und wie unten Deadlock jeweils: Die gegenseitige Ausschlussbedingung existiert in jedem Moment, wenn jede gemeinsam genutzte Ressource entweder genau einen Prozess zugeordnet ist, oder zur Verfügung. Eine Gruppe von Prozessen ist festgefahren, wenn jeder Prozess in der Gruppe auf ein Ereignis wartet, das nur ein anderer Prozess in der Gruppe verursachen kann.

Angenommen, binäre Semaphore werden verwendet, um sicherzustellen, dass nur einer von ihnen gleichzeitig seine kritische Region betreten kann. Da jeder Prozess kurz vor dem Eintritt in seine kritische Region und unmittelbar nach dem Verlassen eine abklingt, ist ein wechselseitiger Ausschluss garantiert.

Ich verstehe, gibt es vier Bedingungen, die alle halten müssen Deadlock auftreten, von denen eines die gegenseitige Ausschlussbedingung (keine zwei Prozesse innerhalb ihrer kritischen Abschnitte gleichzeitig sein kann).

Da wechselseitiger Ausschluss garantiert ist, ist das Programm in diesem Fall deadlock-frei?

Grüße.

Answer 1

Nicht unbedingt. Stellen Sie sich vor, diese beiden Themen:

Thread 1   Thread 2 
============  ============= 
Acquire A   Acquire B 
Acquire B   Acquire A 
Release B   Release A 
Release A   Release B 

Hier wird die gegenseitige Ausgrenzung in der Tat garantiert - zu jedem Zeitpunkt, Semaphore A und B sind entweder im Besitz einer der Fäden oder systemweit verfügbar - aber Deadlock ist immer noch möglich, wenn Thread 1 und 2 Jeder erwirbt seine erste Sperre (A für Thread 1, B für Thread 2), aber dann wird Deadlock warten auf die Ressource, die der andere hält.

Hoffe, das hilft!