Mô hình hệthống
„Mô tảbếtắc
„Các phương pháp xửlý bếtắc
„Ngăn ngừa bếtắc
„Tránh khỏi bếtắc
„Phát hiện bếtắc
„Phục hồi từbếtắc
„Phương pháp kết hợp xửlý bếtắc
Nội dung tài liệu Nguyên lý hệ điều hành - Chương 7: Bế tắc [Deadlocks], để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
1BÀI GIẢNG NGUYÊN LÝ HỆ ĐIỀU HÀNH Chương 7: Bế tắc [Deadlocks] Phạm Quang Dũng Bộ môn Khoa học máy tính Khoa Công nghệ thông tin Trường Đại học Nông nghiệp Hà Nội Website: fita.hua.edu.vn/pqdung 7.2 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Nội dung chương 7 „ Mô hình hệ thống „ Mô tả bế tắc „ Các phương pháp xử lý bế tắc „ Ngăn ngừa bế tắc „ Tránh khỏi bế tắc „ Phát hiện bế tắc „ Phục hồi từ bế tắc „ Phương pháp kết hợp xử lý bế tắc 7.3 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Mục tiêu „ Mô tả bế tắc, tình trạng ngăn cản các tiến trình đồng thời hoàn thành tác vụ „ Giới thiệu các phương pháp khác nhau để ngăn ngừa hoặc tránh khỏi bế tắc trong một hệ thống máy tính. 7.4 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Vấn đề bế tắc [Deadlock] „ Trong môi trường đa chương trình, một số tiến trình có thể tranh nhau một số tài nguyên hạn chế. „ Một tiến trình yêu cầu các tài nguyên, nếu tài nguyên không thể đáp ứng tại thời điểm đó thì tiến trình sẽ chuyển sang trạng thái chờ. „ Các tiến trình chờ có thể sẽ không bao giờ thay đổi lại trạng thái được vì các tài nguyên mà nó yêu cầu bị giữ bởi các tiến trình chờ khác. ⇒ ví dụ: tắc nghẽn trên cầu 27.5 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Ví dụ qua cầu „ Hai [hay nhiều hơn] ô tô đối đầu nhau trên một cây cầu hẹp chỉ đủ độ rộng cho một chiếc. „ Mỗi đoạn của cây cầu có thể xem như một tài nguyên. „ Nếu bế tắc xuất hiện, nó có thể được giải quyết nếu một hay một số ô tô lùi lại nhường đường rồi tiến sau. 7.6 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 7.1. Mô hình hệ thống „ Các loại tài nguyên R1, R2, . . ., Rm Các chu kỳ CPU, không gian bộ nhớ, các tệp, các thiết bị vào-ra „ Mỗi loại tài nguyên Ri cóWi cá thể [instance]. z vd: hệ thống có 2 CPU, có 5 máy in ⇒ có thể đáp ứng yêu cầu của nhiều tiến trình hơn „ Mỗi tiến trình sử dụng tài nguyên theo các bước sau: 1. yêu cầu [request]: nếu yêu cầu không được giải quyết ngay [vd khi tài nguyên đang được tiến trình khác sử dụng] thì tiến trình yêu cầu phải đợi cho đến khi nhận được tài nguyên. 2. sử dụng [use] 3. giải phóng [release] 7.7 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 7.2. Mô tả bế tắc Deadlock có thể xảy ra nếu 4 điều kiện sau đồng thời tồn tại: „ Ngăn chặn lẫn nhau: tại một thời điểm, chỉ một tiến trình có thể sử dụng một tài nguyên. „ Giữ và đợi: một tiến trình đang giữ ít nhất một tài nguyên và đợi để nhận được tài nguyên khác đang được giữ bởi tiến trình khác. „ Không có ưu tiên: một tài nguyên chỉ có thể được tiến trình [tự nguyện!] giải phóng khi nó đã hoàn thành công việc. „ Chờ đợi vòng tròn: tồn tại một tập các tiến trình chờ đợi {P0, P1, , Pn, P0} z P0 đang đợi tài nguyên bị giữ bởi P1, z P1 đang đợi tài nguyên bị giữ bởi P2, z Pn–1 đang đợi tài nguyên bị giữ bởi Pn, z và Pn đang đợi tài nguyên bị giữ bởi P0. 7.8 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Biểu đồ phân phối tài nguyên Một tập các đỉnh V và một tập các cạnh E. „ V được chia thành 2 loại: z P = {P1, P2, , Pn}, tập tất cả các tiến trình. z R = {R1, R2, , Rm}, tập các loại tài nguyên. Mỗi cá thể là một hình vuông bên trong „ cạnh yêu cầu – cạnh có hướng Pi→ Rj . [tiến trình Pi đang đợi nhận một hay nhiều cá thể của tài nguyên Rj]. „ cạnh chỉ định – cạnh có hướng Rj→ Pi . [tiến trình Pi đang giữ một hay nhiều cá thể của tài nguyên Rj]. Pi Rj Pi Rj 37.9 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Vd đồ thị phân phối tài nguyên không chu trình Nếu đồ thị không chu trình thì sẽ không có tiến trình nào bị bế tắc Nếu đồ thị có chu trình thì có thể tồn tại bế tắc 7.10 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Vd đồ thị phân phối tài nguyên có chu trình Bế tắc Không bế tắc: P4 hoặc P2 có thể kết thúc, khiến P1 và P3 kết thúc được. 7.11 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Kết luận về đồ thị „ Nếu đồ thị không chu trình ⇒ không xảy ra bế tắc. „ Nếu đồ thị có chu trình⇒ z nếu mỗi loại tài nguyên chỉ một cá thể thì chắc chắn xảy ra bế tắc. z nếu mỗi loại tài nguyên có một vài cá thể thì có thể xảy ra bế tắc. 7.12 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 7.3. Các phương pháp xử lý bế tắc „ Sử dụng một phương thức để ngăn ngừa hoặc tránh xa, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái bế tắc. „ Cho phép hệ thống đi vào trạng thái bế tắc rồi khôi phục lại. „ Bỏ qua vấn đề này và vờ như bế tắc không bao giờ xuất hiện trong hệ thống. Giải pháp này được sử dụng trong hầu hết các HĐH, bao gồm cả UNIX. 47.13 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 7.4. Ngăn ngừa bế tắc Ngăn cản các cách tạo yêu cầu: đảm bảo ít nhất một trong bốn điều kiện không thể xuất hiện „ Ngăn cản lẫn nhau – đảm bảo là hệ thống không có các file không thể chia sẻ. z một tiến trình không bao giờ phải chờ tài nguyên có thể chia sẻ vd: read-only files z một số tài nguyên là không thể chia sẻ vd: chế độ toàn màn hình „ Giữ và đợi – phải đảm bảo rằng mỗi khi một tiến trình yêu cầu một tài nguyên, nó không giữ bất kỳ tài nguyên nào khác. z Đòi hỏi tiến trình yêu cầu và được phân phối tất cả các tài nguyên của nó trước khi nó bắt đầu thực hiện, hoặc chỉ cho phép tiến trình yêu cầu các tài nguyên khi nó không giữ tài nguyên nào cả. z Hiệu quả sử dụng tài nguyên thấp, có thể xảy ra starvation. 7.14 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Ngăn ngừa bế tắc [tiếp] „ Không có ưu tiên z Nếu một tiến trình đang giữ một số tài nguyên và yêu cầu tài nguyên khác mà không thể được phân phối ngay cho nó thì tất cả các tài nguyên nó đang giữ được giải phóng. z Các tài nguyên ưu tiên được thêm vào danh sách tài nguyên dành cho tiến trình đang chờ đợi. z Tiến trình sẽ được khởi động lại chỉ khi nó có thể lấy lại các tài nguyên cũ của nó cũng như các tài nguyên mới mà nó đang yêu cầu. „ Chờ đợi vòng tròn – áp dụng một thứ tự tuyệt đối cho tất cả các loại tài nguyên: mỗi loại được gắn một số nguyên z mỗi tiến trình yêu cầu các tài nguyên theo thứ tự tăng dần: chỉ có thể nhận được tài nguyên có trọng số cao hơn của bất kỳ tài nguyên nào nó đang giữ z ⇒ Muốn có tài nguyên i, tiến trình phải giải phóng tất cả các tài nguyên có trọng số j > i [nếu có] 7.15 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 7.5. Tránh khỏi bế tắc Yêu cầu HĐH phải có một số thông tin ưu tiên „ Mô hình hữu dụng nhất và đơn giản nhất yêu cầu mỗi tiến trình công bố số lượng tài nguyên lớn nhất của mỗi loại mà nó có thể cần đến. „ Giải thuật tránh bế tắc luôn kiểm tra trạng thái phân phối tài nguyên để đảm bảo rằng sẽ không bao giờ có tình trạng chờ đợi vòng tròn. „ Trạng thái phân phối tài nguyên được xác định bởi số tài nguyên khả dụng và đã được phân phối cũng như sự yêu cầu tối đa từ các tiến trình. 7.16 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 7.5.1. Safe State „ Một trạng thái là an toàn nếu hệ thống có thể phân phối các tài nguyên cho mỗi tiến trình mà vẫn tránh được bế tắc. „ Khi một tiến trình yêu cầu một tài nguyên còn rỗi, hệ thống phải quyết định liệu phân phối ngay lập tức có làm cho hệ thống mất an toàn hay không? „ Hệ thống ở trong trạng thái an toàn nếu tồn tại một chuỗi an toàn của tất cả các tiến trình. 57.17 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Safe State [tiếp] „ Chuỗi là an toàn nếu với mỗi Pi, tài nguyên mà nó yêu cầu có thể được cung cấp bởi tài nguyên khả dụng hiện tại và các tài nguyên đang được giữ bởi Pj, với j