Devoir Surveillé - Systèmes d’exploitation

Exercice 1 : Questions de cours

Cet exercice vise à valider votre compréhension des concepts fondamentaux des systèmes d'exploitation. La précision du vocabulaire est essentielle.

Question 1 - Signification et rôle du PCB et du scheduler

• PCB (Process Control Block) : C'est une structure de données (un bloc de contrôle) gérée par le noyau du système d'exploitation. Il contient toutes les informations contextuelles nécessaires pour gérer un processus (son état, son identifiant, la valeur de ses registres, son espace mémoire, etc.). C'est la "carte d'identité" et le carnet de bord d'un processus.
• Scheduler (Ordonnanceur) : C'est le module du système d'exploitation chargé d'élire le prochain processus prêt à s'exécuter sur le processeur. Il applique une politique d'ordonnancement (comme Tourniquet, Priorité, etc.) pour allouer équitablement ou efficacement le temps CPU.

Question 2 - Différences conceptuelles

Voici la distinction pour chaque paire de termes, en retenant le critère technique principal qui les sépare :

1. Processus vs Thread : Un processus est une unité d'allocation de ressources (code, données, pile, espace mémoire isolé). Un thread (processus léger) est une unité d'exécution au sein d'un processus ; les threads d'un même processus partagent la même mémoire (code et données), mais ont chacun leur propre pile d'exécution.
2. Noyau vs Micronoyau : Un noyau (monolithique) regroupe tous les services du système (gestion mémoire, fichiers, pilotes) dans un espace mémoire unique et privilégié. Un micronoyau ne conserve que les fonctions minimales absolues (communication inter-processus, ordonnancement de base) ; le reste est déporté dans l'espace utilisateur sous forme de serveurs, chargés à la demande.
3. Ressource partagée vs Ressource critique : Une ressource partagée est accessible par plusieurs processus. Elle devient une ressource critique lorsqu'elle exige un accès exclusif (un seul processus à la fois, le nombre de points d'accès est de 1) pour éviter les incohérences de données.
4. Mode maître (kernel mode) vs Mode esclave (user mode) : Le mode maître possède tous les privilèges et permet d'exécuter n'importe quelle instruction matérielle (accès direct à la mémoire, aux périphériques). Le mode esclave est restreint pour les applications courantes, protégeant ainsi le système contre les erreurs ou comportements malveillants.
5. Synchronisation vs Communication : La synchronisation consiste à coordonner l'ordre d'exécution de processus partageant une même mémoire (pour éviter les conflits). La communication implique l'échange de données entre processus distincts, généralement par passage de messages, sans forcément partager d'espace mémoire.
6. Attente active vs Attente passive (blocage) : Une attente active monopolise le processeur (par exemple via une boucle vide while(occupee);) en vérifiant continuellement une condition. Une attente passive libère le processeur ; le processus est mis en état "bloqué" par le système jusqu'à ce qu'un signal le réveille.
7. Famine vs Excès de politesse : La famine se produit lorsqu'un processus attend indéfiniment une ressource car l'ordonnanceur privilégie sans cesse d'autres processus (souvent plus prioritaires). L'excès de politesse (ou livelock) survient quand des processus cèdent volontairement et continuellement leur tour pour éviter un interblocage, n'avançant finalement jamais.
8. wait(pid, etat) vs sleep(temps) : wait() est un appel système de synchronisation où un processus parent se bloque en attendant la fin de l'exécution de son processus fils. sleep() est une simple temporisation où le processus demande à être suspendu pour une durée déterminée, indépendamment de toute filiation.
9. Processus zombi vs Processus orphelin : Un zombi a terminé son exécution, mais son parent n'a pas encore lu son code de retour (via wait), son PCB occupe donc toujours de la place dans le système. Un orphelin est un processus encore en cours d'exécution, mais dont le parent est mort avant lui ; il est généralement rattaché au processus racine (init).
10. Sémaphore vs Moniteur : Tous deux gèrent la synchronisation. Le sémaphore est une primitive de bas niveau (un entier avec des opérations atomiques P et V) où le programmeur doit gérer manuellement l'exclusion mutuelle. Le moniteur est un concept de plus haut niveau (souvent intégré au langage de programmation) qui garantit implicitement l'exclusion mutuelle sur ses méthodes.

Question 3 - Avantages du multithreading par rapport au multitâche

Le multithreading (plusieurs threads dans un processus) offre plusieurs avantages sur le multitâche lourd (plusieurs processus distincts) :

• Performance et rendement : Le changement de contexte entre threads est beaucoup plus rapide et moins coûteux pour le CPU qu'entre processus.
• Partage de ressources naturel : Les threads partagent nativement l'espace mémoire de leur processus, facilitant la communication sans appels système complexes.
• Réactivité : Une application peut continuer de répondre à l'utilisateur via un thread pendant qu'un autre effectue une tâche bloquante.

