Chương 4 Định thời biểu CPU

Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0


Đối với những hệ thống tương tác (như các hệ thống chia thời), một số nhà phân
tích đề nghị rằng sự thay đổi trong thời gian đáp ứng quan trọng hơn tối thiểu hóa thời
gian đáp ứng trung bình. Một hệ thống với thời gian đáp ứng phù hợp và có thể đoán
trước được quan tâm nhiều hơn hệ thống chạy nhanh hơn mức trung bình nhưng biến
đổi cao. Tuy nhiên, gần như không có công việc nào được thực hiện trên các giải thuật
định thời biểu CPU để tối thiểu hóa các thay đổi.
Khi chúng ta thảo luận các giải thuật định thời biểu CPU khác nhau, chúng ta
muốn hiển thị các hoạt động của chúng. Một hình ảnh chính xác nên thông báo tới
nhiều quá trình, mỗi quá trình là một chuỗi của hàng trăm chu kỳ CPU và I/O. Để đơn
giản việc hiển thị, chúng ta xem chỉ một chu kỳ CPU (trong mili giây) trên quá trình
trong các thí dụ của chúng ta. Thước đo của việc so sánh là thời gian chờ đợi trung
bình.
V Các giải thuật định thời
Định thời biểu CPU giải quyết vấn đề quyết định quá trình nào trong hàng đợi
sẳn sàng được cấp phát CPU. Trong phần này chúng ta mô tả nhiều giải thuật định
thời CPU đang có.
V.1 Định thời đến trước được phục vụ trước
Giải thuật định thời biểu CPU đơn giản nhất là đến trước, được phục vụ
trước (first-come, first-served-FCFS). Với cơ chế này, quá trình yêu cầu CPU trước
được cấp phát CPU trước. Việc cài đặt chính sách FCFS được quản lý dễ dàng với
hàng đợi FIFO. Khi một quá trình đi vào hàng đợi sẳn sàng, PCB của nó được liên kết
tới đuôi của hàng đợi. Khi CPU rảnh, nó được cấp phát tới một quá trình tại đầu hàng
đợi. Sau đó, quá trình đang chạy được lấy ra khỏi hàng đợi. Mã của giải thuật FCFS
đơn giản để viết và hiểu.
Tuy nhiên, thời gian chờ đợi trung bình dưới chính sách FCFS thường là dài.
Xét tập hợp các quá trình sau đến tại thời điểm 0, với chiều dài thời gian chu kỳ CPU
được cho theo mini giây.

Quá trình Thời gian xử lý
P1 24
P2 3
P3 3

Nếu các quá trình đến theo thứ tự P
1
, P
2
, P
3
và được phục vụ theo thứ tự
FCFS, chúng ta nhận được kết quả được hiển thị trong lưu đồ Gantt như sau:


24 27 30

Thời gian chờ là 0 mili giây cho quá trình P
1
, 24 mili giây cho quá trình P
2
và
27 mili giây cho quá trình P
3
. Do đó, thời gian chờ đợi trung bình là (0+24+27)/3=17
mili giây. Tuy nhiên, nếu các quá trình đến theo thứ tự P
2
, P
3
, P
1
thì các kết quả được
hiển thị trong lưu đồ Gannt như sau:



Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

60
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0



0 3 6 30

