Chapter 5: Deadlock

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

75
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mỗi tiến trình trong tập hợp đều chờ đợi một sự kiện mà chỉ có một tiến trình khác trong tập hợp mới có thể phát sinh sinh.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chapter 5: Deadlock

Chapter 5: DEADLOCK
Chương 5 : DEADLOCK Nội dung: dung:  Định nghĩa deadlock  Điều kiện để có deadlock  Các phương pháp giải quyết phương Ngăn ngừa deadlock Ngă Tránh deadlock Phát hiện deadlock Phục hồi deadlock  Bài tập 2
 Ví dụ P1 10KB 8KB P2 8KB 4KB spooler P3 3KB 7KB 15KB printer buffer Tắc nghẽn trong giao thông Tắc nghẽn trong quản lý in ấn 3
BÀI TOÁN VỀ 5 TRIẾT GIA ĂN TỐI Năm nhà triết học cùng ngồi ăn tối với món spaghetti nổi tiếng. Mỗi nhà triết học dùng 2 cái nĩa để có thể ăn spaghetti. Nhưng trên bàn chỉ có tổng cộng 5 cái nĩa để xen kẽ với 5 cái đĩa. Nếu 5 nhà triết học đều cầm 5 cái nĩa bên trái cùng lúc, thì sẽ không có ai có cái nĩa bên phải để có thể bắt đầu thưởng thức spaghetti. 4
ĐỊNH NGHĨA  Mỗi tiến trình trong tập hợp đều chờ đợi một sự kiện mà chỉ có một tiến trình khác trong tập hợp mới có thể phát sinh. sinh.  Hay : Mỗi tiến trình trong tập hợp đều chờ được cấp được phát tài nguyên hiện đang bị một quá trình khác cũng ở trạng thái blocked chiếm giữ. giữ.  Một hệ thống bị deadlock : có tiến trình bị deadlock. deadlock. 5
VÍ DỤ & BẢN CHẤT DEADLOCK Hai tiến trình bị deadlock: deadlock: Dạng deadlock: rocess1 Process rocess2 Process P S1 (); P S2 (); R1 R2 P S2 (); P S1 (); Critical Section ritical ection; Critical Section ritical ection; (S1); V (S2); V Process1 Process2 V S2 (); V S1 (); 6
DEADLOCK VÀ TRÌ HOÃN VÔ HẠN ĐỊNH  Deadlock  Đợi sự kiện không bao giờ xảy ra  Nguyên nhân ?  Trì hoãn vô hạn định (Indefinite postponement) postponement)  Đợi sự kiện có thể xảy ra nhưng không xác định như thời điểm  Biểu hiện như deadlock như  Nguyên nhân ?  Deadlock có khác vòng lặp vô hạn ? 7
ĐIỀU KIỆN XẢY RA DEADLOCK 1. Có sử dụng tài nguyên không thể chia sẻ (mutual exclusion) 2. Sự chiếm giữ và yêu cầu thêm tài nguyên (wait for ) 3. Không thu hồi tài nguyên từ tiến trình đang giữ chúng (no-preemption) no-preemption) 4. Tồn tại một chu trình trong đồ thị cấp phát tài nguyên (circular-wait) circular- 8
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN (Resource Allocation Graph)  Process: Process: Pi  Loại tài nguyên với 4 thực thể: thể: Rj Rj  Pi yêu cầu một thực thể của Rj : Pi Rj  Pi đang giữ một thực thể của Rj : Pi Ký hiệu 9
Ví dụ về RAG R1 R3 P1 P2 P3 R2 R4 10
Ví dụ về RAG (tt) R1 R3 P1 P2 P3 Deadlock xảy ra! R2 R4 11
RAG và deadlock  Ví dụ một RAG chứa chu trình nhưng không xảy như ra deadlock: P4 có thể trả lại instance của R2. deadlock: R1 P2 P1 R2 P3 P4 12
RAG và deadlock (tt)  RAG không chứa chu trình (cycle)  không có deadlock  RAG chứa một (hay nhiều) chu trình  Nếu mỗi loại tài nguyên chỉ có một thực thể  deadlock  Nếu mỗi loại tài nguyên có nhiều thực thể  có thể xảy ra deadlock 13
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN (Resource Allocation Graph)  Có thể sử dụng một đồ thị để mô hình hoá việc cấp phát tài nguyên. nguyên. Tiến trình P1 yêu cầu n tài nguyên loại R1 n P1 R1 Tài nguyên P2 đang giữ 1 tài nguyên loại R2 Tài nguyên P2 R2 R1 P1 P2 Một tình huống tắc nghẽn R2 14
CÁC PHƯƠNG PHÁP XỬ LÝ DEADLOK PHƯƠNG Có ba hướng tiếp cận để xử lý tắc nghẽn  Sử dụng phương thức (protocol) để bảo đảm rằng phương hệ thống không bao giờ xảy ra tắc nghẽn. nghẽn.  Cho phép xảy ra tắc nghẽn và tìm cách sửa chữa tắc nghẽn. nghẽn.  Hoàn toàn bỏ qua việc xử lý tắc nghẽn, xem như như hệ thống không bao giờ xảy ra tắc nghẽn. nghẽn. 15
GIẢI QUYẾT DEADLOCK  Ngă Ngăn ngừa deadlock (deadlock prevention)  Qui định cấp, dùng tài nguyênnghiêm ngặt  Không cho các điều kiện deadlock xảy ra  Tránh deadlock (deadlock avoidance)  Vẫn cho các điều kiện deadlock tồn tại  Cấp tài nguyên hợp lý, an toàn  Phát hiện deadlock (deadlock detection)  Phục hồi deadlock (deadlock recovery) 16
NGĂN NGỪA DEADLOCK  Cấm điều kiện tài nguyên không thể chia sẻ (multual-exclusion ) multual-  Cấm điều kiện Sự chiếm giữ và yêu cầu thêm tài nguyên (hold & wait)  Tiến trình yêucầu tất cả tài nguyên một lần  Chỉ được xử lý khi đã đủ tất cả tài nguyên cần thiết được 17
NGĂN NGỪA DEADLOCK  Cấm điều kiện không thu hồi tài nguyên (no-preemption) no-  Nếu yêu cầu tài nguyên không được, tiến trình phải được, giải phóng tất cả tài nguyên đang giữ và yêu cầu lại. lại. (?)  Loại bỏ một chu kỳ (circular-wait) circular-  Sắp xếp tài nguyên theo trật tự và chung cấp cho tiến trình theo đúng trật tự đó. 18
NGĂN NGỪA DEADLOCK (Havender) (Havender)  Ví dụ ieán Tieán eâu Yeâu caàu trình thöïc teá P1 R6, R4, R1 P2 R2, R5, R4 P3 R3, R7, R1 P3 P1 R1 R2 R3 R4 R5 R6 R7 P2  Nhận xét về p/p ngăn ngừa deadlock 19
TRÁNH DEADLOCK Một số khái niệm cơ sở  Trạng thái an toàn. toàn.  Một chuỗi cấp phát an toàn. toàn.  Chiến lược cấp phát. phát.  Giải thuật xác định trạng thái an toàn. toàn.  Giải thuật yêu cầu tài nguyên. nguyên. 20