Bài giảng Hệ điều hành - Chương 2: Quản lý tiến trình - Huỳnh Triệu Vỹ

CHƯƠNG II:QUẢN LÝ TIẾN TRÌNH 
ThS. Huỳnh Triệu Vỹ 
1. TỔNG QUAN VỀ TiẾN TRÌNH 
1.1 Tiến trình(process)? 
Tiến trình là một chương trình đang được thực thi, được sở hữu 1 con trỏ lệnh, tập các thanh ghi và các biến 
Để hoàn thành tác vụ của mình, một tiến trình có thể cần đến một số tài nguyên như CPU, bộ nhớ chính, các tập tin và thiết bị nhập/xuất. 
1.1 Tiến trình(process)?(tt) 
Tiến trình bao gồm 3 thành phần: Code, Data, Stack 
Code: Thành phần câu lệnh thực hiện 
Data: Thành phần dữ liệu 
Stack: Thành phần lưu thông tin tạm thời 
Các câu lệnh trong code chỉ dùng data và stack riêng của mình ngoại trừ các vùng dùng chung 
Tiến trình được hệ thống phân biệt bằng số hiệu pid (proccess identification) 
1.2 Các trạng thái của tiến trình 
Trạng thái của tiến trình tại mỗi thời điểm được xác định bởi hoạt động hiện thời của nó: 
New: tiến trình được tạo lập 
Ready: tiến trình đã sẵn sàng , đang chờ cấp CPU 
Running: tiến trình đang được xử lý 
Waiting: tiến trình tạm dừng và chờ vì thiếu tài nguyên hay chờ 1 sự kiện nào đó 
Halt: Tiến trình hoàn tất (Halt-> ngăn chặn,dừng,tạm dừng,ngưng....) 
Mô tả chuyển trạng thái của tiến trình 
New 
Ready 
Running 
Halt 
Waiting 
(1) 
(2) 
(3) 
(4) 
(5) 
(6) 
1.2 Các trạng thái của tiến trình(tt) 
Tại một thời điểm chỉ có 1 tiến trình ở trạng thái Running trên 1 bộ xử lý bất kỳ và có thể có nhiều tiến trình ở trạng thái Ready và Waiting 
1.3 Chế độ xử lý của tiến trình 
Chế độ xử lý được chia thành 2 chế độ nhờ sự hỗ trợ của phần cứng: Đặc quyền và không đặc quyền 
Tiến trình của HĐH cần được bảo vệ khỏi sự xâm phạm của tiến trình khác 
Tiến trình của HĐH hoạt động trong chế độ đặc quyền và của người sử dụng hoạt động trong chế độ không đặc quyền 
1.3 Chế độ xử lý của tiến trình(tt) 
Tập lệnh của CPU được chia thành 2 tập 
OS (HĐH) 
Hardware 
Shell, editor 
users 
Chế độ không đặc quyền 
Chế độ đặc quyền 
1.4 Các thao tác điều khển tiến trình 
a. Khởi tạo tiến trình 
HĐH gán PID (bộ điều khiển vi tích phân tỉ lệ (bộ điều khiển PID- Proportional Integral Derivative))   và đưa vào danh sách quản lý của hệ thống 
Cấp phát không gian bộ nhớ 
Khởi tạo các thông tin cần thiết cho khối điều khiển tiến trình: Các PID của p cha (nếu có), thông tin trạng thái, độ ưu tiên, ngữ cảnh của processor (bộ vi xử lý) 
Cung cấp đầy đủ các tài nguyên (trừ processor) 
Đưa tiến trình vào danh sách P nào đó: ready list (DS sẵn sàng), waiting list (danh sách chờ) 
1.4. Các thao tác điều khển tiến trình 
b. Kết thúc tiến trình: HĐH thực hiện các thao tác: 
Thu hồi tài nguyên đã cấp phát cho p 
Loại bỏ tiến trình ra khỏi danh sách quản lý của hệ thống 
Hủy bỏ khối điều khiển p 
1.4. Các thao tác điều khển tiến trình 
c. Thay đổi trạng thái của P, HĐH thực hiện: 
Lưu ngữ cảnh của Processor 
Cập nhật PCB (process control block (block=khóa,chặn) ) của tiến trình sao cho phù hợp với trạng thái của P 
Di chuyển PCB của p đến 1 hàng đợi thích hợp 
Chọn tiến trình khác để cho phép nó thực hiện 
Cập nhật PCB của p vừa thực hiện 
Cập nhật thông tin liên quan đến quản lý bộ nhớ 
Khôi phục lại ngữ cảnh của processor 
1.5 Khối điều khiển tiến trình(process control block -PCB). 
Quản lý mọi hoạt động của tiến trình 
Cấu trúc dữ liệu của khối điều khiển bao gồm: 
Định danh tiến trình 
Trạng thái của tiến trình 
Ngữ cảnh của tiến trình 
Thông tin giao tiếp 
Thông tin thống kê 
status 
pid 
Waiting/waiting list 
CPU-state-rec 
Processor 
Main store 
Resource (nguồn) 
Created recource 
Parent (cha mẹ,phụ huynh) 
Progeny (con cháu) 
Priority (ưu tiên) 
CPU time 
Unit 1 
Unit 2 
RCB 1 
RCB 2 
RCB 1 
RCB 2 
PCB 
PCB 1 
PCB 2 
Ngữ cảnh của ttrình 
Thông tin giao tiếp 
Thông tin thống kê 
Trạng thái ttrình 
Định danh ttrình 
1.6 Tiểu trình 
Thông thường mỗi tiến trình có 1 không gian địa chỉ và 1 dòng xử lý 
Mong muốn có nhiều dòng xử lý cùng chia sẻ 1 không gian địa chỉ và các dòng xử lý hoạt động song song như các tiến trình độc lập 
Xuất hiện HĐH có cơ chế thực thi mới gọi là tiểu trình 
Như vậy, tiểu trình là: 
1 đơn vị xử lý cơ bản 
Sở hữu 1 con trỏ lệnh, tập các thanh ghi, 1 vùng nhớ stack riêng 
Có các trạng thái như tiến trình thật. 
2. TÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 
2.1 Tài nguyên găng(Critical Resource) 
Tài nguyên găng? 
Những tài nguyên được HĐH chia sẻ cho nhiều tiến trình hoạt động đồng thời dùng chung mà có nguy cơ tranh chấp giữa các tiến trình này khi sử dụng chúng 
Tài nguyên găng có thể là tài nguyên phần cứng hoặc phần mềm, có thể là tài nguyên phân chia được hoặc không phân chia được 
2.1 Tài nguyên găng(Critical Resource) 
Ví dụ: bài toán rút tiền ngân hàng từ tài khoản dùng chung 
If (tài khoản – tiền rút >=0) 
	tài khoản:=tài khoản – tiền rút 