Thời gian chờ đợi trung bình bây giờ là (6+0+3)/3=3 mili giây. Việc cắt giảm
này là quan trọng. Do đó, thời gian chờ đợi trung bình dưới chính sách FCFS thường
không là tối thiểu và có sự thay đổi rất quan trọng nếu các thời gian CPU dành cho
các quá trình khác nhau rất lớn.
Ngoài ra, xét năng lực của định thời FCFS trong trường hợp động. Giả sử
chúng ta có một quá trình hướng xử lý (CPU-bound) và nhiều quá trình hướng
nhập/xuất (I/O bound). Khi các quá trình đưa đến quanh hệ thống, ngữ cảnh sau có
thể xảy ra. Quá trình hướng xử lý sẽ nhận CPU và giữ nó. Trong suốt thời gian này,
tất cả quá trình khác sẽ kết thúc việc nhập/xuất của nó và chuyển vào hàng đợi sẳn
sàng, các thiết bị nhập/xuất ở trạng thái rảnh. Cuối cùng, quá trình hướng xử lý kết
thúc chu kỳ CPU của nó và chuyển tới thiết bị nhập/xuất. Tất cả các quá trình hướng
xử lý có chu kỳ CPU rất ngắn sẽ nhanh chóng thực thi và di chuyển trở về hàng đợi
nhập/xuất. Tại thời điểm này CPU ở trạng thái rảnh. Sau đó, quá trình hướng xử lý sẽ
di chuyển trở lại hàng đợi sẳn sàng và được cấp CPU. Một lần nữa, tất cả quá trình
hướng nhập/xuất kết thúc việc chờ trong hàng đợi sẳn sàng cho đến khi quá trình
hướng xử lý được thực hiện. Có một tác dụng phụ (convoy effect) khi tất cả các quá
trình khác chờ một quá trình lớn trả lại CPU. Tác dụng phụ này dẫn đến việc sử dụng
thiết bị và CPU thấp hơn nếu các quá trình ngắn hơn được cấp trước.
Giải thuật FCSF là giải thuật định thời không trưng dụng CPU. Một khi CPU
được cấp phát tới một quá trình, quá trình đó giữ CPU cho tới khi nó giải phóng CPU
bằng cách kết thúc hay yêu cầu nhập/xuất. Giải thuật FCFS đặc biệt không phù hợp
đối với hệ thống chia sẻ thời gian, ở đó mỗi người dùng nhận được sự chia sẻ CPU
với những khoảng thời gian đều nhau.
V.2 Định thời biểu công việc ngắn nhất trước
Một tiếp cận khác đối với việc định thời CPU là giải thuật định thời công việc
ngắn nhất trước (shortest-job-first-SJF). Giải thuật này gán tới mỗi quá trình chiều
dài của chu kỳ CPU tiếp theo cho quá trình sau đó. Khi CPU sẳn dùng, nó được gán
tới quá trình có chu kỳ CPU kế tiếp ngắn nhất. Nếu hai quá trình có cùng chiều dài
chu kỳ CPU kế tiếp, định thời FCFS được dùng. Chú ý rằng thuật ngữ phù hợp hơn là
chu kỳ CPU kế tiếp ngắn nhất (shortest next CPU burst) vì định thời được thực hiện
bằng cách xem xét chiều dài của chu kỳ CPU kế tiếp của quá trình hơn là toàn bộ
chiều dài của nó. Chúng ta dùng thuật ngữ SJF vì hầu hết mọi người và mọi sách tham
khảo tới nguyên lý của loại định thời biểu này như SJF.
Thí dụ, xét tập hợp các quá trình sau, với chiều dài của thời gian chu kỳ CPU
được tính bằng mili giây:

Quá trình Thời gian xử lý
P1 6
P2 8
P3 7
P4 3

Dùng định thời SJF, chúng ta định thời biểu cho các quá trình này theo lưu đồ
Gannt như sau:

Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

61
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0



0 3 9 16 24

Thời gian chờ đợi là 3 mili giây cho quá trình P
1
, 16 mili giây cho quá trình
P
2
, 9 mili giây cho quá trình P
3
, và 0 mili giây cho quá trình P
4
. Do đó, thời gian chờ
đợi trung bình là (3+16+9+0)/4 = 7 mili giây. Nếu chúng ta dùng cơ chế định thời
FCFS thì thời gian chờ đợi trung bình là 10.23 mili giây.
Giải thuật SJF có thể là tối ưu, trong đó nó cho thời gian chờ đợi trung bình
nhỏ nhất cho các quá trình được cho. Bằng cách chuyển một quá trình ngắn trước một
quá trình dài thì thời gian chờ đợi của quá trình ngắn giảm hơn so với việc tăng thời
gian chờ đợi của quá trình dài. Do đó, thời gian chờ đợi trung bình giảm.
Khó khăn thật sự với giải thuật SJF là làm thế nào để biết chiều dài của yêu
cầu CPU tiếp theo. Đối với định thời dài trong hệ thống bó, chúng ta có thể dùng
chiều dài như giới hạn thời gian xử lý mà người dùng xác định khi gởi công việc. Do
đó, người dùng được cơ động để ước lượng chính xác giới hạn thời gian xử lý vì giá
trị thấp hơn có nghĩa là đáp ứng nhanh hơn. Định thời SJF được dùng thường xuyên
trong định thời dài.
Mặc dù SJF là tối ưu nhưng nó không thể được cài đặt tại cấp định thời CPU
ngắn vì không có cách nào để biết chiều dài chu kỳ CPU tiếp theo. Một tiếp cận là
khác gần đúng định thời SJF được thực hiện. Chúng ta có thể không biết chiều dài của
chu kỳ CPU kế tiếp nhưng chúng ta có đoán giá trị của nó. Chúng ta mong muốn rằng
chu kỳ CPU kế tiếp sẽ tương tự chiều dài những chu kỳ CPU trước đó. Do đó, bằng
cách tính toán mức xấp xỉ chiều dài của chu kỳ CPU kế tiếp, chúng ta chọn một quá
trình với chu kỳ CPU được đoán là ngắn nhất.
Chu kỳ CPU kế tiếp thường được đoán như trung bình số mũ của chiều dài các
chu kỳ CPU trước đó. Gọi t
n
là chiều dài của chu kỳ CPU thứ n và gọi T
n+1
giá trị
được đoán cho chu kỳ CPU kế tiếp. Thì đối với α, với 0 ≤ α ≤ 1, định nghĩa

