Scheduler CPU — timer interrupt, time slice & CFS

TL;DR: Scheduler là phần của kernel quyết định thread nào trong số các thread ready được chạy tiếp trên mỗi core. Linux (và mọi OS hiện đại) dùng lập lịch preemptive: một timer interrupt đều đặn (thường 100–1000 lần/giây) cướp CPU khỏi thread đang chạy, để kernel có cơ hội chọn lại — nhờ vậy một vòng lặp vô hạn không thể chiếm CPU mãi mãi. Mỗi thread được cấp một phần thời gian (time slice); hết slice thì bị preempt về ready. Độ dài slice là một đánh đổi: quá ngắn thì tốn context switch, quá dài thì phản hồi giật. Priority/nice (từ -20 tới +19 trên Linux) cho một số thread được ưu ái hơn. Scheduler mặc định của Linux là CFS: thay vì gán slice cứng, nó theo dõi mỗi thread đã chạy bao lâu (vruntime) và luôn chọn thread chạy ít nhất — công bằng, và tự nhiên ưu tiên thread hay ngủ (I/O-bound).

Máy bạn có 4 core. htop báo 412 tiến trình. Nếu mỗi core chạy đúng một thread cho tới khi nó xong, thì 408 tiến trình còn lại phải xếp hàng chờ — con trỏ chuột đơ, nhạc dừng, terminal không gõ được. Nhưng thực tế mọi thứ mượt: chuột mượt, nhạc chạy, build vẫn tiến. Ai đó đang chia nhỏ 4 core ra cho 412 tiến trình nhanh tới mức bạn không nhận ra sự chia sẻ. Người đó là scheduler.

Và có một câu hỏi cắc cớ: nếu một tiến trình chạy while (true) {} — vòng lặp không bao giờ gọi I/O, không bao giờ tự nhường CPU — thì làm sao các tiến trình khác được chạy? Nếu scheduler chỉ hoạt động khi thread tự nguyện nhường (cooperative), một vòng lặp tham lam sẽ đóng băng cả máy. Câu trả lời — timer interrupt — là trái tim của lập lịch hiện đại.

Bài này giải thích scheduler preemptive chia CPU thế nào: timer interrupt cướp CPU ra sao, time slice là gì và đánh đổi độ dài của nó, priority/nice, và ý tưởng cốt lõi của CFS. Không đi sâu vào code kernel — mục tiêu là bạn hình dung được cơ chế để đọc nice, htop, và hiểu bài 04 (chọn số thread).

1. Analogy — cô giáo gọi học sinh phát biểu

Một lớp 40 học sinh (thread ready) đều giơ tay, nhưng chỉ có một micro (một CPU core). Cô giáo (scheduler) phải quyết mỗi lúc trao micro cho ai.

Nếu cô để một học sinh nói cho tới khi nào bạn ấy tự dừng (cooperative), một bạn nói dài dòng sẽ chiếm hết tiết học — cả lớp mất lượt. Nên cô đặt đồng hồ: mỗi bạn nói tối đa 1 phút (time slice), hết giờ đồng hồ reo (timer interrupt), cô thu micro và trao cho bạn khác. Không ai độc chiếm được.

Cô cũng không hoàn toàn cào bằng: bạn nào ít được nói nhất từ đầu tiết thì cô ưu tiên gọi (để công bằng theo tổng thời gian nói, chứ không phải theo lượt). Và có bạn được cô thiên vị hơn một chút (priority/nice) — ví dụ bạn phụ trách trình bày chính.

Chi tiết tinh tế: bạn nào giơ tay hỏi một câu ngắn rồi ngồi xuống chờ (hay block chờ I/O) thì tổng thời gian nói của bạn ấy rất ít — nên theo quy tắc "ai nói ít nhất được gọi trước", những bạn này luôn được đáp ứng nhanh khi giơ tay. Đó chính là cách CFS tự nhiên ưu tiên thread I/O-bound mà không cần luật riêng.

2. Preemption — timer interrupt cướp CPU thế nào

Có hai kiểu chia CPU:

