Examen final INF2610

Ce document présente un examen final en système d’exploitation, portant sur le noyau du système. Il évalue les compétences en gestion des processus, synchronisation, ordonnancement, et programmation concurrente à travers des questions théoriques et pratiques.

Question 1 : Généralités

Cette question comporte plusieurs sous-questions portant sur des concepts fondamentaux du système d’exploitation.

a) Principe « copy-on-write » pour cloner un processus

Il est demandé d’expliquer comment le principe « copy-on-write » est utilisé pour créer un clone d’un processus.

Lorsqu’un processus est cloné, la table des pages du processus père est dupliquée. Le père et le fils partagent les mêmes cadres mémoire tant qu’ils y accèdent en lecture. Si l’un des deux (père ou fils) veut écrire dans un cadre mémoire partagé, une copie de ce cadre est alors créée uniquement pour le processus qui écrit. Cela évite de dupliquer toute la mémoire immédiatement, optimisant ainsi la création du clone.

Réponse : Le clone partage initialement la mémoire en lecture seule avec le père, et une copie est créée seulement lors d’une écriture (copy-on-write).

b) Inversion de priorité avec sémaphore binaire et gestion par priorité

Peut-on avoir des problèmes d’inversion de priorités si la file d’attente d’un sémaphore binaire est gérée selon les priorités dans un système préemptif à priorité ?

Oui, car un processus de basse priorité L peut verrouiller le sémaphore. Si un processus de haute priorité H demande ensuite ce sémaphore, il sera bloqué jusqu’à ce que L le libère, ce qui crée une inversion de priorité.

Réponse : Oui, l’inversion de priorité peut se produire malgré la gestion par priorité dans la file du sémaphore.

c) Suspension d’un processus dans sa section critique avec sémaphore et ordonnancement circulaire

Le système peut-il suspendre le processus A durant sa section critique et élire ensuite le processus B ? Si oui, B peut-il entrer en section critique ?

Oui, dans un système à ordonnancement circulaire, si A a consommé tout son quantum, il peut être suspendu et B élu. Cependant, B ne peut pas entrer en section critique car il doit attendre la libération du sémaphore (P(x) le bloque).

Réponse : Oui, A peut être suspendu, mais B ne peut pas entrer en section critique tant que le sémaphore n’est pas libéré.

d) Utilisation de l’algorithme du banquier pour le problème des philosophes

Peut-on utiliser l’algorithme du banquier pour éviter les interblocages dans le problème des philosophes ? Si oui, expliquer la définition de l’état, le traitement des demandes et des libérations, et donner l’état de départ ainsi que l’état après la demande de la fourchette f4 par le philosophe 4.

Oui, l’algorithme du banquier peut être utilisé car on connaît les besoins de chaque philosophe. L’état est défini par :

• E = vecteur des ressources disponibles, ici E = (1 1 1 1 1)
• A = vecteur des ressources allouées, initialement A = (1 1 1 1 1)
• Alloc(phi) = allocation actuelle par philosophe, initialement (0 0 0 0 0)
• Req(phi) = demande actuelle par philosophe, par exemple :

Req(ph0) = (1 0 0 0 1), Req(ph1) = (1 1 0 0 0), Req(ph2) = (0 1 1 0 0), Req(ph3) = (0 0 1 1 0), Req(ph4) = (0 0 0 1 1).

Après la demande de f4 par le philosophe 4, l’état devient :

• E = (1 1 1 1 1)
• A = (1 1 1 1 0)
• Alloc(ph4) = (0 0 0 0 1)
• Req(ph4) = (0 0 0 1 0)

Réponse : Oui, l’algorithme du banquier s’applique avec l’état et les demandes définis ci-dessus, permettant de gérer les demandes et libérations sans interblocage.

e) Avantage et inconvénient d’une file d’exécution par processeur sous Linux

Donner un avantage et un inconvénient d’utiliser une file d’exécution par processeur plutôt qu’une seule file partagée.

Avantage : Avec une seule file d’exécution partagée, l’accès concurrent par plusieurs processeurs nécessite une exclusion mutuelle, ce qui ralentit l’accès et impacte le taux d’utilisation des processeurs.

