Examen - Session Principale - Année Universitaire 2010/2011
Semestre : 2
Niveau d’étude : 1ère année
Matière : Systèmes d’Exploitation 1
Durée : 2 heures
Enseignants responsables : W. Youssef, A. Gazdar, A. Ben Chikha
Documents autorisés : Non
Nombre de pages : 7
Le barème est donné à titre indicatif. La clarté de la copie rendue sera prise en considération.
Institut Supérieur d’Informatique (ISI)
Exercice 1 : Questions de Compréhension (5 points)
- Étant donné un diagramme d’états/transitions, citer la ou les transition(s) à supprimer si on utilise un algorithme d’ordonnancement sans préemption (non préemptif).
Réponse : La transition à supprimer est celle passant de l’état Élu à l’état Prêt, car elle se produit uniquement lors d’une préemption.
- Qu’est-ce qu’un PCB ? Citer trois attributs du PCB.
Réponse : Le PCB (Process Control Block) est une structure de données contenant toutes les informations nécessaires pour décrire le contexte d’un processus. Ses attributs incluent :
- PID (Process ID) et PPID (Parent Process ID)
- État du processus (Prêt, Élu, Bloqué, etc.)
- Priorité
- Qu’est-ce que la MMU ? Expliquer son rôle.
Réponse : La MMU (Memory Management Unit) est une unité matérielle qui gère la mémoire en traduisant les adresses virtuelles en adresses physiques, assurant ainsi une isolation entre les processus et le matériel.
- Qu’est-ce que la fragmentation ? Quelle est la différence entre une fragmentation interne et externe ?
Réponse : La fragmentation est le phénomène de création d’espaces inutilisables en mémoire après l’allocation des processus. Ces fragments sont trop petits pour être utilisés.
- Fragmentation interne : Occurre à l’intérieur d’une partition, notamment dans le cas d’une allocation contiguë à partitions fixes.
- Fragmentation externe : Se produit entre les partitions, typiquement lors d’une allocation contiguë à partitions dynamiques.
- Où peut-on stocker les informations concernant les algorithmes de remplacement de page, comme la date de chargement d’une page utilisée dans l’algorithme FIFO ?
Réponse : Ces informations peuvent être stockées dans la table des pages, où chaque entrée contient des métadonnées associées à une page.
Exercice 2 : Gestion des Processus (7 points)
On considère un système monoprocesseur avec quatre processus : P1, P2, P3 et P4. Chaque processus effectue des calculs et des entrées/sorties (E/S) avec un disque selon les temps suivants :
| Processus | Temps d’exécution CPU (1ère phase) | Temps E/S (1ère phase) | Temps d’exécution CPU (2ème phase) | Temps E/S (2ème phase) |
|---|---|---|---|---|
| P1 | 3 | 7 | 1 | 1 |
| P2 | 4 | 3 | 2 | 2 |
| P3 | 2 | 3 | 2 | 1 |
| P4 | 7 | 3 | — | — |
1. Ordonnancement par priorité préemptible (FIFO pour E/S)
Les processus sont ordonnancés selon leur priorité : P1 > P3 > P2 > P4. Les requêtes E/S sont servies en FIFO.
Temps de rotation moyen (TRM) : 19,5
2. Ordonnancement par priorité préemptible (priorité pour E/S)
Les requêtes E/S sont servies selon la priorité des processus : le processus en attente avec la plus haute priorité est servi en premier.
Temps de rotation moyen (TRM) : 19
3. Ordonnancement tourniquet (quantum = 2, FIFO pour E/S)
Les processus sont ordonnancés selon une politique tourniquet avec un quantum de 2 unités de temps, dans l’ordre d’arrivée : P1, P2, P3, P4.
Temps de rotation moyen (TRM) : 20,5
4. Comparaison et interprétation des TRM
L’algorithme tourniquet présente un TRM plus élevé que l’algorithme de priorité, car il répartit équitablement le temps entre les processus, prolongeant leur durée d’exécution dans le système. Dans cet exemple, le changement de politique pour les E/S n’a pas modifié significativement le TRM.
Exercice 3 : Gestion de la Mémoire (3 points)
Pour la suite de pages {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}, analyser l’évolution de la mémoire centrale avec les algorithmes suivants :
Algorithme FIFO
Avec 3 cases mémoire : 9 défauts de page.
Avec 4 cases mémoire : 10 défauts de page.
Observation : L’augmentation du nombre de cases mémoire n’entraîne pas toujours une réduction des défauts de page. Ici, le nombre de défauts augmente en raison de la séquence initiale des pages.
Algorithme optimal
Avec 4 cases mémoire : 6 défauts de page.
Exercice 4 : Gestion de la Mémoire (5 points)
Étant donnés :
- Une table des pages de taille 128 Ko
- 65 536 entrées dans la table des pages
- Un déplacement codé sur 16 bits
- Une entrée de la table des pages : |n|1|3|, où n est le nombre de bits pour coder un cadre, 1 le bit de présence/absence et 3 les bits pour la date de chargement.
- Déterminer la valeur de n (nombre de bits pour coder un cadre).
Calcul : Taille de la table des pages = (n + 4) × nombre d’entrées.
128 Ko = (n + 4) × 65 536.
128 Ko = (n + 4) × 216.
n = 12 (car 128 Ko = 212 octets).
- Calculer la taille de la mémoire physique.
Réponse : 256 Mo (228 octets).
- Donner la taille de l’espace d’adressage virtuel.
Réponse : 4 Go (232 octets).
- Donner le nombre de bits du bus d’adressage.
Réponse : 32 bits.
- Dire si le nombre d’entrées de la table des pages change en cas d’augmentation de la mémoire physique de 1 Mo.
Réponse : Non, le nombre d’entrées dépend uniquement de la taille de l’espace d’adressage virtuel.
Foire Aux Questions (FAQ)
1. Qu’est-ce qu’un algorithme d’ordonnancement non préemptif ?
Un algorithme d’ordonnancement non préemptif ne suspend pas un processus en cours d’exécution pour lui en attribuer un autre. La transition de l’état Élu à Prêt est donc inutile dans ce contexte.
2. Pourquoi l’algorithme FIFO peut-il entraîner plus de défauts de page avec une mémoire plus grande ?
L’augmentation des cases mémoire peut modifier la séquence de remplacement des pages, entraînant parfois plus de défauts si les pages remplacées sont réutilisées plus rapidement que prévu.
3. En quoi consiste la politique d’ordonnancement tourniquet ?
La politique tourniquet attribue à chaque processus une durée fixe (quantum) avant de le suspendre et de passer au suivant, garantissant ainsi une exécution équitable.