Systèmes d’Exploitation & Programmation Concurrente

Exercice 0 - Question de cours

Dans un contexte de concurrence interprocessus, le problème de famine (starvation) apparaît lorsque des processus (généralement de faible priorité) attendent indéfiniment l'accès à une ressource partagée sans jamais pouvoir y accéder, car d'autres processus continuent de la monopoliser.

La différence majeure avec l'interblocage (deadlock) est que lors d'un interblocage, tous les processus impliqués sont bloqués et aucun ne peut avancer, car chacun attend une ressource détenue par un autre. Dans une situation de famine, le système global continue de fonctionner et d'autres processus avancent, mais certains processus spécifiques sont laissés pour compte indéfiniment.

Exercice 1 - Appels système avec Fork

Question 1 - Arborescence des processus

Le programme utilise une boucle for allant de i = 0 à i = 3 (soit 4 itérations). À chaque itération, l'instruction if(fork()) break; est exécutée. L'appel système fork() renvoie une valeur non nulle (le PID de l'enfant) au processus parent, et 0 au processus enfant.

Par conséquent, à chaque itération, le parent exécute le break et sort de la boucle, tandis que l'enfant continue à l'itération suivante. Cela crée une arborescence linéaire (une chaîne) de processus :

P1 (parent initial, s'arrête à i=0) └── P2 (1er enfant, s'arrête à i=1) └── P3 (2ème enfant, s'arrête à i=2) └── P4 (3ème enfant, s'arrête à i=3) └── P5 (4ème enfant, termine la boucle à i=4)

Question 2 - Évolution des variables par processus

Selon le tableau attendu dans l'énoncé, chaque itération voit un nouveau processus prendre le relais pour la suite de l'exécution :

Itération	Processus actif (qui effectue le fork)
i=0	P1 (nommé P1 dans l'énoncé)
i=1	P2 (nommé P11 dans l'énoncé)
i=2	P3 (nommé P111 dans l'énoncé)
i=3	P4 (nommé P1111 dans l'énoncé)
i=4	P5 (nommé P11111, sort de la boucle normalement)

Question 3 - Affichage possible

Puisque les processus s'exécutent de manière concurrente après leur création et qu'il n'y a pas de mécanisme de synchronisation entre eux pour gérer l'affichage, l'ordre d'affichage n'est pas garanti. Toutefois, chaque processus affichera la lettre correspondant à la valeur de i au moment où il a quitté la boucle ('A' + i).

Les affichages générés seront (dans un ordre quelconque) : Mon nom est <A> Mon nom est <B> Mon nom est <C> Mon nom est <D> Mon nom est <E>

Question 4 - Modification pour un affichage inversé

Pour que l'affichage se fasse dans l'ordre alphabétique inversé (E, D, C, B, A), chaque processus parent doit attendre la terminaison de son processus enfant avant d'exécuter son instruction printf. Il suffit d'ajouter l'appel système wait(NULL); juste avant l'affichage.

Note : Pour que le code soit parfaitement valide et compilable en C, les bibliothèques <sys/wait.h> (pour wait) et <stdlib.h> (pour EXIT_SUCCESS) ont été ajoutées.

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>

int main()
{
    int i;
    for(i=0; i<4; i++) {
        if(fork()) break;
    }
    
    wait(NULL);
    
    printf("Mon nom est <%c>\n", 'A'+i);
    return(EXIT_SUCCESS);
}

Exercice 2 - Concurrence et synchronisation

Question 1 - Conditions pour des résultats corrects

De manière générale, les résultats d'une exécution concurrente (entrelacée) de deux processus sont considérés comme corrects s'ils sont équivalents à ceux obtenus par une exécution séquentielle stricte. Ici, les résultats corrects sont ceux correspondant soit à l'exécution de PA puis PB (PA ; PB), soit de PB puis PA (PB ; PA) :

• PA ; PB : PA lit k=1, écrit k=2, puis PB lit k=2, écrit k=6. Résultat : (2, 6). La valeur finale de k est 6.
• PB ; PA : PB lit k=1, écrit k=5, puis PA lit k=5, écrit k=6. Résultat : (5, 6). La valeur finale de k est 6.

Question 2 - Validité des résultats R1, R2, et R3

• R1 (PA avec k=2, PB avec k=2) : Possible mais non correct. Justification : Cet affichage se produit si l'exécution est entrelacée de la manière suivante : PA1, PA2, PA3, PA4, suivi de PB1, PB2, PB3, PB4 (où PB lit k=1 avant que PA ne modifie k, mais effectue son calcul après). Le résultat final de k sera 5, ce qui diffère de la valeur correcte (6).
• R2 (PA avec k=2, PB avec k=6) : Possible et correct. Justification : Cela correspond exactement à l'exécution séquentielle PA ; PB.
• R3 (PA avec k=5, PB avec k=2) : Impossible et non correct. Justification : Pour que PA affiche 5, il faudrait qu'il lise k=4, ce qui n'est jamais produit. De plus, k est strictement incrémentée par les deux processus, donc la deuxième valeur affichée devrait toujours être strictement supérieure à la première.

Question 3 - Exemples d'entrelacements

a) Un entrelacement possible et correct : L'exécution stricte PB puis PA produit (5, 6). Séquence : PB1 ; PB2 ; PB3 ; PB4 ; PA1 ; PA2 ; PA3 ; PA4.

b) Un entrelacement possible et non correct : L'exécution où les deux processus lisent la valeur initiale simultanément, mais où PA écrase la valeur de PB. Séquence produisant (6, 6) : PB1 ; PB2 ; PB3 ; PA1 ; PA2 ; PA3 ; PA4 ; PB4. PB lit 1, calcule 5, l'écrit. Puis PA lit 5, calcule 6, l'écrit. Enfin, PB affiche la variable globale k qui vaut maintenant 6.

Question 4 - Utilisation de sémaphores

Pour garantir des résultats corrects, il faut protéger la section critique (qui comprend la lecture, la modification et l'affichage de k) par un mécanisme d'exclusion mutuelle à l'aide d'un sémaphore.

Note de conception : La section critique inclut la lecture sur k, l'écriture sur k, et l'affichage final. Le signal V(Mutex) doit impérativement être placé après le printf pour empêcher l'affichage simultané (6, 6) illustré à la question précédente.

#include <stdio.h>

public int k = 1;
public semaphore Mutex = 1; // Sémaphore d'exclusion mutuelle

// Processus PA
int main ()
{
    int i;
    P(Mutex);
    i = k;
    i = i + 1;
    k = i;
    printf("PA avec k=%d\n", k);
    V(Mutex);
    // ...
}

// Processus PB
int main ()
{
    int j;
    P(Mutex);
    j = k;
    j = j + 4;
    k = j;
    printf("PB avec k=%d\n", k);
    V(Mutex);
    // ...
}

Exercice 3 - Ordonnancement

Question 1 - Famine et algorithmes à priorité

Oui, les algorithmes d'ordonnancement basés sur des priorités statiques peuvent engendrer un problème de famine pour les processus à faible priorité, si des processus à haute priorité continuent d'arriver dans le système. Pour éviter ce problème, on utilise un mécanisme de vieillissement (aging) ou un recalcul dynamique des priorités : la priorité d'un processus augmente progressivement à mesure qu'il attend, garantissant ainsi une équité d'exécution.

Question 2 - Ordonnancement statique avec préemption

On utilise les dates d'arrivée relatives : P1 (t=0), P2 (t=0), P3 (t=3), P4 (t=10). La priorité la plus forte correspond à la plus grande valeur.

Diagramme de Gantt : 0 -- P2 -- 3 -- P3 -- 10 -- P4 -- 28 -- P3 -- 29 -- P2 -- 41 -- P1 -- 51

• t=0 : P1 (prio 2) et P2 (prio 3) sont présents. P2 s'exécute.
• t=3 : P3 (prio 4) arrive. P3 préempte P2.
• t=10 : P4 (prio 5) arrive. P4 préempte P3.
• t=28 : P4 termine. P3 reprend.
• t=29 : P3 termine. P2 reprend.
• t=41 : P2 termine. P1 s'exécute enfin.
• t=51 : P1 termine.

Temps de réponse (TR = Date_Fin - Date_Arrivée) :

• TR(P1) = 51 - 0 = 51 mn
• TR(P2) = 41 - 0 = 41 mn
• TR(P3) = 29 - 3 = 26 mn
• TR(P4) = 28 - 10 = 18 mn

Temps de réponse moyen : TR_moyen = (51 + 41 + 26 + 18) / 4 = 136 / 4 = 34 mn. Note : Le corrigé source indique un temps moyen de 40 mn suite à une erreur d'arithmétique dans l'addition finale de l'énoncé. La démarche mathématique rigoureuse donne un résultat de 34 mn.

Question 3 - Ordonnancement à priorité dynamique

Rappel de la formule : Priorité = (T_Att + TE_Restant) / TE. Arrondi au plus proche : si E(2X) == 2E(X) alors E(X) sinon E(X) + 1. Cela équivaut à un arrondi classique (la moitié ou plus s'arrondit à l'entier supérieur).

a) Évolution des priorités et Diagramme de Gantt

Processus	TE	Prio Initiale	t=5	t=10	t=15	t=20	t=25	t=30	t=35	t=40	t=45
P1	10	2	2	1	1	2	2	-	-	-	-
P2	15	3	1	1	2	0	1	1	1	0	0
P3	8	4	-	1	2	3	0	1	1	2	-
P4	18	5	-	5	1	1	1	2	0	1	0

Diagramme de Gantt : 0 -- P2 -- 3 -- P3 -- 5 -- P1 -- 10 -- P4 -- 15 -- P2 -- 20 -- P3 -- 25 -- P1 -- 30 -- P4 -- 35 -- P2 -- 40 -- P3 -- 41 -- P4 -- 45 -- P2 -- 47 -- P4 -- 51

Déroulé détaillé de l'application de la règle d'égalité :

• À t=15 : P2 et P3 ont tous deux une priorité de 2. P2 attend depuis 12 mn (contre 10 mn pour P3). P2 prend la main.
• À t=35 : P2 et P3 ont tous deux une priorité de 1. P2 attend depuis 15 mn (contre 10 mn pour P3). P2 prend la main.
• À t=41 : Entre deux intervalles de recalcul, on garde les priorités de t=40 (P4 a prio 1, P2 a prio 0). P4 s'exécute de 41 à 45.
• À t=45 : P2 et P4 ont une priorité de 0. P2 attend depuis 5 mn, P4 vient de s'exécuter. P2 prend la main et termine à 47. P4 termine le reste.

Temps de réponse de chaque processus (fin - arrivée) :

• TR(P1) = 30 - 0 = 30 mn
• TR(P2) = 47 - 0 = 47 mn
• TR(P3) = 41 - 3 = 38 mn
• TR(P4) = 51 - 10 = 41 mn

Temps de réponse moyen : TR_moyen = (30 + 47 + 38 + 41) / 4 = 156 / 4 = 39 mn.

b) Résolution de la famine Oui, ce procédé résout le problème de la famine. Étant donné que le temps d'attente (T_Att) augmente en continu pour un processus non élu et qu'il figure au numérateur du calcul, la priorité d'un processus en attente finira inéluctablement par dépasser celle des processus nouvellement arrivés ou en cours d'exécution.

Exercice 4 - Synchronisation du problème H2O

Question 1 - Modélisation du problème

Le problème H2O implique une synchronisation où des atomes d'hydrogène (H) et d'oxygène (O) doivent s'attendre mutuellement. Il s'agit d'une combinaison de deux types de problèmes classiques de synchronisation :

1. Producteurs / Consommateurs : Les processus "Hydrogène" produisent des ressources (des atomes H) nécessaires pour qu'un processus "Oxygène" puisse consommer ces deux H et créer la molécule.
2. Rendez-vous (RDV) : Il faut qu'exactement deux atomes d'hydrogène soient disponibles pour s'associer avec un atome d'oxygène.

Question 2 - Synchronisation de base

a) Valeurs initiales des sémaphores : Semaphore Hyd = 0; et Semaphore Oxy = 0; Justification : Ces sémaphores servent de blocage pour initier un point de rendez-vous et gérer le modèle producteur/consommateur. À l'état initial, aucun atome n'est disponible.

b) Code C :

