tailieunhanh - Hệ điều hành ( Vũ Đức Lung ) - Chương 6

Phương pháp kết hợp để giải quyết Deadlock. Vấn đề deadlock trong hệ thống. Tình huống: một tập các process bị blocked, mỗi process giữ tài nguyên và đang chờ tài nguyên mà process khác trong tập đang giữ | Khoa KTMT Chương 6 : Tắc nghẽn(Deadlock) Mô hình hệ thống Định nghĩa Điều kiện cần của deadlock Resource Allocation Graph (RAG) Phương pháp giải quyết deadlock Deadlock prevention Deadlock avoidance Deadlock detection Deadlock recovery Phương pháp kết hợp để giải quyết Deadlock Khoa KTMT Vấn đề deadlock trong hệ thống Tình huống: một tập các process bị blocked, mỗi process giữ tài nguyên và đang chờ tài nguyên mà process khác trong tập đang giữ. Ví dụ 1 Giả sử hệ thống có 2 file trên đĩa. P1 và P2 mỗi process đang mở một file và yêu cầu mở file kia. Ví dụ 2 Semaphore A và B, khởi tạo bằng 1 P0 P1 wait(A); wait(B); wait(B); wait(A); Khoa KTMT Mô hình hóa hệ thống Hệ thống gồm các loại tài nguyên, kí hiệu R1, R2, , Rm , bao gồm: CPU cycle, không gian bộ nhớ, thiết bị I/O, file, semaphore, Mỗi loại tài nguyên Ri có Wi thực thể (instance). Giả sử tài nguyên tái sử dụng theo kỳ (Serially Reusable Resources) Yêu cầu (request): process phải chờ nếu yêu cầu không được đáp ứng . | Khoa KTMT Chương 6 : Tắc nghẽn(Deadlock) Mô hình hệ thống Định nghĩa Điều kiện cần của deadlock Resource Allocation Graph (RAG) Phương pháp giải quyết deadlock Deadlock prevention Deadlock avoidance Deadlock detection Deadlock recovery Phương pháp kết hợp để giải quyết Deadlock Khoa KTMT Vấn đề deadlock trong hệ thống Tình huống: một tập các process bị blocked, mỗi process giữ tài nguyên và đang chờ tài nguyên mà process khác trong tập đang giữ. Ví dụ 1 Giả sử hệ thống có 2 file trên đĩa. P1 và P2 mỗi process đang mở một file và yêu cầu mở file kia. Ví dụ 2 Semaphore A và B, khởi tạo bằng 1 P0 P1 wait(A); wait(B); wait(B); wait(A); Khoa KTMT Mô hình hóa hệ thống Hệ thống gồm các loại tài nguyên, kí hiệu R1, R2, , Rm , bao gồm: CPU cycle, không gian bộ nhớ, thiết bị I/O, file, semaphore, Mỗi loại tài nguyên Ri có Wi thực thể (instance). Giả sử tài nguyên tái sử dụng theo kỳ (Serially Reusable Resources) Yêu cầu (request): process phải chờ nếu yêu cầu không được đáp ứng ngay Sử dụng (use): process sử dụng tài nguyên Hoàn trả (release): process hoàn trả tài nguyên Các tác vụ yêu cầu (request) và hoàn trả (release) đều là system call. Ví dụ request/release device open/close file allocate/free memory wait/signal Khoa KTMT Định nghĩa Một tiến trình gọi là deadlocked nếu nó đang đợi một sự kiện mà sẽ không bao giờ sảy ra. Thông thường, có nhiều hơn một tiến trình bị liên quan trong một deadlock. Một tiến trình gọi là trì hoãn vô hạn định (indefinitely postponed) nếu nó bị trì hoãn một khoảng thời gian dài lặp đi lặp lại trong khi hệ thống đáp ứng cho những tiến trình khác . . Một tiến trình sẵn sàng để xử lý nhưng nó không bao giờ nhận được CPU. Khoa KTMT Điều kiện cần để xảy ra deadlock Bốn điều kiện cần (necessary condition) để xảy ra deadlock Loại trừ hỗ tương (Mutual exclusion): ít nhất một tài nguyên được giữ theo nonsharable mode (ví dụ: printer; ví dụ sharable resource: read-only files). Giữ và chờ cấp thêm tài nguyên (Hold and wait): một .