Examen final INF2610

Ce document présente un examen final du cours INF2610 portant sur la gestion des processus, la synchronisation, les sémaphores, l’interblocage et l’ordonnancement. Il teste les compétences en programmation concurrente, en compréhension des mécanismes de synchronisation, et en analyse des problèmes liés aux ressources partagées.

Question 1 : Généralités

On demande d’analyser un code avec des appels à fork, de répondre à une question sur le partage de pointeurs de fichiers sous Windows, et d’expliquer l’implémentation des moniteurs en Java.

a) Arborescence des processus et valeurs de n

Le code crée des processus en boucle avec fork, et la variable n est modifiée uniquement dans les processus fils. La boucle s’arrête dans un processus père dès que pid != 0.

Analyse :

• Initialement, i=0, n=0.
• Premier fork : le processus principal (P0) crée un fils (F1). P0 a pid ≠ 0, donc il sort de la boucle et affiche n=0.
• F1 a pid=0, donc il continue la boucle, n = n + i = 0 + 0 = 0.
• Deuxième fork dans F1 : crée F11. F1 a pid ≠ 0, il sort et affiche n=0.
• F11 a pid=0, continue, n = 0 + 1 = 1.
• Troisième fork dans F11 : crée F111. F11 a pid ≠ 0, il sort et affiche n=1.
• F111 a pid=0, continue, n = 1 + 2 = 3.
• F111 ne crée plus de processus (i=3), il affiche n=3.

Arborescence :

• P0 (n=0)
• └─ F1 (n=0)
•   └─ F11 (n=1)
•     └─ F111 (n=3)

Valeurs affichées :

• P0 affiche n=0
• F1 affiche n=0
• F11 affiche n=1
• F111 affiche n=3

b) Partage du pointeur de fichier sous Windows

Peut-on partager un même pointeur de fichier entre un processus père et son fils sous Windows ?

Réponse : Oui. Il faut que le handle du fichier soit marqué comme héritable lors de sa création ou ouverture. Ensuite, lors de la création du processus fils, il doit hériter des handles marqués héritable. Ainsi, père et fils peuvent partager le même pointeur de fichier.

c) Implémentation des moniteurs en Java

Java implémente les moniteurs en permettant l’exclusion mutuelle sur les méthodes synchronized d’un objet. Chaque objet possède une variable de condition et deux files d’attente :

• Entry queue : pour gérer les demandes d’accès aux méthodes synchronized.
• Wait queue : pour les threads en attente sur la variable de condition.

Ce modèle correspond à un problème classique de synchronisation similaire à celui des lecteurs/rédacteurs. Les méthodes synchronized sont les rédacteurs (exclusion mutuelle stricte), tandis que les autres méthodes sont les lecteurs (accès concurrent).

Résumé : Java utilise un modèle de moniteur avec exclusion mutuelle sur méthodes synchronized, gérant les files d’attente pour l’accès et l’attente conditionnelle, ce qui correspond à un problème classique de synchronisation vu en cours.

Question 2 : Moniteurs et variables de condition

On doit synchroniser trois threads th1, th2 et th3, chacun exécutant une fonction Fi en boucle infinie. Chaque cycle est une section critique, et chaque cycle de th3 doit être précédé d’un cycle de th1 et d’un cycle de th2.

Il faut compléter le pseudocode du moniteur SynCycles avec des variables de condition pour assurer cette synchronisation.

Analyse :

• On utilise trois variables booléennes t1, t2, t3 indiquant si c’est le tour du thread correspondant (1 = oui, 0 = non).
• Au départ, t1=1, t2=1, t3=0, ce qui signifie que th1 et th2 peuvent commencer, th3 attend.
• Chaque fonction attend que son tour soit actif (t_i=1), puis exécute sa section critique.
• Après th1 ou th2, on met t_i=0, et si les deux sont terminés (t1=0 et t2=0), on active t3=1 et on signale c3.
• Après th3, on remet t3=0, t1=1, t2=1, et on signale c1 et c2 pour recommencer un nouveau cycle.

Code complété :

Moniteur SynCycles
{
  /*0*/ bool c1, c2, c3;
       bool t1=1, t2=1, t3=0;   // ti=1 si c’est le tour de thi, 0 sinon.

  Function F1()  // fonction de th1
  {
    while (1) {
      /*1*/ while (t1 != 1) c1.wait();
      Sc1();  // section critique de th1
      /*2*/ t1 = 0;
            if (t2 == 0) {
              t3 = 1;
              c3.signal();
            }
    }
  }

  Function F2()  // fonction de th2
  {
    while (1) {
      /*3*/ while (t2 != 1) c2.wait();
      Sc2();  // section critique de th2
      /*4*/ t2 = 0;
            if (t1 == 0) {
              t3 = 1;
              c3.signal();
            }
    }
  }

  Function F3()  // fonction de th3
  {
    while (1) {
      /*5*/ while (t3 != 1) c3.wait();
      Sc3();  // section critique de th3
      /*6*/ t3 = 0; t1 = 1; t2 = 1;
            c1.signal(); c2.signal();
    }
  }
}

