Aller au contenu principal
Valrose.tech

Systèmes d'exploitation · L3 · Section 1/6

Ordonnancement

Progression

Points d’expérience : —XPSérie de jours consécutifs : —· —Progression du module : — / —compris

#Ordonnancement

Objectifs d’apprentissage

  • Choisir un algorithme selon le contexte (interactif, batch, mixte).
  • Expliquer l’impact du quantum (RR) sur réactivité vs overhead.
  • Identifier famine (starvation), convoy effect et techniques d’atténuation (aging).
  • Interpréter les métriques: réponse, attente, turnaround, throughput.

#Simulation simple (Round Robin)

Chargement de l’éditeur...

#Visualisation: file prête (RR)

A
B
C
Avant
Arrière
File initialisée avec 3 éléments
Étape 1 / 1 | Taille: 3

#Animation: politiques et compromis

FCFS
Simple ; peut souffrir d’effet convoi
SJF/SRTF
Minimise temps moyen ; nécessite estimation
Round‑Robin
Équité ; quantum ↔ réactivité/overhead
Priorités/Aging
Interactivité ; éviter la famine

#Comparatif visuel (mêmes jobs)

Jobs: A=5, B=4, C=3 (durées CPU, arrivée à t=0). Quantum RR=2.

Temps: 0         5         9        12
Gantt: | AAAAA | BBBB | CCC |
Attente moyenne ≈ (0 + 5 + 9)/3 = 4.67
Étape 1 / 3

#Exercice : Algorithme Shortest Remaining Time First (SRTF)

Implémentez l'algorithme SRTF (préemptif) pour l'ordonnancement de processus.

#Instructions

  1. SRTF est la version préemptive de SJF : le processus avec le temps restant le plus court est toujours exécuté.
  2. À chaque unité de temps, vérifiez si un nouveau processus arrive.
  3. Si un nouveau processus a un temps restant plus court que le processus courant, préemptez le processus courant.
  4. Suivez les métriques : temps d'attente, temps de réponse, temps de rotation.

#Exemple de code

pythonpython

1def srtf_scheduling(processes):2    # processes: liste de tuples (nom, arrival_time, burst_time)3    n = len(processes)4    # Trier par temps d'arrivée5    processes.sort(key=lambda x: x[1])6    7    # Initialisation8    remaining_time = [p[2] for p in processes]9    completion_time = [0] * n10    waiting_time = [0] * n11    turnaround_time = [0] * n12    13    time = 014    completed = 0
Chargement de l’éditeur...

#Quiz

Quel algo favorise les petits jobs et peut pénaliser les longs ?
Quel algo favorise les petits jobs et peut pénaliser les longs ?

#MLFQ (Multi‑Level Feedback Queue)

Principe: plusieurs files de priorités; nouveaux jobs en haut, préemption agressive; descente si quantum consommé, remontée pour I/O bound.

#Animation: MLFQ

Quantums: [5, 10, 20]
Proc A file 1 • reste 30
Proc B file 1 • reste 15
Proc C file 1 • reste 50

#Mini‑simulation

Chargement de l’éditeur...

#Quiz éclair

Quel mécanisme réduit la famine dans un planificateur par priorités ?
Quel mécanisme réduit la famine dans un planificateur par priorités ?

#Politiques classiques et compromis

  • FCFS: simple mais sujet au « convoy effect » si un long job est devant.
  • SJF/SRTF: minimise le temps moyen si on estime la durée; risque de famine pour longs jobs; nécessite préemption pour SRTF.
  • Round‑Robin: bon pour l’interactif; quantum trop petit → overhead; trop grand → se rapproche de FCFS.

#Files multi‑niveaux et priorités

  • MLFQ: promeut les I/O‑bound (réactifs), dégrade les CPU‑bound; aging pour éviter la famine.
  • Inversion de priorité: protocole d’héritage/ceiling sur mutex pour éviter qu’un bas‑priorité bloque un haut‑priorité.