tun Semaphoren genügt beschränkt warten

Question

Stimmt Semaphor begrenzt warten oder sie sind nur für die gegenseitige Ausgrenzung ??

Answer 1

Antwort

brechen Wartezustand theoretisch begrenzt kann, wie Sie unten sehen werden. In der Praxis hängt es stark davon ab, welcher Scheduling-Algorithmus verwendet wird.

Die klassische Umsetzung von wait() und signal() primitiv ist wie:

//primitive 
wait(semaphore* S) 
{ 
    S->value--; 
    if (S->value < 0) 
    { 
     add this process to S->list; 
     block(); 
    } 
} 

//primitive 
signal(semaphore* S) 
{ 
    S->value++; 
    if (S->value <= 0) 
    { 
     remove a process P from S->list; 
     wakeup(P); 
    } 
} 

Wenn ein Prozess die wait() ruft und schlägt die „if“ Test, wird es sich in eine Warteliste gesetzt. Wenn mehrere Prozesse auf dem gleichen Semaphor blockiert sind, werden sie alle in diese Liste eingefügt (oder sie sind irgendwie miteinander verbunden, wie Sie sich vorstellen können). Wenn ein anderer Prozess den kritischen Abschnitt verlässt und das Signal() aufruft, wird ein Prozess in der Warteliste ausgewählt, um aufzuwachen und bereit zu sein, erneut um die CPU zu konkurrieren. Es ist jedoch der Scheduler, der entscheidet, welcher Prozess aus der Warteliste ausgewählt werden soll. Wenn die Planung zum Beispiel in einer LIFO-Methode (last in first out) implementiert wird, ist es möglich, dass ein Prozess ausgehungert wird.

Beispiel

T1: thread 1 calls wait(), enters critical section 
T2: thread 2 calls wait(), blocked in waiting list 
T3: thread 3 calls wait(), blocked in waiting list 
T4: thread 1 leaves critical section, calls signal() 
T5: scheduler wakes up thread 3 
T6: thread 3 enters critical section 
T7: thread 4 calls wait(), blocked in waiting list 
T8: thread 3 leaves critical section, calls signal() 
T9: scheduler wakes up thread 4 
.. 

Wie Sie sehen können, obwohl Sie implementiert/verwendet den Semaphore richtig, Faden 2 hat eine unbeschränkte Wartezeit, möglicherweise sogar Hunger, durch kontinuierliche Eingabe neuer Prozesse verursacht.