Cuộnlạitấtcảcác quá trình bị deadlock.
Lầnluợtcuộnlạitừng quá trình bị deadlock đếntận khi chu trình
deadlock bị loạibỏ.
Chọn quá trình “nạn nhân”?
Độ ưutiêncủa quá trình.
Quá trìnhđãchạyđược bao lâu, còn bao lâu nữanósẽhoàn
tất
42 trang |
Chia sẻ: hao_hao | Lượt xem: 2121 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng Deadlocks, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 6: Deadlocks
7.2 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
NỘI DUNG
Vấn Deadlock
Mô hình hệ thống
Đặc trưng Deadlock
Các phương pháp quản lý Deadlocks
Phòng ngừa Deadlock
Tránh Deadlock
Phát hiện Deadlock
Phục hồi từ Deadlock
7.3 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
MỤC TIÊU
Phát triển một mô tả deadlocks, hiện tượng ngăn cản
tập các giao dịch cạnh tranh hoàn tất nhiệm vụ của
chúng
Giới thiệu một số phương pháp khác nhau để ngăn
ngừa, tránh deadlocks trong hệ thống máy tính.
Giới thiệu phương pháp phát hiện và phục hồi từ
deadlocks
7.4 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
VẤN ĐỀ Deadlock
Một tập các quá trình bị nghẽn, mỗi một chiếm giữ một tài
nguyên và chờ đợi tậu tài nguyên bị chiếm giữ bởi quá trình
khác trong tập hợp.
VD.
z Hệ thống có hai ổ đĩa.
z P1 và P2 mỗi một chiếm giữ một ổ đĩa và mỗi một cần ổ đĩa
kia.
VD.
z semaphores A và B, được khởi động là 1
P0 P1
wait (A); wait(B)
wait (B); wait(A)
7.5 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
VÍ DỤ QUA CẦU
Lưu thông chỉ theo một chiều.
Mỗi phần của cầu được xem như một tài nguyên.
Nếu deadlock xảy ra nó sẽ được giải quyết nếu một xe lùi
lại (trưng các tài nguyên và cuộn lại).
Một vài xe có thể bị lùi lại khi deadlock xảy ra.
Có thể xảy ra “sự chết đói”.
7.6 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
MÔ HÌNH HỆ THỐNG
Các kiểu tài nguyên: R1, R2, . . ., Rm
Các chu kỳ CPU, không gian bộ nhớ, các thiết bị I/O
Mỗi tài nguyên kiểu Ri cóWi thể hiện.
Mỗi quá trình sử dụng một tài nguyên như sau:
z Yêu cầu tài nguyên
z Sử dụng tài nguyên
z Giải phóng tài nguyên
7.7 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
ĐẶC TRƯNG DEADLOCK
Loại trừ tương hỗ (Mutual exclusion): chỉ một quá trình
sử dụng một tài nguyên tại một thời điểm.
Giữ và chờ (Hold and wait): một quá trình chiếm giữ ít
nhất một tài nguyên và chờ tậu các tài nguyên bổ xung bị
chiếm giữ bởi các quá trình khác.
Không có trưng dụng: một tài nguyên chỉ có thể được giải
phóng bởi sự tình nguyện của quá trình chiếm giữ nó (sau
khi quá trình đã hoàn thành nhiệm vụ của nó).
Chờ đợi vòng tròn: Tồn tại một tập {P0, P1, …, P0} các quá
trình chờ đợi sao cho P0 chờ một tài nguyên bị chiếm giữ
bởi P1, P1 chờ một tài nguyên bị chiếm giữ bởi P2, …, Pn–1
chờ một tài nguyên bị chiếm giữ bởi Pn, và Pn chờ một tài
nguyên bị chiếm giữ bởi P0.
Điều kiện cần để deadlock xảy ra:
7.8 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN
V được phân hoạch thành hai kiểu:
z P = {P1, P2, …, Pn}, gồm tất cả các quá trình trong hệ
thống.
z R = {R1, R2, …, Rm}, gồm tất cả các kiểu tài nguyên
trong hệ thống.
Cung yêu cầu – cung hướng từ Pi đến Rj : Pi → Rj
Cung gán – hướng từ Rj đến Pi : Rj→ Pi
Một tập các đỉnh V và một tập các cung E.
7.9 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN (Cont.)
Quá trình
Kiều tài nguyên với 4 thể hiện
Pi yêu cầu thể hiện của Rj
Pi đang chiếm giữ một thể hiện của kiểu tài nguyên Rj
Pi
Pi
Rj
Rj
7.10 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
VÍ DỤ ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN
7.11 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN VỚI DEADLOCK
7.12 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
ĐỒ THỊ CÓ CHU TRÌNH NHƯNG KHÔNG
CÓ Deadlock
7.13 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
CÁC SỰ KIỆN CƠ SỞ
Nếu đồ thị không có chu trình⇒ không có deadlock.
Nếu đồ thị có chu trình⇒
z Nếu mỗi kiểu tài nguyên chỉ có một thể hiện thì có
deadlock.
z Nếu mỗi kiểu tài nguyên có một vài thể hiện thì có
thể có deadlock.
7.14 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
CÁC PHƯƠNG PHÁP QUẢN LÝ DEADLOCKS
Đảm bảo hệ thống không bao giờ rơi vào trạng thái
deadlock.
Cho phép hệ thống rơi vào trạng thái deadlock sau đó phát
hiện và phục hồi.
Bỏ lơ vấn đề và xem như deadlocks không bao giờ xảy ra
(được sử dụng trong hầu hết các HĐH kể cả UNIX).
7.15 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
NGĂN NGỪA DEADLOCK
Loại trừ tương hỗ (Mutual Exclusion) : không được yêu
cầu đối với các tài nguyên có thể chia sẻ nhưng có hiệu lực
đối với tài nguyên có thể chia sẻ.
Giữ và chờ (Hold and Wait) : Phải đảm bảo rằng mỗi khi
quá trình yêu cầu một tài nguyên nó không chiếm giữ một
tài nguyên nào.
z Đòi hỏi quá trình yêu cầu và được cấp phát tất cả các
tài nguyên cần thiết trước khi bắt đầu thực hiện / chỉ
cho phép quá trình yêu cầu các tài nguyên khi nó không
chiếm giữ một tài nguyên nào.
z Hiệu suất sử dụng tài nguyên thấp, có thể xảy ra chết
đói.
Ngăn cản một trong bốn điều kiện cần để xảy ra deadlock
7.16 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
Deadlock Prevention (Cont.)
Không có trưng dụng (no preemption):
z Nếu một quá trình đang chiếm giữ một số tài nguyên yêu
cầu tài nguyên khác nhưng không thể được cấp phát
ngay, các tài nguyên bị chiếm giữ bởi quá trình bị trưng
dụng.
z Các tài nguyên bị trưng dụng được thêm vào danh sách
các tài nguyên quá trình (bị trưng dụng) chờ.
z Quá trình sẽ được khởi động lại chỉ khi nó có thể tậu lại
các tài nguyên cũ cũng như các tài nguyên mới yêu cầu.
Chờ đợi vòng tròn (Circular Wait) – áp đặt một thứ tự toàn
phần trên các kiểu tài nguyên và đòi hỏi mỗi quá trình yêu cầu
tài nguyên theo thứ tự tăng.
7.17 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005
TRÁNH Deadlock
Mô hình đơn giản nhất và hữu dụng nhất là đòi hỏi mỗi quá
trình phải khai báo số lượng tối đa các tài nguyên cần thiết
của mỗi kiểu.
Thuật toán tránh deadlock kiểm tra trạng thái cấp phát tài
nguyên và đảm bảo rằng không xảy ra chờ đợi vòng tròn.
Trạng thái cấp phát tài nguyên được định nghĩa bởi số tài
nguyên sẵn có, số tài nguyên đã được cấp phát và các đò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
Các file đính kèm theo tài liệu này:
- ch6_deadlock_3966.pdf