3.1. Khái niệm điều độ

Trong hệ thống cho phép đa chương trình, nhiều tiến trình có thể tồn tại và thực hiện cùng một lúc. Kỹ thuật đa chương trình có nhiều ưu điểm do cho phép sử dụng CPU hiệu quả, đồng thời đáp ứng tốt hơn yêu cầu tính toán của người dùng. Bên cạnh đó, đa chương trình cũng đặt ra nhiều vấn đề phức tạp hơn đối với hệ điều hành. Một trong những vấn đề cơ bản khi thực hiện đa chương trình là vấn đề điều độ.

Điều độ (scheduling) hay lập lịch là quyết định tiến trình nào được sử dụng tài nguyên phần cứng khi nào, trong thời gian bao lâu. Bài toán điều độ được đặt ra với mọi dạng tài nguyên khác nhau, chẳng hạn thiết bị vào ra, CPU, bộ nhớ..., kể cả trong trường hợp có chia sẻ thời gian hay không. Trong phần này, chúng ta sẽ tập trung vào vấn đề điều độ đối với CPU, gọi là điều độ CPU, hay là điều độ tiến trình.

Đối với hệ thống bao gồm một CPU duy nhất, tại mỗi thời điểm chỉ một tiến trình được cấp CPU để thực hiện. Hệ điều hành có thể chờ cho tới khi tiến trình không sử dụng CPU nữa hoặc chủ động điều độ lại để chuyển CPU sang thực hiện tiến trình khác, tùy thuộc vào phương pháp điều độ cụ thể. Như vậy điều độ tiến trình là quyết định thứ tự và thời gian sử dụng CPU. Đối với hệ thống nhiều CPU, việc điều độ thường phức tạp hơn, và sẽ không được đề cập tới ở đây.

Điều độ tiến trình và điều độ dòng. Trong những hệ thống trước đây, tiến trình là đơn vị thực hiện chính, là đối tượng được cấp CPU, và việc điều độ được thực hiện đối với tiến trình. Hệ thống hiện nay thường hỗ trợ dòng. Trong trường hợp này, dòng mức nhân là đơn vị thực hiện được hệ điều hành cấp phát CPU chứ không phải tiến trình, và do vậy việc điều độ được hệ điều hành thực hiện trực tiếp với dòng. Tuy nhiên, thuật ngữ điều độ tiến trình vẫn được sử dụng rộng rãi và được hiểu tương đương với điều độ dòng, trừ khi có giải thích cụ thể.

3.2. Các dạng điều độ

Điều độ dài hạn và ngắn hạn

Trong một số hệ thống, điều độ tiến trình được phân chia thành một số mức khác nhau, bao gồm: điều độ dài hạn, điều độ trung hạn, và điều độ ngắn hạn. Theo như tên gọi, điều độ dài hạn được thực hiện cho những khoảng thời gian dài và ít diễn ra nhất. Ngược lại, điều độ ngắn hạn diễn ra thường xuyên, điều độ trung hạn chiếm vị trí ở giữa.

Điều độ dài hạn được thực hiện khi mới tạo ra tiến trình. Hệ điều hành quyết định xem tiến trình có được thêm vào danh sách đang hoạt động hay không. Nếu được chấp nhận, trong hệ thống sẽ thêm tiến trình mới. Ngược lại, tiến trình sẽ phải chờ tới thời điểm khác để được tạo ra và thực hiện. Điều độ dài hạn ảnh hưởng tới mức độ đa chương trình, tức là số lượng tiến trình tối đa trong hệ thống. Trong máy tính cá nhân, người dùng ít cảm nhận được ảnh hưởng của điều độ dài hạn do hầu hết tiến trình đều được chấp nhận tạo mới. Đối với những máy tính lớn được sử dụng chung, điều độ dài hạn đóng vai trò quan trọng và rõ ràng hơn.

Điều độ trung hạn là quyết định tiến trình có được cấp bộ nhớ để thực hiện không. Để thực hiện được, tiến trình cần được tải vào bộ nhớ hoàn toàn, hoặc một phần nếu sử dụng bộ nhớ ảo. Trong một số trường hợp như khi mới khởi tạo và bộ nhớ được nạp trang theo nhu cầu, hay khi tiến trình bị trao đổi ra đĩa (swapping) để nhường chỗ cho tiến trình khác, hệ điều hành cần quyết định có cho phép tải tiến trình vào bộ nhớ để thực hiện không. Điều độ trung hạn cũng ảnh hưởng tới mức độ đa chương trình và được quyết định dựa trên mức độ ưu tiên cùng tình trạng hệ thống. Các tiến trình đã được tạo mới và được tải vào bộ nhớ do kết quả điều độ dài hạn và trung hạn được xếp vào hàng đời để điều độ ngắn hạn.

