Πώς λειτουργεί ο χρονοπρογραμματισμός της CPU (CPU scheduling), και ποιοι είναι οι συνηθισμένοι αλγόριθμοι;

Question

IT Interview Practice · Accepted Answer

Ο **χρονοπρογραμματισμός CPU (CPU scheduling)** είναι η απόφαση του kernel για το *ποιο* έτοιμο νήμα παίρνει τη CPU *στη συνέχεια*, και για *πόσο*. Επειδή συνήθως υπάρχουν περισσότερα εκτελέσιμα νήματα από πυρήνες, ο **scheduler** τα πολυπλέκει (multiplexes), στοχεύοντας να ισορροπήσει ανταγωνιστικούς στόχους — **throughput**, **χαμηλή latency / χρόνο απόκρισης**, και **δικαιοσύνη (fairness)** — αποφεύγοντας παράλληλα το **starvation**.

## Συνηθισμένοι αλγόριθμοι

```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** απεικονίζει το βασικό κουμπί ρύθμισης — το **quantum**:

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

## Πραγματικοί schedulers

Η μακροχρόνια προεπιλογή του Linux ήταν ο **CFS (Completely Fair Scheduler)**: αντί για σταθερά χρονικά διαστήματα παρακολουθεί το **virtual runtime (vruntime)** κάθε task και τρέχει πάντα το νήμα που έχει λάβει τη λιγότερη CPU μέχρι στιγμής, σταθμισμένο με την τιμή **nice** του — προσεγγίζοντας το "ο καθένας παίρνει ένα δίκαιο μερίδιο". Χρησιμοποιεί ως κλειδί ένα red-black tree με βάση το vruntime, οπότε η επιλογή του επόμενου task είναι O(log n). (Οι νεότεροι kernels χρησιμοποιούν EEVDF, μια βελτίωση με τον ίδιο στόχο δικαιοσύνης συν αυστηρότερα όρια latency.)

**Preemptive vs cooperative:** τα σύγχρονα OS είναι **preemptive** — ένα timer interrupt επιτρέπει στον scheduler να πάρει βίαια πίσω τη CPU, ώστε ένα νήμα να μην μπορεί να μονοπωλήσει έναν πυρήνα.

## Γιατί έχει σημασία

Ο χρονοπρογραμματισμός διαμορφώνει άμεσα τη latency και το throughput που νιώθουν οι χρήστες. Οι συνεντευξιαστές το εξετάζουν για να δουν αν κατανοείτε τις ανταλλαγές (trade-offs) — γιατί ένα διαδραστικό workload θέλει σύντομα quanta ή αύξηση προτεραιότητας, γιατί ο priority scheduling χρειάζεται **aging** για να αποτρέψει το starvation, και πώς οι MLFQ/CFS πετυχαίνουν καλή διαδραστική συμπεριφορά χωρίς να γνωρίζουν εκ των προτέρων τα μήκη των jobs. Είναι επίσης το νοητικό μοντέλο πίσω από τη ρύθμιση του `nice`, τις προτεραιότητες real-time, και τη διάγνωση μιας υπηρεσίας που λιμοκτονεί ή είναι αργή.

Συνηθισμένοι αλγόριθμοι

Πραγματικοί schedulers

Γιατί έχει σημασία

Σχετικές ερωτήσεις