Deadlock Detection

Thuật toán phát hiện deadlock được phân thành hai loại:

• Mỗi loại tài nguyên chỉ có một thực thể: sử dụng wait-for graph hoặc resource allocation graph
• Mỗi loại tài nguyên có thể có nhiều thực thể: sử dụng resource allocation graph.

Wait-for Graph

Là một dạng độ thì dẫn xuất từ resource allocation graph bằng cách bỏ đi cách node tài nguyên và các cạnh nối với các node đó.

Gọi thực hiện định kỳ một thuật toán kiểm tra sự tồn tại của chu trình ở trong wait-for graph với độ phức tạp là $O(n^2)$ (n là số node của đồ thị).

Resource Allocation Graph (RAG)

Gọi n là số tiến trình và m là số loại tiến trình.

Data Structures

Để sử dụng RAG thì ta cần các cấu trúc dữ liệu sau:

• available: là một vector có độ dài là m lưu số thực thể đang sẵn sàng của các loại tài nguyên.
• allocation: là một ma trận n x m lưu số lượng thực thể của từng loại tài nguyên mà đã được cấp phát cho các tiến trình.
• request: là một ma trận n x m lưu số lượng thực thể của từng loại tài nguyên mà các tiến trình yêu cầu.

Steps

Các bước thực hiện thuật toán:

1. Khởi tạo finish là một vector với kích thước là n.
   • Với mọi $i=0,1,2,\dots ,n$, nếu allocation[i] != 0 thì finish[i] = False, ngược lại finish[i] = True.
2. Tìm i thỏa mãn finish[i] = False và request[i] <= available (hàng thứ i của request có giá trị nhỏ hơn available ở tất cả các cột). Nếu tồn tại i thì nhảy đến bước 2.1, nếu không tồn tại thì nhảy đến bước 2.2.
   1. Gán available = available + allocation[i].
      • Gán finish[i] = True.
      • Quay về bước 2.
   2. Nếu tồn tại i sao cho finish[i] = False thì hệ thống đang ở trạng thái deadlock và tiến trình $P_i$ đang bị deadlock.

Example 1: No Deadlock

Xét một hệ thống có:

• 5 tiến trình: $P_0$, $P_1$, $P_2$, $P_3$ và $P_4$.
• 3 loại tài nguyên: A (7 thực thể), B (2 thực thể) và C (6 thực thể).

Dựa trên RAG, ta có bảng trạng thái các tiến trình và tài nguyên như sau:

	Allocation	Allocation	Allocation	Available	Available	Available	Request	Request	Request
	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

Bước 1: khởi tạo finish:

finish = [False] * n

Iteration 1

Bước 2: tìm được i = 0 thỏa mãn điều kiện request[0] <= available.

Bước 3: gán available = available + allocation[0]:

available = (0, 0, 0) + (0, 1, 0) = (0, 1, 0)

Bảng trạng thái trở thành:

	Allocation	Allocation	Allocation	Available	Available	Available	Request	Request	Request
	A	B	C	A	B	C	A	B	C
P0	0	1	0	0	0	0	0	0	0
P1	2	0	0	0	1	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

Gán finish[0] = True, vector finish trở thành:

finish = [True, False, False, False, False]

Iteration 2

Bước 2: tìm được i = 2 thỏa mãn điều kiện.

Bước 3: cập nhật giá trị của available:

available = (0, 1, 0) + (3, 0, 3) = (3, 1, 3)

Bảng trạng thái trở thành:

	Allocation	Allocation	Allocation	Available	Available	Available	Request	Request	Request
	A	B	C	A	B	C	A	B	C
P0	0	1	0	0	0	0	0	0	0
P1	2	0	0	0	1	0	2	0	2
P2	3	0	3	3	1	3	0	0	0
P3	2	1	1				1	0	0
P4	0	0	2				0	0	2

Gán finish[2] = True, vector finish trở thành:

finish = [True, False, True, False, False]

Iteration 3

Bước 2: tìm được i = 3 thỏa mãn điều kiện.

Bước 3: cập nhật giá trị của available:

available = (3, 1, 3) + (2, 1, 1) = (5, 2, 4)

Bảng trạng thái trở thành:

	Allocation	Allocation	Allocation	Available	Available	Available	Request	Request	Request
	A	B	C	A	B	C	A	B	C
P0	0	1	0	0	0	0	0	0	0
P1	2	0	0	0	1	0	2	0	2
P2	3	0	3	3	1	3	0	0	0
P3	2	1	1	5	2	4	1	0	0
P4	0	0	2				0	0	2

Gán finish[3] = True, vector finish trở thành:

finish = [True, False, True, True, False]

Iteration 4

Bước 2: tìm được i = 4 thỏa mãn điều kiện.

Bước 3: cập nhật giá trị của available:

available = (5, 2, 4) + (0, 0, 2) = (5, 2, 6)

Bảng trạng thái trở thành:

	Allocation	Allocation	Allocation	Available	Available	Available	Request	Request	Request
	A	B	C	A	B	C	A	B	C
P0	0	1	0	0	0	0	0	0	0
P1	2	0	0	0	1	0	2	0	2
P2	3	0	3	3	1	3	0	0	0
P3	2	1	1	5	2	4	1	0	0
P4	0	0	2	5	2	6	0	0	2

Gán finish[4] = True, vector finish trở thành:

finish = [True, False, True, True, True]

Iteration 5

Bước 2: tìm được i = 1 thỏa mãn điều kiện.

Bước 3: cập nhật giá trị của available:

available = (5, 2, 6) + (2, 0, 0) = (7, 2, 6)

Bảng trạng thái trở thành:

	Allocation	Allocation	Allocation	Available	Available	Available	Request	Request	Request
	A	B	C	A	B	C	A	B	C
P0	0	1	0	0	0	0	0	0	0
P1	2	0	0	0	1	0	2	0	2
P2	3	0	3	3	1	3	0	0	0
P3	2	1	1	5	2	4	1	0	0
P4	0	0	2	5	2	6	0	0	2
				7	2	6

Gán finish[1] = True, vector finish trở thành:

finish = [True, True, True, True, True]

Do không tồn tại i sao cho finish[i] = False nên hệ thống đang không có deadlock với chuỗi các tiến trình là:

$$P_0,P_2,P_3,P_4,P_1$$

Example 2: Deadlock

Giả sử ma trận request thay đổi thành như sau:

	A	B	C
P0	0	0	0
P1	2	0	2
P2	0	0	1
P3	1	0	0
P4	0	0	2

Sau khi đáp ứng được cho $P_0$ thì vector available là:

available = (0, 0, 0) + (0, 1, 0) = (0, 1, 0)

Vector finish sẽ là:

finish = [True, False, False, False, False]

Tuy nhiên, không tồn tại i đồng thời thỏa hai điều kiện sau:

• finish[i] = False
• request[i] <= available

Vì thế, thuật toán sẽ nhảy đến bước 4.

Có thể thấy, tồn tại i = 1, 2, 3, 4 sao cho finish[i] = False. Ta kết luận: hệ thống đang có deadlock xảy ra với các tiến trình bị deadlock là:

$$P_1,P_2,P_3,P_4$$

Resources

• Slide deadlock của đại học Bách Khoa.
• Deadlock Detection with Single-Instance Resource Allocation Graph
• Deadlock Detection with Multi-Instance Resource Allocation Graph