Lời mở đầu

Đây là bài viết tiếp theo nói về vấn đề lập lịch CPU trong hệ điều hành, đây là nhiệm vụ của bộ lập lịch ngắn hạn (Short-term Scheduler) đã được trình bày sơ lược trong phần trước.

Chủ yếu tìm hiểu về các lý thuyết về vấn đề này như các khái niệm, các tiêu chí và các thuật toán lập lịch CPU. Khuyến khích người đọc tự tìm hiểu cách các thuật toán chạy thông qua Youtube, bài viết tutorial,...

Ngoài ra còn có bộ điều phối tài nguyên Dispatcher sẽ thực hiện việc cấp CPU cho các tiến trình đã được CPU Scheduler chọn.

Dispatcher sẽ cần phải thực hiện context swtich Process, chuyển Process sang User-Mode và định vị vị trí của câu lệnh tiếp theo để Process thực hiện. Tất cả để đảm bảo Process này khi được cấp hoặc bị thu hồi CPU sẽ có thể tiếp tục các công việc dang dở của mình mà không bị lỗi. Việc này sẽ tốn một khoảng thời gian gọi là Dispatch latency.

Các khái niệm cơ bản

Mục đích của việc lập lịch CPU là để tận dụng tối đa CPU trong các hệ thống đa chương bằng cách chọn một trong các Process trong hàng đợi Ready và cấp CPU cho nó.

Ta có các thuật ngữ cơ bản trong lập lịch:

• CPU Burst Cyce, I/O Burst Cycle nói đến quá trình một Process thực hiện các lệnh CPU hoặc thực hiện lệnh I/O tương ứng. Một Process sẽ thực hiện các CPU Burst và I/O Burst một cách luân phiên trong suốt quá trình thực thi của nó. Một Process sẽ bắt đầu bằng một CPU Burst và kết thúc cũng bằng một CPU Burst đi kèm với một yêu cầu hệ thống để chấm dứt việc thực thi tiến trình.
• Preemptive là đặc tính của một Process mà nếu nó có đặc tính này thì nó sẽ được thực hiện với các tài nguyên được cấp cho đến khi xong mà không thể bị OS thu hồi giữa chừng.
• Non-Preemptive thì ngược lại, Process có đặc tính này có thể bị thu hồi tài nguyên cho các tiến trình khác bởi OS mà chưa thực hiện xong.

CPU Scheduler sẽ được gọi khi một Process:

• Thay đổi từ Running sang Waiting,
• Thay đổi từ Running sang Ready,
• Thay đổi từ Waiting sang Ready,
• Bị Terminated.

Các Tiêu Chí Đánh Giá (Scheduling Criteria)

Trước khi tìm hiểu thuật toán, chúng ta cần nắm các tiêu chí dùng để đánh giá độ hiệu quả:

• Thời gian lưu lại hệ thống (Turnaround time): Là tổng thời gian từ lúc tiến trình xuất hiện đến khi hoàn thành (Thời điểm hoàn thành - Thời điểm có mặt).
• Thời gian chờ (Waiting time): Tổng thời gian tiến trình phải chờ đợi trong hàng đợi ready (Thời điểm nhận CPU - Thời điểm có mặt).
• Thời gian phản hồi (Response time): Thời gian từ lúc yêu cầu được gửi đi đến khi có phản hồi đầu tiên.

Các thuật toán lập lịch

1. Thuật toán Đến trước - Phục vụ trước (First-Come, First-Served - FCFS)

Cách hoạt động: Tiến trình nào yêu cầu CPU trước sẽ được cấp phát CPU trước. Thuật toán này là độc quyền (non-preemptive), nghĩa là hệ điều hành không thể thu hồi CPU giữa chừng cho đến khi tiến trình tự giải phóng.

Ưu điểm: Dễ hiểu và dễ cài đặt.

Nhược điểm: Hiệu suất kém do thời gian chờ trung bình thường cao. Nó có thể gây ra "Hiệu ứng đoàn tàu" (Convoy effect), tức là các tiến trình ngắn phải chờ rất lâu phía sau một tiến trình dài.

Ví dụ: Giả sử có 3 tiến trình đến cùng lúc theo thứ tự $P_1$, $P_2$, $P_3$ với thời gian chạy (Burst time) lần lượt là 24, 3, 3.

• Nếu chạy theo thứ tự $P_1, P_2, P_3$: Thời gian chờ của $P_1 = 0$, $P_2 = 24$, $P_3 = 27$. Thời gian chờ trung bình là $(0 + 24 + 27) / 3 = 17$.
• Ngược lại, nếu chạy theo thứ tự $P_2, P_3, P_1$: Thời gian chờ trung bình giảm xuống chỉ còn $(6 + 0 + 3) / 3 = 3$.

2. Thuật toán Công việc ngắn nhất (Shortest-Job-First - SJF)

Cách hoạt động: Gắn mỗi tiến trình với thời gian chạy tiếp theo của nó, thuật toán sẽ chọn tiến trình có thời gian chạy ngắn nhất để thực thi trước.

Đặc điểm: SJF là thuật toán tối ưu vì nó mang lại thời gian chờ trung bình nhỏ nhất cho một tập hợp các tiến trình.

