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

Questions de Cours

Il est à noter que l'énoncé indique "8 x 1 point" pour les questions de cours, mais seules 7 questions sont imprimées sur le sujet (la question 7 étant divisée en deux parties A et B). Les réponses ci-dessous couvrent l'intégralité des questions fournies.

Question 1 - Multithreading et multiprogrammation

Le multithreading désigne l'exécution concurrente ou parallèle de plusieurs fils d'exécution (threads) partageant le même espace d'adressage à l'intérieur d'un seul et même processus. La multiprogrammation (ou multitâche), en revanche, est l'exécution concurrente de plusieurs processus distincts et indépendants (ayant chacun leur propre espace mémoire) sur un processeur.

Question 2 - Processus vs Thread

• Différences : Un processus est une unité structurelle lourde définie par ses propres segments (Code, Données, Pile) et un contexte d'exécution isolé. Un thread (processus léger) est une unité d'exécution qui possède sa propre pile et son propre compteur ordinal, mais qui partage l'espace d'adressage mémoire (code et données) avec les autres threads de son processus parent.
• Privilège en mémoire partagée : Dans une application partageant des données, il faut privilégier les threads. Leur création et la commutation de contexte entre eux sont beaucoup moins coûteuses en performances, et le partage de la mémoire est natif.

Question 3 - Thread Control Bloc (TCB)

Note : La correction officielle a été tronquée sur ce point. Voici la définition technique attendue. Tout comme le PCB (Process Control Block) contient toutes les informations nécessaires au système pour gérer un processus (PID, état, limites mémoire), le TCB (Thread Control Block) est la structure de données utilisée par le noyau pour gérer un thread. Il contient l'identifiant du thread (TID), l'état courant du thread, le compteur ordinal (l'adresse de la prochaine instruction), les registres du processeur et les pointeurs vers sa pile d'exécution.

Question 4 - Création d'un nouveau processus sous Unix

Note : La correction officielle a également été tronquée ici. Voici la suite logique de la réponse. Lorsqu'il se charge de la création d'un nouveau processus (généralement via l'appel système fork()), le noyau Unix effectue les actions suivantes : il alloue une nouvelle entrée dans la table des processus (nouveau PCB), attribue un identifiant unique (PID), crée une copie exacte de l'espace d'adressage du processus parent (code, données, pile, descripteurs de fichiers), puis place le nouveau processus (le fils) dans la file d'attente des processus éligibles (prêts à être exécutés).

Question 5 - Ressource critique

Une ressource critique est une ressource partagée (variable, fichier, périphérique) qui ne peut être accédée que par un seul processus ou thread à la fois sous peine de corruption des données. Pour autoriser son accès, le système d'exploitation doit assurer la propriété d'exclusion mutuelle : garantir qu'un seul thread s'y trouve à un instant t.

Question 6 - Moyens de synchronisation pour les threads

Les quatre moyens principaux de synchronisation pour les threads POSIX sont :

1. La jointure de threads (attente de terminaison via pthread_join()).
2. Les verrous d'exclusion mutuelle (Mutex).
3. Les sémaphores.
4. Les variables conditionnelles (mécanisme de type moniteur).

Question 7 - États et transitions d'un processus

A) Les trois états :

• Éligible (Prêt) : Le processus a toutes les ressources nécessaires pour s'exécuter, il attend juste que le processeur (CPU) lui soit alloué.
• Élu (En exécution) : Le processus possède le processeur et ses instructions sont en train d'être exécutées.
• Bloqué (En attente) : Le processus ne peut pas s'exécuter car il attend qu'un événement externe se produise (comme la fin d'une opération d'Entrée/Sortie).

B) Les transitions :

