ynchronizedaitotifyotifyAllfsystemutrintrintln
Planche 1

Inf 431 -- Cours 11
Synchronisation par
mémoire partagée


http://jeanjacqueslevy.net
secrétariat de l'enseignement:
Catherine Bensoussan
cb@lix.polytechnique.fr
Aile 00, LIX,
01 69 33 34 67
http://www.enseignement.polytechnique.fr/informatique/IF

Planche 2

Plan

  1. Rappels
  2. Conditions et moniteurs
  3. Etats d'un processus
  4. Ordonnancement
  5. Les lecteurs et les écrivains
  6. Implémentation de la synchronisation
Bibliographie

Greg Nelson, Systems Programming with Modula-3, Prentice Hall, 1991.

Mordechai Ben-Ari, Principles of Concurrent Programming, Prentice Hall, 1982.

Fred B. Schneider, On Concurrent Programming, Springer, 1997.

Jean Bacon, Concurrent Systems, Addison-Wesley, 1998.

S.J. Leffler, M.K. McKusick, M.J. Karels, J.S. Quartermann, The Design and Implementation of the 4.3 BSD Unix Operating System, Addison Wesley 1989.
Planche 3

Rappels

Planche 4

Conditions et moniteurs (1/7)

Planche 5

Conditions et moniteurs (2/7)

Planche 6

Conditions et moniteurs (3/7)

Planche 7

Conditions et moniteurs (4/7)

Planche 8

Conditions et moniteurs (5/7)

Planche 9

Conditions et moniteurs (6/7)

Planche 10

Conditions et moniteurs (7/7)


class FIFO {
  int debut, fin; boolean pleine, vide; int[ ] contenu;
  ...
  synchronized void ajouter (int x) throws InterruptedException {
    while (pleine)
      wait();
    contenu[fin] = x;
    fin = (fin + 1) % contenu.length;
    vide = false; pleine = fin == debut;
    notifyAll();
  }

  synchronized int supprimer () throws InterruptedException {
    while (vide)
      wait();
    int res = contenu[debut];
    debut =  (debut + 1) % contenu.length;
    vide = fin == debut; pleine = false;
    notifyAll();
    return res;
} } Exécution

Planche 11

Etats d'un processus (1/3)


Planche 12

Etats d'un processus (2/3)

Planche 13

Etats d'un processus (3/3)

Planche 14

Ordonnancement (1/2)

Planche 15

Ordonnancement (2/2)

Planche 16

Synchronisation et priorités

Planche 17

Les lecteurs et les écrivains (1/6)

Une ressource partagée est lue ou modifiée concurremment. En lecture, la ressource n'est pas modifiée.
Planche 18

Les lecteurs et les écrivains (2/6)

En lecture, on a nLecteurs simultanés (nLecteurs > 0).

En écriture, on a nLecteurs = -1.
synchronized void accesPartage() {
  while (nLecteurs == -1)
    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();
}

Planche 19

Les lecteurs et les écrivains (3/6)

notifyAll réveille trop de processus se retrouvant immédiatement bloqués. Avec des variables de condition Posix cLecture et cEcriture, on a un contrôle plus fin:
synchronized void accesPartage() {
  ++ nLecteursEnAttente;
  while (nLecteurs == -1)
    waitPosix(cLecture);
  -- nLecteursEnAttente;
  ++ nLecteurs;
}

synchronized void retourPartage() {
  -- nLecteurs;
  if (nLecteurs == 0)
    notifyPosix(cEcriture);
}
synchronized void accesExclusif() {
  while (nLecteurs != 0)
    waitPosix(cEcriture);
  nLecteurs = -1;
}

synchronized void retourExclusif() {
  nLecteurs = 0;
  if (nLecteursEnAttente > 0)
    notifyAllPosix(cLecture);
  else
    notifyPosix(cEcriture);
}

Les conditions Posix n'existent pas en Java !!
Elles existent en C, C++, Ocaml, Modula-3, ADA, etc


Planche 20

Les lecteurs et les écrivains (4/6)

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 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 relâché.

Il vaut mieux faire notify à l'extérieur de la section critique (Ce qu'on ne fait jamais !), ou au moment de la sortie du
synchronized:
void retourPartage() {
  boolean faireNotify;
  synchronized (this) {
    -- nLecteurs;
    faireNotify = nLecteurs == 0;
  }
  if (faireNotify)
    notifyPosix(cEcriture);
}

Planche 21

Les lecteurs et les écrivains (5/6)

Des blocages inutiles sont possibles (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 (nLecteurs == -1)
      waitPosix(cLecture);
    -- nLecteursEnAttente;
    ++ nLecteurs;
  }
  notifyPosix(cLecture);
}
synchronized void retourExclusif() {
  nLecteurs = 0;
  if (nLecteursEnAttente > 0)
    notifyPosix(cLecture);
  else
    notifyPosix(cEcriture);
}



Planche 22

Les lecteurs et les écrivains (6/6)

Famine possible d'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 (this) {
    ++ nLecteursEnAttente;
    if (nEcrivainsEnAttente > 0)
      waitPosix(cLecture);
    while (nLecteurs == -1)
      waitPosix(cLecture);
    -- nLecteursEnAttente;
    ++ nLecteurs;
  }
  notifyPosix(cLecture);
}
synchronized void accesExclusif() {
  ++ nEcrivainsEnAttente;
  while (nLecteurs != 0)
    waitPosix(cEcriture);
  -- nEcrivainsEnAttente;
  nLecteurs = -1;
}





Contrôler finement la synchronisation peut être complexe.


Planche 23

Exclusion mutuelle: implémentation (1/4)

Planche 24

Exclusion mutuelle: implémentation (2/4)

Planche 25

Exclusion mutuelle: implémentation (3/4)

Planche 26

Exclusion mutuelle: implémentation (4/4)

Planche 27

Algorithme de Peterson (1/5)


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
      actif[i] = false;
  } }

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

Planche 28

Algorithme de Peterson (2/5)

Preuve de sureté. (safety)

Si t
0 et t1 sont tous les deux dans leur section critique. Alors actif[0] = actif[1] = true.

Impossible car les deux tests auraient été franchis en même temps alors que tour favorise l'un deux. Donc un seul est entré. Disons t
0.

Cela veut dire que t
1 n'a pu trouver le tour à 1 et n'est pas entré en section critique.

Preuve de vivacité. (lifeness)

Supposons t
0 bloqué dans le while.

Cas 1: t
1 non intéressé à rentrer dans la section critique. Alors actif[1] = false. Et donc t0 ne peut être bloqué par le while.

Cas 2: t
1 est aussi bloqué dans le while. Impossible car selon la valeur de tour, l'un de t0 ou t1 ne peut rester dans le while.

Planche 29

Algorithme de Peterson (3/5)

Planche 30

Algorithme de Peterson (4/5)

Preuve de sureté:
Planche 31

Algorithme de Peterson (5/5)

Preuve de vivacité.
Planche 32

Exercices

Exercice 1 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 2 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 3 Toute variable peut être partagée entre plusieurs processus, quel est le gros danger de la communication par variables partagées?

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

Exercice 5 (difficile) Généraliser l'algorithme de Peterson au cas de n processus (n ³ 2).





This document was translated from LATEX by HEVEA.