Phân loại: * Không độc quyền (Non-preemptive): Khi CPU đã cấp cho tiến trình, nó không bị thu hồi cho đến khi chạy xong. * Độc quyền (Preemptive - hay còn gọi là SRTF): Nếu một tiến trình mới xuất hiện có thời gian chạy ngắn hơn thời gian chạy còn lại của tiến trình đang thực thi, CPU sẽ bị thu hồi và chuyển sang tiến trình mới.

Ví dụ (Preemptive SJF): Các tiến trình đến với Thời gian đến / Thời gian chạy tương ứng:

$P_1$ (0.0 / 7), $P_2$ (2.0 / 4), $P_3$ (4.0 / 1), $P_4$ (5.0 / 4).

• Non_Preemptive SJF:

• Preemptive SJF:

3. Thuật toán theo độ ưu tiên (Priority Scheduling)

Cách hoạt động: Mỗi tiến trình được gắn một số nguyên thể hiện độ ưu tiên (thông thường số càng nhỏ thì độ ưu tiên càng cao). Tiến trình có độ ưu tiên cao nhất sẽ được cấp CPU. Bản thân SJF cũng là một dạng lập lịch ưu tiên, trong đó độ ưu tiên chính là thời gian chạy ngắn nhất.

Vấn đề: Gây ra tình trạng "Đói tài nguyên" (Starvation) - các tiến trình có độ ưu tiên thấp có thể không bao giờ được thực thi.

Giải pháp: Sử dụng cơ chế "Lão hóa" (Aging), nghĩa là theo thời gian, hệ thống sẽ tự động tăng dần độ ưu tiên của các tiến trình đang chờ để đảm bảo cuối cùng chúng cũng được chạy.

Ví dụ: 5 tiến trình đến cùng lúc. (Độ ưu tiên: Số càng nhỏ càng ưu tiên).

• P1: Chạy 10, Độ ưu tiên 3
• P2: Chạy 1, Độ ưu tiên 1 (Cao nhất)
• P3: Chạy 2, Độ ưu tiên 4
• P4: Chạy 1, Độ ưu tiên 5 (Thấp nhất)
• P5: Chạy 5, Độ ưu tiên 2

4. Thuật toán Quay vòng (Round Robin - RR)

Cách hoạt động: Mỗi tiến trình được cấp một lượng thời gian CPU nhỏ gọi là "time quantum" (thường từ 10-100 ms). Sau khi hết khoảng thời gian này, tiến trình bị thu hồi CPU và đẩy xuống cuối hàng đợi ready. Thuật toán này giúp không tiến trình nào bị đói tài nguyên.

Hiệu năng: * Nếu time quantum quá lớn, RR sẽ trở thành thuật toán FCFS.

Nếu time quantum quá nhỏ, số lần chuyển đổi ngữ cảnh (context switch) sẽ tăng cao gây lãng phí thời gian hệ thống.

Ví dụ: 4 tiến trình đến cùng lúc tại thời điểm 0 với Thời gian chạy: $P_1$ (53), $P_2$ (17), $P_3$ (68), $P_4$ (24). Time Quantum = 20.

• Lượt 1: $P_1$ chạy 20 (còn 33), $P_2$ chạy 17 (xong), $P_3$ chạy 20 (còn 48), $P_4$ chạy 20 (còn 4).
• Vòng quay cứ lặp lại như vậy cho đến khi các tiến trình hoàn thành. Mặc dù thời gian lưu lại hệ thống thường cao hơn SJF, nhưng RR có thời gian phản hồi tốt hơn.

5. Hàng đợi đa mức (Multilevel Queue) & Hồi tiếp (Multilevel Feedback Queue)

Multilevel Queue: Hàng đợi ready được chia thành các hàng đợi riêng biệt (ví dụ: foreground cho tương tác và background cho xử lý ngầm). Mỗi hàng đợi có thuật toán lập lịch riêng (như RR cho foreground và FCFS cho background). Mỗi tiến trình chỉ thuộc cố định một hàng đợi.

• Multilevel Feedback Queue: Linh hoạt hơn bằng cách cho phép các tiến trình di chuyển giữa các hàng đợi. Ví dụ: Một tiến trình mới vào sẽ vào hàng đợi $Q_0$ dùng thuật toán RR (quantum 8). Nếu chạy hết 8ms mà chưa xong, nó bị rớt xuống hàng đợi $Q_1$ (quantum 16). Nếu vẫn chưa xong, nó rớt xuống hàng đợi cuối cùng dùng thuật toán FCFS. Cơ chế này dựa trên mong muốn ưu tiên các tiến trình ngắn và tự động điều chỉnh qua thời gian.

Ví dụ: Để dễ hình dung thuật toán này, ta theo dõi chỉ 1 tiến trình P1 có thời gian chạy là 30ms.

Hệ thống có 3 hàng đợi: Q0 (RR q=8), Q1 (RR q=16), Q2 (FCFS).

Kết quả: P1 bị đẩy dần xuống các hàng đợi ưu tiên thấp hơn khi nó tiêu thụ hết time quantum.

Tài liệu tham khảo

• Abraham Silberschartz, Peter Baer Galvin, Greg Gagne, Operating System Concepts, 9th Edition.
• Geekforgeeks, CPU Scheduling in Operating Systems. [Trực tuyến]. Có sẵn tại Geekforgeeks (Truy cập 2026).