Bài giảng Hệ điều hành - Chương 3: Deadlock (Lương Minh Huấn)

TRƯỜNG ĐẠI HỌC SÀI GÒN

CHƯƠNG 3: DEADLOCK

GV: Lương Minh Huấn

NỘI DUNG

I. Khái niệm deadlock

II. Điều kiện xảy ra deadlock

III. Các phương pháp phòng tránh deadlock

1. Ngăn chặn deadlock

3. Phát hiện deadlock

2. Phòng tránh deadlock

4. Phục hồi deadlock

I. KHÁI NIỆM DEADLOCK

➢Hệ thống gồm nhiều tiến trình hoạt động đồng thời cùng sử dụng

tài nguyên.

▪ Mỗi loại tài nguyên có nhiều đơn vị (VD: 2 CPU, 5 máy in..)

➢Mỗi tiến trình thường gồm dãy liên tục các thao tác

▪ Tài nguyên cần nhiều loại (VD: CPU, bộ nhớ,..).

dụng bởi tiến trình khác) ) tiến trình yêu cầu phải đợi

▪ Đòi hỏi tài nguyên: Nếu tài nguyên không có sẵn (đang được sử

▪ Giải phóng tài nguyên được cấp

▪ Sử dụng tài nguyên theo yêu cầu (in ấn, đọc dữ liệu...)

I. KHÁI NIỆM DEADLOCK

➢Khi các tiến trình dùng chung ít nhất 2 tài nguyên, hệ thống có thể

gặp "nguy hiểm"

➢Xét ví dụ:

▪ Hệ thống có hai tiến trình P1 & P2

▪ Hai tiến trình P1 & P2 dùng chung hai tài nguyên R1 & R2

▪ R1 được điều độ bởi đèn báo S1 (S1  1)

▪ R2 được điều độ bởi đèn báo S2 (S2  1)

I. KHÁI NIỆM DEADLOCK

➢Hai (hay nhiều) ôtô đối đầu nhau trên 1 cây cầu hẹp chỉ đủ độ rộng

cho 1 chiếc.

➢Mỗi đoạn của cây cầu có thể xem như 1 tài nguyên

➢Nếu deadlock xuất hiện: nó có thể được giải quyết nếu 1 hay 1 số

ôtô lùi lại nhường đường rồi lên sau

I. KHÁI NIỆM DEADLOCK

➢DeadLock là trạng thái trong hệ thống có ít nhất hai tiến trình đang

dừng chờ lẫn nhau và chúng không thể chạy tiếp được.

➢Sự chờ đợi này có thể kéo dài vô hạn nếu không có sự tác động từ

bên ngoài.

II. ĐIỀU KIỆN XẢY RA DEADLOCK

➢Cần có 4 điều kiện sau, không được thiếu điều kiện nào:

➢Có tài nguyên găng:

(muntual exclusion).

• Chỉ có một tiến trình dùng tài nguyên tại một thời điểm

• Tiến trình khác cũng yêu cầu tài nguyên => yêu cầu phải được hõan lại

tới khi tài nguyên được giải phóng.

▪ Tài nguyên được sử dụng theo mô hình không phân chia được

• Tiến trình không được vào đoạn găng phải xếp hàng chờ đợi.

• Trong khi chờ đợi vẫn chiếm giữ các tài nguyên được cung cấp

▪ Chờ đợi trước khi vào đoạn găng (hold and wait).

II. ĐIỀU KIỆN XẢY RA DEADLOCK

• Tài nguyên không thể được trưng dụng

• Tài nguyên được giải phóng chỉ bởi tiến trình đang chiếm giữ khi đã

hoàn thành nhiệm vụ.

▪ Không có hệ thống phân phối lại tài nguyên găng (no preemption)

▪ Chờ đợi vòng tròn (circular wait): tồn tại 1 chu kỳ đóng các yêu cầu

• Tạo ra chu kỳ không kết thúc được.

tài nguyên.

ĐỒ THỊ CUNG CẤP TÀI NGUYÊN

➢Dùng để mô hình hóa tình trạng bế tắc trong hệ thống

➢Là đồ thị định hướng gồm tập đỉnh V và tập cung E

➢Tập đỉnh V được chia thành 2 kiểu đỉnh:

▪ P = {P1; P2; …; Pn} Tập chứa tất cả các tiến trình trong hệ thống

▪ R = {R1; R2;…; Rm} Tập chứa tất cả các kiểu tài nguyên trong hệ

➢Tập các cung E gồm 2 loại:

thống.

▪ Cung sử dụng: đi từ tài nguyên Rj tới tiến trình Pi : Rj → Pi

▪ Cung yêu cầu: đi từ tiến trình Pi tới tài nguyên Rj : Pi → Rj

ĐỒ THỊ CUNG CẤP TÀI NGUYÊN

➢Khi một tiến trình Pi yêu cầu tài nguyên Rj

1. Cung yêu cầu Pi → Rj được chèn vào đồ thị

dụng Rj → Pi

2. Nếu yêu cầu được thỏa mãn, cung yêu cầu chuyển thành cung sử

3. Khi tiến trình Pi giải phóng tài nguyên Rj , cung sử dụng Rj → Pi

bị xóa khỏi đồ thị

ĐỒ THỊ CUNG CẤP TÀI NGUYÊN

➢Đồ thị không chứa chu trình, không deadlock

➢Nếu đồ thị chứa đựng chu trình

▪ Nếu tài nguyên có nhiều hơn 1 đơn vị: có khả năng deadlock

▪ Nếu tài nguyên chỉ có 1 đơn vị => deadlock

III. CÁC PHƯƠNG PHÁP XỬ LÝ BẾ TẮC

➢Ngăn ngừa

▪ Áp dụng các biện pháp để đảm bảo hệ thống không bao giờ rơi vào

▪ Tốn kém

tình trạng deadlock.

▪ Áp dụng cho hệ thống hay xảy ra deadlock và tổn thất do deadlock

gây ra lớn.

III. CÁC PHƯƠNG PHÁP XỬ LÝ BẾ TẮC

➢Phòng tránh

▪ Kiểm tra từng yêu cầu tài nguyên của tiến trình và không chấp nhận yêu cầu nếu việc cung cấp tài nguyên có khả năng dẫn đến tình trạng deadlock.

▪ Thường yêu cầu các thông tin phụ trợ

▪ Áp dụng cho hệ thống ít xảy ra deadlock nhưng tổn hại lớn

III. CÁC PHƯƠNG PHÁP XỬ LÝ BẾ TẮC

➢Nhận biết và khắc phục:

▪ Cho phép hệ thống hoạt động bình thường => có thể rơi vào tình

▪ Định kỳ kiểm tra xem deadlock có đang xảy ra không.

trạng deadlock,

▪ Nếu đang deadlock, áp dụng các biện pháp loại bỏ deadlock.

▪ Áp dụng cho hệ thống ít xảy ra deadloc và thiệt hại không lớn.

III.1 NGĂN NGỪA DEADLOCK

➢Nguyên tắc: tác động vào 1 trong 4 điều kiện cần của deadlock để

nó không xảy ra.

▪ Chờ đợi trước khi vào đoạn găng

▪ Tài nguyên găng

▪ Trưng dụng tài nguyên găng

▪ Chờ đợi vòng tròn.

III.1 NGĂN NGỪA DEADLOCK

➢Giảm tài nguyên găng

➢Giảm bớt mức độ găng của hệ thống

▪ Tài nguyên không phân chia được: sử dụng không đồng thời

➢Kỹ thuật SPOOL(Simultaneous peripheral operation on-line)

▪ Không phân phối tài nguyên khi không thực sự cần thiết

▪ Tài nguyên phân chia được (file chỉ đọc): sử dụng đồng thời

▪ Chỉ một số ít tiến trình có khả năng yêu cầu tài nguyên

III.1 NGĂN NGỪA DEADLOCK

➢Điều kiện chờ đợi trước khi vào gang

➢Nguyên tắc: đảm bảo một tiến trình xin tài nguyên chỉ khi không

sở hữu bất kỳ tài nguyên nào khác.

➢Cung cấp trước

▪ Tiến trìnhh xin toàn bộ tài nguyên ngay từ đầu và chỉ thực hiện khi

▪ Hiệu quả sử dụng tài nguyên thấp

• Tiến trình chỉ sử dụng tài nguyên ở giai đọan cuối?

• Tổng số tài nguyên đòi hỏi vượt quá khả năng của hệ thống?

đã có đầy đủ tài nguyên

III.1 NGĂN NGỪA DEADLOCK

➢Giải phóng tài nguyên

▪ Tiến trình giải phóng tất cả tài nguyên trước khi xin (xin lại ) tài

▪ Nhận xét

• Tốc độ thực hiện tiến trình chậm

• Phải đảm bảo dữ liệu được giữ trong tài nguyên tạm giải phóng không

bị mất

nguyên mới

III.1 NGĂN NGỪA DEADLOCK

➢Ngăn chặn không thể thu hồi

➢Nếu process A có giữ tài nguyên và đang yêu cầu tài nguyên khác

nhưng tài nguyên này chưa cấp phát ngay được thì:

▪ Cách 1: Hệ thống lấy lại mọi tài nguyên mà A đang giữ

• A chỉ bắt đầu lại được khi có được các tài nguyên đã bị lấy lại cùng với

tài nguyên đang yêu cầu.

III.1 NGĂN NGỪA DEADLOCK

• Nếu tài nguyên được giữ bởi một process khác đang đợi thêm tài nguyên, tài nguyên này được hệ thống lấy lại và cấp phát cho A.

• Nếu tài nguyên được giữ bởi process không đợi tài nguyên, A phải đợi và tài nguyên của A bị lấy lại. Tuy nhiên hệ thống chỉ lấy lại các tài nguyên mà process khác yêu cầu

▪ Cách 2: Hệ thống sẽ xem tài nguyên mà A yêu cầu

III.1 NGĂN NGỪA DEADLOCK

➢Ngăn chặn chờ đợi vòng tròn.

➢Sắp xếp thứ tự cho tất cả loại tài nguyên và đòi hỏi mỗi tiến trình

phải yêu cầu tài nguyên theo thứ tự đó.

➢Ví dụ, một tiến trình muốn dùng ổ đĩa và máy in tại cùng một lúc thì trước tiên phải yêu cầu ổ đĩa, nếu được cấp ổ đĩa thì mới yêu cầu máy in.

III.2 PHÒNG TRÁNH DEADLOCK

➢ Tránh tắc nghẽn (Deadlock Avoidance) đòi hỏi hệ điều hành có trước thông tin bổ sung liên quan đến tài nguyên mà một tiến trình sẽ yêu cầu và sử dụng trong suốt quá trình thực thi.

cần.

➢ Yêu cầu mỗi tiến trình khai báo số lượng tối đa mỗi loại tài nguyên mà nó

➢ Giải thuật tránh tắc nghẽn sẽ kiểm tra trạng thái cấp phát tài nguyên (resource - allocationstate) để bảo đảm hệ thống không rơi vào deadlock.

➢ Trạng thái cấp phát tài nguyên được định nghĩa dựa trên số tài nguyên còn lại, số tài nguyên đã được cấp phát và yêu cầu tối đa của các process.

III.2 PHÒNG TRÁNH DEADLOCK

➢Trạng thái an toàn (safe) là trạng thái trong đó hệ thống có thể

thỏa mãn tất cả các nhu cầu tài nguyên của mỗi tiến trình theo một thứ tự nào đó mà vẫn không xảy ra tắc nghẽn. Thứ tự này còn gọi là thứ tự an toàn (chuỗi an toàn).

➢Một trạng thái của hệ thống được gọi là không an toàn (unsafe)

nếu không tồn tại một chuỗi an toàn.

III.2 PHÒNG TRÁNH DEADLOCK

➢Nếu hệ thống ở trạng thái an toàn => không có deadlock.

➢Nếu hệ thống ở trạng thái không an toàn => có thể có deadlock.

➢Sự tránh khỏi deadlock => đảm bảo rằng hệ thống sẽ không bao

giờ bước vào trạng thái không an toàn:

▪ Mỗi loại tài nguyên có 1 instance: giải thuật đồ thị phân phối tài

▪ Mỗi loại tài nguyên có nhiều instance: giải thuật chủ nhà bang

nguyên.

(banker).

III.2 PHÒNG TRÁNH DEADLOCK

➢Thuật toán đồ thị phân phối tài nguyên:

➢Sử dụng khi mỗi kiểu tài nguyên chỉ có 1 đơn vị (instance)

▪ Có chu trình, sẽ có deadlock

➢Thêm vào đồ thị loại cung mới: cung đòi hỏi Pi → Rj

▪ Cho biết Pi có thể yêu cầu Rj trong tương lai

▪ Cùng hướng với cung yêu cầu, thể hiện trong đồ thị 

III.2 PHÒNG TRÁNH DEADLOCK

➢Tiến trình khi tham gia hệ thống, phải thêm tất cả các cung đòi hỏi

tương ứng vào đồ thị

▪ Khi Pi yêu cầu Rj , cung đòi hỏi Pi  Rj chuyển thành cung yêu cầu

Pi → Rj

▪ Khi Pi giải phóng Rj , cung sử dụng Rj → Pi chuyển thành cung đòi

hỏi Pi  Rj

III.2 PHÒNG TRÁNH DEADLOCK

➢Thuật toán: yêu cầu tài nguyên Rj của tiến trình Pi được thỏa mãn chỉ khi việc chuyển cung yêu cầu Pi → Rj thành cung sử dụng Rj → Pi không tạo chu trình trên đồ thị.

▪ Không chu trình: Hệ thống an toàn

▪ Có chu trình: Việc cung cấp tài nguyên đẩy hệ thống vào tình trạng

không an toàn

III.2 PHÒNG TRÁNH DEADLOCK

➢ Giải thuật nhà băng:

➢ Khi tiến trình mới đưa vào hệ thống, nó phải khai báo số tối đa các đơn vị của mỗi loại tài nguyên mà nó cần. Số này có thể không vượt quá tổng số tài nguyên trong hệ thống.

➢ Khi một tiến trình yêu cầu cấp phát tài nguyên, hệ thống phải xác định sau khi cấp phát các tài nguyên này hệ thống có vẫn ở trong trạng thái an toàn hay không.

▪ Nếu trạng thái hệ thống sẽ vẫn là an toàn, tài nguyên sẽ được cấp

▪ Ngược lại, tiến trình phải chờ cho tới khi một vài tiến trình giải phóng đủ tài

nguyên.

➢ Giải thuật nhà băng dung để xác định trạng thái hiện tại có an toàn hay không?

III.2 PHÒNG TRÁNH DEADLOCK

➢Bước1: Từ bảng trạng thái lập bảng nhu cầu trong đó thay cột Max bằng cột Cần với công thức tính toán Cần= Max – Chiếm. Cột Cần thể hiện số lượng mỗi loại tài nguyên cần cung cấp thêm cho mỗi tiến trình.

➢Bước2:

III.2 PHÒNG TRÁNH DEADLOCK

While i: (Cần(Pi)<>0) and (Cần(Pi)<=Còn)

Begin

Còn= Còn+Chiếm(Pi);

Cần(Pi)=0; Chiếm(Pi)=0;

End

➢If i: Cần(Pi)=0

Then “Trạngtháian toàn”

Else “Trạngtháikhôngan toàn”

III.2 PHÒNG TRÁNH DEADLOCK

if Not(Request(P)<= Còn) Then

“Khôngcấpđược”

Else

Begin

1. Lập bảng trạng thái sau khi cấp tài nguyên cho P:

Còn= Còn–Request(P);

Chiếm(P)= Chiếm(P)+ Request(P);

Max(P)=Max(P);

Các số liệu ứng với các tiến trình khác giữ nguyên;

2. Kiểm tra trạng thái trên có an toàn không

3. If (An toàn) then “Cấp ngay” else “Khôngcấpngay”

end

III.2 PHÒNG TRÁNH DEADLOCK

III.3 PHÁT HIỆN DEADLOCK

➢Nguyên tắc

▪ Không áp dụng các biện pháp ngăn ngừa hoặc phòng tránh, để cho

▪ Định kỳ kiểm tra xem deadloc có đang xảy ra không. Nếu có tìm

deadlock xảy ra.

cách khắc phục

• Thuật toán xác định hệ thống đang deadlock không

• Thuật toán chứa deadlock,

▪ Để thực hiện, hệ thống phải cung cấp

III.3 PHÁT HIỆN DEADLOCK

➢Nhận biết deadlock

▪ Thuật toán dựa trên đồ thị cung cấp tài nguyên

▪ Thuật toán chỉ ra deadlock tổng quát

➢Khắc phục deadlock

▪ Kết thúc tiến trình

▪ Trưng dụng tài nguyên

III.3 PHÁT HIỆN DEADLOCK

➢Thuật toán dựa trên đồ thị cung cấp tài nguyên:

➢Áp dụng khi mỗi tài nguyên trong hệ thống có một đơn vị.

➢Kiểm tra hệ thống có deadloc bằng cách kiểm tra chu trình trên đồ

thị

▪ Nếu trên đồ thị có chu trình, hệ thống đang deadlock.

➢Định kỳ gửi tới các thuật toán kiểm tra chu trình trên đồ thị

▪ Thuật toán đòi hỏi n2 thao tác (n: số đỉnh của đồ thị)

III.3 PHÁT HIỆN DEADLOCK

➢Sử dụng đồ thị chờ đợi - phiên bản thu gọn của đồ thị cung cấp tài

nguyên

▪ Cung chờ đợi Pi → Pj : Tiến trình Pi đang đợi tiến trình Pj giải

▪ Chỉ có các đỉnh dạng tiến trình

phóng tài nguyên Pi cần

▪ Cung chờ đợi Pi → Pj tồn tại trên đồ thị đợi khi và chỉ khi trên đồ thị phân phối tài nguyên tương ứng tồn tại đồng thời cung yêu cầu Pi → R và cung sử dụng R → Pj