Lý thuyết hệ điều hành - Chương 5

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

99
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Điều kiện mutual exclusion: các quá trình cần thực hiện loại trừ tương hỗ trên vùng tranh chấp. Điều kiện hold & wait: quá trình đang giữ tài nguyên có thể yêu cầu thêm tài nguyên khác. Điều kiện no-preemption: tài nguyên chỉ được giải phóng khi quá trình dùng xong. Điều kiện circular-wait: các quá trình giữ và đợi tài nguyên tạo thành vòng luẩn quẩn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lý thuyết hệ điều hành - Chương 5

Chương 5 DEADLOCK -1- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
CHƯƠNG 5 : DEADLOCK Định nghĩa deadlock   Điều kiện để có deadlock  Các phương pháp giải quyết Chống deadlock – Tránh deadlock – Phát hiện deadlock – Phục hồi deadlock – Bài tập  -2- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
ĐỊNH NGHĨA Quá trình deadlock : đợi một sự kiện không bao giờ xảy ra.  Một hệ thống bị deadlock : có quá trình bị deadlock.  P1 10KB 8KB P2 8KB 4KB spooler 3KB P3 7KB printer 15KB buffer Tắc nghẽn trong giao thông Tắc nghẽn trong quản lý in ấn -3- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ & BẢN CHẤT DEADLOCK Hai quá trình bị deadlock: Dạng deadlock: Process1 Process2 P(S1); P(S2); P(S2); P(S1); R1 R2 Critical Critical Section; Section; V(S2); V(S1); V(S1); Process1 Process2 V(S2); -4- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
DEADLOCK VÀ TRÌ HOÃN VÔ HẠN ĐỊNH Deadlock  Đợi sự kiện không bao giờ xảy ra – Nguyên nhân ? – Trì hoãn vô hạn định (Indefinite postponement)  Đợi sự kiện có thể xảy ra nhưng không xác định thời điểm – Biểu hiện như deadlock – Nguyên nhân ? – Deadlock có khác vòng lặp vô hạn ?  -5- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
ĐIỀU KIỆN XẢY RA DEADLOCK 1. Điều kiện mutual exclusion: các quá trình cần thực hiện loại trừ tương hỗ trên vùng tranh chấp 2. Điều kiện hold & wait: quá trình đang giữ tài nguyên có thể yêu cầu thêm tài nguyên khác 3. Điều kiện no-preemption: tài nguyên chỉ được giải phóng khi quá trình dùng xong 4. Điều kiện circular-wait: các quá trình giữ và đợi tài nguyên tạo thành vòng luẩn quẩn -6- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI QUYẾT DEADLOCK Ngăn ngừa deadlock (deadlock prevention)  Qui định cấp , dùng tài nguyên nghiêm ngặt – Không cho các điều kiện deadlock xảy ra – Tránh deadlock (deadlock avoidance)  Vẫn cho các điều kiện deadlock tồn tại – Cấp tài nguyên hợp lý, an toàn – Phát hiện deadlock (deadlock detection)   Phục hồi deadlock (deadlock recovery) -7- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
NGĂN NGỪA DEADLOCK (Havender) Cấm điều kiện multual-exclusion ?   Cấm điều kiện hold & wait Quá trình yêu cầu tất cả tài nguyên một lần – Chỉ được xử lý khi đã đủ tất cả tài nguyên cầøn thiết – Cấm điều kiện no-preemption  Nếu yêu cầu tài nguyên không được, quá trình phải giải phóng – tất cả tài nguyên đang giữ và yêu cầu lại. (?) Loại bỏ circular-wait  Sắp xếp tài nguyên theo trật tự và chung cấp cho quá trình theo – đúng trật tự đó. Chứng minh ? -8- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
NGĂN NGỪA DEADLOCK (Havender) Ví dụ  Yêu cầu Quá trình thực tế P1 R6, R4, R1 P2 R2, R5, R4 P3 R3, R7, R1 P3 P1 R1 R2 R3 R4 R5 R6 R7 P2 Nhận xét về p/p ngăn ngừa deadlock  -9- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
TRÁNH DEADLOCK Giải thuật nhà băng (Banker’s Algorithm)  Hệ điều hành ~ nhà Băng – Quá trình ~ khách hàng – Tài nguyên ~ vốn vay – Ràng buộc  Yêu cầu vay cực đại  vốn nhà băng – Khách không trả vốn nếu vay chưa đủ yêu cầu cực đại – Khi vay đủ, khách phải trả đủ vốn sau thời gian hữu hạn – Trạng thái nhà băng  An toàn (Safe): thỏa yêu cầu mọi khách, ngân hàng thu vốn đủ – Không an toàn ( Unsafe) : ngược lại  có thể deadlock – Hệ thống phải cấp phát tài nguyên sao cho không rơi vào trạng  thái Unsafe -10- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ Trạng thái sau là an toàn. Tại sao ?  Đang mượn Cần tối đa Cần thêm P1 1 4 3 P2 4 6 2 P3 5 8 3 Vôn 12 , còn lại 2 Trạng thái sau là không an toàn. Tại sao ?  Đang mượn Cần tối đa Cần thêm P1 8 10 2 P2 2 5 3 P3 1 3 2 Vôn 12 , còn lại 1 -11- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
PHÁT HIỆN DEADLOCK Ghi nhận, theo dõi yêu cầu, sự cấp phát tài nguyên  cho các quá trình. Dùng đồ thị RAG (Resource Allocation Graph)  P1 yêu cầu n tài nguyên loại R1 n Quá trình R1 P1 P2 đang giữ 1 tài nguyên loại R2 Tài nguyên R2 P2 Tài nguyên -12- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
PHÁT HIỆN DEADLOCK Giản lược RAG  1. Tài nguyên rảnh  cấp cho quá trình yêu cầu 2. Quá trình đủ tài nguyên  xoá mọi cạnh vào, xoá quá qtrình 3. Lặp lại 1 với các quá trình khác đến khi tối giản Khi giải thuật dừng  RAG không còn cạnh: không có deadlock – RAG có chu trình (cycle): deadlock – Nhận xét  Phí tổn lớn – -13- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ 1 : GIẢN ƯỚC RAG P2 P3 R3 P2 P3 R3 R1 R1 P4 P4 P1 P1 R2 R2 P2 P3 R3 P2 P3 R3 R1 R1 P4 P4 P1 R2 P1 R2 -14- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
BÀI TẬP : GIẢN ƯỚC RAG R1 P2 P1 R5 R6 P4 R2 P3 -15- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
PHỤC HỒÀI DEADLOCK  Đikèm với p.p phát hiện deadlock  Thực hiện Chọn lựa quá trình để thu hồi tài nguyên – Treo (suspend) quá trình – Thu hồi tài nguyên (preemptive) – Phục hồi (resume) các quá trình còn lại – có thể giải quyết trọn vẹn  Khó -16- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
BÀI TẬP 1. Hệ thống 1 tốn 10% thời gian cho mỗi ứng dụng để ngăn ngừa deadlock. Hệ thống 2 không ngăn ngừa nên cần 10% thời gian ứng dụng để phục hồi mỗi ứng dụng bị deadlock. So sánh phí tổn 2 hệ thống. 2. Tìm trạng thái của hệ thống sau Đã mượn Nhu cầu tối đa Khách A B C A B C P1 1 1 0 1 3 0 P2 0 1 1 1 1 2 P3 1 0 0 1 1 3 P4 0 1 0 2 1 0 -17- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM