:tocdepth: 2

=================
 Synchronisation
=================

.. include:: common.rst.inc


Ressource critique
==================

Problématique
+++++++++++++

Lorsque deux tâches (processus ou `threads <parallelisme>`:doc:)
accèdent à une même zone mémoire,
elles peuvent interagir de manière indésirable,

* *même* si chaque tâche, prise indiduellement, se comporte correctement.

Concurence sans problème
------------------------

.. figure:: _static/resource_critique_1.png
   :width: 90%

Concurence problématique
------------------------

.. figure:: _static/resource_critique_2.png
   :width: 90%


.. index:: ressource critique, section critique, situation de compétition
   see: race condition; situation de compétition

Définitions
-----------

* Une ressource est dite **ressource critique** lorsque des accès concurrents à cette ressources peuvent résulter dans un état incohérent.

* On parle aussi de **situation de compétition** (*race condition*) pour décrire une situation dont l'issue dépend de l'ordre dans lequel les opérations sont effectuées.

* Une **section critique** est une section de programme manipulant une ressource critique.


.. index:: exclusion mutuelle, atomicité
   see: mutex; exclusion mutuelle

Exclusion mutuelle
++++++++++++++++++

* Une section de programme est dite **atomique** lorsqu'elle ne peut pas être interrompue par un autre processus manipulant les mêmes ressources critiques.

  → c'est donc une atomicité relative à la ressource

* Un mécanisme d'**exclusion mutuelle** sert à assurer l'atomicité des sections critiques relatives à une ressource critique.

  → en anglais : *mutual exclusion*, ou **mutex**


Mise en œuvre abstraite
-----------------------

.. code-block:: c

  int compte;                                   /* commun */
  void entrer_SC_compte();
  void sortir_SC_compte();

  printf("ajout de 1000€\n");                  /* tâche 1 */
  entrer_SC_compte();
  compte += 1000;
  sortir_SC_compte();
  printf("ajout effectué\n");

  printf("retrait de 500€\n");                 /* tâche 2 */
  entrer_SC_compte();
  compte -= 500;
  sortir_SC_compte();
  printf("retrait effectué\n");


Mutex: Critères d'évaluation
----------------------------

* **Exclusion** : deux tâches ne doivent pas se trouver en même temps en SC

* **Progression** : une tâche doit pouvoir entrer en SC si aucune autre ne s'y trouve

* **Équité** : une tâche ne devrait pas attendre indéfiniment pour entrer SC

* L'exclusion mutuelle doit fonctionner dans un contexte **multi-cœurs**


.. index:: attente active

Mauvaise solution : attente active
----------------------------------

On utilise un booléen partagé comme « verrou »

.. code-block:: c

  int verrou = 0;

  void entrer_SC() { while (verrou) {}
                     verrou = 1; }

  void sortir_SC() {  verrou = 0; }

Défauts de l'attente active
---------------------------

* Le processus qui attent consomme du temps processeur (d'où le nom d'attente *active*).

  → NB: on peut améliorer cela en mettant un ``sleep`` ou un ``yield`` dans la boucle.

* Cette approche n'assure par l'exclusion!

  → *verrou* est *lui même* une ressource critique.


Bonne solution
--------------

* On associe à la ressource un jeton, que les processus peuvent prendre et reposer

* Seul le processus possédant le jeton devrait manipuler la ressource

* Donc, si un processus souhaite manipuler la ressource et que le jeton est pris, il doit d'abord attendre que le jeton redevienne disponible

* Utilisation d'un `sémaphore <sémaphore>`:ref: initialisé à 1


Mise en œuvre concrète
----------------------

.. code-block:: c

  int compte;                                   /* commun */
  sem_t mutex_compte;
  status = sem_init(&mutex_compte, 1, 1);

  printf("ajout de 1000€\n");                  /* tâche 1 */
  status = sem_wait(&mutex_compte);
  compte += 1000;
  status = sem_post(&mutex_compte);
  printf("ajout effectué\n");

  printf("retrait de 500€\n");                 /* tâche 2 */
  status = sem_wait(&mutex_compte);
  compte -= 500;
  status = sem_post(&mutex_compte);
  printf("retrait effectué\n");


Remarques
---------

* Certaines opérations sur la ressource critiques ne nécessitent pas forcément d'exclusion mutuelle.

  → exemple : lecture de la valeur du compte (si on accepte que la valeur lue devienne rapidement invalide...)

* Le mécanisme d'exclusion mutuelle n'est *pas* une protection, mais une **convention** entre les processus souhaitant utiliser la ressource sans la corrompre.

  → il est toujours possible de manipuler la ressource sans « prendre le jeton »

