Précédent Remonter Suivant
Chapitre 6 Concurrence

T rès souvent, on doit exécuter plusieurs instructions simultanément, ceci pour plusieurs raisons. D'abord, il existe des machines avec plusieurs processeurs de calcul, et il faut bien les programmer. Ensuite, de nombreux programmes contrôlent des automatismes réagissant à des événements asynchrones (programmation réactive). C'est le cas des jeux dont les programmes réagissent à plusieurs boutons que l'on peut actionner dans des ordres imprévisibles. De même, dans les systèmes embarqués, on réagit aux informations fournies régulièrement par des capteurs. Une autre forte raison à la programmation concurrente est la recherche de la diminution des temps de latence. Par exemple, si un programme controle des claviers ou des périphériques lents, il ne faut pas bloquer tout un système dans l'attente d'événements très peu fréquents. Plus généralement, si on croit que les ordinateurs simulent les humains, on remarque que ces derniers ont un comportement concurrent. Par exemple, on n'arrête pas le fonctionnement de son coeur pour lire ces notes de cours. Une autre raison pour s'intéresser au comportement concurrent des programmes est la multiplicité des utilisateurs d'un système informatique. De même, sur un réseau informatique, un grand nombre d'activités ou d'utilisateurs co-existent. Si on écrit un programme de gestion du réseau, on doit pouvoir traiter l'exécution simultanée de plusieurs tâches. Une dernière raison de s'intéresser aux programmes parallèles est qu'on peut obtenir un facteur d'accélération, puisqu'avec plus de puissance de calcul on peut résoudre plus rapidement un problème. Si cet argument est vrai dans le principe et fait l'objet de l'algorithmique parallèle, il faut remarquer que le facteur d'accélération ne dépasse jamais le nombre de processeurs exécutant ce programme. Souvent il est moindre, car une certaine synchronisation est nécessaire entre les diverses tâches s'exécutant en parallèle.

Toutes ces raisons attestent du besoin d'exprimer la concurrence par programme. Dans ce chapitre, nous introduisons les notions de base de la concurrence: processus, sémaphores, conditions, et problèmes d'ordonnancement.

6.1 Processus

Un processus (thread) est un programme qui s'exécute. Un programme est le texte décrivant une suite d'instructions. Un processus correspond à l'action de l'exécuter. Jusqu'à présent aucune distinction n'était faite, car on ne considérait qu'un seul processus. Dans ce chapitre, comme il sera toujours question de plusieurs processus, la distinction devient importante et on remarque, par exemple, que plusieurs processus peuvent exécuter un même programme.

La partie concurrente de Java correspond à l'interface standard des bibliothèques de processus POSIX (the Portable Operating System Interface), qui existent actuellement sur pratiquement tous les systèmes et toutes les architectures matérielles. Certaines caractéristiques comme le style en programmation par objets sont plus spécifiques à Java.

Voici un programme qui démarre comme d'habitude par la fonction main, puis qui crée deux processus t1 et t2 exécutant en parallèle la méthode run de la classe Code. Cette méthode imprime continuellement le numéro du processus courant, puis laisse un autre processus s'exécuter, puis recommence l'impression du processus courant, etc.
class Code implements Runnable {
  public void run () {
    while (true) {
      System.out.println ("Bonjour de " + Thread.currentThread());
      Thread.yield();
    }
  }

  public static void main (String[ ] args) {
    Code p = new Code();
    Thread t1 = new Thread(p);
    Thread t2 = new Thread(p);
    t1.start(); t2.start();
  }
}


Figure 6.1 : Exécution concurrente de trois processus


L'interface Runnable ne contient que la méthode run qui est appelée au lancement d'un processus. Le constructeur des processus (Thread) prend un objet de la classe Runnable et le transforme en processus. Le lancement des processus t1 et t2 se fait en appelant la méthode start. Les deux processus t1 et t2 exécutent le même code p. La fonction statique currentThread donne la valeur du processus courant. On peut aussi ré-écrire le programme en style programmation par objets, style plus simple, mais qui donne moins de latitude sur la hiérarchie des classes utilisées:
class Code1 extends Thread {
  public void run () {
    while (true) {
      System.out.println ("Bonjour de " + this);
      Thread.yield();
    }
  }

  public static void main (String[ ] args) {
    Thread t1 = new Code1();
    Thread t2 = new Code1();
    t1.start(); t2.start();
  }
}

Remarquer le remplacement de currentThread en this, puisque this est alors le processus en cours d'exécution.

Le programme précédent comporte trois processus: le processus correspondant au programme principal démarrant par la fonction main, les deux processus créés t1 et t2. Un processus s'exécute sur un processeur. Un processeur est une entité matérielle de calcul. Tout ordinateur contient au moins un processeur. Pour que trois processus puissent s'exécuter concurremment, il faudrait au moins trois processeurs. Or bien souvent les machines actuelles n'ont qu'un seul processeur. L'environnement d'exécution simule alors l'existence des trois processeurs demandés, en attribuant par exemple périodiquement une tranche de temps à chacun des trois processus, comme illustré sur la figure 6.2. Nous reviendrons plus tard sur les stratégies d'allocation de temps pour les processus. Pour l'instant, nous ne considérons que la fonction yield qui cède le processeur sur lequel le processus tourne et donne plus de chance aux autres processus de s'exécuter immédiatement.


Figure 6.2 : Exécution concurrente de trois processus sur un processeur


