Nguyên lý hệ điều hành – Chương 7: Bế tắc (Deadlocks) – Tài liệu, ebook, giáo trình

„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 tích hợp xửlý bếtắc

11 trang | Chia sẻ : Mr Hưng| Lượt xem : 8171

| Lượt tải: 2

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
Các file đính kèm theo tài liệu này :

• vn_ch07_deadlocks_9552.pdf

Source: https://vh2.com.vn
Category : Ứng Dụng