Giáo trình Hệ điều hành - Chương 4: Quản lý Processor

hững mục tiêu đề ra. 
Một số đặc tính của tiến trình cần đ−ợc quan tâm nh− tiêu chuẩn điều 
phối : 
a. Tính h−ớng xuất / nhập của tiến trình ( I/O-boundedness): 
 3
Khi một tiến trình nhận đ−ợc CPU, chủ yếu nó chỉ sử dụng CPU đến khi 
phát sinh một yêu cầu nhập xuất. Hoạt động của các tiến trình nh− thế 
th−ờng bao gồm nhiều l−ợt sử dụng CPU , mỗi l−ợt trong một thời gian khá 
ngắn. 
b. Tính h−ớng xử lý của tiến trình ( CPU-boundedness): 
Khi một tiến trình nhận đ−ợc CPU, nó có khuynh h−ớng sử dụng CPU 
đến khi hết thời gian dành cho nó ? Hoạt động của các tiến trình nh− thế 
th−ờng bao gồm một số ít l−ợt sử dụng CPU, nh−ng mỗi l−ợt trong một thời 
gian đủ dài. 
c) Tiến trình t−ơng tác hay xử lý theo lô : 
Ng−ời sử dụng theo kiểu t−ơng tác th−ờng yêu cầu đ−ợc hồi đáp tức thời 
đối với các yêu cầu của họ, trong khi các tiến trình của tác vụ đ−ợc xử lý 
theo lô nói chung có thể trì hoãn trong một thời gian chấp nhận đ−ợc. 
d) Độ −u tiên của tiến trình : 
Các tiến trình có thể đ−ợc phân cấp theo một số tiêu chuẩn đánh giá nào 
đó, một cách hợp lý, các tiến trình quan trọng hơn ( có độ −u tiên cao hơn) 
cần đ−ợc −u tiên hơn. 
e) Thời gian đã sử dụng CPU của tiến trình : 
Một số quan điểm −u tiên chọn những tiến trình đã sử dụng CPU nhiều 
thời gian nhất vì hy vọng chúng sẽ cần ít thời gian nhất để hoàn tất và rời 
khỏi hệ thống . Tuy nhiên cũng có quan điểm cho rằng các tiến trình nhận 
đ−ợc CPU trong ít thời gian là những tiến trình đã phải chờ lâu nhất, do vậy 
−u tiên chọn chúng. 
f) Thời gian còn lại tiến trình cần để hoàn tất : 
Có thể giảm thiểu thời gian chờ đợi trung bình của các tiến trình bằng 
cách cho các tiến trình cần ít thời gian nhất để hoàn tất đ−ợc thực hiện tr−ớc. 
Tuy nhiên đáng tiếc là rất hiếm khi biết đ−ợc tiến trình cần bao nhiêu thời 
gian nữa để kết thúc xử lý. 
 4
1.3. Điều phối không độc quyền và điều phối độc quyền 
(preemptive/nopreemptive) 
Thuật toán điều phối cần xem xét và quyết định thời điểm chuyển đổi 
CPU giữa các tiến trình. Hệ điều hành có thể thực hiện cơ chế điều phối theo 
nguyên lý độc quyền hoặc không độc quyền. 
Điều phối độc quyền : Nguyên lý điều phối độc quyền cho phép một 
tiến trình khi nhận đ−ợc CPU sẽ có quyền độc chiếm CPU đến khi hoàn tất 
xử lý hoặc tự nguyện giải phóng CPU. Khi đó quyết định điều phối CPU sẽ 
xảy ra trong các tình huống sau: 
- Khi tiến trình chuyển từ trạng thái đang xử lý(running) sang trạng thái 
bị khóa blocked ( ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình 
con kết thúc). 
- Khi tiến trình kết thúc. 
Các giải thuật độc quyền th−ờng đơn giản và dễ cài đặt. Tuy nhiên 
chúng th−ờng không thích hợp với các hệ thống tổng quát nhiều ng−ời dùng, 
vì nếu cho phép một tiến trình có quyền xử lý bao lâu tùy ý, có nghĩa là tiến 
trình này có thể giữ CPU một thời gian không xác định, có thể ngăn cản 
những tiến trình còn lại trong hệ thống có một cơ hội để xử lý. 
 Điều phối không độc quyền : Ng−ợc với nguyên lý độc quyền, điều 