T
n+1
= α t
n
+ (1- α) T
n

Công thức này định nghĩa một giá trị trung bình số mũ. Giá trị của t
n
chứa
thông tin mới nhất; T
n
lưu lịch sử quá khứ. Tham số α điều khiển trọng số liên quan
giữa lịch sử quá khứ và lịch sử gần đây trong việc đoán. Nếu α=0 thì T
n+1
=T
n
và lịch
sử gần đây không có ảnh hưởng (điều kiện hiện hành được đảm bảo là ngắn); nếu α
=1 thì T
n+1
=t
n
và chỉ chu kỳ CPU gần nhất có ảnh hưởng (lịch sử được đảm bảo là cũ
và không phù hợp). Thông dụng hơn, α=1/2 thì lịch sử gần đây và lịch sử quá khứ có
trọng số tương đương. Giá trị khởi đầu T
0
có thể được định nghĩa như một hằng số
hay như toàn bộ giá trị trung bình hệ thống. Hình IV.2 dưới đây hiển thị giá trị trung
bình dạng mũ với α=1/2 và T
0
=10.
Để hiểu hành vi của giá trị trung bình dạng mũ, chúng ta có thể mở rộng công
thức cho T
n+1
bằng cách thay thế T
n
để tìm
T
n+1
=α t
n
+(1-α) α t
n-1
+…+(1-α)
j
α t
n-j
+…+(1-α)
n - 1
T
0
Vì cả hai α và (1- α) là nhỏ hơn hay bằng 1, mỗi số hạng tiếp theo có trọng số
nhỏ hơn số hạng trước đó.
Giải thuật SJF có thể trưng dụng hoặc không trưng dụng CPU. Chọn lựa này
phát sinh khi một quá trình mới đến tại hàng đợi sẳn sàng trong khi một quá trình
trước đó đang thực thi. Một quá trình mới có thể có chu kỳ CPU tiêp theo ngắn hơn
chu kỳ CPU được để lại của quá trình thực thi hiện tại. Giải thuật SJF trưng dụng sẽ
trưng dungj CPU của quá trình đang thực thi hiện tại, trong khi giải thuật SJF không
trưng dụng sẽ cho phép quá trình đang thực thi kết thúc chu kỳ CPU của nó. Định thời
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

62
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0


SJF trưng dụng còn được gọi là định thời thời gian còn lại ngắn nhất trước
(shortest-remaining-time-first).













Hình 0-2 Đoán chiều dài của chu kỳ CPU kế tiếp


Thí dụ, xét 4 quá trình sau với chiều dài của thời gian chu kỳ CPU được cho
tính bằng mili giây

Quá trình Thời gian đến Thời gian xử lý
P1 0 8
P2 1 4
P3 2 9
P4 3 5

Nếu các quá trình đi vào hàng đợi sẳn sàng tại những thời điểm và cần thời
gian xử lý được hiển thị trong bảng trên thì thời biểu SJF trưng dụng được mô tả trong
lưu đồ Gannt như sau:

