›
›

Bài giảng Hệ điều hành - Chương 5: Deadlock - Trần Hạnh Nhi

pdf 36 trang huongle 3070
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 5: Deadlock - Trần Hạnh Nhi", để 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:

  • pdfbai_giang_he_dieu_hanh_chuong_5_deadlock_tran_hanh_nhi.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 5: Deadlock - Trần Hạnh Nhi

  1. Bài giảng 5 : Deadlock „ Định nghĩa Deadlock „ Mô hình hệ thống „ Điều kiện phát sinh Deadlock „ Xử lý Deadlock 11/7/2005 Trần Hạnh Nhi 1
  2. Dining Philosophers „ Năm triết gia ngồi chung quanh bàn ăn món spaghetti (yum yum) „ Trên bàn có 5 cái nĩa được đặt giữa 5 cái đĩa (xem hình) „ Để ăn món spaghetti mỗi người cần có 2 cái nĩa „ Triết gia thứ i: „ Thinking „ Eating Chuyện gì có thể xảy ra ? 11/7/2005 Trần Hạnh Nhi 2
  3. Dining Philosophers : Tình huống nguy hiểm ƒ 2 triết gia “giành giật” cùng 1 cái nĩa ƒ Tranh chấp ƒ Cần đồng bộ hoá hoạt động của các triết gia 11/7/2005 Trần Hạnh Nhi 3
  4. Dining Philosophers : Giải pháp đồng bộ semaphore fork[5] = 1; Philosopher (i) { while(true) { down(fork[i]); down(fork[i+1 mod 5]) eat; up(fork[i]); up(fork[i+1 mod 5]); think; Deadlock } 11/7/2005 Trần Hạnh Nhi 4
  5. Định nghĩa Deadlock „ Deadlock : „ Chờ đợi một sự kiện không bao giờ xảy ra „ Các tiến trình trong tập hợp chờ đợi lẫn nhau „ Starvation „ Chờ đợi không có giới hạn một sự kiện mà chưa thấy xảy ra „ Deadlock kéo theo Starvation „ Điều ngược lại không chắc 11/7/2005 Trần Hạnh Nhi 5
  6. Mô hình hệ thống „ Hệ thống bao gồm một số xác định các loại tài nguyên sẽ được chia sẻ cho các tiến trình có nhu cầu „ Mỗi loại tài nguyên có thể có nhiều thể hiện „ Mỗi tiến trình sử dụng tài nguyên theo trình tự „ Request : yêu cầu tài nguyên, nếu yêu cầu không được thoã mãn nay, tiến trình phải đợi „ Use : sử dụng tài nguyên được cấp phát „ Release : giải phóng tài nguyên 11/7/2005 Trần Hạnh Nhi 6
  7. Các điều kiện xảy ra Deadlock „ Coffman, Elphick và Shoshani (1971) đã đưa ra 4 điều kiện cần có thể làm xuất hiện tắc nghẽn: „ Mutual exclusion: hệ thống có sử dụng những loại tài nguyên mang bản chất không chia sẻ được. „ Wait for : Tiến trình tiếp tục chiếm giữ các tài nguyên đã cấp phát cho nó trong khi chờ được cấp phát thêm một số tài nguyên mới. „ No preemption: Tài nguyên chỉ được thu hồi khi tiến trình đang chiếm giữ chúng tự nguyện trao trả. „ Circular wait: Tồn tại một chu kỳ trong đồ thị cấp phát tài nguyên . „ Hội đủ 4 điều kiện trên đây : Deadlock có thể xảy ra 11/7/2005 Trần Hạnh Nhi 7
  8. Đồ thị cấp phát tài nguyên „ 2 loại nodes: „ P = {P1, P2, , Pn}, tập các tiến trình „ R = {R1, R2, , Rm}, tập các loại tài nguyên „ Tiến trình yêu cầu tài nguyên : „ Pi → Rj „ Tài nguyên được cấp phát cho tiến trình : „ Rj → Pi 11/7/2005 Trần Hạnh Nhi 8
  9. Ví dụ đồ thị cấp phát tài nguyên P „ Process i R „ Một loại tài nguyên với 4 thể hiện j P Rj „ Pi yêu cầu 1 thể hiện của Rj i „ Rj Pi đang giữ 1 thể hiện của Rj Pi 11/7/2005 Trần Hạnh Nhi 9
  10. Ví dụ đồ thị cấp phát tài nguyên Example: 11/7/2005 Trần Hạnh Nhi 10
  11. Nhận xét cơ bản „ Nếu đồ thị không có chu trình ⇒ no deadlock. „ Nếu đồ thị có 1 chu trình ⇒ „ Nếu mỗi tài nguyên chỉ có 1 thể hiện ⇒ deadlock. „ Nếu mỗi tài nguyên có nhiều thể hiện ⇒ có thể có deadlock. 11/7/2005 Trần Hạnh Nhi 11
  12. Ví dụ đồ thị cấp phát tài nguyên Deadlocked: 11/7/2005 Trần Hạnh Nhi 12
  13. Ví dụ đồ thị cấp phát tài nguyên With Cycle but No Deadlock: 11/7/2005 Trần Hạnh Nhi 13
  14. Deadlock Prevention „ Đảm bảo Deadlock không thể xảy ra „ Tìm cách loại bỏ ít nhất 1 trong 4 điều kiện cần để xảy ra Deadlock „ Nhắc lại 4 điều kiện cần „ Mutual Exclusion „ Hold and Wait „ No preemption „ Circular wait „ Để xem 11/7/2005 Trần Hạnh Nhi 14
  15. Deadlock Prevention „ Mutual Exclusion „ Không cần đảm bảo độc quyền truy xuất tài nguyên ? „ Thinking „ Thinking „ Thinking „ Với các shareable resources : dĩ nhiên ! „ Với các non-shareable resource : “Mission Impossible” ??? „ Làm gì : virtualize, spooling „ Rất hạn chế, đặc biệt đối với tài nguyên phần mềm ( Kết luận : Không thể loại bỏ 11/7/2005 Trần Hạnh Nhi 15
  16. Deadlock Prevention „ Hold and Wait „ Không cho vừa chiếm giữ vừa yêu cầu thêm tài nguyên „ No Wait „ Cấp cho tiến trình tất cả các tài nguyên cần thiết trước khi bắt đầu xử lý „ Làm sao biết ? „ No Hold „ Tiến trình không xin được tài nguyên mới : trả lại tài nguyên cũ, và chờ xin lại lần sau „ “Trả lại” tài nguyên ở trạng thái nào ? „ Sử dụng tài nguyên kém hiệu quả, có thể starvation ( Kết luận : thật sự khó khả thi, không thể loại bỏ 11/7/2005 Trần Hạnh Nhi 16
  17. Deadlock Prevention „ No Preemption „ Hệ điều hành chủ động thu hồi các tài nguyên của tiến trình blocked „ Tài nguyên nào có thể thu hồi ? „ CPU :OK „ Printer : Hu hu / „ Các tài nguyên bị thu hồi sẽ được bổ sung vào danh sách tài nguyên tiến trình cần xin lại. Tiến trình chỉ có thể tiếp tục xử lý khi xin lại đủ các tài nguyên này (cũ và mới) (Kết luận : thật sự khó loại bỏ hoàn toàn 11/7/2005 Trần Hạnh Nhi 17
  18. Deadlock Prevention Trật tự nào ? „ Circular Wait „ Không để xảy ra chu trình trong đồ thị cấp phát tài nguyên „ Cấp phát tài nguyên theo 1 trật tự nhất định „ Gọi R = {R1, R2, ,Rm} là tập các loại tài nguyên. „ Các loại tài nguyên được phân cấp theo độ ưu tiên F(R) thuộc [1-N] „ Ví dụ : F(đĩa) = 2, F(máy in) = 12 „ Các tiến trình khi yêu cầu tài nguyên phải tuân thủ quy định : khi tiến trình đang chiếm giữ tài nguyên Ri thì chỉ có thể yêu cầu các tài nguyên Rj nếu F(Rj) > F(Ri). R1 F(R1) = 1; F(R2) = 2; P1 P2 R2 11/7/2005 Trần Hạnh Nhi 18
  19. Deadlock Prevention „ Đảm bảo Deadlock không thể xảy ra „ Không thể loại bỏ ít nhất 1 trong 4 điều kiện cần để xảy ra Deadlock „ Quá khắt khe, không khả thi 11/7/2005 Trần Hạnh Nhi 19
  20. Deadlock Avoidance „ Một số định nghĩa cơ bản „ Trạng thái an toàn (Safe): hệ thống có thể thỏa mãn các nhu cầu tài nguyên (cho đến tối đa) của tất cả các tiến trình theo một thứ tự nào đó mà không dẫn đến tắc nghẽn. „ Việc cấp phát tài nguyên không hình thành chu trình nào trong đồ thị cấp phát „ Một chuỗi cấp phát an toàn: một thứ tự kết thúc các tiến trình sao cho với mỗi tiến trình Pi nhu cầu tài nguyên của Pi có thể được thỏa mãn với các tài nguyên còn tự do của hệ thống, cộng với các tài nguyên đang bị chiếm giữ bởi các tiến trình Pj khác, với j<i. „ Thay đổi chiến luợc cấp phát tài nguyên để đảm bảo không dẫn dắt hệ thống vào tình trạng deadlock „ Chỉ thỏa mãn yêu cầu tài nguyên của tiến trình khi trạng thái kết quả là an toàn „ Đòi hỏi phải biết trước một số thông tin về nhu cầu sử dụng tài nguyên của tiến trình 11/7/2005 Trần Hạnh Nhi 20
  21. Nhận xét „ Hệ thống ở safe state ⇒ không deadlocks. „ Nếu hệ thống ở unsafe state ⇒ có khả năng deadlock. „ Avoidance ⇒ bảo đảm hệ thống không bao giờ đi vào trạng thái unsafe. 11/7/2005 Trần Hạnh Nhi 21
  22. Deadlock Avoidance : thông tin cần biết „ Giả sử hệ thống được mô tả với các thông tin sau : „ int Available[NumResources]; „ Available[r]= số lượng các thể hiện còn tự do của tài nguyên r „ int Max[NumProcs, NumResources]; „ Max[p,r]= nhu cầu tối đa của tiến trình p về tài nguyên r „ int Allocation[NumProcs, NumResources]; „ Allocation[p,r] = số lượng tài nguyên r thực sự cấp phát cho p „ int Need[NumProcs, NumResources]; „ Need[p,r] = Max[p,r] - Allocation[p,r] 11/7/2005 Trần Hạnh Nhi 22
  23. Giải thuật cấp phát tài nguyên kiểu cũ „ Pi xin k thể hiện của Rj 1 : if (k <= Need[i,j]) goto 2; else Error(); 2: if (k <= Available[j]) Allocate(i,j,k); //cấp cho Pi k thể hiện Rj else MakeWait(Pi); 11/7/2005 Trần Hạnh Nhi 23
  24. Deadlock Avoidance : Banker’s Algorithm „ Pi xin k thể hiện của Rj 1 : if (k <= Need[i,j]) goto 2; else Error(); 2: if (k <= Available[j]) goto 3; else MakeWait(Pi); 3: /* Giả sử hệ thống đã cấp phát cho Pi các tài nguyên mà nó yêu cầu và cập nhật tình trạng hệ thống như sau:*/ Available[j] = Available[j] - k; Allocation[i,j]= Allocation[i,j]+ k; Need[i,j] = Need[i,j] - k; Result = TestSafe(); if (Result == Safe) Allocate(i,j,k); //cấp cho Pi k thể hiện Rj else MakeWait(Pi); 11/7/2005 Trần Hạnh Nhi 24
  25. TestSafe () 1. Giả sử có các mảng int Work[NumResources] = Available[NumResources]; int Finish[NumProcs] = false; 2. Tìm i sao cho Finish[i] == false & Need[i,j] <= Work[i,j], ∀j <=NumRes Nếu không có i như thế, đến bước 4. 3. Work = Work + Allocation[i]; Finish[i] = true; Đến bước 2 4. Nếu Finish[i] == true với mọi i, thì hệ thống ở trạng thái an toàn. 11/7/2005 Trần Hạnh Nhi 25
  26. Ví dụ 1 Giả sử tình trạng hệ thống được mô tả như sau : Max Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 4 1 2 P2 6 1 3 2 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 11/7/2005 Trần Hạnh Nhi 26
  27. Ví dụ 1 Giả sử tình trạng hệ thống được mô tả như sau : NeedMax Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 23 2 2 1 0 0 4 1 2 P2 64 10 32 2 1 1 P3 31 10 43 2 1 1 P4 4 2 20 0 0 2 3 - 1 11/7/2005 Trần Hạnh Nhi 27
  28. Ví dụ 1 P2 yêu cầu 4 cho R1, 1 cho R3 : cân nhắc NeedMax Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 2 2 1 0 0 40 1 21 P2 40 0 21 26 1 12 P3 1 0 3 2 1 1 P4 4 2 0 0 0 2 11/7/2005 Trần Hạnh Nhi 28
  29. Ví dụ 1 P2 yêu cầu 4 cho R1, 1 cho R3 : cân nhắc NeedMax Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 20 20 20 10 0 0 046097 11232 0423613 P2 40 0 021 620 10 3120 P3 10 0 30 20 10 10 P4 40 20 0 0 0 20 P2 yêu cầu 4 cho R1, 1 cho R3 : chấp nhận 11/7/2005 Trần Hạnh Nhi 29
  30. Deadlock Detection „ Chấp nhận hệ thống rơi vào trạng thái deadlock „ Hệ thống nên cung cấp: „ Một giải thuật kiểm tra và phát hiện deadlock có xảy ra trong hệ thống hay không „ Một giải thuật để hiệu chỉnh, phục hồi hệ thống về trạng thái trước khi deadlock xảy ra. „ Cần tốn kém chi phí để : „ Lưu trữ, cập nhật các thông tin cần thiết „ Xử lý giải thuật phát hiện deadlock „ Chấp nhận khả năng mất mát khi phục hồi. 11/7/2005 Trần Hạnh Nhi 30
  31. Giải thuật phát hiện deadlock „ Cần sử dụng các cấu trúc dữ liệu sau : „ int Available[NumResources]; „ // Available[r]= số lượng các thể hiện còn tự do của tài nguyên r „ int Allocation[NumProcs, NumResources]; „ // Allocation[p,r] = số lượng tài nguyên r thực sự cấp phát cho p „ int Request[NumProcs, NumResources]; „ // Request[p,r] = số lượng tài nguyên r tiến trình p yêu cầu thêm 11/7/2005 Trần Hạnh Nhi 31
  32. Giải thuật phát hiện deadlock 1. Giả sử có các mảng int Work[NumResources] = Available; int Finish[NumProcs] ; for (i = 0; i < NumProcs; i++) Finish[i] = (Allocation[i] == 0); 2. Tìm i sao cho Finish[i] == false & Request[i,j] <= Work[i,j], ∀j <=NumRes Nếu không có i như thế, đến bước 4. 3. Work = Work + Allocation[i]; Finish[i] = true; Đến bước 2 4. Nếu Finish[i] == true với mọi i, thì hệ thống ở trạng thái không có deadlock Ngược lại, các tiến trình Pi, Finish[i] == false sẽ ở trong tình trạng deadlock 11/7/2005 Trần Hạnh Nhi 32
  33. Sử dụng giải thuật phát hiện deadlock „ Khi nào, và mức độ thường xuyên cần kích hoạt giải thuật phát hiện deadlock ? Phụ thuộc vào „ Tần suất xảy ra deadlock? „ Số lượng các tiến trình liên quan, cần “rolled back”? „ 1 cho mỗi chu tri(nh rời nhau „ Một cách cẩn thận tối đa, kích hoạt giải thuật phát hiện mỗi khi có một yêu cầu cấp phát bị từ chối Chi phí cao „ Tiết kiệm chi phí : kích hoạt giải thuật phát hiện deadlock sau những chu kỳ định trước „ Khuyết điểm ? Thiếu thông tin 11/7/2005 Trần Hạnh Nhi 33
  34. Deadlock Recovery: Hủy bỏ tiến trình „ Hủy tất cả các tiến trình liên quan deadlock „ Thiệt hại đáng kể „ Hủy từng tiến trình liên quan cho đến khi giải toả được chu trình deadlock „ Tốn chi phí thực hiện giải thuật phát hiện deadlock „ Bắt đầu từ tiến trình nào ? Sau đó là ai ? „ Priority of the process. „ How long process has computed, and how much longer to completion. „ Resources the process has used. „ Resources process needs to complete. „ How many processes will need to be terminated. „ Is process interactive or batch? „ Sao cho thiệt hại ít nhất 11/7/2005 Trần Hạnh Nhi 34
  35. Deadlock Recovery: Thu hồi tài nguyên „ Lần lượt thu hồi một số tài nguyên từ các tiến trình và cấp phát các tài nguyên này cho những tiến trình khác đến khi giải toả được chu trình deadlock „ 3 vấn đề cần quan tâm : „ Chọn lựa “nạn nhân” : – Thu hồi tài nguyên nào ? Của ai ? „ Tiến trình nắm giữ nhiều tài nguyên „ Tiến trình có thời gian đã xử lý không cao „ ? „ Rollback : quay lại trạng thái an toàn (nào?), khởi động lại tiến trình từ trạng thái an toàn đó. „ Phải lưu vết hoạt động của hệ thống ->Chi phí cao „ Starvation: có thể một tiến trình nào đó luôn luôn bị chọn làm “nạn nhân”, không bao giờ có đủ tài nguyên để tiến triển xử lý. 11/7/2005 Trần Hạnh Nhi 35
  36. Deadlock Ignorance : Ostrich’s algorithm „ Hệ thống : “Deadlock hả ? What, what, what ???” „ Don’t see „ Don’t know „ Don’t care „ Có thể chấp nhận không ? „ Cân nhắc giữa tần suất xảy ra deadlock và chi phí giải quyết deadlock „ Là giải pháp của hầu hết HĐH hiện nay 11/7/2005 Trần Hạnh Nhi 36