Bài viết này sẽ nói về nội dung định thời tiến trình. Tuy nhiên vẫn chưa hoàn tất, sẽ còn update nữa.

Mục đích của hệ thống multiprogram đó là có thể chạy nhiều tiến trình vào tất cả mọi thời điểm, nhờ đó có thể tận dụng tối đa sức mạnh của CPU. Mục địch của time-sharing đó là chuyển đổi qua lại giữa các tiến trình được thực thi trong CPU, nhờ đó người dùng có thể thương tác với mỗi chương trình khi nó đang chạy. Để thực hiện được các mục đích này, bộ định thời tiến trình (process scheduler) sẽ lựa chọn một available process (có thể từ một set gồm nhiều available processes) để tiến hành thực thi chương trình trên CPU. Nếu có nhiều tiến trình, các tiến trình còn lại sẽ phải đợi cho đến khi CPU rãnh rỗi và tiến hành định thời lại.

1. Scheduling queues.

Khi một tiến trình được đưa vào hệ thống, nó sẽ được đặt vào job queue, nơi chứa đựng tất cả các tiến trình của hệ thống. Các tiến trình nằm trong bộ nhớ chính, trong trạng thái sẵn sàng được thực thi sẽ được lưu trữ trong một danh sách gọi là ready queue. Hàng đợi này thông thường sẽ có cấu trúc là một danh sách liên kết. Head của ready queue chứa con trỏ đến PCB đầu tiên và PCB cuối cùng trong danh sách. Mỗi PCB chứa một con trỏ trỏ đến PCB tiếp theo trong ready queue.

Hệ thống cũng bao gồm các hàng đợi khác. Khi một tiến trình được cấp phát CPU, nó thực thi trong một khoảng thời gian, sau đó sẽ thoát ra, vì nó bị gián đoạn hoặc phải chờ sự xuất hiện của một event đặc biệt nào đó, ví dụ như yêu cầu thiết bị I/O.

Giả sử tiến trình thực hiện một yêu cầu I/O đến thiết bị chia sẽ, ví dụ như disk. Vì có nhiều tiến trình trong hệ thống, đĩa cứng có thể sẽ bận bởi vì nó đang đáp ứng cho các tiến trình khác. Vì thế, tiến trình đó cần phải chờ cho đến khi đĩa cứng đáp ứng yêu cầu. Danh sách các tiến trình chờ đợi một thiết bị I/O nào đó được gọi là device queue. Mỗi thiết bị có device queue của riêng nó. (Xem hình)

alt

Một mô tả thông thường cho vấn đề định thời tiến trình đó là queueing diagram, được trình bày ở hình dưới. Mỗi hộp hình chữ nhật mô tả một hàng đợi. Có 2 loại hàng đợi được giới thiệu trong hình: ready queue và một tập các device queues. Hình tròn mô tả các tài nguyên phục vụ cho hàng đợi, và mũi tên chỉ ra đường đi của các tiến trình trong hệ thống.

alt

Một tiến trình được khởi tạo sẽ nằm trong ready queue. Nó sẽ chờ cho đến khi nó được select để thực thi, hoặc bị loại ra khỏi hàng đợi. Một khi tiến trình được cấp phát CPU và thực thi, một trong các sự kiện sau có thể xảy ra:

  • Tiến trình có thể gởi một I/O request và sau đó được chuyển vào một I/O queue.
  • Tiến trình sẽ tạo ra một tiến trình con mới và đợi cho đến khi tiến trình con kết thúc.
  • Tiến trình có thể bị remove bởi CPU, nguyên nhân là do có một interrupt xảy ra, và tiến trình này sẽ được chuyển về lại ready queue.

Trong 2 trường hợp đầu tiên, tiến trình sẽ chuyển từ trạng thái chờ sang ready và nó sẽ được đặt vào ready queue. Một tiến trình tiếp tục chu kì này cho đến khi nó kết thúc, khi đó nó sẽ bị remove ra khỏi tất cả các hàng đợi và PCB và các tài nguyên mà nó sử dụng sẽ bị deallocated, trả lại cho hệ thống.

2. Bộ định thời – Scheduler

Một tiến trình chuyển đổi qua lại giữa các hàng đợi định thời (scheduling queue) suốt thời gian tồn tại của nó. Hệ điều hành cần phải select các tiến trình từ những hàng đợi này tùy theo mục đính định thời, Việc lựa chọn các tiến trình này được xử lí bởi bộ định thời riêng.