Cette solution garantit que chaque cycle de th3 est précédé d’un cycle de th1 et d’un cycle de th2, avec exclusion mutuelle sur chaque section critique.

Question 3 : Sémaphore

On doit synchroniser l’accès à une pile partagée entre plusieurs threads, avec empiler et depiler bloquants selon la disponibilité d’espace ou d’éléments. Puis, on étend à une file circulaire avec enfiler et defiler de plusieurs éléments.

a) Synchronisation de la pile avec sémaphores

Variables :

• sommet : indice du sommet de la pile
• pile[Size] : tableau de la pile
• sémaphores : libre (nombre d’espaces libres), occupe (nombre d’éléments), mutex (exclusion mutuelle)

Initialisation :

Semaphore libre = Size, occupe = 0, mutex = 1;

Fonction empiler :

• P(libre) : attendre qu’il y ait un espace libre
• P(mutex) : entrer en section critique
• pile[sommet] = a; sommet++;
• V(mutex) : sortir de la section critique
• V(occupe) : signaler qu’un élément est disponible

Fonction depiler :

• P(occupe) : attendre qu’il y ait un élément
• P(mutex) : entrer en section critique
• sommet--; tmp = pile[sommet];
• V(mutex) : sortir de la section critique
• V(libre) : signaler qu’un espace est libre
• return tmp;

int sommet = 0;
int pile[Size];

/* 0 */ Semaphore libre = Size, occupe = 0, mutex = 1;

void empiler(int a) {
  /* 1 */ P(libre);
          P(mutex);
          pile[sommet] = a;
          sommet++;
  /* 2 */ V(mutex);
          V(occupe);
}

int depiler() {
  /* 3 */ P(occupe);
          P(mutex);
          sommet--;
          int tmp = pile[sommet];
  /* 4 */ V(mutex);
          V(libre);
          return tmp;
}

Cette solution respecte les contraintes de blocage et d’exclusion mutuelle.

b) Synchronisation d’une file circulaire avec sémaphores

Variables :

• t = indice tête, q = indice queue
• file[Size] : tableau circulaire
• sémaphores : libre (espaces libres), occupe (éléments disponibles), mutex1 et mutex2 pour exclusion mutuelle dans enfiler et defiler respectivement

Initialisation :

Semaphore libre = Size, occupe = 0, mutex1 = 1, mutex2 = 1;

Fonction enfiler (int A[], int m) :

• P(mutex1) : exclusion mutuelle sur enfiler
• Pour i=0 à m-1 : P(libre) pour réserver l’espace nécessaire
• Insérer les éléments A[i] dans file[q], avancer q modulo Size
• V(mutex1) : libérer exclusion mutuelle
• Pour i=0 à m-1 : V(occupe) pour signaler la disponibilité des éléments

Fonction defiler (int A[], int m) :

• P(mutex2) : exclusion mutuelle sur defiler
• Pour i=0 à m-1 : P(occupe) pour attendre les éléments
• Extraire les éléments de file[t] dans A[i], avancer t modulo Size
• V(mutex2) : libérer exclusion mutuelle
• Pour i=0 à m-1 : V(libre) pour signaler la libération d’espace

int t = 0, q = 0;
int file[Size];

/* 0 */ Semaphore libre = Size, occupe = 0, mutex1 = 1, mutex2 = 1;

void enfiler(int A[], int m) {
  int i;
  /* 1 */ P(mutex1);
          for (i = 0; i < m; i++) P(libre);
          for (i = 0; i < m; i++) {
            file[q] = A[i];
            q = (q + 1) % Size;
          }
  /* 2 */ V(mutex1);
          for (i = 0; i < m; i++) V(occupe);
}

void defiler(int A[], int m) {
  int i;
  /* 3 */ P(mutex2);
          for (i = 0; i < m; i++) P(occupe);
          for (i = 0; i < m; i++) {
            A[i] = file[t];
            t = (t + 1) % Size;
          }
  /* 4 */ V(mutex2);
          for (i = 0; i < m; i++) V(libre);
}

Cette solution assure la synchronisation correcte des accès concurrents à la file circulaire.

Question 4 : Interblocage

Trois processus P1, P2 et P3 utilisent 6 ressources R1 à R6 en exclusion mutuelle avec des séquences d’acquisition et de libération.

On demande si un interblocage est possible, et si oui, comment le prévenir ou l’éviter.

Analyse :

