tailieunhanh - Bài giảng Hệ điều hành: Chương 4 - Deadlock

Bài giảng Hệ điều hành: Chương 4 - Deadlock trình bày về mô hình hệ thống; Resource Allocation Graph (RAG); phương pháp giải quyết deadlock; Deadlock prevention; Deadlock avoidance; Deadlock detection; Deadlock recovery. Mời các bạn tham khảo. | 4. Deadlock Mô hình hệ thống Resource Allocation Graph (RAG) Phương pháp giải quyết deadlock Deadlock prevention Deadlock avoidance Deadlock detection Deadlock recovery 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ụ Giả sử hệ thống có một printer và một DVD drive. Quá trình P1 đang giữ DVD drive, quá trình P2 đang giữ printer. Bây giờ P1 yêu cầu printer và phải đợi, và P2 yêu cầu DVD drive và phải đợi. 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 Tài nguyên: CPU cycle, không gian bộ nhớ, thiết bị I/O, file, Mỗi loại tài nguyên Ri có Wi thực thể (instance). Process sử dụng tài nguyên theo thứ tự 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 và hoàn trả được gọi qua system call. Ví dụ request/release device open/close file allocate/free memory Điều kiện cần để xảy ra deadlock (1/2) Bốn điều kiện cần (necessary condition) để xảy ra deadlock Mutual exclusion: một tài nguyên có thể được cấp phát cho nhiều lắm là 1 quá trình (tức là không chia sẻ được) Hold and wait: một quá trình đang giữ một tài nguyên được phép yêu cầu thêm tài nguyên khác. Điều kiện cần để xảy ra deadlock (2/2) No preemption: (= no resource preemption) không lấy lại tài nguyên đã cấp phát cho quá trình, ngoại trừ khi quá trình tự hoàn trả nó. Circular wait: tồn tại một tập {P1, ,Pn} các quá trình đang đợi sao cho P1 đợi một tài nguyên mà P1 đang giữ P2 đợi một tài nguyên mà P2 đang giữ Pn đợi một tài nguyên mà P0 đang giữ Để ý: tài nguyên có thể gồm nhiều instance Resource Allocation Graph (1/2) Resource allocation graph (RAG) là đồ thị có hướng, với tập đỉnh V và tập cạnh E Tập đỉnh V gồm 2 loại: P = {P1, P2, , Pn } (Tất cả process trong hệ thống) R = {R1, R2, , Rm } (Tất cả các loại tài . | 4. Deadlock Mô hình hệ thống Resource Allocation Graph (RAG) Phương pháp giải quyết deadlock Deadlock prevention Deadlock avoidance Deadlock detection Deadlock recovery 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ụ Giả sử hệ thống có một printer và một DVD drive. Quá trình P1 đang giữ DVD drive, quá trình P2 đang giữ printer. Bây giờ P1 yêu cầu printer và phải đợi, và P2 yêu cầu DVD drive và phải đợi. 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 Tài nguyên: CPU cycle, không gian bộ nhớ, thiết bị I/O, file, Mỗi loại tài nguyên Ri có Wi thực thể (instance). Process sử dụng tài nguyên theo thứ tự 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 và hoàn trả được gọi qua system call. Ví dụ .