Bài Giảng Hệ Điều Hành-Chương 6: Deadlocks

Phát triển một mô tả deadlocks, hiện tượng ngăn cản tập các giao dịch cạnh tranh hoàn tất nhiệm vụ của chúng Giới thiệu một số phương pháp khác nhau để ngăn ngừa, tránh deadlocks trong hệ thống máy tính. Giới thiệu phương pháp phát hiện và phục hồi từ deadlocks
Nội dung trích xuất từ tài liệu:
Bài Giảng Hệ Điều Hành-Chương 6: Deadlocks Chương 6: Deadlocks Ch NỘI DUNG Vấn Deadlock Mô hình hệ thống Đặc trư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ục hồi từ Deadlock Silberschatz, Galvin and Gagne ©2005 Operating System Concepts - 7th Edition, Feb 14, 2005 7.2 MỤC TIÊU Phát triển một mô tả deadlocks, hiện tượng ngăn cản tập các giao dịch cạnh tranh hoàn tất nhiệm vụ của chúng Giới thiệu một số phương pháp khác nhau để ngăn ngừa, tránh deadlocks trong hệ thống máy tính. Giới thiệu phương pháp phát hiện và phục hồi từ deadlocks Silberschatz, Galvin and Gagne ©2005 Operating System Concepts - 7th Edition, Feb 14, 2005 7.3 VẤN ĐỀ Deadlock Một tập các quá trình bị nghẽn, mỗi một chiếm giữ một tài nguyên và chờ đợi tậu tài nguyên bị chiếm giữ bởi quá trình khác trong tập hợp. VD. Hệ thống có hai ổ đĩa. P1 và P2 mỗi một chiếm giữ một ổ đĩa và mỗi một cần ổ đĩa kia. VD. semaphores A và B, được khởi động là 1 P0 P1 wait (A); wait(B) wait (B); wait(A) Silberschatz, Galvin and Gagne ©2005 Operating System Concepts - 7th Edition, Feb 14, 2005 7.4 VÍ DỤ QUA CẦU Lưu thông chỉ theo một chiều. Mỗi phần của cầu được xem như một tài nguyên. Nếu deadlock xảy ra nó sẽ được giải quyết nếu một xe lùi lại (trưng các tài nguyên và cuộn lại). Một vài xe có thể bị lùi lại khi deadlock xảy ra. Có thể xảy ra “sự chết đói”. Silberschatz, Galvin and Gagne ©2005 Operating System Concepts - 7th Edition, Feb 14, 2005 7.5 MÔ HÌNH HỆ THỐNG Các kiểu tài nguyên: R1, R2, . . ., Rm Các chu kỳ CPU, không gian bộ nhớ, các thiết bị 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: Yêu cầu tài nguyên Sử dụng tài nguyên Giải phóng tài nguyên Silberschatz, Galvin and Gagne ©2005 Operating System Concepts - 7th Edition, Feb 14, 2005 7.6 ĐẶC TRƯNG DEADLOCK Điều kiện cần để deadlock xảy ra: Loại trừ tương hỗ (Mutual exclusion): chỉ một quá trình sử dụng một tài nguyên tại một thời điểm. Giữ và chờ (Hold and wait): một quá trình chiếm giữ ít nhất một tài nguyên và chờ tậu các tài nguyên bổ xung bị chiếm giữ 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ể được giải phóng bởi sự tình nguyện của quá trình chiếm giữ nó (sau khi quá trình đã hoàn thành nhiệm vụ của nó). Chờ đợi vòng tròn: Tồn tại một tập {P0, P1, …, P0} các quá trình chờ đợi sao cho P0 chờ một tài nguyên bị chiếm giữ bởi P1, P1 chờ một tài nguyên bị chiếm giữ bởi P2, …, Pn–1 chờ một tài nguyên bị chiếm giữ bởi Pn, và Pn chờ một tài nguyên bị chiếm giữ bởi P0. Silberschatz, Galvin and Gagne ©2005 Operating System Concepts - 7th Edition, Feb 14, 2005 7.7 ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN Một tập các đỉnh V và một tập các cung E. V được phân hoạch thành hai kiểu: P = {P1, P2, …, Pn}, gồm tất cả các quá trình trong hệ thống. R = {R1, R2, …, Rm}, gồm tất cả các kiểu tài nguyên trong hệ thống. Cung yêu cầu – cung hướng từ Pi đến Rj : Pi → Rj Cung gán – hướng từ Rj đến Pi : Rj → Pi Silberschatz, Galvin and Gagne ©2005 Operating System Concepts - 7th Edition, Feb 14, 2005 7.8 ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN (Cont.) Quá trình Kiều tài nguyên với 4 thể hiện Pi Pi yêu cầu thể hiện của Rj Rj Pi đang chiếm giữ một thể hiện của kiểu tài nguyên Rj Pi ...