4. Solutions par attente active
4.1 Solution de Peterson
La solution étudiée vise exactement deux participants. Chaque participant p possède un indicateur d’intérêt et connaît other = 1 - p :
Code (c) · sélectionner pour copier
critical[p] = 1;
waiting = p;
while (waiting == p && critical[other] == 1) {
/* attente active */
}
/* section critique */
critical[p] = 0;
critical[p] annonce l’intention d’entrer. waiting départage le cas où les deux sont intéressés. La condition combine donc l’état de l’autre et la décision de priorité.
Pour vérifier l’algorithme, on place des interruptions après chaque affectation possible. Si un seul participant est intéressé, il avance. Si les deux le sont, la dernière valeur de départage permet à un seul de franchir la boucle; l’autre attend jusqu’à ce que le gagnant retire son indicateur. Le raisonnement ne repose pas sur leur vitesse.
La version présentée est pédagogique :
- elle est limitée à deux participants;
- elle doit être recopiée exactement, car inverser le sens d’une condition change sa correction;
- elle pratique l’attente active;
- elle sert surtout à apprendre à prouver l’exclusion mutuelle par les états et les entrelacements.
4.2 Test-and-set et échange atomique
Une instruction test-and-set lit l’ancienne valeur d’un verrou et le place à l’état occupé en une opération atomique. Une instruction exchange échange atomiquement un registre ou une valeur locale avec le verrou. Elles ferment exactement la fenêtre « tester puis écrire » du verrou naïf.
Le participant boucle jusqu’à obtenir l’état libre, exécute sa section critique, puis réécrit zéro. Le résultat est un verrou tournant (spin lock).
4.3 Coût d’un verrou tournant
Un spinlock consomme du processeur et de l’énergie pendant l’attente. Il peut néanmoins être préférable à un blocage lorsque :
- la section critique est extrêmement courte;
- le détenteur s’exécute réellement sur un autre cœur;
- le coût d’un changement de contexte dépasserait l’attente prévue.
Dans les noyaux, une instruction telle que PAUSE peut réduire l’impact de la boucle sur x86. Sur un seul cœur, tourner pendant que le détenteur ne peut pas s’exécuter est inutile : dormir est préférable.
4.4 Inversion de priorité
Un thread L de basse priorité prend un verrou. Un thread H de haute priorité devient ensuite prêt et tente de prendre ce verrou. S’il tourne activement, H peut monopoliser le processeur et empêcher L de reprendre pour libérer la ressource. H est alors indirectement bloqué par L : c’est une inversion de priorité.
Un protocole d’héritage de priorité peut temporairement élever L afin qu’il termine sa section critique. Le point essentiel est qu’une priorité élevée ne supprime pas une dépendance; elle peut même l’aggraver si le mécanisme d’attente est mal choisi.