Lập lịch tiến trình — Khái niệm hệ điều hành

Lập lịch tiến trình là quyết định của hệ điều hành về việc tiến trình sẵn sàng nào sẽ được cấp CPU tiếp theo. Nói đơn giản, đó là quy tắc chọn tiến trình nào chạy ngay bây giờ và tiến trình nào phải chờ. Quy tắc đó làm thay đổi thời gian chờ, thời gian đáp ứng, tính công bằng và thông lượng tổng thể.

Lập lịch tiến trình quan trọng vì cùng một tập tiến trình có thể hoàn thành theo thứ tự rất khác nhau dưới FCFS, SJF hoặc round robin. Nếu bạn hiểu được ý tưởng này, phần lớn các ví dụ trong giáo trình sẽ dễ đọc hơn nhiều.

Lập Lịch Tiến Trình Trong Hệ Điều Hành Là Gì

Trong mô hình hệ điều hành thông thường, tiến trình di chuyển giữa các trạng thái như sẵn sàng, đang chạy và chờ. Bộ lập lịch sẽ chọn trong số các tiến trình đang ở trạng thái sẵn sàng.

Vì vậy, lập lịch tiến trình thường còn được gọi là lập lịch CPU. Nó không tạo ra công việc mới. Nó quyết định thứ tự mà các công việc đang chờ được cấp CPU.

Trong các hệ thống hiện đại, kernel thường lập lịch trực tiếp cho thread, nhưng thuật ngữ cổ điển "lập lịch tiến trình" vẫn là cách gọi chuẩn trong giảng dạy.

Bộ Lập Lịch Muốn Tối Ưu Điều Gì

Một bộ lập lịch thường cố gắng cân bằng nhiều mục tiêu:

• thời gian chờ thấp
• phản hồi nhanh cho các tác vụ tương tác
• thông lượng tốt
• tính công bằng
• hành vi có thể dự đoán được

Các mục tiêu này có thể xung đột với nhau. Một chính sách làm giảm thời gian chờ trung bình trong một ví dụ đơn giản hóa vẫn có thể tạo cảm giác thiếu công bằng trong thực tế, và một chính sách chia sẻ thời gian công bằng có thể làm chậm việc hoàn thành của một công việc ngắn.

Lập Lịch Có Ngắt Và Không Ngắt

Bộ lập lịch không ngắt cho phép một tiến trình đang chạy giữ CPU cho đến khi nó hoàn thành CPU burst hoặc bị chặn. First-come, first-served là ví dụ tiêu biểu.

Bộ lập lịch có ngắt có thể tạm dừng một tiến trình đang chạy và cấp CPU cho tiến trình khác. Round robin và nhiều bộ lập lịch ưu tiên hoạt động theo cách này.

Sự khác biệt này quan trọng vì thời gian đáp ứng thường được cải thiện khi hệ thống được phép ngắt các công việc chạy dài.

Các Thuật Toán Lập Lịch Tiến Trình Phổ Biến

First-Come, First-Served

First-come, first-served, hay FCFS, chạy các tiến trình theo thứ tự đến. Nó dễ hiểu và đơn giản để cài đặt, nhưng một công việc dài ở đầu hàng có thể khiến mọi công việc ngắn phía sau phải chờ.

Shortest Job First

Shortest job first, hay SJF, ưu tiên tiến trình có CPU burst nhỏ nhất. Trong bối cảnh đơn giản hóa khi độ dài burst được biết chính xác, nó có thể làm giảm thời gian chờ trung bình. Trong các hệ thống thực, độ dài burst đó thường phải được ước lượng.

Round Robin

Round robin cấp cho mỗi tiến trình sẵn sàng một lát thời gian nhỏ gọi là quantum. Nếu tiến trình chưa hoàn thành trong lát thời gian đó, nó sẽ quay lại hàng đợi sẵn sàng. Cách này thường cải thiện tính công bằng và khả năng đáp ứng cho các tải công việc tương tác.

Priority Scheduling

Lập lịch ưu tiên chạy tiến trình sẵn sàng có độ ưu tiên cao nhất trước. Nó hữu ích khi một số tác vụ quan trọng hơn các tác vụ khác, nhưng nếu các tác vụ ưu tiên thấp phải chờ quá lâu thì có nguy cơ starvation.

Một Ví Dụ Có Lời Giải Về Thời Gian Chờ

Giả sử có ba tiến trình đều đến tại thời điểm $0$ và mỗi tiến trình chỉ cần thời gian CPU:

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

Giả sử:

• có một CPU
• không có chặn do I/O
• bỏ qua chi phí chuyển ngữ cảnh