Dans la terminologie officielle des systèmes d'exploitation, nos processus (threads) sont plutôt appelés des processus légers (light-weight processes). Les processus (lourds) sont les processus gérés directement par le système d'exploitation (Unix, Linux, Windows). Dans le système Unix, on obtient leur liste par la commande ps ou psaux. Un processus lourds peut générer plusieurs processus légers, qui sont donc gérés par un sous-système, par exemple par l'interpréteur de programmes Java (la Java Virtual Machine --- JVM). Les processus sont dits légers car basculer d'un processus à un autre est censé être une opération peu coûteuse. On dit alors que le changement de contexte est rapide. Du point de vue de la programmation, la principale différence entre processus lourds et légers concerne la mémoire: les processus légers partagent la zone mémoire, les processus lourds possèdent leur propre mémoire. De toutes façons, ici, comme nous ne nous soucions pas du système d'exploitation sous-jascent, les processus légers sont simplement appelés des processus.

6.2 Terminaison

Un processus peut se terminer spontanément. On peut aussi vouloir l'arrêter depuis un autre processus. Dans l'exemple précédent, le processus principal s'arrêtait juste après avoir lancé le processus t2. Les processus t1 et t2 eux ne s'arrêtaient pas et continuaient leur exécution indéfiniment. Cela n'est pas trop grave, puisqu'on peut toujours continuer à faire d'autres tâches en parallèle. Pourtant, en utilisant la fonction interrupt qui lève l'exception InterruptedException, on peut interrompre l'exécution d'un processus comme indiqué dans le programme suivant:
class Exemple1 implements Runnable {
  public void run () {
    try {
      while (true) {
 System.out.println ("Bonjour de " + Thread.currentThread());
 Thread.sleep (1000);  // Une seconde de pause
      }
    } catch (InterruptedException e) { }
  }

  public static void main (String[ ] args) {
    Thread t = new Thread (new Exemple1());
    t.start();
    t.interrupt();
  }
}

La fonction sleep arrête l'exécution d'un processus pendant le nombre de millisecondes données en argument. On l'utilise ici pour faire une pause entre deux impressions. Sur notre exemple, on constate que le processus t n'est pas arrêté brutalement depuis un autre processus puisqu'une exception lui est simplement envoyée. C'est le processus t qui gère sa propre terminaison. Ainsi les invariants logiques de t sont préservés, et le processus t peut se terminer dans un état cohérent.

Un processus peut aussi tester régulièrement s'il n'est pas interrompu, au lieu d'attendre une exception. Pour cela, il fait une attente active sur la fonction booléenne isInterrupted de la bibliothèque standard de Java:
class Exemple2 extends Thread {
  public void run () {
    while (!isInterrupted()) {
      System.out.println ("Bonjour de " + this);
    }
  }

  public static void main (String[ ] args) {
    Thread t = new Exemple2();
    t.start();
    t.interrupt();
  }
}

Un processus attend souvent la fin d'un autre processus. Par exemple, on lance un processus t et on attend qu'il finisse. Cela peut se réaliser en utilisant la fonction join qui prend en argument un délai maximum d'attente en millisecondes (0 si ce délai est infini). Ainsi:
class Exemple3 extends Thread {
  public void run () {
    System.out.println ("Bonjour de " + this);
  }

  public static void main (String[ ] args)
    throws InterruptedException {
    Thread t = new Exemple3();
    t.start();
    t.join (0);
  }
}

La méthode join lance une exception si un autre processus a interrompu le processus courant (qui est en attente).

Nous avons donc considéré la création, le lancement et l'arrêt des processus. Ceci constitue l'essentiel si les processus ne communiquent pas entre eux. Mais c'est rarement le cas, puisque si plusieurs activités sont menées en parallèle, c'est souvent pour calculer un résultat commun ou partager certaines informations. Le reste du chapitre décrit la synchronisation nécessaire pour communiquer entre processus. Plusieurs modèles standards existent pour cette communication. Ici nous allons considérer le modèle simple de la mémoire partagée.

6.3 Variables partagées

Dans le programme suivant, la variable globale x de la classe P peut être modifiée par les deux processus t1 et t2. Comme ces deux processus s'exécutent en parallèle, il est dûr de prédire la valeur de x imprimée dans main: 0, 23, 7 ou autre chose?
class P {
  static int x = 0;

  public static void main (String args[ ])
    throws InterruptedException {
    Thread t1 = new P1(), t2 = new P2();
    t1.start(); t2.start();
    while (true) {
      System.out.println (x);
      Thread.sleep (1000);
} } }

class P1 extends Thread {
  public void run () {
    while (true) {
      P.x = 23;
      Thread.yield();
} } }

class P2 extends Thread {
  public void run () {
    while (true) {
      P.x = 7;
      Thread.yield();
} } }

Pour répondre à cette question, il faut comprendre l'atomicité des instructions et l'ordonnancement des processus. Une instruction est atomique si elle ne peut être interrompue pour laisser l'exécution à un autre processus. Très peu d'instructions sont atomiques au niveau du langage de programmation puisque chaque instruction correspond à plusieurs instructions machine exécutées par le processeur. Toutefois on peut dire que la lecture ou de l'écriture d'un mot (de 32 bits) dans la mémoire d'un ordinateur est atomique. Au niveau de Java, on peut donc dire que l'écriture d'un entier dans une variable et que la lecture de la valeur d'une variable entière sont atomiques. Cependant, cela n'est plus vrai pour les entiers longs (de 64 bits) ou pour les flottants en double précision (double), sauf si on dispose d'un processeur 64 bits.

Par ailleurs, on ne peut prédire l'ordre dans lequel t1 ou t2 modifient la variable partagée x. Cela dépend de l'ordonnancement des processus t1, t2 et de celui exécutant main. Cet ordre peut varier entre deux exécutions du même programme. La seule conclusion à retenir est que les programmes concurrents sont souvent non déterministes. Ils peuvent donner des résultats différents sur les mêmes données dans deux exécutions distinctes. Ce phénomène rend particulièrement délicate la programmation de processus concurrents.

