Merci pour le document. Tu m’as demandé une explication détaillée et approfondie des pages 50 à 67.
Voici comment je te propose de procéder :
1. Je vais te résumer et expliquer chaque section présente sur ces pages de façon claire, en français,
avec les exemples et les points essentiels.
2. On va diviser ça en parties pour que tu puisses bien assimiler.
3. Tu pourras me poser des questions à chaque étape si quelque chose reste flou.
Pages 50 à 67 couvrent principalement les thèmes suivants :
Les algorithmes d’ordonnancement (scheduling) du processeur
La synchronisation des processus (section critique, sémaphores, problèmes classiques comme les
philosophes, lecteurs-rédacteurs…)
Les constructeurs de haut niveau (regions critiques, moniteurs)
Les transactions atomiques et la gestion des erreurs
La gestion de l’accès concurrent à la mémoire
Souhaites-tu que je commence par l’ordonnancement des processus (CPU Scheduling) ou un autre
thème en priorité ?
Parfait, on commence donc par l’ordonnancement des processus (CPU Scheduling). Voici une explication
détaillée et claire de ce que tu trouveras dans cette section du cours (pages 50 à 53 environ).
---
1. Qu’est-ce que l’ordonnancement du CPU ?
L'ordonnancement du CPU (CPU Scheduling) consiste à choisir, parmi les processus prêts à s'exécuter,
celui qui obtiendra le processeur. Cela se produit quand plusieurs processus sont en file d’attente (ready
queue).
Pourquoi c’est important ?
Parce qu’un seul processus peut s’exécuter à un moment donné sur le CPU, donc le système
d’exploitation doit décider lequel va passer.
---
2. Les files d’attente (Queues)
Job queue : tous les processus du système.
Ready queue : les processus qui sont prêts et en mémoire, en attente d’utilisation du CPU.
Device queues : les processus en attente d’un périphérique (comme un disque dur).
Chaque processus se déplace entre ces files au cours de son exécution.
---
3. Types de planificateurs (Schedulers)
a. Long-Term Scheduler (ordonnanceur à long terme)
Sélectionne les processus à charger dans la mémoire.
Contrôle le niveau de multiprogrammation (combien de processus sont en mémoire en même temps).
b. Short-Term Scheduler (ordonnanceur à court terme)
Sélectionne le prochain processus à exécuter sur le CPU.
Doit être très rapide car il agit souvent (toutes les millisecondes).
c. Medium-Term Scheduler (ordonnanceur à moyen terme)
Peut retirer temporairement un processus de la mémoire (swapping) pour libérer de la place.
Puis le réintroduire plus tard pour qu’il continue.
---
4. PCB : Process Control Block (Bloc de Contrôle de Processus)
Chaque processus est représenté par un PCB contenant :
Son état (prêt, en cours, bloqué…)
Le compteur de programme (adresse de la prochaine instruction)
Les registres du CPU
Les infos de planification
L’espace mémoire alloué
Les infos d’E/S (fichiers ouverts, périphériques utilisés…)
---
5. Algorithmes de planification
Maintenant on rentre dans les différents algorithmes d’ordonnancement. C’est ce qui détermine dans
quel ordre les processus accèdent au CPU.
Je te propose de les expliquer un par un avec des exemples clairs. Voici la liste :
1. FCFS – First Come First Served
2. SJF – Shortest Job First
3. Priority Scheduling
4. Round Robin (RR)
Tu veux qu’on commence par FCFS, le plus simple ?
Super, on commence donc par le premier algorithme : FCFS – First Come, First Served (Premier arrivé,
premier servi).
---
1. FCFS – First Come, First Served
Définition :
Cet algorithme attribue le CPU au processus qui est arrivé en premier dans la file d’attente. C’est comme
dans une file d’attente au supermarché : on sert les gens dans l’ordre d’arrivée.
Caractéristiques :
Simple à comprendre et à implémenter.
Utilise une file FIFO (First-In, First-Out).
Non préemptif : un processus garde le CPU jusqu’à ce qu’il termine.
---
2. Exemple :
Supposons que 4 processus arrivent dans cet ordre avec les temps d’exécution (burst time) suivants :
Ordre d’arrivée : P1, P2, P3, P4
Gantt Chart (Chronologie d’exécution)
| P1 | P2 | P3 | P4 |
0 3 8 10 14
Calcul des temps :
Waiting Time (WT) = Temps d’attente avant l’exécution
P1 = 0
P2 = 3 (attend que P1 finisse)
P3 = 8 (attend que P1 + P2 finissent)
P4 = 10 (attend que P1 + P2 + P3 finissent)
Turnaround Time (TAT) = WT + temps d’exécution
P1 = 0 + 3 = 3
P2 = 3 + 5 = 8
P3 = 8 + 2 = 10
P4 = 10 + 4 = 14
Moyennes :
Temps d’attente moyen = (0 + 3 + 8 + 10) / 4 = 5.25 ms
Temps de séjour moyen = (3 + 8 + 10 + 14) / 4 = 8.75 ms
---
3. Avantages et Inconvénients
Avantages :
Simple à coder
Équitable en surface (pas de favoritisme)
Inconvénients :
Peut provoquer un long temps d’attente pour les petits processus si un gros arrive avant (effet de
convoi).
Pas adapté aux systèmes interactifs.
---
Tu veux que je continue avec le deuxième algorithme (SJF - Shortest Job First) ou tu veux qu'on fasse un
petit quiz rapide pour voir si tu as bien compris ?
Parfait, continuons avec le deuxième algorithme : SJF – Shortest Job First (Processus le plus court en
premier).
---
2. SJF – Shortest Job First
Définition :
Le processeur est alloué au processus avec le plus petit temps d’exécution (CPU burst).
C’est comme si tu faisais passer en premier les gens avec les courses les plus rapides à scanner.
---
Types :
Non préemptif : Une fois qu’un processus commence, il va jusqu’au bout.
Préemptif (Shortest Remaining Time First - SRTF) : Si un nouveau processus plus court arrive, il
interrompt le processus en cours.
---
Exemple non préemptif :
Ordre choisi par SJF :
On trie par ordre croissant du temps CPU : P3, P1, P4, P2
Gantt Chart :
| P3 | P1 | P4 | P2 |
0 2 5 9 14
Waiting Time (WT) :
P3 = 0
P1 = 2
P4 = 5
P2 = 9
Turnaround Time (TAT) = WT + Temps CPU :
P3 = 0 + 2 = 2
P1 = 2 + 3 = 5
P4 = 5 + 4 = 9
P2 = 9 + 5 = 14
Moyennes :
Temps d’attente moyen = (0 + 2 + 5 + 9) / 4 = 4 ms
Temps de séjour moyen = (2 + 5 + 9 + 14) / 4 = 7.5 ms
---
Exemple préemptif (SRTF) :
Gantt Chart :
|P1|P2|P4|P1|P3|
0 1 5 10 17 26
Waiting Time :
P1 = 10 - 0 - 1 (début) = 9
P2 = 1 - 1 = 0
P3 = 17 - 2 = 15
P4 = 5 - 3 = 2
Temps d’attente moyen = (9 + 0 + 15 + 2) / 4 = 6.5 ms
---
Avantages / Inconvénients :
Avantages :
Minimise le temps d’attente moyen
Optimal théoriquement
Inconvénients :
Difficile de prédire le prochain burst CPU
Peut provoquer une famine : les longs processus peuvent attendre indéfiniment
---
Souhaites-tu que je continue avec l’algorithme par priorité, ou tu veux que je te propose un exercice
d’application sur SJF ?
Parfait, on continue donc avec le troisième algorithme : l’ordonnancement par priorité (Priority
Scheduling).
---
3. Priority Scheduling – Ordonnancement par Priorité
Définition :
Chaque processus se voit attribuer une priorité. Le CPU est attribué au processus avec la plus haute
priorité.
Priorité plus petite = plus importante (ex: priorité 1 > priorité 4)
Peut être préemptif ou non préemptif
---
Exemple :
Ordre basé sur priorité (plus petite = plus prioritaire) :
1. P2 (priorité 1)
2. P4 (2)
3. P1 (3)
4. P3 (4)
5. P5 (5)
Gantt Chart (non préemptif) :
| P2 | P4 | P1 | P3 | P5 |
0 1 5 15 18 20
Temps d’attente (WT) :
P2 = 0
P4 = 1 – 1 = 0
P1 = 5 – 0 = 5
P3 = 15 – 2 = 13
P5 = 18 – 5 = 13
Temps moyen d’attente = (0 + 0 + 5 + 13 + 13) / 5 = 6.2 ms
---
Préemptif ou non ?
Non préemptif : un processus garde le CPU jusqu’à la fin.
Préemptif : un processus avec une priorité plus haute peut interrompre celui en cours.
---
Problèmes :
Famine (Starvation) : un processus avec une priorité basse peut attendre indéfiniment.
Solution : utiliser l'"aging"** : augmenter progressivement la priorité d’un processus qui attend trop
longtemps.
---
Souhaites-tu qu’on continue avec Round Robin, ou tu préfères un petit exercice pour t’entraîner sur la
planification par priorité ?
D’accord, on continue avec le dernier algorithme de planification classique : Round Robin (RR).
---
4. Round Robin (RR) – Algorithme du tourniquet
Définition :
Chaque processus reçoit une quantité de temps fixe, appelée quantum (ou time slice).
Si le processus n’a pas fini à la fin du quantum, il est interrompu et replacé à la fin de la file d’attente.
Le CPU passe ensuite au processus suivant.
C’est comme un tour de manège : tout le monde passe à son tour, pour une durée limitée.
---
Caractéristiques :
Préemptif par nature
Très utilisé dans les systèmes temps partagé (multitâche interactif)
Temps de réponse rapide pour tous les processus
Efficacité dépend beaucoup de la taille du quantum :
Trop petit = trop de changements = perte de temps
Trop grand = comme FCFS
---
Exemple :
Quantum = 1 ms
Gantt Chart :
P1 P2 P3 P4 P1 P2 P4 P2 P4 P2
0 1 2 3 4 5 6 7 8 9 10
Calcul du temps d’attente (WT) :
On calcule le moment où chaque processus est en pause, on additionne ces périodes avant son dernier
passage, et on soustrait son temps d’exécution final pour obtenir WT.
Ou plus simplement :
P1 : commence à 0, revient à 4 → WT = (0 + (4 – 1)) = 3
P2 : (1 + (5 – 2) + (7 – 6) + (9 – 8)) = 1 + 3 + 1 + 1 = 6
P3 : (2) + (6 – 3) = 2 + 3 = 5
P4 : (3 + (6 – 4) + (8 – 7)) = 3 + 2 + 1 = 6
Temps d’attente moyen = (3 + 6 + 5 + 6) / 4 = 5 ms
---
Avantages / Inconvénients
Avantages :
Équitable : tout le monde a du temps CPU
Temps de réponse rapide
Très adapté aux systèmes interactifs
Inconvénients :
Pas optimal pour les processus courts si le quantum est mal choisi
Peut provoquer un peu de surcharge à cause des interruptions fréquentes
---
Voilà pour les 4 principaux algorithmes ! Tu veux maintenant :
1. Un récapitulatif comparatif
2. Un exercice pour t’entraîner
3. Ou on continue avec la suite du cours (comme la synchronisation des processus) ?
À toi de choisir !
D’accord, on continue avec le dernier algorithme de planification classique : Round Robin (RR).
---
4. Round Robin (RR) – Algorithme du tourniquet
Définition :
Chaque processus reçoit une quantité de temps fixe, appelée quantum (ou time slice).
Si le processus n’a pas fini à la fin du quantum, il est interrompu et replacé à la fin de la file d’attente.
Le CPU passe ensuite au processus suivant.
C’est comme un tour de manège : tout le monde passe à son tour, pour une durée limitée.
---
Caractéristiques :
Préemptif par nature
Très utilisé dans les systèmes temps partagé (multitâche interactif)
Temps de réponse rapide pour tous les processus
Efficacité dépend beaucoup de la taille du quantum :
Trop petit = trop de changements = perte de temps
Trop grand = comme FCFS
---
Exemple :
Quantum = 1 ms
Gantt Chart :
P1 P2 P3 P4 P1 P2 P4 P2 P4 P2
0 1 2 3 4 5 6 7 8 9 10
Calcul du temps d’attente (WT) :
On calcule le moment où chaque processus est en pause, on additionne ces périodes avant son dernier
passage, et on soustrait son temps d’exécution final pour obtenir WT.
Ou plus simplement :
P1 : commence à 0, revient à 4 → WT = (0 + (4 – 1)) = 3
P2 : (1 + (5 – 2) + (7 – 6) + (9 – 8)) = 1 + 3 + 1 + 1 = 6
P3 : (2) + (6 – 3) = 2 + 3 = 5
P4 : (3 + (6 – 4) + (8 – 7)) = 3 + 2 + 1 = 6
Temps d’attente moyen = (3 + 6 + 5 + 6) / 4 = 5 ms
---
Avantages / Inconvénients
Avantages :
Équitable : tout le monde a du temps CPU
Temps de réponse rapide
Très adapté aux systèmes interactifs
Inconvénients :
Pas optimal pour les processus courts si le quantum est mal choisi
Peut provoquer un peu de surcharge à cause des interruptions fréquentes
---
Voilà pour les 4 principaux algorithmes ! Tu veux maintenant :
Excellent choix ! Voici un récapitulatif comparatif clair et structuré des 4 algorithmes de planification que
nous avons vus :
---
Tableau comparatif des algorithmes d’ordonnancement du CPU
---
Quelques conseils pratiques :
Pour les systèmes batch : SJF est souvent théoriquement le plus efficace.
Pour les systèmes interactifs / multitâches : Round Robin est recommandé.
FCFS est trop simple pour les systèmes modernes, mais bon pour débuter.
Priority est utile quand certains processus sont plus critiques, mais attention à la famine.
---
Tu es maintenant bien armé pour comprendre l’ordonnancement des processus !
Prêt(e) à continuer avec la synchronisation des processus (section suivante du cours) ? Ça parle de
sections critiques, sémaphores, et des problèmes classiques comme les philosophes.
Super, entrons maintenant dans la synchronisation des processus, une partie essentielle des systèmes
d’exploitation, surtout quand plusieurs processus s’exécutent en même temps (concurrence).
---
1. Qu’est-ce que la synchronisation des processus ?
C’est la gestion de l’accès concurrent à des ressources partagées (ex. : fichiers, variables, imprimantes…).
On doit éviter que deux processus modifient en même temps une donnée partagée, ce qui pourrait
causer des incohérences.
---
2. Le Problème de la Section Critique
Une section critique est une portion de code où un processus accède à des données partagées. Il faut
que seul un processus à la fois puisse l’exécuter.
Exemple de structure :
while (true) {
// Entrée : demander l'accès
// SECTION CRITIQUE : accès à la ressource partagée
// Sortie : libérer la ressource
// Reste du code (remainder section)
---
3. Conditions qu’une solution doit respecter :
1. Exclusion mutuelle (Mutual Exclusion) : un seul processus dans la section critique à la fois.
2. Progrès (Progress) : s’il n’y a aucun processus dans la section critique, un processus qui veut y entrer
doit pouvoir le faire.
3. Attente bornée (Bounded Waiting) : un processus ne doit pas attendre éternellement pour entrer.
---
4. Outils de synchronisation : les sémaphores
Un sémaphore est une variable spéciale utilisée pour contrôler l’accès à des ressources.
Il existe deux opérations fondamentales :
wait(S) ou P(S) : décrémente S. Si S < 0, le processus est bloqué.
signal(S) ou V(S) : incrémente S. Si des processus sont en attente, l’un d’eux est réveillé.
Exemple simple :
Semaphore S = 1;
wait(S); // demande d'accès
// section critique
signal(S); // libération
---
5. Sémaphores binaires vs comptants
Binaire (mutex) : ne vaut que 0 ou 1 → utilisé pour l’exclusion mutuelle
Comptant : peut avoir n’importe quelle valeur entière → utilisé pour les files d’attente
---
Souhaites-tu que je continue avec les problèmes classiques de synchronisation (philosophes,
lecteurs/rédacteurs, buffer borné) ou veux-tu un petit exercice sur les sémaphores pour tester ta
compréhension ?
Parfait, on enchaîne avec les problèmes classiques de synchronisation, qui sont souvent posés en
examen ou entretien. Ils illustrent comment utiliser les sémaphores dans des situations concrètes.
---
1. Le problème du tampon borné (Bounded Buffer Problem)
Aussi appelé Producteur - Consommateur.
Contexte :
Un producteur crée des éléments et les place dans un tampon (buffer).
Un consommateur retire les éléments du tampon.
Le tampon a une capacité limitée (N éléments).
Objectif :
Ne pas produire quand le tampon est plein.
Ne pas consommer quand le tampon est vide.
Éviter que le producteur et le consommateur modifient le tampon en même temps.
Sémaphores utilisés :
mutex (binaire) = contrôle l’accès au tampon (exclusion mutuelle)
empty (comptant) = nombre de cases vides dans le tampon
full (comptant) = nombre de cases pleines
Initialisation :
mutex = 1;
empty = N; // N = taille du tampon
full = 0;
Code du producteur :
do {
produire_un_element();
wait(empty); // attendre une place vide
wait(mutex); // entrer section critique
ajouter_au_buffer();
signal(mutex); // sortir de la section critique
signal(full); // indiquer qu’un élément est dispo
} while (true);
Code du consommateur :
do {
wait(full); // attendre qu’un élément soit disponible
wait(mutex); // entrer section critique
retirer_du_buffer();
signal(mutex); // sortir de la section critique
signal(empty); // indiquer qu’une place s’est libérée
consommer_element();
} while (true);
---
2. Le problème des lecteurs/rédacteurs (Readers-Writers)
Contexte :
Plusieurs lecteurs peuvent lire en même temps.
Un seul rédacteur peut écrire à la fois.
Aucun lecteur ne doit lire pendant qu’un rédacteur écrit.
But :
Autoriser plusieurs lecteurs en même temps
Mais un seul rédacteur exclusif
Solution :
Utiliser un compteur readcount et deux sémaphores :
mutex : protège readcount
wrt : protège l’accès exclusif à la ressource
Code du lecteur :
wait(mutex);
readcount++;
if (readcount == 1)
wait(wrt); // premier lecteur bloque les écrivains
signal(mutex);
// LECTURE
wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt); // dernier lecteur libère l'accès
signal(mutex);
Code du rédacteur :
wait(wrt);
// ÉCRITURE
signal(wrt);
---
3. Le problème des philosophes (Dining Philosophers)
Contexte :
5 philosophes autour d’une table.
Chaque philosophe a besoin de 2 baguettes pour manger (une à gauche, une à droite).
Il ne peut manger que s’il a les deux baguettes.
Risque de blocage (deadlock) si tous prennent une seule baguette en même temps.
Solution simple (avec sémaphores) :
Une baguette = un sémaphore
Le philosophe i prend :
wait(chopstick[i]);
wait(chopstick[(i + 1) % 5]);
Et relâche après avoir mangé :
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
Mais attention : cette solution peut mener à un deadlock si tous prennent leur baguette gauche en
même temps.
Amélioration possible :
Faire en sorte que seulement 4 philosophes maximum puissent essayer de manger en même temps.
Utiliser un sémaphore général room = 4 :
wait(room);
wait(chopstick[i]);
wait(chopstick[(i + 1) % 5]);
// manger
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
signal(room);
---
Souhaites-tu qu’on passe maintenant aux constructeurs plus avancés comme les régions critiques et les
moniteurs, ou tu veux faire un petit quiz sur ces trois problèmes classiques ?
