Bài giảng Nguyên lý hệ điều hành - Nguyễn Hải Châu - Tuần 5: Bế tắc (Deadlock)

 tránh được bế tắc, hay
z Hệ thống ở trong trạng thái an toàn nếu và chỉ
nếu tồn tại một thứ tự an toàn (safe-sequence)
35
Thứ tự an toàn
z Thứ tự các tiến trình gọi là một 
thứ tự an toàn (safe-sequence) cho trạng thái 
cấp-phát hiện-tại nếu với mỗi Pi, yêu cầu cấp 
phát tài nguyên của Pi vẫn có thể được thỏa 
mãn căn cứ vào trạng thái của:
z Tất cả các tài nguyên rỗi hiện có, và
z Tất cả các tài nguyên đang bị chiếm giữ bởi tất cả
các Pj ∀j<i.
36
Các trạng thái an toàn, không 
an toàn và bế tắc
z Trạng thái an toàn 
không là trạng thái bế
tắc
z Trạng thái bế tắc là
trạng thái không an 
toàn
z Trạng thái không an 
toàn có thể là trạng thái 
bế tắc hoặc không
An toàn
Không an toàn
Bế tắc
737
Ví dụ trạng thái an toàn, bế tắc
z Xét một hệ thống có 12 tài nguyên là 12 băng 
từ và 3 tiến trình P0, P1, P2 với các yêu cầu 
cấp phát:
z P0 yêu cầu nhiều nhất 10 băng từ
z P1 yêu cầu nhiều nhất 4 băng từ
z P2 yêu cầu nhiều nhất 9 băng từ
z Giả sử tại một thời điểm t0, P0 đang chiếm 5 
băng từ, P1 và P2 mỗi tiến trình chiếm 2 băng 
từ. Như vậy có 3 băng từ rỗi
38
Ví dụ trạng thái an toàn, bế tắc
Yêu cầu nhiều nhất Yêu cầu hiện tại
P0 10 5
P1 4 2
P2 9 2
z Tại thời điểm t0, hệ thống ở trạng thái an toàn
z Thứ tự thỏa mãn điều kiện an toàn
z Giả sử ở thời điểm t1, P2 có yêu cầu và được 
cấp phát 1 băng từ: Hệ thống không ở trạng thái 
an toàn nữa... -> quyết đinh cấp tài nguyên cho 
P2 là sai.
39
Thuật toán đồ thị cấp phát tài 
nguyên
z Giả sử các tài nguyên chỉ có 1 thể hiện
z Sử dụng đồ thị cấp phát tài nguyên như ở
slide 16 và thêm một loại cung nữa là cung 
báo trước (claim)
z Cung báo trước Pi→Rj chỉ ra rằng Pi có thể
yêu cầu cấp phát tài nguyên Rj, được biểu 
diễn trên đồ thị bằng các đường nét đứt
z Khi tiến trình Pi yêu cầu cấp phát tài nguyên 
Rj, đường nét đứt trở thành đường nét liền
40
Thuật toán đồ thị cấp phát tài 
nguyên
z Chú ý rằng các tài nguyên phải được thông 
báo trước khi tiến trình thực hiện
z Các cung báo trước sẽ phải có trên đồ thị
cấp phát tài nguyên
z Tuy nhiên có thể giảm nhẹ điều kiện: cung 
thông báo Pi→Rj được thêm vào đồ thị nếu 
tất cả các cung gắn với Pi đều là cung thông 
báo
41
Thuật toán đồ thị cấp phát tài 
nguyên
z Giả sử Pj yêu cầu cấp phát Rj. Yêu cầu này 
chỉ có thể được chấp nhận nếu ta chuyển 
cung báo trước Pi→Rj thành cung cấp phát 
Rj→Pi và không tạo ra một chu trình
z Chúng ta kiểm tra bằng cách sử dụng thuật 
toán phát hiện chu trình trong đồ thị: Nếu có
n tiến trình trong hệ thống, thuật toán phát 
hiện chu trình có độ phức tạp tính toán O(n2)
z Nếu không có chu trình: Cấp phát->trạng thái 
an toàn, ngược lại: Trạng thái không an toàn
42
Ví dụ
z Giả sử P1 yêu cầu cấp 
phát R2
z Mặc dù R2 rỗi nhưng 
chúng ta không thể cấp 
phát R2, vì nếu cấp phát 
ta sẽ có chu trình trong 
đồ thị và gây ra chờ vòng 
→ Hệ thống ở trạng thái 
không an toàn
P1 P2
R2
R1
P1 P2
R2
R1
843
Thuật toán banker
z Thuật toán đồ thị phân phối tài nguyên không 
áp dụng được cho các hệ thống có những tài 
nguyên có nhiều thể hiện
z Thuật toán banker được dùng cho các hệ có
tài nguyên nhiều thể hiện, nó kém hiệu quả 
hơn thuật toán đồ thị phân phối tài nguyên
z Thuật toán banker có thể dùng trong ngân 
hàng: Không bao giờ cấp phát tài nguyên 
(tiền) gây nên tình huống sau này không đáp 
ứng được nhu cầu của tất cả các khách hàng 44
Ký hiệu dùng trong banker
z Tài nguyên rỗi: Vector m thành phần 
Available, Available[j]=k nghĩa là có k thể
hiện của Rj rỗi
z Max: Ma trận nxm xác định yêu cầu tài 
nguyên max của mỗi tiến trình. Max[i][j]=k có
nghĩa là tiến trình Pi yêu cầu nhiều nhất k thể
hiện của tài nguyên Rj.
45
Ký hiệu dùng trong banker
z Cấp phát: Ma trận nxm xác định số thể hiện 
của các loại tài nguyên đã cấp phát cho mỗi 
tiến trình. Allocation[i][j]=k có nghĩa là tiến 
trình Pi được cấp phát k thể hiện của Rj.
z Cần thiết: Ma trận nxm chỉ ra số lượng thể
hiện của các tài nguyên mỗi tiến trình cần 
cấp phát tiếp. Need[i][j]=k có nghĩa là tiến 
trình Pi còn có thể cần thêm k thể hiện nữa 
của tài nguyên Rj.
46
Ký hiệu dùng trong banker
z Số lượng và giá trị các biến trên biến đổi theo 
trạng thái của hệ thống
z Qui ước: Nếu hai vector X, Y thỏa mãn 
X[i]≤Y[i] ∀i thì ta ký hiệu X≤Y.
z Giả sử Work và Finish là các vector m và n
thành phần. 
z Request[i] là vector yêu cầu tài nguyên của 
tiến trình Pi. Request[i][j]=k có nghĩa là tiến 
trình Pi yêu cầu k thể hiện của tài nguyên Rj
47
Thuật toán trạng thái an toàn
1. Khởi tạo Work=Available và Finish[i]=false 
∀i=1..n
2. Tìm i sao cho Finish[i]==false và Need[i]≤Work
Nếu không tìm được i, chuyển đến bước 4
3. Work=Work+Allocation[i], Finish[i]=true
Chuyển đến bước 2
4. Nếu Finish[i]==true ∀i thì hệ thống ở trạng thái 
an toàn
z Độ phức tạp tính toán của thuật toán trạng thái 
an toàn: O(m.n2) 48
Thuật toán yêu cầu tài nguyên
1. Nếu Request[i]≤Need[i], chuyển đến bước 2
Ngược lại thông báo lỗi (không có tài nguyên rỗi)
2. Nếu Request[i]≤Available, chuyển đến bước 3. 
Ngược lại Pi phải chờ vì không có tài nguyên
3. Nếu việc thay đổi trạng thái giả định sau đây:
Available=Availalble-Request[i]
Allocation=Allocation+Request[i]
Need[i]=Need[i]-Request[i]
đưa hệ thống vào trạng thái an toàn thì cấp phát tài 
nguyên cho Pi, ngược lại Pi phải chờ Request[i] và
trạng thái của hệ thống được khôi phục như cũ
949
Ví dụ banker
z Xét một hệ thống các tiến trình và tài nguyên 
như sau:
Allocation Max Available 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
50
Ví dụ banker
z Hệ thống hiện đang ở trạng thái an toàn
z Thứ tự thỏa mãn tiêu chuẩn 
an toàn
z Giả sử P1 có yêu cầu: Request[1]=(1,0,2)
z Để quyết định xem có cấp phát tài nguyên 
theo yêu cầu này không, trước hết ta kiểm tra 
Request[1]≤Available: (1,0,2)<(3,3,2): Đúng
z Giả sử yêu cầu này được cấp phát, khi đó
trạng thái giả định của hệ thống là:
51
Ví dụ banker
Allocation Need Available
A B C A B C A B C
P0 0 1 0 7 4 3 3 3 2
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
z Thực hiện thuật toán trạng thái an toàn và thấy rằng 
thứ tự . Do đó có thể cấp phát tài 
nguyên cho P1 ngay.
52
Ví dụ banker
z Tuy nhiên, nếu hệ thống ở trạng thái sau thì
z Yêu cầu (3,3,0) của P4 không thể cấp phát ngay 
vì các tài nguyên không rỗi
z Yêu cầu (0,2,0) của P0 cũng không thể cấp phát 
ngay vì mặc dù các tài nguyên rỗi nhưng việc 
cấp phát sẽ làm cho hệ thống rơi vào trạng thái 
không an toàn
z Bài tập: Thực hiện kiểm tra và quyết định 
cấp phát hai yêu cầu trên
53
Phát hiện bế tắc
z Nếu không áp dụng phòng tránh hoặc ngăn 
chặn bế tắc thì hệ thống có thể bị bế tắc
z Khi đó:
z Cần có thuật toán kiểm tra trạng thái để xem có
bế tắc xuất hiện hay không
z Thuật toán khôi phục nếu bế tắc xảy ra
54
Tài nguyên chỉ có một thể hiện
z Sử dụng thuật toán đồ thị chờ: Đồ thị chờ có 
được từ đồ thị cấp phát tài nguyên bằng cách 
xóa các đỉnh tài nguyên và nối các cung liên 
quan
z Cung Pi→Pj có nghĩa là Pi đang chờ Pj giải phóng tài 
nguyên mà Pi cần
z Cung Pi→Pj tồn tại trong đồ thị chờ nếu và chỉ nếu 
đồ thị cấp phát tài nguyên tương ứng có hai cung 
Pi→Rq và Rq→Pj với Rq là tài nguyên
z Hệ thống có bế tắc nếu đồ thị chờ có chu trình
z Để phát hiện bế tắc: Cần cập nhật đồ thị chờ và thực 
hiện định kỳ thuật toán phát hiện chu trình
10
55 56
Tài nguyên có nhiều thể hiện
z Available: Vector m thành phần chỉ ra số 
lượng thể hiện của mỗi loại tài nguyên
z Allocation: Ma trận nxm xác định số thể hiện 
của mỗi loại tài nguyên đang được cấp phát 
cho các tiến trình
z Request: Ma trận nxm xác định yêu cầu hiện 
tại của mỗi tiến trình. Nếu Request[i][j]=k thì
tiến trình Pi yêu cầu cấp phát k thể hiện của 
tài nguyên Rj.
57
Tài nguyên có nhiều thể hiện
1. Giả sử Work và Finish là các vector m và n thành 
phần. Khởi tạo Work=Available. Với mỗi i=0..n-1 gán 
Finish[i]=false nếu Allocation[i]≠0, ngược lại gán 
Finish[i]=true
2. Tìm i sao cho Finish[i]==false và Request[i]≤Work. Nếu 
không tìm thấy i, chuyển đến bước 4
3. Work=Work+Allocation, Finish[i]=true; chuyển đến 
bước 2
4. Nếu Finish[i]==false với 0≤i≤n-1 thì hệ thống đang bị
bế tắc (và tiến trình Pi đang bế tắc).
z Độ phức tạp tính toán của thuật toán: O(m.n2)
58
Sử dụng thuật toán phát hiện
z Tần suất sử dụng phụ thuộc:
z Tần suất xảy ra bế tắc
z Bao nhiêu tiến trình bị ảnh hưởng bởi bế tắc?
z Sử dụng thuật toán phát hiện:
z Định kỳ: Có thể có nhiều chu trình trong đồ thị, 
không biết được tiến trình/request nào gây ra bế
tắc
z Khi có yêu cầu cấp phát tài nguyên: Tốn tài 
nguyên CPU
59
Khôi phục khi có bế tắc
z Kết thúc tiến trình:
z Kết thúc toàn bộ các tiến trình bị bế tắc (1)
z Kết thúc từng tiến trình và dừng quá trình này 
khi bế tắc chấm dứt (2)
z Tiến trình bị kết thúc ở (2) căn cứ vào:
z Độ ưu tiên
z Thời gian đã thực hiện và thời gian còn lại
z Số lượng và các loại tài nguyên đã sử dụng
z Các tài nguyên cần cấp phát thêm
z Số lượng các tiến trình phải kết thúc
z Tiến trình là tương tác hay xử lý theo lô (batch) 60
Khôi phục khi có bế tắc
z Giải phóng tài nguyên một cách bắt buộc 
(preemption):
z Chọn tài nguyên nào và tiến trình nào để thực 
hiện?
z Khôi phục trạng thái của tiến trình đã chọn ở (1) 
như thế nào?
z Làm thế nào để tránh tình trạng một tiến trình 
luôn bị bắt buộc giải phóng tài nguyên?
11
61
Tóm tắt
z Khái niệm bế tắc
z Các điều kiện cần để có bế tắc
z Đồ thị phân phối tài nguyên
z Các phương pháp xử lý bế tắc: Ngăn chặn 
và tránh bế tắc (thuật toán đồ thị cấp phát tài 
nguyên và thuật toán banker)
z Khôi phục khi bế tắc đã xảy ra: Kết thúc tiến 
trình và preemption
62
Bài tập
z Thực hiện lại ví dụ phát hiện bế tắc ở trang 
264 trong giáo trình
z Làm bài tập số 7.1 trong giáo trình (trang 
268)
z Làm bài tập số 7.11 trong giáo trình (trang 
270)