1
4. Deadlock
Mô hình h th ngệ ố
Resource Allocation Graph (RAG)
Phương pháp gi i quy t deadlockả ế
Deadlock prevention
Deadlock avoidance
Deadlock detection
Deadlock recovery
2
V n ấđ deadlock trong h th ngề ệ ố
Tình hu ngố: m t t p các process b blocked, m i process gi tài ộ ậ ị ỗ ữ
nguyên và đang ch tài nguyên mà process khác trong t p ờ ậ đang
gi .ữ
Ví dụ
●Gi s h th ng có m t printer và m t DVD drive. Quá trình P1 ả ử ệ ố ộ ộ đang gi ữ
DVD drive, quá trình P2 đang gi printer.ữ
Bây gi P1 yêu c u printer và ph i ờ ầ ả đi, và P2 yêu c u DVD drive và ph i ợ ầ ả
đi.ợ
3
Mô hình hóa h th ngệ ố
H th ng g m các lo i ệ ố ồ ạ tài nguyên, kí hi u ệR1, R2,…, Rm
●Tài nguyên: CPU cycle, không gian b nh , thi t b I/O, file,…ộ ớ ế ị
•M i lo i tài nguyên ỗ ạ Ri có Wi th c thự ể (instance).
Process s d ng tài nguyên theo th tử ụ ứ ự
●Yêu c uầ (request): process ph i ch n u yêu c u không ả ờ ế ầ đưc ợđáp ng ngayứ
●S d ngử ụ (use): process s d ng tài nguyênử ụ
●Hoàn trả (release): process hoàn tr tài nguyênả
Các tác v yêu c u và hoàn tr ụ ầ ả đưc g i qua ợ ọ system call. Ví dụ
●request/release device
●open/close file
●allocate/free memory
4
Đi u ki n c n ề ệ ầ đ x y ra deadlock (1/2)ể ả
B n ốđi u ki n ề ệ c nầ (necessary condition) đ x y ra deadlockể ả
1. Mutual exclusion: m t tài nguyên có th ộ ể đưc c p phát cho ợ ấ
nhi u l m là 1 quá trình (t c là không chia s ề ắ ứ ẻ đưc)ợ
2. Hold and wait: m t quá trình ộđang gi m t tài nguyên ữ ộ đưc ợ
phép yêu c u thêm tài nguyên khác.ầ
5
Đi u ki n c n ề ệ ầ đ x y ra deadlock (2/2)ể ả
3. No preemption: (= no resource preemption) không l y l i tài ấ ạ
nguyên đã c p phát cho quá trình, ngo i tr khi quá trình t ấ ạ ừ ự
hoàn tr nó.ả
4. Circular wait: t n t i m t t p {Pồ ạ ộ ậ 1,…,Pn} các quá trình đang đi ợ
sao cho
P1 đi m t tài nguyên mà Pợ ộ 1 đang giữ
P2 đi m t tài nguyên mà Pợ ộ 2 đang giữ
…
Pn đi m t tài nguyên mà Pợ ộ 0 đang giữ
Đ ý: tài nguyên có th g m nhi u instanceể ể ồ ề
