Samuel Tardieu @ rfc1149.net

Synchronisation : exercices

Des exercices complémentaires se trouvent sur cette page.

Liste des problèmes

Énoncé: Création de processus

Solution
Combien de processus exécuteront le code suivant ? 
int main ()
{
  int i;
  for (i = 0; i < 4; i++) {
    fork ();
  }
  exit (0);
}

Énoncé: Ressource non bloquante

Solution
Plusieurs processus souhaitent accéder à une ressource partagée uniquement si celle-ci est disponible, sans bloquer (potentiellement longtemps) sur un sémaphore si elle est occupée. Comment faire ?

Énoncé: Compteur protégé

Solution
On souhaite partager un compteur N entre différents processus, qui pourront l’incrémenter et le décrémenter. Quel est le problème si les processus le manipulent directement ?
Comment le protéger ?
Les processus utilisent ce compteur pour compter le nombre de processus en attente sur une ressource protégée par un sémaphore S. Un processus préfère échouer s’il y a déjà 10 processus en attente, plutôt que d’être bloqué. Comment faire ?

Solution: Création de processus

Énoncé
Combien de processus exécuteront le code suivant ? 
int main ()
{
  int i;
  for (i = 0; i < 4; i++) {
    fork ();
  }
  exit (0);
}
Le nombre de processus double à chaque étape. Lorsqu’un processus est cloné, i hérite de la même valeur, et le père et le fils se retrouvent au même point.
  • Au début: 1 processus
  • Quand i vaut 0, 1 nouveau processus, total: 2
  • Quand i vaut 1, 2 nouveaux processus, total: 4
  • Quand i vaut 2, 4 nouveaux processus, total: 8
  • Quand i vaut 3, 8 nouveaux processus, total: 16

Solution: Ressource non bloquante

Énoncé
Plusieurs processus souhaitent accéder à une ressource partagée uniquement si celle-ci est disponible, sans bloquer (potentiellement longtemps) sur un sémaphore si elle est occupée. Comment faire ?
On doit utiliser un sémaphore, mais sur une section critique la plus courte possible. Pour cela, on utilise un sémaphore S initialisé avec 
Init (S, 1);
et une variable indiquant si la ressource est disponible initialisée avec 
libre = 1;
Le code pour faire un traitement si la ressource est disponible est maintenant: 
P (S);
if (libre == 1) {
   libre = 0;   /* La ressource est maintenant prise */
   V (S);
   ...          /* Traitement potentiellement long */
   libre = 1;   /* La ressource est maintenant disponible */
} else {
   V (S);
}

Solution: Compteur protégé

Énoncé
On souhaite partager un compteur N entre différents processus, qui pourront l’incrémenter et le décrémenter. Quel est le problème si les processus le manipulent directement ?
Si le code est 
N = N + 1
alors la loi de Murphy (dite aussi « loi de l’emmerdement maximal ») fera qu’un des processus sera interrompu après le calcul de N+1 mais avant l’écriture de la nouvelle valeur. Lorsqu’il reprendra la main, il écrira une valeur obsolète.
Comment le protéger ?

Il suffit de créer un sémaphore X initialisé par

Init (X, 1)
et de protéger par une section critique tous les accès au compteur: 
P (X);
N = N + 1;
V (X);
Les processus utilisent ce compteur pour compter le nombre de processus en attente sur une ressource protégée par un sémaphore S. Un processus préfère échouer s’il y a déjà 10 processus en attente, plutôt que d’être bloqué. Comment faire ? 
P (X);
if (N == 10) {
   /* Il y a déjà 10 processus en attente, échouer */
   V (X);
   return -1;
}
N = N + 1;
V (X);

/* Obtention de la ressource protégée */
P (S);

/* Décrémentation du nombre de processus en attente */
P (X);
N = N - 1;
V (X);

/* Utilisation de la ressource */
...

/* Libération de la ressource et sortie avec succès */
V (S);
return 0;