Bài giảng Hệ điều hành - Chương 6: Deadlocks (Phần 2)

Chương 6: Deadlocks - 2

Câu hỏi ôn tập chương 6 - 1

 Deadlock là gì? Cho ví dụ trong thực tế?

 Một tiến trình khi nào gọi là bị deadlock? trì hoãn vô

hạn định?

 Khi nào sẽ xảy ra deadlock?

 Các phương pháp giải quyết deadlock?

 Làm gì để ngăn deadlock?

 Làm gì để tránh deadlock?

Deadlocks

2

Câu hỏi ôn tập chương 6 – 1 (tt)

 Sơ đồ sau có xảy ra deadlock?

R₃

R₁

P₁

P₃

P₂

Deadlock ?

R₂

R₄

Deadlocks

3

Câu hỏi ôn tập chương 6 – 1 (tt)

 Hệ thống có 18 tape drive và 4 tiến trình P0, P1, P2, P3

 Tại thời điểm t_o

Max

10

4

Allocation

Need

5

Available

P0

P1

P2

P3

5

2

6

5

3

2

15

10

13

4

16

10

Deadlocks

4

Mục tiêu

 Hiểu được thêm các phương pháp giải quyết

deadlock

 Tránh deadlock

 Phát hiện

 Phục hồi

 Hiểu và hiện thực được giải thuật Banker

Deadlocks

5

Nội dung

 Giải thuật đồ thị cấp phát tài nguyên

 Giải thuật banker

 Phát hiện deadlock

 Phục hồi deadlock

Deadlocks

6

Giải thuật đồ thị cấp phát tài nguyên

Deadlocks

7

Giải thuật Banker

 Mỗi loại tài nguyên có nhiều thực thể

 Bắt chước nghiệp vụ ngân hàng

 Điều kiện:

 Mỗi tiến trình phải khai báo số lượng thực thể tối đa

của mỗi 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ể phải đợi

 Khi tiến trình đã có được đầy đủ tài nguyên thì phải

hoàn trả trong một khoảng thời gian hữu hạn nào đó

Deadlocks

8

Cấu trúc dữ liệu cho giải thuật Banker

n: số tiến trình; m: số loại tài nguyên

 Available: vector độ dài m

 Available[j] = k  loại tài nguyên Rj có k instance sẵn sàng

 Max: ma trận n × m

 Max[i, j] = k  tiến trình Pi yêu cầu tối đa k instance của loại tài

nguyên Rj

 Allocation: ma trận độ dài n ×m

 Allocation[i, j] = k  Pi đã được cấp phát k instance của Rj

 Need: ma trận độ dài n × m

 Need[i, j] = k  Pi cần thêm k instance của Rj

 Need[i, j] = Max[i, j] - Allocation[i, j]

Ký hiệu Y  X  Y[i]  X[i], với mọi i.

Ví dụ (0, 3, 2, 1)  (1, 7, 3, 2)

Deadlocks

9

Giải thuật an toàn

1. Gọi Work va

̀

Finish là hai vector đô

̣

dài lần lượt là m va

̀

n. Khꢀi tạo:

Work = Available

Finish[i] = false, i = 0, 1, …, n-1

2. Tìm i thꢁa

(a) Finish[i] == false

(b) Need_i≤ Work (hàng thứ i của Need)

Nếu không tồn tại i như vậy, đến bước 4.

3. Work = Work + Allocation_i

Finish[i] = true

quay về bước 2

4. Nếu Finish[i] == true, i = 1,…, n, thì hệ thống đang ꢀ

trạng thái safe

Deadlocks

10

Giải thuật Banker - Ví dụ

 5 tiến trình P0,…,P4

 3 loại tài nguyên:

 A (10 thực thể), B (5 thực thể), C (7 thực thể)

 Sơ đồ cấp phát trong hệ thống tại thời điểm T0

Allocation

Max

B

Available

Need

A

B

1

0

1

0

C

A

7

3

9

2

4

C

A

B

C

A

7

1

6

0

4

B

4

2

0

1

3

C

3

2

0

1

P0

P1

P2

P3

P4

0

2

3

2

0

