Bài giảng Nguyên lí hệ điều hành - Chương II: Quản lý tiến trình

1 
Chương 2 – QUẢN LÝ TIẾN TRÌNH $1- TiẾN TRÌNH VÀ ĐiỀU ĐỘ TiẾN TRÌNH  
1.1 - Định nghĩa tiến trình: 
1.2 – Phân loại : kế tiếp và song song, 
Tiến trình song song: 
2 
Phân loại 
3 
Phân loại 
a) Độc lập: Bảo vệ thông tin, 
b)Quan hệ thông tin: 
Tiến trình nhận: Tồn tại? Ở đâu? Giai đoạn nào? 
Cơ chế truyền tin: 
Hòm thư, 
I/O Ports, 
Monitor/ 
4 
Phân loại 
c) Phân cấp : 
Tài nguyên cho tiến trình con: 
Hệ thống QL tài nguyên tập trung: từ hệ thống, 
Hệ thống QL tài nguyên phân tán: từ vốn tài nguyên tiến trình chính, 
QL phân tán: Tiến trình chính phải kết thúc sau tiến trình con  POST, WAIT. 
d) Đồng mức : 
Sử dụng chung theo nguyên tắc lần lượt, 
Các hệ thống mô phỏng, trò chơi, . . . 
5 
1.3 - BIỂU DIỄN TIẾN TRÌNH SONG SONG 
Giả thiết: S1, S2, . . ., Sn – các công việc thực hiện song song (Trên 1 hoặc nhiều máy). 
6 
BIỂU DIỄN 
2 cách mô tả phổ biến: 
PARBEGIN 	 COBEGIN 
	 S 1 ;	 S 1 ; 
	S 2 ; 	 S 2 ; 
. . . . . . . . . . . . . . 
	 S n 	 S n 
PAREND; 	 COEND; 
Các công việc S i được mô tả chính xác bằng một ngôn ngữ lập trình cụ thể. 
7 
1.4 – TÀI NGUYÊN GĂNG và ĐOẠN GĂNG 
Tài nguyên găng: Khả năng phục vụ đồng thời bị hạn chế, thông thường - bằng 1. 
Ví dụ: Máy in, quá trình bán vé máy bay . . . 
Đoạn găng (chổ hẹp) của tiến trình, 
Điều độ tiến trình qua đoạn găng: Tổ chức cho mọi tiến trình qua được chổ hẹp của mình. 
Giải thuật điều độ phải đảm bảo 4 yêu cầu. 
8 
Yêu cầu 
i) Đảm bảo tài nguyên găng không phải phục vụ quá khả năng của mình, 
ii) Không để tiến trình nằm vô hạn trong đoạn găng, 
iii) Nếu có xếp hàng chờ thì sớm hay muộn tiến trình cũng qua được đoạn găng, 
iv) Nếu có tiến trình chờ đợi và nếu tài nguyên găng được giải phóng, thì tài nguyên găng phải phục vụ ngay cho tiến trình đang chờ đợi. 
9 
Công cụ điều độ 
Công cụ điều độ: 2 loại: 
Cấp cao : do hệ thống đảm nhiệm, nằm ngoài tiến trình được điều độ, 
Cấp thấp : cài đặt ngay vào trong tiến trình được điều độ. 
Các giải thuật điều độ cấp thấp: 3 lớp giải thuật : 
Phương pháp khoá trong, 
Phương pháp kiểm tra và xác lập, 
Kỹ thuật đèn báo. 
10 
$2 – CÁC GIẢI THUẬT ĐIỀU ĐỘ 
2.1 Phương pháp khoá trong : 
Nguyên lý: 
Mỗi tiến trình (TT) đặt tương ứng tài nguyên găng với 1 biến G, 
TT dùng biến này để đánh dấu việc mình đang sử dụng tài nguyên găng, 
Trước khi vào đoạn găng TT phải kiểm tra biến tương ứng của các TT khác và chỉ vào đoạn găng khi không có TT nào đang sử dụng tài nguyên găng. 
11 
Phương pháp khoá trong 
Môi trường ví dụ : Xét trường hợp: 
2 tiến trình, 
Mỗi TT có một đoạn găng ở đầu, 
1 tài nguyên găng với khả năng phục vụ:1, 
Các tiến trình lặp vô hạn. 
Tránh nhầm lẫn giữa 2 khái niệm : 
Sơ đồ nguyên lý : nêu ý tưởng chung, 
Giải thuật điều độ : sơ đồ hành động để đảm bảo điều độ. 
12 
SƠ ĐỒ NGUYÊN LÝ 
Var c 
1 
, 
c 
2 
: 
Integer 
; 
BEGIN c 
1 
:= 
0 
; 
c 
2 
:= 
0 
; 
 PARBEGIN 
 TT 
1 
: 
Repeat 
TT 
2 
: 
Repeat 
 While c 
2 
0 
do 
; 
While c 
1 
0 
do 
; 
 c 
1 
:= 
1 
; 
c 
2 
:= 
1 
; 
 { 
Đoạn găng TT 
1 
} { 
Đoạn găng TT 
1 
} 
 c 
1 
:= 
0 
; 
c 
2 
:= 
0 
; 
 { 
Phần còn lại của TT 
1 
} { 
Phần còn lại của TT 
1 
} 
 Until false 
; 
Until false 
 PAREND 
 END 
. 
Có khả năng cả 
2 
TT cùng vào đoạn găng 
13 
SƠ ĐỒ NGUYÊN LÝ 
14 
SƠ ĐỒ NGUYÊN LÝ 
Nguyên nhân không đáp ứng yêu cầu điều đô: 
Kiểm tra và Xác lập – 2 công việc riêng biệt , 
Khoảng cách thời gian giữa 2 công việc, 
Giữa 2 công việc: Processor có thể bị chuyển sang công việc khác . 
1968: Dekker công bố giải thuật điều độ, kết nối Kiểm tra và Xác lập thành một khối. 
15 
Giải thuật Dekker 
16 
Giải thuật Dekker 
Đặc điểm: 
Không đòi hỏi công cụ đặc biệt  áp dụng được trong mọi môi trường (hệ thống và ngôn ngữ LT), 
Phức tạp, độ phức tạp tăng khi số tiến trình tăng, 
Tồn tại hiện tượng chờ đợi tích cực. 
Nguyên nhân: 
Không cục bộ hoá biến trong tiến trình, 
Mỗi TT phải tự Kiểm tra và xác lập. . 
17 
 2.2 KIỂM TRA VÀ XÁC LẬP (TEST and SET) 
Cơ sở: dùng lệnh máy TS có từ các máy tính thế hệ III trở đi. 
18 
TEST and SET 
IBM 360/370:  1 lệnh TS ( mã 92 H ), 
IBM PC: Nhóm lệnh BTS (Binary Test and Set): 
L:= 
G 
¬ G 
G 
¬ G 
G:= 
1 
0 
1 
0 
19 
TEST and SET 
Sơ đồ điều độ: 
20 
TEST and SET 
Đặc điểm: 
Đơn giản, độ phức tạp không tăng khi số tiến trình tăng. Nguyên nhân: Cục bộ hoá biến và tính liên tục của KT & XL, 
Tồn tại hiện tượng chờ đợi tích cực . Nguyên nhân: Mỗi TT phải tự đưa mình vào đoạn găng. 
21 
2.3 KỸ THUẬT ĐÈN BÁO 
Dijsktra đề xuất 1972. 
Đề xuất : 
Mỗi tài nguyên găng được đặt tương ứng với một biến nguyên đặc biệt S (Semaphore), 
Ban đầu: S ← Khả năng phục vụ t.ng. găng , 
 2 lệnh máy P(S) và V(S) thay đổi giá tri của S, mỗi lệnh làm 2 công việc và làm một cách liên tục . 
22 
KỸ THUẬT ĐÈN BÁO 
Nội dung lệnh P(S): 
	* Dec(s); 
	** If S < 0 then Đưa TT đi xếp hàng . 
Nội dung lệnh V(S):	 
	* Inc(s); 
	** If S 0 then Kích hoạt TT đang xếp hàng . 