6.4 Sections critiques

Une section critique rend atomique un ensemble d'instructions, par exemple pour modifier plusieurs données ou une donnée composite, tout en maintenant des invariants. Prenons l'exemple classique du transfert d'argent entre deux comptes bancaires, on veut que la somme des deux comptes reste constante, même si plusieurs appels de la fonction transfertVersB sont faits simultanément dans des processus distincts. Pour cela, il suffit interdire l'exécution de cette fonction pendant qu'un autre processus l'exécute. C'est ce que fait le qualificatif synchronized qui contrôle l'accès à une section critique:
class ComptesBancaires {
  private int compteA, compteB;

  synchronized void transfertVersB (int s) {
    compteA = compteA - s;
    compteB = compteB + s;
  }
}

Le corps de la fonction transfertVersB est une section critique qui doit s'exécuter en exclusion mutuelle. Les exécutions de cette fonction sont donc sérialisées, c'est-à-dire faites séquentiellement, puisqu'on garantit qu'un seul appel de cette fonction s'exécute au plus à un moment donné. Pour cela, le processus, qui appelle une méthode avec le qualificatif synchronized, doit obtenir un verrou sur cette fonction. Si le verrou est déjà pris par ce processus ou par un autre, l'appel est suspendu jusqu'à ce que le verrou soit disponible. En Java, comme tout est objet, les verrous sont associés à des objets: une méthode synchronisée doit prendre le verrou sur l'objet dont elle est une méthode. Il n'y a qu'un verrou par objet. Si deux méthodes d'un même objet sont synchronisées, elles s'excluent donc mutuellement. Par conséquent, une méthode synchronisée au plus peut être appelée simultanément sur un même objet. Mais une même méthode peut être appelée simultanément sur deux objets différents, car les deux appels prennent alors un verrou différent sur chaque objet. Pour les méthodes statiques, une méthode statique prend un verrou associée à toute la classe si elle est synchronisée.

Finalement, remarquons que seules les méthodes peuvent avoir le mot-clé synchronized, les champs de données ne peuvent avoir ce qualificatif. Il est toutefois possible de rendre atomique un ensemble d'instructions, plutôt que le corps d'une fonction. Alors il faut donner en argument l'objet sur lequel on veut prendre le verrou. Cette forme de section critique permet de faire une section critique plus finement que sur des appels de méthodes.
class ComptesBancaires {
  private int compteA, compteB;

  void transfertVersB (int a) {
    ...
    synchronized (this) {
      compteA = compteA - s;
      compteB = compteB + s;
    }
    ...
  }
}

Il est possible de prendre plusieurs verrous pour exécuter un bout de programme. Mais créer des sections critiques demande un peu d'attention, puisque des interblocages (deadlocks) sont possibles. Ainsi dans:
class P1 extends Thread {
  public void run () {
    synchronized (a) {
      synchronized (b) {
        ...
} } } }

class P2 extends Thread {
  public void run () {
    synchronized (b) {
      synchronized (a) {
        ...
} } } }

Si deux processus t1 et t2 exécutent les codes de P1 et P2 en parallèle, le processus t1 peut prendre le verrou sur a; le processus t2 peut alors prendre le verrou sur b, et il y a un interblocage, puisque les deux verrous sont pris et que chaque processus attend la libération d'un verrou pris par l'autre processus. Détecter les interblocages peut être très complexe, c'est un des problèmes standards des systèmes concurrents. Souvent un tel système s'arrête à cause d'un tel interblocage.
Exercice 33   Faire un exemple d'interblocage avec des appels sur des méthodes synchronisées.

6.5 Conditions

Un paradigme de la programmation concurrente est celui de la file d'attente concurrente. Pour simplifier, supposons que la longueur maximale de la file vaut 1. Alors la file ne peut qu'osciller entre les deux états: vide ou plein. Les deux méthodes ajouter et supprimer peuvent s'exécuter de manière concurrente. On pourrait être tenté d'écrire:
class FIFO {
  boolean   pleine;
  int       contenu;
  FIFO () { pleine = false; }

  synchronized void ajouter (int x) {
    if (pleine)
      // Attendre que la file se vide
    contenu = x;
    pleine = true;
  }

  synchronized int supprimer () {
    if (!pleine)
      // Attendre que la file devienne pleine
    pleine = false;
    return contenu;
  }
}

La fonction ajouter attend que la file se vide, la fonction supprimer attend que la file se remplisse. Ces deux opérations s'excluent mutuellement pour que les variables internes de la file (contenu, pleine) restent dans un état cohérent. Mais ce code ne fonctionne pas, puisqu'un ajout dans une file pleine prend le verrou et interdit à quiconque de vider la file. Dans chacun des cas d'attente, la fonction devrait relâcher le verrou pour que l'autre processus puisse s'exécuter. Il faut donc ressortir de chaque méthode sans se bloquer et revenir tester la file. C'est alors une attente active (busy wait) qui coûte cher en temps. Il est préférable d'utiliser le concept de condition dû à Hoare. Une condition est associée à un verrou. Quand on attend sur une condition, on relâche atomiquement le verrou et on attend un signal sur la condition. Quand il y a notification d'un signal sur la condition, on reprend le verrou (si possible) et on redémarre à l'endroit où on s'était mis en attente.

