Process Scheduling Algorithms and Concepts

L'Ordonnancement des Processus : Le Cheatsheet Ultime

L'ordonnancement des processus est une fonction cruciale des systèmes d'exploitation, gérant la compétition entre plusieurs processus pour l'accès au temps processeur (UCT).

Objectifs Clés de l'Ordonnancement

• Maximiser l'utilisation du processeur : Garder l'UCT occupée le plus longtemps possible.

• Temps de réponse acceptable : Assurer une bonne réactivité pour l'utilisateur.

• Équité : Distribuer le temps UCT selon les politiques définies.

L'Ordonnanceur (Scheduler)

• C'est la partie du système d'exploitation qui gère les états des processus (Prêt, Actif, etc.) et alloue l'UCT.

• Il prend une décision chaque fois qu'un processus exécutant est interrompu ou qu'un nouvel événement survient.

Décisions de l'Ordonnanceur (Quand interveint-il ?)

1. Un processus se présente (nouveau) ou se termine.

2. Un processus exécutant devient bloqué (attente I/O, par exemple).

3. Un processus passe de l'état "exécutant" à "prêt".

4. Un processus passe de "attente" à "prêt".

Préemption : L'ordonnanceur retire l'UCT à un processus sans que celui-ci ne l'ait libérée de sa propre initiative. Par exemple, si un processus de plus haute priorité devient prêt, l'ordonnanceur peut préempter le processus courant.

Critères de Performance des Algorithmes d'Ordonnancement

• Utilisation UCT : Pourcentage d'occupation de l'UCT (à maximiser).

• Débit (Throughput) : Nombre de processus terminés par unité de temps (à maximiser).

• Temps de rotation (Turnaround Time - TAT) : Durée totale passée dans le système (fin - arrivée) (à minimiser).

• Temps d'attente (Waiting Time - WT) : Temps passé dans la file des prêts (à minimiser).

• Temps de réponse (Response Time - RT) : Temps entre la demande et la première réponse (pour les systèmes interactifs) (à minimiser).

Types d'Ordonnancement

• Préemptif : L'ordonnanceur peut interrompre un processus en cours d'exécution pour en allouer un autre (souvent plus prioritaire).

• Coopératif (Non-préemptif) : Un processus garde le contrôle de l'UCT jusqu'à son achèvement ou jusqu'à ce qu'il se bloque volontairement.

Algorithmes d'Ordonnancement

1. First Come, First Served (FCFS) / Premier Arrivé, Premier Servi

• Principe : Les processus sont exécutés dans leur ordre d'arrivée. C'est un algorithme non-préemptif.

• Simplicité : Facile à implémenter.

• Inconvénient majeur : Le temps d'attente moyen peut varier grandement selon l'ordre d'arrivée (ex: un long processus en premier bloque tout les autres).

• Exemple (avec P1=24, P2=3, P3=3 arrivant à dans l'ordre P1, P2, P3):
  P1 (0-24), P2 (24-27), P3 (27-30)
  WT moyen:
  Si l'ordre est P2, P3, P1: P2 (0-3), P3 (3-6), P1 (6-30)
  WT moyen: (Beaucoup mieux !)

2. Shortest Job First (SJF) / Plus Court d'Abord

• Principe : L'ordonnanceur choisit le processus avec le temps d'exécution (CPU burst) le plus court.

• Optimalité : Minimise le temps d'attente moyen.

• Inconvénient : Nécessite la connaissance du temps de service à l'avance (souvent difficile à estimer).

• Risque : Peut entraîner la *famine* des processus longs.

• Variantes:

  • SJF non-préemptif : Une fois qu'un processus démarre, il s'exécute jusqu'à la fin.

  • SJF préemptif (Shortest Remaining Time First - SRTF) : À l'arrivée d'un nouveau processus, l'ordonnanceur compare le temps restant du processus courant avec le burst du nouveau. Si le nouveau est plus court, il y a préemption. C'est une extension "dynamique" du SJF.

• Exemple (SJF préemptif vs non-préemptif):

  Processus	Arrivée	Cycle
  	0	7
  	2	4
  	4	1
  	5	4

  
  SJF non-préemptif WT moyen = 4
  SJF préemptif WT moyen = 3 (Meilleur!)

3. Round Robin (RR) / Tourniquet

• Principe : Chaque processus reçoit un petit quantum de temps fixe (Q) pour s'exécuter. C'est un algorithme préemptif.

• Fonctionnement : Les processus sont exécutés en séquence dans une file circulaire (RR = FCFS + Q). Si un processus n'a pas terminé après son quantum, il est interrompu et replacé en fin de file.

• Avantages :

  • Assure un traitement équitable.

  • Offre une réactivité raisonnable aux événements.

• Inconvénients :

  • Quantum trop court → surcoût important lié aux changements de contexte.

  • Quantum trop long → se rapproche de FCFS, perd la réactivité.

  • Non adapté si certaines priorités sont cruciales.

4. Ordonnancement à Priorité (Priority Scheduling)

• Principe : À chaque processus est attribuée une priorité. L'ordonnanceur choisit le processus le plus prioritaire parmi ceux qui sont prêts.

• Gestion des égalités : Les processus de même priorité sont souvent gérés par FCFS ou Round Robin.

• Problèmes :

  • Famine : Les processus de faible priorité peuvent ne jamais s'exécuter.

  • Vieillissement (Aging) : Une solution pour la famine où la priorité d'un processus augmente avec son temps d'attente.

5. Files d'Attente Rétroactives (Multilevel Feedback Queues)

• Principe : Utilisation de plusieurs files d'attente avec des priorités et des quanta de temps variés.

• Fonctionnement :

  • Un nouveau processus entre dans la file de plus haut niveau (plus haute priorité, petit quantum).

  • S'il termine avant son quantum, il reste à ce niveau ou est retiré.

  • S'il dépasse son quantum, il est rétrogradé à la file de niveau inférieur (priorité plus basse, quantum plus long ou FCFS).

  • Si un processus est bloqué avant la fin de son quantum (e.g., attente I/O), il peut être promu à un niveau supérieur pour récompenser son comportement interactif.

• Avantages : Combine l'interactivité (petits quanta pour les courtes tâches) avec l'efficacité (grands quanta pour les longues tâches). Permet de donner l'UCT rapidement aux tâches interactives sans pénaliser excessivement les tâches de fond.

• Exemple de configuration:

  • Q0 : Tourniquet, quantum 8 ms

  • Q1 : Tourniquet, quantum 16 ms

  • Q2 : FCFS

  
  Un nouveau processus commence dans Q0. Si non terminé, passe à Q1. Si encore non terminé, passe à Q2.

Conclusion

Le choix de l'algorithme d'ordonnancement dépend des objectifs spécifiques du système (temps réel, interactif, batch, etc.). Chaque algorithme présente des compromis entre l'utilisation du CPU, le temps de réponse, le débit et l'équité.