• Activation (Éligible -> Élu) : A lieu lorsque l'ordonnanceur (scheduler) du noyau choisit ce processus dans la file d'attente et lui alloue le processeur.
• Préemption (Élu -> Éligible) : A lieu lorsque le quantum de temps alloué au processus est écoulé, ou qu'un processus de plus forte priorité devient éligible.
• Attente (Élu -> Bloqué) : A lieu lorsque le processus demande une opération lente (lecture disque, attente réseau) ou une ressource indisponible.
• Fin d'attente (Bloqué -> Éligible) : A lieu lorsque l'événement attendu s'est produit (l'Entrée/Sortie est terminée, la ressource est libérée).

Programmation concurrente

Exercice 1 - Arborescence fork()

#include <unistd.h>
int main(void)
{
    fork() && (fork() || fork());
    sleep(2);
    return 0;
}

Pour comprendre le nombre de processus, il faut se rappeler deux règles en C :

1. fork() renvoie le PID (une valeur non nulle, donc VRAI) au processus père, et 0 (FAUX) au processus fils.
2. L'évaluation paresseuse (court-circuit) : dans A && B, B n'est évalué que si A est VRAI. Dans A || B, B n'est évalué que si A est FAUX.

Déroulement : Soit P0 le processus père initial. Il évalue l'expression de gauche à droite.

• P0 exécute le premier fork() (appelons-le A). Il crée le processus fils P1.
  • Pour P0, A est VRAI. P0 doit donc évaluer la suite : (fork() || fork()).
  • Pour P1, A est FAUX (0). À cause du &&, P1 n'évalue pas le reste de la ligne et passe directement au sleep(2).
• P0 exécute le deuxième fork() (appelons-le B). Il crée le processus fils P2.
  • Pour P0, B est VRAI. À cause du ||, P0 n'évalue pas le reste de l'expression (le troisième fork()) et passe au sleep(2).
  • Pour P2, B est FAUX (0). P2 doit évaluer la partie droite du ||.
• P2 exécute le troisième fork() (appelons-le C). Il crée le processus fils P3.
  • Pour P2, C est VRAI. Il passe au sleep(2).
  • Pour P3, C est FAUX (0). Il passe au sleep(2).

Résultat : Le programme engendre 3 nouveaux processus (P1, P2, P3), pour un total de 4 processus en cours d'exécution.

Arborescence : P0 (Père) |-- P1 (Fils issu du premier fork) |-- P2 (Fils issu du deuxième fork) |-- P3 (Fils de P2, issu du troisième fork)

Exercice 2 - Variables partagées

Les deux processus exécutent les instructions suivantes (que nous numéroterons pour la clarté) : Processus PA : I1: i=k; | I2: i=i+1; | I3: k=i; | I4: printf("k=%d",k); Processus PB : J1: j=k; | J2: j=j+4; | J3: k=j; | J4: printf("k=%d",k); Initialisation : k=1.

Question 1 - Résultats possibles

• R1 (K=2 pour PA, K=2 pour PB) : Oui, c'est possible.

  • Trace d'exécution : PA lit k=1 (i=1). PB lit k=1 (j=1). PA calcule i=2 et écrit k=2. PB calcule j=5 et écrit k=5. Ensuite, PA écrase la valeur avec k=2. PA affiche 2. PB lit k en mémoire pour l'afficher et trouve 2. Il affiche 2.
  • Ordre précis : I1, J1, I2, J2, J3, I3, I4, J4. (Ce résultat démontre une situation de compétition ou "race condition").

• R2 (K=2 pour PA, K=6 pour PB) : Oui, c'est possible.

  • Trace d'exécution : PA s'exécute entièrement, puis PB s'exécute entièrement.
  • Ordre précis : I1, I2, I3, I4 (PA écrit k=2 et affiche 2). Ensuite J1, J2, J3, J4 (PB lit k=2, calcule j=6, écrit k=6 et affiche 6).

