Bài giảng Hệ điều hành - Chương 6: Deadlock - Hà Duy An

Nội dung text: Bài giảng Hệ điều hành - Chương 6: Deadlock - Hà Duy An

1. Khoa Công Nghệ Thông Tin & Truyền Thông ĐạihọcCầnThơ Giảng viên: Hà Duy An
2. 1. Deadlock là gì? 2. Các phương pháp xử lý Deadlock o Ngănchặn Deadlock o Tránh Deadlock o Phát hiệnvàphụchồitừ Deadlock 9/27/2013 2 Chương 6: Deadlock
3. • Hệ thống máy tính bao gồmmộttậphợp các nguồn tài nguyên • Các kiểu tài nguyên R1,R2, ,Rm o Ví dụ: CPU cycles, memory space, I/O devices • Mỗi tài nguyên Ri có Wi thể hiện. • Tiến trình sử dụng một tài nguyên theo các bướcnhư sau: o Yêu cầu (request) o Sử dụng (use) o Giải phóng (release) 9/27/2013 4 Chương 6: Deadlock
4. • Mộttậphợp các tiến trình bị nghẽn, mỗitiếntrìnhđang giữ một tài nguyên và cũng đang chờđểxin một tài nguyên khác, mà tài nguyên này lại đang bị giữ bởimộttiến trình khác trong tậphợp trên. • Ví dụ o Hệ thống có 2 ổ chứabăng từ. o P1 và P2,mộttiếntrìnhđang giữ một ổ và đang cần ổ kia. • Ví dụ:môphỏng sử dụng semaphore o Các semaphores A và B, khởitạolà1 P0 P1 wait (A); wait(B) wait (B); wait(A) 9/27/2013 5 Chương 6: Deadlock
5. 9/27/2013 6 Chương 6: Deadlock
6. Deadlock có thể phát sinh nếu4điềukiệnsauthỏa cùng lúc: • Loạitrừ hỗ tương:chỉ mộttiến trình có thể sử dụng tài nguyên tạimột thời điểm. • Giữ và chờ:Mộttiếntrìnhđang giữ ít nhấtlàmột tài nguyên và đang chờđểđạt đượcmột tài nguyên khác đang bị giữ bởitiến trình khác. • Không trưng dụng:một tài nguyên chỉ có thểđượcgiải phóng một cách tự nguyệnbởitiếntrìnhđang giữ nó, sau khi tiến trình này hoàn thành. • Chờđợi vòng tròn:tồntạimộttậphợp{P0,P1, ,Pn} các tiếntrình đang chờđợinhư sau: P0 đang đợi tài nguyên mà P1 đang giữ,P1 đang đợi tài nguyên mà P2 đang giữ, ,Pn–1 đang đợi tài nguyên mà Pn đang giữ và Pn lại đang chờđợi tài nguyên mà P0 đang giữ. 9/27/2013 7 Chương 6: Deadlock
7. • Bao gồmtậphợp các đỉnh V và tậphợp các cạnh E. • V đượcchialàm2dạng: o P={P1,P2, ,Pn},làtậphợp các tiếntrìnhđang tồntại trong hệ thống. o R={R1,R2, ,Rm},làtậphợp các tài nguyên đang tồntại trong hệ thống. • Echialàm2dạng: o Cạnh yêu cầu: cạnh có hướng Pi →Rj o Cạnh cấp phát: cạnh có hướng Rj →Pi 9/27/2013 8 Chương 6: Deadlock
8. • Tiến trình: • Tài nguyên với4thể hiện: P • Pi yêu cầumộtthể hiệncủaRj: i Rj • Pi đang giữ mộtthể hiệncủaRj: Pi Rj 9/27/2013 9 Chương 6: Deadlock
9. 9/27/2013 10 Chương 6: Deadlock
10. 9/27/2013 11 Chương 6: Deadlock
11. 9/27/2013 12 Chương 6: Deadlock
12. • Nếu đồ thị không có chu trình (cycle) không có deadlock. • Nếu đồ thị có một chu trình: o Nếumột tài nguyên chỉ có mộtthể hiện thì deadlock xảy ra. o Nếumột tài nguyên có vài thể hiện, có khả năng deadlock xảy ra. 9/27/2013 13 Chương 6: Deadlock
13. • Đảmbảorằng hệ thống sẽ không bao giờ bướcvàotrạng thái deadlock bằng các biện pháp ngănchặn hay tránh deadlock. • Cho phép hệ thống bướcvàotrạng thái deadlock và sau đó phục hồilại. • Bỏ qua vấn đề này và xem như hệ thống sẽ không bao giờ xảyra deadlock. o Biệnphápnàyđượcsử dụng trong hầuhết các hệđiềuhành,baogồm cả UNIX. 9/27/2013 15 Chương 6: Deadlock
14. Thắtchặtlại các cách thứcyêucầu tài nguyên củatiến trình. • Loạitrừ hỗ tương: không yêu cầu đốivới các tài nguyên có thể chia sẻ;chỉ áp dụng đốivới các tài nguyên không thể chia sẻ. • Giữ và chờ:phải đảmbảorằng mỗi khi mộttiếntrìnhyêucầu một tài nguyên, nó không đang giữ một tài nguyên khác. o Đòi hỏitiến trình yêu cầuvà đượccấptấtcả các tài nguyên nó cần trước khi bắt đầuthựcthi o Chỉ chophéptiếntrìnhyêucầu tài nguyên chỉ khi nó hiện không giữ một tài nguyên nào cả. o Giảiphápnàylàmgiảm đáng kể hiệuxuấtsử dụng tài nguyên, và có thể gây ra tình trạng đói tài nguyên. 9/27/2013 17 Chương 6: Deadlock
15. • Không trưng dụng (no preemption): o Nếumộttiếntrình đang giữ mộtsố tài nguyên lạiyêucầuthêmmột tài nguyên mới, nhưng tài nguyên mới này không thểđượccấpphát, thì tiếntrìnhđóphảigiải phóng tấtcả các tài nguyên nó đang giữ. • Các tài nguyên vừa đượctrưng dụng được thêm vào danh sách các tài nguyên mà tiếntrìnhđang cần. • Tiến trình sẽ bị khởi động lạichỉ khi nó không thể xin lại đượccáctài nguyên cũ cũng như tài nguyên mớinóđang cần. • Chờđợi vòng tròn (circular wait):phảiápđặtthứ tự toàn cục củatấtcả các lọai tài nguyên và yêu cầurằng mỗitiếntrìnhphải yêu cầu các tài nguyên theo thứ tự tăng. 9/27/2013 18 Chương 6: Deadlock
16. Yêu cầu thông tin bổ sung về cách thức tài nguyên đượcyêucầu. • Mô hình đơngiảnvàhữuíchnhấtlàyêucầumỗitiến trình khai báo số lượng tối đa củamỗidạng tài nguyên mà nó cần. o Vớinhững thông tin đượcbiếttrước, ta có thể xây dựng các giảithuật để bảo đảmrằng hệ thống sẽ không đivàotrạng thái deadlock. • Giảithuật tránh deadlock sẽ kiểmtrađộng trạng thái cấppháttài nguyên để bảo đảmrằng không bao giờ xảyrachờđợi vòng tròn. • Trạng thái cấp phát tài nguyên được định nghĩabởisố lượng tài nguyên đã đượccấp phát, số lượng tài nguyên sẵn dùng, và nhu cầutối đacủa các tiến trình. 9/27/2013 20 Chương 6: Deadlock
17. • Khi mộttiến trình yêu cầumột tài nguyên đang sẵn dùng, hệ thống phải quyết định xem việccấp tài nguyên này tứcthờicógiữ hệ thống ở trạng thái an toàn hay không. • Hệ thống ở trạng thái an toàn nếutồntạimột dãy an toàn (safe sequence) cho tấtcả tiến trình. • Dãy đượcgọilàantoànnếuvớimỗitiếntrìnhPi, các tài nguyên mà Pi có khả năng yêu cầuvẫncóthểđượcthỏamãnbởi các tài nguyên đang sẵn dùng + các tài nguyên đang bị giữ bởitấtcả tiếntrình trình Pj,vớij<i. o Nếu các nhu cầu tài nguyên củaPi không được làm thõa mãn ngay tức thì, thì Pi có thểđợi đến khi tấtcả Pj hoàn thành. o Khi Pj hoàn thành, Pi có thể lấy các tài nguyên cầnthiết, thựcthitiếp, trả lạisố tài nguyên đãchiếmvàkết thúc. o Khi Pi kết thúc, Pi+1 có thể lấy các tài nguyên mà nó cần, 9/27/2013 21 Chương 6: Deadlock
18. • Nếuhệ thống ở trong trạng thái an toàn không có deadlock. • Nếuhệ thống ở trong trạng thái không an toàn có thể có deadlock. • Tránh deadlock đảm bảorằng hệ thống sẽ không bao giờ rơivào trạng thái không an toàn. 9/27/2013 22 Chương 6: Deadlock
19. 1. Mỗiloại tài nguyên có mộtthể hiện: o Sử dụng giảithuật đồ thị cấp phát tài nguyên (Resource-Allocation- Graph Algorithm). 2. Mỗiloại tài nguyên có hơnmộtthể hiện: o Sử dụng giảithuật Banker. 9/27/2013 23 Chương 6: Deadlock
20. • Đượcápdụng trong hệ thống chỉ có mộtthể hiệnchomỗidạng tài nguyên. • Cạnh "dựđịnh yêu cầu"Pi→ Rj chỉ ra rằng tiến trình Pj có thể yêu cầu tài nguyên Rj; đượcbiểudiễnbởi một đường chấm. • Cạnh dựđịnh chuyểnthànhcạnh yêu cầu khi tiến trình yêu cầumộttài nguyên. • Khi một tài nguyên đượcgiải phóng bởimộttiến trình, cạnh cấp phát chuyển thành cạnh dựđịnh yêu cầu. • Tài nguyên phải đượcdự tính yêu cầutrước trong hệ thống. o Các cạnh dựđịnh yêu cầuphảixuấthiệnsẵn trong đồ thị trước khi nó chuyển thành cạnh yêu cầu. • Mộtyêucầuchỉđượccấpchỉ khi việcchuyểntừ Pi → Rj sang Rj → Pi không tạo ra chu trình trong đồ thị cấp phát tài nguyên. o Việckiểmtratrạng thái an toàn đượcthựchiệnbằng giảithuật phát hiện chu trình (cycle-detection algorithm) 9/27/2013 24 Chương 6: Deadlock
21. Yêu cầu tài nguyên củaP2 đốivớiR2sẽ không đượccấp phát, mặc dù R2 đang sẵn dùng, bởivìcóthể tạo ra chu trình, dẫntới deadlock. 9/27/2013 25 Chương 6: Deadlock
22. • Đượcápdụng trong hệ thống có nhiềuthể hiện cho mỗidạng tài nguyên. • Mỗitiến trình phải khai báo số lượng tối đa các thể hiệncủamỗi dạng tài nguyên mà nó cần. • Khi mộttiến trình yêu cầumột tài nguyên, nó có thể phảichờđợi. • Khi mộttiếntrìnhcóđượctấtcả tài nguyên mà nó cần, nó phảitrả lạihết các tài nguyên trong một khoảng thờigianhữuhạn. 9/27/2013 26 Chương 6: Deadlock
23. Đặtn=số lượng tiến trình, m = số các loại tài nguyên. • Available: vector có chiềudàim.Nếu Available [j] = k, có k thể hiệncủadạng tài nguyên Rj đang sẵn dùng. • Max:matrậnnxm.Nếu Max [i,j] = k, thì tiến trình Pi có thể yêu cầutối đakthể hiệncủa tài nguyên Rj. • Allocation:matrậnnxm.Nếu Allocation[i,j] = k thì Pi đang giữ kthể hiệncủaRj. • Need:Matrậnnxm.Nếu Need[i,j] = k, thì Pi có thể cầnthêmk thể hiệncủa tài nguyên Rj để có thể hoàn thành công việccủa nó. Need [i,j] = Max[i,j] – Allocation [i,j]. 9/27/2013 27 Chương 6: Deadlock
24. 1. Đặt Work và Finish là các vectors có chiềudàitương ứng là m và n. Khởitạo: Work = Available Finish[i] = false for i = 0,1,2,3, ,n-1. 2. Tìm i để cả hai điềukiệnsauthỏa: a. Finish[i] = false b. Need[i] ≤Work Nếu không tồntạii,nhảy đếnbước4. 3. Work = Work + Allocation[i] Finish[i] = true nhảy đếnbước2. 4. Nếu Finish [i] == true vớimọii,thìhệ thống đang ở trạng thái an toàn. 9/27/2013 28 Chương 6: Deadlock
25. • Request = vector yêu cầuchotiếntrìnhPi.Nếu Request[i,j] = k thì tiến trình Pi muốnkthể hiệncủa tài nguyên Rj. 1. Nếu Request[i,j] ≤Need[i,j] nhảysangbước2.Ngượclại, báo lỗidotiến trình đãvượt quá số tài nguyên đãdựđịnh sử dụng. 2. Nếu Request[i,j] ≤ Available[j], nhảysangbước3.NgượclạiPi phải chờ, do các tài nguyên nó yêu cầuhiện không sẵn dùng. 3. Giả vờ nhưđang cấp tài nguyên cho Pi bằng cách sửa đổitrạng thái như sau: Available[j] = Available[j] – Request[i,j]; Allocation[i,j] = Allocation[i,j] + Request[i,j]; Need[i,j] = Need[i,j] – Request[i,j] • Nếu an toàn ⇒tài nguyên đượccấp cho Pi. • Nếu không an toàn ⇒ Pi phải đợi, và trạng thái cấp phát tài nguyên cũ đượcphụchồi. 9/27/2013 29 Chương 6: Deadlock
26. • 5tiến trình từ P0 đến P4; 3 loại tài nguyên A (10 thể hiện), B (5 thể hiện), và C (7 thể hiện). • Hiệntrạng tạithời điểm T0 Allocation Max Available ABC ABC ABC P0 010 753 332 P1 200 322 P2 302 902 P3 211 222 P4 002 433 9/27/2013 30 Chương 6: Deadlock
27. • Nội dung củamatrận Need = Max – Allocation. Need ABC P0 743 P1 122 P2 600 P3 011 P4 431 • Hệ thống đang ở trạng thái an toàn do dãy thõa mãn tiêu chí về an toàn. 9/27/2013 31 Chương 6: Deadlock
28. • Kiểm tra Request1 ≤ Available (nghĩa là, (1,0,2) ≤ (3,3,2)) ⇒ true. Allocation Need Available ABC ABC ABC P0 010 743 230 P1 302 020 P2 302 600 P3 211 011 P4 002 431 • Sự thựchiệngiảithuậtantoànchothấydãy thõa mãn yêu cầuvề an toàn yêu cầucủaP1 được đáp ứng ngay lậptức. • Yêu cầu (3,3,0) củaP4 có thểđượccấp không? • Yêu cầu (0,2,0) củaP0 có thểđượccấp không? 9/27/2013 32 Chương 6: Deadlock
29. • Cho phép hệ thống bướcvàotrạng thái deadlock. • Giảithuật phát hiện. • Sơđồphụchồi. 9/27/2013 34 Chương 6: Deadlock
30. • Dùng mộtbiến đổicủa đồ thị cấp phát tài nguyên, gọilàđồ thị chờ (wait-for). • Đồ thị chờ: o Các nút là các tiến trình. o Pi →Pj nếuPiđang đợiPj. • Định kỳ thựchiệngiảithuật tìm kiếm chu trình trong đồ thị. • Deadlock tồntại trong hệ thống nếuvàchỉ nếu đồ thị wait-for chứamột chu trình. • Mộtgiảithuật phát hiện chu trình trong đồ thị yêu cầu theo thứ tự n2 thao tác, vớinlàsố cạnh trong đồ thị. 9/27/2013 35 Chương 6: Deadlock
31. Đồ thị cấp phát tài nguyên Đồ thị wait-for tương ứng 9/27/2013 36 Chương 6: Deadlock
32. • Available:một vector có chiềudàimchỉ ra số lượng thể hiệncòn sẵn dùng củamỗiloại tài nguyên. • Allocation:mộtmatrậnnxmđịnh nghĩasố lượng thể hiệncủa mỗiloại tài nguyên hiện đang đượccấp phát cho mỗitiến trình. • Request:mộtmatrậnnxmchỉ ra lượng yêu cầucủamỗitiến trình. Nếu Request [i,j] = k, thì tiến trình Pi đang yêu cầuthêmk thể hiệncủa tài nguyên loạiRj. 9/27/2013 37 Chương 6: Deadlock
33. 1. Đặt Work và Finish là các vectors có chiềudàitương ứng m và n, khởitạo: a. Work = Available b. For i = 0,1,2, , n-1 if Allocation[i] ≠0 then Finish[i] = false; else Finish[i] = true; 2. Tìm ra chỉ số i để hai điềukiệnsauđượcthỏa: a. Finish[i] == false b. Request[i] ≤Work Nếu không tồntại i,nhảy đếnbước4. 3. Work = Work + Allocation[i] Finish[i] = true Nhảy đếnbước2. 4. If Finish[i] == false cho vài i,1≤ i ≤ n, then hệ thống đang ở trạng thái deadlock. Ngoài ra, if Finish[i] == false,thenPi đang bị deadlock. GiảithuậtyêucầuO(mxn2)thaotácđể xác định hệ thống có trong trạng thái deadlock hay không. 9/27/2013 38 Chương 6: Deadlock
34. • Nămtiến trình P0 đếnP4;có3kiểu tài nguyên A (7 thể hiện), B (2 thể hiện), và C (6 thể hiện). • Hiệntrạng tạithời điểmT0: Allocation Request Available ABC ABC ABC P0 010 000 000 P1 200 202 P2 303 000 P3 211 100 P4 002 002 • Dãy sẽ dẫn đến Finish[i] = true vớimọii.Hệ thống không trong trạng thái deadlock. 9/27/2013 39 Chương 6: Deadlock
35. • P2 yêu cầuthêmmộtthể hiệncủa tài nguyên loạiC. Request ABC P0 000 P1 201 P2 001 P3 100 P4 002 • Trạng thái củahệ thống? o P0 không yêu cầu thêm tài nguyên nào, nhưng hệ thống vẫn không đủ tài nguyên để thỏa nhu cầucủa các tiến trình khác. o Deadlock xảy ra, bao gồm các tiếntrìnhP1,P2,P3,vàP4. 9/27/2013 40 Chương 6: Deadlock
36. • Sử dụng giảithuật khi nào và thường xuyên như thế nào sẽ phụ thuộcvào: o Việc deadlock xảyrathường xuyên như thế nào? o Bao nhiêu tiếntrìnhbịảnh hưởng bởi deadlock, cầnphảiquaylại (rollback) khi nó xuấthiện? • Cầnmộttiếntrìnhđể mở một chu trình (cycle) • Nếugiảithuậtpháthiện deadlock đượcgọi quá ít, thì có thể sẽ có nhiều chu trình xuấthiện trong đồ thị.Khi đó, khó có thể biết rằng tiến trình nào trong số các tiến trình bị deadlock đãgâyra deadlock. 9/27/2013 41 Chương 6: Deadlock
37. • Khipháthiện deadlock, mộtsố cách có thể dùng để phụchồitừ deadlock: o Phụchồibằng tay: cho phép thao tác viên phụchồibằng tay. o Phụchồitựđộng:haitùychọncóthể dùng để xóa deadlock: • Hủytiếntrình:Ngưng mộthoặc nhiềutiếntrìnhđể xóa các chu trình sinh deadlock • Trưng dụng:mộthoặcnhiều tài nguyên từ mộthoặc nhiềutiếntrình bị deadlock. 9/27/2013 42 Chương 6: Deadlock
38. • Hai phương pháp: o Hủybỏ tấtcả các tiến trình bị deadlock • Chi phí lớn: do tiếntrìnhcóthểđã tính toán trong thờigiandài việc tính toán lạisẽ mất nhiềuthờigian. o Hủybỏ mỗilầnmộttiếntrìnhđến khi chu trình deadlock bị loạitrừ. • Chi phí cũng phải được xem xét, vì sau mỗibuớcphảichạylạigiảithuật phát hiện deadlock. • Thế chúng ta nên hủybỏ các tiến trình theo thứ tự nào? o Độ ưu tiên củatiến trình. o Tiếntrìnhđãdiễn ra lâu chưavànócòntiếpdiễnbaolâunữa. o Số tài nguyên mà tiếntrìnhđãsử dụng. o Số tài nguyên mà tiến trình cần để hoàn thành. o Có bao nhiêu tiến trình cầnphải đượckết thúc. o Tiến trình là tương tác hay không (batch process). 9/27/2013 43 Chương 6: Deadlock
39. • Chọnramộtnạn nhân: o Chọn tài nguyên và tiến trình nào bị trưng dụng. o Cầnxácđịnh thứ tự trưng dụng để tốithiểu hóa chi phí. • Quay lại (rollback): o Đưatiến trình quay lai mộttrạng thái an toàn nào đó. o Khởi động lạitiếntrìnhtừ trạng thái đó. o Đòi hỏihệ thống phảilưulại thông tin về trạng thái an toàn củatấtcả các tiếntrìnhđang chạy. • Đói tài nguyên (starvation): o Tránh tình trạng mộttiến trình có thể liên tụcbị chọnlànạn nhân. 9/27/2013 44 Chương 6: Deadlock