›
›

Bài giảng Hệ điều hành - Chương 3: Deadlock - Lương Minh Huấn

pdf 62 trang Gia Huy 16/05/2022 6560
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 3: Deadlock - Lương Minh Huấn", để 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_3_deadlock_luong_minh_huan.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 3: Deadlock - Lương Minh Huấn

  1. TRƯỜNG ĐẠI HỌC SÀI GÒN CHƯƠNG 3: DEADLOCK GV: Lương Minh Huấn
  2. NỘI DUNG I. Khái niệm deadlock II. Điều kiện xảy ra deadlock III. Các phương pháp phòng tránh deadlock 1. Ngăn chặn deadlock 2. Phòng tránh deadlock 3. Phát hiện deadlock 4. Phục hồi deadlock
  3. I. KHÁI NIỆM DEADLOCK ➢Hệ thống gồm nhiều tiến trình hoạt động đồng thời cùng sử dụng tài nguyên. ▪ Tài nguyên cần nhiều loại (VD: CPU, bộ nhớ, ). ▪ Mỗi loại tài nguyên có nhiều đơn vị (VD: 2 CPU, 5 máy in ) ➢Mỗi tiến trình thường gồm dãy liên tục các thao tác ▪ Đòi hỏi tài nguyên: Nếu tài nguyên không có sẵn (đang được sử dụng bởi tiến trình khác) ) tiến trình yêu cầu phải đợi ▪ Sử dụng tài nguyên theo yêu cầu (in ấn, đọc dữ liệu ) ▪ Giải phóng tài nguyên được cấp
  4. I. KHÁI NIỆM DEADLOCK ➢Khi các tiến trình dùng chung ít nhất 2 tài nguyên, hệ thống có thể gặp "nguy hiểm" ➢Xét ví dụ: ▪ Hệ thống có hai tiến trình P1 & P2 ▪ Hai tiến trình P1 & P2 dùng chung hai tài nguyên R1 & R2 ▪ R1 được điều độ bởi đèn báo S1 (S1  1) ▪ R2 được điều độ bởi đèn báo S2 (S2  1)
  5. I. KHÁI NIỆM DEADLOCK
  6. I. KHÁI NIỆM DEADLOCK
  7. I. KHÁI NIỆM DEADLOCK ➢Hai (hay nhiều) ôtô đối đầu nhau trên 1 cây cầu hẹp chỉ đủ độ rộng cho 1 chiếc. ➢Mỗi đoạn của cây cầu có thể xem như 1 tài nguyên ➢Nếu deadlock xuất hiện: nó có thể được giải quyết nếu 1 hay 1 số ôtô lùi lại nhường đường rồi lên sau
  8. I. KHÁI NIỆM DEADLOCK ➢DeadLock là trạng thái trong hệ thống có ít nhất hai tiến trình đang dừng chờ lẫn nhau và chúng không thể chạy tiếp được. ➢Sự chờ đợi này có thể kéo dài vô hạn nếu không có sự tác động từ bên ngoài.
  9. II. ĐIỀU KIỆN XẢY RA DEADLOCK ➢Cần có 4 điều kiện sau, không được thiếu điều kiện nào: ➢Có tài nguyên găng: ▪ Tài nguyên được sử dụng theo mô hình không phân chia được (muntual exclusion). • Chỉ có một tiến trình dùng tài nguyên tại một thời điểm • Tiến trình khác cũng yêu cầu tài nguyên => yêu cầu phải được hõan lại tới khi tài nguyên được giải phóng. ▪ Chờ đợi trước khi vào đoạn găng (hold and wait). • Tiến trình không được vào đoạn găng phải xếp hàng chờ đợi. • Trong khi chờ đợi vẫn chiếm giữ các tài nguyên được cung cấp
  10. II. ĐIỀU KIỆN XẢY RA DEADLOCK ▪ Không có hệ thống phân phối lại tài nguyên găng (no preemption) • Tài nguyên không thể được trưng dụng • Tài nguyên được giải phóng chỉ bởi tiến trình đang chiếm giữ khi đã hoàn thành nhiệm vụ. ▪ Chờ đợi vòng tròn (circular wait): tồn tại 1 chu kỳ đóng các yêu cầu tài nguyên. • Tạo ra chu kỳ không kết thúc được.
  11. ĐỒ THỊ CUNG CẤP TÀI NGUYÊN ➢Dùng để mô hình hóa tình trạng bế tắc trong hệ thống ➢Là đồ thị định hướng gồm tập đỉnh V và tập cung E ➢Tập đỉnh V được chia thành 2 kiểu đỉnh: ▪ P = {P1; P2; ; Pn} Tập chứa tất cả các tiến trình trong hệ thống ▪ R = {R1; R2; ; Rm} Tập chứa tất cả các kiểu tài nguyên trong hệ thống. ➢Tập các cung E gồm 2 loại: ▪ Cung yêu cầu: đi từ tiến trình Pi tới tài nguyên Rj : Pi → Rj ▪ Cung sử dụng: đi từ tài nguyên Rj tới tiến trình Pi : Rj → Pi
  12. ĐỒ THỊ CUNG CẤP TÀI NGUYÊN ➢Khi một tiến trình Pi yêu cầu tài nguyên Rj 1. Cung yêu cầu Pi → Rj được chèn vào đồ thị 2. Nếu yêu cầu được thỏa mãn, cung yêu cầu chuyển thành cung sử dụng Rj → Pi 3. Khi tiến trình Pi giải phóng tài nguyên Rj , cung sử dụng Rj → Pi bị xóa khỏi đồ thị
  13. ĐỒ THỊ CUNG CẤP TÀI NGUYÊN
  14. ĐỒ THỊ CUNG CẤP TÀI NGUYÊN
  15. ĐỒ THỊ CUNG CẤP TÀI NGUYÊN
  16. ĐỒ THỊ CUNG CẤP TÀI NGUYÊN
  17. ĐỒ THỊ CUNG CẤP TÀI NGUYÊN ➢Đồ thị không chứa chu trình, không deadlock ➢Nếu đồ thị chứa đựng chu trình ▪ Nếu tài nguyên chỉ có 1 đơn vị => deadlock ▪ Nếu tài nguyên có nhiều hơn 1 đơn vị: có khả năng deadlock
  18. III. CÁC PHƯƠNG PHÁP XỬ LÝ BẾ TẮC ➢Ngăn ngừa ▪ Áp dụng các biện pháp để đảm bảo hệ thống không bao giờ rơi vào tình trạng deadlock. ▪ Tốn kém ▪ Áp dụng cho hệ thống hay xảy ra deadlock và tổn thất do deadlock gây ra lớn.
  19. III. CÁC PHƯƠNG PHÁP XỬ LÝ BẾ TẮC ➢Phòng tránh ▪ Kiểm tra từng yêu cầu tài nguyên của tiến trình và không chấp nhận yêu cầu nếu việc cung cấp tài nguyên có khả năng dẫn đến tình trạng deadlock. ▪ Thường yêu cầu các thông tin phụ trợ ▪ Áp dụng cho hệ thống ít xảy ra deadlock nhưng tổn hại lớn
  20. III. CÁC PHƯƠNG PHÁP XỬ LÝ BẾ TẮC ➢Nhận biết và khắc phục: ▪ Cho phép hệ thống hoạt động bình thường => có thể rơi vào tình trạng deadlock, ▪ Định kỳ kiểm tra xem deadlock có đang xảy ra không. ▪ Nếu đang deadlock, áp dụng các biện pháp loại bỏ deadlock. ▪ Áp dụng cho hệ thống ít xảy ra deadloc và thiệt hại không lớn.
  21. III.1 NGĂN NGỪA DEADLOCK ➢Nguyên tắc: tác động vào 1 trong 4 điều kiện cần của deadlock để nó không xảy ra. ▪ Tài nguyên găng ▪ Chờ đợi trước khi vào đoạn găng ▪ Trưng dụng tài nguyên găng ▪ Chờ đợi vòng tròn.
  22. III.1 NGĂN NGỪA DEADLOCK ➢Giảm tài nguyên găng ➢Giảm bớt mức độ găng của hệ thống ▪ Tài nguyên phân chia được (file chỉ đọc): sử dụng đồng thời ▪ Tài nguyên không phân chia được: sử dụng không đồng thời ➢Kỹ thuật SPOOL(Simultaneous peripheral operation on-line) ▪ Không phân phối tài nguyên khi không thực sự cần thiết ▪ Chỉ một số ít tiến trình có khả năng yêu cầu tài nguyên
  23. III.1 NGĂN NGỪA DEADLOCK
  24. III.1 NGĂN NGỪA DEADLOCK ➢Điều kiện chờ đợi trước khi vào gang ➢Nguyên tắc: đảm bảo một tiến trình xin tài nguyên chỉ khi không sở hữu bất kỳ tài nguyên nào khác. ➢Cung cấp trước ▪ Tiến trìnhh xin toàn bộ tài nguyên ngay từ đầu và chỉ thực hiện khi đã có đầy đủ tài nguyên ▪ Hiệu quả sử dụng tài nguyên thấp • Tiến trình chỉ sử dụng tài nguyên ở giai đọan cuối? • Tổng số tài nguyên đòi hỏi vượt quá khả năng của hệ thống?
  25. III.1 NGĂN NGỪA DEADLOCK ➢Giải phóng tài nguyên ▪ Tiến trình giải phóng tất cả tài nguyên trước khi xin (xin lại ) tài nguyên mới ▪ Nhận xét • Tốc độ thực hiện tiến trình chậm • Phải đảm bảo dữ liệu được giữ trong tài nguyên tạm giải phóng không bị mất
  26. III.1 NGĂN NGỪA DEADLOCK
  27. III.1 NGĂN NGỪA DEADLOCK
  28. III.1 NGĂN NGỪA DEADLOCK
  29. III.1 NGĂN NGỪA DEADLOCK
  30. III.1 NGĂN NGỪA DEADLOCK ➢Ngăn chặn không thể thu hồi ➢Nếu process A có giữ tài nguyên và đang yêu cầu tài nguyên khác nhưng tài nguyên này chưa cấp phát ngay được thì: ▪ Cách 1: Hệ thống lấy lại mọi tài nguyên mà A đang giữ • A chỉ bắt đầu lại được khi có được các tài nguyên đã bị lấy lại cùng với tài nguyên đang yêu cầu.
  31. III.1 NGĂN NGỪA DEADLOCK ▪ Cách 2: Hệ thống sẽ xem tài nguyên mà A yêu cầu • Nếu tài nguyên được giữ bởi một process khác đang đợi thêm tài nguyên, tài nguyên này được hệ thống lấy lại và cấp phát cho A. • Nếu tài nguyên được giữ bởi process không đợi tài nguyên, A phải đợi và tài nguyên của A bị lấy lại. Tuy nhiên hệ thống chỉ lấy lại các tài nguyên mà process khác yêu cầu
  32. III.1 NGĂN NGỪA DEADLOCK ➢Ngăn chặn chờ đợi vòng tròn. ➢Sắp xếp thứ tự cho tất cả loại tài nguyên và đòi hỏi mỗi tiến trình phải yêu cầu tài nguyên theo thứ tự đó. ➢Ví dụ, một tiến trình muốn dùng ổ đĩa và máy in tại cùng một lúc thì trước tiên phải yêu cầu ổ đĩa, nếu được cấp ổ đĩa thì mới yêu cầu máy in.
  33. III.2 PHÒNG TRÁNH DEADLOCK ➢Tránh tắc nghẽn (Deadlock Avoidance) đòi hỏi hệ điều hành có trước thông tin bổ sung liên quan đến tài nguyên mà một tiến trình sẽ yêu cầu và sử dụng trong suốt quá trình thực thi. ➢Yêu cầu mỗi tiến trình khai báo số lượng tối đa mỗi loại tài nguyên mà nó cần. ➢Giải thuật tránh tắc nghẽn sẽ kiểm tra trạng thái cấp phát tài nguyên (resource - allocationstate) để bảo đảm hệ thống không rơi vào deadlock. ➢Trạng thái cấp phát tài nguyên được định nghĩa dựa trên số tài nguyên còn lại, số tài nguyên đã được cấp phát và yêu cầu tối đa của các process.
  34. III.2 PHÒNG TRÁNH DEADLOCK ➢Trạng thái an toàn (safe) là trạng thái trong đó hệ thống có thể thỏa mãn tất cả các nhu cầu tài nguyên của mỗi tiến trình theo một thứ tự nào đó mà vẫn không xảy ra tắc nghẽn. Thứ tự này còn gọi là thứ tự an toàn (chuỗi an toàn). ➢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.
  35. III.2 PHÒNG TRÁNH DEADLOCK ➢Nếu hệ thống ở trạng thái an toàn => không có deadlock. ➢Nếu hệ thống ở trạng thái không an toàn => có thể có deadlock. ➢Sự tránh khỏi deadlock => đảm bảo rằng hệ thống sẽ không bao giờ bước vào trạng thái không an toàn: ▪ Mỗi loại tài nguyên có 1 instance: giải thuật đồ thị phân phối tài nguyên. ▪ Mỗi loại tài nguyên có nhiều instance: giải thuật chủ nhà bang (banker).
  36. III.2 PHÒNG TRÁNH DEADLOCK ➢Thuật toán đồ thị phân phối tài nguyên: ➢Sử dụng khi mỗi kiểu tài nguyên chỉ có 1 đơn vị (instance) ▪ Có chu trình, sẽ có deadlock ➢Thêm vào đồ thị loại cung mới: cung đòi hỏi Pi → Rj ▪ Cùng hướng với cung yêu cầu, thể hiện trong đồ thị  ▪ Cho biết Pi có thể yêu cầu Rj trong tương lai
  37. III.2 PHÒNG TRÁNH DEADLOCK ➢Tiến trình khi tham gia hệ thống, phải thêm tất cả các cung đòi hỏi tương ứng vào đồ thị ▪ Khi Pi yêu cầu Rj , cung đòi hỏi Pi  Rj chuyển thành cung yêu cầu Pi → Rj ▪ Khi Pi giải phóng Rj , cung sử dụng Rj → Pi chuyển thành cung đòi hỏi Pi  Rj
  38. III.2 PHÒNG TRÁNH DEADLOCK ➢Thuật toán: yêu cầu tài nguyên Rj của tiến trình Pi được thỏa mãn chỉ khi việc chuyển cung yêu cầu Pi → Rj thành cung sử dụng Rj → Pi không tạo chu trình trên đồ thị. ▪ Không chu trình: Hệ thống an toàn ▪ Có chu trình: Việc cung cấp tài nguyên đẩy hệ thống vào tình trạng không an toàn
  39. III.2 PHÒNG TRÁNH DEADLOCK
  40. III.2 PHÒNG TRÁNH DEADLOCK
  41. III.2 PHÒNG TRÁNH DEADLOCK
  42. III.2 PHÒNG TRÁNH DEADLOCK
  43. III.2 PHÒNG TRÁNH DEADLOCK
  44. III.2 PHÒNG TRÁNH DEADLOCK
  45. III.2 PHÒNG TRÁNH DEADLOCK
  46. III.2 PHÒNG TRÁNH DEADLOCK ➢ Giải thuật nhà băng: ➢ Khi tiến trình mới đưa vào hệ thống, nó phải khai báo số tối đa các đơn vị của mỗi loại tài nguyên mà nó cần. Số này có thể không vượt quá tổng số tài nguyên trong hệ thống. ➢ Khi một tiến trình yêu cầu cấp phát tài nguyên, hệ thống phải xác định sau khi cấp phát các tài nguyên này hệ thống có vẫn ở trong trạng thái an toàn hay không. ▪ Nếu trạng thái hệ thống sẽ vẫn là an toàn, tài nguyên sẽ được cấp ▪ Ngược lại, tiến trình phải chờ cho tới khi một vài tiến trình giải phóng đủ tài nguyên. ➢ Giải thuật nhà băng dung để xác định trạng thái hiện tại có an toàn hay không?
  47. III.2 PHÒNG TRÁNH DEADLOCK ➢Bước1: Từ bảng trạng thái lập bảng nhu cầu trong đó thay cột Max bằng cột Cần với công thức tính toán Cần= Max – Chiếm. Cột Cần thể hiện số lượng mỗi loại tài nguyên cần cung cấp thêm cho mỗi tiến trình. ➢Bước2:
  48. III.2 PHÒNG TRÁNH DEADLOCK While i: (Cần(Pi)<>0) and (Cần(Pi)<=Còn) Begin Còn= Còn+Chiếm(Pi); Cần(Pi)=0; Chiếm(Pi)=0; End ➢If i: Cần(Pi)=0 Then “Trạngtháian toàn” Else “Trạngtháikhôngan toàn”
  49. III.2 PHÒNG TRÁNH DEADLOCK if Not(Request(P)<= Còn) Then “Khôngcấpđược” Else Begin 1. Lập bảng trạng thái sau khi cấp tài nguyên cho P: Còn= Còn–Request(P); Chiếm(P)= Chiếm(P)+ Request(P); Max(P)=Max(P); Các số liệu ứng với các tiến trình khác giữ nguyên; 2. Kiểm tra trạng thái trên có an toàn không 3. If (An toàn) then “Cấp ngay” else “Khôngcấpngay” end
  50. III.2 PHÒNG TRÁNH DEADLOCK
  51. III.3 PHÁT HIỆN DEADLOCK ➢Nguyên tắc ▪ Không áp dụng các biện pháp ngăn ngừa hoặc phòng tránh, để cho deadlock xảy ra. ▪ Định kỳ kiểm tra xem deadloc có đang xảy ra không. Nếu có tìm cách khắc phục ▪ Để thực hiện, hệ thống phải cung cấp • Thuật toán xác định hệ thống đang deadlock không • Thuật toán chứa deadlock,
  52. III.3 PHÁT HIỆN DEADLOCK ➢Nhận biết deadlock ▪ Thuật toán dựa trên đồ thị cung cấp tài nguyên ▪ Thuật toán chỉ ra deadlock tổng quát ➢Khắc phục deadlock ▪ Kết thúc tiến trình ▪ Trưng dụng tài nguyên
  53. III.3 PHÁT HIỆN DEADLOCK ➢Thuật toán dựa trên đồ thị cung cấp tài nguyên: ➢Áp dụng khi mỗi tài nguyên trong hệ thống có một đơn vị. ➢Kiểm tra hệ thống có deadloc bằng cách kiểm tra chu trình trên đồ thị ▪ Nếu trên đồ thị có chu trình, hệ thống đang deadlock. ➢Định kỳ gửi tới các thuật toán kiểm tra chu trình trên đồ thị ▪ Thuật toán đòi hỏi n2 thao tác (n: số đỉnh của đồ thị)
  54. III.3 PHÁT HIỆN DEADLOCK ➢Sử dụng đồ thị chờ đợi - phiên bản thu gọn của đồ thị cung cấp tài nguyên ▪ Chỉ có các đỉnh dạng tiến trình ▪ Cung chờ đợi Pi → Pj : Tiến trình Pi đang đợi tiến trình Pj giải phóng tài nguyên Pi cần ▪ Cung chờ đợi Pi → Pj tồn tại trên đồ thị đợi khi và chỉ khi trên đồ thị phân phối tài nguyên tương ứng tồn tại đồng thời cung yêu cầu Pi → R và cung sử dụng R → Pj
  55. III.3 PHÁT HIỆN DEADLOCK
  56. III.3 PHÁT HIỆN DEADLOCK ➢Thuật toán chỉ ra deadlock tổng quát: ➢Sử dụng cho các hệ thống có các kiểu tài nguyên gồm nhiều đơn vị. ➢Thuật toán tương tự thuật toán nhà băng
  57. III.3 PHÁT HIỆN DEADLOCK
  58. III.3 PHÁT HIỆN DEADLOCK
  59. III.4 PHỤC HỒI DEADLOCK ➢Nguyên tắc: ▪ Trưng dụng liên tục một vài tài nguyên từ một số tiến trình đang deadlock cho các tiến trình khác đến khi deadlock được hủy bỏ. ➢Các vấn đề cần quan tâm: ▪ Lựa chọn nạn nhân (victim): • Tài nguyên nào và tiến trình nào được chọn? • Trật tự trưng dụng để chi phí nhỏ nhất? • Lượng tài nguyên nắm giữ, thời gian sử dụng
  60. III.4 PHỤC HỒI DEADLOCK ▪ Quay lui (Rollback) • Quay lui tới một trạng thái an toàn trước đó và bắt đầu lại • Yêu cầu lưu giữ thông tin trạng thái của tiến trình đang thực hiện. ▪ Đói tài nguyên (Starvation) • Một tiến trình bị trưng dụng quá nhiều lần => chờ đợi vô hạn • Giải pháp: ghi lại số lần bị trưng dụng