P1 P2 P3
0 1 5 10 17 26

Quá trình P
1
được bắt đầu tại thời điểm 0, vì nó là quá trình duy nhất trong
hàng đợi. Quá trình P
2
đến tại thời điểm 1. Thời gian còn lại cho P
1
(7 mili giây) là lớn
hơn thời gian được yêu cầu bởi quá trình P
2
(4 mili giây) vì thế quá trình P
1
bị trưng
dụng CPU và quá trình P
2
được định thời biểu. Thời gian chờ đợi trung bình cho thí
dụ này là: ((10-1) + (1-1) + (17-2) + (5-3))/4 = 6.5 mili giây. Định thời SJF không
trưng dụng cho kết quả thời gian chờ đợi trung bình là 7.75 mili giây.
V.3 Định thời theo độ ưu tiên
Giải thuật SJF là trường hợp đặc biệt của giải thuật định thời theo độ ưu tiên
(priority-scheduling algorithm). Độ ưu tiên được gán với mỗi quá trình và CPU được
cấp phát tới quá trình với độ ưu tiên cao nhất. Quá trình có độ ưu tiên bằng nhau được
định thời trong thứ tự FCFS.
Giải thuật SJF là giải thuật ưu tiên đơn giản ở đó độ ưu tiên p là nghịch đảo
với chu kỳ CPU được đoán tiếp theo. Chu kỳ CPU lớn hơn có độ ưu tiên thấp hơn và
ngược lại.
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

63
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0


Bây giờ chúng ta thảo luận định thời có độ ưu tiên cao và thấp. Các độ ưu tiên
thường nằm trong dãy số cố định, chẳng hạn 0 tới 7 hay 0 tới 4,095. Tuy nhiên, không
có sự thoả thuận chung về 0 là độ ưu tiên thấp nhất hay cao nhất. Một vài hệ thống
dùng số thấp để biểu diễn độ ưu tiên thấp; ngược lại các hệ thống khác dùng các số
thấp cho độ ưu tiên cao. Sự khác nhau này có thể dẫn đến sự lẫn lộn. Trong giáo trình
này chúng ta dùng các số thấp để biểu diễn độ ưu tiên cao.
Thí dụ, xét tập hợp quá trình sau đến tại thời điểm 0 theo thứ tự P
1
, P
2
,…, P
5
với chiều dài thời gian chu kỳ CPU được tính bằng mili giây:

Quá trình Thời gian xử lý Độ ưu tiên
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

Sử dụng định thời theo độ ưu tiên, chúng ta sẽ định thời các quá trình này theo
lưu đồ Gannt như sau:

P2 P5 P1 P3 P4
0 1 6 16 18 19

Thời gian chờ đợi trung bình là 8.2 mili giây.
Độ ưu tiên có thể được định nghĩa bên trong hay bên ngoài. Độ ưu tiên được
định nghĩa bên trong thường dùng định lượng hoặc nhiều định lượng có thể đo để tính
toán độ ưu tiên của một quá trình. Thí dụ, các giới hạn thời gian, các yêu cầu bộ nhớ,
số lượng tập tin đang mở và tỉ lệ của chu kỳ nhập/xuất trung bình với tỉ lệ của chu kỳ
CPU trung bình. Các độ ưu tiên bên ngoài được thiết lập bởi các tiêu chuẩn bên ngoài
đối với hệ điều hành như sự quan trọng của quá trình, loại và lượng chi phí đang được
trả cho việc dùng máy tính, văn phòng hỗ trợ công việc,
Định thời biểu theo độ ưu tiên có thể trưng dụng hoặc không trưng dụng CPU.
Khi một quá trình đến hàng đợi sẳn sàng, độ ưu tiên của nó được so sánh với độ ưu
tiên của quá trình hiện đang chạy. Giải thuật định thời theo độ ưu tiên trưng dụng sẽ
chiếm CPU nếu độ ưu tiên của quá trình mới đến cao hơn độ ưu tiên của quá trình
đang thực thi. Giải thuật định thời theo độ ưu tiên không trưng dụng sẽ đơn giản đặt
quá trình mới tại đầu hàng đợi sẳn sàng.
Vấn đề chính với giải thuật định thời theo độ ưu tiên là nghẽn không hạn
định (indefinite blocking) hay đói CPU (starvation). Một quá trình sẳn sàng chạy
nhưng thiếu CPU có thể xem như bị nghẽn-chờ đợi CPU. Giải thuật định thời theo độ
ưu tiên có thể để lại nhiều quá trình có độ ưu tiên thấp chờ CPU không hạn định.
Trong một hệ thống máy tính tải cao, dòng đều đặn các quá trình có độ ưu tiên cao
hơn có thể ngăn chặn việc nhận CPU của quá trình có độ ưu tiên thấp Thông thường,
một trong hai trường hợp xảy ra. Cuối cùng, một quá trình sẽ được chạy (lúc 2 a.m
chủ nhật là thời điểm cuối cùng hệ thống nạp các quá trình nhẹ), hay cuối cùng hệ
thống máy tính sẽ đổ vỡ và mất tất cả các quá trình có độ ưu tiên thấp chưa được kết
thúc.
Một giải pháp cho vấn đề nghẽn không hạn định này là sự hoá già (aging).
Hóa già là kỹ thuật tăng dần độ ưu tiên của quá trình chờ trong hệ thống một thời gian
dài. Thí dụ, nếu các độ ưu tiên nằm trong dãy từ 127 (thấp) đến 0 (cao), chúng ta giảm
độ ưu tiên của quá trình đang chờ xuống 1 mỗi 15 phút. Cuối cùng, thậm chí một quá
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