Remarques (2)
`````````````

Les sections critiques sont un **mal nécessaire**:

* un mal, parce qu'elles empêches le parallélisme qu'on a eu tant de mal à mettre en place... elles réduisent donc les performances.

* nécessaire, parce qu'elles garantissent l'intégrité des ressources critiques

Conséquence :

* les éviter lorsqu'on le peut (e.g. en concevant des structures de données toujours cohérentes)


Remarques (3)
-------------

* sinon, les réduire au strict minimum

.. code-block:: c

  /* n'écrivez PAS --------------------------------- */
  status = sem_wait(&mutex_compte);
  printf("ajout de 1000€\n");
  compte += 1000;
  printf("ajout effectué\n");
  status = sem_post(&mutex_compte);

  /* mais écrivez ---------------------------------- */
  printf("retrait de 500€\n");
  status = sem_wait(&mutex_compte);
  compte -= 500;
  status = sem_post(&mutex_compte);
  printf("retrait effectué\n");

.. index:: inter-blocage
   see: deadlock; inter-blocage

.. _inter-blocage:

Inter-blocage
+++++++++++++

Un **inter-blocage** (*deadlock*) est une situation où
plusieurs tâches sont bloquées car chacune attend
un événement que doit produite une autre.

Un exemple classique se produit lorsque deux tâche attendent chacune un « jeton » détenu par l'autre :

.. code-block:: c

  /* tâche 1 */                    /* tâche 2 */
  sem_wait(&mutex_A);              sem_wait(&mutex_B);
  utilise(A);                      utilise(B);
  sem_wait(&mutex_B);              sem_wait(&mutex_A);
  utilise(A, B);                   utilise(A, B);
  /* ... */                        /* ... */

Solution possible
-----------------

Une manière d'éviter les inter-blocages consiste à toujours réclamer les ressources dans le même ordre (quitte à libérer une ressource avant de la réclamer à nouveau).

.. code-block:: c

  /* tâche 1 */                    /* tâche 2 */
  sem_wait(&mutex_A);              sem_wait(&mutex_B);
  utilise(A);                      utilise(B);
  sem_wait(&mutex_B);              sem_post(&mutex_B);
  utilise(A, B);                   sem_wait(&mutex_A); 
  /* ... */                        sem_wait(&mutex_B);
                                   utilise(A, B);
                                   /* ... */


Problèmes typiques de synchronisation
=====================================

.. contents::
   :local:
   :depth: 0
   :backlinks: none

Pas une liste exhaustive, mais une source d'inspiration.


.. index:: producteurs / consommateurs

Producteurs/consommateurs
+++++++++++++++++++++++++

* Un ensemble de processus, divisé en deux catégories, partage une zone mémoire.

* Les premiers (producteurs) remplissent la mémoire partagée, avec des éléments.

  → la mémoire ne peut contenir qu'un nombre d'éléments limité et connu à l'avance

* Les seconds (consommateurs) utilisent ces éléments et les retirent de la mémoire.

* Exemple : file d'impression

Exemple
-------

.. container:: build animation stacked

    .. figure:: _static/prod-cons_1.png
       :width: 50%

    .. figure:: _static/prod-cons_2.png
       :width: 50%

    .. figure:: _static/prod-cons_3.png
       :width: 50%

    .. figure:: _static/prod-cons_4.png
       :width: 50%

    .. figure:: _static/prod-cons_5.png
       :width: 50%

    .. figure:: _static/prod-cons_6.png
       :width: 50%

    .. figure:: _static/prod-cons_7.png
       :width: 50%


Problème
--------

* Un producteur doit se bloquer lorsque la mémoire partagée est pleine

* Un consommateur doit se bloquer lorsque la mémoire partagée est vide

Principe de solution
--------------------

* Utilisation de deux sémaphores, implémentant les deux critères de blocage

  * l'un représente le nombre de cases libres
  * l'autre représente le nombre de cases occupées

* Analogie : deux piles de jetons, avec une quantité de jetons constante

  * les jetons passent d'une pile dans une autre lorsqu'une case change d'état

Principe de solution (2)
````````````````````````

* Si les opérations sur la zone mémoire partagée ne sont pas atomiques, il faut les protéger par une section critique

  → troisième sémaphore


Algorithme
----------

.. rst-class:: columns
.. list-table::

  * -
     .. code-block:: c

      elt_t tab[N]
      sem_t libres, occupes, mutex;
      sem_init(&libres,  1, N);
      sem_init(&occupes, 1, 0);
      sem_init(&mutex,   1, 1);

      void producteur() {
        elt_t e = produire();
        sem_wait(&libres);
          sem_wait(&mutex);
            ajouter(e, tab);
          sem_post(&mutex);
        sem_post(&occupes);
      }

    -
     .. code-block:: c

      void consommateur() {
        sem_wait(&occupes);
          sem_wait(&mutex);
            elt_t e = retirer(tab);
          sem_post(&mutex);
        sem_post(&libres);
        consommer(e);
      }



Remarques
---------

* « Passage » de jetons entre ``libres`` et ``occupes``
* Ordre emboitement correct des sémaphores (inter-blocage)
* Opérations de production/consommation hors de la section critique (paralélisme, cf. section précédente)...
* ...mais également sans posséder de jeton ``libres``/``occupes``.


.. index:: lecteurs / rédacteurs

Lecteurs/rédacteurs
+++++++++++++++++++

* Un ensemble de processus, divisé en deux catégories, partage une zone mémoire.

* Certains processus (les lecteurs) font des accès en lecture seule à cette zone.

* D'autres processus (les rédacteurs) modifient le contenu de cette zone.

  NB : on parle parfois d'écrivains plutôt que de rédacteurs

Problème
--------

* Lorsqu'un rédacteur accède à la mémoire partagée, aucune autre processus (qu'il soit lecteur ou rédacteur) ne doit y avoir accès.

  → problème d'exclusion mutuelle classique

* En revanche, les lecteurs peuvent être plusieurs à utiliser la zone en même temps, cela ne pose pas de problème.

Principe de solution
--------------------

* On protège la mémoire partagée par une exclusion mutuelle, mais...

* les lecteurs n'ont besoin de cette exclusion mutuelle **que si** aucun autre lecteur n'utilise la mémoire ;

* pour le vérifier, ils utilisent un compteur (nombre de lecteurs en train d'utiliser la zone), lui aussi protégé par une exclusion mutuelle.


Algorithme
----------

.. rst-class:: columns
.. list-table::

  * -
     .. code-block:: c

      int c = 0;                 //
      sem_t mutex_m, mutex_c;      
      sem_init(&mutex_m,  1, 1);   
      sem_init(&mutex_c,  1, 1);   



      void redacteur() {           
        sem_wait(&mutex_m);        
          ecrire(e, tab);          
        sem_post(&mutex_m);        
      }                            

    -
     .. code-block:: c

      void lecteur() {              //
        sem_wait(&mutex_c);    
          if (c == 0)          
            sem_wait(&mutex_m);
          c += 1;              
        sem_post(&mutex_c);    

          lire();              

        sem_wait(&mutex_c);    
          if (c == 1)          
            sem_post(&mutex_m);
         c -= 1;               
        sem_post(&mutex_c);    
      }                        



Remarques
---------

* Le lecteur qui prend le jeton de mutex_m n'est pas forcément celui qui le rend

* On note que les lecteurs peuvent parfois se bloquer dans la section critique du compteur c.

  → Cela peut-il créer un :ref:`inter-blocage <inter-blocage>` ?

* L'algorithme proposé fonctionne, mais n'assure pas l'équité : un rédacteur peut attendre indéfiniment avant d'avoir accès à la mémoire (:ref:`famine <famine>`)

  → Comment le modifier pour assurer l'équité ?


.. index:: philosophes

Philosophes
+++++++++++

.. figure:: _static/philosophers.png
   :figclass: float-right
   :figwidth: 50%
   :width: 100%
      
   Illustration : `© Benjamin Esham`__


Problème proposé par Dijkstra_.
    
Cinq philosophes passent leur vie à penser et manger autour d'une table.

Pour manger, ils ont besoin de deux fourchettes, mais il n'y a que cinq fourchettes.


__ http://en.wikipedia.org/wiki/Image:Dining_philosophers.png

.. _Dijkstra: http://fr.wikipedia.org/wiki/Edsger_Dijkstra


Problème
--------

* Proposer un algorithme qui évite :

  * les :ref:`inter-blocages <inter-blocage>`
  * la :ref:`famine <famine>`

* Mauvaise solution :

  chaque philosophe, lorsqu'il a faim, prend la fourchette de gauche, puis celle de droite, mange, puis les repose

Principe de solution
--------------------

* Chaque philosophe a trois états :

  « je pense », « j'ai faim », « je mange »

  par lesquels il passe toujours dans cet ordre

* Lorsqu'il a faim, un philosophe ne peut manger que si ses deux voisins ne mangent pas, sinon attend

* Lorsqu'il termine de manger, le philosophe réveille ses voisins et se remet à penser


Algorithme
----------

.. rst-class:: columns
.. list-table::

  * -
     .. code-block:: c

      sem_t mutex;     // init à 1
      sem_t reveils[N];// init à 0
      int etats[n];    // init à PENSE

      void CommenceManger(int id) {
        sem_wait(mutex);
        etats[id] = FAIM;
        bool ok = etat[id-1] != MANGE
               && etat[id+1] != MANGE;
        if (ok) {
          etat[id] = MANGE;
          sem_post(mutex);
        } else {
          sem_post(mutex);
          sem_wait(reveils[id]);
        }
      }


    -
     .. code-block:: c

      void FinitManger(int id) {
        sem_wait(mutex);
        etats[id] = PENSE;
        /* voisin gauche */
        if (etat[id-1] == FAIM
        &&  etat[id-2] != MANGE) {
          etat[id-1] = MANGE;
          sem_post(reveils[id-1]);
        }
        /* voisin droit */
        if (etat[id+1] == FAIM
        &&  etat[id+2] != MANGE) {
          etat[id+1] = MANGE;
          sem_post(reveils[id+1]);
        }
        sem_post(mutex);
      }




Remarques
---------

* L'algorithme proposé prévient les :ref:`inter-blocages <inter-blocage>`,
  mais pas la :ref:`famine <famine>`.

* Pour l'améliorer,
  une solution consiste à ne réveiller un voisin que si
  son autre voisin (id±2) n'est pas dans l'état FAIM
  depuis trop longtemps / depuis plus longtemps que lui
  

Mutex internes au système
=========================

Motivation
++++++++++

* Le système d'exploitation lui même peut avoir besoin d'exclusion mutuelle, pour toutes ses structures de données...

* ... et notamment pour les sémaphores eux-mêmes !

  → on ne peut pas utiliser de sémaphore pour implémenter un sémaphore...


Problème
++++++++

Les procédures `sem_wait` et `sem_post` sont des sections critiques pour le sémaphore lui même...

.. parsed-literal::

  **proc** sem_wait(sem):                                         .
    **si** *sem.c* = 0 **alors**
      bloquer le processus courant
    **finsi**
    *sem.c* ← *sem.c* - 1

  **proc** sem_post(sem)
    *sem.c* ← *sem.c* + 1
    **si** des processus sont bloqués
      en attente du sémaphore
    **alors**
      débloquer un des processus
    **finsi**



Sections critiques dans un sémaphore
------------------------------------

.. role:: red

.. raw:: html

  <style type="text/css">
    .red { color: red }
  </style>

.. rst-class:: columns
.. list-table::

  * -
      .. parsed-literal::

       **proc** sem_wait(sem):
         :red:`entrer_SC()`
         **si** *sem.c* = 0 **alors**
           :red:`sortir_SC()`
           bloquer le processus courant
         **sinon**
           *sem.c* ← *sem.c* - 1
           :red:`sortir_SC()`
         **finsi**

    -
      .. parsed-literal::

       **proc** sem_post(sem):
         :red:`entrer_SC()`
         *sem.c* ← *sem.c* + 1
         **si** des processus sont bloqués
           en attente du sémaphore
         **alors**
           débloquer un des processus
           sem.c ← sem.c - 1
        **finsi**
        :red:`sortir_SC()`



.. index:: attente active

Exclusion mutuelle de bas niveau
++++++++++++++++++++++++++++++++

* On utilise l'instruction *test_and_set* du langage machine: elle consulte *et* modifie une variable de manière atomique:

  * si la variable vaut 1, elle retourne 1
  * si la variable vaut 0, elle la met à 1 et retourne 0

* Cela permet d'écrire une attente active qui assure l'exclusion:

  .. code-block:: c

     void entrer_SC() {
        while (test_and_set(&verrou)) {}
     }

Autres solutions
----------------

* Il existe des solutions purement logicielles (i.e. qui ne
  nécessitent pas l'existence d'instruction atomique pour
  tester et modifier une variable)

  * `algorithme de Peterson`__
  * `algorithme de la Boulangerie`__

__ http://fr.wikipedia.org/wiki/Algorithme_de_Peterson
__ http://fr.wikipedia.org/wiki/Algorithme_de_la_boulangerie

* Mécanismes plus complexe qu'un simple verrou, pour
  ne rien avoir à faire *après* l'attente active

  * tableau de verrous
  * notion de tour


Conclusion
==========

À retenir
+++++++++

* Les signaux et les sémaphores permettent la synchronisation de processus.

* Problèmes typiques de synchronisation :

  * exclusion mutuelle,
  * problèmes plus complexes.

* À un plus bas niveau, on doit avoir recours à l'attente active :

  * implémentation des sémaphores,
  * mais aussi certains périphériques ne gérant pas les interruptions...