Devoir Surveillé en Systèmes d’exploitation et Programmation Concurrente

Exercice 1 - Questions de cours

Question 1 - Termes techniques

a) L’un des rôles importants d’un système d’exploitation est de masquer la mise en œuvre des services : Abstraction. b) Section de code qui doit s’exécuter de manière atomique afin d’éviter les conditions de vitesse : Section critique. c) Fonction système de clonage du processus (Unix) courant : fork() (ou l'appel de fork puis exec). d) Etat d’un processus qui n’est pas en cours d’exécution mais éligible à être ordonnancé : Prêt (Ready). e) L’intervalle de temps entre le lancement d’un processus et sa fin : Temps de réponse (ou temps de séjour). f) Un dispositif matériel qui permet au système d'exploitation la protection des processus en exécution : Mode d'exécution (aussi appelé bit de mode ou MMU).

Question 2 - Interblocage et blocage

Le blocage d’un processus correspond à l’attente d'éléments dont il a besoin et qui ne sont pas immédiatement disponibles (par exemple : attente de la réalisation d’une opération d’Entrée/Sortie, attente du signalement d’un événement).

Un ensemble de processus est en interblocage (deadlock) si et seulement si tout processus de l'ensemble est en attente d'un événement qui ne peut être déclenché que par un autre processus de ce même ensemble. Dans ce cas, aucun processus ne peut avancer.

Question 3 - Famine

La famine (starvation) est la situation où un processus demande l'accès à une ressource (ou cherche à franchir un point de synchronisation) et voit l'exécution de sa demande perpétuellement différée au profit d'autres processus, l'empêchant ainsi de progresser indéfiniment.

Question 4 - Files d'attente pour un moniteur

Pour implémenter un moniteur, plusieurs files d'attente sont nécessaires :

1. Une file d'attente d'entrée pour mémoriser les demandes d’accès au moniteur lui-même (une file par fonction du moniteur ou pour l'ensemble du moniteur).
2. Une file d'attente par variable de condition pour gérer les processus suspendus lors d'un appel à wait(c).
3. Une file d'attente des processus signalés (éventuellement), pour les processus suspendus suite à l'exécution d'une opération signal(x). Si cette file est implémentée (sémantique de signalement strict), elle possède une priorité supérieure à la file d'attente d'entrée classique.

Question 5 - Création de processus en C

Le fragment de code extrait du document source comporte une erreur de parenthèses de syntaxe, typique des erreurs de frappe (une parenthèse fermante en trop). Voici le code corrigé, intégré dans un programme C complet et exécutable, qui respecte la logique d'engendrer exactement 6 processus descendants liés à l'ancêtre (soit 7 processus au total).

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

int main() {
    /* L'opérateur logique || (OU) évalue la partie droite uniquement si la partie gauche est fausse (vaut 0, donc le processus fils).
       L'opérateur logique && (ET) évalue la partie droite uniquement si la partie gauche est vraie (différente de 0, donc le père). */
       
    if (fork()) {
        // Exécuté par le processus racine et certains de ses descendants
        ((fork() || (fork() && fork())) && fork());
    } else {
        // Exécuté par le premier processus fils
        fork();
    }
    
    // Le père attend ses enfants pour éviter la création de processus zombies
    while(wait(NULL) > 0);
    
    return 0;
}

Exercice 2 - Synchronisation par pthread_join

Voici un programme complet en C utilisant la bibliothèque Pthread pour calculer la somme des éléments d'une matrice colonne par colonne. Conformément à l'énoncé, la matrice est initialisée par une fonction init_mat, chaque thread gère une colonne et retourne sa somme via pthread_exit, et le thread principal récupère ces valeurs avec pthread_join.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define m 4
#define n 5

// Déclaration globale de la matrice
int M[m][n];

// Fonction demandée par l'énoncé pour initialiser la matrice
void init_mat(int matrice[m][n]) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            matrice[i][j] = 2; // Remplissage d'exemple
        }
    }
}

// Fonction exécutée par chaque thread
void* somme_colonne(void* arg) {
    int j = *((int*) arg);
    int* somme_partielle = malloc(sizeof(int));
    *somme_partielle = 0;
    
    for (int i = 0; i < m; i++) {
        *somme_partielle += M[i][j];
    }
    
    // Retour de la somme partielle
    pthread_exit((void*) somme_partielle);
}

int main() {
    pthread_t threads[n];
    int indices[n];
    int ST = 0; // Somme Totale

    init_mat(M);

    // Lancement des n threads concurrents
    for (int j = 0; j < n; j++) {
        indices[j] = j;
        if (pthread_create(&threads[j], NULL, somme_colonne, &indices[j]) != 0) {
            perror("Erreur lors de la création du thread");
            return 1;
        }
    }

    // Récupération des sommes partielles
    for (int j = 0; j < n; j++) {
        void* ret;
        pthread_join(threads[j], &ret);
        ST += *((int*) ret);
        free(ret); // Libération de la mémoire allouée par le thread
    }

    printf("La somme totale des éléments de la matrice est : %d\n", ST);
    
    return 0;
}

