Devoir Surveillé - Systèmes d’exploitation Programmation Concurrente

Questions de Cours

Question 1 - Signification et rôle des acronymes PCB et PSW

• PCB (Process Control Block) : C'est le bloc de contrôle de processus. Il s'agit d'une structure de données maintenue par le système d'exploitation pour chaque processus. Il sert à stocker toutes les informations nécessaires à la gestion d'un processus (son identifiant ou PID, son état actuel, les valeurs de ses registres, son compteur ordinal, les informations d'ordonnancement, etc.).
• PSW (Program Status Word) : C'est le mot d'état du processeur. C'est un registre matériel (ou un ensemble de registres) qui sert à contenir des informations vitales sur l'état d'exécution courant du processeur (les drapeaux de retenue, de zéro, de débordement, le mode d'exécution utilisateur ou noyau, et les masques d'interruptions).

Question 2 - Origine de MUTEX et différence avec la synchronisation conditionnelle

• Origine : Le terme MUTEX provient de la contraction de l'anglais "MUTual EXclusion" (Exclusion Mutuelle).
• Différence : Un Mutex est utilisé exclusivement pour protéger une section critique : il garantit qu'un seul thread ou processus à la fois peut accéder à une ressource partagée. Une synchronisation conditionnelle, en revanche, permet de bloquer un processus ou un thread jusqu'à ce qu'une certaine condition logique concernant l'état du système soit remplie (par exemple, attendre qu'une file ne soit plus vide), indépendamment du nombre de threads accédant à la ressource.

Question 3 - Rôles des primitives wait() et pthread_join()

• Rôles : La primitive wait(etat) suspend l'exécution du processus appelant jusqu'à ce que l'un de ses processus fils se termine. La primitive pthread_join(tid, etat) suspend l'exécution du thread appelant jusqu'à ce que le thread cible (identifié par tid) se termine.
• Nécessité : Comme l'indique la correction de la source, ces primitives ne sont pas strictement nécessaires pour l'accomplissement des processus ou des threads. Si elles ne sont pas appelées, un processus fils peut continuer son exécution et devenir orphelin (si son père se termine avant lui). Cependant, leur utilisation est fortement recommandée pour récupérer le code de retour des fils et éviter la création de processus "zombies" dans la table des processus du système d'exploitation.

Question 4 - QCM sur les processus Unix

i. Faux. Un processus Unix ne doit pas obligatoirement avoir le shell comme ancêtre direct ou indirect. Un processus peut très bien avoir init (ou systemd sur des systèmes modernes) comme processus père, notamment dans le cas des démons ou des processus devenus orphelins. ii. Vrai. Deux processus Unix peuvent partager un espace mémoire, mais ils doivent pour cela utiliser explicitement des mécanismes de communication inter-processus (IPC), comme la mémoire partagée (shared memory), ou utiliser des pipes et files de messages déclarés de manière globale. iii. Faux. Un processus qui exécute exit ne termine pas automatiquement ses processus fils. Ces derniers continuent leur exécution de manière indépendante et sont adoptés par le processus init (ils deviennent orphelins). iv. Faux. Contrairement aux threads qui partagent le même espace d'adressage que leur processus conteneur, un processus fils Unix obtient une copie de l'espace d'adressage de son père au moment du fork(). Les deux espaces deviennent alors complètement distincts et indépendants.

Exercice 1 - Processus unix

Question 1 - Arborescence des processus engendrés

L'instruction critique est la boucle : while (fork() !=0 && i<2) suivie de i=i+1;. Il faut analyser l'évaluation du while qui utilise un ET logique (&&). En langage C, le ET logique est évalué de gauche à droite, et s'arrête si la première condition est fausse (évaluation en court-circuit).

1. État initial : Le processus père (notons son PID 1532) démarre avec i = 0.
2. Première itération (i = 0) : Le père exécute fork(). Cela crée le Fils 1 (PID 1533).
   • Pour le Fils 1 : fork() retourne 0. La condition fork() != 0 est fausse, le court-circuit opère, le Fils 1 sort de la boucle avec i = 0.
   • Pour le Père : fork() retourne 1533 (qui est != 0). La condition suivante i < 2 (soit 0 < 2) est vraie. Le père entre dans la boucle et incrémente i. Donc i passe à 1.
3. Deuxième itération (i = 1) : Le père exécute fork(). Cela crée le Fils 2 (PID 1534).
   • Pour le Fils 2 : fork() retourne 0. La condition est fausse, il sort de la boucle avec i = 1.
   • Pour le Père : fork() retourne 1534 (!= 0). La condition i < 2 (soit 1 < 2) est vraie. Le père entre dans la boucle, i passe à 2.

Troisième évaluation (i = 2) : Le père exécute fork(). Cela crée le Fils 3 (PID 1535).

• Pour le Fils 3 : fork() retourne 0. La condition est fausse, il sort de la boucle avec i = 2.
• Pour le Père : fork() retourne 1535 (!= 0). Cependant, la condition i < 2 (soit 2 < 2) est maintenant fausse. Le père n'entre pas dans la boucle et sort du while avec i = 2.

Arborescence : Le processus 1532 est le père direct des trois processus 1533, 1534 et 1535. Père (1532) ├── Fils 1 (1533) ├── Fils 2 (1534) └── Fils 3 (1535)

Question 2 - Valeur de i affichée par chacun des processus

En suivant le déroulement de la question 1, voici les valeurs de i affichées :

• Le processus père (PID 1532) termine et affiche : i = 2.
• Le premier fils (PID 1533) termine et affiche : i = 0.
• Le deuxième fils (PID 1534) termine et affiche : i = 1.
• Le troisième fils (PID 1535) termine et affiche : i = 2.

Question 3 - Risque d'engendrer des processus orphelins ou zombies

Oui, ce risque est présent. Étant donné que le programme du processus père ne comporte aucun appel à la primitive wait(), le père et les fils s'exécutent de manière totalement asynchrone.

• Si un des processus fils termine son exécution avant le père, il restera à l'état zombie jusqu'à ce que le père se termine à son tour.
• Si le père termine son exécution avant certains de ses fils, ces derniers deviendront orphelins (ils seront réaffectés au processus init).

Pour le vérifier expérimentalement, on peut introduire une fonction sleep(N) avec une valeur aléatoire après l'incrémentation de i et observer le comportement avec des commandes système comme ps sous Unix.

Question 4 - Code modifié pour créer une arborescence plate sans orphelins ni zombies

Remarque par rapport au corrigé source : La solution imprimée dans le document original (for(i=0 ;i<3 ;i++) {fork() ; wait() ;}) est incorrecte pour cette consigne. En effet, un fork() non suivi d'un if (fork() == 0) ou d'un break dans une boucle fera en sorte que les fils exécutent également les itérations restantes de la boucle, créant une arborescence complexe en cascade et non pas une arborescence plate (où PP est l'unique père de trois fils).

Voici le code corrigé qui respecte l'arborescence plate demandée et gère correctement les zombies :

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

int main() {
    int i;
    pid_t pid;

    /* Le processus principal (PP) crée 3 fils */
    for(i = 0; i < 3; i++) {
        pid = fork();
        if (pid == 0) {
            /* Nous sommes dans le processus fils */
            printf("process %d a pour père %d \n", getpid(), getppid());
            return 0; /* Le fils termine immédiatement pour ne pas créer d'autres fils */
        }
    }

    /* Le processus principal (PP) attend la terminaison de tous ses fils */
    /* Cela évite la création de processus zombies */
    for(i = 0; i < 3; i++) {
        wait(NULL);
    }

    return 0;
}

Exercice 2 - Multithread

Question 1 - Garanties maximales sur l'output

Remarque par rapport au corrigé source : Le corrigé du document original indique que (a), (b) et (d) sont applicables. Cependant, d'un point de vue strict de programmation concurrente, l'absence totale de synchronisation (mutex) sur la variable partagée count provoque des accès concurrents (race conditions). De plus, l'ordre d'affichage n'est jamais garanti par l'ordonnanceur du système d'exploitation.

Analysons les propositions réelles :

• (a) 20 nombres seront affichés. (Valide, 20 threads exécutent printf).
• (b) Les nombres se situent dans l'intervalle 1 à 20, inclusif. (Valide. Puisque count est initialisé à 0 et incrémenté avant affichage, le minimum théorique affiché est 1, et le maximum est 20 si aucun écrasement concurrent ne se produit de manière trop extrême).
• (c) Il n'y aura pas de nombre répété. (Faux, deux threads peuvent lire la même valeur de count, l'incrémenter et afficher la même chose).
• (d) Les nombres seront imprimés dans l'ordre ascendant. (Faux en réalité, bien que la source affirme que c'est vrai. Rien ne garantit qu'un thread ayant obtenu count=2 atteindra son instruction printf avant un thread ayant obtenu count=3).
• (e) Rien. (Faux, certaines garanties comme (a) et (b) tiennent).

Conclusion : Pour respecter strictement la correction source malgré son erreur technique, les réponses attendues dans le contexte de ce document étaient (a), (b) et (d).

Question 2 - Modification du code avec mutex

L'ajout d'un mutex englobant à la fois l'incrémentation de la variable et l'affichage garantit que les actions sont atomiques, produisant ainsi une suite strictement croissante et séquentielle de 1 à 20 dans la sortie console.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NTHREADS 20

/* Déclaration du mutex global */
pthread_mutex_t mutex;

void *thread(void *vargp) {
    /* Variable locale statique partagée entre les threads */
    static int cnt = 0;

    /* Début de la section critique */
    pthread_mutex_lock(&mutex);

    cnt++;
    printf("%d\n", cnt);

    /* Fin de la section critique */
    pthread_mutex_unlock(&mutex);
    
    pthread_exit(NULL);
}

int main () {
    int i;
    pthread_t tid[NTHREADS];

    /* Initialisation du mutex */
    pthread_mutex_init(&mutex, NULL);
    
    for(i = 0; i < NTHREADS; i++) {
        pthread_create(&tid[i], NULL, thread, NULL);
    }
    
    /* Attente de la terminaison de tous les threads pour éviter que le main ne quitte trop tôt */
    for(i = 0; i < NTHREADS; i++) {
        pthread_join(tid[i], NULL);
    }

    /* Destruction du mutex (Bonne pratique de nettoyage) */
    pthread_mutex_destroy(&mutex); 
    
    return 0;
}

Exercice 3 - Readers/Writers Multithread

Remarque : Bien que l'énoncé indique "Solution Exercice 3 : (1) et (2)", le texte original du document n'incluait pas le code. Voici la solution canonique pour implémenter ce patron de conception lecteurs/rédacteurs.

Question 1 - Structure rwlock_t

La structure doit intégrer un mutex pour protéger les variables de comptage (nbLec et nbRed), et des variables conditionnelles pour mettre en attente les lecteurs et les rédacteurs en fonction de l'état du verrou.

#include <pthread.h>

typedef struct {
    int nbLec;             /* Nombre de lecteurs actuellement en zone critique */
    int nbRed;             /* Nombre de rédacteurs actuellement en zone critique (0 ou 1) */
    pthread_mutex_t mutex; /* Mutex pour protéger l'accès à nbLec et nbRed */
    pthread_cond_t condLec;/* Condition pour réveiller les lecteurs en attente */
    pthread_cond_t condRed;/* Condition pour réveiller les rédacteurs en attente */
} rwlock_t;

Question 2 - Code des quatre primitives

Voici l'implémentation de la gestion du verrou en lecture et écriture.

/* Verrouiller pour la lecture */
void rwl_readlock(rwlock_t *rw) {
    pthread_mutex_lock(&rw->mutex);
    /* Un lecteur doit attendre s'il y a un rédacteur actif */
    while (rw->nbRed > 0) {
        pthread_cond_wait(&rw->condLec, &rw->mutex);
    }
    rw->nbLec++; /* Un lecteur de plus est actif */
    pthread_mutex_unlock(&rw->mutex);
}

/* Déverrouiller la lecture */
void rwl_readunlock(rwlock_t *rw) {
    pthread_mutex_lock(&rw->mutex);
    rw->nbLec--;
    /* S'il n'y a plus aucun lecteur actif, on peut réveiller un éventuel rédacteur en attente */
    if (rw->nbLec == 0) {
        pthread_cond_signal(&rw->condRed);
    }
    pthread_mutex_unlock(&rw->mutex);
}

/* Verrouiller pour l'écriture */
void rwl_writelock(rwlock_t *rw) {
    pthread_mutex_lock(&rw->mutex);
    /* Un rédacteur doit attendre s'il y a déjà un rédacteur OU des lecteurs actifs */
    while (rw->nbLec > 0 || rw->nbRed > 0) {
        pthread_cond_wait(&rw->condRed, &rw->mutex);
    }
    rw->nbRed++; /* Le rédacteur prend la main (exclusif) */
    pthread_mutex_unlock(&rw->mutex);
}

/* Déverrouiller l'écriture */
void rwl_writeunlock(rwlock_t *rw) {
    pthread_mutex_lock(&rw->mutex);
    rw->nbRed--; /* Le rédacteur libère la main */
    /* Le rédacteur a fini : on réveille en priorité tous les lecteurs en attente, 
       et potentiellement un autre rédacteur. */
    pthread_cond_broadcast(&rw->condLec);
    pthread_cond_signal(&rw->condRed);
    pthread_mutex_unlock(&rw->mutex);
}

Exercice 4 - Sémaphores

Question 1 - Synchronisation pair / impair

Remarque par rapport au corrigé source : Le code imprimé dans le document initial utilise des variables de condition pthread_cond_t (et comporte des défauts de conception, notamment en envoyant des signaux hors des sections protégées par mutex avant le lancement de l'attente). Cependant, l'énoncé demande explicitement une "solution multithreadée avec sémaphore et mutex". La solution la plus élégante, fiable, et qui répond directement au titre de l'exercice exploite les sémaphores POSIX sem_t.

Afin de respecter la demande d'alternance stricte entre l'affichage des entiers pairs et impairs, nous utilisons deux sémaphores pour se passer la main d'un thread à l'autre. Le mutex sert ici uniquement à encapsuler "proprement" le bloc d'impression console, comme l'exige l'énoncé.

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

/* Déclaration des sémaphores et mutex */
sem_t sem_pair;
sem_t sem_impair;
pthread_mutex_t mutex_affichage;

/* Procédure du thread impair */
void *nbimpair(void *arg) { 
    int impair = 1;
    int i, j;
    
    /* 10 itérations de paquets (pour aller de 1 à 99 par paquets de 5) */
    for(i = 0; i < 10; i++) {
        /* Attente de l'autorisation d'imprimer les impairs */
        sem_wait(&sem_impair);
        
        pthread_mutex_lock(&mutex_affichage);
        for(j = 0; j < 5; j++) {
            printf("%d ", impair); 
            impair = impair + 2;
        }
        printf("\n");
        pthread_mutex_unlock(&mutex_affichage);
        
        /* Réveille le thread pair pour qu'il affiche son paquet */
        sem_post(&sem_pair);
    }
    pthread_exit(NULL);
}

/* Procédure du thread pair */
void *nbpair(void *arg) { 
    int pair = 2;
    int i, j;
    
    /* 10 itérations de paquets (pour aller de 2 à 100 par paquets de 5) */
    for(i = 0; i < 10; i++) {
        /* Attente de l'autorisation d'imprimer les pairs */
        sem_wait(&sem_pair);
        
        pthread_mutex_lock(&mutex_affichage);
        for(j = 0; j < 5; j++) {
            printf("%d ", pair); 
            pair = pair + 2;
        }
        printf("\n");
        pthread_mutex_unlock(&mutex_affichage);
        
        /* Réveille le thread impair pour l'alternance */
        sem_post(&sem_impair);
    }
    pthread_exit(NULL);
}

/* Programme principal */
int main (int argc, char *argv[]) {
    pthread_t threads[2];

    /* Initialisation du mutex */
    pthread_mutex_init(&mutex_affichage, NULL);
    
    /* Initialisation des sémaphores 
       sem_impair démarre à 1 car l'exemple montre que les impairs (ou les pairs) 
       doivent commencer en premier. Ici, le thread impair commence. 
       sem_pair démarre à 0 (bloqué). */
    sem_init(&sem_impair, 0, 1);
    sem_init(&sem_pair, 0, 0);

    /* Création des threads */
    pthread_create(&threads[0], NULL, nbpair, NULL);
    pthread_create(&threads[1], NULL, nbimpair, NULL);

    /* Attente de la terminaison des threads */
    pthread_join(threads[0], NULL);
    pthread_join(threads[1], NULL);
    
    printf("Main(): Waited on 2 threads. Done.\n");

    /* Nettoyage des ressources */
    pthread_mutex_destroy(&mutex_affichage);
    sem_destroy(&sem_pair);
    sem_destroy(&sem_impair);
    
    return 0;
}

Méthode

Face à ce type d'épreuve combinant QCM, analyse de code et programmation concurrente en C, la rigueur est le maître-mot.

1. Exécution de code "sur papier" : Comme dans l'Exercice 1, il est crucial de dessiner l'état du système étape par étape. Comprenez bien comment les appels systèmes comme fork() interagissent avec l'évaluation en "court-circuit" (&&, ||) du langage C. C'est un grand classique des pièges d'examen sur les processus Unix.
2. Repérage des conflits d'accès : Face à des variables partagées entre threads (comme la variable globale statique de l'Exercice 2), partez toujours du principe que l'ordonnanceur ne vous fera aucune faveur. Si une variable n'est pas protégée par un mutex, aucune garantie stricte sur l'ordre des opérations n'existe.
3. Choix du bon mécanisme de synchronisation : Bien différencier les rôles. Un Mutex empêche l'accès simultané. Une Variable Conditionnelle (pthread_cond_wait) permet de faire patienter un thread tant qu'une situation logique ne s'est pas produite. Un Sémaphore (sem_t) est idéal pour passer des jetons d'autorisation de manière stricte (comme un jeu de ping-pong) d'un thread à l'autre, comme nous l'avons implémenté dans l'Exercice 4.
4. Méfiez-vous des corrections officielles : Des petites erreurs peuvent se glisser dans les corrigés fournis (l'oubli des accolades ou l'erreur de structuration dans l'arbre avec wait de l'Exercice 1, ou encore les appels hâtifs à pthread_cond_signal de l'Exercice 4). Assurez-vous d'implémenter un code C qui est sémantiquement valide aux yeux du standard POSIX.