Question 4 - Les sémaphores pour les processus distants (systèmes distribués) ?

Non. Les sémaphores classiques reposent fondamentalement sur une variable entière située dans une mémoire partagée accessible par tous les processus concernés. Dans un système distribué, les processus s'exécutent sur des machines physiques différentes sans mémoire physique commune. La synchronisation doit alors se faire par passage de messages ou via des algorithmes distribués (comme les horloges logiques).

Exercice 2 : IPC - Moniteur

Analyse de l'énoncé et correction du code

Le but est d'écrire un moniteur qui gère l'allocation de 3 imprimantes en favorisant les processus avec la priorité la plus haute. La proposition de correction incluse dans le document source contient du pseudo-code mélangé avec des notions de C et de Java.

Pour respecter le fonctionnement d'un moniteur et fournir un code qui s'exécute de manière valide (comme exigé), nous allons écrire ce moniteur en langage Java. Java implémente le concept de moniteur à l'aide des blocs synchronized ou des verrous explicites (ReentrantLock et Condition). Le pseudo-code de la correction utilise wait(C) et broadcast(C), ce qui correspond à la méthode Mesa des moniteurs (nécessitant une boucle while pour revérifier la condition au réveil).

Note pédagogique sur la correction fournie : La correction de l'énoncé utilise while (!Dispo && (At_Proc[0] != id)). En C ou Java, !Dispo n'est valide que pour un booléen. Puisque Dispo est un entier, il faut écrire Dispo == 0.

