Khoa Công Nghệ Thông Tin & Truyền Thông
Đại học Cần Thơ
Giảng viên: Hà Duy An


1. Deadlock là gì?
2. Các phương pháp xử lý Deadlock
o Ngăn chặn Deadlock
o Tránh Deadlock
o Phát hiện và phục hồi từ Deadlock

9/27/2013

2

Chương 6: Deadlock



• Hệ thống máy tính bao gồm một tập hợp các nguồn tài nguyên
• Các kiểu tài nguyên R1, R2, . . ., Rm
o Ví dụ: CPU cycles, memory space, I/O devices

• Mỗi tài nguyên Ri có Wi thể hiện.
• Tiến trình sử dụng một tài nguyên theo các bước như sau:
o Yêu cầu (request)
o Sử dụng (use)
o Giải phóng (release)

9/27/2013


6

Chương 6: Deadlock


Deadlock có thể phát sinh nếu 4 điều kiện sau thỏa cùng lúc:
• Loại trừ hỗ tương: chỉ một tiến trình có thể sử dụng tài nguyên tại một
thời điểm.
• Giữ và chờ: Một tiến trình đang giữ ít nhất là một tài nguyên và đang
chờ để đạt được một tài nguyên khác đang bị giữ bởi tiến trình khác.
• Không trưng dụng: một tài nguyên chỉ có thể được giải phóng một cách
tự nguyện bởi tiến trình đang giữ nó, sau khi tiến trình này hoàn thành.
• Chờ đợi vòng tròn: tồn tại một tập hợp {P0, P1, …, Pn} các tiến trình
đang chờ đợi như sau: P0 đang đợi tài nguyên mà P1 đang giữ, P1 đang
đợi tài nguyên mà P2 đang giữ, …, Pn–1 đang đợi tài nguyên mà Pn đang
giữ và Pn lại đang chờ đợi tài nguyên mà P0 đang giữ.

9/27/2013

7

Chương 6: Deadlock


• Bao gồm tập hợp các đỉnh V và tập hợp các cạnh E.
• V được chia làm 2 dạng:
o P = {P1, P2, …, Pn}, là tập hợp các tiến trình đang tồn tại trong hệ
thống.
o R = {R1, R2, …, Rm}, là tập hợp các tài nguyên đang tồn tại trong hệ
thống.


9/27/2013

10

Chương 6: Deadlock


9/27/2013

11

Chương 6: Deadlock


9/27/2013

12

Chương 6: Deadlock


• Nếu đồ thị không có chu trình (cycle)  không có deadlock.
• Nếu đồ thị có một chu trình:
o Nếu một tài nguyên chỉ có một thể hiện thì deadlock xảy ra.
o Nếu một tài nguyên có vài thể hiện, có khả năng deadlock xảy ra.

9/27/2013

13

một tài nguyên nào cả.
o Giải pháp này làm giảm đáng kể hiệu xuất sử dụng tài nguyên, và có
thể gây ra tình trạng đói tài nguyên.
9/27/2013

17

Chương 6: Deadlock


• Không trưng dụng (no preemption):
o Nếu một tiến trình đang giữ một số tài nguyên lại yêu cầu thêm một
tài nguyên mới, nhưng tài nguyên mới này không thể được cấp phát,
thì tiến trình đó phải giải phóng tất cả các tài nguyên nó đang giữ.
• Các tài nguyên vừa được trưng dụng được thêm vào danh sách các
tài nguyên mà tiến trình đang cần.
• Tiến trình sẽ bị khởi động lại chỉ khi nó không thể xin lại được các tài
nguyên cũ cũng như tài nguyên mới nó đang cần.

• Chờ đợi vòng tròn (circular wait): phải áp đặt thứ tự toàn cục
của tất cả các lọai tài nguyên và yêu cầu rằng mỗi tiến trình phải
yêu cầu các tài nguyên theo thứ tự tăng.

9/27/2013

18

Chương 6: Deadlock



thì, thì Pi có thể đợi đến khi tất cả Pj hoàn thành.
o Khi Pj hoàn thành, Pi có thể lấy các tài nguyên cần thiết, thực thi tiếp, trả
lại số tài nguyên đã chiếm và kết thúc.
o Khi Pi kết thúc, Pi+1 có thể lấy các tài nguyên mà nó cần, …
9/27/2013

21

Chương 6: Deadlock


• Nếu hệ thống ở trong
trạng thái an toàn 
không có deadlock.
• Nếu hệ thống ở trong
trạng thái không an toàn
 có thể có deadlock.
• Tránh deadlock  đảm
bảo rằng hệ thống sẽ
không bao giờ rơi vào
trạng thái không an toàn.

9/27/2013

22

Chương 6: Deadlock


1. Mỗi loại tài nguyên có một thể hiện:


9/27/2013

24

Chương 6: Deadlock


Yêu cầu tài nguyên của P2 đối với R2 sẽ không được cấp phát, mặc
dù R2 đang sẵn dùng, bởi vì có thể tạo ra chu trình, dẫn tới deadlock.
9/27/2013

25

Chương 6: Deadlock