Exercice 3 - Ordonnancement

Question 1 - Ordonnancement préemptif (Cas 1)

Règles appliquées : Priorité P3 (3) > P2 (2) > P1 (1). L'ordonnancement est préemptif.

Déroulement détaillé :

• t=0 à 2 : P1 (seul prêt) s'exécute (Code A) → A A
• t=2 à 3 : P1 prend X et commence sa Section Critique (SC) → X
• t=3 : P2 arrive (priorité 2 > 1). P2 préempte P1.
• t=3 à 5 : P2 s'exécute (Code A) → A A
• t=5 : P2 demande X (occupé par P1). P2 se bloque. P1 reprend.
• t=5 à 8 : P1 continue sa SC → X X X (Fin de sa SC de 4 ut)
• t=8 : P1 libère X. P2 est débloqué et préempte immédiatement P1. P2 prend X puis Y.
• t=8 à 10 : P2 commence sa SC avec les 2 sémaphores → 2 2
• t=10 : P3 arrive (priorité 3 > 2). P3 préempte P2.
• t=10 à 12 : P3 s'exécute (Code A) → A A
• t=12 : P3 demande Y (occupé par P2). P3 se bloque. P2 reprend.
• t=12 à 14 : P2 termine sa SC → 2 2
• t=14 : P2 libère Y (P3 se débloque mais se bloque juste après sur X que P2 détient encore), puis P2 libère X. P3 se débloque et préempte P2.
• t=14 à 18 : P3 exécute toute sa SC → 2 2 2 2
• t=18 à 21 : P3 libère les sémaphores et termine avec le Code B → B B B. P3 est terminé.
• t=21 à 24 : P2 reprend et termine avec le Code B → B B B. P2 est terminé.
• t=24 à 27 : P1 reprend et termine avec le Code B → B B B. P1 est terminé.

Diagramme de Gantt synthétisé :

Période (ut)	00-02	02-03	03-05	05-08	08-10	10-12	12-14	14-18	18-21	21-24	24-27
Processus actif	P1	P1	P2	P1	P2	P3	P2	P3	P3	P2	P1
État exécuté	A A	X	A A	X X X	2 2	A A	2 2	2 2 2 2	B B B	B B B	B B B

Calculs :

a) Temps de réponse (TR) (Date de fin - Date d'arrivée)

• TR P1 : 27 - 0 = 27 ut
• TR P2 : 24 - 3 = 21 ut
• TR P3 : 21 - 10 = 11 ut
• Temps de réponse moyen : (27 + 21 + 11) / 3 = 59 / 3 = 19,67 ut (ou 19 2/3)

b) Temps d'attente (TA) (TR - Temps d'exécution total de 9 ut)

• TA P1 : 27 - 9 = 18 ut
• TA P2 : 21 - 9 = 12 ut
• TA P3 : 11 - 9 = 2 ut
• Temps d'attente moyen : (18 + 12 + 2) / 3 = 32 / 3 = 10,67 ut

c) Rendement du CPU

• Rendement = (Temps utile total) / (Temps total) = (3 processus × 9 ut) / 27 ut = 27 / 27 = 100% (1/9 jobs/ut comme précisé par la correction officielle).

Question 2 - Ordonnancement avec nouvelles priorités et arrivées (Cas 2)

Nouvelles règles : P1 (Prio 1, t=0) ; P2 (Prio 3, t=6) ; P3 (Prio 2, t=3). Priorité : P2 > P3 > P1.

Déroulement :

• t=0 à 2 : P1 s'exécute (Code A) → A A
• t=2 à 3 : P1 prend X et exécute sa SC → X
• t=3 : P3 arrive (prio 2 > 1) et préempte P1.
• t=3 à 5 : P3 s'exécute (Code A) → A A
• t=5 : P3 prend Y, puis demande X (occupé par P1). P3 se bloque. P1 reprend.
• t=5 à 6 : P1 exécute sa SC → X
• t=6 : P2 arrive (prio 3 > 1) et préempte P1.
• t=6 à 8 : P2 s'exécute (Code A) → A A
• t=8 : P2 demande X (occupé par P1). P2 se bloque. P1 reprend.
• t=8 à 10 : P1 termine sa SC de 4 ut → X X
• t=10 : P1 libère X. P2 et P3 attendent X. P2 a la priorité la plus haute (3 > 2), c'est donc P2 qui obtient X.
• t=10 (suite) : P2 possède maintenant X et demande Y. Cependant, Y est occupé par P3 (depuis t=5). P2 se bloque.
• P3 attend X qui est possédé par P2. P2 attend Y qui est possédé par P3. C'est un état de Deadlock.

Remarque par rapport à la correction officielle : Bien que P1 ne soit pas bloqué et puisse terminer son code B entre t=10 et t=13, les processus P2 et P3 entrent dans un interblocage circulaire insoluble. Le corrigé officiel comptabilise donc :

• Débit du système (Job throughput) : 0
• Temps de réponse moyen : Infini.

Conclusion : Le système subit un interblocage (deadlock) à t=10.

