mise en œuvre incorrecte de la méthode barrière de synchronisation

Question

Considérons la méthode barrière suivante pour mettre en œuvre la synchronisation:

void barrier 
{ 
    P(s); 
    process_arrived++; 
    V(s); 
    while(process_arrived != 3); 
    P(s); 
    process_left++; 
    if(process_left == 3) 
    { 
     process_Arrived = 0; 
     process_left = 0; 
     } 
    V(s); 
} 

On sait que ce code ne fonctionne pas à cause d'un défaut, mais je ne suis pas en mesure de trouver la faille.

Answer 1

Le problème est à la condition: if (process_left == 3)

Il peut conduire à une impasse si deux invocations de barrière sont utilisés en succession immédiate.

Initialement, process_arrived et process_left seront '0'.
Lorsqu'un processus arrive, il incrémente process_arrived et attend jusqu'à ce que le nombre maximal de processus soit arrivé. Après que les processus sont autorisés à partir.

Envisagez le scénario suivant:

P1 est et attend jusqu'à ce que process_arrived devient 3 (actuellement process_arrived = 1)
P2 vient et attend jusqu'à ce que process_arrived devient 3 (actuellement process_Arrived = 2)
maintenant P3 vient pour l'exécution. La condition dans while boucle échoue et s'exécute plus loin, en faisant process_left = 1 et entre de nouveau dans la fonction immédiatement.
Il fait process_Arrived = 4 et attend la boucle while.
P2 obtient une chance d'exécution rend process_left = 2 et quitte.
P1 s'exécute plus loin et trouve que process_left = 3, faisant ainsi process_arrived et process_left = 0. (Rappelez-vous que P3 est déjà entré et attend à la barrière, donc un nombre est perdu)
P1 exécute à nouveau, fait process_arrived = 1 et attend.
P2 est également réexécuté. rend process_arrived = 2 et attend.

Maintenant, chaque processus attendra pour toujours. D'où une impasse s'est produite.