Chapter 5: Deadlock

Chapter 5: DEADLOCK 2Chương 5 : DEADLOCK Nội dung:  Định nghĩa deadlock  Điều kiện để có deadlock  Các phương pháp giải quyết Ngăn ngừa deadlock Tránh deadlock Phát hiện deadlock Phục hồi deadlock  Bài tập 315KB buffer 8KB 4KB 3KB printer 10KB 8KB 7KB P1 P2 P3 spooler Tắc nghẽn trong giao thông Tắc nghẽn trong quản lý in ấn Ví dụ 4Nă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. BÀI TOÁN VỀ 5 TRIẾT GIA ĂN TỐI 5 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.  Hay : Mỗi tiến trình trong tập hợp đều chờ được cấp 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ữ.  Một hệ thống bị deadlock : có tiến trình bị deadlock. ĐỊNH NGHĨA 6VÍ DỤ & BẢN CHẤT DEADLOCK Hai tiến trình bị deadlock: rocessPP 11 (P SP S11); (P SP S22); riticalCC ectionSS ; (V SV S11); (V SV S22); rocessPP 22 (P SP S22); (P SP S11); riticalCC ectionSS ; (V SV S22); (V SV S11); Process1 R1 Process2 R2 Dạng deadlock: 7DEADLOCK 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) Đợi sự kiện có thể xảy ra nhưng không xác định thời điểm Biểu hiện như deadlock Nguyên nhân ?  Deadlock có khác vòng lặp vô hạn ? 8Đ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) 4. Tồn tại một chu trình trong đồ thị cấp phát tài nguyên (circular-wait) 9ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN (Resource Allocation Graph)  Process:  Loại tài nguyên với 4 thực thể:  Pi yêu cầu một thực thể của Rj :  Pi đang giữ một thực thể của Rj : Pi Pi Pi Rj Rj Rj Ký hiệu 10 Ví dụ về RAG R1 R3 P1 P2 P3 R2 R4 11 Ví dụ về RAG (tt) R1 R3 P1 P2 P3 R2 R4 Deadlock xảy ra! 12 RAG và deadlock  Ví dụ một RAG chứa chu trình nhưng không xảy ra deadlock: P4 có thể trả lại instance của R2. R1 P1 P2 P3R2 P4 13 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 14 ĐỒ 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. Tiến trình Tài nguyên P1 yêu cầu n tài nguyên loại R1 P1 n R1 P2 R2 P2 đang giữ 1 tài nguyên loại R2Tài nguyên P1 P2 R1 R2 Một tình huống tắc nghẽn 15 CÁC PHƯƠNG PHÁP XỬ LÝ DEADLOK 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 hệ thống không bao giờ xảy ra tắc 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.  Hoàn toàn bỏ qua việc xử lý tắc nghẽn, xem như hệ thống không bao giờ xảy ra tắc nghẽn. 16 GIẢI QUYẾT DEADLOCK  Ngăn ngừa deadlock (deadlock prevention) Qui định cấp, dùng tài nguyên nghiê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) 17 NGĂN NGỪA DEADLOCK  Cấm điều kiện tài nguyên không thể chia sẻ (multual-exclusion )  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êu cầ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 18 NGĂN NGỪA DEADLOCK  Cấm điều kiện không thu hồi tài nguyên (no-preemption) Nếu yêu cầu tài nguyên không được, tiến trình phải giải phóng tất cả tài nguyên đang giữ và yêu cầu lại. (?)  Loại bỏ một chu kỳ (circular-wait) 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ự đó. 19 NGĂN NGỪA DEADLOCK (Havender)  Ví dụ TTieán trình YYeâu caàu thöïc teá P1P1 , ,R6 R4 R16 4 1 P2P2 , ,R2 R5 R42 5 4 P3P3 , ,R3 R7 R13 7 1 R1 R5R2 R3 R4 R6 R7 P2 P1 P3  Nhận xét về p/p ngăn ngừa deadlock 20 Một số khái niệm cơ sở  Trạng thái an toàn.  Một chuỗi cấp phát an toàn.  Chiến lược cấp phát.  Giải thuật xác định trạng thái an toàn.  Giải thuật yêu cầu tài nguyên. TRÁNH DEADLOCK 21 Trạng thái safe và unsafe  Một trạng thái của hệ thống được gọi là an toàn (safe) nếu tồn tại một chuỗi an toàn (safe sequence). 22 Chuỗi an toàn  Một chuỗi quá trình là một chuỗi an toàn nếu Với mọi i = 1,…,n, yêu cầu tối đa về tài nguyên của Pi có thể được thỏa bởi  tài nguyên mà hệ thống đang có sẵn sàng (available)  cùng với tài nguyên mà tất cả Pj , j < i, đang giữ.  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. 23 Chuỗi an toàn (tt) Ví dụ: Hệ thống có 12 tape drives và 3 quá trình P0, P1, P2  Tại thời điểm t0 Còn 3 tape drive sẵn sàng. Chuỗi là chuỗi an toàn  hệ thống là an toàn PP 00 1010 55 PP 11 44 22 PP 22 99 22 cần tối đa đang giữ 24 Chuỗi an toàn (tt)  Giả sử tại thời điểm t1, P2 yêu cầu và được cấp phát 1 tape drive còn 2 tape drive sẵn sàng • Hệ thống trở nên không an toàn. PP 00 1010 55 PP 11 44 22 PP 22 99 33 cần tối đa đang giữ 25  Khi một process yêu cầu một tài nguyên đang sẵn sàng, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay. 26 Trạng thái safe/unsafe và deadlock  Nếu hệ thống đang ở trạng thái safe  không deadlock.  Nếu hệ thống đang ở trạng thái unsafe  có thể dẫn đến deadlock.  Tránh deadlock bằng cách bảo đảm hệ thống không đi đến trạng thái unsafe. safe unsafedeadlock 27 TRÁNH DEADLOCK Giải thuật banker  Áp dụng cho hệ thống cấp phát tài nguyên trong đó mỗi loại tài nguyên có thể có nhiều instance.  Bắt chước nghiệp vụ ngân hàng (banking) 28 TRÁNH DEADLOCK  Giải thuật nhà băng (Banker’s Algorithm) Hệ điều hành = nhà Băng Tiến trình = khách hàng Tài nguyên = vốn vay  Ràng buộc Yêu cầu vay cực đại  vốn nhà băng Khách không trả vốn nếu vay chưa đủ yêu cầu cực đại Khi vay đủ, khách phải trả đủ vốn sau thời gian hữu hạn 29 TRÁNH DEADLOCK  Trạng thái nhà băng An toàn (Safe): thỏa yêu cầu mọi khách, ngân hàng thu vốn đủ Không an toàn ( Unsafe) : ngược lại  có thể deadlock  Hệ thống phải cấp phát tài nguyên sao cho không rơi vào trạng thái Unsafe 30 VÍ DỤ  Trạng thái sau là an toàn. Tại sao ? Ñang möôïn CCaàn toái ña CCaàn theâm P1P1 11 44 33 P2P2 44 66 22 P3P3 55 88 33 VVoán 12 12 , coøn laïi 22 31 VÍ DỤ Ñang möôïn CCaàn toái ña CCaàn theâm P1P1 88 1010 22 P2P2 22 55 33 P3P3 11 33 22 VVoáân 12 12 , coøn laïi 11  Trạng thái sau là không an toàn. Tại sao ? 32 Giải thuật kiểm tra trạng thái an toàn – Ví dụ  Có 5 process P0 ,…, P4  Có 3 loại tài nguyên: A (có 10 instance), B (5 instance) và C (7 instance).  Sơ đồ cấp phát trong hệ thống tại thời điểm T0 llocationAA axM vailableAA eedN AA BB CC AA BB CC AA BB CC AA BB CC PP 00 00 11 00 77 55 33 33 33 22 77 44 33 PP 11 22 00 00 33 22 22 11 22 22 PP 22 33 00 22 99 00 22 66 00 00 PP 33 22 11 11 22 22 22 00 11 11 PP 44 00 00 22 44 33 33 44 33 11      33 GT kiểm tra trạng thái an toàn – Vd (tt) Allocation Need Work A B C A B C A B C P0 0 1 0 7 4 3 3 3 2 P1 2 0 0 1 2 2 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 Chuỗi an toàn 7 4 3 7 4 5 10 4 7 10 5 7 5 3 2 34 GT cấp phát tài nguyên – Ví dụ  Yêu cầu (1, 0, 2) của P1 có thỏa được không?  Kiểm tra điều kiện Request1  Available:  (1, 0, 2)  (3, 3, 2) là đúng  Giả định thỏa yêu cầu, kiểm tra trạng thái mới có phải là safe hay không.  Trạng thái mới là safe (chuỗi an toàn là ), vậy có thể cấp phát tài nguyên cho P1. llocationAA eedN vailableAA AA BB CC AA BB CC AA BB CC PP 00 00 11 00 77 44 33 22 33 00 PP 11 33 00 22 00 22 00 PP 22 33 00 22 66 00 00 PP 33 22 11 11 00 11 11 PP 44 00 00 22 44 33 11 35 GT cấp phát tài nguyên – Ví dụ (tt)  P4 yêu cầu (3, 3, 0) hoặc P0 yêu cầu (0, 2, 0) thì có thỏa mãn được hay không? 36 PHÁT HIỆN DEADLOCK  Ghi nhận, theo dõi yêu cầu, sự cấp phát tài nguyên cho các quá trình.  Dùng đồ thị cấp phát tài nguyên. Tiến trình Tài nguyên P1 yêu cầu n tài nguyên loại R1 P1 n R1 P2 R2 P2 đang giữ 1 tài nguyên loại R2 Tài nguyên 37 PHÁT HIỆN DEADLOCK  Giản lược đồ thị cấp phát 1. Tài nguyên rảnh cấp cho quá trình yêu cầu 2. Quá trình đủ tài nguyên xoá mọi cạnh vào, xoá quá qtrình 3. Lặp lại 1 với các quá trình khác đến khi tối giản  Khi giải thuật dừng  Đồ thị cấp phát không còn cạnh: không có deadlock  Đồ thị cấp phát có chu trình (cycle): deadlock  Nhận xét  Phí tổn lớn 38 VÍ DỤ 1 : GIẢN ƯỚC P2 R1 P1 R2 P3 R3 P4 P2 R1 P1 R2 P3 R3 P4 P2 R1 P1 R2 P3 R3 P4 P2 R1 P1 R2 P3 R3 P4 39 BÀI TẬP : GIẢN ƯỚC R1 P1 P3 P2 P4R2 R6 R5 R3 40 PHỤC HỒÀI DEADLOCK Đình chỉ hoạt động của các quá trình liên quan.  Thu hồi tài nguyên. Khó có thể giải quyết trọn vẹn 41 BÀI TẬP Tìm trạng thái của hệ thống sau QUAUAÙ TRT Ì NHH Nhu caàu toái ña ( CACAÀN COCOÙ ÑUUÛ SOSOÁ TATAØI NGUYEUYEÂN ÑEEÅ XXÖÛ Lyù) Ñaõ möôïn ( CACAÁP PHAP PHAÙT TAT TAØI NGUYEUYEÂ )N HHieän coøn laïi ( TATAØI NGUYEUYEÂN COCOØN TTÖÏ )DOO AA BB CC AA BB CC AA BB CC P1P1 33 22 22 11 00 00 44 11 22 P2P2 66 11 33 22 11 11 P3P3 33 11 44 22 11 11 P4P4 44 22 22 00 00 22 42 QUAUAÙ TRT ÌNHH eedN Ñaõ möôïn ( CACAÁP PHAP PHAÙT TAT TAØI NGUYEUYEÂ )N HHieän coøn laïi ( TATAØI NGUYEUYEÂN COCOØN TTÖÏ )DOO AA BB CC AA BB CC AA BB CC P1P1 22 22 22 11 00 00 44 11 22 P2P2 44 00 22 22 11 11 P3P3 11 00 33 22 11 11 P4P4 44 22 00 00 00 22 43 QUAUAÙ TRT ÌNHH eedN Ñaõ möôïn ( CACAÁP PHAP PHAÙT TAT TAØI NGUYEUYEÂ )N HHieän coøn laïi ( TATAØI NGUYEUYEÂN COCOØN TTÖÏ )DOO AA BB CC AA BB CC AA BB CC P1P1 22 22 22 11 00 00 66 22 33 P2P2 00 00 00 00 00 00 P3P3 11 00 33 22 11 11 P4P4 44 22 00 00 00 22 44 QUAUAÙ TRT ÌNHH eedN Ñaõ möôïn ( CACAÁP PHAP PHAÙT TAT TAØI NGUYEUYEÂ )N HHieän coøn laïi ( TATAØI NGUYEUYEÂN COCOØN TTÖÏ )DOO AA BB CC AA BB CC AA BB CC P1P1 00 00 00 00 00 00 77 22 33 P2P2 00 00 00 00 00 00 P3P3 11 00 33 22 11 11 P4P4 44 22 00 00 00 22 45 QUAUAÙ TRT ÌNHH eedN Ñaõ möôïn ( CACAÁP PHAP PHAÙT TAT TAØI NGUYEUYEÂ )N HHieän coøn laïi ( TATAØI NGUYEUYEÂN COCOØN TTÖÏ )DOO AA BB CC AA BB CC AA BB CC P1P1 00 00 00 00 00 00 99 33 44 P2P2 00 00 00 00 00 00 P3P3 00 00 00 00 00 00 P4P4 44 22 00 00 00 22 46 QUAUAÙ TRT ÌNHH eedN Ñaõ möôïn ( CACAÁP PHAP PHAÙT TAT TAØI NGUYEUYEÂ )N HHieän coøn laïi ( TATAØI NGUYEUYEÂN COCOØN TTÖÏ )DOO AA BB CC AA BB CC AA BB CC P1P1 00 00 00 00 00 00 99 33 66 P2P2 00 00 00 00 00 00 P3P3 00 00 00 00 00 00 P4P4 00 00 00 00 00 00 47  Chuỗi cấp phát an toàn : 48 Nhu caàu toái ña Ñaõ möôïn HHieän coøn laïi AA BB CC AA BB CC AA BB CC P1P1 00 00 11 00 00 11 11 55 22 P2P2 11 77 55 11 00 00 P3P3 00 66 55 00 66 33 P4P4 00 66 55 00 00 11 Nếu quá trình P2 thay bằng yêu cầu (0,4,2) thì hệ thống cấp phát tức thời cho nó không ? Tìm trạng thái của hệ thống sau eedN Ñaõ möôïn HHieän coøn laïi AA BB CC AA BB CC AA BB CC P1P1 00 00 00 00 00 11 11 55 22 P2P2 00 44 22 11 00 00 P3P3 00 00 22 00 66 33 P4P4 00 66 44 00 00 11 49 Chuỗi cấp phát an toàn QUAUAÙ TRT ÌNHH eedN Ñaõ möôïn ( CACAÁP PHAP PHAÙT TAT TAØI NGUYEUYEÂ )N HHieän coøn laïi ( TATAØI NGUYEUYEÂN COCOØN TTÖÏ )DOO AA BB CC AA BB CC AA BB CC P1P1 00 00 00 00 00 00 22 1111 77 P2P2 00 00 00 00 00 00 P3P3 00 00 00 00 00 00 P4P4 00 00 00 00 00 00 50 Tìm trạng thái của hệ thống sau