Exercices

Exercice 1 [Examen de septembre 1995] Soient 3 processus qui exécutent les programmes suivants :


P1: loop A1 end_loop
P2: loop A2 end_loop     
P3: loop A3 end_loop

Utiliser des sémaphores pour synchroniser ces 3 processus de telle manière que:

Question 1 Les actions Ai ne soient jamais simultanées.

Question 2 Les actions Ai ne soient jamais simultanées et se déroulent toujours dans l'ordre A1A2A3A1A2A3...

Question 3 Les actions Ai ne soient jamais simultanées et se déroulent toujours dans l'ordre A1(A2 ou A3)A1(A2 ou A3)...

Question 4 Les actions Ai se déroulent toujours séquentiellement mais dans un ordre quelconque, par exemple : (A2A1A3)(A2A3A1)...

Exercice 2 [Examen de juin 1996] Soient les deux processus P1 et P2 suivants. Ils se partagent deux sémaphores, S1 et S2 initialisés à 0.


  P1 {                     P2 {
       procedure A1;            procedure A2;
       V(S2);                   V(S1);
       P(S1);                   P(S2);
       procedure B1;            procedure B2;
     }                        }

Question 1 Quelle synchronisation a-t-on imposée sur les exécutions des procédures A1, A2, B1 et B2 ?

Question 2 Écrire le code afin d'imposer la même synchronisation pour N processus en utilisant N sémaphores.

Question 3 On peut résoudre le problème pour N processus avec uniquement deux sémaphores (et un compteur). Donner le code des processus dans ce cas.

Exercice 3 [La mangeoire (d'après Tim Roberts)] Un abri pour oiseaux comporte de nombreuses portes. Chaque porte possède un bouton à l'intérieur et un bouton à l'extérieur. L'abri peut contenir au maximum trois oiseaux.

Les oiseaux sont dressés pour appuyer sur les boutons s'ils veulent entrer ou sortir. Ils sont aussi dressés pour que un seul d'entre-eux ne rentre ou sorte quand une porte s'ouvre.

Quand un oiseau utilise un des boutons, les fonctions suivantes sont appelées :


int birds_in = 0 ; 

bird_wants_to_leave (int button)
{
  birds_in-- ; 
  open_door (button) ; 
}

bird_wants_to_enter (int button) 
{
  if (birds_in < 3) {
    birds_in++ ;
    open_door (button) ; 
  }
}

Le code de ces fonctions est faux et pose de nombreux problèmes.

Question 1 Établir une liste des problèmes pouvant survenir.

Question 2 Utiliser des sémaphores pour résoudre ces problèmes.

Exercice 4 [La salle de bain (à nouveau d'après Tim Roberts)] La salle de bain commune d'une pension mixte est utilisée par les filles et les garçons. Les règles suivantes sont observées :

au plus MAX filles utilisent simultanément la salle de bain ;
au plus MAX garçons utilisent simultanément la salle de bain ;
la salle de bain n'est jamais utilisé simultanément par des garçons et des filles ;
les filles ont priorité sur les garçons pour utiliser la salle de bain ;
les garçons ne peuvent entrer dans la salle de bain que si aucune fille n'utilise ou n'attend pour utiliser la salle de bain.

Question 1 À quelle condition une fille peut-elle entrer dans la salle de bain ? Et un garçon ?

Question 2 Identifier les événements qui peuvent bloquer un processus (fille ou garçon).

Question 3 Donner le code des quatre fonctions

void boy_wants_to_use_bathroom () ; 
void boy_leaves_bathroom () ; 
void girl_wants_to_use_bathroom () ; 
void girl_leaves_bathroom () ;

3 Exercices