Chương
Chương
6: Deadlocks
6: Deadlocks
7.2
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
N
N
Ộ
Ộ
I DUNG
I DUNG
 Vấn Deadlock
 Mô hình hệ thống
 Đặctrư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ụchồitừ Deadlock
7.3
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
M
M
Ụ

z P
1
và P
2
mỗimộtchiếmgiữ một ổđĩavàmỗimộtcần ổđĩa
kia.
 VD.
z semaphores A và B, đượckhởi động là 1
P
0
P
1
wait (A); wait(B)
wait (B); wait(A)
7.5
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
V
V
Í
Í
D
D
Ụ
Ụ
QUA C
QUA C
Ầ

Các chu kỳ CPU, không gian bộ nhớ, các thiếtbị I/O
 Mỗi tài nguyên kiểu R
i
có W
i
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 ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
Đ
Đ
Ặ
Ặ
C TRƯNG DEADLOCK
C TRƯNG DEADLOCK
 Loạitrừ tương hỗ (Mutual exclusion): chỉ một quá trình
sử dụng một tài nguyên tạimộtthời điểm.
 Giữ và chờ (Hold and wait): một quá trình chiếmgiữ ít
nhấtmột tài nguyên và chờ tậu các tài nguyên bổ xung bị
chiếmgiữ 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ểđượcgiải
phóng bởisự tình nguyệncủa quá trình chiếmgiữ nó (sau
khi quá trình đã hoàn thành nhiệmvụ củanó).
 Chờđợi vòng tròn: Tồntạimộttập{P

Edition, Feb 14, 2005
Đ
Đ
Ồ
Ồ
TH
TH
Ị
Ị
C
C
Ấ
Ấ
P PH
P PH
Á
Á
T T
T T
À
À
I NGUYÊN
I NGUYÊN
 V được phân hoạch thành hai kiểu:
z P = {P
1
, P
2
, …, P
n

th
Edition, Feb 14, 2005
Đ
Đ
Ồ
Ồ
TH
TH
Ị
Ị
C
C
Ấ
Ấ
P PH
P PH
Á
Á
T T
T T
À
À
I NGUYÊN (Cont.)
I NGUYÊN (Cont.)
 Quá trình
 Kiều tài nguyên với 4 thể hiện
 P
i
yêu cầuthể hiệncủa R
j

TH
Ị
Ị
C
C
Ấ
Ấ
P PH
P PH
Á
Á
T T
T T
À
À
I NGUYÊN
I NGUYÊN
7.11
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
Đ
Đ
Ồ
Ồ
TH
TH
Ị
Ị

Ị
C
C
Ó
Ó
CHU TRÌNH NHƯNG KHÔNG
CHU TRÌNH NHƯNG KHÔNG
C
C
Ó
Ó
Deadlock
Deadlock
7.13
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
C
C
Á
Á
C S
C S
Ự
Ự
KI
KI
Ệ
Ệ

deadlock.
 Chophéphệ thống rơivàotrạng thái deadlock sau đóphát
hiệnvàphụchồi.
 Bỏ lơ vấn đề và xem như deadlocks không bao giờ xảyra
(đượcsử dụng trong hầuhếtcác HĐH kể cả UNIX).
7.15
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
NGĂN NG
NGĂN NG
Ừ
Ừ
A DEADLOCK
A DEADLOCK
 Loạitrừ tương hỗ (Mutual Exclusion) : không đượcyêu
cầu đốivới các tài nguyên có thể chia sẻ nhưng có hiệulực
đốivới tài nguyên có thể chia sẻ.
 Giữ và chờ (Hold and Wait) : Phải đảmbảorằng mỗikhi
quá trình yêu cầumột tài nguyên nó không chiếmgiữ một
tài nguyên nào.
z Đòi hỏi quá trình yêu cầuvàđượccấp phát tấtcả các
tài nguyên cầnthiếttrướckhibắt đầuthựchiện/ chỉ
cho phép quá trình yêu cầu các tài nguyên khi nó không
chiếmgiữ một tài nguyên nào.
z Hiệusuấtsử dụng tài nguyên thấp, có thể xảyrachết
đói.
Ngăncảnmột trong bốn điềukiệncần để xảy ra deadlock
7.16

trình phải khai báo số lượng tối đa các tài nguyên cầnthiết
củamỗikiểu.
 Thuật toán tránh deadlock kiểmtratrạng thái cấp phát tài
nguyên và đảmbảorằng không xảyrachờđợi vòng tròn.
 Trạng thái cấp phát tài nguyên được định nghĩabởisố tài
nguyên sẵncó, số tài nguyên đã đượccấp phát và các đòi
hỏitối đacủa các quá trình.
Đòi hỏihệ thống phải có thông tin tiên quyết.
7.18
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
TR
TR
Ạ
Ạ
NG TH
NG TH
Á
Á
I AN TO
I AN TO
À
À
N
N
 Khi một quá trình yêu cầumột tài nguyên sẵncó, hệ thống phải
xác định nếucấp phát ngay, hệ thống vẫn trong trạng thái an
toàn.

i
có thể nhận được các tài nguyên cầnthiết,
thựchiện, trả lại các tài nguyên đượccấp phát và kết thúc.
z Khi P
i
kết thúc, P
i +1
nhận được các tài nguyên cầnthiếtvà
cứ như vậy
7.19
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
S
S
Ự
Ự
KI
KI
Ệ
Ệ
N CƠ S
N CƠ S
Ở
Ở
 Nếuhệ thống trong trạng thái an toàn ⇒ không có
deadlocks.
 Nếuhệ thống không trong trạng thái an toàn ⇒ có thể có
deadlock.

th
Edition, Feb 14, 2005
THU
THU
Ậ
Ậ
T TO
T TO
Á
Á
N TR
N TR
Á
Á
NH DEADLOCK
NH DEADLOCK
 Mỗikiểu tài nguyên có đúng mộtthể hiện. Sử dụng đồ thị
cấp phát tài nguyên.
 Mỗikiểu tài nguyên có mộtvàithể hiện. Sử dụng thuật toán
banker
7.22
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
SƠ Đ
SƠ Đ
Ồ
Ồ
Đ

; đượcbiểudiễnbởi đường đứt quãng.
 Cung Claim đượcchuyển thành cung Request khi quá trình
yêu cầu tài nguyên.
 Cung Request đượcchuyển thành cung Assignment khi tài
nguyên đượccấp cho quá trình.
 Khi tài nguyên đượcgiả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 ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
Đ
Đ
Ồ
Ồ
TH
TH
Ị
Ị
C
C
Ấ
Ấ
P PH
P PH
Á
Á
T T

C
C
Ấ
Ấ
P PH
P PH
Á
Á
T T
T T
À
À
I NGUYÊN
I NGUYÊN
7.25
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts - 7
th
Edition, Feb 14, 2005
THU
THU
Ậ
Ậ
T TO
T TO
Á
Á
N Đ
N Đ
Ồ