Thông thường, trong hệ thống batch, nhiều tiến trình cần được xem xét trước hơn là được thực thi ngay lập tức. Các tiến trình này được lưu trữ tạm thời trên mass-storage device (thông thường là đĩa cứng) – nơi mà chúng sẽ ở lại cho đến lượt thực thi sau. Bộ định thời long-term scheduler, hay job scheduler, lựa chọn các tiến trình từ pool này và load vào bộ nhớ để thực thi.

Short-term scheduler, hay CPU scheduler, lựa chọn từ các tiến trình đang sẵn sàng được thực thi và cấp phát CPU cho một trong số các tiến trình đó.

Điểm khác biệt chủ yếu giữa hai bộ định thời này nằm ở chỗ tần số thực thi. Short-term scheduler phải lựa chọn một tiến trình mới cho CPU một cách thường xuyên, đều đặn. Một tiến trình có thể thực thi chỉ trong vài mili giây trước khi chuyển sang chờ đợi một I/O request được đáp ứng. Chính vì thời gian thực thi giữa 2 tiến trình rất ngắn, nên short-term scheduler cần phải nhanh. Nếu cần 10 mili giây để đưa ra quyết định thực thi một tiến trình trong 100 mili giây, thì 10/(100+10)=9% CPU được sử dụng chỉ đơn giản để scheduling works.

Long-term scheduler thực thi ít thường xuyên hơn; khoảng cách thời gian khởi tạo giữa 2 tiến trình khác nhau có thể khoảng vài phút. Long-term scheduler điều khiển cái gọi là degree of multiprogramming (số tiến trình trong bộ nhớ chính) – tạm gọi là mức độ đa chương. Nếu mức độ đa chương này là ổn định thì tỉ lệ trung bình của các tiến trình mới khởi tạo phải bằng với tỉ lệ trung bình các tiến trình kết thúc, được giải phóng ra khỏi hệ thống. Vì vậy, long-term scheduler có thể chỉ cần được gọi khi một tiến trình rời khỏi hệ thống. Bởi vì khoảng thời gian giữa hai lần thực thi của long-term scheduler dài hơn nên nó có thể đáp ứng được vấn đề cần nhiều thời gian để quyết định tiến trình nào nên được chọn để thực thi.

Một vấn đề quan trọng đó là long-term scheduler cần phải lựa chọn các tiến trình một cách kĩ càng. Thông thường, hầu hết các process có thể thiên về một trong hai hướng: thiên về I/O (I/O bound) hoặc thiên về CPU (CPU bound). Một tiến trình thiên về I/O (I/O-bound process) sẽ dành nhiều thời gian để thực hiện các tác vụ I/O hơn là thực hiện công việc tính toán, và ngược lại, tiến trình thiên về CPU (CPU-bound process) sẽ dành thời gian cho I/O ít thường xuyên hơn, thay vào đó sẽ tập trung thực hiện các công việc tính toán. Điều quan trọng ở đây là long-term scheduler cần phải chọn một tiến trình tốt, kết hợp giữa I/O-bound processes và CPU-bound processes. Nếu tất cả các tiến trình đều là I/O bound, ready queue hầu như sẽ luôn luôn trống và short-term scheduler sẽ có ít việc để làm hơn. Nếu tất cả các tiến trình đều là CPU bound, hàng đợi I/O sẽ hầu như luôn luôn trống, các thiết bị sẽ không được sử dụng và như vậy, hệ thống lại trở nên mất cân bằng. Một hệ thống với hiệu năng tối đa vì vậy sẽ có sự kết hợp giữa CPU-bound và I/O-bound precesses.

Trên một số hệ thống, long-term scheduler có thể sẽ không có hoặc rất nhỏ. Ví dụ như hệ thống time-sharing như UNIX và Microsoft Windows thường không có long-term scheduler, nó chỉ đơn giản đặt mọi tiến trình mới vào bộ nhớ cho short-term scheduler.

Trong một vài hệ điều hành, ví dụ như hệ thống time-sharing, còn có thể giới thiệu bộ định thời medium-term scheduler. Ý tưởng chính của mid-term scheduler là đôi khi, việc remove các tiến trình sẽ có lợi cho bộ nhớ, và như vậy sẽ giảm degree of multiprogramming (mức độ đa chương). Sau này, tiến trình có thể sẽ được đưa trở lại vào bộ nhớ chính để tiếp tục thực thi. Cơ chế này gọi là swapping. Tiến trình được swap out, sau đó lại swap in bởi medium-term scheduler.

alt