Bagaimana penjadualan CPU berfungsi, dan apakah algoritma yang lazim?

Question

IT Interview Practice · Accepted Answer

**Penjadualan CPU (CPU scheduling)** ialah keputusan kernel tentang *thread sedia mana* mendapat CPU *seterusnya*, dan untuk *berapa lama*. Oleh sebab biasanya terdapat lebih banyak thread yang boleh berjalan daripada core, **scheduler** memultipleks mereka, bertujuan mengimbangi matlamat yang bersaing — **throughput**, **latency / masa tindak balas rendah**, dan **keadilan** — sambil mengelakkan **starvation** (kebuluran).

## Algoritma lazim

```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 utama — **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 sebenar

Lalai lama Linux ialah **CFS (Completely Fair Scheduler)**: berbanding hirisan tetap, ia menjejaki **virtual runtime (vruntime)** setiap task dan sentiasa menjalankan thread yang telah menerima CPU paling sedikit setakat ini, dipemberat mengikut nilai **nice**-nya — menghampiri "setiap orang mendapat bahagian yang adil". Ia mengunci pokok merah-hitam (red-black tree) mengikut vruntime, jadi memilih task seterusnya ialah O(log n). (Kernel yang lebih baharu menggunakan EEVDF, penambahbaikan dengan matlamat keadilan yang sama serta batasan latency yang lebih ketat.)

**Preemptive lawan cooperative:** OS moden bersifat **preemptive** — satu timer interrupt membenarkan scheduler merampas semula CPU secara paksa, jadi satu thread tidak boleh memonopoli sebuah core.

## Mengapa ia penting

Penjadualan membentuk secara langsung latency dan throughput yang dirasai pengguna. Penemu duga menyiasatnya untuk melihat sama ada anda memahami trade-off — mengapa beban kerja interaktif mahukan quantum pendek atau rangsangan priority, mengapa penjadualan priority memerlukan **aging** untuk mengelakkan starvation, dan bagaimana MLFQ/CFS memperoleh tingkah laku interaktif yang baik tanpa mengetahui panjang job terlebih dahulu. Ia juga model mental di sebalik penalaan `nice`, priority real-time, dan mendiagnosis service yang terbiar atau tersekat-sekat.

Algoritma lazim

Scheduler sebenar

Mengapa ia penting

Soalan berkaitan