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

Rappels

• un processus t (Thread) est un programme qui s'exécute;
  
  
• t.start lance l'exécution concurrente de la méthode t.run de t;
  
  
• t.interrupt signale qu'on demande l'interruption de t;
  
  
• isInterrupted teste si un signal d'interruption est arrivé;
  
  
• InterruptedException est levée quand t est en attente (et ne peut pas tester isInterrupted;
  
  
• les méthodes synchronized d'un même objet s'exécutent en exclusion mutuelle;
  
  
• wait, notify, notifyAll permettent la gestion concurrente de données.

Conditions et moniteurs (1/7)

• Paradigme de la concurrence º la file d'attente concurrente.
  
  
• Pour simplifier, supposons la file f de longueur t.q. £ 1.
  
  
• ajouter et supprimer s'exécutent de manière concurrente.
  
    static synchronized void ajouter (int x, FIFO f) {
      if (f.pleine)
        // Attendre que la file se vide
      f.contenu = x;
      f.pleine = true;
    }
    
    static synchronized int supprimer (FIFO f) {
      if (!f.pleine)
        // Attendre que la file devienne pleine
      f.pleine = false;
      return f.contenu;
    }

Conditions et moniteurs (2/7)

• ajouter attend que la file f se vide, si f est pleine.
  
  
• supprimer attend que la file f se remplisse, si f est vide
  
  
• il faut relâcher le verrou pour que l'autre puisse s'exécuter.
  
  
• 2 solutions:
  • ·ressortir de chaque méthode sans se bloquer et revenir tester la file Þ attente active (busy wait) qui coûte cher en temps.
    
    
  • ·atomiquement relâcher le verrou + attendre sur une condition.
    Quand la condition est notifiée, on repart en reprenant le verrou.
  
  
  
• en Java, une condition est une simple référence à un objet (son adresse). Par exemple, ici la file elle-même f.
  
  
• quand on remplit la file, on envoie un signal sur une condition et réveiller un processus en attente sur la condition.

Conditions et moniteurs (3/7)

• wait et notify sont deux méthodes de la classe Object. Tous les objets ont ces deux méthodes.
  
  static void ajouter (int x, FIFO f) throws InterruptedException {
    synchronized (f) {
      while (f.pleine)
        f.wait();
      f.contenu = x;
      f.pleine = true;
      f.notify();
  } }
  
  static int supprimer (FIFO f) throws InterruptedException {
    synchronized (f) {
      while (!f.pleine)
        f.wait();
      f.pleine = false;
      f.notify();
      return f.contenu;
  } } Exécution

Conditions et moniteurs (4/7)

• Même programme en programmation par objets.
  
  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;
  } Exécution

Conditions et moniteurs (5/7)

• si plus de deux processus sont en jeu, notifyAll réveille tous les processus en attente sur la condition.
  
  synchronized void ajouter (int x) throws InterruptedException {
      while (pleine)
        wait();
      contenu = x;
      pleine = true;
      notifyAll();
  }
  
  synchronized int supprimer () throws InterruptedException {
      while (!pleine)
        wait();
      pleine = false;
      notifyAll();
      return contenu;
  } Exécution

Conditions et moniteurs (6/7)

• notify n'a pas de mémoire. On réveille un quelconque des processus en attente sur la condition.
  
  
• l'action relâchant le verrou et de mise en attente engendrée par wait est atomique. Sinon, on peut perdre un signal émis par notify avant d'attendre sur la condition.
  
  
• de même notify est fait avant de relâcher le verrou.
  
  
• il faut utiliser un while et non un if dans la section critique, car un autre processus peut être réveillé et invalider le test.

Conditions et moniteurs (7/7)

Etats d'un processus (1/3)

• État prêt: un processus peut s'exécuter.
  
  
• État exécution: un processus qui s'exécute (currentThread).
  
  
• État bloqué: on attend sur une condition.
  
  
• Un signal émis sur une condition peut réveiller le processus et le faire passer dans l'état prêt.

Etats d'un processus (2/3)

• Il peut y avoir plus de processus prêts que de processeurs.
  
  
• Les processus prêts forment un ensemble, souvent géré comme une FIFO ou une file de priorités (runQ)
  
  
• Le système (la JVM) en choisit un pour l'exécution. Lequel?
  
  
• C'est le problème de l'ordonnancement des processus (scheduling).
  
  
• ·Systèmes préemptifs peuvent arrêter un processus en cours d'exécution et le mettre dans l'état prêt.
  
  
• ·Systèmes non préemptifs attendent qu'un processus relâche le processeur (par |Thread.yield()|).  \itemBDansles systèmes non préemptifs, les processus fonctionnent en coroutines.

Etats d'un processus (3/3)

• création ® prêt: |start()|
  
  
• prêt ® exécution: ordonnanceur (scheduler)
  
  
• exécution ® prêt: |Thread.yield()|ou fin d'un quantum de temps (pour systèmes préemptifs)
  
  
• exécution ® bloqué: |wait()|,début de synchronized
  
  
• bloqué ® prêt: réveil sur |notify()|ou |notifyAll()|,fin de synchronized
  
  
• exécution ® mort: fin de |run()|

Ordonnancement (1/2)

• Priorités statiques. Les méthodes getPriority. et setPriority donnent les valeurs de la priorité d'un processus.
  
  
• Les priorités suivantes MIN_PRIORITY, NORM_PRIORITY, MAX_PRIORITY sont prédéfinies.
  
  
• En fait, l'ordonnanceur peut aussi affecter des priorités dynamiques pour avoir une 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é.
  
  
• L'important est d'écrire du code portable Þ 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.

Ordonnancement (2/2)

• priorité sur l'age. Au début, p=p₀ est la priorité statique donnée au processus. Si un processus prêt attend le processeur pendant k secondes, on incrémente p. Quand il s'exécute, on fait p = p₀.
  
  
• priorité décroit si on utilise beaucoup de processeur (Unix 4.3BSD). Au début p = PUSER + 2 p_nice est la priorité initiale statique.
  Tous les 40ms, la priorité est recalculée par:

  p = PUSER +

  é ê ê ê

  pcpu 4

  ù ú ú ú

  + 2  pnice

  Tous les 10 ms, p_cpu est incrémenté quand le processus s'exécute.
  Toutes les secondes, p_cpu est aussi modifié par le filtre suivant:

  pcpu =

  2 load 2 load + 1

  pcpu + pnice

  qui fait baisser sa valeur en fonction de la charge globale du système load (nombre moyen de processus prêts sur la dernière minute).
  
  Pour Unix, la priorité croit dans l'ordre inverse de sa valeur (0 est fort, 127 est bas).

Synchronisation et priorités

• Avec les verrous pour l'exclusion mutuelle, une inversion de priorités est possible.
  
  
• 3 processus P_b, P_m, P_h s'exécutent en priorité basse, moyenne, et haute.
  
  
• P_b prend un verrou qui bloque P_h.
  
  
• P_m s'exécute et empêche P_b (de priorité plus faible) de s'exécuter.
  
  
• le verrou n'est pas relâché et un processus de faible priorité P_m peut empêcher le processus P_h de s'exécuter.
  
  
• on peut s'en sortir en affectant des priorités sur les verrous en notant le processus de plus haute priorité attendant sur ce verrou. Alors on fait monter la priorité d'un processus ayant pris ce verrou (Win 2000).
  
  
• tout cela est dangereux.