Else 
	Thông báo lỗi 
endif 
2.2 Đoạn găng(Critical Section) 
Các đoạn code trong các chương trình dùng để truy cập đến tài nguyên găng được gọi là đoạn găng 
Để hạn chế lỗi có thể xảy ra do sử dụng tài nguyên găng, tại 1 thời điểm HĐH chỉ cho 1 tiến trình nằm trong đoạn găng 
HĐH có cơ chế điều độ tiến trình qua đoạn găng 
2.3 Yêu cầu của công tác điều độ tiến trình qua đoạn găng 
Tại 1 thời điểm chỉ cho phép 1 tiến trình nằm trong đoạn găng, các tiến trình khác có nhu cầu vào đoạn găng phải chờ 
Tiến trình chờ ngoài đoạn găng không được ngăn cản các tiến trình khác vào đoạn găng 
Không có tiến trình nào phải chờ lâu để được vào đoạn găng 
Đánh thức các tiến trình trong hàng đợi để tạo điều kiện cho nó vào đoạn găng khi tài nguyên găng được giải phóng 
2.4 Điều độ tiến trình qua đoạn găng 
a. Giải pháp phần cứng 
Dùng cặp chỉ thị STI(setting interrupt (ngắt,gián đoạn) ) và CLI (clean interrupt) 
Ví dụ: 
Procedure P(i: integer) 
	begin 
	repeat 
	CLI; 
	; 
	STI; 
	; 
	until .F. 
	end; 
