Questions de cours (4,5 points)
- Pourquoi l’algorithme d’ordonnancement SJF n’est-il pas réellement applicable ? Car il est impossible de prévoir la durée d’exécution d’un processus.
- A. Définir la notion de PCB.
PCB : Process Control Block est une structure de données associée à un processus et contenant toutes les informations décrivant son contexte, comme le bloc de contrôle.
- B. Citer quatre attributs parmi ceux qui constituent le PCB :
- PID (Identifiant du processus)
- PPID (Identifiant du processus parent)
- État du processus
- Priorité du processus
- Quel est l’effet de la diminution du quantum sur les performances de l’algorithme RR (Round Robin) ? La diminution du quantum entraîne une dégradation des performances de l’algorithme RR en augmentant le temps de commutation et de changement de contexte.
- Les algorithmes d’ordonnancement basés sur des priorités peuvent engendrer la famine (non-exécution) des processus à faible priorité. Comment peut-on éviter ce problème ?
On peut utiliser un algorithme de tourniquet (Round Robin) ou une approche de priorité dynamique.
- Citer trois architectures des systèmes d’exploitation :
- Monolithique
- En couches
- Modulaire
Exercice 1
Gestion des processus (10 points)
On considère une architecture monoprocesseur avec les processus suivants :
| Processus | Temps d’arrivée | Temps d’exécution total |
|---|---|---|
| A | 0 | 10 |
| B | 0 | 6 |
| C | 1 | 8 |
| D | 5 | 4 |
Hypothèses :
- Un seul canal pour gérer le disque.
- Ordonnancement des requêtes selon la politique FCFS (First-Come First-Served).
- Une opération d’entrée-sortie commencée ne peut être préemptée.
- À la moitié de son exécution, chaque processus doit effectuer 3 unités de temps d’entrée-sortie avant de reprendre.
A. Ordonnancement par tourniquet (Round Robin) avec quantum q=2
A.1.
Remplir les grilles annexes A selon les règles suivantes :
- Si plusieurs processus sont disponibles, choisir celui qui attend le plus longtemps.
- En cas d’égalité de temps d’attente, privilégier l’ordre A-B-C-D.
A.2.
Calculer le temps de rotation moyen (TRM1) avec la formule suivante :
TRM1 = [(Tfin A - Tarrivée A) + (Tfin B - Tarrivée B) + (Tfin C - Tarrivée C) + (Tfin D - Tarrivée D)] / 4
Résultat : TRM1 = 21
B. Ordonnancement à priorité préemptive (SJF avec préemption)
B.1.
Il s’agit d’un algorithme à priorité dynamique, car la priorité d’un processus évolue en fonction du temps d’exécution total restant.
B.2.
L’algorithme SNRT (Shortest Remaining Time Next) ou SRT (Shortest Remaining Time), équivalent à SJF avec préemption, produit un résultat similaire en privilégiant les processus avec le temps d’exécution restant le plus court.
B.3.
Remplir les grilles annexes B selon les règles suivantes :
- En cas d’égalité de priorité, privilégier le processus en cours d’exécution.
B.4.
Calculer le temps de rotation moyen (TRM2) avec la formule suivante :
TRM2 = [(Tfin A - Tarrivée A) + (Tfin B - Tarrivée B) + (Tfin C - Tarrivée C) + (Tfin D - Tarrivée D)] / 4
Résultat : TRM2 = 17
C. Comparaison et analyse des résultats
Le TRM1 (21) est supérieur au TRM2 (17), car l’algorithme SNRT permet de terminer les processus les plus courts en priorité, réduisant ainsi leur temps de séjour.
Exercice 2
Gestion de la mémoire (5,5 points)
A. Allocation contiguë
Un espace mémoire de 1000 blocs utilise une allocation contiguë. Les opérations (+) et (-) représentent respectivement une demande d’allocation et de libération.
A.1.
État de la mémoire centrale après chaque étape (algorithme First Fit) :
- Étape 1 : A (300), B (200), C (260)
- Étape 2 : B (-200), D (100), A (-300), E (250), C (-260)
- Étape 3 : G (150), H (120), D (-100), H (-120), I (200)
- Étape 4 : G (-150), E (-250), J (100), J (-100), I (-200)
A.2.
Avantage de l’allocation First Fit par rapport à Best Fit :
First Fit est plus simple à implémenter et plus rapide à exécuter, car il alloue le premier bloc disponible, contrairement à Best Fit qui parcourt toute la mémoire pour trouver le bloc le plus adapté.
B. Pagination
B.1.
La pagination est une technique de gestion de la mémoire non contiguë qui divise la mémoire en blocs de taille égale (appelés pages physiques ou frames) et les processus en blocs de même taille (appelés pages logiques). Elle utilise une table de pages pour associer les pages logiques aux frames physiques.
Avantages par rapport à l’allocation contiguë (fixe ou dynamique) :
- Réduction de la fragmentation externe.
- Flexibilité accrue dans l’allocation des ressources.
- Amélioration des performances grâce à une meilleure utilisation de la mémoire.
B.2.
Calcul de l’adresse physique pour l’adresse logique 36870 :
Paramètres :
- Bus d’adresses de 16 bits.
- Taille d’une page de 4 Ko (4096 octets).
Formule :
Numéro de page = Adresse logique / Taille page et Offset = Adresse logique % Taille page
Résultat :
Numéro de page = 9, Offset = 6 → Adresse physique = 12292 (binaire : 0011 0000 0000 0110).
FAQ
- Qu’est-ce que l’algorithme SJF ? SJF (Shortest Job First) est un algorithme d’ordonnancement qui privilégie les processus avec le temps d’exécution le plus court.
- Quelle est la différence entre First Fit et Best Fit ? First Fit alloue le premier bloc disponible, tandis que Best Fit cherche le bloc le plus adapté en taille pour réduire la fragmentation.
- Comment fonctionne la pagination en mémoire ? La pagination divise la mémoire en frames et les processus en pages, utilisant une table pour mapper les pages logiques aux frames physiques, ce qui élimine la fragmentation externe.