23 
KỸ THUẬT ĐÈN BÁO 
Thực hiện: 
Vì nhiều lý do, không thể chế tạo MT với 2 lệnh trên, 
Lệnh P(S), V(S)  thủ tục tương ứng. 
Đảm bảo tính liên tục: 
24 
KỸ THUẬT ĐÈN BÁO 
Sơ đồ điều độ: 
25 
Semaphore nhị phân : 
Phần lớn các tài nguyên găng có khả năng phục vụ = 1  S nhị phân. 
P(S): 
 If s = 0 then Xếp_hàng Else s := 0; 
V(S): 
 If dòng_xếp_hàng NULL then K ích_hoạt 
 Else s := 1; 
Vấn đề đặt tên các thủ tục P và V. 
KỸ THUẬT ĐÈN BÁO 
26 
2.4 – CÔNG CỤ ĐIỀU ĐỘ CẤP CAO 
Đoạn găng quy ước, 
Biến điều kiện quy ước, 
Monitor hỗ trợ điều độ: cung cấp giá trị cho biến điều kiện quy ước. 
Monitor đóng vai trò vỏ bọc bảo vệ ngăn cách giữa tài nguyên găng và công cụ truy nhập tới nó. 
27 
$3 - BẾ TẮC và CHỐNG BẾ TẮC 
Khái niệm bế tắc ( Deadlock ): 
Cùng chờ đợi, 
Vô hạn nếu không có tác động từ bên ngoài. 
Sẽ không có bế tắc nếu TT A bắt đầu đủ sớm hay đủ muộn. 
28 
BẾ TẮC và CHỐNG BẾ TẮC 
3.1 Điều kiện xuất hiện bế tắc: hội đủ đồng thời 4 điều kiện: 
 tài nguyên găng, 
Có sự xếp hàng chờ đợi, 
Không phân phối lại tài nguyên, 
 hiện tượng chờ đợi vòng tròn. 