Inconvénient : Il faut gérer la répartition des processus entre les différentes files d’exécution, ce qui complique la gestion globale.

Réponse : Avantage : réduction des blocages liés à l’accès concurrent. Inconvénient : complexité de gestion de la répartition des processus.

Question 2 : Barrières et compteurs d’événements

On demande de synchroniser des tâches selon des contraintes de précédence en utilisant d’abord des barrières, puis des compteurs d’événements.

a) Synchronisation avec barrières

Compléter le pseudo-code des tâches T1, T2, T3 et T4 pour respecter les contraintes :

• Le premier cycle de T1 est exécuté en premier ;
• Les cycles de T2 et T3 sont exécutés en concurrence après T1 ;
• Le cycle de T4 commence après ceux de T2 et T3 ;
• Le second cycle de T1 commence après T4, et ainsi de suite.

Barrières utilisées :

• B123 (3) : synchronise T1, T2 et T3
• B234 (3) : synchronise T2, T3 et T4
• B14 (2) : synchronise T1 et T4

Code complété :

T1( )
{
  while (1)
  {
    cycle(T1);
    B123.Barriere();
    B14.Barriere();
  }
}

T2( )
{
  while (1)
  {
    B123.Barriere();
    cycle(T2);
    B234.Barriere();
  }
}

T3( )
{
  while (1)
  {
    B123.Barriere();
    cycle(T3);
    B234.Barriere();
  }
}

T4( )
{
  while (1)
  {
    B234.Barriere();
    cycle(T4);
    B14.Barriere();
  }
}

Rôle : B123 lance T2 et T3 après T1, B234 lance T4 après T2 et T3, B14 lance T1 après T4.

b) Synchronisation avec compteurs d’événements

Utiliser un compteur d’événements E initialisé à 0, avec les opérations atomiques E.Read(), E.Advance() et E.Await(val).

Variables :

• Compteur d’événements E
• Variables entières n initialisées différemment selon la tâche

Code :

T1( )
{
  int n=0;
  while (1)
  {
    cycle(T1);
    n = n + 4;
    E.Advance();
    E.Await(n);
  }
}

T2( )
{
  int n=1;
  while (1)
  {
    E.Await(n);
    cycle(T2);
    n = n + 4;
    E.Advance();
  }
}

T3( )
{
  int n=1;
  while (1)
  {
    E.Await(n);
    cycle(T3);
    n = n + 4;
    E.Advance();
  }
}

T4( )
{
  int n=3;
  while (1)
  {
    E.Await(n);
    cycle(T4);
    n = n + 4;
    E.Advance();
  }
}

Rôle : Chaque tâche attend que le compteur atteigne une certaine valeur avant de commencer son cycle, puis avance le compteur à la fin, assurant la synchronisation selon les contraintes.

Question 3 : Moniteurs

Compléter un moniteur AccesBD pour gérer le problème des lecteurs-rédacteurs avec accès partagé en lecture et exclusif en écriture, sans gérer la famine des rédacteurs.

Variables utilisées :

• int nbl = nombre de lecteurs actifs
• bool libre = indique si la base est libre (1) ou occupée (0)
• int nbwait = nombre de processus en attente
• condition d’attente acces

Code complété :

Moniteur AccesBD
{
  int nbl=0, nbwait=0;
  bool libre=1;
  condition acces;

  ReadRequest()
  {
    if (nbl == 0)
    {
      if (libre)
        libre = 0;
      else
      {
        nbwait++;
        wait(acces);
      }
    }
    nbl++;
  }

  WriteRequest()
  {
    if (libre)
      libre = 0;
    else
    {
      nbwait++;
      wait(acces);
    }
  }

  ReadEnd()
  {
    nbl--;
    if (nbl == 0)
    {
      if (nbwait > 0)
      {
        nbwait--;
        signal(acces);
      }
      else
        libre = 1;
    }
  }

  WriteEnd()
  {
    if (nbwait > 0)
    {
      nbwait--;
      signal(acces);
    }
    else
      libre = 1;
  }
}

Explication : Les lecteurs peuvent accéder simultanément tant que la ressource est libre. Le premier lecteur verrouille la ressource. Les écrivains attendent que la ressource soit libre. À la fin, on signale les processus en attente ou on libère la ressource.

