CPU scheduling ทำงานอย่างไร และมีอัลกอริทึมที่พบบ่อยอะไรบ้าง?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** คือการตัดสินใจของ kernel ว่า *เธรดที่พร้อมทำงานตัวไหน* จะได้ CPU *เป็นตัวถัดไป* และ *นานแค่ไหน* เนื่องจากปกติมีเธรดที่รันได้มากกว่าจำนวน core **scheduler** จึงสลับ (multiplex) พวกมัน โดยมุ่งสร้างสมดุลระหว่างเป้าหมายที่ขัดแย้งกัน — **throughput**, **latency / เวลาตอบสนองต่ำ**, และ **ความยุติธรรม** — พร้อมกับหลีกเลี่ยง **starvation** (การอดอยาก)

## อัลกอริทึมที่พบบ่อย

```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** แสดงให้เห็นปุ่มปรับหลักตัวหนึ่ง — **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 ตัวจริง

ค่าดีฟอลต์ที่อยู่คู่ Linux มายาวนานคือ **CFS (Completely Fair Scheduler)**: แทนที่จะใช้ช่วงเวลาคงที่ มันติดตาม **virtual runtime (vruntime)** ของแต่ละ task และรันเธรดที่ได้รับ CPU น้อยที่สุดจนถึงตอนนี้เสมอ โดยถ่วงน้ำหนักตามค่า **nice** ของมัน — เป็นการประมาณแนวคิด "ทุกคนได้ส่วนแบ่งที่ยุติธรรม" มันใช้ red-black tree ที่คีย์ด้วย vruntime ดังนั้นการเลือก task ถัดไปจึงเป็น O(log n) (kernel รุ่นใหม่กว่าใช้ EEVDF ซึ่งเป็นการปรับปรุงที่มีเป้าหมายความยุติธรรมเดิมบวกกับขอบเขต latency ที่แน่นขึ้น)

**Preemptive vs cooperative:** OS สมัยใหม่เป็นแบบ **preemptive** (แย่งได้) — timer interrupt ยอมให้ scheduler บังคับยึด CPU กลับมา ดังนั้นเธรดหนึ่งจึงไม่สามารถผูกขาด core ได้

## ทำไมจึงสำคัญ

Scheduling กำหนดรูปร่างของ latency และ throughput ที่ผู้ใช้รู้สึกได้โดยตรง ผู้สัมภาษณ์เจาะหัวข้อนี้เพื่อดูว่าคุณเข้าใจการแลกเปลี่ยนหรือไม่ — ทำไมงานแบบ interactive จึงต้องการ quantum สั้นหรือการ boost priority, ทำไม priority scheduling จึงต้องมี **aging** เพื่อกัน starvation, และทำไม MLFQ/CFS จึงได้พฤติกรรม interactive ที่ดีโดยไม่ต้องรู้ความยาวของงานล่วงหน้า มันยังเป็นโมเดลความคิดเบื้องหลังการปรับ `nice`, priority แบบ real-time, และการวินิจฉัยเซอร์วิสที่ถูกอดอยากหรือหน่วงกระตุก

อัลกอริทึมที่พบบ่อย

scheduler ตัวจริง

ทำไมจึงสำคัญ

คำถามที่เกี่ยวข้อง