Algorithmes distribués et interblocages

Ce chapitre introduit les problèmes liés à la gestion de processus concurrents. Le problème à résoudre est le partage de ressources entre différents processus asynchrones. Les IPC et les verrous sont deux types d'outils permettant le partage asynchrone de ressources entre processus.

Exemple

Les méfaits des accès concurrents

L'exemple le plus simple est une variable entière partagée par deux processus ou threads, ou bien manipulée par une fonction asynchrone comme un gestionnaire de signal. Supposons que l'on définisse deux fonctions de manipulation de la variable :

int getValue(void);
void setValue(int);

Pour incrémenter la variable, il suffit d'exécuter setValue(getValue() + 1);. Décomposons en int tmp = getValue(); setValue(tmp + 1);, ce qui ne change pas grand-chose, tmp étant simplement allouée sur la pile dans le premier cas. Regardons l'exécution suivante du code par deux threads :

int tmp1 = getValue();
                        | int tmp2 = getValue();
setValue(tmp1 + 1);
                        | setValue(tmp2 + 1);

Que s'est-il passé ? La variable n'a été incrémentée qu'une fois.

Exclusion mutuelle

Problème : il y a une rivière que l'on peut traverser par un gué fait de pierres alignées, où il n'est pas possible de se croiser, et il n'est pas possible de faire demi-tour. Comment doit-on organiser le passage ?

1. regarder avant de traverser ;
2. si deux personnes arrivent en même temps, chacune sur une rive :
   • si elles avancent en même temps : interblocage,
   • si elles attendent en même temps : interblocage ;
3. un remède : un côté prioritaire, mais risque de famine ;
4. une solution : alterner les priorités.

Pour des ressources système comme les fichiers, le partage n'est pas géré par le SGF. Il faut donc un mécanisme de partage : les verrous, qui permettent un partage dynamique et partiel (portions de fichiers). Pour un partage entre utilisateurs, on utilise plutôt des outils de gestion de versions comme SCCS ou RCS (aujourd'hui Git).

Mode d'utilisation des ressources par un processus

Formalisons les opérations réalisables sur une ressource :

• requête : demande bloquante de la ressource (par exemple pose d'un verrou avec F_SETLKW) ;
• utilisation : lecture/écriture sur la zone verrouillée ;
• libération : retrait du verrou (verrou de type F_UNLCK).

Définition de l'interblocage (deadlock)

Un ensemble de processus est en interblocage si et seulement si tout processus de l'ensemble est en attente d'un événement qui ne peut être réalisé que par un autre processus de l'ensemble.

Quatre conditions nécessaires à l'interblocage

Les conditions suivantes (conditions de Coffman) sont nécessaires pour qu'un interblocage soit possible :

• exclusion mutuelle : les ressources ne sont pas partageables, un seul processus à la fois peut utiliser la ressource ;
• possession et attente : il doit exister un processus qui détient au moins une ressource et qui est en attente d'une autre ressource ;
• sans préemption : les ressources ne sont pas préemptibles, c'est-à-dire que les libérations sont faites volontairement par les processus. On ne peut pas forcer un processus à rendre une ressource ;
• attente circulaire : il doit exister un ensemble de processus $\{P_0, \dots, P_n\}$ tel que $P_i$ attend une ressource possédée par $P_{i+1}$ pour $i < n$, et $P_n$ attend une ressource possédée par $P_0$.

Supprimer l'une de ces quatre conditions suffit à prévenir l'interblocage.

Les graphes d'allocation de ressources

Les graphes d'allocation de ressources permettent de décrire simplement les problèmes d'interblocage :

$$G = (N, T), \quad N = P \cup R$$

où $P$ est l'ensemble des processus et $R$ l'ensemble des ressources.

Soit le couple $(x, y) \in T$. Si $(x, y) \in R \times P$, cela signifie que la ressource $x$ est utilisée par le processus $y$ ; si $(x, y) \in P \times R$, cela signifie que le processus $x$ demande la ressource $y$.

Un cycle dans ce graphe est une condition nécessaire d'interblocage ; lorsque chaque ressource n'existe qu'en un seul exemplaire, c'est aussi une condition suffisante.