›
›

Cơ sở dữ liệu - Chương 6: Deadlocks

pdf 42 trang vanle 3990
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chương 6: Deadlocks", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfco_so_du_lieu_chuong_6_deadlocks.pdf

Nội dung text: Cơ sở dữ liệu - Chương 6: Deadlocks

  1. ChChươươngng 6:6: DeadlocksDeadlocks
  2. NNỘỘII DUNGDUNG „ Vấn Deadlock „ Mô hình hệ thống „ Đặctrư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ụchồitừ Deadlock Operating System Concepts - 7th Edition, Feb 14, 2005 7.2 Silberschatz, Galvin and Gagne ©2005
  3. MMỤỤCC TIÊUTIÊU „ Phát triểnmộtmôtả deadlocks, hiệntượng ngăncản tập các giao dịch cạnh tranh hoàn tất nhiệmvụ của chúng „ Giớithiệumộtsố phương pháp khác nhau để ngăn ngừa, tránh deadlocks trong hệ thống máy tính. „ Giớithiệuphương pháp phát hiệnvàphụchồitừ deadlocks Operating System Concepts - 7th Edition, Feb 14, 2005 7.3 Silberschatz, Galvin and Gagne ©2005
  4. VVẤẤNN ĐĐỀỀ DeadlockDeadlock „ Mộttập các quá trình bị nghẽn, mỗimộtchiếmgiữ mộttài nguyên và chờđợitậu tài nguyên bị chiếmgiữ bởi quá trình khác trong tậphợp. „ VD. z Hệ thống có hai ổđĩa. z P1 và P2 mỗimộtchiếmgiữ một ổđĩavàmỗimộtcần ổđĩa kia. „ VD. z semaphores A và B, đượckhởi động là 1 P0 P1 wait (A); wait(B) wait (B); wait(A) Operating System Concepts - 7th Edition, Feb 14, 2005 7.4 Silberschatz, Galvin and Gagne ©2005
  5. VVÍÍ DDỤỤ QUAQUA CCẦẦUU „ Lưu thông chỉ theo mộtchiều. „ Mỗiphầncủacầu được xem như một tài nguyên. „ Nếu deadlock xảyranósẽ đượcgiảiquyếtnếumộtxelùi lại(trưng các tài nguyên và cuộnlại). „ Một vài xe có thể bị lùi lại khi deadlock xảyra. „ Có thể xảyra“sự chết đói”. Operating System Concepts - 7th Edition, Feb 14, 2005 7.5 Silberschatz, Galvin and Gagne ©2005
  6. MÔMÔ HÌNHHÌNH HHỆỆ THTHỐỐNGNG „ Các kiểu tài nguyên: R1, R2, . . ., Rm Các chu kỳ CPU, không gian bộ nhớ, các thiếtbị 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 Operating System Concepts - 7th Edition, Feb 14, 2005 7.6 Silberschatz, Galvin and Gagne ©2005
  7. ĐĐẶẶCC TRTRƯƯNGNG DEADLOCKDEADLOCK Điềukiệncần để deadlock xảyra: „ Loạitrừ tương hỗ (Mutual exclusion): chỉ một quá trình sử dụng một tài nguyên tạimộtthời điểm. „ Giữ và chờ (Hold and wait): một quá trình chiếmgiữ ít nhấtmột tài nguyên và chờ tậu các tài nguyên bổ xung bị chiếmgiữ 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ểđượcgiải phóng bởisự tình nguyệncủa quá trình chiếmgiữ nó (sau khi quá trình đã hoàn thành nhiệmvụ củanó). „ Chờđợi vòng tròn: Tồntạimộttập{P0, P1, , P0} các quá trình chờđợi sao cho P0 chờ một tài nguyên bị chiếmgiữ bởi P1, P1 chờ một tài nguyên bị chiếmgiữ bởi P2, , Pn–1 chờ một tài nguyên bị chiếmgiữ bởi Pn, và Pn chờ mộttài nguyên bị chiếmgiữ bởi P0. Operating System Concepts - 7th Edition, Feb 14, 2005 7.7 Silberschatz, Galvin and Gagne ©2005
  8. ĐĐỒỒ THTHỊỊ CCẤẤPP PHPHÁÁTT TTÀÀII NGUYÊNNGUYÊN Mộttậpcácđỉnh V và mộttập các cung E. „ V được phân hoạch thành hai kiểu: z P = {P1, P2, , Pn}, gồmtấtcả các quá trình trong hệ thống. z R = {R1, R2, , Rm}, gồmtấtcả các kiểu tài nguyên trong hệ thống. „ Cung yêu cầu – cung hướng từ Pi đếnRj : Pi → Rj „ Cung gán – hướng từ Rj đếnPi : Rj → Pi Operating System Concepts - 7th Edition, Feb 14, 2005 7.8 Silberschatz, Galvin and Gagne ©2005
  9. ĐĐỒỒ THTHỊỊ CCẤẤPP PHPHÁÁTT TTÀÀII NGUYÊNNGUYÊN (Cont.)(Cont.) „ Quá trình „ Kiều tài nguyên với 4 thể hiện „ Pi yêu cầuthể hiệncủa Rj Pi Rj „ Pi đang chiếmgiữ mộtthể hiệncủakiểu tài nguyên Rj Pi Rj Operating System Concepts - 7th Edition, Feb 14, 2005 7.9 Silberschatz, Galvin and Gagne ©2005
  10. VVÍÍ DDỤỤ ĐĐỒỒ THTHỊỊ CCẤẤPP PHPHÁÁTT TTÀÀII NGUYÊNNGUYÊN Operating System Concepts - 7th Edition, Feb 14, 2005 7.10 Silberschatz, Galvin and Gagne ©2005
  11. ĐĐỒỒ THTHỊỊ CCẤẤPP PHPHÁÁTT TTÀÀII NGUYÊNNGUYÊN VVỚỚII DEADLOCKDEADLOCK Operating System Concepts - 7th Edition, Feb 14, 2005 7.11 Silberschatz, Galvin and Gagne ©2005
  12. ĐĐỒỒ THTHỊỊ CCÓÓ CHUCHU TRÌNHTRÌNH NHNHƯƯNGNG KHÔNGKHÔNG CCÓÓ DeadlockDeadlock Operating System Concepts - 7th Edition, Feb 14, 2005 7.12 Silberschatz, Galvin and Gagne ©2005
  13. CCÁÁCC SSỰỰ KIKIỆỆNN CCƠƠ SSỞỞ „ Nếu đồ thị không có chu trình ⇒ không có deadlock. „ Nếu đồ thị có chu trình ⇒ z Nếumỗikiểu tài nguyên chỉ có mộtthể hiệnthìcó deadlock. z Nếumỗikiểutàinguyêncómộtvàithể hiệnthìcó thể có deadlock. Operating System Concepts - 7th Edition, Feb 14, 2005 7.13 Silberschatz, Galvin and Gagne ©2005
  14. CCÁÁCC PHPHƯƠƯƠNGNG PHPHÁÁPP QUQUẢẢNN LÝLÝ DEADLOCKSDEADLOCKS „ Đảmbảohệ thống không bao giờ rơivàotrạng thái deadlock. „ Chophéphệ thống rơivàotrạng thái deadlock sau đóphát hiệnvàphụchồi. „ Bỏ lơ vấn đề và xem như deadlocks không bao giờ xảyra (đượcsử dụng trong hầuhếtcác HĐH kể cả UNIX). Operating System Concepts - 7th Edition, Feb 14, 2005 7.14 Silberschatz, Galvin and Gagne ©2005
  15. NGNGĂĂNN NGNGỪỪAA DEADLOCKDEADLOCK Ngăncảnmột trong bốn điềukiệncần để xảy ra deadlock „ Loạitrừ tương hỗ (Mutual Exclusion) : không đượcyêu cầu đốivới các tài nguyên có thể chia sẻ nhưng có hiệulực đốivới tài nguyên có thể chia sẻ. „ Giữ và chờ (Hold and Wait) : Phải đảmbảorằng mỗikhi quá trình yêu cầumột tài nguyên nó không chiếmgiữ một tài nguyên nào. z Đòi hỏi quá trình yêu cầuvàđượccấp phát tấtcả các tài nguyên cầnthiếttrướckhibắt đầuthựchiện/ chỉ cho phép quá trình yêu cầu các tài nguyên khi nó không chiếmgiữ một tài nguyên nào. z Hiệusuấtsử dụng tài nguyên thấp, có thể xảyrachết đói. Operating System Concepts - 7th Edition, Feb 14, 2005 7.15 Silberschatz, Galvin and Gagne ©2005
  16. DeadlockDeadlock PreventionPrevention (Cont.)(Cont.) „ Không có trưng dụng (no preemption): z Nếumột quá trình đang chiếmgiữ mộtsố tài nguyên yêu cầu tài nguyên khác nhưng không thể đượccấp phát ngay, các tài nguyên bị chiếmgiữ 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ẽ đượckhởi động lạichỉ khi nó có thể tậulại các tài nguyên cũ cũng như các tài nguyên mớiyêucầu. „ Chờđợi vòng tròn (Circular Wait) –ápđặtmộtthứ tự toàn phầntrêncáckiểu tài nguyên và đòi hỏimỗi quá trình yêu cầu tài nguyên theo thứ tự tăng. Operating System Concepts - 7th Edition, Feb 14, 2005 7.16 Silberschatz, Galvin and Gagne ©2005
  17. TRTRÁÁNHNH DeadlockDeadlock Đòi hỏihệ thống phải có thông tin tiên quyết. „ Mô hình đơngiảnnhấtvàhữudụng nhấtlàđòi hỏimỗi quá trình phải khai báo số lượng tối đa các tài nguyên cầnthiết củamỗikiểu. „ Thuật toán tránh deadlock kiểmtratrạng thái cấp phát tài nguyên và đảmbảorằng không xảyrachờđợi vòng tròn. „ Trạng thái cấp phát tài nguyên được định nghĩabởisố tài nguyên sẵncó, số tài nguyên đã đượccấp phát và các đòi hỏitối đacủa các quá trình. Operating System Concepts - 7th Edition, Feb 14, 2005 7.17 Silberschatz, Galvin and Gagne ©2005
  18. TRTRẠẠNGNG THTHÁÁII ANAN TOTOÀÀNN „ Khi một quá trình yêu cầumột tài nguyên sẵncó, hệ thống phải xác định nếucấ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ếutồntạimộtdãy củaTẤT CẢ các quá trình trong hệ thống sao cho đốivới mỗiPi, tấtcả các tài nguyên mà Pi cần đượcthỏamãnbởicác tàinguyênnóhiện có + các tài nguyên bị chiếmgiữ bởicácPj, với j < i. „ Đólà: z NếutàinguyênmàPi cầnchưacósẵn, Pi có thể chờđếnkhi tấtcả 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ầnthiết, thựchiện, trả lại các tài nguyên đượccấ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ầnthiếtvà cứ như vậy Operating System Concepts - 7th Edition, Feb 14, 2005 7.18 Silberschatz, Galvin and Gagne ©2005
  19. SSỰỰ KIKIỆỆNN CCƠƠ SSỞỞ „ Nếuhệ thống trong trạng thái an toàn ⇒ không có deadlocks. „ Nếuhệ thống không trong trạng thái an toàn ⇒ có thể có deadlock. „ Tránh ⇒ đảmbảohệ thống không bao giờ rơivàotrạng thái không an toàn. Operating System Concepts - 7th Edition, Feb 14, 2005 7.19 Silberschatz, Galvin and Gagne ©2005
  20. TRTRẠẠNGNG THTHÁÁII ANAN TOTOÀÀN,N, KHÔNGKHÔNG ANAN TOTOÀÀNN && DeadlockDeadlock Operating System Concepts - 7th Edition, Feb 14, 2005 7.20 Silberschatz, Galvin and Gagne ©2005
  21. THUTHUẬẬTT TOTOÁÁNN TRTRÁÁNHNH DEADLOCKDEADLOCK „ Mỗikiểu tài nguyên có đúng mộtthể hiện. Sử dụng đồ thị cấp phát tài nguyên. „ Mỗikiểu tài nguyên có mộtvàithể hiện. Sử dụng thuật toán banker Operating System Concepts - 7th Edition, Feb 14, 2005 7.21 Silberschatz, Galvin and Gagne ©2005
  22. SSƠƠ ĐĐỒỒ ĐĐỒỒ THTHỊỊ CCẤẤPP PHPHÁÁTT TTÀÀII NGUYÊNNGUYÊN „ Cung Claim (Claim edge) Pi → Rj chỉ ra rằng Pj có thể yêu cầu tài nguyên Rj ; đượcbiểudiễnbởi đường đứt quãng. „ Cung Claim đượcchuyển thành cung Request khi quá trình yêu cầu tài nguyên. „ Cung Request đượcchuyển thành cung Assignment khi tài nguyên đượccấp cho quá trình. „ Khi tài nguyên đượcgiả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. Operating System Concepts - 7th Edition, Feb 14, 2005 7.22 Silberschatz, Galvin and Gagne ©2005
  23. ĐĐỒỒ THTHỊỊ CCẤẤPP PHPHÁÁTT TTÀÀII NGUYÊNNGUYÊN Operating System Concepts - 7th Edition, Feb 14, 2005 7.23 Silberschatz, Galvin and Gagne ©2005
  24. TRTRẠẠNGNG THTHÁÁII KHÔNGKHÔNG ANAN TOTOÀÀNN TRONGTRONG ĐĐỒỒ THTHỊỊ CCẤẤPP PHPHÁÁTT TTÀÀII NGUYÊNNGUYÊN Operating System Concepts - 7th Edition, Feb 14, 2005 7.24 Silberschatz, Galvin and Gagne ©2005
  25. THUTHUẬẬTT TOTOÁÁNN ĐĐỒỒ THTHỊỊ CCẤẤPP PHPHÁÁTT TTÀÀII NGUYÊNNGUYÊN „ Giả sử quá trình Pi yêu cầumột tài nguyên Rj „ Yêu cầucóthểđượccấpchỉ nếuviệcchuyểncung Request thành cung Assignment không gây ra chu trình trong đồ thị cấp phát tài nguyên Operating System Concepts - 7th Edition, Feb 14, 2005 7.25 Silberschatz, Galvin and Gagne ©2005
  26. THUTHUẬẬTT TOTOÁÁNN BankerBanker „ Đathể hiện „ Mỗi quá trình phảikhaibáosố tốđacácthể hiệncủamỗi kiểu tài nguyên cầnthiết. „ Khi quá trình yêu cầumột tài nguyên, có thể nó phảichờ. „ Khi quá trình nhận đượctấtcả các tài nguyên cầnthiếtnó phảitrả lại chúng sau mộtkhoảng thờigianhữuhạn. Operating System Concepts - 7th Edition, Feb 14, 2005 7.26 Silberschatz, Galvin and Gagne ©2005
  27. CCẤẤUU TRTRÚÚCC DDỮỮ LILIỆỆUU CHOCHO THUTHUẬẬTT TOTOÁÁNN BankerBanker’’ss n = số quá trình, m = số các kiểu tài nguyên „ Available:Vector độ dài m. available [j] = k, có nghĩalàcó sẵn k thể hiệncủakiể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ềunhất k thể hiệncủakiểu tài nguyên Rj. „ Allocation: ma trậnn x m. Allocation[i,j] = k có nghĩalàPi hiện đượccấp phát k thể hiệncủa Rj. „ Need: ma trậnn x m. Need[i,j] = k có nghĩalàPi có thể cần thêm k thể hiệnnữacủa Rj Need [i,j] = Max[i,j] – Allocation [i,j]. Operating System Concepts - 7th Edition, Feb 14, 2005 7.27 Silberschatz, Galvin and Gagne ©2005
  28. THUTHUẬẬTT TOTOÁÁNN ANAN TOTOÀÀNN 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ềukiệnsauthỏ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ớimọi i, hệ thông trong trạng thái an toàn. Operating System Concepts - 7th Edition, Feb 14, 2005 7.28 Silberschatz, Galvin and Gagne ©2005
  29. THUTHUẬẬTT TOTOÁÁNN YÊUYÊU CCẦẦUU TTÀÀII NGUYÊNNGUYÊN ĐĐỐỐII VVỚỚII QUQUÁÁ TRÌNHTRÌNH PPi Request = vector Request đốivới quá trình Pi. Nếu Requesti [j] = k có nghĩa Pi muốn k thể hiệncủakiể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ảichờ, (tài nguyên không có sẵn). 3. Giảđịnh cấp phát các tài nguyên đượcyêucầuchoPi bằng cách sủa đổitrạng thái như sau: Available = Available – Request; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti; z Nếutrạng thái mới là an toàn ⇒ Cấp phát tài nguyên cho Pi. z Nếutrạng thái mới không an toàn ⇒ Pi phảichờ, trạng thái cấp phát tài nguyên cũđượcphụchồi Operating System Concepts - 7th Edition, Feb 14, 2005 7.29 Silberschatz, Galvin and Gagne ©2005
  30. VVÍÍ DDỤỤ THUTHUẬẬTT TOTOÁÁNN BankerBanker „ 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ứccảnh tạithờ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 Operating System Concepts - 7th Edition, Feb 14, 2005 7.30 Silberschatz, Galvin and Gagne ©2005
  31. VD.VD. (Cont.)(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. Operating System Concepts - 7th Edition, Feb 14, 2005 7.31 Silberschatz, Galvin and Gagne ©2005
  32. VDVD :: PP1 YÊUYÊU CCẦẦUU (1,0,2)(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ầucủaP0 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ạythuật toán an toàn, tìm được dãy an toàn ; như vậycóthể cấptheoyêucầucủaP0. „ Yêu cầu (3,3,0) bởi P4 đượccấp? „ Yêu cầu (0,2,0) bời P0 đượccấp? Operating System Concepts - 7th Edition, Feb 14, 2005 7.32 Silberschatz, Galvin and Gagne ©2005
  33. PHPHÁÁTT HIHIỆỆNN DEADLOCKSDEADLOCKS „ Chophéphệ thống rơivàotrạng thái deadlock „ Thuật toán phát hiện deadlock „ Sơđồphụchồi Operating System Concepts - 7th Edition, Feb 14, 2005 7.33 Silberschatz, Galvin and Gagne ©2005
  34. MMỖỖII KIKIỂỂUU TTÀÀII NGUYÊNNGUYÊN CHCHỈỈ CCÓÓ MMỘỘTT THTHỂỂ HIHIỆỆNN „ Duy trì đồ thị chờ z Nodes là các quá trình. z Pi → Pj nếu Pi chờ Pj. „ Theo chu kỳ gọithuật toán tìm kiếmchutrìnhtrongđồ 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ạpthờigianO(n2) , n = sốđỉnh của đồ thị. Operating System Concepts - 7th Edition, Feb 14, 2005 7.34 Silberschatz, Galvin and Gagne ©2005
  35. ĐỒ 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 Operating System Concepts - 7th Edition, Feb 14, 2005 7.35 Silberschatz, Galvin and Gagne ©2005
  36. MMỖỖII KIKIỂỂUU TTÀÀII NGUYÊNNGUYÊN CCÓÓ MMỘỘTT VVÀÀII THTHỂỂ HIHIỆỆNN „ 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 đượccấp k thể hiệncủakiểu tài nguyên j. „ Request: ma trận n x m, Request [i, j] = k : Pi yêu cầuthêm k thể hiệncủakiểu tài nguyên Rj. Operating System Concepts - 7th Edition, Feb 14, 2005 7.36 Silberschatz, Galvin and Gagne ©2005
  37. THUTHUẬẬTT TOTOÁÁNN PHPHÁÁTT HIHIỆỆNN 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ộtchỉ 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ớimột i, 1 ≤ i ≤ n, hệ thống trong trạng thái deadlock. Hơnnữa, nếu Finish[i] == false, thì Pi bị deadlock. Thuậttoáncóđộ phứctạpthờigianO(m x n2). Operating System Concepts - 7th Edition, Feb 14, 2005 7.37 Silberschatz, Galvin and Gagne ©2005
  38. VDVD THUTHUẬẬTT TOTOÁÁNN PHPHÁÁTT HIHIỆỆNN „ 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ứccảnh tạithờ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ạythuật toán ta được dãy an toàn ; finish[i] == true vớimọii; hệ thống không trong trạng thái deadlock Operating System Concepts - 7th Edition, Feb 14, 2005 7.38 Silberschatz, Galvin and Gagne ©2005
  39. VDVD (Cont.)(Cont.) „ Tứccả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ồntại Deadlock, các quá trình bị deadlock P1, P2, P3, P4. Operating System Concepts - 7th Edition, Feb 14, 2005 7.39 Silberschatz, Galvin and Gagne ©2005
  40. PHPHỤỤCC HHỒỒII TTỪỪ DEADLOCKDEADLOCK „ Cuộnlạitấtcả các quá trình bị deadlock. „ Lầnluợtcuộnlạitừng quá trình bị deadlock đếntận khi chu trình deadlock bị loạibỏ. „ Chọn quá trình “nạn nhân”? z Độ ưutiêncủa quá trình. z Quá trình đãchạy được bao lâu, còn bao lâu nữanósẽ hoàn tất. z Lượng tài nguyên quá trình chiếmgiữ. z Lượng tài nguyên quá trình cầnthêm. z Bao nhiêu quá trình bị cuộnlại. z Quá trình ở dạng trao đổihay bó? Operating System Concepts - 7th Edition, Feb 14, 2005 7.40 Silberschatz, Galvin and Gagne ©2005
  41. PHPHỤỤCC HHỒỒII TTỪỪ DEADLOCKDEADLOCK „ Tốithiểu hóa “giá” „ Chết đói : một quá trình luôn bị chọnlà“nạn nhân”. Operating System Concepts - 7th Edition, Feb 14, 2005 7.41 Silberschatz, Galvin and Gagne ©2005
  42. EndEnd ofof ChapterChapter 66