Semaphore Hyd = 0;
Semaphore Oxy = 0;

void Hydrogene()
{
    while (1) {
        V(Oxy);  // Indique la disponibilité d'un atome H au consommateur (O)
        P(Hyd);  // Attend au point de rendez-vous que la molécule soit créée
    }
}

void OxyReady()
{
    while (1) {
        P(Oxy);       // Consomme le 1er atome H
        P(Oxy);       // Consomme le 2nd atome H
        makeWater();  // Crée la molécule H2O
        V(Hyd);       // Libère le 1er atome H du point de rendez-vous
        V(Hyd);       // Libère le 2nd atome H du point de rendez-vous
    }
}

Question 3 - Scénario problématique

Déroulement H1, H2, puis O1, O2 : Si deux processus H arrivent, ils font chacun un V(Oxy), montant la valeur du sémaphore Oxy à 2. Ensuite, si deux processus O arrivent quasi simultanément, le premier O (O1) pourrait passer le premier P(Oxy), mais le second O (O2) pourrait être ordonnancé immédiatement et passer le second P(Oxy).

Conclusion : Ceci est très dangereux car cela mène à une situation de famine ou interblocage partiel. Les deux atomes d'oxygène (O1 et O2) auront tous les deux décrémenté le sémaphore Oxy une fois. Ils resteront bloqués sur leur second appel P(Oxy) car il n'y a plus d'atome H disponible. Aucune molécule d'eau n'est fabriquée alors que les atomes nécessaires sont pourtant présents dans le système.