Question 3 - Solution à l'interblocage

Pour empêcher l'interblocage identifié à la question 2, il faut prévenir la condition d'attente circulaire.

Modification proposée : Il faut respecter strictement le même ordre d’appel des sémaphores d'exclusion mutuelle (mutex) dans les processus P2 et P3. Ainsi, il suffit d'inverser l’ordre des appels P(Y) et P(X) dans le code de P3, pour qu'il demande toujours X en premier puis Y, exactement comme P2.

Exercice 4 - Synchronisation

Question 1 - Différence avec le modèle lecteurs/rédacteurs

Dans le modèle standard des lecteurs/rédacteurs, on ne peut trouver qu'un seul rédacteur à la fois en train d'occuper la ressource partagée. Dans le problème des trains, la ressource (la voie) peut être occupée par plusieurs processus (trains) en même temps, et ce principe est valable pour les deux classes (T-AB et T-BA), tant qu'ils circulent dans le même sens. Les deux classes agissent comme des "lecteurs" vis-à-vis d'elles-mêmes, mais comme des "rédacteurs" vis-à-vis de l'autre classe.

Question 2 - Explication de la solution erronée

La solution proposée est incorrecte car elle utilise un seul et unique compteur par classe (nbA et nbB) pour comptabiliser à la fois les trains en cours de circulation et ceux qui sont en attente. Cela conduit à un risque d'interblocage (deadlock).

Exemple de scénario problématique :

1. Le train A1 arrive : nbA passe à 1, nbB vaut 0. Il circule.
2. Le train B1 arrive : nbB passe à 1. Puisque nbA > 0, B1 se bloque sur la variable de condition cb.
3. Le train A2 arrive : nbA passe à 2. Puisque nbB > 0 (B1 l'a incrémenté bien qu'il soit bloqué), A2 se bloque sur ca.
4. Le train A1 sort de la voie. Il décrémente nbA qui passe à 1. Puisque nbA n'est pas égal à 0, il n'émet aucun signal pour réveiller B1. Résultat : Tous les trains suivants restent bloqués indéfiniment.

Question 3 - Correction de la solution

Pour corriger ce moniteur, il est nécessaire de séparer le décompte des trains actifs sur la voie de celui des trains en attente, en introduisant les variables attA et attB. Notez également le réveil en cascade (un train qui entre réveille les autres trains attendant dans la même direction).

Monitor AB {
    int nbA = 0, nbB = 0;
    int attA = 0, attB = 0;
    condition ca, cb;

    void Entree_A() {
        if (nbB > 0) { 
            attA++; 
            wait(ca); 
        }
        nbA++; 
        // Réveil en cascade des autres trains allant de A vers B
        if (attA > 0) { 
            attA--; 
            signal(ca); 
        }
    }

    void Sortie_B() {
        nbA--;
        // Si plus aucun train de A vers B n'est sur la voie, 
        // on laisse passer les trains de B vers A en attente
        if (nbA == 0) { 
            if (attB > 0) { 
                attB--; 
                signal(cb); 
            } 
        }
    }

    void Entree_B() {
        if (nbA > 0) { 
            attB++; 
            wait(cb); 
        }
        nbB++; 
        // Réveil en cascade des autres trains allant de B vers A
        if (attB > 0) { 
            attB--; 
            signal(cb); 
        }
    }

    void Sortie_A() {
        nbB--;
        // Si plus aucun train de B vers A n'est sur la voie, 
        // on laisse passer les trains de A vers B en attente
        if (nbB == 0) { 
            if (attA > 0) { 
                attA--; 
                signal(ca); 
            } 
        }
    }
}

Méthode

Face à une épreuve de Systèmes d'Exploitation et de Programmation Concurrente :

1. Traces de Gantt : Soyez méticuleux avec les timestamps d'arrivée et les préemptions. Dans les exercices avec sémaphores, n'oubliez pas qu'un processus préempté conserve les sémaphores qu'il a déjà acquis. C'est la source numéro un d'interblocages et d'inversions de priorité.
2. Identification des Interblocages : Ne vous arrêtez pas au moment où un processus se termine, vérifiez systématiquement l'état des files d'attente des ressources. Si deux processus forment un graphe d'attente circulaire (P2 attend Y possédé par P3, P3 attend X possédé par P2), marquez l'arrêt, déclarez le deadlock, et n'essayez pas de forcer la suite de l'exécution.
3. Problèmes de Synchronisation : Lorsque vous manipulez des moniteurs avec des catégories multiples, ayez toujours le réflexe de séparer les compteurs "en cours d'exécution" des compteurs "en attente". C'est l'outil indispensable pour éviter d'empêcher l'accès à une ressource vide. Tracez mentalement le pire des scénarios avec des arrivées alternées (A, puis B, puis A).
4. Code en C (Fork) : Analysez l'arbre de création étape par étape en vous rappelant que les opérateurs logiques && et || court-circuitent (short-circuit evaluation). Si la partie gauche d'un || (le PID pour le processus père) est évaluée à vrai, la partie droite ne sera jamais exécutée par lui.