Question 4 : Ordonnancement

On considère un système monoprocesseur avec 3 producteurs (P1, P2, P3) et un consommateur (C1) communiquant via un tampon de taille 3. Chaque production ou consommation prend 1 quantum de temps.

a) Attente active

Donner le nombre d’items produits ou consommés par chaque processus à la fin de 10 quanta, avec un diagramme de Gantt.

Analyse :

• Ordre d’arrivée dans la file : P1, P2, P3, C1
• Chaque producteur produit 1 item par quantum, mais s’arrête si tampon plein (attente active)
• Consommateur consomme 1 item par quantum, mais s’arrête si tampon vide (attente active)

Diagramme de Gantt simplifié (P=production, C=consommation, (AA)=attente active) :

P1 P2 P3 C1 P1 P2(AA) P3(AA) C1 P1 P2(AA)

Nombre d’items produits/consommés :

• P1 : 3 productions
• P2 : 1 production
• P3 : 1 production
• C1 : 2 consommations

Réponse : P1 produit 3 items, P2 et P3 produisent 1 item chacun, C1 consomme 2 items.

b) Attente passive avec sémaphores FIFO

Les attentes actives sont remplacées par des attentes passives sur sémaphores P(libre) et P(occupe), avec files FIFO.

Diagramme de Gantt :

P1 P2 P3 C1 P1 P2(B) P3(B) C1 P1 P2(B) C1 P1 P3(B) C1

Nombre d’items produits/consommés :

• P1 : 4 productions
• P2 : 1 production
• P3 : 1 production
• C1 : 4 consommations

Réponse : Avec attente passive, P1 produit 4 items, P2 et P3 produisent 1 item chacun, C1 consomme 4 items.

Question 5 : Ordonnancement temps réel

Considérons un système avec n tâches périodiques A1,...,An et m=2n tâches périodiques B1,...,Bm. Les tâches Ai ont période 12 et durée 2, les tâches Bi ont période 6 et durée 1. Les échéances sont égales aux périodes.

a) Nombre maximal de tâches admises avec EDF

Calcul de l’utilisation CPU :

Utilisation des Ai : n * (2/12) = n/6

Utilisation des Bi : 2n * (1/6) = 2n/6 = n/3

Utilisation totale = n/6 + n/3 = n/6 + 2n/6 = 3n/6 = n/2

Pour que le système soit ordonnançable, utilisation ≤ 1 donc :

n/2 ≤ 1 ⇒ n ≤ 2

Réponse : Le nombre maximal de tâches Ai est 2, donc 4 tâches Bi.

b) Diagramme de Gantt pour n=1, tâches A1, B1, B2 arrivant aux temps 0, 1 et 2 avec EDF

Ordonnancement EDF :

• À t=0, A1 arrive (deadline 12)
• À t=1, B1 arrive (deadline 7)
• À t=2, B2 arrive (deadline 8)

Priorité EDF : tâches avec échéance la plus proche sont exécutées en premier.

Exécution :

• t=0 : A1 commence (durée 2)
• t=1 : B1 arrive, mais A1 continue car en cours
• t=2 : B2 arrive, A1 termine
• t=2 : B1 a échéance 7, B2 échéance 8, B1 prioritaire, exécute 1 quantum
• t=3 : B2 exécute 1 quantum
• t=4 : A1 peut être réexécuté si périodique, sinon idle

Diagramme simplifié :

A1 A1 B1 B2 A1 B1 ...

Réponse : Le diagramme montre l’exécution d’A1 en premier, puis B1 et B2 selon leurs échéances.

Méthode

Ce sujet récompense la maîtrise des concepts fondamentaux du système d’exploitation, notamment la gestion mémoire (copy-on-write), la synchronisation (barrières, compteurs d’événements, moniteurs), et l’ordonnancement (temps partagé, temps réel, sémaphores). Il faut toujours justifier les réponses, expliciter les étapes et utiliser les notations et conventions données. Les erreurs fréquentes concernent la mauvaise compréhension des mécanismes de synchronisation, l’oubli des blocages liés aux sémaphores, ou l’application incorrecte des algorithmes d’ordonnancement. La rigueur dans le raisonnement et la clarté dans la présentation des solutions sont essentielles.