Giáo trình Hệ điều hành - Định thời biểu CPU

ệ thống máy tính được mô tả như một mạng các server. Mỗi server có một 
hàng đợi cho các quá trình. CPU là một server với hàng đợi sẳn sàng của nó, như là 
một hệ thống nhập/xuất với các hàng đợi thiết bị. Biết tốc độ đến và tốc độ phục vụ, 
chúng ta có thể tính khả năng sử dụng, chiều dài hàng đợi trung bình, thời gian chờ 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 74
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
trung bình,..Lĩnh vực nghiên cứu này được gọi là phân tích mạng hàng đợi (queueing-
network analysis). 
Thí dụ, gọi n là chiều dài hàng đợi trung bình (ngoại trừ các quá trình đang 
được phục vụ), gọi W là thời gian chờ đợi trung bình trong hàng đợi và λ là tốc độ đến 
trung bình cho các quá trình mới trong hàng đợi (chẳng hạn 3 quá trình trên giây). Sau 
đó, chúng ta mong đợi trong suốt thời gian W một quá trình chờ, λ x W các quá trình 
mới sẽ đến trong hàng đợi. Nếu hệ thống ở trong trạng thái đều đặn thì số lượng quá 
trình rời hàng đợi phải bằng số lượng quá trình đến. Do đó, 
n = λ x W 
Công thức này được gọi là công thức Little. Công thức Little là đặc biệt có ích 
vì nó phù hợp cho bất cứ giải thuật định thời và sự phân bổ các quá trình đến. 
Chúng ta sử dụng công thức Little để tính một trong ba biến, nếu chúng ta biết 
hai biến khác. Thí dụ, nếu chúng ta biết có 7 quá trình đến mỗi giây (trung bình) và 
thường có 14 quá trình trong hàng đợi thì chúng ta có thể tính thời gian chờ đợi trung 
bình trên mỗi quá trình là 2 giây. 
Phân tích hàng đợi có thể có ích trong việc so sánh các giải thuật định thời 
nhưng nó cũng có một số giới hạn. Hiện nay, các loại giải thuật và sự phân bổ được 
quản lý là tương đối giới hạn. Tính toán của các giải thuật phức tạp và sự phân bổ là 
rất khó để thực hiện. Do đó, phân bổ đến và phục vụ thường được định nghĩa không 
thực tế, nhưng dễ hướng dẫn về mặt tính toán. Thông thường cần thực hiện một số giả 
định độc lập có thể không chính xác. Do đó, để chúng sẽ có thể tính câu trả lời, các 
mô hình hàng đợi thường chỉ xấp xỉ hệ thống thật. Vì thế, độ chính xác của các kết 
quả tính toán có thể là sự nghi vấn. 
VIII.3 Mô phỏng 
Để đạt được sự đánh giá các giải thuật định thời chính xác hơn, chúng ta có 
thể dùng mô phỏng (simulations). Mô phỏng liên quan đến lập trình một mô hình hệ 
thống máy tính. Cấu trúc dữ liệu phần mềm biểu diễn các thành phần quan trọng của 
hệ thống. Bộ mô phỏng có một biến biểu diễn đồng hồ; khi giá trị của biến này tăng, 
bộ mô phỏng sửa đổi trạng thái hệ thống để phản ánh các hoạt động của các thiết bị, 
các quá trình và các bộ định thời. Khi sự mô phỏng thực thi, các thống kê hiển thị 
năng lực của giải thuật được tập hợp và in ra. 
Hình 0-8 Đánh giá các bộ định thời CPU bằng mô phỏng 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 75
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
Dữ liệu để định hướng sự mô phỏng có thể được sinh ra trong nhiều cách. 
Cách thông dụng nhất dùng bộ sinh số ngẫu nhiên, được lập trình để sinh ra các quá 
trình, thời gian chu kỳ CPU, đến, đi của quá trình,..dựa trên phân bổ xác suất. Sự phân 
bổ này có thể được định nghĩa dạng toán học (đồng nhất, hàm mũ, phân bổ Poisson) 
hay theo kinh nghiệm. Nếu sự phân bổ được định nghĩa theo kinh nghiệm thì các 
thước đo của hệ thống thật dưới sự nghiên cứu là lấy được. Các kết quả được dùng để 
định nghĩa sự phân bổ thật sự các sự kiện trong hệ thống thực và sau đó sự phân bổ 
này có thể được dùng để định hướng việc mô phỏng. 
Tuy nhiên, một mô phỏng hướng phân bổ có thể không chính xác do mối quan 
hệ giữa các sự kiện tiếp theo trong hệ thống thực. Sự phân bổ thường xuyên hiển thị 
chỉ bao nhiêu sự kiện xảy ra; nó không hiển thị bất cứ thứ gì về thứ tự xảy ra của 
chúng. Để sửa chữa vấn đề này, chúng ta dùng băng từ ghi vết (trace tapes). Chúng ta 
tạo một băng từ ghi vết bằng cách giám sát hệ thống thực, ghi lại chuỗi các sự kiện 
thật (như hình IV.8). Sau đó, thứ tự này được dùng để định hướng việc mô phỏng. 
Băng từ ghi vết cung cấp cách tuyệt vời để so sánh chính xác hai giải thuật trên cùng 
một tập hợp dữ liệu vào thật. Phương pháp này có thể cung cấp các kết quả chính xác 
cho dữ liệu vào của nó. 
Tuy nhiên, mô phỏng có thể rất đắt và thường đòi hỏi hàng giờ máy tính để 
thực hiện. Một mô phỏng chi tiết hơn cung cấp các kết quả chính xác hơn nhưng cũng 
yêu cầu nhiều thời gian máy tính hơn. Ngoài ra, các băng từ ghi vết có thể yêu cầu 
lượng lớn không gian lưu trữ. Cuối cùng, thiết kế, mã, gỡ rối của bộ mô phỏng là một 
tác vụ quan trọng. 
VIII.4 Cài đặt 
Ngay cả mô phỏng cũng cho độ chính xác có giới hạn. Chỉ có cách chính xác 
hoàn toàn để đánh giá giải thuật định thời là mã hóa (code) nó, đặt nó vào trong hệ 
điều hành và xem nó làm việc như thế nào. Tiếp cận này đặt một giải thuật thật sự vào 
hệ thống thật để đánh giá dưới điều kiện hoạt động thật sự. 
Khó khăn chủ yếu là chi phí của tiếp cận. Chi phí bao gồm không chỉ mã hóa 
giải thuật và sửa đổi hệ điều hành để hỗ trợ nó cũng như các cấu trúc dữ liệu được yêu 
cầu mà còn phản ứng của người dùng đối với sự thay đổi liên tục hệ điều hành. Hầu 
hết người dùng không quan tâm việc xây dựng một hệ điều hành tốt hơn; họ chỉ đơn 
thuần muốn biết các quá trình của họ thực thi và dùng các kết quả của chúng. Một hệ 
điều hành thay đổi liên tục không giúp cho người dùng nhận thấy công việc của họ 
được thực hiện. Một dạng của phương pháp này được dùng phổ biến cho việc cài đặt 
máy tính mới. Thí dụ, một tiện ích Web mới có thể mô phỏng tải người dùng được 
phát sinh trước khi nó “sống” (goes live), để xác định bất cứ hiện tượng thắt cổ chai 
trong tiện ích và để ước lượng bao nhiêu người dùng hệ thống có thể hỗ trợ. 
Một khó khăn khác với bất cứ việc đánh giá giải thuật nào là môi trường trong đó giải 
thuật được dùng sẽ thay đổi. Môi trường sẽ thay đổi không chỉ trong cách thông 
thường như những chương trình mới được viết và các loại vấn đề thay đổi, mà còn kết 
quả năng lực của bộ định thời. Nếu các quá trình được cho với độ ưu tiên ngắn thì 
người dùng có thể tách các quá trình lớn thành tập hợp các quá trình nhỏ hơn. Nếu 
quá trình giao tiếp được cho độ ưu tiên vượt qua các quá trình không giao tiếp thì 
người dùng có thể chuyển tới việc dùng giao tiếp.
Thí dụ, trong DEC TOPS-20, hệ thống được phân loại các quá trình giao tiếp 
và không giao tiếp một cách tự động bằng cách xem lượng nhập/xuất thiết bị đầu 
cuối. Nếu một quá trình không có nhập hay xuất tới thiết bị đầu cuối trong khoảng 
thời gian 1 phút thì quá trình được phân loại là không giao tiếp và được di chuyển tới 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 76
Đạ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àng đợi có độ ưu tiên thấp. Chính sách này dẫn đến trường hợp một người lập trình 
sửa đổi chương trình của mình để viết một ký tự bất kỳ tới thiết bị đầu cuối tại khoảng 
thời gian đều đặn ít hơn 1 phút. Hệ thống này cho những chương trình này có độ ưu 
tiên cao mặc dù dữ liệu xuất của thiết bị đầu cuối là hoàn toàn không có ý nghĩa. 
Các giải thuật có khả năng mềm dẻo nhất có thể được thay đổi bởi người quản lý hay 
người dùng. Trong suốt thời gian xây dựng hệ điều hành, thời gian khởi động, thời 
gian chạy, các biến được dùng bởi các bộ định thời có thể được thay đổi để phản ánh 
việc sử dụng của hệ thống trong tương lai. Yêu cầu cho việc định thời biểu mềm dẻo 
là một trường hợp khác mà ở đó sự tách riêng các cơ chế từ chính sách là có ích. Thí 
dụ, nếu các hóa đơn cần được xử lý và in lập tức nhưng thường được thực hiện như 
công việc bó có độ ưu tiên thấp, hàng đợi bó được cho tạm thời độ ưu tiên cao hơn. 
Tuy nhiên, rất ít hệ điều hành chấp nhận loại định thời này. 
IX Tóm tắt 
Định thời CPU là một tác vụ chọn một quá trình đang chờ từ hàng đợi sẳn sàng 
và cấp phát CPU tới nó. CPU được cấp phát tới quá trình được chọn bởi bộ cấp phát. 
Định thời đến trước, được phục vụ trước (FCFS) là giải thuật định thời đơn giản nhất, 
nhưng nó có thể gây các quá trình ngắn chờ các quá trình quá trình quá dài. Định thời 
ngắn nhất, phục vụ trước (SJF) có thể tối ưu, cung cấp thời gian chờ đợi trung bình 
ngắn nhất. Cài đặt định thời SJF là khó vì đoán trước chiều dài của chu kỳ CPU kế 
tiếp là khó. Giải thuật SJF là trường hợp đặc biệt của giải thuật định thời trưng dụng 
thông thường. Nó đơn giản cấp phát CPU tới quá trình có độ ưu tiên cao nhất. Cả hai 
định thời độ ưu tiên và SJF có thể gặp phải trở ngại của việc đói tài nguyên. 
Định thời quay vòng (RR) là hợp lý hơn cho hệ thống chia sẻ thời gian. Định 
thời RR cấp phát CPU tới quá trình đầu tiên trong hàng đợi sẳn sàng cho q đơn vị thời 
gian, ở đây q là định mức thời gian. Sau q đơn vị thời gian, nếu quá trình này không 
trả lại CPU thì nó bị chiếm và quá trình này được đặt vào đuôi của hàng đợi sẳn sàng. 
Vấn đề quan trọng là chọn định mức thời gian. Nếu định mức quá lớn, thì định thời 
RR giảm hơn định thời FCFS ; nếu định mức quá nhỏ thì chi phí định thời trong dạng 
thời gian chuyển ngữ cảnh trở nên thừa. 
Giải thuật FCFS là không ưu tiên; giải thuật RR là ưu tiên. Các giải thuật SJF 
và ưu tiên có thể ưu tiên hoặc không ưu tiên. 
Các giải thuật hàng đợi nhiều cấp cho phép các giải thuật khác nhau được 
dùng cho các loại khác nhau của quá trình. Chung nhất là hàng đợi giao tiếp ở chế độ 
hiển thị dùng định thời RR và hàng đợi bó chạy ở chế độ nền dùng định thời FCFS. 
Hàng đợi phản hồi nhiều cấp cho phép các quá trình di chuyển từ hàng đợi này sang 
hàng đợi khác. 
Vì có nhiều giải thuật định thời sẳn dùng, chúng ta cần các phương pháp để 
chọn giữa chúng. Các phương pháp phân tích dùng cách thức phân tích toán học để 
xác định năng lực của giải thuật. Các phương pháp mô phỏng xác định năng lực bằng 
cách phỏng theo giải thuật định thời trên những mẫu ‘đại diện’ của quá trình và tính 
năng lực kết quả. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 77