Trong các điều kiện đó, thời gian chờ là thời gian một tiến trình nằm trong hàng đợi sẵn sàng trước khi được chạy. Thời gian hoàn thành là

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

Nếu dùng FCFS, thứ tự là $P_1 \rightarrow P_2 \rightarrow P_3$.

Dòng thời gian:

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

Thời gian chờ:

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

Thời gian chờ trung bình:

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

Nếu dùng SJF không ngắt, thứ tự là $P_3 \rightarrow P_2 \rightarrow P_1$.

Dòng thời gian:

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

Thời gian chờ:

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

Thời gian chờ trung bình:

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

Ví dụ này cho thấy trực giác chính. Tải công việc không thay đổi, nhưng quy tắc đã làm thay đổi kết quả. Ở đây, SJF cho thời gian chờ trung bình thấp hơn vì các công việc ngắn không bị mắc kẹt phía sau công việc dài.

Điều đó không có nghĩa SJF luôn là lựa chọn tốt nhất trong thực tế. Nó chỉ có nghĩa là dưới các giả thiết của ví dụ này, thứ tự lập lịch ảnh hưởng rất lớn đến kết quả.

Trực Giác Cần Ghi Nhớ

Hãy xem lập lịch tiến trình như kỷ luật phục vụ hàng đợi cho CPU. Hàng đợi sẵn sàng có thể chứa cùng một tập công việc, nhưng quy tắc phục vụ hàng đợi đó sẽ làm thay đổi trải nghiệm của người dùng.

Nếu bạn quan tâm nhất đến phản hồi đầu tiên nhanh, bạn có thể thích việc chia sẻ thường xuyên. Nếu bạn quan tâm nhất đến việc hoàn thành nhanh nhiều công việc ngắn, bạn có thể thích một chính sách ưu tiên các burst ngắn. Nếu bạn cần ràng buộc thời gian nghiêm ngặt, bạn có thể lại cần một bộ lập lịch khác.

Những Lỗi Thường Gặp Trong Bài Toán Lập Lịch

Cho rằng một chính sách luôn tốt nhất trong mọi trường hợp

Không có một lựa chọn thắng tuyệt đối cho mọi tải công việc. Một chính sách có thể trông rất tốt về thời gian chờ trung bình nhưng vẫn kém về tính công bằng hoặc việc đáp ứng hạn chót.

Nhầm lẫn giữa thời gian chờ, thời gian đáp ứng và thời gian hoàn thành

Các đại lượng này có liên quan nhưng không giống nhau. Đặc biệt, thời gian đáp ứng thường là thời gian cho đến lần đầu được cấp CPU hoặc lần đầu có phản hồi nhìn thấy được, còn thời gian hoàn thành đo toàn bộ công việc từ lúc đến cho đến lúc kết thúc.

Bỏ qua điều kiện đứng sau công thức

Các đại lượng chỉ có ý nghĩa dưới những giả thiết đã nêu. Nếu bài toán có chặn do I/O, thời điểm đến khác nhau hoặc chi phí chuyển ngữ cảnh, thì dòng thời gian và kết quả sẽ thay đổi.

Quên mất chính sách có ngắt hay không

SJF và shortest remaining time first không phải là cùng một quy tắc. Lập lịch ưu tiên cũng hành xử khác nhau tùy vào việc một công việc ưu tiên cao hơn có thể ngắt công việc hiện tại hay không.

Lập Lịch Tiến Trình Được Dùng Ở Đâu

Lập lịch tiến trình quan trọng ở bất cứ đâu hệ điều hành phải chia sẻ thời gian CPU:

• hệ thống desktop và di động cần ứng dụng phản hồi nhanh
• máy chủ xử lý nhiều yêu cầu
• hệ thống xử lý theo lô quan tâm đến thông lượng
• hệ thống thời gian thực quan tâm đến bảo đảm thời gian

Các bộ lập lịch thực tế thường phức tạp hơn nhiều so với phiên bản trong giáo trình, nhưng những sự đánh đổi cốt lõi vẫn xuất hiện.

Hãy Thử Phiên Bản Của Riêng Bạn

Hãy thay đổi ví dụ sao cho $P_2$ đến muộn hơn, hoặc thay FCFS bằng round robin với quantum $2\ \mathrm{ms}$, rồi xem mô hình thời gian chờ thay đổi thế nào. Nếu muốn thêm một bước sau khi tự làm bằng tay, hãy thử phiên bản của riêng bạn trong GPAI Solver và so sánh dòng thời gian bạn dự đoán với dòng thời gian được tính ra.