• Cooperative (hợp tác): thread chỉ mất CPU khi nó tự nguyện nhường — gọi I/O, hoặc gọi một hàm yield(). Nếu một thread không bao giờ nhường (while (true) {}), nó chiếm core vĩnh viễn. Các OS đời đầu (Windows 3.x, Mac OS cổ) dùng kiểu này và một app treo là đóng băng cả máy.
• Preemptive (ưu tiên/cướp): kernel có thể lấy lại CPU khỏi thread bất cứ lúc nào, kể cả khi thread không muốn nhường. Mọi OS hiện đại (Linux, Windows, macOS) dùng kiểu này.

Cơ chế biến preemptive thành hiện thực là timer interrupt. Phần cứng có một bộ đếm giờ được lập trình để phát interrupt đều đặn — trên Linux, tần số này (HZ) thường là 100, 250, hoặc 1000 lần/giây tuỳ cấu hình kernel. Mỗi lần timer interrupt xảy ra:

1. CPU đang chạy thread người dùng thì bị ngắt, nhảy vào kernel để xử lý interrupt (interrupt là chủ đề của module 01).
2. Kernel cập nhật số liệu thời gian đã chạy của thread hiện tại và hỏi scheduler: "thread này nên tiếp tục, hay đã đến lúc nhường?".
3. Nếu đến lúc nhường (hết time slice, hoặc có thread ready xứng đáng hơn), kernel thực hiện context switch (bài 02) sang thread khác.
4. Nếu chưa, thread hiện tại chạy tiếp — chỉ mất một chút thời gian cho lần ngắt.

Nhờ interrupt này, dù thread của bạn là while (true) {} không bao giờ tự nhường, timer vẫn đều đặn kéo kernel vào và cho thread khác cơ hội. Đó là vì sao một vòng lặp vô hạn trong một tiến trình không làm treo cả máy trên OS hiện đại — nó chỉ ngốn phần CPU của mình, còn con trỏ chuột và các tiến trình khác vẫn được chia lượt.

flowchart LR
  A["Thread dang chay<br/>(user mode)"] -->|timer interrupt| B["Kernel: cap nhat thoi gian<br/>hoi scheduler"]
  B -->|"con slice"| A
  B -->|"het slice / co thread xung dang hon"| C["Context switch<br/>sang thread khac"]

3. Time slice — dài bao nhiêu là vừa?

Time slice (còn gọi là quantum) là lượng thời gian một thread được chạy trước khi scheduler cân nhắc preempt nó. Chọn độ dài slice là một đánh đổi kinh điển, và OSTEP trình bày rất rõ:

• Slice ngắn (ví dụ 1 ms): mỗi thread chờ ít hơn tới lượt mình → phản hồi nhanh (gõ phím, di chuột thấy mượt). Nhưng đổi thread thường xuyên hơn → nhiều context switch hơn, mà mỗi switch tốn chi phí trực tiếp + làm nguội cache/TLB (bài 02). Nếu slice ngắn tới mức xấp xỉ chi phí một context switch, CPU dành phần lớn thời gian đổi việc thay vì làm việc.
• Slice dài (ví dụ 100 ms): ít context switch → ít lãng phí, thông lượng cao cho tác vụ tính toán. Nhưng một thread phải chờ lâu hơn tới lượt → phản hồi giật: bạn di chuột mà thấy khựng vì một thread khác đang giữ core cả 100 ms.

Time slice ngan  ---> phan hoi nhanh, NHUNG nhieu context switch (ton)
Time slice dai   ---> it overhead, thong luong cao, NHUNG phan hoi giat

Muc tieu: du dai de context switch khong dang ke so voi thoi gian lam viec,
          du ngan de nguoi dung khong cam thay giat.

Nguyên tắc thực dụng: slice nên dài hơn nhiều lần chi phí một context switch (để overhead không đáng kể) nhưng đủ ngắn để độ trễ phản hồi nằm dưới ngưỡng con người cảm nhận (~vài chục ms). Đây là lý do time slice điển hình rơi vào khoảng vài ms (dưới tải nặng CFS còn chia nhỏ hơn nữa — sched_latency mặc định ~6 ms chia đều cho các thread đang chạy; các scheduler quantum cố định kiểu cũ mới lên tới vài chục ms) — vùng cân bằng giữa hai thái cực (slice ngắn hơn một tick 10 ms của HZ=100 cần high-resolution timer — sched hrtick).

4. Priority và nice — không phải ai cũng bình đẳng

