Devoir Surveillé en Systèmes d’exploitation et Programmation Concurrente
Devoir Surveillé en Systèmes d’exploitation et Programmation Concurrente
Programmation, Systèmes d'exploitation, Mathématiques · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
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).
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.
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.
Pour implémenter un moniteur, plusieurs files d'attente sont nécessaires :
wait(c).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.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;
}
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;
}
Règles appliquées : Priorité P3 (3) > P2 (2) > P1 (1). L'ordonnancement est préemptif.
Déroulement détaillé :
A AX et commence sa Section Critique (SC) → XA AX (occupé par P1). P2 se bloque. P1 reprend.X X X (Fin de sa SC de 4 ut)X. P2 est débloqué et préempte immédiatement P1. P2 prend X puis Y.2 2A AY (occupé par P2). P3 se bloque. P2 reprend.2 2Y (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.2 2 2 2B B B. P3 est terminé.B B B. P2 est terminé.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)
b) Temps d'attente (TA) (TR - Temps d'exécution total de 9 ut)
c) Rendement du CPU
Nouvelles règles : P1 (Prio 1, t=0) ; P2 (Prio 3, t=6) ; P3 (Prio 2, t=3). Priorité : P2 > P3 > P1.
Déroulement :
A AX et exécute sa SC → XA AY, puis demande X (occupé par P1). P3 se bloque. P1 reprend.XA AX (occupé par P1). P2 se bloque. P1 reprend.X XX. P2 et P3 attendent X. P2 a la priorité la plus haute (3 > 2), c'est donc P2 qui obtient X.X et demande Y. Cependant, Y est occupé par P3 (depuis t=5). P2 se bloque.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 :
Conclusion : Le système subit un interblocage (deadlock) à t=10.
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.
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.
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 :
nbA passe à 1, nbB vaut 0. Il circule.nbB passe à 1. Puisque nbA > 0, B1 se bloque sur la variable de condition cb.nbA passe à 2. Puisque nbB > 0 (B1 l'a incrémenté bien qu'il soit bloqué), A2 se bloque sur ca.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.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);
}
}
}
}
Face à une épreuve de Systèmes d'Exploitation et de Programmation Concurrente :
&& 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.