Systèmes d'Exploitation III - 2

Question 1 - Le problème du partage de ressources

Dans un système multi-programmé en temps partagé, plusieurs processus s'exécutent de manière concurrente et peuvent être interrompus à tout moment (préemption) pour laisser la place à un autre processus. Lorsque ces processus partagent des ressources (comme des variables en mémoire, des fichiers ou des périphériques), des problèmes majeurs surviennent car les opérations sur ces ressources ne sont généralement pas atomiques (elles s'exécutent en plusieurs cycles d'horloge).

Si un processus est préempté au milieu de la modification d'une ressource partagée, et qu'un autre processus y accède, cela crée une situation de compétition (race condition). Le résultat dépendra de l'ordre d'exécution (entrelacement) des processus, ce qui conduit à des données incohérentes, des comportements imprévisibles, ou des pannes du système.

Question 2 - Contrôle des accès sous UNIX

Le système UNIX fournit plusieurs mécanismes de communication inter-processus (IPC) pour contrôler l'accès aux ressources partagées et garantir la synchronisation :

• Les sémaphores (System V ou POSIX) : Ce sont des compteurs protégés par le système d'exploitation, manipulables uniquement via des opérations atomiques (Wait/Post ou P/V). Ils permettent de gérer l'exclusion mutuelle ou de coordonner l'ordre d'exécution.
• Les verrous d'exclusion mutuelle (Mutex) : Souvent utilisés avec les threads (pthreads), ils fonctionnent comme des verrous binaires pour protéger des sections critiques.
• Les verrous sur les fichiers (File Locks) : Avec des appels système comme fcntl() ou flock(), UNIX permet de verrouiller un fichier ou une partie d'un fichier pour empêcher d'autres processus de le modifier simultanément.
• Les tubes (Pipes) et les files de messages (Message Queues) : Ils permettent de transférer des données de manière synchronisée, le système bloquant automatiquement le lecteur si la structure est vide, ou l'écrivain si elle est pleine.

Question 3 - Définition d'une section critique

Une section critique est une portion de code au sein d'un processus ou d'un thread durant laquelle celui-ci accède à une ressource partagée (variable, fichier, port matériel) qui ne doit pas être manipulée simultanément par d'autres processus. Pour garantir la cohérence des données, le système doit s'assurer que l'exécution des sections critiques de processus concurrents s'exclut mutuellement : un seul processus peut se trouver dans sa section critique pour une ressource donnée à un instant T.

Question 4 - Les causes de blocage d'un processus

Réponse correcte : B. lorsqu'il demande un sémaphore "vide".

Explication de l'analyse :