Question 4 - Correction pour éviter la famine

Pour éviter qu'un second atome d'oxygène n'interfère pendant qu'un premier essaie de réunir ses deux atomes d'hydrogène, il faut englober la procédure du processus oxygène dans une zone d'exclusion mutuelle à l'aide d'un sémaphore Mutex.

Semaphore Hyd = 0; // Sémaphore de blocage pour le RDV
Semaphore Oxy = 0; // Sémaphore pour compter les H
Semaphore Mutex = 1; // Exclusion mutuelle pour l'attente des deux H

void Hydrogene()
{
    while (1) {
        V(Oxy);  // Producteur de H
        P(Hyd);  // Rendez-vous avec la molécule
    }
}

void OxyReady()
{
    while (1) {
        P(Mutex);     // Bloque l'accès aux autres processus Oxygène
        
        P(Oxy);       // Consomme le 1er atome H
        P(Oxy);       // Consomme le 2nd atome H
        makeWater();  // Crée la molécule H2O
        V(Hyd);       // Libère le 1er H
        V(Hyd);       // Libère le 2nd H
        
        V(Mutex);     // Libère l'accès pour le prochain atome d'oxygène
    }
}

Méthode

Face à une épreuve de ce type (Systèmes d'Exploitation et Concurrence), voici comment structurer votre approche :

1. Lisez très attentivement les règles d'ordonnancement : Les erreurs de calcul viennent presque systématiquement des exceptions de priorités ou des événements arrivant au même instant. Dressez toujours un tableau d'évolution des états (comme à l'exercice 3.3) avant de dessiner votre diagramme de Gantt.
2. Exécution manuelle (Desk Checking) des sémaphores : Ne présumez jamais que votre code de synchronisation fonctionne au premier regard. Prenez une marge d'entrelacement pathologique ("que se passe-t-il si un processus est préempté exactement entre le premier P() et le second ?") pour détecter les cas de famine ou de deadlock.
3. Respect strict des définitions : Si l'énoncé vous donne une formule pour les priorités avec des arrondis spécifiques, n'utilisez pas de raccourci mental ; calculez la partie fractionnaire et appliquez le palier indiqué au risque de décaler tout le reste de votre ordonnancement.
4. Vérification de cohérence : Assurez-vous que vos temps de réponse moyens soient cohérents avec votre diagramme de Gantt. En cas de litige entre un calcul formel et une impression visuelle sur le Gantt, revérifiez les instants d'arrivée (t_attente = t_actuel - t_arrivée).