Voici le code complet, valide et exécutable, respectant fidèlement la logique et les variables du sujet d'examen :

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class PrinterMonitor {
    // Variables demandées par l'énoncé
    private int dispo = 3;
    private int nb_At = 0;
    private int[] at_Proc = new int[100]; // Taille arbitraire max pour l'exemple
    
    // Le moniteur nécessite un verrou pour l'exclusion mutuelle 
    // et une variable condition 'C'
    private final Lock monitorLock = new ReentrantLock();
    private final Condition C = monitorLock.newCondition();

    // Fonction utilitaire factice pour remplacer l'appel système de l'OS
    private int getpid() {
        return (int) Thread.currentThread().getId();
    }

    // Procédure de tri demandée (tri par priorité décroissante)
    // Pour simplifier cet exemple exécutable, on simule un tri simple.
    // Dans un vrai OS, l'ID serait mappé à une priorité.
    private void sort(int[] array, int size) {
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                // On trie arbitrairement par ID pour simuler le comportement
                if (array[j] < array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public void allouer() {
        monitorLock.lock(); // Entrée dans le moniteur (exclusion mutuelle)
        try {
            if (dispo > 0 && nb_At == 0) {
                dispo--;
                return; // Imprimante allouée immédiatement
            }

            int id = getpid();
            at_Proc[nb_At] = id;
            nb_At++;
            sort(at_Proc, nb_At);

            // Tant qu'il n'y a pas d'imprimante OU que je ne suis pas le plus prioritaire (index 0)
            while (dispo == 0 || at_Proc[0] != id) {
                try {
                    C.await(); // wait(C) : libère le verrou et met en attente
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }

            // Réveil et condition vérifiée : on alloue l'imprimante
            // On retire le processus actuel de la file d'attente
            at_Proc[0] = at_Proc[nb_At - 1]; 
            nb_At--;
            sort(at_Proc, nb_At);
            dispo--;

        } finally {
            monitorLock.unlock(); // Sortie du moniteur
        }
    }

    public void liberer() {
        monitorLock.lock();
        try {
            dispo++;
            C.signalAll(); // broadcast(C) : réveille tous les processus en attente
        } finally {
            monitorLock.unlock();
        }
    }
}

Exercice 3 : Synchronisation par sémaphores

Note : La proposition de correction pour cet exercice était absente du document source fourni. La solution ci-dessous est construite à partir de l'énoncé de l'examen afin de répondre à toutes les questions posées, en traduisant le pseudo-code attendu en véritable code C compilable, utilisant la bibliothèque POSIX pour les sémaphores.

Analyse et définition des variables

L'assemblée nécessite un quorum pour commencer : 2 × (N ÷ 3). Il nous faut protéger l'accès concurrent aux variables globales (Nb_Votant et Nb_Vote) et bloquer l'exécution jusqu'à ce que certaines conditions soient remplies (atteinte du quorum, puis fin des votes).

Nous définissons 4 sémaphores :

• Mutex_Votant (initialisé à 1) : Protège l'incrémentation de Nb_Votant.
• Mutex_Vote (initialisé à 1) : Protège l'incrémentation de Nb_Vote (l'urne).
• Attente_Quorum (initialisé à 0) : Bloque les députés arrivant tôt jusqu'à ce que le quorum soit réuni.
• Attente_Depouillement (initialisé à 0) : Bloque le processus de signature jusqu'à ce que tous les présents aient voté.

Solution exécutable (Langage C avec Pthreads)

Le code ci-dessous remplit les "trous" (pointillés) du tableau de l'énoncé. Les fonctions P() et V() classiques de l'algorithmique sont remplacées par leurs équivalents C fonctionnels : sem_wait() et sem_post().

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

#define N 217
#define Quorum (2 * (N / 3)) // Vaut 144

int Nb_Votant = 0;
int Nb_Vote = 0;

// Variables pour le dépouillement (simulées)
int Nb_favorable = 0;
int Nb_defavorable = 0;

// Déclaration des sémaphores
sem_t Mutex_Votant;
sem_t Mutex_Vote;
sem_t Attente_Quorum;
sem_t Attente_Depouillement;

// Fonctions factices pour simuler les actions de l'énoncé
void Faire_choix() { /* L'élu réfléchit */ }
void Deposer_bulletin_vote() { /* Insertion dans l'urne */ }
void depouiller(int* fav, int* defav) { /* Lecture des bulletins */ }

// ---------------------------------------------------------
// Processus Se_Reunir (Exécuté par chaque élu arrivant)
// ---------------------------------------------------------
void* Se_Reunir(void* arg) {
    sem_wait(&Mutex_Votant);   // Début protection Nb_Votant
    Nb_Votant++;
    
    if (Nb_Votant < Quorum) {
        sem_post(&Mutex_Votant);
        sem_wait(&Attente_Quorum); // Attend que le quorum soit atteint
    } 
    else if (Nb_Votant == Quorum) {
        // Le quorum est atteint par CET élu, il réveille les autres
        for (int i = 1; i < Quorum; i++) {
            sem_post(&Attente_Quorum);
        }
        sem_post(&Mutex_Votant);
    } else {
        // Pour les retardataires arrivant après le quorum
        sem_post(&Mutex_Votant);
    }
    return NULL;
}

// ---------------------------------------------------------
// Processus Voter (Exécuté par chaque élu présent)
// ---------------------------------------------------------
void* Voter(void* arg) {
    Faire_choix();
    
    sem_wait(&Mutex_Vote);     // Début protection de l'urne
    Deposer_bulletin_vote();
    Nb_Vote++;
    
    if (Nb_Votant == Nb_Vote) {
        // Le dernier votant réveille le dépouillement
        sem_post(&Attente_Depouillement);
    }
    sem_post(&Mutex_Vote);     // Fin protection de l'urne
    
    return NULL;
}

// ---------------------------------------------------------
// Processus Signer_texte_loi
// ---------------------------------------------------------
void* Signer_texte_loi(void* arg) {
    // Attend que TOUS les votants aient déposé leur bulletin
    sem_wait(&Attente_Depouillement);
    
    // Le passage par adresse & est nécessaire en C pour modifier les variables
    depouiller(&Nb_favorable, &Nb_defavorable);
    
    if (Nb_favorable > (Nb_Vote * 51 / 100)) {
        printf("Le Président signe le texte de loi.\n");
    }
    return NULL;
}

int main() {
    // Initialisation des sémaphores
    sem_init(&Mutex_Votant, 0, 1);
    sem_init(&Mutex_Vote, 0, 1);
    sem_init(&Attente_Quorum, 0, 0);
    sem_init(&Attente_Depouillement, 0, 0);
    
    // Le reste du main consisterait à instancier les threads (non exigé par l'énoncé)
    return 0;
}

Méthode

Face à une épreuve de Systèmes d'Exploitation, voici la démarche à adopter :

1. Vocabulaire exact : Les définitions de l'exercice 1 ne supportent pas l'à-peu-près. Un thread n'est pas "un sous-processus", c'est une "unité d'exécution partageant l'espace mémoire". Apprenez vos paires d'opposition (ex: Actif/Passif, Shared/Critique) en ciblant le critère discriminant.
2. Synchronisation - Identifiez la ressource : Avant d'écrire un sémaphore ou un moniteur, posez-vous toujours deux questions : "Quelle est la variable partagée ?" et "Qui risque de la modifier en même temps ?". Tout compteur (comme Nb_Votant ou Dispo) doit être protégé par une exclusion mutuelle.
3. Mesa vs Hoare : Dans l'exercice 2, l'utilisation de la boucle while lors d'un wait(C) est une signature de la sémantique de type "Mesa". Un broadcast réveille tous les processus, mais un seul obtiendra le verrou. La condition (Dispo == 0 ou priorité) ayant pu changer entre le réveil et l'acquisition effective du processeur, le processus doit obligatoirement la re-tester (d'où le while et non un if).
4. Barrières de synchronisation : L'exercice 3 est un grand classique d'une barrière. Le processus qui fait passer la variable globale à la valeur seuil (le quorum) est celui qui a la responsabilité de libérer (via V() ou sem_post()) tous les processus qui s'étaient endormis. Vérifiez toujours la condition de votre if / else if pour vous assurer qu'un seul processus exécutera la boucle de réveil.