Bài giảng Nguyên lý hệ điều hành (Bài giảng tuần 5) - Nguyễn Hải Châu

Trong hệ thống máy tính, tình huống bế tắc (Deadlock) xuất hiện khi hai tiến trình phải chờ đợi nhau giải phóng tài nguyên hoặc nhiều tiến trình chờ sử dụng các tài nguyên theo một “vòng tròn” (circular chain). Trong bài giảng tuần 5 này, các bạn sẽ cùng tìm hiểu các đinh nghĩa cơ bản về bế tắc, các phương pháp xử lý bế tắc trong hệ điều hành, cách ngăn chặn bế tắc (Deadlock prevention), cách tránh bế tắc (Deadlock avoidance),... 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 Nguyên lý hệ điều hành (Bài giảng tuần 5) - Nguyễn Hải Châu Nguyên lý hệ điều hành Bế tắc (Deadlock) Nguyễn Hải Châu Khoa Công nghệ thông tin Trường Đại học Công nghệ 1 2 Định nghĩa Hai con dê qua cầu: Bế tắc z Bế tắc là tình huống xuất hiện khi hai hay nhiều “hành động” phải chờ một hoặc nhiều hành động khác để kết thúc, nhưng không bao giờ thực hiện được z Máy tính: Bế tắc là tình huống xuất hiện khi hai tiến trình phải chờ đợi nhau giải phóng tài nguyên hoặc nhiều tiến trình chờ sử dụng các tài nguyên theo một “vòng tròn” (circular chain) 3 4 Bế tắc giao thông tại ngã tư Bế tắc trong máy tính z Tiến trình A: z Tiến trình B { { … … Khóa file F1; Khóa file F2; ... ... Mở file F2; Mở file F1; … … Đóng F1 (mở khóa F1); Đóng F1 (mở khóa F1); } } 5 6 1 Qui trình sử dụng tài nguyên Điều kiện cần để có bế tắc z Một tiến trình thường sử dụng tài nguyên z Bế tắc xuất hiện nếu 4 điều kiện sau xuất theo các bước tuần tự sau: hiện đồng thời (điều kiện cần): z Xin phép sử dụng (request) z C1: Loại trừ lẫn nhau (mutual exclusion) z Sử dụng tài nguyên (use) z C2: Giữ và chờ (hold and wait) z Giải phóng tài nguyên sau khi sử dụng (release) z C3: Không có đặc quyền (preemption) z C4: Chờ vòng (circular wait) 7 8 C1: Loại trừ lẫn nhau C2: Giữ và chờ z Một tài nguyên bị chiếm bởi một tiến trình, và z Một tiến trình giữ ít nhất một tài nguyên và không tiến trình nào khác có thể sử dụng tài chờ một số tài nguyên khác rỗi để sử dụng. nguyên này Các tài nguyên này đang bị một tiến trình khác chiếm giữ 9 10 C3: Không có đặc quyền C3: Chờ vòng z Tài nguyên bị chiếm giữ chỉ có thể rỗi khi tiến z Một tập tiến trình {P0, P1, ..., Pn} có xuất hiện trình “tự nguyện” giải phóng tài nguyên sau điều kiện “chờ vòng” nếu P0 chờ một tài khi đã sử dụng xong. nguyên do P1 chiếm giữ, P1 chờ một tài nguyên khác do P2 chiếm giữ, ..., Pn-1 chờ tài nguyên do Pn chiếm giữ và Pn chờ tài nguyên do P0 chiếm giữ 11 12 2 Đồ thị cấp phát tài nguyên Đồ thị cấp phát tài nguyên z Thuật ngữ: Resource allocation graph z Cung có hướng từ tiến trình Pi đến tài z Để mô tả một cách chính xác bế tắc, chúng nguyên Rj, ký hiệu là Pi→Rj có ý nghĩa: Tiến ta sử dụng đồ thị có hướng gọi là “đồ thị cấp trình Pi yêu cầu một thể hiện của Ri. Ta gọi phát tài nguyên” G=(V, E) với V là tập đỉnh, E Pi→Rj là cung yêu cầu (request edge) là tập cung z Cung có hướng từ tài nguyên Rj đến tiến z E được chia thành hai tập con P={P0, P1, ..., trình Pi ký hiệu là Rj→Pi có ý nghĩa: Một thể Pn} là tập các tiến trình trong hệ thống và R= hiện của tài nguyên Rj đã được cấp phát cho {R0, R1, ..., Rm} là tập các loại tài nguyên tiến trình Pi. Ta gọi Rj→Pi là cung cấp phát trong hệ thống thỏa mãn P∪R=E và P∩R= ∅ (asignment edge) 13 14 Đồ thị cấp phát tài nguyên Đồ thị cấp phát tài nguyên z Ký hiệu hình vẽ: z Nếu không có chu trình trong đồ thị cấp phát z Pi là hình tròn tài nguyên: Không có bế tắc. Nế ...