phối theo nguyên lý không độc quyền cho phép tạm dừng hoạt động của một 
tiến trình đang sẵn sàng xử lý. Khi một tiến trình nhận đ−ợc CPU, nó vẫn 
đ−ợc sử dụng CPU đến khi hoàn tất hoặc tự nguyện giải phóng CPU nh−ng 
một tiến trình khác có độ −u tiên cao hơn có thể giành quyền sử dụng CPU 
của tiến trình ban đầu. Nh− vậy là tiến trình có thể bị tạm dừng hoạt động bất 
cứ lúc nào mà không đ−ợc báo tr−ớc để tiến trình khác xử lý. Các quyết định 
điều phối xảy ra khi : 
 5
- Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng 
thái bị khóa blocked (ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình 
con kết thúc ). 
- Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng 
thái ready ( ví dụ xảy ra một ngắt). 
- Khi tiến trình chuyển từ trạng thái chờ (blocked) sang trạng thái ready 
( ví dụ một thao tác nhập/xuất hoàn tất). 
- Khi tiến trình kết thúc. 
Các thuật toán điều phối theo nguyên tắc không độc quyền ngăn cản 
đ−ợc tình trạng một tiến trình độc chiếm CPU, nh−ng việc tạm dừng một tiến 
trình có thể dẫn đến các mâu thuẫn trong truy xuất, đòi hỏi phải sử dụng một 
ph−ơng pháp đồng bộ hóa thích hợp để giải quyết. 
Trong các hệ thống sử dụng nguyên lý điều phối độc quyền có thể xảy 
ra tình trạng các tác vụ cần thời gian xử lý ngắn phải chờ tác vụ xử lý với 
thời gian rất dài hoàn tất. Nguyên lý điều phối độc quyền th−ờng chỉ thích 
hợp với các hệ xử lý theo lô. 
Đối với các hệ thống t−ơng tác (time sharing), các hệ thời gian thực 
(real time), cần phải sử dụng nguyên lý điều phối không độc quyền để các 
tiến trình quan trọng có cơ hội hồi đáp kịp thời. Tuy nhiên thực hiện điều 
phối theo nguyên lý không độc quyền đòi hỏi những cơ chế phức tạp trong 
việc phân định độ −u tiên, và phát sinh thêm chi phí khi chuyển đổi CPU qua 
lại giữa các tiến trình. 
IV.2. Phân phối VXL 
Mỗi ph−ơng pháp phân phối CPU đ−ợc đánh giá thông qua các tiêu chí : 
- Thứ tự thực hiện các tiến trình 
- Thời gian chờ của mỗi tiến trình : Thời điểm đ−ợc thực hiện – thời 
điểm xuất hiện 
 6
- Thời gian hoàn thành : thời điểm kết thúc - thời điểm xuất hiện 
IV.3.1. Chiến l−ợc FIFO 
Nguyên tắc : CPU đ−ợc cấp phát cho tiến trình đầu tiên trong danh sách 
sẵn sàng có yêu cầu (là tiến trình đ−ợc đ−a vào hệ thống sớm nhất). Đây là 
thuật toán điều phối theo nguyên tắc độc quyền. Một khi CPU đ−ợc cấp phát 
cho tiến trình, CPU chỉ đ−ợc tiến trình tự nguyện giải phóng khi kết thúc xử 
lý hay khi có một yêu cầu nhập/xuất. 
Ví dụ : 
Tiến trình Thời điểm vào Thời gian xử lý 
P1 0 24 
P2 1 3 
P3 2 3 
- Thứ tự cấp phát CPU cho các tiến trình là : 
 P1 → P2 → P3 
- Thời gian chờ đợi đ−ợc xử lý là : 
P1 : 0 
P2 : 24 -1 = 23 
P3: 24 + 3 -2 =25 
- Thời gian chờ trung bình là ( 0+23+25)/3 = 16 milisecondes. 
- Thời gian hoàn thành : 
Thảo luận : Thời gian chờ trung bình không đạt cực tiểu, và biến đổi 
đáng kể đối với các giá trị về thời gian yêu cầu xử lý và thứ tự khác nhau của 
các tiến trình trong danh sách sẵn sàng. Có thể xảy ra hiện t−ợng tích lũy 
thời gian chờ, khi các tất cả các tiến trình (có thể có yêu cầu thời gian ngắn) 
phải chờ đợi một tiến trình có yêu cầu thời gian dài kết thúc xử lý. 
 7