En Java, une condition est une simple référence à un objet (son adresse). Il n'y a qu'une seule condition par objet (ce qui est une solide restriction). On peut attendre sur la condition d'un objet dont on a déjà pris le verrou. L'exemple précédent s'écrit donc précisément:
  synchronized void ajouter (int x)
    throws InterruptedException {
    while (pleine)
      wait();
    contenu = x;
    pleine = true;
    notify();
  }

  synchronized int supprimer ()
    throws InterruptedException {
    while (!pleine)
      wait();
    pleine = false;
    notify();
    return contenu;
  }

Les fonctions wait et notifiy sont deux méthodes de la classe Object. Tous les objets possèdent ces deux méthodes puisque toute classe est une sous-classe de Object. La méthode wait attend sur la condition et relâche le verrou de l'objet correspondant à la condition. Si ce verrou n'est pas pris, l'exception IllegalMonitorStateException est levée. (Cette exception est une exception du système d'exécution, c'est-à-dire sous-classe de RuntimeException; il n'est pas nécessaire de la mentionner dans la signature des fonctions ajouter et supprimer). La méthode notify met dans l'état prêt à l'exécution un des processus en attente sur cette condition. Quand celui-ci repart, il reprend automatiquement le verrou. Remarquons que l'on itère sur l'attente de la condition avec une instruction while, plutôt que de faire une simple instruction conditionnelle if. En effet, entre le moment où le processus est réveillé et celui où il s'exécute, rien n'empêche qu'un autre processus ne prenne le verrou n'invalide le test sur l'état de la file. Il faut donc toujours utiliser une telle instruction while. Si on veut réveiller plusieurs processus, on utilise la méthode notifyAll, qui réveille tous les processus en attente sur la condition.

Enfin, on remarque que les les méthodes wait et notify peuvent générer l'exception InterruptedException en cas d'interruption des processus les appelant. Au total, le programme contenant le lancement des deux processus t1 et t2 qui appellent les fonctions ajouter et supprimer s'écrit comme suit.
class FIFO {
  ... // définitions de la classe, d'ajouter et de supprimer

  public static void main (String[ ] args)
    throws InterruptedException {
    FIFO f = new FIFO();
    Thread t1 = new P1(f), t2 = new P2(f);
    t1.start(); t2.start();
    Thread.sleep (200);
    t1.interrupt(); t2.interrupt();
} }

class P1 extends Thread {
  static int i = -1;
  FIFO f;
  P1 (FIFO x) {f = x; }

  public void run () {
    try {
      while (true) f.ajouter(++i);
    } catch (InterruptedException s) { }
} }

class P2 extends Thread {
  FIFO f;
  P2 (FIFO x) {f = x; }

  public void run () {
    try { while (true)
 System.out.println(f.supprimer());
    } catch (InterruptedException s) { }
} }

Exercice 34   Expliquer ce qu'il se passe si on n'interrompt pas le processus t2.

Exercice 35   Modifier le programme pour que la file puisse contenir n éléments (n > 1).

Exercice 36   Ecrire un programme de gestion d'une pile concurrente avec deux méthodes ajouter et supprimer.

Pour bien comprendre le sens de wait et de notify, on remarque que cette dernière fonction n'a pas de mémoire. Elle ne fait qu'envoyer un signal à un des processus en attente. Rien n'est enregistré. C'est pourquoi la méthode wait atomiquement relâche le verrou et attend sur la condition. Sinon, un processus pourrait prendre le verrou et envoyer un signal de reprise avant que l'on attende sur la condition et ce signal serait perdu.
Exercice 37   Expliquer ce qu'il se passe si notify est fait après avoir relâché le verrou.

6.6 Etats d'un processus et ordonnancement

Un processus peut être dans plusieurs états comme indiqué sur la figure 6.3. Dans l'état prêt, un processus est prêt à être exécuté. Si un processeur devient disponible, il passe dans l'état exécution. Alors le processus s'exécute. En Java, il donne alors sa valeur à la variable globale currentThread qui indique à tout moment le processus courant. Un processus peut quitter l'état d'exécution pour plusieurs raisons. Par exemple, il termine en passant à l'état mort. Il peut aussi laisser sa place à un autre processus en repassant à l'état prêt. Il peut enfin passer à l'état bloqué, car en attente d'une condition ou d'un verrou. Si ceux-ci se libèrent, il passe dans l'état prêt.


Figure 6.3 : Les états d'un processus


