ENSI 2012/2013

Ce document présente un ensemble d'exercices sur l'ordonnancement de processus, destiné à évaluer les compétences en compréhension et application des algorithmes d'ordonnancement classiques en systèmes d'exploitation. Les exercices portent sur la construction de diagrammes de Gantt, le calcul des temps moyens de traitement, ainsi que l'analyse comparative des algorithmes FIFO, PCTER, SJF, SRT et tourniquet avec différents quantum.

Exercice 1

On considère cinq exécutions de processus avec des durées exprimées en secondes. Il s'agit de :

• 1. Donner les diagrammes de Gantt et calculer les temps moyens de traitement obtenus avec les algorithmes FIFO (Premier arrivé - Premier servi), PCTER (Plus Court Temps d’Exécution Restant) et Tourniquet (quantum = 1), en supposant un temps de commutation de contexte négligeable.
• 2. Si le temps de commutation est de 0,5 seconde, calculer le temps moyen de traitement pour PCTER et Tourniquet, puis en déduire une conclusion.

1. Diagrammes de Gantt et temps moyens avec temps de commutation négligeable

Le premier point demande de représenter graphiquement l'exécution des processus selon les trois algorithmes, puis de calculer le temps moyen de traitement (tmt) pour chacun.

Le FIFO exécute les processus dans l'ordre d'arrivée sans interruption. Le PCTER privilégie toujours le processus avec le plus court temps d'exécution restant, ce qui peut entraîner des interruptions. Le Tourniquet exécute chaque processus par tranches de 1 seconde (quantum = 1), en alternant entre les processus prêts.

Les diagrammes de Gantt ne sont pas fournis dans le document, mais la méthode consiste à placer sur une ligne temporelle les blocs d'exécution de chaque processus selon l'algorithme choisi.

2. Calcul du temps moyen de traitement avec un temps de commutation de 0,5 seconde

Le temps moyen de traitement (tmt) est calculé en tenant compte du temps d'arrivée et de fin de chaque processus, ainsi que du nombre de commutations de contexte (changement de processus élu).

Pour le cas PCTER :

Nombre de commutations : 5

Calcul du tmt :

((18,5 - 0) + (12 - 1) + (3,5 - 1) + (7,5 - 2) + (5 - 3)) / 5 = 7,9 secondes

Pour le cas Tourniquet :

Nombre de commutations : 13

Calcul du tmt :

((22,5 - 0) + (19 - 1) + (11,5 - 1) + (14,5 - 2) + (10 - 3)) / 5 = 14,1 secondes

Conclusion : Même en tenant compte du temps de commutation, l'algorithme PCTER reste plus performant que le Tourniquet en termes de temps moyen de traitement. Cependant, le temps dû aux commutations est plus sensible avec le protocole Tourniquet, ce qui implique que ce dernier doit être utilisé avec un quantum modéré pour limiter l'impact des commutations.

Réponse finale :

• Temps moyen de traitement PCTER avec commutation : 7,9 secondes
• Temps moyen de traitement Tourniquet avec commutation : 14,1 secondes
• L'algorithme PCTER est meilleur que le Tourniquet même en tenant compte du temps de commutation.

Exercice 2

Avec les processus listés dans un tableau non fourni, il est demandé de dessiner un schéma illustrant leur exécution selon différents algorithmes :

• (a) Algorithme FCFS (First Come First Served)
• (b) Algorithme SJF (Shortest Job First)
• (c) Algorithme SRT (Shortest Remaining Time)
• (d) Algorithme Tourniquet avec quantum = 2
• (e) Algorithme Tourniquet avec quantum = 1

(a) Algorithme FCFS

Les processus sont exécutés dans l'ordre de leur arrivée, sans interruption. Chaque processus commence son exécution dès que le précédent est terminé.

Réponse : Le schéma montre une exécution séquentielle des processus selon leur ordre d'arrivée.

(b) Algorithme SJF

L'algorithme SJF exécute toujours le processus le plus court disponible au moment où le processeur devient libre.

Déroulement :

• À la date 0, seul le processus A est disponible, il commence donc son exécution.
• À la date 3, le processus B est le seul dans la file, il s'exécute.
• À la date 9, B s'achève, le processus D est choisi car il est plus court que C.

Réponse : Le schéma illustre l'exécution dans l'ordre A, B, D, puis C.

(c) Algorithme SRT

L'algorithme SRT est une version préemptive du SJF, où le processus en cours peut être interrompu si un nouveau processus avec un temps restant plus court arrive.

Déroulement :

• À la date 0, A commence car il est seul.
• Lorsque B arrive, A continue car son temps restant est plus court.
• À la date 3, B est seul, il s'exécute.
• À la date 4,001, C arrive et commence son exécution car son temps restant (4) est inférieur à celui de B (4,999).
• À la date 6,001, C continue car son temps restant (1,999) est inférieur à celui de D (2).
• Après la fin de C, D s'exécute car son temps restant est inférieur à celui de B.

Réponse : Le schéma montre une exécution dynamique où les processus sont préemptés selon leur temps restant.

(d) Algorithme Tourniquet (quantum = 2)

Chaque processus s'exécute par tranches de 2 secondes, puis passe en fin de file si non terminé.

Déroulement :

• Après le premier quantum de A, B s'exécute.
• À la date 4, A est relancé, B revient dans la file.
• À la date 4,001, C arrive et rejoint la file après B.
• À la date 5, A termine, B s'exécute.
• À la date 6,001, D arrive et rejoint la file derrière C.
• À partir de la date 7, les processus C, D, B, C s'exécutent tour à tour.

Réponse : Le schéma montre une rotation des processus par quantum de 2 secondes avec arrivée dynamique de nouveaux processus.

(e) Algorithme Tourniquet (quantum = 1)

Chaque processus s'exécute par tranches de 1 seconde, avec alternance plus fréquente.

Déroulement :

• A s'exécute pendant deux tranches, car B n'arrive qu'à 1,001.
• B s'exécute à la date 4, C arrive à 4,001.
• B s'exécute à nouveau à la date 6, puis D arrive à 6,001.
• D rejoint la file derrière C.
• À partir de la date 7, l'exécution tourne en boucle entre C, D et B.

Réponse : Le schéma illustre une rotation rapide entre les processus avec quantum de 1 seconde, permettant une meilleure réactivité mais plus de commutations.

Méthode

Ce devoir récompense la maîtrise des algorithmes d'ordonnancement classiques, la capacité à construire des diagrammes de Gantt précis et à calculer les temps moyens de traitement en tenant compte des temps de commutation.

Les erreurs pénalisées sont :

• Ne pas respecter l’ordre d’arrivée ou la préemption selon l’algorithme.
• Oublier d’inclure les temps de commutation dans le calcul des temps moyens.
• Confondre quantum et durée d’exécution dans le tourniquet.
• Ne pas justifier les choix d’ordonnancement dans les cas préemptifs (SRT, PCTER).

Il est essentiel de détailler chaque étape, notamment dans les algorithmes préemptifs, pour montrer la compréhension des critères de sélection des processus et des impacts sur le temps de traitement.