Synchronisation

Lorsque plusieurs processus coopèrent, ils doivent souvent intéragir entre eux, ils doivent parfois attendre qu'une opération soit effectuée par un autre processus pour travailler.

Il faut donc avoir des mécanismes qui permettent d'envoyer des événements aux processus (un processus doit pouvoir attendre l'évènement).

Types de synchronisation

Sous UNIX, les mécanismes suivants sont mis en oeuvre pour la synchronisation :

Les signaux
Les sémaphores

On parlera de point de synchronisation lorsqu'un processus attend un autre.

Les signaux

Un signal est un événement capturé par un processus, c'est aussi un mécanisme simple utilisé par le système d'exploitation pour signaler aux processus une erreur (SIGILL, SIGFPE, SIGUSR1, SIGUSR2, etc).

Exemple

Voici par exemple un programme dont la fonction sighandler est appellée lorsque le signal SIGUSR1 est déclenché :

#include <stdio.h>
#include <signal.h>
#include <unistd.h>
#include <stdlib.h>

void sighandler(int signum);

/*
  Ce programme va lier la fonction sighandler au signal SIGUSR1
  Ce qui signifie que lorsque l'on lance le programme (qui contient une boucle infinie), lorsque l'on lance le signal via "pkill -SIGUSR1 a.out" (par exemple)
  La fonction sighandler va être appellée et "SIGUSR1 reçu" va donc s'afficher à l'écran.
*/
int main(void) {
  /* Si on remplace ici SIGUSR1 par SIGINT et que l'on fait CTRL+C, on va appeller la commande sighandler */
  if(signal(SIGUSR1, sighandler) == SIG_ERR) {
    printf("Erreur sur la gestion du signal\n");
    exit(-1);
  }

  while(1) {
    sleep(1);
    printf("Hello\n");
  }

  return EXIT_SUCCESS;
}

void sighandler(int signum) {
  printf("SIGUSR1 reçu\n");
}

Opérations

Il existe plusieurs opérations différentes sur les signaux :

signal et sigset qui lient un signal à une fonction. signal la lie une seule fois, tandis que sigset la lie continuellement.
alarm déclenche le signal SIGALARM au processus courrant.
pause suspend le processus jusqu'a la réception d'un signal
kill envoie un certain signal au processus dont le PID est donné.

Les sémaphores

Un sémaphore est une variable entière en mémoire qui excepté pour son initialisation est accédée uniquement au moyen de fonction atomiques (ne pouvant pas être décomposée) p() et v().

La fonction p(sem) va vérifier que la valeur est plus grande que zero, si c'est le cas, la variable est décrementée et l'exécution continue, si ce n'est pas le cas, alors il attend que ce soit le cas.

La fonction v(sem) va simplement incrémenter la variable de 1, et va ainsi réveiller tous les processus qui attendrait ce sémaphore.

Ces foncitons ne sont pas présente dans C de base il faut importer les fichiers semadd.h et semadd.c depuis l'espace de cours.

Exemple

Voici un exemple d'un programme qui communique avec un processus fils via 2 sémaphores. Il est intéressant de noter que généralement un processus ne va faire qu'une seule opération par sémaphore (par exemple que des p() sur sem1 et que des v() sur sem2 ou inversément)

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include "semadd.h"

#define SEM1 12345
#define SEM2 23456

/*
  Ce programme va créer 2 sémaphores et 2 processus (un père et un fils).
  Le fils et le père vont tous les deux exécuter une boucle sauf qu'a chaque itération ils vont s'attendre l'un l'autre.
  Ainsi le père attends le sémaphore du fils (sem2) qui est émit lorsque le fils a fini son itération
  De même le fils va ensuite attendre le sémaphore du père (sem1) qui est émit lorsque le père a fini son itération

  Si on exécute ipcs -s lors de l'exécution du programme, on peut voir la liste des sémaphores créés.

  Contrairement aux signaux, on peut créer nos propres sémaphores tandis que les signaux eux sont défini par le système d'exploitation.
*/
int main(void) {
  int sem1, sem2, i;

  /* Création des sémaphores */
  sem1=sem_transf(SEM1);
  sem2=sem_transf(SEM2);

  /* Création des deux processus */
  switch(fork()) {
    case -1:
      printf("Erreur fork()\n");
      exit(-1);

    /* Boucle du fils */
    case 0:
      printf("Je suis le fils %d\n", getpid());
      for(i=0;i<5;++i) {
        printf("[FILS] Valeur de i : %d\n",i);
        sleep(5);
        v(sem2); /* Envois du sémaphore (2) au père */
        p(sem1); /* Attente du sémaphore (1) du père */
      }

    /* Boucle du père */
    default:
      for(i=0;i<5;++i) {
        p(sem2); /* Attente du sémaphore (2) du fils */
        printf("[PERE] Je suis le père\n");
        sleep(5);
        v(sem1); /* Envois du sémaphore (1) au fils */
      }
  }

  return EXIT_SUCCESS;
}

