Bài giảng Hệ điều hành - Chương 6: Deadlocks

 đòi
hỏi tối đa của các quá trình.
Đòi hỏi hệ thống phải có thông tin tiên quyết.
7.18 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
TRẠNG THÁI AN TOÀN
„ Khi một quá trình yêu cầu một tài nguyên sẵn có, hệ thống phải
xác định nếu cấp phát ngay, hệ thống vẫn trong trạng thái an 
toàn.
„ Hệ thống trong trạng thái an toàn nếu tồn tại một dãy <P1, P2, …, 
Pn> của TẤT CẢ các quá trình trong hệ thống sao cho đối với
mỗi Pi, tất cả các tài nguyên mà Pi cần được thỏa mãn bởi các
tài nguyên nó hiện có + các tài nguyên bị chiếm giữ bởi các Pj, 
với j < i.
„ Đó là: 
z Nếu tài nguyên mà Pi cần chưa có sẵn, Pi có thể chờ đến khi
tất cả các Pj (j <i) hoàn tất
z Khi Pj hoàn tất, Pi có thể nhận được các tài nguyên cần thiết, 
thực hiện, trả lại các tài nguyên được cấp phát và kết thúc. 
z Khi Pi kết thúc, Pi +1 nhận được các tài nguyên cần thiết và
cứ như vậy... 
7.19 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
SỰ KIỆN CƠ SỞ
„ Nếu hệ thống trong trạng thái an toàn⇒ không có
deadlocks.
„ Nếu hệ thống không trong trạng thái an toàn⇒ có thể có
deadlock.
„ Tránh⇒ đảm bảo hệ thống không bao giờ rơi vào trạng
thái không an toàn. 
7.20 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
TRẠNG THÁI AN TOÀN, KHÔNG AN TOÀN & 
Deadlock 
7.21 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
THUẬT TOÁN TRÁNH DEADLOCK
„ Mỗi kiểu tài nguyên có đúng một thể hiện. Sử dụng đồ thị
cấp phát tài nguyên.
„ Mỗi kiểu tài nguyên có một vài thể hiện. Sử dụng thuật toán
banker
7.22 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
SƠ ĐỒ ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN
„ Cung Claim (Claim edge) Pi→ Rj chỉ ra rằng Pj có thể yêu
cầu tài nguyên Rj ; được biểu diễn bởi đường đứt quãng.
„ Cung Claim được chuyển thành cung Request khi quá trình
yêu cầu tài nguyên.
„ Cung Request được chuyển thành cung Assignment khi tài
nguyên được cấp cho quá trình.
„ Khi tài nguyên được giải phóng, cung Assignment được
chuyển thành cung Claim.
„ Các tài nguyên phải được khai báo trước.
7.23 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN
7.24 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
TRẠNG THÁI KHÔNG AN TOÀN TRONG ĐỒ THỊ
CẤP PHÁT TÀI NGUYÊN
7.25 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
THUẬT TOÁN ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN
„ Giả sử quá trình Pi yêu cầu một tài nguyên Rj
„ Yêu cầu có thể được cấp chỉ nếu việc chuyển cung
Request thành cung Assignment không gây ra chu
trình trong đồ thị cấp phát tài nguyên
7.26 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
THUẬT TOÁN Banker
„ Đa thể hiện
„ Mỗi quá trình phải khai báo số tố đa các thể hiện của mỗi
kiểu tài nguyên cần thiết.
„ Khi quá trình yêu cầu một tài nguyên, có thể nó phải chờ. 
„ Khi quá trình nhận được tất cả các tài nguyên cần thiết nó
phải trả lại chúng sau một khoảng thời gian hữu hạn.
7.27 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
CẤU TRÚC DỮ LIỆU CHO THUẬT TOÁN 
Banker’s
„ Available: Vector độ dài m. available [j] = k, có nghĩa là có
sẵn k thể hiện của kiểu tài nguyên Rj .
„ Max: ma trận n x m. Max [i,j] = k, có nghĩa là quá trình Pi
có thể yêu cầu nhiều nhất k thể hiện của kiểu tài nguyên Rj.
„ Allocation: ma trận n x m. Allocation[i,j] = k có nghĩa là Pi
hiện được cấp phát k thể hiện của Rj.
„ Need: ma trận n x m. Need[i,j] = k có nghĩa là Pi có thể cần
thêm k thể hiện nữa của Rj
Need [i,j] = Max[i,j] – Allocation [i,j].
n = số quá trình, m = số các kiểu tài nguyên
7.28 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
THUẬT TOÁN AN TOÀN
1. Work và Finish là các vectors độ dài m và n, tương ứng. 
Khởi động:
Work = Available
Finish [i] = false for i = 0, 1, …, n- 1.
2. Tìm i sao cho hai điều kiện sau thỏa mãn: 
(a) Finish [i] = false
(b) Needi ≤Work
Nếu không tìm thấy, go to 4.
3. Work = Work + Allocationi
Finish[i] = true
go to 2.
4. Nếu Finish [i] == true với mọi i, hệ thông trong trạng thái an toàn.
7.29 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
THUẬT TOÁN YÊU CẦU TÀI NGUYÊN ĐỐI VỚI 
QUÁ TRÌNH Pi
Request = vector Request đối với quá trình Pi. Nếu Requesti [j] 
= k có nghĩa Pi muốn k thể hiện của kiểu tài nguyên Rj.
1. Nếu Requesti ≤ Needi go to 2. Nếu không thông báo lỗi
“tiêu thụ tài nguyên vượt quá khai báo”.
2. Nếu Requesti ≤ Available, go to 3. Nếu không Pi phải chờ, 
(tài nguyên không có sẵn).
3. Giả định cấp phát các tài nguyên được yêu cầu cho Pi bằng
cách sủa đổi trạng thái như sau:
Available = Available – Request;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
z Nếu trạng thái mới là an toàn⇒ Cấp phát tài nguyên
cho Pi. 
z Nếu trạng thái mới không an toàn⇒ Pi phải chờ, trạng
thái cấp phát tài nguyên cũ được phục hồi
7.30 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
VÍ DỤ THUẬT TOÁN Banker
„ 5 quá trình P0, P1, P2, P3, và P4
3 Kiểu tài nguyên:
A (10 thể hiện), B (5 thể hiện), và C (7 thể hiện).
„ Tức cảnh tại thời điểm T0:
Allocation Max Available
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2 
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3 
7.31 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
VD. (Cont.)
„ Ma trận Need = Max – Allocation.
Need
A B C
P0 7 4 3 
P1 1 2 2 
P2 6 0 0 
P3 0 1 1
P4 4 3 1 
„ Thuật toán an toàn cho ra dãy an toàn , như vậy
hệ thống trong trạng thái an toàn. 
7.32 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
VD : P1 YÊU CẦU (1,0,2)
„ Kiểm tra Request1 ≤ Need1 ((1,0,2) ≤ (1, 2, 2) ⇒ true )
„ Kiểm tra Request1 ≤ Available ( (1,0,2) ≤ (3,3,2) ⇒ true ).
„ Giả định cấp phát theo yêu cầu của P0
Allocation Need Available
A B C A B C A B C 
P0 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0 
P2 3 0 1 6 0 0 
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1 
„ Chạy thuật toán an toàn, tìm được dãy an toàn ; 
như vậy có thể cấp theo yêu cầu của P0. 
„ Yêu cầu (3,3,0) bởi P4 được cấp?
„ Yêu cầu (0,2,0) bời P0 được cấp?
7.33 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
PHÁT HIỆN DEADLOCKS
„ Cho phép hệ thống rơi vào trạng thái deadlock
„ Thuật toán phát hiện deadlock
„ Sơ đồ phục hồi
7.34 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
MỖI KIỂU TÀI NGUYÊN CHỈ CÓ MỘT THỂ HIỆN
„ Duy trì đồ thị chờ
z Nodes là các quá trình.
z Pi→ Pj nếu Pi chờ Pj.
„ Theo chu kỳ gọi thuật toán tìm kiếm chu trình trong đồ thị. 
có chu trình ⇔ có deadlock.
„ Thuật toán phát hiện chu trình trong một đồ thị có độ phức
tạp thời gian O(n2) , n = số đỉnh của đồ thị.
7.35 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN & ĐỒ THỊ CHỜ
Đồ thị cấp phát tài nguyên Đồ thị chờ tương ứng
7.36 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
MỖI KIỂU TÀI NGUYÊN CÓ MỘT VÀI THỂ HIỆN
„ Available: vector độ dài m, available[j]=k : kiểu tài nguyên Rj
còn k thể hiện.
„ Allocation: ma trận n x m, Allocation[i, j] = k : quá trình i 
được cấp k thể hiện của kiểu tài nguyên j.
„ Request: ma trận n x m, Request [i, j] = k : Pi yêu cầu thêm
k thể hiện của kiểu tài nguyên Rj.
7.37 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
THUẬT TOÁN PHÁT HIỆN
1. Work và Finish là các vectors độ dài m và n, tương ứng
Initialize:
(a) Work = Available
(b) For i = 1,2, …, n, if Allocationi ≠ 0, then 
Finish[i] = false; otherwise, Finish[i] = true.
2. Tìm một chỉ số i sao cho:
(a) Finish[i] == false
(b) Requesti ≤ Work
Nếu không tìm thấy, go to 4. 
3. Work = Work + Allocationi
Finish[i] = true
go to 2.
4. Nếu Finish[i] == false, với một i, 1 ≤ i ≤ n, hệ thống trong trạng thái deadlock. 
Hơn nữa, nếu Finish[i] == false, thì Pi bị deadlock.
Thuật toán có độ phức tạp thời gian O(m x n2). 
7.38 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
VD THUẬT TOÁN PHÁT HIỆN
„ 5 quá trình : P0, P1, P2, P3 và P4;
3 kiểu tài nguyên
A (7 thể hiện), B (2 thể hiện), và C (6 thể hiện).
„ Tức cảnh tại thời điểm T0:
Allocation Request Available
A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 0 
P3 2 1 1 1 0 0 
P4 0 0 2 0 0 2
„ Chạy thuật toán ta được dãy an toàn ; 
finish[i] == true với mọi i; hệ thống không trong trạng thái deadlock
7.39 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
VD (Cont.)
„ Tức cảnh:
Allocation Request Available
A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 1 
P3 2 1 1 1 0 0 
P4 0 0 2 0 0 2
„ Trạng thái hệ thống?
z Tồn tại Deadlock, các quá trình bị deadlock P1, P2, P3, P4.
7.40 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
PHỤC HỒI TỪ DEADLOCK
„ Cuộn lại tất cả các quá trình bị deadlock.
„ Lần luợt cuộn lại từng quá trình bị deadlock đến tận khi chu trình
deadlock bị loại bỏ.
„ Chọn quá trình “nạn nhân”?
z Độ ưu tiên của quá trình.
z Quá trình đã chạy được bao lâu, còn bao lâu nữa nó sẽ hoàn
tất.
z Lượng tài nguyên quá trình chiếm giữ.
z Lượng tài nguyên quá trình cần thêm.
z Bao nhiêu quá trình bị cuộn lại. 
z Quá trình ở dạng trao đổi hay bó?
7.41 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
PHỤC HỒI TỪ DEADLOCK
„ Tối thiểu hóa “giá”
„ Chết đói : một quá trình luôn bị chọn là “nạn nhân”.
End of Chapter 6