L'interblocage

Deux ressources pour une seule opération

Une cellule d'assemblage comporte un convoyeur et un bras robotique. Transférer une pièce demande les deux en même temps : le convoyeur doit rester immobile pendant que le bras saisit la pièce. Deux lignes de production partagent cette cellule, et chacune réserve ce dont elle a besoin par un verrou.

La ligne A réserve le convoyeur puis le bras, ce qui est l'ordre naturel de son opération : la pièce arrive par le convoyeur, le bras la reprend. La ligne B fait l'inverse, tout aussi naturellement : le bras dépose la pièce, le convoyeur l'emporte. Chacune prend ses deux verrous, s'en sert, et les libère. Chaque programme, pris isolément, est juste.

Deux clics suffisent. La ligne A détient le convoyeur et demande le bras ; la ligne B détient le bras et demande le convoyeur. Aucun bouton n'accepte plus le clic, aucune des deux ne relâchera quoi que ce soit, puisque chacune attend avant la partie de son programme qui libère. La figure l'annonce en toutes lettres : interblocage. Le compteur de pièces transférées est resté à 0, et il y restera.

Sur le terrain, cela s'appelle une ligne arrêtée. Aucun voyant ne s'allume, aucune alarme ne se déclenche, les deux automates sont sous tension et « en cours de traitement ». Le diagnostic prend des heures, parce que la première question posée est toujours « qu'est-ce qui a planté ? », et que rien n'a planté.

Un code juste, qui ne s'arrête jamais

Le point le plus important du chapitre est celui-ci, et il mérite d'être martelé : ce programme n'a aucune erreur de programmation au sens habituel. Il compile, il passe l'analyse statique, chaque fonction prise séparément est correcte, les verrous sont libérés dans un bloc with, et une relecture ligne à ligne ne révèle rien, parce qu'il n'y a rien à voir sur une ligne. Le défaut est une propriété de deux morceaux de code mis ensemble, et il porte sur l'ordre dans lequel ils réclament leurs ressources.

Restent les tests. Ils ne le trouvent pas davantage, et la figure explique pourquoi mieux qu'un discours.

C'est le même programme, avec une ligne d'affichage de plus dans chaque fil. Le compte donne trente-six entrelacements, dont deux finissent en interblocage. Sur la figure précédente, plus courte, c'étaient deux entrelacements sur six.

Le nombre d'entrelacements dangereux n'a pas bougé, c'est le nombre total qui a été multiplié par six. Autrement dit, plus le programme contient de travail entre les acquisitions, plus l'interblocage devient rare, sans jamais devenir impossible. Un test qui lance la cellule cent fois a de bonnes chances de ne rien voir. Le blocage attendra la charge réelle, celle où les deux lignes tournent ensemble des milliers de fois par jour, et il arrivera.

La règle qui dissout l'attente circulaire

L'attente circulaire a besoin d'un cycle. Supprimer le cycle supprime l'interblocage, et il existe une façon de le supprimer qui ne coûte rien : décider un ordre unique sur tous les verrous du programme, et exiger que chaque fil acquière les siens dans cet ordre.

Avec l'ordre « convoyeur avant bras », la ligne B doit réclamer le convoyeur en premier, même si son opération commence par le bras. Rien d'autre ne change.

Deux entrelacements, aucun interblocage, et le compteur finit à 2 dans les deux cas. La raison tient en une phrase : celui qui obtient le premier verrou obtiendra le second, puisque personne ne peut détenir le second sans avoir obtenu le premier. Le cycle est devenu impossible à former, et il l'est par construction, pas par chance.

Trois postes, trois verrous, et un cycle plus difficile à voir

À deux fils, le cycle se repère en lisant deux lignes côte à côte. À trois, plus personne ne le voit, parce qu'aucune paire de fils prise isolément n'est fautive. Une cellule complète comporte un convoyeur, un bras et une palette ; chaque poste n'a besoin que de deux ressources sur les trois.

Trois clics, un par poste, et la cellule est figée : A tient le convoyeur et veut le bras, B tient le bras et veut la palette, C tient la palette et veut le convoyeur. Aucune paire ne suffit à expliquer le blocage, il faut les trois.

Le compte donne quatre cent deux entrelacements, dont six finissent en interblocage, soit un peu moins de un et demi pour cent. Un essai sur soixante-sept, voilà la fréquence d'un défaut qui arrête une ligne de production. Aucune campagne de tests ne garantit de le rencontrer, et son absence ne prouve rien.

La règle ne change pas d'un iota, et elle traite le cas à trois aussi bien que le cas à deux. Ordre retenu ici : bras, puis convoyeur, puis palette. Chaque poste réclame ce dont il a besoin dans cet ordre, en sautant les verrous qui ne le concernent pas.