Điều độ ngắn hạn là quyết định tiến trình nào được cấp CPU để thực hiện. Việc điều độ ngắn hạn được thực đối với những tiến trình đang ở trạng thái sẵn sàng. Hệ điều hành lựa chọn một tiến trình đang trong bộ nhớ và sẵn sàng thực hiện để cấp phát CPU. Việc lựa chọn tiến trình được thực hiện theo một thuật toán nào đó.

Các dạng điều độ gắn liền với việc chuyển tiến trình tự trạng thái này sang trạng thái khác. Hình ??? minh họa quan hệ giữa trạng thái tiến trình và ba dạng điều độ trên.

Hình vẽ: vẽ thêm vào trạng thái tiến trình

Trong các phần tiếp theo, chúng ta chỉ xem xét vấn đề điều độ ngắn hạn. Vì vậy, nếu không nói gì thêm, điều độ tiến trình được hiểu là điều độ ngắn hạn hay điều độ CPU.

Điều độ có phân phối lại

Tùy thuộc vào việc hệ điều hành có thể thực hiện điều độ khi một tiến trình đang sử dụng CPU hay không, ta phân biệt điều độ không phân phối lại (nonpreemptive) và điều độ có phân phối lại (preemptive).

Điều độ có phân phối lại là kiểu điều độ trong đó hệ điều hành có thể sử dụng cơ chế ngắt để thu hồi CPU của một tiến trình đang trong trạng thái chạy, tức là tiến trình đang sử dụng CPU để thực hiện lệnh của mình. Với kiểu điều độ này, hệ điều hành có thể phân phối lại CPU một cách chủ động, không cần chờ cho tới khi tiến trình đang chạy kết thúc hoặc chuyển sang trạng thái chờ đợi (tức là trạng thái không sử dụng CPU).

Điều độ không phân phối lại là kiểu điều độ trong đó tiến trình đang ở trạng thái chạy sẽ được sử dụng CPU cho đến khi xảy ra một trong các tình huống sau: tiến trình kết thúc, tiến trình phải chuyển sang trạng thái chờ đợi (do thực hiện yêu cầu vào/ra hoặc lời gọi hệ thống, hoặc chờ đợi tín hiệu đồng bộ từ tiến trình khác). Điều độ không phân phối lại còn gọi lại điều độ hợp tác (cooperative), do việc điều độ chỉ có thể thực hiện khi tiến trình nhường lại CPU do không cần dùng nữa, hoặc chủ động nhường lại. Trong trường hợp tiến trình không hợp tác và chiếm CPU vô hạn, ví dụ khi sử dụng vòng lặp vô hạn không chứa lời gọi hệ thống, các tiến trình khác sẽ không bao giờ được cấp CPU.

Các phiên bản đầu tiên của Windows là Windows 3.x sử dụng điều độ không phân phối lại. Windows 95, NT và các phiên bản sau sử dụng điều độ có phân phối lại, cho phép thực hiện đa chương trình và chia sẻ thời gian đúng nghĩa và tin cậy hơn.

So với điều độ không phân phối lại, điều độ có phân phối lại có nhiều ưu điểm hơn do hệ điều hành chủ động hơn, không phụ thuộc vào hoạt động của tiến trình. Chỉ có điều độ phân phối lại mới đảm bảo chia sẻ thời gian thực sự. Tuy nhiên, điều độ có phân phối lại đòi hỏi phần cứng phải có bộ định thời gian (timer) và một số hỗ trợ khác.

Bên cạnh đó, điều độ có phân phối lại cũng làm cho vấn đề quản lý tiến trình phức tạp hơn, đặc biệt trong trường hợp các tiến trình chia sẻ dữ liệu dùng chung hoặc có cạnh tranh về tài nguyên. Lấy ví dụ hai tiến trình cùng sử dụng một mảng dữ liệu chung. Do có phân phối lại, CPU có thể được thu hồi từ tiến trình thứ nhất để cấp cho tiến trình thứ hai khi chưa tiến trình thứ nhất chưa cập nhật xong dữ liệu. Nếu tiến trình thứ hai đọc dữ liệu khi đó sẽ nhận được dữ liệu không toàn vẹn.