• R3 (K=5 pour PA, K=2 pour PB) : Non, c'est impossible.

  • Justification : Pour que PA affiche 5, il faut que k vaille 5 au moment de I4. La valeur 5 ne peut être produite que par PB (si PB lit 1 et ajoute 4). Cela implique que PB a terminé son écriture (J3). Pour que PB affiche 2, il faut que PA ait écrit 2 après que PB ait écrit 5. Mais si PA écrit 2 en dernier, alors k vaut 2, et PA afficherait 2 (et non 5). L'état croisé des affichages est mathématiquement bloqué par les valeurs produites.

Question 2 - Autres exécutions concurrentes possibles

Note sur la correction officielle : Le corrigé source propose la séquence I1; I2; I3; J1; J2; J3; J4; I4 pour obtenir (5,5). C'est une erreur de la source : si I3 écrit k=2 avant que J1 ne lise, PB lira k=2, écrira k=6, et les deux afficheront (6,6). Voici les véritables traces pour obtenir les résultats valides.

1. Exécution séquentielle inverse (K=5 pour PB, K=6 pour PA) : PB s'exécute en premier en entier (lit 1, écrit 5, affiche 5). Puis PA s'exécute (lit 5, ajoute 1, écrit 6, affiche 6).
2. Affichage simultané de la valeur écrasée (K=5 pour PA, K=5 pour PB) :
   • PA lit k=1 (i=1).
   • PB lit k=1 (j=1).
   • PA calcule i=2. PB calcule j=5.
   • PA écrit k=2 (I3).
   • PB écrit k=5 (J3).
   • PB affiche K=5 (J4).
   • PA affiche la valeur actuelle de la mémoire, K=5 (I4).
   • Ordre : I1, I2, J1, J2, I3, J3, J4, I4.

Exercice 3 - Reader/Writer Multithread

Note sur le code source : Plusieurs erreurs de syntaxe C ont été corrigées dans les extraits ci-dessous pour garantir la compilation (ajout des pointeurs dans les signatures, inclusion des arguments pour pthread et semaphores).

Question 1 - Origine de l'erreur de segmentation

L'erreur survient à cause d'une situation de compétition (race condition) lors de l'initialisation du pointeur. L'écrivain alloue la mémoire avec pointer = malloc(sizeof(int));. S'il est préempté par l'ordonnanceur juste après l'allocation et avant d'avoir exécuté *pointer = rand();, le thread lecteur prend la main. Le lecteur voit que pointer != NULL, tente de l'afficher (lisant une mémoire non initialisée), puis exécute free(pointer). Lorsque l'écrivain reprend son exécution, il tente d'écrire la valeur aléatoire via *pointer = rand(); dans un espace mémoire qui vient d'être libéré. Cela provoque une "Erreur de segmentation" (Segfault).

Question 2 - Résolution par sémaphore

Pour régler cela, nous ajoutons un sémaphore configuré en mode Mutex (initialisé à 1 dans le programme principal) pour rendre atomique le bloc de vérification, d'allocation/libération et d'écriture/lecture.

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

int *pointer = NULL;
sem_t sem; // À initialiser avec sem_init(&sem, 0, 1) dans le main

void *writer_thread(void *arg) {
    while (1) {
        sem_wait(&sem);
        if (pointer == NULL) {
            pointer = malloc(sizeof(int));
            *pointer = rand();
        }
        sem_post(&sem);
    }
    return NULL;
}

void *reader_thread(void *arg) {
    while (1) {
        sem_wait(&sem);
        if (pointer != NULL) {
            printf("pointer = %d\n", *pointer);
            free(pointer);
            pointer = NULL;
        }
        sem_post(&sem);
    }
    return NULL;
}

Question 3 - Solution sans synchronisation