• Scénario d’interblocage possible :
• P1 prend R4 et R5
• P3 prend R1 et R2
• P2 prend R3
• P1 attend R3 (occupée par P2)
• P3 attend R5 (occupée par P1)
• P2 attend R2 (occupée par P3)
• Chacun attend une ressource détenue par un autre, formant un cycle d’attente bloquante.

Oui, un interblocage peut survenir.

Prévention :

• Imposer un ordre total sur les ressources : R1 < R2 < R3 < R4 < R5 < R6.
• Modifier les codes pour que chaque processus demande les ressources dans cet ordre croissant.

Code modifié :

P1()
{
  while(1) {
    prendre(R3);
    prendre(R4);
    prendre(R5);
    // Utiliser R4, R5, R3
    liberer(R4);
    liberer(R5);
    liberer(R3);
  }
}

P2()
{
  while(1) {
    prendre(R2);
    prendre(R3);
    prendre(R6);
    // Utiliser R3, R2, R6
    liberer(R6);
    liberer(R2);
    liberer(R3);
  }
}

P3()
{
  while(1) {
    prendre(R1);
    prendre(R2);
    prendre(R5);
    // Utiliser R1, R2, R5
    liberer(R5);
    liberer(R2);
    liberer(R1);
  }
}

Cette stratégie empêche la formation de cycles d’attente.

Évitement :

• On peut appliquer l’algorithme du banquier, car les besoins maximaux sont connus.
• Au départ, toutes les ressources sont libres, et la matrice d’allocation est nulle.
• L’algorithme vérifie que l’allocation ne mène jamais à un état non-sûr.

Conclusion : L’interblocage est possible, mais on peut le prévenir en ordonnant les demandes de ressources, ou l’éviter en utilisant l’algorithme du banquier.

Question 5 : Ordonnancement de processus

Deux parties : a) ordonnancement préemptif à priorités fixes avec quantum, b) ordonnançabilité RMA avec protocole PIP.

a) Ordonnancement préemptif à priorités fixes

On considère 5 processus P1 à P5 avec dates d’arrivée, priorités et temps d’exécution donnés dans un tableau. Le système est monoprocesseur, avec un seul périphérique d’E/S partagé, temps de commutation nul, priorité 1 la plus basse, et round-robin entre processus de même priorité avec quantum 3.

Le diagramme de Gantt montre l’exécution des processus en fonction de leur priorité et arrivée, en préemptant les processus de plus basse priorité dès qu’un plus prioritaire arrive, et en partageant le CPU entre processus de même priorité par quantum.

Le corrigé fournit un diagramme détaillé (non reproduit ici faute de figure), indiquant l’ordre d’exécution des processus selon ces règles.

b) Ordonnançabilité RMA avec protocole PIP

On considère 3 tâches partageant une ressource R, avec dates d’arrivée, temps d’exécution et deadlines égales à leur période :

Processus	Date d’arrivée	Temps d’exécution	Deadline = Période
P1	6	3	6
P2	8	2	8
P3	12	0	12

On doit vérifier si ces tâches sont ordonnançables avec Rate Monotonic Analysis (RMA) en utilisant le protocole d’héritage de priorités (PIP) pour gérer les inversions de priorité, sur l’intervalle [0,27].

Le corrigé ne fournit pas de calcul explicite, mais la question implique d’appliquer les tests d’ordonnançabilité RMA en tenant compte des blocages dus au partage de la ressource R et de la gestion PIP.

Sans données supplémentaires, on ne peut conclure ici.

Méthode

Ce type d’examen récompense une compréhension précise des mécanismes de synchronisation et de gestion des processus concurrents. Les points clés sont :

• Analyser soigneusement le comportement des processus et des threads, notamment avec fork ou en présence de variables partagées.
• Utiliser correctement les primitives de synchronisation (sémaphores, moniteurs, variables de condition) en respectant les contraintes d’exclusion mutuelle et d’attente.
• Pour les problèmes d’interblocage, identifier les cycles d’attente et proposer des solutions classiques : ordonnancement des ressources, algorithme du banquier.
• En ordonnancement, appliquer les règles de priorité, préemption, quantum, et protocoles de gestion des ressources partagées.
• Présenter les raisonnements étape par étape, justifier chaque choix et ne pas hésiter à expliciter les états intermédiaires.

Les erreurs pénalisées sont notamment :

• Oublier l’exclusion mutuelle lors de l’accès aux structures partagées.
• Ne pas gérer correctement les conditions de blocage (par exemple, ne pas attendre la disponibilité d’une ressource).
• Ignorer les règles d’ordonnancement ou de priorité.
• Ne pas justifier les réponses ou donner des résultats sans démonstration.

En résumé, la rigueur dans l’analyse et la maîtrise des concepts de synchronisation sont essentielles pour réussir ce type d’épreuve.