Dùng chỉ thị TSL(Test and set) 
Function TestAndSetLock(Var i:integer):boolean 
Begin 
	if i=0 then 
	begin 
	i:=1; 
	TestAndSetLock:=true 
	end; 
	else 
	TestAndSetLock:=false 
End; 
Procedure P(lock: integer); 
	begin 
	repeat 
	while 	(TestAnhSetLock(lock)) do; 
	; 
	lock:=0 
	; 
	until .F. 
	end; 
b. Giải pháp dùng biến khóa 
Dùng biến khóa chung 
Procedure P(lock: integer); 
	begin 
	repeat 
	while 	lock=1 do; 
	Lock=1 
	; 
	lock:=0 
	; 
	until .F. 
	end; 
Dùng biến khóa riêng 
Var lock1, lock2: byte; 
begin 
lock1:=0; lock2:=1 
	p1: repeat 
	while 	lock2=1 do; 
	Lock1:=1 
	; 
	lock1:=0 
	; 
	 until .F. 
	p2: repeat 
	while 	lock1=1 do; 
	Lock2:=1 
	; 
	lock2:=0 
	; 
	 until .F. 
end 
C. Giải pháp được hỗ trợ bởi HĐH và ngôn ngữ lập trình 
Dùng Semaphore(đèn báo) 
Semaphore S là 1 biến nguyên, khởi gán bằng 1 giá trị không âm, là khả năng phục vụ của tài nguyên găng tương ứng với nó 
Ứng với S có 1 hàng đợi F(s) lưu các tiến trình đang chờ trên S 
Thao tác Down giảm S 1 đơn vị, Up tăng S 1 đơn vị 
Mỗi tiến trình trước khi vào đoạn găng cần gọi Down để giảm S và kiểm tra nếu S>=0 thì được vào đoạn găng 
Mỗi tiến trình khi ra khỏi đoạn găng phải gọi Up để tăng S lên 1 đơn vị và ktra nếu S <=0 thì đưa 1 tiến trình trong F(s) vào đoạn găng 
Procedure Down(S); 
Begin 
	S:=S-1; 
If s<0 then 
Begin 
	Status(p)=waiting; 
	Enter(p,F(s)); 
end 
End; 
Procedure Up(S); 
Begin 
	S:=S+1; 
If s<=0 then 
Begin 
	Exit(Q,F(S)); 
	Status(Q)=ready; 
	Enter(Q,ready-list); 