3.2 Chống bế tắc : 3 lớp giải thuật 
Phòng ngừa, 
Dự báo và tránh, 
Nhận biết và khắc phục. 
29 
Phòng ngừa 
Điều kiện áp dụng: 
Xác xuất xuất hiện bế tắc lớn, 
Các biện phápTổn thất lớn. 
Biện pháp: tác động lên một hoặc một số điều kiện gây bế tắc để 4 điều kiện không xuất hiện đồng thời. 
Các giải pháp: được áp dụng để nâng cao hiệu quả của hệ thống. 
30 
Phòng ngừa 
Chống tài nguyên găng: 
Bố sung TN vật lí 
Tổ chức hệ thống tài nguyên lô gíc , 
2 mức truy nhập, 
SPOOL. 
Chống xếp hàng chờ đợi: 
Chế độ phân phối sơ bộ, 
Trước khi ngắt TT: lưu trạng thái (Dump), 
Công cụ: 
Điểm gác (Control Points), 
Điểm ngắt (Break Points) 
31 
Phòng ngừa 
Đặt điểm gác: 
Cố định trong CT, 
Theo tác nhân ngoài 
(vd: thời gian) 
Ứng dụng: 
Hiệu chỉnh CT, 
Thực hiện các CT dài, 
Với toàn bộ hệ thống: Hibernating. 
32 
Phòng ngừa 
Phân phối lại tài nguyên: 
Các tài nguyên quan trọng (Bộ nhớ, Processor . . .) luôn luôn được phân phối lại, 
Chủ yếu: chỉ cần lưu ý các tài nguyên riêng, 
Hệ thống tài nguyên lô gíc: giảm nhu cầu phân phối lại. 
Để phân phối lại: Lưu và khôi phục trạng thái tài nguyên. 
33 
Phòng ngừa 
Chống chờ đợi vòng tròn: 
Phân lớp tài nguyên, tạo thành hệ thống phân cấp, 
Nguyên tắc phân phối: Khi chuyển lớp - phải giải phóng tài nguyên lớp cũ. 
34 
DỰ BÁO VÀ TRÁNH 
Điều kiện môi trường: 
Xác xuất xẩy ra bế tắc nhỏ, 
Tổn thất (nếu có bế tắc) – lớn. 
Mỗi lần phân phối một tài nguyên: kiểm tra xem việc phân phối này có thể dẫn đến nguy cơ bế tắc cho một số tiến trình nào đó hay không và là những tiến trình nào ? 
35 
DỰ BÁO VÀ TRÁNH 
Giải thuật tiêu biểu: “ Người chủ ngân hàng ”. 
Giả thiết: 
Xét 1 loại tài nguyên, số lượng  tstb, 
n tiến trình, 
Max i , 
Ffoi i , 
Kt i – boolean, 
True – chắc chắn kết thúc được, 
False – trong trường hợp ngược lại. 
36 
DỰ BÁO VÀ TRÁNH 
37 
DỰ BÁO VÀ TRÁNH 
Tiêu chuẩn dự báo: ngặt, 
Dựa vào Kt i  biết các TT có nguy cơ bế tắc, 
Xử lý trước khi TT bị bế tắc. 
Đặc điểm giải thuật: 
Đơn giản, 
Input: Max i – tin cậy, 
Mỗi loại tài nguyên thủ tục, 
Mỗi lần phân phối  kiểm tra. 
38 
NHẬN BIẾT VÀ KHẮC PHỤC 
Điều kiện áp dụng: 
Xác xuất xẩy ra bế tắc bé, 
Tổn thất (nếu có bế tắc) – bé. 
Định kỳ kiểm tra các TT chờ đợi để phát hiện bế tắc, 
Áp dụng với phần lớn OS trong thực tế, 
Do OP đảm nhiệm. 
39 
NHẬN BIẾT VÀ KHẮC PHỤC 
Lệnh OP  các nhóm lệnh phục vụ nhận biết và khắc phục, 
Nhóm lệnh xem trạng thái (Display Status), 
Nhóm lệnh tác động lên dòng xếp hàng TT, 
Nhóm lệnh tác động lên TT, 
Quan trọng: các lệnh huỷ tiến trình, 
Các biện pháp hỗ trợ và ngăn chặn tự động. 
40 
$4 – QUẢN LÝ PROCESSOR 
Mục đích: Giảm thời gian chết của Processor  nâng cao hiệu quả hệ thống , 
Vai trò thiết bị trung tâm: liên kết các bộ phận đọc lập (cứng và mềm) thành hệ thống hoạt động đồng bộ. 
Trong phần này: xét hoạt động của 1 CPU. 
41 
4.1 – PROCESSOR LÔ GÍC 
42 
 CÁC TRẠNG THÁI CƠ BẢN CỦA TIẾN TRÌNH 
Đặc trưng các loại trạng thái, 
Vấn đề cần giải quyết: 3 loại. 
43 
4 .2 VẤN ĐỀ LẬP LỊCH 
44 
VẤN ĐỀ 
a) Liên quan tới dòng TT sẵn sàng: Cách tổ chức phục vụ dòng xếp hàng? 
45 
VẤN ĐỀ 
Trình tự phục vụ tác động lên thời gian chờ đợi trung bình t w : giả thiết – 3 TT : 
46 
VẤN ĐỀ 
Thời gian thực hiện tiến trình: 
Không đẩy ra (Non-preemptive), 
(Xử lý theo lô) 
Có đẩy ra (Preemptive) 
(Phân chia thời gian) 
Lượng tử thời gian: 0.03”  0.2”. 
47 
VẤN ĐỀ 
c) Thời điểm đưa TT chờ đợi trở lại sẵn sàng? Cơ chế sự kiện và ngắt . 
48 
4.3 - ĐIỀU ĐỘ THỰC HIỆN TT 
TT th ứ tự ưu tiên phục vụ, 
Yêu cầu: 
t w  min. 
TT kết thúc . 
Chế độ: 
Một dòng xếp hàng, 
Nhiều dòng xếp hàng. 
49 
Chế độ một dòng xếp hàng 
a) FCFS (First come – First served ): 
+ Tổ chức: 
Ưu tiên ngoài 
Ưu tiên xếp hàng 
Phục vụ 
+ Đánh giá: 
Đơn giản, 
 TT kết thúc được, 
