Các thuật toán process scheduling phổ biến là gì? (FCFS, Round Robin, SJF)

Các thuật toán scheduling khác nhau về cách ưu tiên process: FCFS đơn giản nhưng tệ với latency, Round Robin fair nhất, SJF tối ưu throughput nhưng gây starvation.

• FCFS (First-Come First-Served): process đến trước chạy trước — đơn giản nhưng convoy effect: một process dài block tất cả process ngắn phía sau, average waiting time cao.
• Round Robin (RR): mỗi process chạy một time quantum (10-100ms) rồi preempt — fair, responsive, phù hợp time-sharing systems; quantum quá nhỏ tốn context switch, quá lớn thành FCFS.
• SJF (Shortest Job First): chạy process có burst time ngắn nhất trước — tối ưu average waiting time nhưng starvation cho process dài, và không biết trước burst time trong thực tế.
• Priority Scheduling: mỗi process có độ ưu tiên, process ưu tiên cao chạy trước — có thể bị starvation (giải quyết bằng aging: tăng priority theo thời gian chờ).
• Multilevel Feedback Queue (Linux CFS): kết hợp nhiều queue, tự động điều chỉnh — đây là algorithm Linux kernel dùng, fair nhưng ưu tiên interactive process hơn batch.

Scheduling algorithms differ in how they prioritize processes: FCFS is simple but bad for latency, Round Robin is the fairest, SJF optimizes throughput but causes starvation.

• FCFS (First-Come First-Served): processes run in arrival order — simple but suffers from the convoy effect: one long process blocks all shorter processes behind it, resulting in high average waiting time.
• Round Robin (RR): each process runs for a time quantum (10–100ms) before being preempted — fair, responsive, suitable for time-sharing systems; too small a quantum wastes time on context switches, too large degrades into FCFS.
• SJF (Shortest Job First): runs the process with the shortest burst time first — minimizes average waiting time but causes starvation for long processes, and burst time is generally unknown in advance.
• Priority Scheduling: each process has a priority and higher-priority processes run first — can lead to starvation (mitigated by aging: gradually increasing the priority of waiting processes).
• Multilevel Feedback Queue (Linux CFS): combines multiple queues with different priorities and adjusts dynamically — the algorithm used by the Linux kernel, fair while favoring interactive processes over batch workloads.