64
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0


trình với độ ưu tiên khởi đầu 127 sẽ đạt độ ưu tiên cao nhất trong hệ thống và sẽ được
thực thi. Thật vậy, một quá trình sẽ mất không quá 32 giờ để đạt được độ ưu tiên từ
127 tới 0.
V.4 Định thời luân phiên
Giải thuật định thời luân phiên (round-robin scheduling algorithm-RR) được
thiết kế đặc biệt cho hệ thống chia sẻ thời gian. Tương tự như định thời FCFS nhưng
sự trưng dụng CPU được thêm vào để chuyển CPU giữa các quá trình. Đơn vị thời
gian nhỏ được gọi là định mức thời gian (time quantum) hay phần thời gian (time
slice) được định nghĩa. Định mức thời gian thường từ 10 đến 100 mili giây. Hàng đợi
sẳn sàng được xem như một hàng đợi vòng. Bộ định thời CPU di chuyển vòng quanh
hàng đợi sẳn sàng, cấp phát CPU tới mỗi quá trình có khoảng thời gian tối đa bằng
một định mức thời gian.
Để cài đặt định thời RR, chúng ta quản lý hàng đợi sẳn sàng như một hàng đợi
FIFO của các quá trình. Các quá trình mới được thêm vào đuôi hàng đợi. Bộ định thời
CPU chọn quá trình đầu tiên từ hàng đợi sẳn sàng, đặt bộ đếm thời gian để ngắt sau 1
định mức thời gian và gởi tới quá trình.
Sau đó, một trong hai trường hợp sẽ xảy ra. Quá trình có 1 chu kỳ CPU ít hơn
1 định mức thời gian. Trong trường hợp này, quá trình sẽ tự giải phóng. Sau đó, bộ
định thời biểu sẽ xử lý quá trình tiếp theo trong hàng đợi sẳn sàng. Ngược lại, nếu chu
kỳ CPU của quá trình đang chạy dài hơn 1 định mức thời gian thì độ đếm thời gian sẽ
báo và gây ra một ngắt tới hệ điều hành. Chuyển đổi ngữ cảnh sẽ được thực thi và quá
trình được đặt trở lại tại đuôi của hàng đợi sẳn sàng. Sau đó, bộ định thời biểu CPU sẽ
chọn quá trình tiếp theo trong hàng đợi sẳn sàng.
Tuy nhiên, thời gian chờ đợi trung bình dưới chính sách RR thường là quá dài.
Xét một tập hợp các quá trình đến tại thời điểm 0 với chiều dài thời gian CPU-burst
được tính bằng mili giây:

Quá trình Thời gian xử lý
P1 24
P2 3
P3 3