Không phải mọi thread đáng được chia CPU như nhau. Một tác vụ nền nén video có thể nhường bước cho một tiến trình giao diện đang cần phản hồi tức thì. Linux thể hiện điều này qua nice value.

Nice value chạy từ -20 (ưu tiên cao nhất) tới +19 (ưu tiên thấp nhất), mặc định 0. Tên "nice" nghĩa là "tử tế": nice cao (dương) là thread "tử tế", chịu nhường CPU cho thread khác; nice thấp (âm) là thread "đòi hỏi", được ưu ái. Theo sched(7), mỗi đơn vị chênh lệch nice đổi mức ưu ái khoảng 1,25 lần — tức thread nice 0 nhận CPU gấp ~1,25 lần thread nice +1 khi cả hai cùng tranh.

# Chay mot tac vu nen voi uu tien thap (nhuong CPU cho viec khac)
nice -n 10 ./batch_job.sh

# Dat nice TUYET DOI = 5 cho tien trinh CUA MINH (nhuong bot uu tien): khong can dac quyen
renice -n 5 -p 12345
# Nhung: giam nice (ke ca ve 0 tu so duong) hoac renice tien trinh user khac -> can quyen/root

Lưu ý renice -n 5 đặt nice tuyệt đối bằng 5 (theo util-linux, không phải cộng thêm 5 vào giá trị hiện tại) — nên nó chỉ thực sự "tăng" nice khi giá trị hiện tại đang dưới 5, ví dụ mặc định 0. Chỉ root mới hạ nice xuống âm (tăng ưu tiên vượt mặc định); người dùng thường chỉ tăng nice (nhường bớt). Ngoài SCHED_OTHER (chính sách mặc định dùng nice), Linux còn có chính sách thời gian thực (SCHED_FIFO, SCHED_RR) cho tác vụ cần đảm bảo cứng — nằm ngoài phạm vi bài này.

5. Ý tưởng CFS — công bằng bằng "vruntime"

Từ Linux 2.6.23, scheduler mặc định là CFS — Completely Fair Scheduler (thay cho scheduler "O(1)" cũ). Bạn không cần đọc code kernel; chỉ cần nắm ý tưởng cốt lõi, vì nó giải thích cả tính công bằng lẫn việc I/O-bound được ưu tiên tự nhiên.

5.1 vruntime và cây đỏ-đen

CFS bỏ khái niệm "time slice cứng gán trước". Thay vào đó, nó theo dõi cho mỗi thread một con số: vruntime (virtual runtime) — thời gian CPU thread đó đã thực sự chạy (có điều chỉnh theo nice). Quy tắc chọn cực kỳ đơn giản, đúng như tài liệu kernel viết: CFS luôn chọn chạy thread có vruntime nhỏ nhất — tức thread "đã chạy ít nhất cho tới giờ", thread thiệt thòi nhất.

Cơ chế: CFS giữ mọi thread ready trong một cây đỏ-đen (red-black tree — cây tìm kiếm nhị phân tự cân bằng, thao tác O(log n), phần tử nhỏ nhất luôn ở nhánh trái cùng) sắp theo vruntime. Thread có vruntime nhỏ nhất nằm ở nút trái nhất (leftmost) — CFS lấy nó ra chạy. Khi thread chạy, vruntime của nó tăng dần, nên nó "trôi" sang phải trong cây, nhường chỗ nút-trái-nhất cho thread khác. Kết quả là mọi thread luân phiên tiến về phía "chạy ít nhất", giữ tổng thời gian chạy xấp xỉ nhau — đó là "completely fair".

flowchart TB
  subgraph tree["Red-black tree cac thread ready (sap theo vruntime)"]
    L["Leftmost:<br/>vruntime NHO NHAT<br/>(chay it nhat)"] --- M["..."] --- R["vruntime lon<br/>(vua chay nhieu)"]
  end
  L -->|"CFS chon chay"| RUN["Thread chay,<br/>vruntime tang dan"]
  RUN -->|"troi sang phai,<br/>nhuong leftmost"| tree

5.2 nice và ưu tiên I/O-bound

Hai hệ quả quan trọng của quy tắc này:

