tailieunhanh - Nguyên lý hệ điều hành - Phần 5

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) 3 Hai con dê qua cầu: Bế tắc 4 Bế tắc giao thông tại ngã tư Bế tắc trong máy tính Tiến trình A: { Khóa file F1; . Mở file F2; Đóng F1 (mở khóa. | 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 tiến .