Systèmes d'Exploitation : Exercices sur l'Ordonnancement des Processus
Institut Supérieur d'Informatique - 1ère Année SIL
Semestre 2
Exercice 1
Cinq travaux (A, B, C, D et E) arrivent simultanément dans un centre de calcul. Leurs temps d'exécution sont estimés à 10, 6, 2, 4 et 8 secondes respectivement. Tracez le diagramme de Gantt et calculez le temps moyen de rotation pour chacun des algorithmes d'ordonnancement suivants, sans tenir compte du temps de commutation des processus :
- Premier arrivé, premier servi (FCFS) : exécution dans l'ordre 10, 6, 2, 4, 8 secondes ;
- Plus court d'abord (SJF) ;
- Tourniquet (Round-Robin) avec un quantum q = 4 secondes.
Exercice 2
Considérons un ensemble de processus avec des priorités dynamiques. Voici les consignes :
- A- En utilisant un algorithme d'ordonnancement basé sur la priorité (où les priorités sont croissantes : 5 est la plus prioritaire), présentez le diagramme de Gantt pour les priorités données dans le tableau.
- B- Pour une priorité dynamique recalculée toutes les 5 minutes, utilisez la formule suivante : arrondissez selon les règles suivantes : 3,5 ou 3,6 → 4, 3,1 ou 3,4 → 3.
1. Établissez le diagramme de Gantt avec ce recalcul de priorité.
2. Calculez le temps d'attente moyen ainsi que le temps de rotation moyen.
3. Comparez les résultats obtenus avec ceux de l'algorithme de priorité classique.
Exercice 3
Sur une architecture monoprocesseur, exécutez quatre programmes dont les comportements sont définis comme suit :
- Programme P1 : Date d'arrivée à 0, calcul pendant 6 unités de temps, E/S pendant 3 unités de temps, calcul pendant 3 unités de temps, E/S pendant 4 unités de temps, calcul pendant 2 unités de temps.
- Programme P2 : Date d'arrivée à 3, calcul pendant 2 unités de temps, E/S pendant 5 unités de temps, calcul pendant 2 unités de temps, E/S pendant 2 unités de temps, calcul pendant 1 unité de temps.
- Programme P3 : Date d'arrivée à 5, calcul pendant 2 unités de temps, E/S pendant 4 unités de temps, calcul pendant 1 unité de temps.
- Programme P4 : Date d'arrivée à 8, calcul pendant 1 unité de temps, E/S pendant 1 unité de temps, calcul pendant 1 unité de temps.
On suppose un seul canal simple pour gérer le disque, avec une politique FCFS pour les requêtes. L'ordonnancement sur le processeur suit la stratégie SRT (Shortest Remaining Time).
- Remplissez le diagramme de Gantt correspondant.
- Calculez le nombre de commutations de contexte.
- Déterminez les :
- Temps d'attente du processeur pour chaque programme.
- Temps d'exécution total de chaque programme.
Exercice 4
Quatre processus (A, B, C, D) nécessitent les ressources suivantes :
- Processus A : 7 unités de temps CPU, 3 unités de temps E/S, puis 5 unités de temps CPU.
- Processus B : 6 unités de temps CPU, 4 unités de temps E/S, puis 4 unités de temps CPU.
- Processus C : 5 unités de temps CPU.
- Processus D : 1 unité de temps CPU, 4 unités de temps E/S, puis 2 unités de temps CPU.
Les processus arrivent selon les instants suivants : A à 0, B à 1, C à 9, D à 12.
Montrez comment ces processus utilisent le processeur dans les cas suivants :
- Chaque processus dispose de son propre périphérique E/S et l'ordonnanceur fonctionne selon FCFS (sans préemption).
- Chaque processus possède son propre périphérique E/S, et l'ordonnanceur utilise Round-Robin avec un quantum de 5 secondes. Le temps de commutation est nul. Indiquez les temps de rotation des processus A, B, C et D.
- Les trois processus (A, B, D) partagent le même périphérique E/S, dont la file d'attente est gérée par FCFS. L'ordonnanceur du processeur utilise Round-Robin avec un quantum de 5 secondes. Le temps de commutation est supposé nul.
Exercice 5
Trois processus (P1, P2, P3) ont des durées d'exécution respectives de 6, 4 et 8 unités de temps. Après 1 unité de temps d'exécution, le processus P2 crée un processus fils (P4) de 3 unités de temps. Le processus P4, après 2 unités de temps d'exécution, crée à son tour un processus fils (P5) de 2 unités de temps. Un processus parent doit attendre la fin de son processus fils avant de continuer.
En supposant que tous les processus sont gérés par l'ordonnancement Round-Robin avec un quantum de 2 unités de temps, tracez le diagramme de Gantt.
Foire Aux Questions (FAQ)
Qu'est-ce qu'un diagramme de Gantt ?
Un diagramme de Gantt est un outil visuel utilisé pour représenter l'ordonnancement des tâches ou processus sur une période donnée. Il permet de visualiser les temps d'exécution et les éventuels chevauchements.
Comment calculer le temps moyen de rotation ?
Le temps moyen de rotation est calculé en additionnant les temps de rotation de tous les processus, puis en divisant par le nombre total de processus. Le temps de rotation d'un processus est la somme de son temps d'attente et de son temps d'exécution.
Quelle est la différence entre FCFS et Round-Robin ?
FCFS (First-Come, First-Served) est un algorithme sans préemption où le processus qui arrive en premier est exécuté en premier. Round-Robin est un algorithme avec préemption où chaque processus obtient un temps d'exécution limité (quantum) avant que le processeur ne passe au processus suivant.