• Nice điều chỉnh tốc độ tăng vruntime. Thread nice thấp (ưu tiên cao) tích vruntime chậm hơn so với thời gian thực nó chạy, nên nó lâu rơi khỏi vị trí "chạy ít nhất" → được chọn thường xuyên hơn. Đó là cách nice biến thành "1,25 lần mỗi đơn vị" một cách mượt mà.
• Thread hay ngủ (I/O-bound) được ưu tiên tự nhiên. Một thread thường xuyên block chờ I/O tích luỹ rất ít vruntime (vì nó ít chạy). Khi I/O xong và nó quay lại ready, vruntime nhỏ của nó đưa nó lên gần nút-trái-nhất → được chọn nhanh. Vì vậy các tác vụ tương tác (gõ phím, chuột) — vốn I/O-bound — luôn phản hồi nhanh mà không cần luật đặc biệt. Đây là điểm nối thẳng sang bài 04.

6. Pitfall của riêng concept này

❌ Nhầm 1 — tưởng while (true) {} treo cả máy:

✅ Trên OS preemptive, timer interrupt đều đặn kéo kernel vào và chia lượt cho thread khác, nên một vòng lặp vô hạn chỉ ngốn phần CPU của nó (tối đa một core nếu đơn luồng), không đóng băng máy. Bạn vẫn di được chuột, mở được terminal, và kill được nó. (Trên OS cooperative đời cũ thì đúng là treo — nhưng đó là quá khứ.)

❌ Nhầm 2 — tưởng nice đặt mức CPU tuyệt đối:

✅ Nice chỉ đổi tỉ lệ chia khi tranh chấp. Thread nice +19 vẫn dùng 100% CPU nếu không ai khác cần. Muốn giới hạn cứng (ví dụ "container này tối đa 2 core"), dùng cgroups CPU quota, không phải nice.

❌ Nhầm 3 — tưởng scheduler "cào bằng round-robin từng lượt":

✅ CFS không xoay vòng theo số lượt, mà cân bằng theo tổng thời gian đã chạy (vruntime). Một thread ngủ nhiều rồi thức dậy được ưu tiên hơn thread vừa chạy liên tục — dù xét theo "số lượt" thì có vẻ không công bằng. Chính điều này làm tác vụ tương tác mượt.

7. 📚 Deep Dive Linux

8. Liên hệ các bài khác

• Bài 02 — Trạng thái và context switch: preempt (running→ready) chính là scheduler cướp CPU; chi phí context switch là lý do time slice không nên quá ngắn.
• Bài 04 — CPU-bound vs I/O-bound: CFS ưu tiên thread hay ngủ (vruntime nhỏ) — nền để hiểu vì sao thêm thread giúp I/O-bound.
• Interrupt và trap (Module 01): timer interrupt là cơ chế phần cứng đưa kernel vào cuộc để preempt — chi tiết ở module 01.
• Tiến trình và PCB (Module 02): scheduler thao tác trên các cấu trúc kernel mô tả thread/tiến trình.

9. Tóm tắt

• Scheduler chọn thread ready nào chạy tiếp trên mỗi core.
• Lập lịch preemptive dùng timer interrupt (thường 100–1000 lần/giây) để cướp CPU đều đặn — nên while (true) {} không treo được cả máy.
• Time slice là phần thời gian trước khi preempt; đánh đổi: ngắn = phản hồi nhanh nhưng tốn context switch, dài = thông lượng cao nhưng giật.
• Nice (-20 tới +19) đổi mức ưu ái ~1,25 lần mỗi đơn vị; chỉ có tác dụng khi các thread tranh nhau core, không đặt mức tuyệt đối.
• CFS theo dõi vruntime (thời gian đã chạy, điều chỉnh theo nice) và luôn chọn thread vruntime nhỏ nhất qua cây đỏ-đen (nút trái nhất) — công bằng theo tổng thời gian chạy.
• Nice điều chỉnh tốc độ tăng vruntime; thread I/O-bound (hay ngủ) tích ít vruntime nên được ưu tiên tự nhiên khi thức dậy.
• CFS đang được thay dần bằng EEVDF trong kernel mới, nhưng ý tưởng công bằng theo thời gian ảo vẫn là mô hình để nắm.

10. Tự kiểm tra

Bài tiếp theo: CPU-bound vs I/O-bound — chọn số thread thế nào