Nếu sử dụng định mức thời gian là 4 mili giây thì quá trình P
1
nhận 4 mili giây
đầu tiên. Vì nó yêu cầu 20 mili giây còn lại nên nó bị trưng dụng CPU sau định mức
thời gian đầu tiên và CPU được cấp tới quá trình tiếp theo trong hàng đợi, quá trình
P
2
. Vì P
2
không cần tới 4 mili giây nên nó kết thúc trước khi định mức thời gian của
nó hết hạn. Sau đó, CPU được cho tới quá trình kế tiếp, quá trình P
3
. Một khi mỗi quá
trình nhận 1 định mức thời gian thì CPU trả về quá trình P
1
cho định mức thời gian
tiếp theo. Thời biểu RR là:



0 4 7 10 14 18 22 26 30

Thời gian chờ đợi trung bình là 17/3=5.66 mili giây.
Trong giải thuật RR, không quá trình nào được cấp phát CPU cho nhiều hơn 1
định mức thời gian trong một hàng. Nếu chu kỳ CPU của quá trình vượt quá 1 định
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

65
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0


mức thời gian thì quá trình đó bị trưng dụng CPU và nó được đặt trở lại hàng đợi sẳn
sàng. Giải thuật RR là giải thuật trưng dụng CPU.
Nếu có n quá trình trong hàng đợi sẳn sàng và định mức thời gian là q thì mỗi
quá trình nhận 1/n thời gian CPU trong các phần, nhiều nhất q đơn vị thời gian. Mỗi
quá trình sẽ chờ không dài hơn (n-1)x q đơn vị thời gian cho tới khi định mức thời
gian tiếp theo của nó. Thí dụ, nếu có 5 quá trình với định mức thời gian 20 mili giây
thì mỗi quá trình sẽ nhận 20 mili giây sau mỗi 100 mili giây.
Năng lực của giải thuật RR phụ thuộc nhiều vào kích thước của định mức thời
gian. Nếu định mức thời gian rất lớn (lượng vô hạn) thì chính sách RR tương tự như
chính sách FCFS. Nếu định mức thời gian là rất nhỏ (1 mili giây) thì tiếp cận RR
được gọi là chia sẻ bộ xử lý (processor sharing) và xuất hiện (trong lý thuyết) tới
người dùng như thể mỗi quá trình trong n quá trình có bộ xử lý riêng của chính nó
chạy tại 1/n tốc độ của bộ xử lý thật.












Hình 0-3 Hiển thị một định mức thời gian nhỏ hơn tăng chuyển đổi ngữ cảnh như thế nào
Tuy nhiên, trong phần mềm chúng ta cũng cần xem xét hiệu quả của việc
chuyển đổi ngữ cảnh trên năng lực của việc định thời RR. Chúng ta giả sử rằng chỉ có
1 quá trình với 10 đơn vị thời gian. Nếu một định mức là 12 đơn vị thời gian thì quá
trình kết thúc ít hơn 1 định mức thời gian, với không có chi phí nào khác. Tuy nhiên,
nếu định mức là 6 đơn vị thời gian thì quá trình cần 2 định mức thời gian, dẫn đến 1
chuyển đổi ngữ cảnh. Nếu định mức thời gian là 1 đơn vị thời gian thì 9 chuyển đổi
ngữ cảnh sẽ xảy ra, việc thực thi của quá trình bị chậm như được hiển thị trong hình
IV.3 .
Do đó chúng ta mong muốn định mức thời gian lớn đối với thời gian chuyển
ngữ cảnh. Nếu thời gian chuyển ngữ cảnh chiếm 10% định mức thời gian thì khoảng
10% thời gian CPU sẽ được dùng cho việc chuyển ngữ cảnh.
Thời gian hoàn thành cũng phụ thuộc kích thước của định mức thời gian.
Chúng ta có thể thấy trong hình IV.4, thời gian hoàn thành trung bình của tập hợp các
quá trình không cần cải tiến khi kích thước định mức thời gian tăng. Thông thường,
thời gian hoàn thành trung bình có thể được cải tiến nếu hầu hết quá trình kết thúc chu
kỳ CPU kế tiếp của chúng trong một định mức thời gian. Thí dụ, cho 3 quá trình có 10
đơn vị thời gian cho mỗi quá trình và định mức thời gian là 1 đơn vị thời gian, thì thời
gian hoàn thành trung bình là 29. Tuy nhiên, nếu định mức thời gian là 10 thì thời
gian hoàn thành trung bình giảm tới 20. Nếu thời gian chuyển ngữ cảnh được thêm
vào thì thời gian hoàn thành trung bình gia tăng đối với định mức thời gian nhỏ hơn vì
các chuyển đổi ngữ cảnh thêm nữa sẽ được yêu cầu.


Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

