Lập lịch CPU hoạt động ra sao, và có những thuật toán phổ biến nào?

Question

IT Interview Practice · Accepted Answer

**Lập lịch CPU (CPU scheduling)** là quyết định của kernel về việc *thread sẵn sàng nào* sẽ được CPU *tiếp theo*, và trong *bao lâu*. Vì thường có nhiều thread chạy được hơn số core, **scheduler** phân chia (multiplex) chúng, nhắm tới cân bằng các mục tiêu đối chọi nhau — **throughput**, **latency / thời gian phản hồi thấp**, và **công bằng** — đồng thời tránh **starvation** (bỏ đói).

## Các thuật toán phổ biến

```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** minh họa cái núm điều chỉnh cốt lõi — **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 thật

Mặc định lâu đời của Linux là **CFS (Completely Fair Scheduler)**: thay vì các lát thời gian cố định, nó theo dõi **virtual runtime (vruntime)** của mỗi task và luôn chạy thread đã nhận ít CPU nhất cho tới hiện tại, có trọng số theo giá trị **nice** của nó — xấp xỉ tinh thần "ai cũng được phần công bằng". Nó khóa một cây đỏ-đen (red-black tree) theo vruntime, nên việc chọn task tiếp theo là O(log n). (Các kernel mới hơn dùng EEVDF, một bản tinh chỉnh với cùng mục tiêu công bằng cộng thêm giới hạn latency chặt hơn.)

**Preemptive vs cooperative:** các OS hiện đại là **preemptive** (giành quyền) — một timer interrupt cho phép scheduler cưỡng bức lấy lại CPU, nên một thread không thể độc chiếm một core.

## Tại sao điều này quan trọng

Lập lịch định hình trực tiếp latency và throughput mà người dùng cảm nhận. Người phỏng vấn dò chủ đề này để xem bạn có hiểu các đánh đổi không — vì sao workload tương tác muốn quantum ngắn hoặc được boost priority, vì sao priority scheduling cần **aging** để tránh starvation, và làm sao MLFQ/CFS có hành vi tương tác tốt mà không cần biết trước độ dài job. Đây cũng là mô hình tư duy đằng sau việc chỉnh `nice`, priority real-time, và chẩn đoán một service bị bỏ đói hoặc giật lag.

Các thuật toán phổ biến

Scheduler thật

Tại sao điều này quan trọng

Câu hỏi liên quan