Devoir Surveillé - Systèmes d’exploitation
Devoir Surveillé - Systèmes d’exploitation
Systèmes d'exploitation, Programmation, Mathématiques · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Cet exercice vise à valider votre compréhension des concepts fondamentaux des systèmes d'exploitation. La précision du vocabulaire est essentielle.
Voici la distinction pour chaque paire de termes, en retenant le critère technique principal qui les sépare :
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.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.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).Le multithreading (plusieurs threads dans un processus) offre plusieurs avantages sur le multitâche lourd (plusieurs processus distincts) :
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).
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();
}
}
}
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.
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é.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;
}
Face à une épreuve de Systèmes d'Exploitation, voici la démarche à adopter :
Nb_Votant ou Dispo) doit être protégé par une exclusion mutuelle.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).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.