Cinq cent trente-huit entrelacements, aucun interblocage, et le compteur finit à 3 dans tous les cas. Deux postes ont changé : A prend désormais le bras avant le convoyeur, et C le convoyeur avant la palette, l'un et l'autre à rebours de leur logique métier. C'est le prix à payer, et il est nul.

La famine

L'interblocage n'est pas la seule façon de ne jamais avancer. Un fil peut aussi rester correct, non bloqué au sens de la figure, et pourtant ne jamais obtenir ce qu'il demande, simplement parce que d'autres le reprennent plus vite que lui.

Le fil lent demande le verrou en premier et passe en dernier. À chaque libération, rien n'oblige le système à le servir : si le fil rapide redemande aussitôt, il peut très bien l'obtenir de nouveau, et le lent attend un tour de plus. Ici le programme finit, parce que le fil rapide n'a que trois passages à faire ; dans un programme qui tourne en continu, il n'en a pas trois mais un flot, et le fil lent peut attendre indéfiniment.

Un verrou ordinaire ne promet rien sur l'ordre de service. Les remèdes relèvent de la conception : réduire la durée de détention pour que les passages soient plus nombreux, employer une file d'attente qui sert dans l'ordre d'arrivée quand la plateforme en offre une, ou revoir un découpage qui fait passer un même fil cent fois plus souvent que les autres.

Les gestes Python

Deux points pratiques accompagnent la règle d'ordre. Le premier est un piège qui produit un interblocage à un seul fil : un verrou ordinaire pris deux fois par le même fil se bloque lui-même, car il ne compte pas ses acquisitions.

La seconde acquisition d'un Lock échoue, et elle aurait bloqué le fil pour toujours si elle avait été demandée normalement. Le cas se produit dès qu'une fonction protégée en appelle une autre qui prend le même verrou, ce qui arrive sans que personne ne l'ait voulu, après une réorganisation du code. Le RLock accepte la reprise par son détenteur et demande autant de libérations que d'acquisitions.

Le second point est la mise en œuvre de l'ordre unique. Quand les verrous sont connus d'avance, il suffit de les écrire dans le bon ordre. Quand ils sont créés dynamiquement, un par machine ou un par dossier, l'ordre se définit sur une clé stable, et l'acquisition passe par une pile de contextes.

L'appelant demande ses ressources dans l'ordre qui l'arrange, sorted impose l'ordre commun, et ExitStack libère tout à la sortie du bloc, y compris si une exception traverse le traitement. L'ordre d'acquisition cesse alors de dépendre de la vigilance du rédacteur, ce qui est la seule façon d'en faire une règle tenable.

Exercices type

Vérification

La méthode

1. Lister les fils qui prennent plus d'un verrou : ce sont les seuls concernés, et ils sont en général peu nombreux.
2. Écrire, pour chaque fil, la suite de ses acquisitions, dans l'ordre du programme, sur une seule ligne par fil.
3. Tracer les attentes : chaque fil attend une ressource détenue par un autre, et un cycle dans ce tracé est un interblocage possible.
4. Décider un ordre unique sur toutes les ressources, fondé sur une clé stable, et l'écrire à un endroit que le prochain rédacteur trouvera.
5. Vérifier que chaque suite d'acquisitions est croissante pour cet ordre, fil par fil, sans jamais raisonner par paires de fils.
6. Confier l'ordre au code plutôt qu'à la vigilance : une fonction d'acquisition qui trie les clés et empile les contextes, plutôt qu'une consigne écrite dans un document.
7. Éprouver le résultat sur une figure : le compte des entrelacements ne doit plus en donner aucun qui laisse le travail inachevé.

Synthèse

• Un interblocage est un état où chaque fil d'un groupe attend une ressource détenue par un autre : aucun n'a fini, aucun ne peut avancer, et la situation ne se dénoue jamais.
• Sa cause est l'attente circulaire, qui apparaît dès que deux fils acquièrent deux verrous dans des ordres opposés.
• Le code fautif est syntaxiquement parfait et logiquement juste : la faute porte sur l'ordre des acquisitions, ne se voit sur aucune ligne, et n'apparaît que sur une petite part des entrelacements, six sur quatre cent deux dans la cellule à trois postes.
• La règle qui dissout le cycle est d'acquérir les verrous dans un ordre identique partout ; l'ordre choisi est indifférent, son unicité ne l'est pas, et l'ordre de libération n'a aucune importance.
• Sur des verrous créés à la volée, l'ordre se définit sur une clé stable de la ressource, et se met en œuvre par un tri des clés suivi d'une pile de contextes.
• La famine est un autre échec à progresser, mais d'une autre nature : le programme avance, et c'est un fil en particulier que les autres devancent sans cesse.

Les deux derniers chapitres ont ajouté des verrous, puis des règles pour que les verrous ne se retournent pas contre le programme. Le chapitre suivant change de modèle et pose la question autrement : et si les fils ne pouvaient être interrompus qu'aux endroits marqués par le rédacteur, la plupart de ces verrous auraient-ils encore lieu d'être ?