Les sémaphores satisfont-ils à l'attente bornée?

Question

Est-ce que le sémaphore satisfait l'attente bornée ou est-ce juste pour fournir une exclusion mutuelle?

Answer 1

Réponse

Il peut se briser bornées état d'attente théoriquement comme vous le verrez ci-dessous. En pratique, cela dépend fortement de l'algorithme d'ordonnancement utilisé.

La mise en œuvre est aussi classique de wait() et signal() primitive:

//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); 
    } 
} 

Lorsqu'un processus appelle l'wait() et échoue au test « si », il se mettra dans une liste d'attente. Si plus d'un processus sont bloqués sur le même sémaphore, ils sont tous mis dans cette liste (ou ils sont liés d'une manière ou d'une autre comme vous pouvez l'imaginer). Lorsqu'un autre processus quitte la section critique et appelle signal(), un processus de la liste d'attente sera choisi pour se réveiller, prêt à être de nouveau en concurrence pour le processeur. Cependant, c'est le planificateur qui décide du processus à choisir dans la liste d'attente. Si la planification est mise en œuvre de manière LIFO (dernier entré, premier sorti) par exemple, il est possible que certains processus soient affamés.

Exemple

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 
.. 

Comme vous pouvez le voir, même si vous implémente/utilise correctement le sémaphores, le thread 2 a un temps d'attente sans bornes, même peut-être la famine, causée par entrée continue de nouveaux procédés.