Bài giảng Lập trình hệ điều hành: Chương 6 - Hà Duy Anh

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

112
lượt xem 9
download

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

Bài giảng "Lập trình hệ điều hành - Chương 6: Deadlock" cung cấp cho người học các kiến thức: Deadlock là gì, các phương pháp xử lý Deadlock (Ngăn chặn Deadlock, tránh Deadlock, phát hiện và phục hồi từ Deadlock). Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Lập trình hệ điều hành: Chương 6 - Hà Duy Anh

Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ Giảng viên: Hà Duy An
1. Deadlock là gì? 2. Các phương pháp xử lý Deadlock o Ngăn chặn Deadlock o Tránh Deadlock o Phát hiện và phục hồi từ Deadlock 9/27/2013 2 Chương 6: Deadlock
• Hệ thống máy tính bao gồm một tập hợp các nguồn tài nguyên • Các kiểu tài nguyên R1, R2, . . ., Rm o Ví dụ: CPU cycles, memory space, I/O devices • Mỗi tài nguyên Ri có Wi thể hiện. • Tiến trình sử dụng một tài nguyên theo các bước như sau: o Yêu cầu (request) o Sử dụng (use) o Giải phóng (release) 9/27/2013 4 Chương 6: Deadlock
• Một tập hợp các tiến trình bị nghẽn, mỗi tiến trình đang giữ một tài nguyên và cũng đang chờ để xin một tài nguyên khác, mà tài nguyên này lại đang bị giữ bởi một tiến trình khác trong tập hợp trên. • Ví dụ o Hệ thống có 2 ổ chứa băng từ. o P1 và P2, một tiến trình đang giữ một ổ và đang cần ổ kia. • Ví dụ: mô phỏng sử dụng semaphore o Các semaphores A và B, khởi tạo là 1 P0 P1 wait (A); wait(B) wait (B); wait(A) 9/27/2013 5 Chương 6: Deadlock
9/27/2013 6 Chương 6: Deadlock
Deadlock có thể phát sinh nếu 4 điều kiện sau thỏa cùng lúc: • Loại trừ hỗ tương: chỉ một tiến trình có thể sử dụng tài nguyên tại một thời điểm. • Giữ và chờ: Một tiến trình đang giữ ít nhất là một tài nguyên và đang chờ để đạt được một tài nguyên khác đang bị giữ bởi tiến trình khác. • Không trưng dụng: một tài nguyên chỉ có thể được giải phóng một cách tự nguyện bởi tiến trình đang giữ nó, sau khi tiến trình này hoàn thành. • Chờ đợi vòng tròn: tồn tại một tập hợp {P0, P1, …, Pn} các tiến trình đang chờ đợi như sau: P0 đang đợi tài nguyên mà P1 đang giữ, P1 đang đợi tài nguyên mà P2 đang giữ, …, Pn–1 đang đợi tài nguyên mà Pn đang giữ và Pn lại đang chờ đợi tài nguyên mà P0 đang giữ. 9/27/2013 7 Chương 6: Deadlock
• Bao gồm tập hợp các đỉnh V và tập hợp các cạnh E. • V được chia làm 2 dạng: o P = {P1, P2, …, Pn}, là tập hợp các tiến trình đang tồn tại trong hệ thống. o R = {R1, R2, …, Rm}, là tập hợp các tài nguyên đang tồn tại trong hệ thống. • E chia làm 2 dạng: o Cạnh yêu cầu: cạnh có hướng Pi →Rj o Cạnh cấp phát: cạnh có hướng Rj →Pi 9/27/2013 8 Chương 6: Deadlock
• Tiến trình: • Tài nguyên với 4 thể hiện: • Pi yêu cầu một thể hiện của Rj: Pi Rj • Pi đang giữ một thể hiện của Rj: Pi Rj 9/27/2013 9 Chương 6: Deadlock
9/27/2013 10 Chương 6: Deadlock
9/27/2013 11 Chương 6: Deadlock
9/27/2013 12 Chương 6: Deadlock
• Nếu đồ thị không có chu trình (cycle)  không có deadlock. • Nếu đồ thị có một chu trình: o Nếu một tài nguyên chỉ có một thể hiện thì deadlock xảy ra. o Nếu một tài nguyên có vài thể hiện, có khả năng deadlock xảy ra. 9/27/2013 13 Chương 6: Deadlock
• Đảm bảo rằng hệ thống sẽ không bao giờ bước vào trạng thái deadlock bằng các biện pháp ngăn chặn hay tránh deadlock. • Cho phép hệ thống bước vào trạng thái deadlock và sau đó phục hồi lại. • Bỏ qua vấn đề này và xem như hệ thống sẽ không bao giờ xảy ra deadlock. o Biện pháp này được sử dụng trong hầu hết các hệ điều hành, bao gồm cả UNIX. 9/27/2013 15 Chương 6: Deadlock
Thắt chặt lại các cách thức yêu cầu tài nguyên của tiến trình. • Loại trừ hỗ tương: không yêu cầu đối với các tài nguyên có thể chia sẻ; chỉ áp dụng đối với các tài nguyên không thể chia sẻ. • Giữ và chờ: 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 đang giữ một tài nguyên khác. o Đòi hỏi tiến trình yêu cầu và được cấp tất cả các tài nguyên nó cần trước khi bắt đầu thực thi o Chỉ cho phép tiến trình yêu cầu tài nguyên chỉ khi nó hiện không giữ một tài nguyên nào cả. o Giải pháp này làm giảm đáng kể hiệu xuất sử dụng tài nguyên, và có thể gây ra tình trạng đói tài nguyên. 9/27/2013 17 Chương 6: Deadlock
• Không trưng dụng (no preemption): o Nếu một tiến trình đang giữ một số tài nguyên lại yêu cầu thêm một tài nguyên mới, nhưng tài nguyên mới này không thể được cấp phát, thì tiến trình đó phải giải phóng tất cả các tài nguyên nó đang giữ. • Các tài nguyên vừa được trưng dụng được thêm vào danh sách các tài nguyên mà tiến trình đang cần. • Tiến trình sẽ bị khởi động lại chỉ khi nó không thể xin lại được các tài nguyên cũ cũng như tài nguyên mới nó đang cần. • Chờ đợi vòng tròn (circular wait): phải áp đặt thứ tự toàn cục của tất cả các lọai tài nguyên và yêu cầu rằng mỗi tiến trình phải yêu cầu các tài nguyên theo thứ tự tăng. 9/27/2013 18 Chương 6: Deadlock
Yêu cầu thông tin bổ sung về cách thức tài nguyên được yêu cầu. • Mô hình đơn giản và hữu ích nhất là yêu cầu mỗi tiến trình khai báo số lượng tối đa của mỗi dạng tài nguyên mà nó cần. o Với những thông tin được biết trước, ta có thể xây dựng các giải thuật để bảo đảm rằng hệ thống sẽ không đi vào trạng thái deadlock. • Giải thuật tránh deadlock sẽ kiểm tra động trạng thái cấp phát tài nguyên để bảo đảm rằng không bao giờ 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ố lượng tài nguyên đã được cấp phát, số lượng tài nguyên sẵn dùng, và nhu cầu tối đa của các tiến trình. 9/27/2013 20 Chương 6: Deadlock