Skip to main content

Algorithmes Distribués & 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 asycrones. Les IPC et 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é par une fonction asyncrones comme un handler de signal. Supposons que l'on définisse deux fonctions de manipulation de la variable :

int getValue();
void setValue(int);

Pour incrémenter la variable, il suffit d'exécuter setValue(getValue()+1); mais décomposont 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 suivant du code par deux thread.

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

Que c'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 pierre 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 sur chaque rive,
    • si elles avancent en même temps -> interblocage
    • si elles attendent en même temps -> interblocage
  3. Un remède : un conté prioritaire -> 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 comme SCCS, RCS.

Mode d'utilisation des ressources par un processus​

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

  • requete : demande bloquante des ressources
  • utilisation : lecture/écriture sur la zone verrouillée
  • libération : verrou L-type

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 sont nécessaires pour avoir possibilité d'interblocage

  • Exclusion mutuelle les ressources ne sont pas partageables, un seul processus à la fois peut utiliser la ressource
  • Possession & attente il doit exister un processus qui utilise une ressource et qui est en attente sur une requête
  • 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 Pi tel que Pi attend une ressource possédée par Pi+1.

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) N = P U R
P : ensemble des processus
R : ensemble des ressources

Soit le coupe (x,y) appartenant à T, si (x,y) appartient à RXP, cela signifie que la ressource x est utilisée par le processus y, si (x,y) appartient à PXR, cela signifie que le processus x demande la ressource y.

0%