Bài giảng môn Hệ điều hành - Chương 4: Deadlock & xử lý

 1 tài nguyên thì khi 1 
process Pi nào ₫ó ₫ang chiếm giữ tài nguyên Rj thì không có
process nào khác có thể truy xuất Rj nữa (nguyên tắc loại trừ 
tương hỗ). Như vậy, nếu process Pj cần truy xuất Rj, nó buộc phải 
dừng chờ process Pi trả tài nguyên Rj, ta nói trong trường hợp 
này, Pj phụ thuộc Pi.
ƒ Ý tưởng cơ bản của giải thuật phát hiện deadlock ₫ơn giản là hệ
thống sẽ xây dựng và quản lý ₫ồ thị miêu tả sự phụ thuộc giữa 
các process theo thời gian. Đồ thị này có các thành phần sau : 
mỗi process hay mỗi tài nguyên là 1 nút của ₫ồ thị, cung có 
hướng từ nút i ₫ến j miêu tả phần tử i phụ thuộc phần tử j.
Giải thuật phát hiện deadlock ₫ơn giản 
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 7
Chương 4 : Deadlockvà xử lý
Giải thuật phát hiện deadlock ₫ơn giản 
Tài nguyên R1 
₫ang bị
P1 truy 
xuất (chiếm giữ)
Process P2 ₫ang dừng chờ
tài 
nguyên R2 (₫ang bị
chiếm giữ
 bởi process khác)
