Chương 6: Deadlocks

Chia sẻ: Kieu Thu Trang | Ngày: | Loại File: PDF | Số trang:42

Thêm vào BST

Báo xấu

115
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Vấn Deadlock Mô hình hệ thống Đặc trưng Deadlock Các phương pháp quản lý Deadlocks Phòng ngừa Deadlock Tránh Deadlock Phát hiện Deadlock Phục hồi từ Deadlock Phát triển một mô tả deadlocks, hiện tượng ngăn cản tập các giao dịch cạnh tranh hoàn tất nhiệm vụ của chúng Giới thiệu một số phương pháp khác nhau để ngăn ngừa, tránh deadlocks trong hệ thống máy tính. Giới thiệu phương pháp phát hiện và phục hồi từ deadlocks...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 6: Deadlocks

Chương 6: Deadlocks
NỘI DUNG Vấn Deadlock Mô hình hệ thống Đặc trưng Deadlock Các phương pháp quản lý Deadlocks Phòng ngừa Deadlock Tránh Deadlock Phát hiện Deadlock Phục hồi từ Deadlock Operating System Concepts - 7th Edition, Feb 14, 2005 7.2 Silberschatz, Galvin and Gagne ©2005
MỤC TIÊU Phát triển một mô tả deadlocks, hiện tượng ngăn cản tập các giao dịch cạnh tranh hoàn tất nhiệm vụ của chúng Giới thiệu một số phương pháp khác nhau để ngăn ngừa, tránh deadlocks trong hệ thống máy tính. Giới thiệu phương pháp phát hiện và phục hồi từ deadlocks Operating System Concepts - 7th Edition, Feb 14, 2005 7.3 Silberschatz, Galvin and Gagne ©2005
VẤN ĐỀ Deadlock Một tập các quá trình bị nghẽn, mỗi một chiếm giữ một tài nguyên và chờ đợi tậu tài nguyên bị chiếm giữ bởi quá trình khác trong tập hợp. VD. Hệ thống có hai ổ đĩa. P1 và P2 mỗi một chiếm giữ một ổ đĩa và mỗi một cần ổ đĩa kia. VD. semaphores A và B, được khởi động là 1 P0 P1 wait (A); wait(B) wait (B); wait(A) Operating System Concepts - 7th Edition, Feb 14, 2005 7.4 Silberschatz, Galvin and Gagne ©2005
VÍ DỤ QUA CẦU Lưu thông chỉ theo một chiều. Mỗi phần của cầu được xem như một tài nguyên. Nếu deadlock xảy ra nó sẽ được giải quyết nếu một xe lùi lại (trưng các tài nguyên và cuộn lại). Một vài xe có thể bị lùi lại khi deadlock xảy ra. Có thể xảy ra “sự chết đói”. Operating System Concepts - 7th Edition, Feb 14, 2005 7.5 Silberschatz, Galvin and Gagne ©2005
MÔ HÌNH HỆ THỐNG Các kiểu tài nguyên: R1, R2, . . ., Rm Các chu kỳ CPU, không gian bộ nhớ, các thiết bị I/O Mỗi tài nguyên kiểu Ri có Wi thể hiện. Mỗi quá trình sử dụng một tài nguyên như sau: Yêu cầu tài nguyên Sử dụng tài nguyên Giải phóng tài nguyên Operating System Concepts - 7th Edition, Feb 14, 2005 7.6 Silberschatz, Galvin and Gagne ©2005
ĐẶC TRƯNG DEADLOCK Điều kiện cần để deadlock xảy ra: Loại trừ tương hỗ (Mutual exclusion): chỉ một quá trình sử dụng một tài nguyên tại một thời điểm. Giữ và chờ (Hold and wait): một quá trình chiếm giữ ít nhất một tài nguyên và chờ tậu các tài nguyên bổ xung bị chiếm giữ bởi các quá trình khác. Không có trưng dụng: một tài nguyên chỉ có thể được giải phóng bởi sự tình nguyện của quá trình chiếm giữ nó (sau khi quá trình đã hoàn thành nhiệm vụ của nó). Chờ đợi vòng tròn: Tồn tại một tập {P0, P1, …, P0} các quá trình chờ đợi sao cho P0 chờ một tài nguyên bị chiếm giữ bởi P1, P1 chờ một tài nguyên bị chiếm giữ bởi P2, …, Pn–1 chờ một tài nguyên bị chiếm giữ bởi Pn, và Pn chờ một tài nguyên bị chiếm giữ bởi P0. Operating System Concepts - 7th Edition, Feb 14, 2005 7.7 Silberschatz, Galvin and Gagne ©2005
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN Một tập các đỉnh V và một tập các cung E. V được phân hoạch thành hai kiểu: P = {P1, P2, …, Pn}, gồm tất cả các quá trình trong hệ thống. R = {R1, R2, …, Rm}, gồm tất cả các kiểu tài nguyên trong hệ thống. Cung yêu cầu – cung hướng từ Pi đến Rj : Pi → Rj Cung gán – hướng từ Rj đến Pi : Rj → Pi Operating System Concepts - 7th Edition, Feb 14, 2005 7.8 Silberschatz, Galvin and Gagne ©2005
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN (Cont.) Quá trình Kiều tài nguyên với 4 thể hiện Pi yêu cầu thể hiện của Rj Pi Rj Pi đang chiếm giữ một thể hiện của kiểu tài nguyên Rj Pi Rj Operating System Concepts - 7th Edition, Feb 14, 2005 7.9 Silberschatz, Galvin and Gagne ©2005
VÍ DỤ ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN Operating System Concepts - 7th Edition, Feb 14, 2005 7.10 Silberschatz, Galvin and Gagne ©2005
ĐỒ THỊ CẤP PHÁT TÀI NGUYÊN VỚI DEADLOCK Operating System Concepts - 7th Edition, Feb 14, 2005 7.11 Silberschatz, Galvin and Gagne ©2005
ĐỒ THỊ CÓ CHU TRÌNH NHƯNG KHÔNG CÓ Deadlock Operating System Concepts - 7th Edition, Feb 14, 2005 7.12 Silberschatz, Galvin and Gagne ©2005
CÁC SỰ KIỆN CƠ SỞ Nếu đồ thị không có chu trình ⇒ không có deadlock. Nếu đồ thị có chu trình ⇒ Nếu mỗi kiểu tài nguyên chỉ có một thể hiện thì có deadlock. Nếu mỗi kiểu tài nguyên có một vài thể hiện thì có thể có deadlock. Operating System Concepts - 7th Edition, Feb 14, 2005 7.13 Silberschatz, Galvin and Gagne ©2005
CÁC PHƯƠNG PHÁP QUẢN LÝ DEADLOCKS Đảm bảo hệ thống không bao giờ rơi vào trạng thái deadlock. Cho phép hệ thống rơi vào trạng thái deadlock sau đó phát hiện và phục hồi. Bỏ lơ vấn đề và xem như deadlocks không bao giờ xảy ra (được sử dụng trong hầu hết các HĐH kể cả UNIX). Operating System Concepts - 7th Edition, Feb 14, 2005 7.14 Silberschatz, Galvin and Gagne ©2005
NGĂN NGỪA DEADLOCK Ngăn cản một trong bốn điều kiện cần để xảy ra deadlock Loại trừ tương hỗ (Mutual Exclusion) : không được yêu cầu đối với các tài nguyên có thể chia sẻ nhưng có hiệu lực đối với tài nguyên có thể chia sẻ. Giữ và chờ (Hold and Wait) : Phải đảm bảo rằng mỗi khi quá trình yêu cầu một tài nguyên nó không chiếm giữ một tài nguyên nào. Đòi hỏi quá trình yêu cầu và được cấp phát tất cả các tài nguyên cần thiết trước khi bắt đầu thực hiện / chỉ cho phép quá trình yêu cầu các tài nguyên khi nó không chiếm giữ một tài nguyên nào. Hiệu suất sử dụng tài nguyên thấp, có thể xảy ra chết đói. Operating System Concepts - 7th Edition, Feb 14, 2005 7.15 Silberschatz, Galvin and Gagne ©2005
Deadlock Prevention (Cont.) Không có trưng dụng (no preemption): Nếu một quá trình đang chiếm giữ một số tài nguyên yêu cầu tài nguyên khác nhưng không thể được cấp phát ngay, các tài nguyên bị chiếm giữ bởi quá trình bị trưng dụng. Các tài nguyên bị trưng dụng được thêm vào danh sách các tài nguyên quá trình (bị trưng dụng) chờ. Quá trình sẽ được khởi động lại chỉ khi nó có thể tậu lại các tài nguyên cũ cũng như các tài nguyên mới yêu cầu. Chờ đợi vòng tròn (Circular Wait) – áp đặt một thứ tự toàn phần trên các kiểu tài nguyên và đòi hỏi mỗi quá trình yêu cầu tài nguyên theo thứ tự tăng. Operating System Concepts - 7th Edition, Feb 14, 2005 7.16 Silberschatz, Galvin and Gagne ©2005
TRÁNH Deadlock Đòi hỏi hệ thống phải có thông tin tiên quyết. Mô hình đơn giản nhất và hữu dụng nhất là đòi hỏi mỗi quá trình phải khai báo số lượng tối đa các tài nguyên cần thiết của mỗi kiểu. Thuật toán tránh deadlock kiểm tra trạng thái cấp phát tài nguyên và đảm bảo rằng không xảy ra chờ đợi vòng tròn. Trạng thái cấp phát tài nguyên được định nghĩa bởi số tài nguyên sẵn có, số tài nguyên đã được cấp phát và các đòi hỏi tối đa của các quá trình. Operating System Concepts - 7th Edition, Feb 14, 2005 7.17 Silberschatz, Galvin and Gagne ©2005
TRẠNG THÁI AN TOÀN Khi một quá trình yêu cầu một tài nguyên sẵn có, hệ thống phải xác định nếu cấp phát ngay, hệ thống vẫn trong trạng thái an toàn. Hệ thống trong trạng thái an toàn nếu tồn tại một dãy của TẤT CẢ các quá trình trong hệ thống sao cho đối với mỗi Pi, tất cả các tài nguyên mà Pi cần được thỏa mãn bởi các tài nguyên nó hiện có + các tài nguyên bị chiếm giữ bởi các Pj, với j < i. Đó là: Nếu tài nguyên mà Pi cần chưa có sẵn, Pi có thể chờ đến khi tất cả các Pj (j
SỰ KIỆN CƠ SỞ Nếu hệ thống trong trạng thái an toàn ⇒ không có deadlocks. Nếu hệ thống không trong trạng thái an toàn ⇒ có thể có deadlock. Tránh ⇒ đảm bảo hệ thống không bao giờ rơi vào trạng thái không an toàn. Operating System Concepts - 7th Edition, Feb 14, 2005 7.19 Silberschatz, Galvin and Gagne ©2005
TRẠNG THÁI AN TOÀN, KHÔNG AN TOÀN & Deadlock Operating System Concepts - 7th Edition, Feb 14, 2005 7.20 Silberschatz, Galvin and Gagne ©2005