Nguyên lí hệ điều hành - Bế tắc (deadlock)

BẾ TẮC (DEADLOCK)
ThS. Nguyễn Thị Hải Bình
Khoa CNTT, ĐH Giao thông vận tải
Email: calmseahn@gmail.com
Website: calmseahn.weebly.com
BRIDGE CROSSING EXAMPLE
2
DEADLOCK EXAMPLE
3
Process 1 Process 2
1. Process 1 requests the printer, gets it
2. Process 2 requests the tape unit, gets it 
3. Process 1 requests the tape unit, waits
4. Process 2 requests the printer, waits 
4Bế tắc là tình huống xuất hiện khi hai
tiến trình phải chờ đợi nhau giải
phóng tài nguyên hoặc nhiều tiến
trình chờ sử dụng các tài nguyên theo
một “vòng tròn” (circular chain).
MÔ HÌNH HỆ THỐNG
• Xem hệ thống như một tập hợp có giới hạn các tài nguyên
• Kiểu tài nguyên (type)
• Các tài nguyên được chia thành các kiểu, ví dụ: memory, printers, 
CPUs, open files, tape drives, CD-ROMS, 
• Hệ thống có 2 CPU thì kiểu tài nguyên CPU có 2 đối tượng
• Các đối tượng (instances) trong cùng một kiểu tài nguyên có
vai trò như nhau
• Tiến trình sử dụng tài nguyên theo trình tự
• Yêu cầu (Request)
• Sử dụng (Use)
• Giải phóng (Release)
• Một tập hợp các tiến trình ở tình trạng bế tắc khi mỗi tiến
trình đều chờ tài nguyên từ một tiến trình khác trong tập
hợp
5
ĐIỀU KIỆN CẦN ĐỂ CÓ BẾ TẮC
• Bế tắc xuất hiện nếu 4 điều kiện sau đồng thời xuất
hiện
• Độc quyền truy xuất (Mutal exclusion): ít nhất một tài
nguyên bị nắm giữ thuộc kiểu không thể dùng chung
• Giữ và chờ (Hold and wait): tồn tại tiến trình đang nắm
giữ tài nguyên, đồng thời lại chờ tài nguyên bị giữ bởi
tiến trình khác
• Không chiếm đoạt (No preemption): hệ thống không thể
chiếm tài nguyên của tiến trình
• Vòng đợi (Circular wait): Tồn tại tập hợp các tiến trình
{P0, P1, , Pn}, mà P0 chờ P1, P1 chờ P2, , Pn chờ P0
6
ĐỒ THỊ PHÂN PHỐI TÀI NGUYÊN
• Tập đỉnh V
• P = {P1, P2, , Pn} - ứng với các tiến trình
• R = {R1, R2, , Rn} - ứng với các kiểu tài nguyên của hệ
thống
• Tập cung E
• Cung yêu cầu
• Cung phân phối
7
Pi Rj
Pi Rj
ĐỒ THỊ PHÂN PHỐI TÀI NGUYÊN
• Ví dụ
• Tập đỉnh: V = P  R
• P = {P1, P2, P3}
• R = {R1, R2, R3, R4}
• Tập cung
• E = {P1 R1, P2 R3, R1 P2, 
R2 P2, R2 P1, R3 P3}
8
PHÁT HIỆN BẾ TẮC BẰNG ĐTPPTN
• Nếu đồ thị không có chu trình, thì không có tiến
trình nào bị bế tắc
• Nếu đồ thì có chu trình
• Nếu mỗi kiểu tài nguyên trong chu trình có đúng một đối
tượng, thì các tiến trình trong chu trình rơi vào trạng
thái bế tắc
• Nếu mỗi kiểu tài nguyên trong chu trình có nhiều hơn
một đối tượng, thì bế tắc có thể xảy ra
9
10
Thêm vào
cung P3 R3
11
GIẢI QUYẾT BẾ TẮC
• Ba giải pháp
• Đảm bảo hệ thống không rơi vào trạng thái bế tắc
• Sử dụng một trong hai giao thức sau: ngăn chặn bế tắc
(deadlock prevention) hoặc tránh bế tắc (deadlock avoidance)
• Cho phép hệ thống rơi vào trạng thái bế tắc, sau đó phát
hiện (deadlock detection) và khắc phục (recovery)
• Bỏ qua mọi vấn đề, xem như bế tắc không bao giờ xuất
hiện
12
NGĂN CHẶN BẾ TẮC
• Ý tưởng: đảm bảo ít nhất một trong bốn điều kiện
cần của bế tắc không xảy ra
• Độc quyền truy xuất (Mutal exclusion): ít nhất một tài
nguyên bị nắm giữ thuộc kiểu không thể dùng chung
• Giữ và chờ (Hold and wait): tồn tại tiến trình đang nắm
giữ tài nguyên, đồng thời lại chờ tài nguyên bị giữ bởi
tiến trình khác
• Không chiếm đoạt (No preemption): hệ thống không thể
chiếm tài nguyên của tiến trình
• Vòng đợi (Circular wait): Tồn tại tập hợp các tiến trình
{P0, P1, , Pn}, mà P0 chờ P1, P1 chờ P2, , Pn chờ P0
13
NGĂN CHẶN BẾ TẮC
• Điều kiện “độc quyền truy xuất”
• Liên quan tới bản chất của tài nguyên
• Điều kiện này luôn đúng với các tài nguyên không thể
chia sẻ (ví dụ máy in)
• Không thể loại bỏ điều kiện này
• Điều kiện “giữ và chờ”
• Đảm bảo tiến trình không nắm giữ bất kỳ tài nguyên nào
khi yêu cầu tài nguyên khác
• Giải pháp
• Tiến trình yêu cầu tất cả các tài nguyên trước khi thực thi
• Trước khi yêu cầu thêm tài nguyên, tiến trình phải giải phóng
tất cả tài nguyên đang giữ
• “Nạn đói”
14
NGĂN CHẶN BẾ TẮC
• Điều kiện “không chiếm đoạt”
• Giải pháp 1: Nếu tiến trình phải chờ một tài nguyên, thì
hệ thống sẽ thu hồi tất cả tài nguyên mà tiến trình đó
đang giữ
• Giải pháp 2: 
• Nếu tiến trình P yêu cầu một tài nguyên, và tài nguyên đó đang
bị giữ bởi tiến trình Q.
• Nếu Q đang bị phong toả (i.e. đang chờ tài nguyên khác) thì tài
nguyên của Q bị chiếm bởi P
• Nếu ngược lại thì P phải chờ
15
NGĂN CHẶN BẾ TẮC
• Điều kiện “Vòng đợi”
• Đánh số tất cả các tài nguyên
• Các tiến trình yêu cầu cấp phát tài nguyên theo thứ tự
tăng dần
• Ưu điểm
• Dễ cài đặt
• Nhược điểm
• Giảm hiệu suất sử dụng của tài nguyên
• Giảm thông lượng của hệ thống
16
TRÁNH BẾ TẮC
• Ý tưởng
• Nếu biết trước được tất cả nhu cầu sử dụng tài nguyên
của tiến trình, hệ thống có thể quyết định việc cấp phát
tài nguyên để tránh bế tắc
• Hiểu biết về nhu cầu sử dụng tài nguyên có thể là
• Số lượng cực đại các tài nguyên mà tiến trình cần
• Hoặc thứ tự các tài nguyên mà tiến trình cần
17
TRÁNH BẾ TẮC
• Khái niệm “trạng thái cấp phát tài nguyên”
• Xác định bởi số lượng tài nguyên rảnh rỗi, các tài nguyên
đã cấp phát, và tất cả nhu cầu sử dụng tài nguyên của
các tiến trình
• Trạng thái an toàn (Safe state)
• Hệ thống có thể cấp phát tài nguyên cho tất cả các tiến
trình mà không xảy ra bế tắc
• Hệ thống ở trong tình trạng an toàn khi tồn tại một dãy
an toàn
• { P0, P1, P2, ..., PN } là dãy an toàn nếu yêu cầu tài nguyên
của tiến trình Pi có thể được đáp ứng bởi các tài nguyên
chưa cấp phát và các tài nguyên đang bị giữ bởi Pj với j<i
18
19
VÍ DỤ VỀ TRẠNG THÁI AN TOÀN
• Xét hệ thống có 12 tài nguyên là 12 băng từ
• Tại thời điểm t0 hệ thống ở trạng thái như sau:
• Hệ thống ở trạng thái an toàn vì tồn tại {P1, P0, P2} là dãy
an toàn
20
Process Max needs Allocated Current needs
P0 10 5 5
P1 4 2 2
P2 9 2 7
VÍ DỤ VỀ TRẠNG THÁI AN TOÀN
• Xét hệ thống có 12 tài nguyên là 12 băng từ
• Tại thời điểm t1, P2 xin cấp phát 1 tài nguyên và được
chấp nhận. Hệ thống chuyển sang trạng thái như sau:
• Hệ thống ở trạng thái không an toàn
21
Process Max needs Allocated Current needs
P0 10 5 5
P1 4 2 2
P2 9 3 6
THUẬT TOÁN ĐỒ THỊ CẤP PHÁT TÀI
NGUYÊN
• Giả sử mỗi kiểu tài nguyên chỉ có một đối tượng
• Đồ thị gồm có:
• Tập đỉnh: P  R
• Tập cung
• Cung yêu cầu
• Cung phân phối
• Cung nhu cầu (cung báo trước) 
22
23
Resource-allocation graph 
for deadlock avoidance
An unsafe state in a 
resource-allocation graph
THUẬT TOÁN NGÂN HÀNG (BANKER’S 
ALGORITHM)
• Tự đọc
24
PHÁT HIỆN BẾ TẮC
• Kiểu tài nguyên có một đối tượng
• Sử dụng đồ thị đợi chờ (wait-for graph)
• Nếu tồn tại chu trình thì có bế tắc
25
PHÁT HIỆN BẾ TẮC
• Kiểu tài nguyên có nhiều đối tượng
• Giả sử hệ thống có m kiểu tài nguyên và n tiến trình
• Thuật toán phát hiện bế tắc sử dụng các biến sau
• Mảng available[m]
• Mảng allocation[n,m]
• Mảng request[n,m]
• Mảng work[m]
• Mảng finish[n]
26
27
Available [m]
Allocation [n,m] 
Request [n,m]
Work[m]
Finish[n]
The algorithm is as follows:
1. Initialize Work = Available
For i = 1 to n do
If Allocation(i) = 0 then Finish[i] = true else Finish[i] = false
2. Search an i such that
Finish[i] = false and Request(i) ≤ Work
If no such i can be found, go to step 4.
3. For that i found in step 2 do:
Work = Work + Allocation(i)
Finish[i] = true
Go to step 2.
4. If Finish[i] ≠ true for a some i then the system is in deadlock 
state else the system is safe 
KHẮC PHỤC BẾ TẮC
• Tự đọc
28
BÀI TẬP
• Đồ thị phân phối tài nguyên sau có xuất hiện bế tắc
hay không?
29
30
31
32
33
• Xét hệ thống có 9 tài nguyên
• Trạng thái hiện thời của hệ thống như sau
• Hệ thống có ở trạng thái an toàn hay không?
34