CPU
Scheduling

4.1 Bài toán scheduling

Máy bạn có 4 CPU core nhưng đang chạy hàng trăm process (Chrome, VS Code, system services...). Tại mọi thời điểm, mỗi core chỉ chạy 1 thread. Vậy ai chạy, ai chờ?

Scheduler là phần của kernel quyết định: tại mỗi thời điểm, thread/process nào sẽ được CPU. Nó chạy hàng nghìn lần mỗi giây, mỗi lần đưa ra quyết định trong micro giây.

Phân loại theo loại workload

• CPU-bound (compute): dành phần lớn thời gian tính toán, ít I/O. Vd: render video, train ML.
• I/O-bound: dành nhiều thời gian đợi I/O (disk, network, user input). Vd: database, web server, text editor.

Scheduler hiện đại phải cân bằng: ưu tiên I/O-bound (để app responsive) nhưng không bỏ đói CPU-bound.

4.2 Tiêu chí đánh giá scheduler

Các metric này thường mâu thuẫn nhau: tối ưu throughput có thể hi sinh response time. Chọn scheduler là chọn trade-off.

4.3 Preemptive vs Non-preemptive

Cơ chế preemption: hardware timer phát interrupt mỗi vài ms. Kernel handle interrupt → chạy scheduler → có thể đổi process.

4.4 FCFS — First-Come, First-Served

Đơn giản nhất: process đến trước được phục vụ trước. Dùng FIFO queue.

Ví dụ minh hoạ

Process  Burst time
  P1        24
  P2         3
  P3         3

Order: P1 → P2 → P3
Gantt: |---------- P1 ----------|P2|P3|
       0                       24  27 30

Waiting time:
  P1: 0
  P2: 24
  P3: 27
Avg waiting: (0+24+27)/3 = 17

Vấn đề: Convoy Effect

Nếu P1 chạy lâu (24), P2 và P3 phải đợi rất lâu — dù chúng nhanh. Toàn bộ "đoàn xe" mắc kẹt sau 1 xe chậm. Nếu thay đổi thứ tự: P2 → P3 → P1 → avg waiting = (0+3+6)/3 = 3 (giảm 5.7×).

• Ưu: đơn giản, fair theo thứ tự đến
• Nhược: convoy effect, response time tệ
• Preemptive? Không

4.5 SJF — Shortest Job First (và SRTF)

Chọn process có burst time ngắn nhất chạy trước.

Process  Burst time
  P1        24
  P2         3
  P3         3

Order: P2 → P3 → P1
Gantt: |P2|P3|--------- P1 ---------|
       0  3  6                      30

Waiting time:
  P2: 0, P3: 3, P1: 6
Avg waiting: (0+3+6)/3 = 3

SJF tối ưu lý thuyết — cho average waiting time thấp nhất. Nhưng có 2 vấn đề thực tế:

1. Không biết burst time tương lai! Phải dự đoán dựa trên lịch sử (exponential averaging).
2. Starvation: nếu liên tục có process ngắn đến, process dài có thể không bao giờ chạy.

SRTF — Shortest Remaining Time First (preemptive SJF)

Preemptive version: process mới đến có remaining time ngắn hơn process hiện tại → preempt ngay.

4.6 Priority Scheduling + Aging

Mỗi process gắn 1 số priority. Scheduler chọn process có priority cao nhất.

Process  Burst  Priority (smaller = higher)
  P1       10      3
  P2        1      1   ← highest
  P3        2      4
  P4        1      5
  P5        5      2

Order: P2 → P5 → P1 → P3 → P4
Gantt: |P2|----- P5 -----|------ P1 ------|--P3--|P4|

Starvation và Aging

Process priority thấp có thể không bao giờ chạy nếu liên tục có process priority cao. Starvation.

Aging: tăng priority dần theo thời gian process đợi. Sau đủ lâu, dù priority ban đầu thấp, nó sẽ leo lên cao và được chạy.

Linux nice value

# Tạo process với priority thấp (nice +10, "tử tế hơn")
nice -n 10 ./long_running_task

# Đổi priority của process đang chạy
renice -n 5 -p 1234

# Xem nice value
ps -eo pid,ni,comm | head

Linux nice: -20 (cao nhất) đến +19 (thấp nhất). User thường: 0 đến +19. Cần root để đặt nice âm.