Giải thuật này đặc biệt không phù hợp với các hệ phân chia thời gian, 
trong các hệ này, cần cho phép mỗi tiến trình đ−ợc cấp phát CPU đều đặn 
trong từng khoảng thời gian. 
IV.3.2. Chiến l−ợc công việc ngắn nhất (Shortest Job First SJF) 
SJF còn đ−ợc gọi là SJN ( Shorstest Job Next) 
Nguyên tắc : Đây là một tr−ờng hợp đặc biệt của giải thuật điều phối 
với độ −u tiên. Trong giải thuật này, độ −u tiên p đ−ợc gán cho mỗi tiến trình 
là nghịch đảo của thời gian xử lý t mà tiến trình yêu cầu : p = 1/t. Khi CPU 
đ−ợc tự do, nó sẽ đ−ợc cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết 
thúc- tiến trình ngắn nhất. Giải thuật này cũng có thể độc quyền hay không 
độc quyền. Sự chọn lựa xảy ra khi có một tiến trình mới đ−ợc đ−a vào danh 
sách sẵn sàng trong khi một tiến trình khác đang xử lý. Tiến trình mới có thể 
sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) 
ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lý. Giải thuật SJF 
không độc quyền sẽ dừng hoạt động của tiến trình hiện hành, trong khi giải 
thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lý. 
Ví dụ : 
Tiến trình P1 P2 P3 P4 
Thời điểm xuất hiện (s) 0 2 3 5 
Thời gian thực hiện (s) 14 3 13 7 
Sử dụng thuật giải SJF độc quyền, thứ tự cấp phát CPU nh− sau: 
 P1 → P2 → P4 → P3 
Sử dụng thuật giải SJF không độc quyền, thứ tự cấp phát CPU nh− sau: 
P1 → P2 →P1 →P4→P3 
SJF không độc quyền còn đ−ợc gọi là SRN ( Shortest Remaining-time 
Next). 
 8
Thảo luận : Giải thuật này cho phép đạt đ−ợc thời gian chờ trung bình 
cực tiểu. Khó khăn thực sự của giải thuật SJF là không thể biết đ−ợc thời 
gian yêu cầu xử lý còn lại của tiến trình ? Chỉ có thể dự đoán giá trị này theo 
cách tiếp cận sau : gọi tn là độ dài của thời gian xử lý lần thứ n, t n+1 là giá 
trị dự đoán cho lần xử lý tiếp theo. Với hy vọng giá trị dự đoán sẽ gần giống 
với các giá trị tr−ớc đó, có thể sử dụng công thức: 
t n+1 = a tn + (1-a )t n 
Trong công thức này,tn chứa đựng thông tin gần nhất ; t n chứa đựng 
các thông tin quá khứ đ−ợc tích lũy. Tham số a ( 0 <= a <= 1) kiểm soát 
trọng số của hiện tại gần hay quá khứ ảnh h−ởng đến công thức dự đón. 
 IV.3.2. Chiến l−ợc phân phối xoay vòng (Round Robin) 
Nguyên tắc : Danh sách sẵn sàng đ−ợc xử lý nh− một danh sách vòng, 
bộ điều phối lần l−ợt cấp phát cho từng tiến trình trong danh sách một 
khoảng thời gian sử dụng CPU gọi là quantum. Đây là một giải thuật điều 
phối không độc quyền : khi một tiến trình sử dụng CPU đến hết thời gian 
quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp 
trong danh sách. Nếu tiến trình bị khóa hay kết thúc tr−ớc khi sử dụng hết 
thời gian quantum, hệ điều hành cũng lập tức cấp phát CPU cho tiến trình 
khác. Khi tiến trình dùng hết thời gian CPU dành cho nó mà ch−a hoàn tất, 
tiến trình đ−ợc đ−a trở lại vào cuối danh sách sẵn sàng để đợi đ−ợc cấp CPU 
trong l−ợt kế tiếp. 
 Ví dụ : 
Tiến trình Thời điểm vào Thời gian xử lý 
P1 0 24 
P2 1 3 
P3 2 3 
 9
 Nếu sử dụng quantum là 4 milisecondes, thứ tự cấp phát CPU sẽ là : 
P1 P2 P3 P1 P1 P1 P1 P1 
Thời gian chờ đợi trung bình sẽ là (0+6+3+5)/3 = 4.66 milisecondes. 
Nếu có n tiến trình trong danh sách sẵn sàng và sử dụng quantum q, thì 
mỗi tiến trình sẽ đ−ợc cấp phát CPU 1/n trong từng khoảng thời gian q. Mỗi 
tiến trình sẽ không phải đợi quá (n-1)q đơn vị thời gian tr−ớc khi nhận đ−ợc 
CPU cho l−ợt kế tiếp. 
Thảo luận : Vấn đề đáng quan tâm đối với giải thuật RR là độ dài của 
quantum. Nếu thời l−ợng quantum quá bé sẽ phát sinh quá nhiều sự chuyển 
đổi giữa các tiến trình và khiến cho việc sử dụng CPU kém hiệu qủa. Nh−ng 
nếu sử dụng quantum quá lớn sẽ làm tăng thời gian hồi đáp và giảm khả 
năng t−ơng tác của hệ thống. 
 10