tailieunhanh - 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),. . | Nguyên lý hệ điều hành Nguyễn Hải Châu Khoa Công nghệ thông tin Trường Đại học Công nghệ Bế tắc Deadlock Định nghĩa Hai con dê qua cầu Bế tắc 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 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 4 Bế tắc giao thông tại ngã tư Bế tắc trong máy tính Tiến trình A 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 6 1 Qui trình sử dụng tài nguyên Một tiến trình thường sử dụng tài nguyên theo các bước tuần tự sau Xin phép sử dụng request Sử dụng tài nguyên use Giải phóng tài nguyên sau khi sử dụng release Điều kiện cần để có bế tắc Bế tắc xuất hiện nếu 4 điều kiện sau xuất hiện đồng thời điều kiện cần C1 Loại trừ lẫn nhau mutual exclusion C2 Giữ và chờ hold and wait C3 Không có đặc quyền preemption C4 Chờ vòng circular wait C1 Loại trừ lẫn nhau Một tài nguyên bị chiếm bởi một tiến trình và không tiến trình nào khác có thể sử dụng tài nguyên này C2 Giữ và chờ Một tiến trình giữ ít nhất một tài nguyên và chờ một số tài nguyên khác rỗi để sử dụng. Các tài nguyên này đang bị một tiến trình khác chiếm giữ 10 C3 Không có đặc quyền Tài nguyên bị chiếm giữ chỉ có thể rỗi khi tiến trình tự nguyện giải phóng tài nguyên sau khi đã sử dụng xong. C3 Chờ vòng Một tập tiến trình P0 P1 . Pn có xuất hiện điều kiện chờ vòng nếu P0 chờ một tài 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 Thuật ngữ Resource allocation graph Để mô tả một cách chính xác bế tắc chúng ta sử dụng đồ thị có hướng gọi là đồ thị cấp phát tài nguyên G V E với Vlà tập đỉnh E là tập cung Eđược chia thành hai tập con P P0 P1 . Pn là tập các .