P1
R1
P2
R2
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 8
Chương 4 : Deadlockvà xử lý
Giải thuật phát hiện deadlock ₫ơn giản 
‰ Thí dụ có 2 process P1 và P2 ₫ang chạy, theo giải thuật process 
P1 sẽ truy xuất tài nguyên R1 rồi R2, trong khi ₫ó process P2 sẽ
truy xuất R2 rồi R1 với tiến ₫ộ thời gian cụ thể như sau :
ƒ tại t1 : process P1 xin truy xuất R1 ⇒ OK ⇒ hệ thống vẽ 1 cung 
từ R1 tới P1 và cho P1 chạy tiếp.
ƒ tại t2 : process P2 xin truy xuất R2 ⇒ OK ⇒ hệ thống vẽ 1 cung 
từ R2 tới P2 và cho P2 chạy tiếp.
ƒ tại t3 : process P1 xin truy xuất R2 (₫ang bị P2 chiếm giữ) ⇒ hệ
thống vẽ 1 cung từ P1 tới R2 và bắt P1 dừng ₫ợi process P2.
ƒ tại t4 : process P2 xin truy xuất R1 (₫ang bị P1 chiếm giữ) ⇒ hệ
thống vẽ 1 cung từ P2 tới R1 và bắt P2 dừng ₫ợi process P1.
ƒ từ t4 trở ₫i : ₫ã xuất hiện vòng kép kín chứa 2 process P1 và P2 ⇒
2 process P1 và P2 ₫ều bị dừng vì phải chờ lẫn nhau và chúng 
không bao giờ chạy ₫ược nữa ⇒ deadlock.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 9
Chương 4 : Deadlockvà xử lý
Giải thuật phát hiện deadlock ₫ơn giản
P1
P2
R1 R2
t1
t2
t3
t4
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 10
Chương 4 : Deadlockvà xử lý
Trạng thái sử
dụng các tài nguyên của các process tại từng thời 
₫iểm ₫ược xác ₫ịnh bởi 4 thông số sau ₫ây :
ƒ vector miêu tả số lượng tài nguyên tổng thể ₫ã ₫ược gắn vào máy 
E(E1, E2,...,Em), trong ₫ó Ei là số lượng tài nguyên loại i mà hệ
thống ₫ược trang bị. Như vậy vector E là hằng số trong lúc hệ
thống hoạt ₫ộng (ta không ₫ược phép gắn/gở tài nguyên trong lúc 
máy ₫ang vận hành). 
ƒ vector miêu tả số lượng tài nguyên chưa dùng (₫ang rãnh) A(A1, 
A2,...,Am), trong ₫ó Ai là số lượng tài nguyên loại i còn ₫ang rãnh. 
Như vậy, vector A ≤ E theo nghĩa ∀j, Aj ≤ Ej. 
4.5 Giải thuật phát hiện deadlock tổng quát
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 11
Chương 4 : Deadlockvà xử lý
ƒ ma trận C miêu tả số lượng tài nguyên thuộc từng loại ₫ã ₫ược cấp 
phát cho các process (giả sử có n process và m loại tài nguyên 
khác nhau) : 
4.5 Giải thuật phát hiện deadlock tổng quát
C11 C12 C13 ... C1m
C21 C22 C23 ... C2m
.
.
.
.
.
.
.
.
.
.
Cn1 Cn2 Cn3 ... Cnm
Phần tử
Cij miêu tả
số lượng tài nguyên loại j ₫ang bị
process i 
chiếm giữ.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 12
Chương 4 : Deadlockvà xử lý
ƒ ma trận R miêu tả số lượng tài nguyên thuộc từng loại ₫ang ₫ược 
các process xin thêm nhưng chưa ₫ược cấp phát (vì chưa có
sẵn!) : 
4.5 Giải thuật phát hiện deadlock tổng quát
R11 R12 R13 ... R1m
R21 R22 R23 ... R2m
.
.
.
.
.
.
.
.
.
.
Rn1 Rn2 Rn3 ... Rnm
Phần tử
Rij miêu tả
số lượng tài nguyên loại j ₫ang ₫ược 
process i xin thêm nhưng chưa ₫ược cấp phát.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 13
Chương 4 : Deadlockvà xử lý
Ej = Aj + ∑
=
n
1i
ijC
4.5 Giải thuật phát hiện deadlock tổng quát
Số
tài nguyên 
tổng thể
loại j
Số
tài nguyên 
loại j còn rãnh
Tổng Số
tài nguyên 
loại j ₫ang bị
n process 
chiếm giữ
= +
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 14
Chương 4 : Deadlockvà xử lý
BOOL deadlock[n]; // = 0 : chua deadlock, = 1 : bi deadlock
int E[m]; // bản sao vector E của hệ
thống
Int A[m];
// bản sao vector A của hệ
thống
int C[n][m];
// bản sao vector E của hệ
thống
int R[n][m];
// bản sao vector E của hệ
thống
4.5 Giải thuật phát hiện deadlock tổng quát
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 15
Chương 4 : Deadlockvà xử lý
// dung timer ₫ịnh ky tao ngăt ₫ø̉
chay thu tuc nay
void Deadlock_Detection(void) {
int i;
//1. khơi ₫úng cac process ₫ø̀u bị deadlock
for (i=0; i<n; i++) deadlock[i] = 1;
//2. Lặp těm process i chay ₫ươc
while (i=FindProcess()) >=0) { // co
process chay ₫ươc
deadlock[i] = 0;
for (j = 0; j<m;j++) A[j] += C[i][j];
}
//3. kiø̉m tra co
deadlock khúng
for (i=0; i<n,i++) if (deadlock[i] ==1) break;
if (i>=n) return; // khúng co deadlock
// co
deadlock, giai quyǿt
....
}
4.5 Giải thuật phát hiện deadlock tổng quát
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 16
Chương 4 : Deadlockvà xử lý
// Těm 1 process co thø̉ chay ₫ươc
int FindProcess(void) {
for (i=0; i<n;i++)
if (deadlock[i]==1 && lessequal(R,i,A)) return i;
// khúng těm ₫ươc process co thø̉ chay tiǿp
return -1;
}
// Kiø̉m tra hang i cua ma trön C co
nho hơn hay băng vector A
BOOL lessequal(C,i,A) {
for (j=0;j A[j]) return FALSE;
return TRUE;
}
4.5 Giải thuật phát hiện deadlock tổng quát
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 17
Chương 4 : Deadlockvà xử lý
Chữa trị
deadlock :
ƒ dùng cơ chề "Preemption" tài nguyãn có liên quan : không 
tổng quát vì không khả thi nếu tài nguyêôn liên quan là tài 
nguyên dạng “non-preemptive”.
ƒ giết 1 hay n process rồi cho chúng chạy lại từ ₫ầu : chọn 
process nào ₫ể giết? Giết process sẽ làm mất tính nhất quán 
dữ liệu (vì bị process hiệu chỉnh 1 phần rồi).
ƒ rollback process về checkpoint thích hợp : tốn bộ nhớ lưu trữ
trạng thái process ở những checkpoint.
4.5 Giải thuật phát hiện deadlock tổng quát
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 18
Chương 4 : Deadlockvà xử lý
4.6 Chiến lược né
tránh deadlock
Né
tránh deadlock :
ƒ ₫ể hệ thống hoạt ₫ộng tự do, chỉ khi cần cấp phát tài nguyên 
cho process thì phải cẩn thận : tiên tri xem nếu cấp phát thì có
dẫn hệ thống ₫ến deadlock không ? Nếu có thì không cấp phát 
(cho process xin cấp phát ngủ chờ), nều không thì cấp phát tài 
nguyên bình thường.
ƒ Trạng thái an toàn là trạng thái mà ở ₫ó chưa có deadlock và
tồn tại ít nhất 1khả năng chạy các process sao cho chúng hoàn 
tất chức năng. Ngược lại ta nói hệ thống ₫ang ở trạng thái không 
an toàn.
ƒ Như vậy, trạng thái bắt ₫ầu của hệ thống (E0,A0,C0,R0) là trạng 
thái an ntoàn.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 19
Chương 4 : Deadlockvà xử lý
4.6 Chiến lược né
tránh deadlock
ƒ Nếu hệ thống ₫ang ở trạng thái an toàn (Ei,Ai,Ci,Ri), nếu có
process giải phóng tài nguyên thì hệ thống sẽ chuyển ₫ến trạng 
thái (Ei+1,Ai+1,Ci+1,Ri+1), an toàn hơn ⇒ không cần kiểm tra 
trường hợp này.
ƒ Nếu hệ thống ₫ang ở trạng thái an toàn (Ei,Ai,Ci,Ri), nếu có
process xin cấp phát tài nguyên thì hệ thống sẽ chuyển ₫ến 
trạng thái (Ei+1,Ai+1,Ci+1,Ri+1), trạng thái này có thể an toàn 
hoặc không an toàn ⇒ cần kiểm tra cẩn thận trường hợp này : 
dùng thuật giải phát hiện deadlock trên trạng thái 
(Ei+1,Ai+1,Ci+1,Ri+1) xem có bị deadlock không? Nếu có thì
không cấp phát (cho process xin cấp phát ngủ chờ), nếu không 
thì cấp phát tài nguyên bình thường.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 20
Chương 4 : Deadlockvà xử lý
4.7 Chiến lược ₫ề
phòng deadlock
Tìm cách cấp phát tài nguyên sao cho về
nguyên tắc không thể
gây 
ra deadlock về
sau :
ƒ Ngừa nguyên nhân 1 : ₫ừng tạo cơ hội cho các process phải 
loại trừ tương hỗ lẫn nhau khi thi hành ₫oạn code CS truy xuất 
tài nguyên dùng chung, thí dụ dùng kỹ thuật 'Spooling' máy in. 
Kỹ thuật này không có tính tổng quát cao vì không thích hợp 
cho mọi tài nguyên.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 21
Chương 4 : Deadlockvà xử lý
4.7 Chiến lược ₫ề
phòng deadlock
Ngừa nguyên nhân 2 : ₫ừng ₫ể
process giữ
tài nguyên cũ (₫ang 
chiếm giữ) khi xin và
chờ
tài nguyên mới : 
ƒ cho mỗi process dùng ₫úng 1 tài nguyên, như vậy nếu process 
₫ang xin tài nguyên mà chưa cấp phát thì không process nào 
chờ nó cả, còn nếu process ₫ã ₫ược cấp phát tài nguyên, nó 
không ₫ược xin thêm nên không thể chờ process khác ₫ược. 
ƒ cho mỗi process dùng tự do n tài nguyên, nhưng phải xin toàn 
bộ 1 lần, không ₫ược xin nhiều lần ⇒ cũng không gây ra việc 
các process chờ vòng lẫn nhau.
ƒ cho mỗi process dùng tự do n tài nguyên và ₫ược phép xin nhiều 
lần theo yêu cầu của thuật giải riêng, nhưng mỗi lần xin tài 
nguyên mới, process phải trả lại tất cả các tài nguyên ₫ang 
chiếm giữ rồi xin lại cùng với tài nguyên mới ⇒ cũng không gây 
ra việc các process chờ vòng lẫn nhau.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ ₫iều hành
Slide 22
Chương 4 : Deadlockvà xử lý
4.7 Chiến lược ₫ề
phòng deadlock
ƒ Ngừa nguyên nhân 3 : ₫ừng sử dụng tài nguyên dạng "No 
preemptive" ⇒ không khả thi.
ƒ Ngừa nguyên nhân 4 : ₫ừng ₫ể các process tạo vòng chờ khép 
kín : ₫ánh số thứ tự các tài nguyên rồi yêu cầu các process phải 
xin cấp phát các tài nguyên theo thứ tự xác ₫ịnh (tăng dần hay 
giảm dần). Vấn ₫ề là ₫ánh số các tài nguyên theo thứ tự nào cho 
hợp lý ₫ể mọi process ₫ều có thể hoạt ₫ộng theo thuật giải riêng 
của mình?