• A. Libérer un sémaphore (opération V ou Signal) ne bloque jamais le processus qui effectue l'action ; cela incrémente le compteur.
• B. Demander un sémaphore (opération P ou Wait) décrémente le compteur. Si le sémaphore est "vide" (c'est-à-dire que sa valeur est égale à 0), le processus appelant est suspendu et placé dans la file d'attente du sémaphore jusqu'à ce que la ressource se libère. C'est la bonne réponse.
• C. Créer un sémaphore est une opération d'initialisation qui ne cause pas de blocage (sauf erreur système critique).
• D. Libérer un sémaphore sur lequel un autre processus attend va débloquer cet autre processus, mais le processus qui libère le sémaphore continue son exécution normalement.

Question 5 - Graphe de précédence et sémaphores

Note concernant le document source : L'énoncé indique "graphe de précédence ci-dessous" mais l'image du graphe est manquante dans le texte extrait. Il n'est donc pas possible de donner la solution exacte pour ce graphe spécifique. Cependant, voici la méthode pour résoudre ce type d'exercice.

Méthode générale en cas de présence du graphe :

1. Identifier chaque flèche allant d'un processus A vers un processus B. Cela signifie que A doit terminer son exécution avant que B ne commence.
2. Pour chaque flèche, créer un sémaphore d'initialisation à 0 (ex: Semaphore S_AB = 0;).
3. À la fin du bloc d'instructions de A, ajouter une opération de libération V(S_AB);.
4. Au début du bloc d'instructions de B, ajouter une opération de demande P(S_AB);. Si un processus a plusieurs dépendances (plusieurs flèches entrantes), il fera plusieurs P() au début. S'il débloque plusieurs processus (plusieurs flèches sortantes), il fera plusieurs V() à la fin.

Question 6 - Analyse du code pour les processus P1, P2 et P3

Note concernant le document source : Les codes des processus contenant la proposition du programmeur sont absents du texte extrait. Seules les déclarations Semaphore mutex1 = 1 ; Semaphore mutex2 = 1 ; sont fournies.

Sous-question 6(a) - Validité de la proposition

Puisque le code proposé par le programmeur est manquant, il est impossible d'évaluer sa validité, ni de repérer s'il génère des interblocages (deadlocks) ou des violations d'exclusion mutuelle sur les variables n et out. Généralement, l'utilisation de plusieurs mutex imbriqués dans des ordres différents par différents processus est la cause classique d'une réponse "Non, car il y a un risque d'interblocage".

Sous-question 6(b) - Solution correcte

Faute d'énoncé complet, la règle générale pour protéger des accès multiples à n et out est de définir un seul mutex global si les variables sont toujours mises à jour ensemble, ou de s'assurer que si plusieurs mutex sont utilisés, tous les processus acquièrent les sémaphores (opérations P) dans le même ordre strict pour éviter l'étreinte fatale (deadlock).

Question 7 - Les trains sur voie unique

Sous-question 7(a) - Modèle correspondant

Ce problème correspond à une variante du modèle des Lecteurs / Rédacteurs. Dans notre contexte, une direction (par exemple Train A vers B) agit comme un groupe de lecteurs, et l'autre direction (Train B vers A) agit comme un autre groupe. Plusieurs trains d'un même groupe peuvent partager la ressource (la voie) simultanément (comme des lecteurs multiples), mais la ressource doit être strictement exclusive entre les groupes opposés (exclusion mutuelle comme entre lecteurs et rédacteurs). C'est un modèle symétrique de lecteurs/lecteurs exclusifs.

Sous-question 7(b) - Traduction avec des sémaphores

Nous allons utiliser deux compteurs et trois sémaphores pour reproduire la logique d'accès.

Variables partagées :

Semaphore voie = 1;      // Protège l'accès exclusif à la voie (entre A->B et B->A)
Semaphore mutex_A = 1;   // Protège la modification du compteur_A
Semaphore mutex_B = 1;   // Protège la modification du compteur_B
int compteur_A = 0;      // Nombre de trains allant de A vers B sur la voie
int compteur_B = 0;      // Nombre de trains allant de B vers A sur la voie

Code pour Train AversB :

// Demande d'accès à la voie par A
P(mutex_A);
compteur_A = compteur_A + 1;
if (compteur_A == 1) {
    P(voie); // Le premier train ferme l'accès à l'autre direction
}
V(mutex_A);

// Circulation sur la voie de A vers B

// Sortie de la voie par B
P(mutex_A);
compteur_A = compteur_A - 1;
if (compteur_A == 0) {
    V(voie); // Le dernier train libère la voie pour l'autre direction
}
V(mutex_A);

Code pour Train BversA :

// Demande d'accès à la voie par B
P(mutex_B);
compteur_B = compteur_B + 1;
if (compteur_B == 1) {
    P(voie); // Le premier train ferme l'accès à l'autre direction
}
V(mutex_B);

// Circulation sur la voie de B vers A

// Sortie de la voie par A
P(mutex_B);
compteur_B = compteur_B - 1;
if (compteur_B == 0) {
    V(voie); // Le dernier train libère la voie pour l'autre direction
}
V(mutex_B);

Question 8 - Threads et pointeur partagé

Sous-question 8(a) - Origine de l'erreur de segmentation

L'erreur provient d'une situation de compétition (race condition) qui mène à la déréférenciation d'un pointeur NULL ou à un "Use-After-Free". Le reader_thread vérifie if (pointer != NULL). Supposons que cette condition soit vraie. Le thread est préempté juste après cette vérification et avant d'afficher la valeur. Pendant ce temps, le reader_thread est exécuté une autre fois (ou un autre lecteur) qui libère la mémoire avec free(pointer) et met le pointeur à NULL. Lorsque le premier lecteur reprend son exécution, il exécute printf("pointer = %d", *pointer);. À cet instant, pointer vaut NULL ou est invalide, ce qui provoque immédiatement une "Erreur de segmentation".

Sous-question 8(b) - Résolution avec un sémaphore

Nous devons protéger toute la section critique englobant le test du pointeur et son traitement. (Note : Nous ajoutons #include <stdlib.h> et <stdio.h> pour rendre le code exécutable).

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

int *pointer = NULL;
// On déclare le sémaphore initialisé à 1 dans le main
// Semaphore mutex = 1; 

void * writer_thread() {
    while (1) {
        P(mutex);
        if (pointer == NULL) {
            pointer = malloc(sizeof(int));
            *pointer = rand();
        }
        V(mutex);
    }
}

void *reader_thread() {
    while (1) {
        P(mutex);
        if (pointer != NULL) {
            printf("pointer = %d\n", *pointer);
            free(pointer);
            pointer = NULL;
        }
        V(mutex);
    }
}

Sous-question 8(c) - Résolution sans mécanismes de synchronisation

Pour une seule paire d'écrivain et lecteur : Oui, il est théoriquement possible de résoudre ce problème sans sémaphore en utilisant l'attente active (busy-waiting) basée sur la valeur même du pointeur partagé. Puisqu'il n'y a qu'un seul thread modifiant le pointeur de NULL à valide, et un seul thread modifiant le pointeur de valide à NULL, des boucles comme while(pointer == NULL); dans le lecteur et while(pointer != NULL); dans l'écrivain créeraient une alternance stricte. Cela consommerait beaucoup de ressources CPU (spin-lock), mais cela fonctionnerait en l'absence de réordonnancement mémoire par le processeur.

Pour plusieurs paires (plusieurs écrivains / plusieurs lecteurs) : Non. Dès qu'il y a plus d'un lecteur ou d'un écrivain, la simple vérification n'est plus atomique. Deux écrivains pourraient détecter un pointeur NULL simultanément et effectuer un malloc en même temps, entraînant une fuite de mémoire (memory leak) ou un écrasement. Des mécanismes matériels (comme les instructions Test-and-Set) ou logiciels (sémaphores, mutex) deviennent absolument indispensables.

Sous-question 8(d) - Utilisation de variables conditionnelles

La variable conditionnelle permet à un thread de s'endormir (sans consommer de CPU) jusqu'à ce que la donnée soit disponible.

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

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

void * writer_thread() {
    while (1) {
        pthread_mutex_lock(&mutex);
        if (pointer == NULL) {
            pointer = malloc(sizeof(int));
            *pointer = rand();
            // Alerte le lecteur qu'une modification a eu lieu
            pthread_cond_signal(&cond); 
        }
        pthread_mutex_unlock(&mutex);
    }
}

void *reader_thread() {
    while (1) {
        pthread_mutex_lock(&mutex);
        // Utilisation d'un while pour prévenir les réveils spontanés
        while (pointer == NULL) {
            pthread_cond_wait(&cond, &mutex);
        }
        printf("pointer = %d\n", *pointer);
        free(pointer);
        pointer = NULL;
        pthread_mutex_unlock(&mutex);
    }
}

Question 9 - Ordres d'exécution avec un Sémaphore

Sous-question 9(a) - S initialisé à 1

Puisque S = 1, les opérations encadrées par P(S) et V(S) forment des sections critiques s'excluant mutuellement. Le bloc {b} de A et le bloc {c, d} de B ne peuvent pas s'entrelacer. De plus, l'instruction a dans A précède toujours P(S), elle est donc indépendante de la section critique. Les exécutions possibles dépendent de l'ordre d'acquisition du sémaphore :

Cas 1 : A prend le sémaphore en premier.

• A exécute a, prend S, exécute b, libère S. B prend S, exécute c, puis d.
• Résultat : a, b, c, d

Cas 2 : B prend le sémaphore en premier. L'instruction a peut s'exécuter avant que B ne commence sa section critique, pendant, ou après, mais toujours avant que A ne fasse b.

• Résultat 1 : a, c, d, b
• Résultat 2 : c, a, d, b
• Résultat 3 : c, d, a, b

Ce sont les 4 ordres d'exécution atomiques valides.

Sous-question 9(b) - S initialisé à 0

Si S = 0, la première opération de demande P(S) bloquera le processus appelant car le compteur passera en négatif ou s'arrêtera à 0.

• Le Processus A commence, exécute l'instruction a, puis est bloqué sur P(S).
• Le Processus B commence et est immédiatement bloqué sur P(S). Aucun processus ne peut exécuter de V(S) pour débloquer l'autre. Nous sommes dans une situation d'interblocage (Deadlock). L'unique séquence exécutée avant le blocage définitif est : a.

Question 10 - Synchronisation via signaux (SIGCONT)

Sous-question 10(a) - Accès simultané en section critique (SC)

Oui, les deux processus peuvent se retrouver en section critique en même temps. Justification : Le test while (verrou != 0) et l'affectation verrou = 1 ne sont pas atomiques. Si verrou est initialement à 0 et que l'ordonnanceur préempte P1 juste après son test conditionnel (mais avant de mettre verrou à 1), P2 peut alors s'exécuter, voir que verrou est toujours à 0, et l'affecter à 1 avant d'entrer dans la fonction SC(). Lorsque P1 reprend, il sort du test, met verrou = 1 et entre également dans SC(). L'exclusion mutuelle est violée.

Sous-question 10(b) - Blocage infini d'un processus

Oui, un des processus peut se retrouver en pause pour toujours (Lost Wakeup Problem). Justification : L'instruction pause() attend qu'un signal (comme SIGCONT) soit reçu pour débloquer le processus. Supposons que P1 entre en section critique (verrou devient 1). P2 s'exécute, constate que verrou != 0. P2 est préempté juste avant d'exécuter pause(). P1 termine sa section critique, remet verrou à 0, et exécute kill(P2, SIGCONT). Comme P2 n'est pas encore en état de pause, le signal est ignoré par le système. Lorsque P2 reprend la main, il exécute pause() et attend un signal qui est déjà passé et ne sera plus jamais renvoyé. P2 restera bloqué indéfiniment.

Question 11 - Graphe de précédence P1 -> P2 -> P3

Nous devons imposer l'ordre séquentiel strict : I1 doit se terminer pour que I2 démarre, et I2 doit se terminer pour que I3 démarre.

PROGRAM P1P2P3 ; 
var
  S12, S23 : semaphore ;
semaphore init
  S12 = 0, S23 = 0 ;

Process P1 { 
    I1 ; 
    V(S12) ; 
}

Process P2 { 
    P(S12) ; 
    I2 ; 
    V(S23) ; 
}

Process P3 { 
    P(S23) ; 
    I3 ; 
}

Méthode

Face à une épreuve de systèmes d'exploitation portant sur la concurrence :

1. Identifier le défaut d'atomicité : Pensez systématiquement à l'effet de la préemption. Posez-vous toujours la question : "Que se passe-t-il si le processus A est mis en pause par l'ordonnanceur exactement entre la ligne de lecture et la ligne d'écriture de cette variable partagée ?". C'est ainsi que l'on trouve les violations d'exclusion mutuelle et les pertes de données.
2. Savoir manier les sémaphores : Un sémaphore initialisé à 1 sert à l'exclusion mutuelle (un lock). Un sémaphore initialisé à 0 sert à la synchronisation/signalisation (attendre qu'un événement précédent se produise).
3. Se méfier des fonctions système sans état matériel : Comme illustré avec le problème du signal SIGCONT, une synchronisation purement logicielle basée sur des signaux est souvent vulnérable à l'interruption entre la validation de la condition et l'entrée en sommeil. Les primitives de type mutex et variables conditionnelles (POSIX threads) pallient ces défauts.