66
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0





















Hình 0-4 Hiển thị cách thời gian hoàn thành biến đổi theo định mức thời gian

Ngoài ra, nếu định mức thời gian quá lớn thì người thiết kế việc định thời RR
bao gồm chính sách FCFS. Qui tắc là định mức thời gian nên dài hơn 80% chu kỳ
CPU.
V.5 Định thời biểu với hàng đợi nhiều cấp
Một loại giải thuật định thời khác được tạo ra cho những trường hợp mà trong
đó các quá trình được phân lớp thành các nhóm khác nhau. Thí dụ: việc phân chia
thông thường được thực hiện giữa các quá trình chạy ở chế độ giao tiếp (foreground
hay interactive) và các quá trình chạy ở chế độ nền hay dạng bó (background hay
batch). Hai loại quá trình này có yêu cầu đáp ứng thời gian khác nhau và vì thế có yêu
cầu về định thời biểu khác nhau. Ngoài ra, các quá trình chạy ở chế độ giao tiếp có độ
ưu tiên (hay được định nghĩa bên ngoài) cao hơn các quá trình chạy ở chế độ nền.
Một giải thuật định thời hàng đợi nhiều cấp (multilevel queue-scheduling
algorithm) chia hàng đợi thành nhiều hàng đợi riêng rẻ (hình IV.5). Các quá trình
được gán vĩnh viễn tới một hàng đợi, thường dựa trên thuộc tính của quá trình như
kích thước bộ nhớ, độ ưu tiên quá trình hay loại quá trình. Mỗi hàng đợi có giải thuật
định thời của chính nó. Thí dụ: các hàng đợi riêng rẻ có thể được dùng cho các quá
trình ở chế độ nền và chế độ giao tiếp. Hàng đợi ở chế độ giao tiếp có thể được định
thời bởi giải thuật RR trong khi hàng đợi ở chế độ nền được định thời bởi giải thuật
FCFS.
Ngoài ra, phải có việc định thời giữa các hàng đợi, mà thường được cài đặt
như định thời trưng dụng với độ ưu tiên cố định. Thí dụ, hàng đợi ở chế độ giao tiếp
có độ ưu tiên tuyệt đối hơn hàng đợi ở chế độ nền.





Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

67
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0














Hình 0-5 Định thời hàng đợi nhiều mức

Chúng ta xét một thí dụ của giải thuật hàng đợi nhiều mức với năm hàng đợi:

• Các quá trình hệ thống
• Các quá trình giao tiếp
• Các quá trình soạn thảo giao tiếp
• Các quá trình bó
• Các quá trình sinh viên

Mỗi hàng đợi có độ ưu tiên tuyệt đối hơn hàng đợi có độ ưu tiên thấp hơn. Thí
dụ: không có quá trình nào trong hàng đợi bó có thể chạy trừ khi hàng đợi cho các quá
trình hệ thống, các quá trình giao tiếp và các quá trình soạn thảo giao tiếp đều rỗng.
Nếu một quá trình soạn thảo giao tiếp được đưa vào hàng đợi sẳn sàng trong khi một
quá trình bó đang chạy thì quá trình bó bị trưng dụng CPU. Solaris 2 dùng dạng giải
thuật này.
Một khả năng khác là phần (slice) thời gian giữa hai hàng đợi. Mỗi hàng đợi
nhận một phần thời gian CPU xác định, sau đó nó có thể định thời giữa các quá trình
khác nhau trong hàng đợi của nó. Thí dụ, trong hàng đợi giao tiếp-nền, hàng đợi giao
tiếp được cho 80% thời gian của CPU cho giải thuật RR giữa các quá trình của nó,
ngược lại hàng đợi nền nhận 20% thời gian CPU cho các quá trình của nó theo cách
FCFS.
V.6 Định thời hàng đợi phản hồi đa cấp
Thông thường, trong giải thuật hàng đợi đa cấp, các quá trình được gán vĩnh
viễn tới hàng đợi khi được đưa vào hệ thống. Các quá trình không di chuyển giữa các
hàng đợi. Nếu có các hàng đợi riêng cho các quá trình giao tiếp và các quá trình nền
thì các quá trình không di chuyển từ một hàng đợi này tới hàng đợi khác vì các quá
trình không thay đổi tính tự nhiên giữa giao tiếp và nền. Cách tổ chức có ích vì chi phí
định thời thấp nhưng thiếu linh động và có thể dẫn đến tình trạng “đói CPU”.






Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