Không cần input bổ sung, 
Tw – lớn, 
Non-Preemtipve. 
50 
Chế độ một dòng xếp hàng 
b) SJN (Shortest Job – Next): 
Thời gian thực hiện ít  ưu tiên cao, 
T w giảm, 
TT dài có nguy cơ không kết thúc được, 
Khó dự báo thời điểm phục vụ TT, 
Non-Preemtipve, 
Input: Thời gian thực hiện TT. 
51 
Chế độ một dòng xếp hàng 
c) SRT (Shortest Remaining Time): 
Thứ tự ưu tiên phục vụ: xác định theo lượng thời gian còn lại cần thiết để kết thúc TT, 
t w giảm mạnh, 
Các đặc trưng khác: tương tự như SJN, 
TT dài càng có nguy cơ không kết thúc được! 
Ở các chế độ Non-Preemtipve: cần có t lim  huỹ TT hoặc đưa về thứ tự ưu tiên thấp nhất. 
52 
Chế độ một dòng xếp hàng 
d) RR (Round Robin): 
Preemtipve, 
 TT - kết thúc đươc, 
Khả năng đối thoại với TT, 
Ưu tiên thích đáng với TT dài: phân lớp phục vụ với t lớn hơn. 
53 
Chế độ nhiều dòng xếp hàng 
54 
$5 - GỌI TIẾN TRÌNH 
TT có thể cạnh tranh hoặc tương tác với nhau, 
Mối quan hệ tương tác: tuần tự hoặc song song, 
Xác lập quan hệ: 
Lời gọi, 
Cơ chế xử lý sự kiện (Sẽ xét ở chương sau), 
Các cách gọi: 
Trong phạm vi một hệ thống, 
Giữa các hệ thống: 
RI (Remote Invocation), 
RPC (Remote Procedure Call), 
Lý thuyết chung: RMI (Remote Methods Invocation) 
55 
GỌI TIẾN TRÌNH 
Sơ đồ gọi: 
Không đối xứng, 
Đối xứng. 
Kỹ thuật truyền tham số: 
Theo giá trị, 
Theo địa chỉ, 
CR (Call by Copy/Restore). 
56 
GỌI TIẾN TRÌNH 
Thông tin tối thiểu để lưu và khôi phục TT: 
Nội dung các thanh ghi, 
Địa chỉ lệnh, 
Vùng bộ nhớ RAM liên quan, 
Vùng bộ nhớ phục vụ của hệ thống, 
Các sự kiện chưa xử lý. 
Phân biệt sơ đồ gọi đối xứng và đệ quy. 
57 
$6 - NGẮT và XỬ LÝ NGẮT 
6.1 Định nghĩa ngắt (Interrupt): 
Cơ chế Sự kiện và Ngắt : từ MT thế hệ III, 
IBM 360/370 – 7 loại sự kiện, 
IBM PC – 256 loại sự kiện. 
58 
6.2 PHÂN LOẠI NGẮT 
Ngắt trong và ngắt ngoài, 
Ngắt trong: /0, tràn ô, . . . 
Ngắt ngoài: I/O Int, Timer, . . . 
Ngắt chắn được và không chắn được: 
Chắn được: i/o Int, 
Không chắc được: Timer Int. 
Ngắt cứng và ngắt mềm. 
59 
6.3 XỬ LÝ NGẮT 
60 
CT con và CT xử lý ngắt 
61 
6.4 - Xử lý ngắt trong IBM PC 
Ngắt Pointer (4 bytes), 
Véc tơ ngắt = {Pointers} (1 KB), 
Khối bộ nhớ xử lý ngắt, 
Nét đặc biệt: 
 các ngắt | Pointer  Bảng tham số (Int 11, 1E, 41, . . .), 
Ngắt KT CT – Int 20, Ngắt thường trú CT Int 27, 
Ngắt R/W đĩa theo địa chỉ tuyệt đối – Int 25, 26, 
 ngắt tương ứng với việc bấm phím (Int 05, 1B), 
Ngăt OS mô phỏng xử lý các sự kiện (Int 21), 
Một số sự kiện: dành cho user tạo ngắt mềm  Lập trình hướng sự kiện (EOP).