Bagaimana CPU scheduling bekerja, dan apa saja algoritma yang umum?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** adalah keputusan kernel tentang *thread siap* mana yang mendapat CPU *berikutnya*, dan *selama berapa lama*. Karena biasanya ada lebih banyak thread yang dapat dijalankan daripada core, **scheduler** melakukan multiplexing terhadap mereka, dengan tujuan menyeimbangkan sasaran yang saling bersaing — **throughput**, **latency / response time rendah**, dan **keadilan (fairness)** — sambil menghindari **starvation**.

## Algoritma yang umum

```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** menggambarkan tombol pengatur inti — **quantum**:

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

## Scheduler nyata

Default lama Linux adalah **CFS (Completely Fair Scheduler)**: alih-alih slice tetap, ia melacak **virtual runtime (vruntime)** setiap task dan selalu menjalankan thread yang sejauh ini menerima CPU paling sedikit, dengan bobot menurut nilai **nice**-nya — mendekati "semua orang mendapat bagian yang adil." Ia mengindeks sebuah red-black tree berdasarkan vruntime, sehingga memilih task berikutnya adalah O(log n). (Kernel yang lebih baru memakai EEVDF, penyempurnaan dengan tujuan keadilan yang sama plus batas latency yang lebih ketat.)

**Preemptive vs cooperative:** OS modern bersifat **preemptive** — sebuah timer interrupt memungkinkan scheduler secara paksa merebut kembali CPU, sehingga satu thread tidak bisa memonopoli sebuah core.

## Mengapa ini penting

Scheduling secara langsung membentuk latency dan throughput yang dirasakan pengguna. Pewawancara menyelidikinya untuk melihat apakah Anda memahami trade-off — mengapa beban kerja interaktif menginginkan quantum pendek atau boost prioritas, mengapa priority scheduling membutuhkan **aging** untuk mencegah starvation, dan bagaimana MLFQ/CFS mendapat perilaku interaktif yang baik tanpa mengetahui panjang job di muka. Ini juga model mental di balik penyetelan `nice`, prioritas real-time, dan mendiagnosis sebuah service yang kelaparan atau lag.

Algoritma yang umum

Scheduler nyata

Mengapa ini penting

Pertanyaan terkait