Banker's Algorithm

Definition

Là một thuật toán tránh deadlock (xem thêm Deadlock Avoidance). Nó còn được dùng để phát hiện xem deadlock có xảy ra trong tương lai hay không.

• Mỗi tiến trình phải khai báo số lượng thực thể (instance) tối đa của một loại tài nguyên mà nó cần.
• Khi tiến trình yêu cầu tài nguyên thì có thể cần phải đợi mặc dù tài nguyên được yêu cầu đang có sẵn.
• Khi tiến trình đã có đủ tài nguyên thì phải hoàn trả trong một thời gian hữu hạn nào đó.

Implementation

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

Data Structures

Khởi tạo các cấu trúc dữ liệu sau:

• available: là một vector có độ dài là m lưu số lượng thực thể đang sẵn sàng của các loại tài nguyên.
• max: là một ma trận n x m lưu số lượng thực thể tối đa mà các tiến trình cần.
• allocation: là một ma trận n x m lưu số lượng thực thể mà các tiến trình đang nắm giữ.
• need: là một ma trận n x m lưu số lượng thực thể mà các tiến trình cần (need = max - allocation)

Steps

Các bước của thuật toán:

1. Gọi finish là vector có độ dài là n.
   • Khởi tạo finish[i] = False (với $i=0,1,...,n$)
2. Tìm i theo thứ tự từ 0 đến n thỏa finish[i] = False và need[i] <= available (hàng thứ i của need 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 finish[i] = True với mọi $i\in 0,1,...,n$ thì hệ thống đang ở trạng thái safe. Ngược lại, nếu tồn tại ít nhất một giá trị của i sao cho finish[i] = False thì hệ thống đang ở trạng thái unsafe.

Độ phức tạp thời gian là $O(m\cdot n^2)$.

Example

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 (10 thực thể), B (5 thực thể) và C (7 thực thể).

Ta có:

n = 5, m = 3

Bảng cho biết trạng thái cấp phát tài nguyên của hệ thống ở thời điểm $t_0$:

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

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

finish = [False] * n

Iteration 1

Bước 2: tìm i thỏa finish = False và need[i] <= available: ta tìm được i = 1 thỏa bởi vì (1, 2, 2) <= (3, 3, 2). Tiến trình $P_1$ sẽ được đưa vào chuỗi tiến trình và sẽ được cấp phát tài nguyên để thực thi.

Bước 3: sau khi tiến trình $P_1$ thực thi thì nó sẽ hoàn trả lại tất cả tài nguyên đã được cấp phát. Do đó, vector available sẽ có giá trị là available + allocation[i]:

available = (3, 3, 2) + (2, 0, 0) = (5, 3, 2)

Điền vào bảng trạng thái giá trị mới của available:

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

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

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

Iteration 2

Tìm được i = 3 thỏa điều kiện, đưa tiến trình $P_3$ vào chuỗi tiến trình. Sau khi tiến trình này thực thi thì available sẽ có giá trị mới là:

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

Bảng trạng thái khi đó sẽ là:

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

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

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

Iteration 3

Tìm được i = 4 thỏa điều kiện, đưa tiến trình $P_4$ vào chuỗi tiến trình. Sau khi tiến trình này thực thi thì available sẽ có giá trị mới là:

available = (7, 4, 3) + (0, 0, 2) = (7, 4, 5)

Bảng trạng thái khi đó sẽ là:

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

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

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

Iteration 4

Tìm được i = 0 thỏa điều kiện, đưa tiến trình $P_0$ vào chuỗi tiến trình. Sau khi tiến trình này thực thi thì available sẽ có giá trị mới là:

available = (7, 4, 5) + (0, 1, 0) = (7, 5, 5)

Bảng trạng thái khi đó sẽ là:

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

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

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

Iteration 5

Tìm được i = 2 thỏa điều kiện, đưa tiến trình $P_2$ vào chuỗi tiến trình. Sau khi tiến trình này thực thi thì available sẽ có giá trị mới là:

available = (7, 5, 5) + (3, 0, 2) = (10, 5, 7)

Bảng trạng thái khi đó sẽ là:

	Allocation	Allocation	Allocation	Max	Max	Max	Available	Available	Available	Need	Need	Need
	A	B	C	A	B	C	A	B	C	A	B	C
P0	0	1	0	7	5	3	3	3	2	7	4	3
P1	2	0	0	3	2	2	5	3	2	1	2	2
P2	3	0	2	9	0	2	7	4	3	6	0	0
P3	2	1	1	2	2	2	7	4	5	0	1	1
P4	0	0	2	4	3	3	7	5	5	4	3	1
							10	5	7

Gán finish[2] = 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 ta kết luận hệ thống đang ở trong trạng thái an toàn với chuỗi an toàn là:

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

Resources

• Slide deadlock của đại học Bách Khoa.
• L-4.5: Deadlock Avoidance Banker’s Algorithm with Example | With English Subtitles