Bài giảng Deadlocks

Chương 6: Deadlocks 7.2 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 NỘI DUNG „ Vấn Deadlock „ Mô hình hệ thống „ Đặc trưng Deadlock „ Các phương pháp quản lý Deadlocks „ Phòng ngừa Deadlock „ Tránh Deadlock „ Phát hiện Deadlock „ Phục hồi từ Deadlock 7.3 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 MỤC TIÊU „ Phát triển một mô tả deadlocks, hiện tượng ngăn cản tập các giao dịch cạnh tranh hoàn tất nhiệm vụ của chúng „ Giới thiệu một số phương pháp khác nhau để ngăn ngừa, tránh deadlocks trong hệ thống máy tính. „ Giới thiệu phương pháp phát hiện và phục hồi từ deadlocks 7.4 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 VẤN ĐỀ Deadlock „ Một tập các quá trình bị nghẽn, mỗi một chiếm giữ một tài nguyên và chờ đợi tậu tài nguyên bị chiếm giữ bởi quá trình khác trong tập hợp. „ VD. z Hệ thống có hai ổ đĩa. z P1 và P2 mỗi một chiếm giữ một ổ đĩa và mỗi một cần ổ đĩa kia. „ VD. z semaphores A và B, được khởi động là 1 P0 P1 wait (A); wait(B) wait (B); wait(A) 7.5 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 VÍ DỤ QUA CẦU „ Lưu thông chỉ theo một chiều. „ Mỗi phần của cầu được xem như một tài nguyên. „ Nếu deadlock xảy ra nó sẽ được giải quyết nếu một xe lùi lại (trưng các tài nguyên và cuộn lại). „ Một vài xe có thể bị lùi lại khi deadlock xảy ra. „ Có thể xảy ra “sự chết đói”. 7.6 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 MÔ HÌNH HỆ THỐNG „ Các kiểu tài nguyên: R1, R2, . . ., Rm Các chu kỳ CPU, không gian bộ nhớ, các thiết bị I/O „ Mỗi tài nguyên kiểu Ri cóWi thể hiện. „ Mỗi quá trình sử dụng một tài nguyên như sau: z Yêu cầu tài nguyên z Sử dụng tài nguyên z Giải phóng tài nguyên 7.7 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 ĐẶC TRƯNG DEADLOCK „ Loại trừ tương hỗ (Mutual exclusion): chỉ một quá trình sử dụng một tài nguyên tại một thời điểm. „ Giữ và chờ (Hold and wait): một quá trình chiếm giữ ít nhất một tài nguyên và chờ tậu các tài nguyên bổ xung bị chiếm giữ bởi các quá trình khác. „ Không có trưng dụng: một tài nguyên chỉ có thể được giải phóng bởi sự tình nguyện của quá trình chiếm giữ nó (sau khi quá trình đã hoàn thành nhiệm vụ của nó). „ Chờ đợi vòng tròn: Tồn tại một tập {P0, P1, …, P0} các quá trình chờ đợi sao cho P0 chờ một tài nguyên bị chiếm giữ bởi P1, P1 chờ một tài nguyên bị chiếm giữ bởi P2, …, Pn–1 chờ một tài nguyên bị chiếm giữ bởi Pn, và Pn chờ một tài nguyên bị chiếm giữ bởi P0. Điều kiện cần để deadlock xảy ra: 7.8 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN „ V được phân hoạch thành hai kiểu: z P = {P1, P2, …, Pn}, gồm tất cả các quá trình trong hệ thống. z R = {R1, R2, …, Rm}, gồm tất cả các kiểu tài nguyên trong hệ thống. „ Cung yêu cầu – cung hướng từ Pi đến Rj : Pi → Rj „ Cung gán – hướng từ Rj đến Pi : Rj→ Pi Một tập các đỉnh V và một tập các cung E. 7.9 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN (Cont.) „ Quá trình „ Kiều tài nguyên với 4 thể hiện „ Pi yêu cầu thể hiện của Rj „ Pi đang chiếm giữ một thể hiện của kiểu tài nguyên Rj Pi Pi Rj Rj 7.10 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 VÍ DỤ ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN 7.11 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN VỚI DEADLOCK 7.12 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 ĐỒ THỊ CÓ CHU TRÌNH NHƯNG KHÔNG CÓ Deadlock 7.13 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 CÁC SỰ KIỆN CƠ SỞ „ Nếu đồ thị không có chu trình⇒ không có deadlock. „ Nếu đồ thị có chu trình⇒ z Nếu mỗi kiểu tài nguyên chỉ có một thể hiện thì có deadlock. z Nếu mỗi kiểu tài nguyên có một vài thể hiện thì có thể có deadlock. 7.14 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 CÁC PHƯƠNG PHÁP QUẢN LÝ DEADLOCKS „ Đảm bảo hệ thống không bao giờ rơi vào trạng thái deadlock. „ Cho phép hệ thống rơi vào trạng thái deadlock sau đó phát hiện và phục hồi. „ Bỏ lơ vấn đề và xem như deadlocks không bao giờ xảy ra (được sử dụng trong hầu hết các HĐH kể cả UNIX). 7.15 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 NGĂN NGỪA DEADLOCK „ Loại trừ tương hỗ (Mutual Exclusion) : không được yêu cầu đối với các tài nguyên có thể chia sẻ nhưng có hiệu lực đối với tài nguyên có thể chia sẻ. „ Giữ và chờ (Hold and Wait) : Phải đảm bảo rằng mỗi khi quá trình yêu cầu một tài nguyên nó không chiếm giữ một tài nguyên nào. z Đòi hỏi quá trình yêu cầu và được cấp phát tất cả các tài nguyên cần thiết trước khi bắt đầu thực hiện / chỉ cho phép quá trình yêu cầu các tài nguyên khi nó không chiếm giữ một tài nguyên nào. z Hiệu suất sử dụng tài nguyên thấp, có thể xảy ra chết đói. Ngăn cản một trong bốn điều kiện cần để xảy ra deadlock 7.16 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 Deadlock Prevention (Cont.) „ Không có trưng dụng (no preemption): z Nếu một quá trình đang chiếm giữ một số tài nguyên yêu cầu tài nguyên khác nhưng không thể được cấp phát ngay, các tài nguyên bị chiếm giữ bởi quá trình bị trưng dụng. z Các tài nguyên bị trưng dụng được thêm vào danh sách các tài nguyên quá trình (bị trưng dụng) chờ. z Quá trình sẽ được khởi động lại chỉ khi nó có thể tậu lại các tài nguyên cũ cũng như các tài nguyên mới yêu cầu. „ Chờ đợi vòng tròn (Circular Wait) – áp đặt một thứ tự toàn phần trên các kiểu tài nguyên và đòi hỏi mỗi quá trình yêu cầu tài nguyên theo thứ tự tăng. 7.17 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 TRÁNH Deadlock „ Mô hình đơn giản nhất và hữu dụng nhất là đòi hỏi mỗi quá trình phải khai báo số lượng tối đa các tài nguyên cần thiết của mỗi kiểu. „ Thuật toán tránh deadlock kiểm tra trạng thái cấp phát tài nguyên và đảm bảo rằng không xảy ra chờ đợi vòng tròn. „ Trạng thái cấp phát tài nguyên được định nghĩa bởi số tài nguyên sẵn có, số tài nguyên đã được cấp phát và các đòi hỏi tối đa của các quá trình. Đòi hỏi hệ thống phải có thông tin tiên quyết. 7.18 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 TRẠNG THÁI AN TOÀN „ Khi một quá trình yêu cầu một tài nguyên sẵn có, hệ thống phải xác định nếu cấp phát ngay, hệ thống vẫn trong trạng thái an toàn. „ Hệ thống trong trạng thái an toàn nếu tồn tại một dãy <P1, P2, …, Pn> của TẤT CẢ các quá trình trong hệ thống sao cho đối với mỗi Pi, tất cả các tài nguyên mà Pi cần được thỏa mãn bởi các tài nguyên nó hiện có + các tài nguyên bị chiếm giữ bởi các Pj, với j < i. „ Đó là: z Nếu tài nguyên mà Pi cần chưa có sẵn, Pi có thể chờ đến khi tất cả các Pj (j <i) hoàn tất z Khi Pj hoàn tất, Pi có thể nhận được các tài nguyên cần thiết, thực hiện, trả lại các tài nguyên được cấp phát và kết thúc. z Khi Pi kết thúc, Pi +1 nhận được các tài nguyên cần thiết và cứ như vậy... 7.19 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 SỰ KIỆN CƠ SỞ „ Nếu hệ thống trong trạng thái an toàn⇒ không có deadlocks. „ Nếu hệ thống không trong trạng thái an toàn⇒ có thể có deadlock. „ Tránh⇒ đảm bảo hệ thống không bao giờ rơi vào trạng thái không an toàn. 7.20 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 TRẠNG THÁI AN TOÀN, KHÔNG AN TOÀN & Deadlock 7.21 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 THUẬT TOÁN TRÁNH DEADLOCK „ Mỗi kiểu tài nguyên có đúng một thể hiện. Sử dụng đồ thị cấp phát tài nguyên. „ Mỗi kiểu tài nguyên có một vài thể hiện. Sử dụng thuật toán banker 7.22 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 SƠ ĐỒ ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN „ Cung Claim (Claim edge) Pi→ Rj chỉ ra rằng Pj có thể yêu cầu tài nguyên Rj ; được biểu diễn bởi đường đứt quãng. „ Cung Claim được chuyển thành cung Request khi quá trình yêu cầu tài nguyên. „ Cung Request được chuyển thành cung Assignment khi tài nguyên được cấp cho quá trình. „ Khi tài nguyên được giải phóng, cung Assignment được chuyển thành cung Claim. „ Các tài nguyên phải được khai báo trước. 7.23 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN 7.24 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 TRẠNG THÁI KHÔNG AN TOÀN TRONG ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN 7.25 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 THUẬT TOÁN ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN „ Giả sử quá trình Pi yêu cầu một tài nguyên Rj „ Yêu cầu có thể được cấp chỉ nếu việc chuyển cung Request thành cung Assignment không gây ra chu trình trong đồ thị cấp phát tài nguyên 7.26 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 THUẬT TOÁN Banker „ Đa thể hiện „ Mỗi quá trình phải khai báo số tố đa các thể hiện của mỗi kiểu tài nguyên cần thiết. „ Khi quá trình yêu cầu một tài nguyên, có thể nó phải chờ. „ Khi quá trình nhận được tất cả các tài nguyên cần thiết nó phải trả lại chúng sau một khoảng thời gian hữu hạn. 7.27 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 CẤU TRÚC DỮ LIỆU CHO THUẬT TOÁN Banker’s „ Available: Vector độ dài m. available [j] = k, có nghĩa là có sẵn k thể hiện của kiểu tài nguyên Rj . „ Max: ma trận n x m. Max [i,j] = k, có nghĩa là quá trình Pi có thể yêu cầu nhiều nhất k thể hiện của kiểu tài nguyên Rj. „ Allocation: ma trận n x m. Allocation[i,j] = k có nghĩa là Pi hiện được cấp phát k thể hiện của Rj. „ Need: ma trận n x m. Need[i,j] = k có nghĩa là Pi có thể cần thêm k thể hiện nữa của Rj Need [i,j] = Max[i,j] – Allocation [i,j]. n = số quá trình, m = số các kiểu tài nguyên 7.28 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 THUẬT TOÁN AN TOÀN 1. Work và Finish là các vectors độ dài m và n, tương ứng. Khởi động: Work = Available Finish [i] = false for i = 0, 1, …, n- 1. 2. Tìm i sao cho hai điều kiện sau thỏa mãn: (a) Finish [i] = false (b) Needi ≤Work Nếu không tìm thấy, go to 4. 3. Work = Work + Allocationi Finish[i] = true go to 2. 4. Nếu Finish [i] == true với mọi i, hệ thông trong trạng thái an toàn. 7.29 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 THUẬT TOÁN YÊU CẦU TÀI NGUYÊN ĐỐI VỚI QUÁ TRÌNH Pi Request = vector Request đối với quá trình Pi. Nếu Requesti [j] = k có nghĩa Pi muốn k thể hiện của kiểu tài nguyên Rj. 1. Nếu Requesti ≤ Needi go to 2. Nếu không thông báo lỗi “tiêu thụ tài nguyên vượt quá khai báo”. 2. Nếu Requesti ≤ Available, go to 3. Nếu không Pi phải chờ, (tài nguyên không có sẵn). 3. Giả định cấp phát các tài nguyên được yêu cầu cho Pi bằng cách sủa đổi trạng thái như sau: Available = Available – Request; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti; z Nếu trạng thái mới là an toàn⇒ Cấp phát tài nguyên cho Pi. z Nếu trạng thái mới không an toàn⇒ Pi phải chờ, trạng thái cấp phát tài nguyên cũ được phục hồi 7.30 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 VÍ DỤ THUẬT TOÁN Banker „ 5 quá trình P0, P1, P2, P3, và P4 3 Kiểu tài nguyên: A (10 thể hiện), B (5 thể hiện), và C (7 thể hiện). „ Tức cảnh tại thời điểm T0: Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 7.31 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 VD. (Cont.) „ Ma trận Need = Max – Allocation. Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 „ Thuật toán an toàn cho ra dãy an toàn , như vậy hệ thống trong trạng thái an toàn. 7.32 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 VD : P1 YÊU CẦU (1,0,2) „ Kiểm tra Request1 ≤ Need1 ((1,0,2) ≤ (1, 2, 2) ⇒ true ) „ Kiểm tra Request1 ≤ Available ( (1,0,2) ≤ (3,3,2) ⇒ true ). „ Giả định cấp phát theo yêu cầu của P0 Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 1 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 „ Chạy thuật toán an toàn, tìm được dãy an toàn ; như vậy có thể cấp theo yêu cầu của P0. „ Yêu cầu (3,3,0) bởi P4 được cấp? „ Yêu cầu (0,2,0) bời P0 được cấp? 7.33 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 PHÁT HIỆN DEADLOCKS „ Cho phép hệ thống rơi vào trạng thái deadlock „ Thuật toán phát hiện deadlock „ Sơ đồ phục hồi 7.34 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 MỖI KIỂU TÀI NGUYÊN CHỈ CÓ MỘT THỂ HIỆN „ Duy trì đồ thị chờ z Nodes là các quá trình. z Pi→ Pj nếu Pi chờ Pj. „ Theo chu kỳ gọi thuật toán tìm kiếm chu trình trong đồ thị. có chu trình ⇔ có deadlock. „ Thuật toán phát hiện chu trình trong một đồ thị có độ phức tạp thời gian O(n2) , n = số đỉnh của đồ thị. 7.35 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN & ĐỒ THỊ CHỜ Đồ thị cấp phát tài nguyên Đồ thị chờ tương ứng 7.36 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 MỖI KIỂU TÀI NGUYÊN CÓ MỘT VÀI THỂ HIỆN „ Available: vector độ dài m, available[j]=k : kiểu tài nguyên Rj còn k thể hiện. „ Allocation: ma trận n x m, Allocation[i, j] = k : quá trình i được cấp k thể hiện của kiểu tài nguyên j. „ Request: ma trận n x m, Request [i, j] = k : Pi yêu cầu thêm k thể hiện của kiểu tài nguyên Rj. 7.37 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 THUẬT TOÁN PHÁT HIỆN 1. Work và Finish là các vectors độ dài m và n, tương ứng Initialize: (a) Work = Available (b) For i = 1,2, …, n, if Allocationi ≠ 0, then Finish[i] = false; otherwise, Finish[i] = true. 2. Tìm một chỉ số i sao cho: (a) Finish[i] == false (b) Requesti ≤ Work Nếu không tìm thấy, go to 4. 3. Work = Work + Allocationi Finish[i] = true go to 2. 4. Nếu Finish[i] == false, với một i, 1 ≤ i ≤ n, hệ thống trong trạng thái deadlock. Hơn nữa, nếu Finish[i] == false, thì Pi bị deadlock. Thuật toán có độ phức tạp thời gian O(m x n2). 7.38 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 VD THUẬT TOÁN PHÁT HIỆN „ 5 quá trình : P0, P1, P2, P3 và P4; 3 kiểu tài nguyên A (7 thể hiện), B (2 thể hiện), và C (6 thể hiện). „ Tức cảnh tại thời điểm T0: Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 „ Chạy thuật toán ta được dãy an toàn ; finish[i] == true với mọi i; hệ thống không trong trạng thái deadlock 7.39 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 VD (Cont.) „ Tức cảnh: Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 1 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 „ Trạng thái hệ thống? z Tồn tại Deadlock, các quá trình bị deadlock P1, P2, P3, P4. 7.40 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 PHỤC HỒI TỪ DEADLOCK „ Cuộn lại tất cả các quá trình bị deadlock. „ Lần luợt cuộn lại từng quá trình bị deadlock đến tận khi chu trình deadlock bị loại bỏ. „ Chọn quá trình “nạn nhân”? z Độ ưu tiên của quá trình. z Quá trình đã chạy được bao lâu, còn bao lâu nữa nó sẽ hoàn tất. z Lượng tài nguyên quá trình chiếm giữ. z Lượng tài nguyên quá trình cần thêm. z Bao nhiêu quá trình bị cuộn lại. z Quá trình ở dạng trao đổi hay bó? 7.41 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 14, 2005 PHỤC HỒI TỪ DEADLOCK „ Tối thiểu hóa “giá” „ Chết đói : một quá trình luôn bị chọn là “nạn nhân”. End of Chapter 6