Bài giảng Hệ điều hành: Chương 6 - Trần Công Án (ĐH Cần Thơ)

Bài giảng "Hệ điều hành - Chương 6: Deadlock (Khóa chết)" cung cấp các kiến thức giúp người đọc có thể mô tả tình trạng deadlock của hệ thống – một trạng thái mà các tiến trình không thể tiến triển để hoàn thành các tác vụ của chúng, trình bày các phương pháp để ngăn chặn hoặc tránh deadlock,... Mời các bạn cùng tham khảo
Nội dung trích xuất từ tài liệu:
Bài giảng Hệ điều hành: Chương 6 - Trần Công Án (ĐH Cần Thơ) CT107. Hệ Điều HànhChương 6. Deadlock (Khóa Chết)Giảng viên: Trần Công Án (tcan@cit.ctu.edu.vn) Bộ môn Mạng máy tính & Truyền thông Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ 2014 [CT107] Ch6. Deadlock Mục Tiêu I Mô tả tình trạng deadlock của hệ thống – một trạng thái mà các tiến trình không thể tiến triển để hoàn thành các tác vụ của chúng. I Trình bày các phương pháp để ngăn chặn hoặc tránh deadlock; và các biện pháp để phát hiện và phục hồi hệ thống một khi deadlock xảy ra.TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 2 [CT107] Ch6. Deadlock Nội DungTS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 3 [CT107] Ch6. Deadlock Giới thiệu Deadlock Deadlock là gì? Deadlock Là Gì? I Deadlock là một trạng thái của hệ thống trong đó: I một tập hợp các tiến trình đang bị nghẽn I mỗi tiến trình đang giữ một tài nguyên và cũng đang chờ một tài nguyên đang bị giữ bởi một tiến trình khác trong tập các tiến trình đang bị nghẽn. I Ví dụ 1: I Giả sử 1 hệ thống có 2 tiến trình P và Q và F1, F2 là 2 tập tin. I Tiến trình P đang giữ F1 và cần truy xuất thêm F2. I Tiến trình Q đang giữ F2 và cần truy xuất thêm F1.TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 4 [CT107] Ch6. Deadlock Giới thiệu Deadlock Deadlock là gì? Ví Dụ 342 2 – Traffic Deadlock Chapter 7 Deadlocks • • • • • • • • • • • • Figure 7.10 Traffic deadlock for Exercise 7.11.TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 5 [CT107] Ch6. Deadlock Giới thiệu Deadlock Điều kiện phát sinh deadlock Điều Kiện Phát Sinh Deadlock 1. Loại trừ hỗ tương: ít nhất một tài nguyên được giữ ở chế độ không chia sẻ (nonsharable mode). 2. Giữ và chờ: một tiến trình đang giữ ít nhất một tài nguyên và đợi thêm tài nguyên đang bị giữ bởi tiến trình khác. 3. Không trưng dụng tài nguyên: không trưng dụng tài nguyên cấp phát tiến trình, trừ khi tiến trình tự hoàn trả. 4. Chờ đợi vòng tròn: tồn tại một tập các tiến trình {P0 , P1 , . . . , Pn } đang chờ đợi như sau: P0 đợi một tài nguyên P1 đang giữ, P1 đợi một tài nguyên P2 đang giữ, . . . , Pn đang đợi một tài nguyên P0 đang giữ.TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 6 [CT107] Ch6. Deadlock Giới thiệu Deadlock Mô hình hóa hệ thống Mô Hình Hóa Hệ Thống I Hệ thống gồm một tập các loại tài nguyên, kí hiệu R1 , R2 , . . . , Rm I Ví dụ: CPU cycles, memory space, I/O devices, . . . I Mỗi loại tài nguyên Ri có một tập các thể hiện (instances) Wi I Tiến trình sử dụng tài nguyên theo các bước: 1. Yêu cầu (request) – phải chờ nếu không được đáp ứng ngay. 2. Sử dụng (use) 3. Giải phóng (release) I Các tác vụ yêu cầu và hoàn trả được thực hiện bằng các lời gọi hệ thống.TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 7 [CT107] Ch6. Deadlock Giới thiệu Deadlock Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên – RAG I Là đồ thị có hướng, với tập đỉnh V và tập cạnh E I Tập đỉnh V gồm 2 loại: I Tập P = {P1 , P2 , . . . , Pn }: tập các tiến trình trong hệ thống I Tập R = {R1 , R2 , . . . , Rm }: tập các tài nguyên của hệ thống I Tập cạnh cũng gồm 2 loại: I Cạnh yêu cầu (request edge): có hướng từ Pi đến Rj I Cạnh cấp phát (assignment edge): có hướng từ RJ đến PiTS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 8 [CT107] Ch6. Deadlock Giới thiệu Deadlock Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Ký Hiệu Pi I Tiến trình: ●● ●● I Loại tài nguyên (với 4 th ...