Il peut donc y avoir plusieurs processus prêts à l'exécution. Si le nombre de processeurs est suffisant, ils peuvent tous passer à l'état d'exécution. Si ce n'est pas le cas (comme cela l'est bien souvent), le système doit choisir un des processus pour l'exécuter. En Java, c'est la JVM qui doit faire ce choix. Il lui faut donc une politique d'ordonnancement des processus. Les politiques d'ordonnancement se rangent en deux grandes catégories.

La stratégie d'allocation des processeurs peut être non préemptive. Cela signifie qu'un processus ne relâche pas un processeur tant qu'il ne l'a pas fait explicitement, par exemple avec la fonction Thread.yield. On dit aussi parfois que les processus fonctionnent alors en co-routines. Le désavantage d'une telle technique est que rien ne peut empécher un processus gourmand de monopoliser un processeur. Le gros avantage de cette technique est sa simplicité, car c'est le programme qui se charge de l'ordonnancement.

La deuxième technique d'allocation des processeurs est préemptive. Cela signifie que le système d'exécution des processus peut arrêter à tout moment un processus pour laisser la place à un autre. Souvent cela fonctionne avec un quantum de temps que l'exécution de tout processus ne doit pas dépasser avant d'abandonner le processeur.

Au niveau de Java, les transitions entre les divers états d'un processus sont donnés par:



Tous les processus ne sont pas égaux. On peut établir des priorités entre eux dans l'accès à l'état d'exécution. Les priorités sont simplement des nombres entiers associés à chaque processus. Les priorités statiques peuvent être manipulées et affectées par le programmeur avec les fonctions getPriority et setPriority. On peut utiliser les priorités suivantes prédéfinies: MIN_PRIORITY, NORM_PRIORITY, MAX_PRIORITY. L'ordonnanceur peut aussi affecter des priorités dynamiques pour gérer sa politique d'allocation du (des) processeur(s). La spécification de Java dit qu'en général les processus de forte priorité vont s'exécuter avant les processus de basse priorité.

Cependant, il est important d'écrire du code portable, donc de comprendre ce que la JVM garantit sur tous les systèmes. Ecrire du code contrôlant l'accès à des variables partagées en faisant des hypothèses sur la priorité des processus ou sur leur vitesse relative (race condition) est très dangereux, et doit donc être banni.





A titre de curiosité, nous considérons deux exemples de politique d'ordonnancement: la priorité sur l'age et la priorité dans le système Unix 4.3 BSD. Dans la stratégie de la priorité sur l'age, tout processus a initialement une priorité p=p0 dite priorité statique. Si un processus prêt attend le processeur pendant k secondes, on incrémente p. Le processus qui s'exécute est choisi parmi les processus prêts de plus forte priorité. Quand il s'exécute, on refait p = p0. Cette politique garantit qu'un processus en attente d'exécution depuis longtemps va prendre le processeur. Après exécution, on oublie son histoire et on revient à la priorité statique initiale. Cette stratégie donne donc la priorité aux vieux.

Dans la politique d'ordonnancement des processus du système Unix, au début p = pnice est la priorité statique initiale, où on a -20 £ pnice £ 20 (-20 pour le plus prioritaire, et 20 pour le moins prioritaire). Nous écrivons pnice au lieu de p0 pour rappeler que c'est la commande nice d'Unix qui fixe cette valeur. Toutes les 40ms, la priorité p d'un processus est recalculée par:
p = PUSER + é
ê
ê
ê
pcpu
4
ù
ú
ú
ú
+ 2  pnice
PUSER est une même constante pour tous les processus utilisateurs (ainsi distingués des processus du système), et pcpu est incrémentée toutes les 10 ms quand le processus s'exécute. Ainsi la valeur de p augmente si on utilise longtemps le processeur, le processus devient donc moins prioritaire. Les processus correspondants à des programmes interactifs, peu consommateurs du processeur, sont donc avantagés. Cependant, toutes les secondes, pcpu est aussi modifiée par le filtre suivant:
pcpu =
load
load + 1
  pcpu + pnice
qui fait baisser sa valeur en fonction de la charge globale du système load (la charge est le nombre moyen de processus prêts sur la dernière minute). Si la charge est grande, la valeur de pcpu est peut altérée, et les processus gros consommateurs de processeur sont toujours pénalisés. Au contraire, si la charge est faible, la valeur de pcpu diminue et on essaie de faire disparaitre aussi vite que possible un processus qui s'exécute en lui donnant plus longtemps le processeur. (A nouveau, dans le système Unix, la priorité croit dans l'ordre inverse de sa valeur: p < 0 est très prioritaire; p = 127 correspond à un processus peu prioritaire).





Finallement, voici un exemple démontrant le danger de l'interaction entre la synchronisation et les priorités, c'est le phénomène d'inversion de priorités suivant: soient trois processus tb, tm, th s'exécutant en priorité basse, moyenne, et haute. Supposons que tb prenne un verrou qui bloque th. Si maintenant tm s'exécute, il empêche tb (de priorité plus faible) de s'exécuter. Supposons que tm ne relâche pas le processeur, alors tb ne peut progresser, et le processus de plus faible priorité tm empêche le processus th de s'exécuter. On peut s'en sortir en affectant des priorités sur les verrous en notant qu'un processus de plus haute priorité attendant sur ce verrou, et on fait monter la priorité d'un processus ayant pris un verrou bloquant un processus de forte priorité (cela fonctionne en Windows). Pour conclure, un bon conseil est d'éviter le mélange de priorités et de synchronisations.

6.7 Les lecteurs et les écrivains

L'exemple de la file d'attente avec accès concurrents ne fait pas de distinction entre les phases de lecture et d'écriture. Pourtant il est très courant d'avoir des fonctions d'accès différenciés entre celles ne consistant qu'à lire la structure de donnée partagée et celles la modifiant. La particularité de la lecture est qu'elle ne change pas la valeur de la donnée lue. Plusieurs lectures concurrentes peuvent donc s'effectuer simultanément. Pour l'écriture, au contraire, il faut s'assurer qu'elle se fait en exclusion mutuelle de toutes les autres fonctions d'accès à la donnée, puisque, si on lit une donnée en cours de modification, on peut obtenir un résultat incohérent. C'est le problème dit des lecteurs et des écrivains. Une donnée partagée peut autoriser la lecture par n (n > 0) processus simultanément, mais ne permet l'écriture que par un seul processus. Tous les systèmes de réservation de places en ligne (train, avion, théatre) sont des exemples de ce problème, puisqu'il ne s'agit pas de signaler une place disponible au moment même où un autre client la prend.

La lecture commence par exécuter la fonction accesPartage qui vérifie que l'on peut obtenir un accès partagé à la donnée que l'on veut lire. Elle se finit par une fonction retourPartage qui remet en place les verrous pris pour effectuer la lecture. De même, l'écriture commence par l'exécution de la fonction accesExclusif et se finit par une autre fonction retourExclusif. Nous supposons qu'une variable globale nLecteurs donne à tout moment le nombre de lecteurs. Par convention, nLecteurs = -1 si un écrivain est en action.
void lecture() {
  accesPartage();
  // lire la donnée partagée
  retourPartage();
}

void ecriture() {
  accesExclusif();
  // modifier la donnée partagée
  retourExclusif();
}

synchronized void accesPartage() {
  while (nLecteurs < 0)
    wait();
  ++nLecteurs;
}

synchronized void retourPartage() {
  -- nLecteurs;
  if (nLecteurs == 0)
    notify();
}

synchronized void accesExclusif() {
  while (nLecteurs != 0)
    wait();
  nLecteurs = -1;
}

synchronized void retourExclusif() {
  nLecteurs = 0;
  notifyAll();
}

NotifyAll est pratique, il évite de gérer l'ensemble des lecteurs en attente. Pourtant il peut réveiller trop de processus qui se retrouvent immédiatement bloqués. Pour arriver à un contrôle plus fin, on peut considérer deux conditions séparées en lecture et en écriture, et attendre sur l'une ou sur l'autre. Ceci est impossible en Java, car on ne peut disposer de conditions différentes sur un même verrou, mais cela est possible dans toutes les bibliothèques de processus Posix (un standard assez répandu). Pour exposer notre solution, nous supposons disposer de telles conditions Posix: wait est une méthode prenant en argument l'objet dont la condition libère ou reprend le verrou, notify, notifyAll ont leur sens classique. Avec deux conditions (lecture et écriture), et une variable globale nLecteursEnAttente qui compte le nombre de lecteurs en attente. on obtient le contrôle plus fin suivant:
synchronized void accesPartage() {
  ++ nLecteursEnAttente;
  while (nLecteurs < 0)
    lecture.wait(this);
  -- nLecteursEnAttente;
  ++ nLecteurs;
}

synchronized void retourPartage(this) {
  -- nLecteurs;
  if (nLecteurs == 0)
    ecriture.notify();
}

synchronized void accesExclusif() {
  while (nLecteurs != 0)
    ecriture.wait(this);
  nLecteurs = -1;
}

synchronized void retourExclusif() {
  nLecteurs = 0;
  if (nLecteursEnAttente > 0)
    lecture.notifyAll();
  else
    ecriture.notify();
}

Exécuter notify à l'intérieur d'une section critique n'est pas très efficace. Avec un seul processeur, ce n'est pas un problème car les processus réveillés passent dans l'état prêt attendant la disponibilité du processeur. Avec plusieurs processeurs, le processus réveillé peut retomber rapidement dans l'état bloqué, tant que le verrou n'est pas relaché. Le mieux est de faire notify à l'extérieur de la section critique.
void retourPartage() {
  boolean faireNotify;
  synchronized (this) {
    -- nLecteurs;
    faireNotify = nLecteurs == 0;
  }
  if (faireNotify)
    ecriture.notify();
}

Des blocages inutiles sont possibles (même avec plusieurs processeurs) sur le notifyAll de fin d'écriture. Comme avant, on peut le sortir de la section critique. Si plusieurs lecteurs sont réveillés, un seul prend le verrou. Mieux vaut faire notify en fin d'écriture, puis refaire notify en fin d'accès partagé pour relancer les autres lecteurs.
void accesPartage() {
  synchronized (this) {
    ++ nLecteursEnAttente;
    while (i < 0)
      lecture.wait(this);
    -- nLecteursEnAttente;
    ++ nLecteurs;
  }
  lecture.notify();
}

Une famine est possible pour un écrivain en attente de fin de lecture. La politique d'ordonnancement des processus peut aider. On peut aussi logiquement imposer le passage d'un écrivain.
void accesPartage() {
  synchronized () {
    ++ nLecteursEnAttente;
    if (nEcrivainsEnAttente > 0)
      lecture.wait(this);
    while (i < 0)
      lecture.wait(this);
    -- nLecteursEnAttente;
    ++ nLecteurs;
  }
  lecture.notify();
}

synchronized void accesExclusif() {
  ++ nEcrivains;
  while (i != 0)
    ecriture.wait(this);
  -- nEcrivainsEnAttente;
  nLecteurs = -1;
}

En conclusion, on constate que contrôler finement la synchronisation peut être complexe.
Exercice 38   Donner un exemple précis où notifyAll fait une différence avec notify.

Exercice 39   Montrer que le réveil des processus n'est pas forcément dans l'ordre premier en attente, premier réveillé.

Exercice 40   Donner un exemple où un processus peut attendre un temps infini avant d'entrer en section critique.

Exercice 41   Comment programmer un service d'attente où les processus sont réveillés dans l'ordre d'arrivée.

6.8 Implémentation de la synchronisation

Avec des fonctions synchronisées et des opérations atomiques comme wait ou signal, on peut aisément réaliser la synchronisation entre les processus. Il reste à comprendre comment implémenter ces deux fonctions et la prise d'un verrou. En général, cela dépend de l'architecture matérielle disponible. Très souvent, les ordinateurs disposent d'une instruction machine ininterruptible Test and Set. Cette opération TAS(m) teste atomiquement si la variable m vaut false et la positionne si m = false. Le résultat est vrai si m = true avant l'exécution, faux sinon. C'est sur les ordinateurs avec plusieurs processeurs que cette opération prend tout son sens, où une mémoire spéciale de ``verrous ``, accessibles par TAS, est souvent partagée entre tous les processeurs.

On programme une section critique ainsi, en posant m = false comme valeur initiale de m:
  while ( TAS(m) )
    ;
  // section critique
  m = false;

