Comment fonctionne l'ordonnancement CPU, et quels sont les algorithmes courants ?

Question

IT Interview Practice · Accepted Answer

Le **CPU scheduling (ordonnancement CPU)** est la décision du kernel sur *quel* thread prêt obtient le CPU *ensuite*, et pour *combien de temps*. Comme il y a généralement plus de threads exécutables que de cœurs, le **scheduler** les multiplexe, en cherchant à équilibrer des objectifs concurrents — **throughput**, **latence / temps de réponse faible**, et **équité** — tout en évitant la **starvation** (famine).

## Les algorithmes courants

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

**Round-robin** illustre le réglage central — le **quantum** :

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## Les schedulers réels

Le choix par défaut de longue date de Linux était **CFS (Completely Fair Scheduler)** : au lieu de tranches fixes, il suit le **virtual runtime (vruntime)** de chaque tâche et exécute toujours le thread qui a reçu le moins de CPU jusqu'ici, pondéré par sa valeur **nice** — approximant « chacun obtient une part équitable ». Il indexe un arbre rouge-noir (red-black tree) par vruntime, donc choisir la tâche suivante est en O(log n). (Les kernels plus récents utilisent EEVDF, un raffinement avec le même objectif d'équité plus des bornes de latence plus strictes.)

**Preemptive vs cooperative :** les OS modernes sont **preemptive** (préemptifs) — une timer interrupt permet au scheduler de reprendre de force le CPU, de sorte qu'un thread ne peut pas monopoliser un cœur.

## Pourquoi c'est important

L'ordonnancement façonne directement la latence et le throughput ressentis par les utilisateurs. Les recruteurs sondent ce sujet pour voir si vous comprenez les compromis — pourquoi une charge de travail interactive veut des quanta courts ou un boost de priorité, pourquoi le priority scheduling a besoin de l'**aging** pour éviter la starvation, et comment MLFQ/CFS obtiennent un bon comportement interactif sans connaître à l'avance la durée des jobs. C'est aussi le modèle mental derrière le réglage de `nice`, des priorités temps réel, et le diagnostic d'un service affamé ou saccadé.

Les algorithmes courants

Les schedulers réels

Pourquoi c'est important

Questions connexes