• Pour une seule paire lecteur/écrivain : Oui, c'est théoriquement possible en utilisant une variable locale. L'écrivain alloue et initialise complètement un pointeur local, puis assigne ce pointeur à la variable globale partagée en une seule instruction atomique : int *local = malloc(sizeof(int)); *local = rand(); pointer = local; Le lecteur ne verra le pointeur que lorsqu'il sera entièrement initialisé.
• Pour plusieurs paires lecteur/écrivain : Non. Sans exclusion mutuelle stricte, deux écrivains pourraient évaluer pointer == NULL simultanément, allouer chacun de la mémoire, et écraser le pointeur l'un de l'autre, provoquant une fuite de mémoire (memory leak). De même, deux lecteurs pourraient tenter de faire un free() sur le même pointeur (double free). Un mécanisme de synchronisation est obligatoire.

Question 4 - Variable conditionnelle

La variable conditionnelle permet de bloquer efficacement un thread en attendant que la ressource soit prête, évitant l'attente active du while(1). Note : Il est impératif d'utiliser une boucle while (et non un simple if) autour du pthread_cond_wait pour se protéger des réveils intempestifs (spurious wakeups), une règle de base de la programmation POSIX.

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

int *pointer = NULL;
pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

void *writer_thread(void *arg) {
    while (1) {
        pthread_mutex_lock(&mut);
        // On attend tant que le lecteur n'a pas consommé
        while (pointer != NULL) { 
            pthread_cond_wait(&cond, &mut);
        }
        
        pointer = malloc(sizeof(int));
        *pointer = rand();
        
        pthread_cond_signal(&cond); // Alerte le lecteur
        pthread_mutex_unlock(&mut);
    }
    return NULL;
}

void *reader_thread(void *arg) {
    while (1) {
        pthread_mutex_lock(&mut);
        // On attend tant que l'écrivain n'a pas produit
        while (pointer == NULL) {
            pthread_cond_wait(&cond, &mut);
        }
        
        printf("Valeur: %d\n", *pointer);
        free(pointer);
        pointer = NULL;
        
        pthread_cond_signal(&cond); // Alerte l'écrivain
        pthread_mutex_unlock(&mut);
    }
    return NULL;
}

Question 5 - Le thread principal (main)

Le code du main manquait dans la correction source. Le voici complété pour assurer le fonctionnement et l'initialisation des primitives POSIX.

int main(void) {
    pthread_t writer, reader;
    
    // Initialisation du mutex et de la condition (déjà fait statiquement 
    // ci-dessus, mais voici la méthode dynamique demandée en annexe)
    pthread_mutex_init(&mut, NULL);
    pthread_cond_init(&cond, NULL);
    
    // Création des threads
    pthread_create(&writer, NULL, writer_thread, NULL);
    pthread_create(&reader, NULL, reader_thread, NULL);
    
    // Attente de terminaison (bien que les threads soient des boucles infinies ici)
    pthread_join(writer, NULL);
    pthread_join(reader, NULL);
    
    // Nettoyage des ressources
    pthread_mutex_destroy(&mut);
    pthread_cond_destroy(&cond);
    
    return 0;
}

Méthode

Pour réussir les épreuves de Systèmes d'exploitation et Programmation Concurrente, voici les réflexes à adopter :

• Tracez les entrelacements : Ne devinez jamais le comportement d'un code concurrent. Prenez une feuille de brouillon et dessinez deux colonnes (Thread A, Thread B). Avancez instruction par instruction, en simulant la pire préemption possible (par exemple, couper l'exécution juste après une lecture de pointeur mais avant son utilisation).
• Connaissez vos primitives C/POSIX : Un sémaphore doit toujours encadrer la section critique (wait en entrée, post en sortie). Une variable conditionnelle doit TOUJOURS être utilisée à l'intérieur d'un verrou Mutex, et évaluée dans une boucle while pour contrer les réveils spontanés. Faites très attention à la syntaxe, l'API POSIX utilise massivement les pointeurs (&mut).
• La généalogie des processus : Lors des exercices sur fork(), rappelez-vous que les opérateurs logiques && et || en C sont paresseux. Tracez l'arbre des processus fils en validant ou invalidant l'évaluation droite de l'expression.