end 
End; 
3. TẮC NGHẼN VÀ CHỐNG TẮC NGHẼN 
3.1 Tắc nghẽn 
Sự xung đột về tài nguyên của các tiến trình hoạt động đồng thời trong hệ thống 
Tắc nghẽn thường xảy ra với xung đột tài nguyên không phân chia được, ít xảy ra với tài nguyên phân chia được 
3.2 Điều kiện hình thành tắc nghẽn 
Sử dụng tài nguyên không thể chia sẻ 
Chiếm giữ và yêu cầu tài nguyên 
Không thu hồi tài nguyên từ tiến trình đang chiếm giữ chúng 
Đợi vòng tròn 
3.3 Các mức phòng tránh tắc nghẽn 
Ngăn ngừa 
Dự báo và tránh tắc nghẽn 
Nhận biết và khắc phục 
4. ĐIỀU PHỐI TIẾN TRÌNH 
4.1 Mục tiêu điều phối 
Sự công bằng 
Tính hiệu quả 
Thời gian đáp ứng hợp lý 
Thời gian lưu lại trong hệ thống 
Thông lượng tối đa 
4.2 Cơ chế điều phối 
Độc quyền: Tiến trình toàn quyền sử dụng processor cho đến khi kết thúc hoặc tự động trả lại 
Quyết định điều phối khi tiến trình chuyển từ Running sang Waiting (blocked) hoặc kết thúc 
Không độc quyền: Tiến trình đang xử lý thì bị thu hồi processor để cấp cho tiến trình khác 
Quyết định điều phối khi tiến trình chuyển từ Running sang Waiting (blocked) hoặc ready hoặc kết thúc hoặc từ Waiting sang ready 
4.3 Các đặc điểm của tiến trình 
Tính hướng xuất nhập 
Tính hướng xử lý 
Tương tác hay xử lý theo lô 
Độ ưu tiên của tiến trình 
Thời gian sử dụng CPU 
Thời gian còn lại để tiến trình hoàn tất 
4.4 Tổ chức điều phối 
HĐH sử dụng 2 loại danh sách để tổ chức lưu trữ các tiến trình: 
Danh sách Ready: Chỉ tồn tại 1 danh sách này 
Danh sách Waiting: Có thể tồn tại nhiều danh sách này 
4.5 Các chiến lược điều phối 
Chiến lược FIFO: Tiến trình nào được đưa vào danh sách ready trước sẽ được cấp Processor trước 
Ví dụ 
Tiến trình 
Thời điểm vào 
t/g xử lý 
P1 
0 
24 
P2 
1 
3 
P3 
2 
3 
Thời điểm cấp processor 
P1 
P2 
P3 
0 
24 
27 
Thời gian chờ: 
P1: 0 
P2: 23 
P3: 25 
4.5 Các chiến lược điều phối 
Chiến lược phân phối xoay vòng: 
Tiến trình nào vào danh sách Ready trước được cấp processor trước 
Mỗi tiến trình chỉ được sử dụng processor trong 1 khoản thời gian bằng nhau được gọi là Quantum 
Ví dụ 
Tiến trình 
Thời điểm vào 
t/g xử lý 
P1 
0 
24 
P2 
1 
3 
P3 
2 
3 
Quantum=4 
Tiến trình 
P1 
P2 
P3 
P1 
P1 
P1 
P1 
Thời điểm 
0 
4 
7 
10 
14 
18 
22 
4.5 Các chiến lược điều phối 
Chiến lược theo độ ưu tiên: 
Mỗi tiến trình được gán cho một độ ưu tiên tương ứng, tiến trình có độ ưu tiên cao nhất sẽ được chọn để cấp phát CPU đầu tiên 
Độ ưu tiên của tiến trình do HĐH gán và có thể bị thay đổi 
Giải thuật điều phối với độ ưu tiên có thể theo nguyên tắc độc quyền hay không độc quyền 
Điều phối với độ ưu tiên và không độc quyền sẽ thu hồi processor từ tiến trình hiện hành để cấp cho tiến trình mới nếu độ ưu tiên của tiến trình này cao hơn 
Điều phối với độ ưu tiên và độc quyền sẽ chỉ chèn tiến trình mới vào danh sách sẵn sàng tại vị trí phù hợp 
4.5 Các chiến lược điều phối 
Tiến trình 
Độ ưu tiên 
t/g xử lý 
P1 
3 
24 
P2 
2 
3 
P3 
1 
3 
Thời điểm cấp processor 
P1 
P2 
P3 
0 
24 
27 
Nhược điểm: Tiến trình có độ ưu tiên thấp dễ rơi vào trạng thái chờ vô hạn 
=>Cần giảm độ ưu tiên của tiến trình sau mỗi lần được cấp processor 
Ví dụ 
4.5 Các chiến lược điều phối 
Chiến lược công việc ngắn nhất (shortest job first - SJF): 
Đâ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 
độ ư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 
CPU được 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 
Giải thuật này cũng có thể độc quyền hoặc không độc quyền 
4.5 Các chiến lược điều phối 
Chiến lược nhiều cấp độ ưu tiên 
Phân lớp các tiến trình tùy theo độ ưu tiên của chúng để có cách thức điều phối thích hợp cho từng nhóm 
Mỗi danh sách bao gồm các tiến trình có cùng độ ưu tiên và được áp dụng một giải thuật điều phối thích hợp để điều phối 
Ngoài ra, còn có một giải thuật điều phối giữa các nhóm, thường giải thuật này là giải thuật không độc quyền và sử dụng độ ưu tiên cố định 
Một tiến trình thuộc về danh sách ở cấp ưu tiên i sẽ chỉ được cấp phát CPU khi các danh sách ở cấp ưu tiên lớn hơn i đã trống