2

1

2

5

3 3

3

2

3

0

2

3

Deadlocks

11

Giải thuật Banker - Ví dụ (tt)

 Chuỗi an toàn <P1, P3, P4, P2, P0>

Deadlocks

12

Giải thuật yêu cầu tài nguyên cho tiến trình Pi

Request_ilà request vector của process P_i.

Request_i[j] = k  P_icần k instance của tài nguyên R_j.

1. Nếu Request_i≤ Need_ithì đến bước 2. Nếu không, báo

lỗi vì tiến trình đã vượt yêu cầu tối đa.

2. Nếu Request_i≤ Available thì qua bước 3. Nếu không, P_i

phải chờ vì tài nguyên không cꢂn đủ để cấp phát.

3. Giả định cấp phát tài nguyên đáp ứng yêu cầu của P_i

bꢃng cách cập nhật trạng thái hệ thống như sau:

Available = Available – Request_i

Allocation_i= Allocation_i+ Request_i

Need_i= Need_i– Request_i

Deadlocks

13

Giải thuật yêu cầu tài nguyên cho tiến trình Pi (tt)

 Áp dụng giải thuật kiểm tra trạng thái an toàn lên

trạng thái trên hệ thống mới

 Nếu trạng thái là safe thì tài nguyên được cấp

thực sự cho Pi

 Nếu trạng thái là unsafe thì Pi phải đợi và phục

hồi trạng thái

Available = Available + Request_i

Allocation_i= Allocation_i– Request_i

Need_i

= Need_i+ Request_i

Deadlocks

14

Ví dụ: P1 yêu cầu (1, 0, 2)

 Kiểm tra Request 1 ≤ Available :

 (1, 0, 2) ≤ (3, 3, 2)  Đúng

 Trạng thái mới là safe (chuỗi an toàn là <P1, P3, P4, P0, P2>

vậy có thể cấp phát tài nguyên cho P1

Deadlocks

15

Ví dụ: P4 yêu cầu (3, 3, 0)

 Kiểm tra Request 4 ≤ Available:

 (3, 3, 0) ≤ (3, 3, 2)  Đúng

Allocation

A B C

0 1 0

3 0 2

2 1 1

3 3 2

Need

Available

A B C

0 0 2

A B C

7 4 3

1 2 2

6 0 0

0 1 1

1 0 1

P₀

P₁

P₂

P₃

P₄

 Trạng thái mới là unsafe vậy không thể cấp phát tài nguyên

cho P4

Deadlocks

16

Ví dụ: P0 yêu cầu (0, 2, 0)

 Kiểm tra Request 4 ≤ Available:

 (0, 2, 0) ≤ (3, 3, 2)  Đúng

Allocation

A B C

0 3 0

3 0 2

2 1 1

0 0 2

Need

Available

A B C

3 1 2

A B C

7 2 3

1 2 2

6 0 0

0 1 1

4 3 1

P₀

P₁

P₂

P₃

P₄

 Trạng thái mới là safe, chuỗi an toàn <P3, P1, P2, P0, P4>

vậy có thể cấp phát tài nguyên cho P0

Deadlocks

17

Phát hiện deadlock

• Chấp nhận xảy ra deadlock trong hệ thống

• Giải thuật phát hiện deadlock

• Cơ chế phục hồi

Deadlocks

18

Mỗi loại tài nguyên chỉ có một thực thể

 Sử dụng wait-for graph

 Các Node là các tiến trình

 Pi  Pj nếu Pi chờ tài nguyên từ Pj

 Mỗi giải thuật kiểm tra có tồn tại chu trình trong wait-

for graph hay không sẽ được gọi định kỳ. Nếu có chu

trình thì tồn tại deadlock

 Giải thuật phát hiện chu trình có thời gian chạy là O(n²),

với n là số đỉnh của graph

Deadlocks

19

Sơ đồ cấp phát tài nguyên và sơ đồ wait-for

Resource-Allocation Graph

Corresponding wait-for graph

Deadlocks

20

Bài giảng Hệ điều hành - Chương 6: Deadlocks (Phần 2) - Trần Thị Như Nguyệt