68
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0














Hình 0-6 Các hàng đợi phản hồi nhiều cấp

Tuy nhiên, định thời hàng đợi phản hồi đa cấp (multilevel feedback queue
scheduling) cho phép một quá trình di chuyển giữa các hàng đợi. Ý tưởng là tách
riêng các quá trình với các đặc điểm chu kỳ CPU khác nhau. Nếu một quá trình dùng
quá nhiều thời gian CPU thì nó sẽ được di chuyển tới hàng đợi có độ ưu tiên thấp. Cơ
chế này để lại các quá trình hướng nhập/xuất và các quá trình giao tiếp trong các hàng
đợi có độ ưu tiên cao hơn. Tương tự, một quá trình chờ quá lâu trong hàng đợi có độ
ưu tiên thấp hơn có thể được di chuyển tới hàng đợi có độ ưu tiên cao hơn. Đây là
hình thức của sự hóa già nhằm ngăn chặn sự đói CPU.
Thí dụ, xét một bộ định thời hàng đợi phản hồi nhiều cấp với ba hàng đợi được
đánh số từ 0 tới 2 (như hình IV.6). Bộ định thời trước tiên thực thi tất cả quá trình
chứa trong hàng đợi 0. Chỉ khi hàng đợi 0 rỗng nó sẽ thực thi các quá trình trong hàng
đợi 1. Tương tự, các quá trình trong hàng đợi 2 sẽ được thực thi chỉ nếu hàng đợi 0 và
1 rỗng. Một quá trình đến hàng đợi 1 sẽ ưu tiên hơn quá trình đến hàng đợi 2. Tương
tự, một quá trình đến hàng đợi 0 sẽ ưu tiên hơn một quá trình vào hàng đợi 1.
Một quá trình đưa vào hàng đợi sẳn sàng được đặt trong hàng đợi 0. Một quá
trình trong hàng đợi 0 được cho một định mức thời gian là 8 mili giây. Nếu nó không
kết thúc trong thời gian này thì nó sẽ di chuyển vào đuôi của hàng đợi 1. Nếu hàng
đợi 0 rỗng thì quá trình tại đầu của hàng đợi 1 được cho định mức thời gian là 16 mili
giây. Nếu nó không hoàn thành thì nó bị chiếm CPU và được đặt vào hàng đợi 2. Các
quá trình trong hàng đợi 2 được chạy trên cơ sở FCFS chỉ khi hàng đợi 0 và 1 rỗng.
Giải thuật định thời này cho độ ưu tiên cao nhất tới bất cứ quá trình nào với chu
kỳ CPU 8 mili giây hay ít hơn. Một quá trình như thế sẽ nhanh chóng nhận CPU, kết
thúc chu kỳ CPU của nó và bỏ đi chu kỳ I/O kế tiếp của nó. Các quá trình cần hơn 8
mili giây nhưng ít hơn 24 mili giây được phục vụ nhanh chóng mặc dù với độ ưu tiên
thấp hơn các quá trình ngắn hơn. Các quá trình dài tự động rơi xuống hàng đợi 2 và
được phục vụ trong thứ tự FCFS với bất cứ chu kỳ CPU còn lại từ hàng đợi 0 và 1.
Nói chung, một bộ định thời hàng đợi phản hồi nhiều cấp được định nghĩa bởi
các tham số sau:

• Số lượng hàng đợi
• Giải thuật định thời cho mỗi hàng đợi
• Phương pháp được dùng để xác định khi nâng cấp một quá trình tới hàng
đợi có độ ưu tiên cao hơn.
• Phương pháp được dùng để xác định khi nào chuyển một quá trình tới hàng
đợi có độ ưu tiên thấp hơn.
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang

69

Xem chi tiết: Chương 4 Định thời biểu CPU