L'opération TAS(m) permet de tester et de modifier atomiquement la variable partagée m, et donc de garantir l'exclusion mutuelle pour l'exécution de la section critique. Cependant ce programme fait une attente active sur le passage de la valeur de m à false. En fait, comme nous le verrons plus loin avec les sémaphores, l'environnement d'exécution gère un ensemble de processus en attente sur le changement de valeur de certaines variables. Ces processus sont alors suspendus pendant cette attente.

Mais, sans l'instruction TAS, on peut tout de même y arriver, en n'utilisant que l'indivisibilité de la lecture ou de l'écriture en mémoire d'un scalaire de base. Ces algorithmes compliqués (Dekker, Peterson) sont des curiosités, car inutiles puisque le matériel procure toujours des verrous avec TAS. Cependant, ces algorithmes démontrent bien l'aspect complexe de la concurrence.
class Peterson extends Thread {
  static int tour = 0;
  static boolean[ ] actif  = {falsefalse};
  int i, j;
  Peterson (int x) { i = x; j = 1 - x; }

  public void run() {
    while (true) {
      actif[i] = true;
      tour = j;
      while (actif[j] && tour == j)
        ;
      // section critique
      ...
      // fin de section critique
      actif[i] = false;
      Thread.yield();
  } }

  public static void main (String[ ] args) {
    Thread t0 = new Peterson(0), t1 = new Peterson(1);
    t0.start(); t1.start();
} }

La démonstration est loin d'être évidente. Montrons d'abord la sureté de ce mécanisme d'exclusion mutuelle. Si t0 et t1 entrent tous les deux dans leur section critique, alors actif[0] = actif[1] = true. C'est impossible car les deux tests auraient été franchis en même temps alors que tour favorise l'un d'entre eux. Donc un des deux est entré. Disons t0. Cela veut dire que t1 n'a pu avoir trouvé le tour à 1 et qu'il n'est pas entré en section critique.

Montrons à présent la vivacité, c'est-à-dire qu'un processus voulant entrer dans la section critique finit par y entrer. En effet, supposons t0 bloqué dans le while. On a deux cas. Dans le premier cas, le processus t1 n'est pas intéressé par rentrer dans la section critique. Alors actif[1] = false. Et donc t0 ne peut être bloqué par le while. Dans le deuxième cas, le processus t1 est aussi bloqué dans le while. C'est impossible car tour vaut 0 ou 1. Donc l'un de t0 ou t1 ne peut rester dans le while.

Cette démonstration est formalisée avec des assertions logiques faisant intervenir la valeur des variables et des compteurs ordinaux c0 et c1, c'est-à-dire des emplacements de l'exécution dans chacun des deux processus. Les valeurs de ci sont les numéros affichés ci-dessous à gauche des lignes de la fonction run. Décorons le code de la fonction avec les assertions suivantes:
.  public void run() {
.    while (true) {
       {¬actif[i] Ù ci¹ 2 }
1      actif[i] = true;
       {actif[i] Ù ci = 2}
2      tour = j;
       {actif[i] Ù ci ¹ 2}
3      while (actif[j] && tour == j)
.        ;
       {actif[i] Ù ci¹ 2 Ùactif[j]Ú tour= i Ú cj = 2)}
.      // section critique
.      ...
.      // fin de section critique
5      actif[i] = false;
       {¬actif[i] Ù ci¹ 2}
6      Thread.yield();
.  } }

En outre, on adjoint à toutes les assertions la proposition suivante: j = 1 - i Ù (tour= 0 Ú tour= 1). On peut vérifier que chaque assertion est vérifiée quand chacun des deux processus s'exécute. On en déduit alors que les deux programmes ne peuvent atteindre la section critique simultanément, puisqu'alors on aurait simultanément les deux invariants de la ligne 5, c'est-à-dire:
  (tour= 0 Ú tour= 1)
Ù actif[0]  Ù  c0¹ 2  Ù  (¬actif[1]Ú tour= 0 Ú c1 = 2)
Ù actif[1]  Ù  c1¹ 2  Ù  (¬actif[0]Ú tour= 1 Ú c0 = 2)
qui équivaut à
(tour= 0 Ú tour= 1) Ù tour = 0 Ù tour = 1
ce qui est impossible.

On peut aussi prouver la vivacité avec les assertions. Par exemple, il est impossible que t0 soit en dehors de l'accès à la section critique pendant que t1 reste bloqué dans le while, car alors:
Ù ¬actif[0] Ù c0¹ 2 Ù (tour= 0 Ú tour= 1)
Ù actif[1] Ù c1¹ 2
Ù actif[0] Ù tour= 0
ce qui implique ¬actif[0] Ù actif[0]. Impossible! De même, les deux processus t0 et t1 ne peuvent rester tous les deux bloqués dans l'instruction while, car alors on a:
actif[1] Ù tour= 1 Ù actif[0] Ù tour= 0 Ù (tour= 0 Ú tour= 1)
ce qui est aussi impossible.
Exercice 42   Généraliser l'algorithme de Peterson au cas de n processus et d'une section critique en exclusion mutuelle.

6.9 Sémaphores

Une autre forme de synchronisation de bas niveau est la notion de sémaphore due à Dijkstra. Un sémaphore est une variable s booléenne, sur laquelle on fait les deux opérations atomiques suivantes: A la différence des conditions de Java, les sémaphores ne sont pas attachés à un verrou. Ce sont des variables qui ont un état. On peut les utiliser pour justement programmer un verrou comme dans l'exclusion mutuelle de sections critiques. Ainsi la construction de Java
  synchronized (o) {
    // section critique
  }