4.7 Round Robin (RR) — fair time slicing

Mỗi process được CPU 1 khoảng time quantum (vd 10ms). Hết quantum, OS preempt và chuyển sang process tiếp theo trong queue (FIFO). Process bị preempt được đẩy về cuối queue.

Process  Burst time      Quantum = 4ms
  P1        24
  P2         3
  P3         3

Gantt:
|P1|P2|P3|P1|P1|P1|P1|P1|
0  4  7 10 14 18 22 26 30

Waiting time:
  P1: (10-4) = 6  (chỉ tính lần đầu đợi)
  P2: 4
  P3: 7
Avg: (6+4+7)/3 = 5.67

Time quantum — chọn thế nào?

• Quá nhỏ (vd 1ms): nhiều context switch → overhead cao, throughput thấp
• Quá lớn (vd 1s): RR thoái hoá thành FCFS, response time tệ
• Vừa phải (10-100ms): cân bằng — Linux mặc định ~6ms với CFS

• Ưu: fair, response time tốt
• Nhược: không tối ưu turnaround/waiting; mọi process được đối xử như nhau (không xét priority hay loại workload)

4.8 MLFQ — Multi-Level Feedback Queue

Thuật toán "tự học" — kết hợp nhiều RR queue với priority khác nhau, và tự điều chỉnh priority dựa trên hành vi process.

Quy tắc MLFQ

1. Process mới → vào queue cao nhất (Q0)
2. Scheduler chọn process từ queue cao nhất không rỗng
3. Process dùng hết quantum mà chưa xong → đẩy xuống queue thấp hơn (CPU-bound)
4. Process tự nguyện block I/O trước khi hết quantum → giữ priority (I/O-bound)
5. Định kỳ "boost" mọi process lên Q0 (tránh starvation)

Hiệu ứng: I/O-bound process (text editor, terminal) ở Q cao → response nhanh. CPU-bound process (build, render) "rơi" xuống Q thấp → vẫn chạy nhưng không chiếm hết CPU.

MLFQ là tổ tiên của các scheduler hiện đại. Windows NT, BSD đều dùng biến thể MLFQ.

4.9 Linux CFS — Completely Fair Scheduler

Linux từ 2.6.23 (2007) dùng CFS. Ý tưởng: mô phỏng "ideal multitasking" — nếu có N process, mỗi process đáng lẽ phải nhận 1/N CPU time. CFS theo dõi vruntime (virtual runtime) của mỗi process, chọn process có vruntime nhỏ nhất để chạy.

Cấu trúc dữ liệu

CFS dùng Red-Black Tree sắp xếp process theo vruntime. Lấy min = O(log n).

Cách vruntime tăng

Process chạy 10ms thực tế → vruntime tăng 10ms × hệ số (phụ thuộc nice value). Nice cao (priority thấp) → vruntime tăng nhanh hơn → ít được chạy.

Các tunable

# Xem các CFS parameter
cat /proc/sys/kernel/sched_min_granularity_ns       # min slice ~1.5ms
cat /proc/sys/kernel/sched_latency_ns               # target latency ~6ms
cat /proc/sys/kernel/sched_wakeup_granularity_ns

# Xem scheduling stats của 1 process
cat /proc/$$/sched | head

Real-time scheduler (SCHED_FIFO, SCHED_RR)

Cho process cần độ trễ thấp (audio, robot control), Linux có scheduling class riêng: SCHED_FIFO (FCFS, không preempt cho đến khi block) và SCHED_RR (RR với time quantum). Cần root: chrt -f 99 ./realtime_app.

Bài tập

Tổng kết chương 4

• ✅ Scheduler = bộ não chọn process nào dùng CPU; chạy hàng nghìn lần/giây
• ✅ 6 metric đánh giá: utilization, throughput, turnaround, waiting, response, fairness — thường mâu thuẫn
• ✅ Preemptive (cần timer interrupt) là chuẩn của OS hiện đại
• ✅ FCFS: convoy effect; SJF: optimal lý thuyết, có starvation
• ✅ Priority + Aging: tránh starvation
• ✅ Round Robin: fair với time quantum, response tốt
• ✅ MLFQ: tự học CPU-bound vs I/O-bound
• ✅ Linux CFS: vruntime + Red-Black tree, không có "queue", priority qua nice