Semget - Allocation de sémaphores

L'allocation se fait via int semget(int key, int nb, int flag), où

La valeur retournée est un descripteur "semid"
La clé est la valuer qui identifie le sémaphore
Les flags définissent les permissions, comme pour les mémoires partagées IPC_CREAT permet de demander la création des sémaphores

On peut aussi simplifier l'allocation à partir d'une clé en utilisant int sem_transf(int key), cette fonction n'est pas officielle mais le fichier est disponible sur HELMo Learn.

Semctl - Gestion de sémaphores

On peut gérer les sémaphores (nottament pour libérer la mémoire) en utilisant int semctl(int semid, int semnum, int cmd, union semun attr) où

semid est le descripteur du sémaphore
semnum identifie le sémaphore (généralement c'est 0 si il n'y en a qu'un)
cmd identifie la commande (IPC_SET, GETVAL, SETVAL, IPC_RMID ou IPC_STAT).
union semun attr est une "union" (un type de structure où chaqun des éléments partagent la même zone mémoire, ainsi ce ne peut être qu'un seul élément à la fois, un peu comme une enum en Rust). Il faut généralement définir cette structure soi-même en revanche.

Semop - Faire les opérations sur les sémaphores

int semop(int semid, struct sembuf* sops, unsigned nsops) est la fonction qui est derrière les fonctions p() et v().

semid est le descripteur du sémaphore
sops est un tableau de structures semfus (contenant l'opération)
nsops est le nombre d'éléménts du tableau sops

Section critique

C'est bien beau la synchronisation sauf que la coopération entre plusieurs processus pose également des problème si deux processus concurrents souhaite modifier les même données au même moment.

Définition section critique

On peut donc mettre en place une section critique, c'est un ensemble d'instructions qui devraient être exécutées du début à la fin sans interruption.

Une section critique est indispensable lorsque l'on traite des données partagée afin qu'elle soit protégée et que ces données partagées ne deviennent pas incohérente.

Par exemple, si on fait par exemple une liste chainée, elle risque de ne plus être cohérente après plusieurs modifications.

On ne peut cependant pas empêcher la concurrence entre les processus. Pour cela on va mettre en place des protections avant toute modification pour s'assurer qu'un autre processus n'est pas déjà en train de modifier la zone partagée.

Variable partagée

Celle ci consiste à partager une variable entre plusieurs processus, qui est initiallement définie à 0. Avant d'entrer dans le processus, on boucle sur la valeur de cette variable.

Si la variable est différente de 0 on boucle (et on attends). Ensuite on place la variable à 1 avant de commencer la section critique puis on la remet à 0 une fois que cela est fini.

while (i != 0);
i = 1;
/* Section critique ici */
i = 0;

Problème

Un gros problème peut survenir si un processus reviens dans l'état ready (par exemple avec la fin de son quantum de temps) entre l'instruction while et l'instruction de i = 1.

Ainsi l'autre processus peut lui aussi entrer en section critique et peut lui aussi avoir son quantum de temps qui expire durant celui ci.

Ainsi on peut donc arriver dans une situation ou plusieurs processus sont dans une section critique en même temps (ce qui est justement la chose à éviter).

Ainsi, cette méthode de protection n'est pas fiable.

En plus de cela, utiliser une boucle while comme ceci consomme inutilement du CPU.

Pour plus d'infomration voir la vidéo de la séance 3 du cours d'OS 2020 à 2:25:50.

Par alternance

La protection par alternance consiste de manière similaire à la méthode précédente à avoir une variable partagée mais ou chaque processus attends une valeur différente.

Ainsi, par exemple un programme 1 pourrait avoir le code suivant :

while (tour != 0);
/* Section critique ici */
tour = 1;

Et un programme 2 pourrait avoir le code suivant :

while (tour != 1);
/* Section critique ici */
tour = 0;

Ainsi lorsque tour est à 0, le programme 1 peut exécuter sa section critique, une fois qu'elle a fini le programme 2 peut exécuter la sienne, et une fois que le progrmame 2 à fini, le programme 1 peut recommencer.

Problèmes

Cette méthode de protection est fiable, contrairement à la précédente. Cependant elle souffre tout de même d'assez gros problèmes…

Premièrement, elle est assez difficile à gérer, surtout si il y a plus de deux processus à synchroniser.

Et deuximèment, comme la précédente, elle est assez peu efficace car utiliser une boucle while ainsi consomme inutilement du CPU.

Pour plus d'infomration voir la vidéo de la séance 3 du cours d'OS 2020 à 2:33:20.

Par fichier

La protection par fichier consiste à ouvrir et créer un fichier (appellé "lock file") en mode exclusif (c'est à dire qu'un seul processus peut accéder au fichier à la fois) pour annoncer que la section critique commence.

Puis enfin à supprimer le fichier une fois que la section critique est terminée.

#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#define FIN_SECTION_CRITIQUE 1
#define DEBUT_SECTION_CRITIQUE -1

int quid(int op, char* nom, int essais) {
  int i;

  /*
   * Quand on débute la section critique, on crée un fichier dit "lock file" en mode exclusif,
   * si cela n'est pas possible c'est qu'une section critique est déjà en cours
   */
  if(op == DEBUT_SECTION_CRITIQUE) {
    for(i=0;i<essais;++i) {
      /* Tenter d'écrire un fichier en mode exclusif (un seul processus a accès au fichier à la fois) et renvoyer 0 en cas de succès */
      if(open(nom,O_WRONLY|O_CREAT|O_EXCL) >=0) {
        return 0;
      }

      /* Si cela n'a pas fonctionné, réessayer dans une seconde */
      else if(i<essais) {
        sleep(1);
      }
    }
  }

  /*
   * A la fin d'une section critique on supprime le lock file
   */
  if(op == FIN_SECTION_CRITIQUE) {
    /* Suppression du fichier et retourne 0 en cas de succès */
    if(unlink(nom) == 0) {
      return 0;
    }
  }

  /* Retourne -1 en cas d'erreur ou dans le cas où tous les essais ont échoués */
  return -1;
}


int main(void) {
  printf("Attente section critique\n");
  quid(DEBUT_SECTION_CRITIQUE, "program.lock", 5);

  /* Section critique ici */
  printf("Début section critique\n");
  sleep(5);

  printf("Fin section critique\n");
  quid(FIN_SECTION_CRITIQUE, "program.lock", 5);

  return EXIT_SUCCESS;
}

Problèmes

Cette solution est tout à fait fonctionnelle et fiable, cependant le fait de devoir gérer un fichier peut rendre les choses un peu compliquée, de plus cela ralenti les choses. Car pour chaque accès au fichier, le processus devra passer en état waiting, puis ready, puis de nouveau running.

Pour plus d'infomration voir la vidéo de la séance 3 du cours d'OS 2020 à 2:37:50.

Synchronisation hardware

La synchronisation hardware consiste à utiliser des instructions assembleurs pour protéger une section critique.

Voici un pseudo-code de démonstration :

boolean TestAndSet (boolean target) {
    /* On copie la valeur de target */
    boolean rv = target;

    /* On met target à true */
    target = true;

    /* On retourne la copie de la valeur initiale */
    return rv;
}

Ainsi pour l'utiliser il suffirait de faire ceci :

/* On attends que le lock (variable partagée initialement à false) soit mis à false pour continuer */
while (TestAndSet(lock));

/* Section critique ici */

/* On met le lock à false une fois terminé */
lock = false;

Ainsi lorsque lock est à false, TestAndSet va la mettre à true et retourner false ce qui va donc faire passer la boucle et entrer en section critique. Une fois cette dernière terminée, le lock retourne à false.

En revanche si lock est à true, TestAndSet va retourner true et par conséquent rester dans le while, en attente jusqu'a ce que la variable soit à false.

Problèmes

Cette méthode est fiable mais le problème avec celle ci c'est l'utilisation du while qui va une fois de plus consomer du CPU pour simplement attendre.

Il est toute fois bon de noter que cette méthode est utilisée par le système d'exploitation pour gérer d'autes systèmes de protection tel que les sémaphores.

Pour plus d'infomration voir la vidéo de la séance 3 du cours d'OS 2020 à 2:47:00.

Sémaphore

Les sémaphores permettent de très simplement protéger une section critique, voici un exemple :

#include "semadd.h"
#include "sys/sem.h"
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>

#define KEY_SEM1 12345
#define KEY_SEM2 12346

int main(void) {

  int sem1, sem2;

  /* On crée 2 sémaphores */
  sem1 = sem_transf(KEY_SEM1);
  sem2 = sem_transf(KEY_SEM2);

  /* On crée un nouveau processus */
  switch (fork()) {
    case -1:
      printf("Quelque chose s'est mal passé lors de la création du processus...\n");
      return EXIT_FAILURE;

    /* Pour le fils */
    case 0:
      /* Attente du père */
      printf("En attente du père\n");
      p(sem1);

      /* Section critique */
      printf("Section critique du fils commence\n");
      sleep(3);

      /* Annonce au père qu'il a fini */
      printf("Section critique du fils se termine\n");
      v(sem2);

      break;


    /* Pour le père */
    default:
      /* Section critique */
      printf("Début de la section critique du père\n");
      sleep(3);

      /* Annonce au fils qu'il a fini */
      printf("Fin de la section critique du père\n");
      v(sem1);

      /* Attends le fils avant de supprimer les sémaphores */
      p(sem2);
      semctl(sem1, IPC_RMID, 0);
      semctl(sem2, IPC_RMID, 0);
  }

  return EXIT_SUCCESS;
}

Comme vu précédemment, les p et v des sémaphores sont des actions unitaires, il n'y a donc pas de risque que le processus soit arreter au millieu. L'utilisation des sémaphores est la manière recommandée de gérer des sections critiques.