s'écrit en termes de sémaphores de la manière suivante:
  P(s0);
  try {
    // section critique
  } finally V(s0);

en supposant que so est un sémaphore associé à l'objet o. On peut aussi définir une classe Semaphore avec deux méthodes P et V en fonction des primitives wait et notify de Java:
class Semaphore {
  boolean libre;
  Semaphore (boolean x) { libre = x; }

  static void P(Semaphore s) {
    synchronized  (s) {
      while (!s.libre)
 try {
   s.wait();
 } catch (InterruptedException x) { }
    s.libre = false;
    }
  }

  static void V(Semaphore s) {
    synchronized (s) {
    s.libre = true;
    s.notify();
} } }

D'autres définitions de sémaphores sont possibles. Par exemple, pour V(s), on peut d'abord mettre le sémaphore à true, puis réveiller un des processus en attente sur s, s'il en existe un. Ainsi, le processus t effectuant V(s) peut continuer à s'effectuer, même si d'autres processus t1, t2, ...tn sont en attente sur s (c'est aussi le cas avec la première définition), mais maintenant t peut reprendre le sémaphore avant que le processus ti réveillé ne passe. On peut aussi définir des sémaphores FIFO tels que le premier processus en attente sur s soit le premier réveillé. En fait, ces différences n'interviennent pas dans les propriétés de sureté, mais n'affectent que la vivacité des algorithmes. Cela signifie que les exclusions mutuelles des sections critiques sont bien respectées, mais que la garantie de rentrer dans une section critique n'est pas toujours vraie, car cela peut dépendre de l'équité de la politique d'ordonnancement entre les divers processus.

Avec les sémaphores, on peut implémenter les conditions Posix avec les deux fonctions wait et notify de la manière suivante:
class ConditionPosix {
  Semaphore sem;
  Condition () { s = new Semaphore(false); }

  public void wait (Semaphore m) {
    Semaphore.V(m);
    Semaphore.P(sem);
    Semaphore.P(m);
  }

  public void notify () {
    Semaphore.V(sem);
  }
}
Toutefois, il est beaucoup plus difficile de définir notifyAll avec des sémaphores, puisqu'on doit alors faire intervenir l'ensemble des processus en attente sur le sémaphore.

On peut enfin généraliser légèrement la notion de sémaphore, en utilisant un compteur. Un sémaphore généralisé est une variable s entière positive, sur laquelle on fait deux opérations atomiques suivantes:
6.10 Producteur -- Consommateur

Les sémaphores sont des primitives de bas niveau. Toutefois, elles peuvent servir à programmer quelques exemples non triviaux, même si la bonne manière consiste presque toujours à utiliser des sections critiques en exclusion mutuelle avec des conditions. L'exemple type est celui du producteur -- consommateur. Un processus produit de l'information, et un autre la consomme. Le premier processus produit son résultat dans un medium (par exemple une file d'attente) dans lequel l'autre processus retire l'information. Comme déjà vu pour la file d'attente concurrente, il faut gérer les cas où l'on veut consommer dans un medium vide, et où l'on veut produire dans un medium plein. Supposons le medium infini, seul le cas vide importe. Alors la solution standard s'écrit de la manière suivante:
class FIFO {
  static final int N = 100000;
  int          debut, fin;
  int[]        contenu;
  Semaphore    s, s_occupees;

  FIFO (int n) {
    debut = fin = 0; contenu = new int[N];
    s_occupees = new Semaphore(0);
    s = new Semaphore(1);
  }

  void ajouter (int x) {
    SemaPhore>P¨s);
    contenu[fin++] = x;
    Semaphore.V(s);
    Semaphore.V(s_occupees);
  }

  int supprimer () {
    int res;
    Semaphore.P(s_occupees);
    Semaphore.P(s);
    res = contenu[debut++];
    Semaphore.V(s);
    return res;
  }
}

On peut aussi traiter le cas où la file est de longueur bornée avec un autre sémaphore généralisé comptant le nombre de cases vides dans la file d'attente. Les deux fonctions de manipulation de la file concurrente deviennent alors:
  FIFO (int n) {
    debut = fin = 0; contenu = new int[N];
    s_occupees = new Semaphore(0); s_libres = new Semaphore(N);
    s = new Semaphore(1);
  }

  void ajouter (int x) {
    Semaphore.P(s_libres);
    Semaphore.P(s);
    contenu[fin] = x;
    fin = (fin + 1) % N;
    Semaphore.V(s);
    Semaphore.V(s_occupees);
  }

  int supprimer () {
    int res;
    Semaphore.P(s_occupees);
    Semaphore.P(s);
    res = contenu[debut];
    debut = (debut + 1 ) % N;
    Semaphore.V(s);
    Semaphore.V(s_libres);
    return res;
  }

Exercice 43   Implanter les sémaphores généralisés en Java avec avec les verrous et conditions.

Exercice 44   Dans le langage Ada, la communication se fait par rendez-vous. Deux processus P et Q font un rendez-vous s'ils s'attendent mutuellement chacun à un point de son programme. On peut en profiter pour passer une valeur. Comment organiser cela en Java?

Exercice 45   Une barrière de synchronisation entre plusieurs processus est un endroit commun que tous les processus actifs doivent franchir simultanément. C'est donc une généralisation à n processus d'un rendez-vous. Comment la programmer en Java?

Exercice 46   Toute variable peut être partagée entre plusieurs processus, quel est le gros danger de la communication par variables partagées?

Exercice 47   Un ordonnanceur est juste s'il garantit à tout processus prêt de passer dans l'état exécution. Comment le construire?


Précédent Remonter Suivant