Devoir Surveillé - Systèmes d'Exploitation I
Questions de cours (5 points)
- Pourquoi l'algorithme d'ordonnancement SJF (Shortest Job First) n'est-il pas réellement applicable en pratique ?
- A. Définir la notion de PCB (Process Control Block).
B. Citer quatre attributs parmi ceux qui constituent le PCB. - Quel est l'effet de la diminution du quantum sur les performances de l'algorithme RR (Round Robin) ?
- 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 ?
- Citer trois architectures des systèmes d'exploitation (sans détails).
Exercice 1 : Gestion des processus (9 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.
- Politique FCFS (First Come First Served) pour l'ordre des requêtes.
- Les opérations d'entrée-sortie ne peuvent pas être préemptées.
- À la moitié de son exécution, chaque processus doit faire 3 unités de temps d'entrée-sortie, puis reprendre son exécution.
Partie A : Ordonnancement par Round Robin (quantum q=2)
A.1. Compléter les grilles annexes A en suivant les règles suivantes :
- Si le système a le choix entre plusieurs processus, il choisit celui qui attend depuis le plus longtemps.
- Si plusieurs processus ont le même temps d'attente, adopter l'ordre A-B-C-D.
A.2. Calculer le temps de rotation moyen (TRM1) de cet algorithme en fournissant la formule détaillée.
Partie B : Ordonnancement par priorité préemptive
La priorité d'un processus est inversement proportionnelle à son temps d'exécution total restant. Autrement dit, le processus ayant le temps d'exécution total restant le plus court est le plus prioritaire.
B.1. S'agit-il d'un algorithme à priorité statique ou dynamique ? Justifier.
B.2. Quel algorithme connu produit un résultat équivalent ? Justifier votre réponse.
B.3. Compléter les grilles annexes B en suivant les règles suivantes :
- Si plusieurs processus ont la même priorité, favoriser celui qui était en cours d'exécution.
B.4. Calculer le temps de rotation moyen (TRM2) de cet algorithme en fournissant la formule détaillée.
Partie C : Comparaison et analyse
Comparer TRM1 et TRM2 et analyser les résultats obtenus.
Exercice 2 : Gestion de la mémoire (6 points)
Partie A : Allocation contiguë
On considère un espace mémoire de 1000 blocs utilisant une allocation contiguë. Les demandes d'allocation (+) et de libération (-) sont indiquées ci-dessous.
A.1. En utilisant l'algorithme First Fit, indiquer les différents états de la mémoire centrale après chaque étape (les étapes sont successives, initialement la mémoire est vide) :
- É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. Quel est l'avantage d'une stratégie d'allocation First Fit par rapport à une stratégie Best Fit ?
Partie B : Pagination
B.1. Définir la pagination. Quels sont ses avantages par rapport aux techniques de gestion contiguë de la mémoire (par partition fixe et dynamique) ?
B.2. Calculer l'adresse physique correspondant à l'adresse logique 36870, en supposant que :
- Bus d'adresses de 16 bits
- Taille d'une page de 4 Ko
- Table de page suivante (valeurs en décimal) :
| Index | Adresse physique |
|---|---|
| 15 | 000 |
| 14 | 000 |
| 13 | 010 |
| 12 | 000 |
| 11 | 100 |
| 10 | 111 |
| 09 | 011 |
| 08 | 000 |
| 07 | 110 |
| 06 | 000 |
| 05 | 000 |
| 04 | 101 |
| 03 | 000 |
| 02 | 000 |
| 01 | 000 |
| 00 | 001 |
Questions fréquentes (FAQ)
Qu'est-ce qu'un algorithme d'ordonnancement SJF ?
SJF (Shortest Job First) est un algorithme théorique qui exécute toujours le processus ayant le temps d'exécution le plus court. Il n'est pas applicable en pratique car le temps d'exécution d'un processus est souvent inconnu avant son exécution.
Quelle est la différence entre First Fit et Best Fit ?
First Fit alloue le premier bloc mémoire disponible qui est suffisamment grand, tandis que Best Fit choisit le bloc le plus petit qui puisse satisfaire la demande, ce qui peut entraîner une fragmentation plus importante.
Pourquoi la pagination est-elle préférée à l'allocation contiguë ?
La pagination permet une meilleure utilisation de la mémoire en évitant la fragmentation externe et en facilitant le partage de mémoire entre processus. Elle offre aussi une plus grande flexibilité pour la gestion des programmes.