Đề tài 16: Các thuật toán ngăn ngừa và phòng tránh eadlock - Công nghệ thông tin | Đại học Hoa Sen
Đề tài 16: Các thuật toán ngăn ngừa và phòng tránh eadlock - Công nghệ thông tin | Đại học Hoa Sen được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem
Môn: Công nghệ thông tin (asf-1243)
Trường: Đại học Hoa Sen
Thông tin:
Tác giả:
Tài liệu liên quan:
Preview text:
Nhóm 3:
Nguyễn Võ Minh Anh - 22011815 Lê Đức Anh - 22003052
Đề tài 16: Các thuật toán ngăn ngừa và phòng tránh Deadlock Nội dung: I.
Các thuật toán phát hiện Deadlock II. Ngăn deadlock.
III. Cách ngăn chặn Deadlock: IV. Tránh deadlock.
-----------------------------------------------------------------------------------------
Ⅰ. Các thuật toán phát hiện Deadlock:
- Có một số kỹ thuật phát hiện Deadlock phổ biến được sử dụng trong hệ điều hành và
các hệ thống quản lý tài nguyên. Dưới đây là một số kỹ thuật phát hiện Deadlock quan trọng:
+ Giải thuật Wait-For Graph:
Giải thuật này xây dựng đồ thị từ các quy trình và tài nguyên để đại diện cho các phụ
thuộc chờ đợi giữa chúng.
Bằng cách phân tích đồ thị, giải thuật có thể phát hiện chu trình chờ đợi (circular wait) và xác định Deadlock.
+ Giải thuật Resource Allocation Graph:
Giải thuật này sử dụng đồ thị để biểu diễn mối quan hệ giữa các quy trình và tài nguyên.
Bằng cách phân tích đồ thị, giải thuật có thể xác định các trạng thái kẹt (deadlocked
state) và phát hiện Deadlock. + Giải thuật Banker’s:
Giải thuật này kiểm tra xem việc cấp phát tài nguyên cho các quy trình có làm tăng nguy cơ Deadlock hay không.
Nếu một yêu cầu tài nguyên mới có thể dẫn đến tình trạng chờ đợi vô hạn, giải thuật
sẽ từ chối cấp phát tài nguyên đó để ngăn chặn Deadlock.
+ Giải thuật Ostrich Algorithm:
Giải thuật này thực hiện kiểm tra Deadlock định kỳ nhưng không thực hiện giải quyết ngay lập tức.
Nếu Deadlock được phát hiện, giải thuật chỉ ghi nhận và tiếp tục hoạt động mà không
thực hiện biện pháp giải quyết, giống như một con đà điểu chui đầu vào cát.
- Các kỹ thuật phát hiện Deadlock này có thể được áp dụng trong các hệ điều hành và
hệ thống quản lý tài nguyên để giúp xác định khi nào Deadlock xảy ra và đưa ra biện
pháp giải quyết phù hợp.
. Ngăn Deadlock: bằng 4 đk cần của deadlock Ⅱ
+ Ngăn “Mutual exclusion”:
- Đối với tài nguyên không chia sẻ (vd: printer): không làm được
- Đối với tài nguyên chia sẻ (vd: read-only file): không cần thiết + Ngăn “Hold and wait”:
Cách 1: Mỗi tiến trình yêu cầu toàn bộ tài nguyên cần thiết 1 lần. Nếu có đủ tài
nguyên thì hệ thống sẽ cấp phát, nếu không đủ tài nguyên thì tiến trình sẽ phải bị block.
Cách 2: Khi yêu cầu tài nguyên, tiến trình không được giữ tài nguyên nào. Nếu
đang có thì phải trả lại trước khi yêu cầu
+ Ngăn “No preemption”: nếu tiến trình A có giữ tài nguyên và đang yêu cầu tài
nguyên khác nhưng tài nguyên này chưa được cấp phát ngay thì
Cách 1: Hệ thống lấy lại mọi tài nguyên mà A đang giữ.
- A chỉ bắt đầu lại được khi có được các tài nguyên đã bị lấy lại và tài nguyên đang yêu cầu.
Cách 2: Hệ thống sẽ xem tài nguyên mà A yêu cầu
- Nếu tài nguyên được giữ bởi 1 tiến trình khác đang đợi thêm tài nguyên, tài nguyên
này được hệ thống lấy lại và cấp phát cho A.
- Nếu tài nguyên được giữ bởi tiến trình không đợi tài nguyên A phải đợi và tài
nguyên A bị lấy lại. Tuy nhiên, hệ thống chỉ lấy lại các tài nguyên mà các tiến trình khác yêu cầu.
+ Ngăn Circular wait”: Gán 1 thứ tự cho tất cả các tài nguyên trong hệ thống
- Tập hợp tại nguyên: R = {R1, R2,..,Rm}
- Hàm ánh xạ: F:R -> N (Với N là tập hợp các số tự nhiên)
. Cách ngăn chặn Deadlock: Ⅲ
- Để ngăn chặn Deadlock trong hệ điều hành, bạn có thể áp dụng các phương pháp sau đây:
+ Quản lý tài nguyên một cách an toàn:
Sử dụng các nguyên tắc quản lý tài nguyên như “yêu cầu-trả lại” (request-release) và
“yêu cầu-nhả” (request-kill) để đảm bảo tài nguyên được sử dụng một cách hợp lý và không gây xung đột.
+Thực hiện việc phân chia tài nguyên một cách cẩn thận và tránh việc giữ tài nguyên
lâu dài mà không sử dụng.
+Thiết kế hệ thống và ứng dụng hợp lý:
Xác định và thiết kế các quy trình và luồng công việc sao cho tránh xảy ra tình trạng
chờ đợi vô hạn (circular wait) giữa các tài nguyên.
Đảm bảo rằng các quy trình chỉ yêu cầu tài nguyên cần thiết và không yêu cầu các tài
nguyên mà không sử dụng.
+Sử dụng giải thuật Banker’s để phân bổ tài nguyên:
Sử dụng giải thuật Banker’s để đảm bảo rằng việc phân bổ tài nguyên không gây ra
tình trạng chờ đợi vô hạn.
Trước khi cấp phát tài nguyên cho một quy trình, kiểm tra xem việc cấp phát đó có
làm tăng nguy cơ Deadlock hay không.
+Sử dụng các kỹ thuật phát hiện Deadlock:
Sử dụng các giải thuật phát hiện Deadlock để xác định khi nào Deadlock xảy ra và
thực hiện các biện pháp giải quyết.
Các giải thuật phát hiện Deadlock phổ biến bao gồm giải thuật Banker’s, giải thuật
Wait-For Graph, và giải thuật Ostrich Algorithm.
Giám sát và ghi nhật ký hoạt động hệ thống:
Theo dõi và ghi lại hoạt động của các quy trình và tài nguyên trong hệ thống để phát
hiện và giải quyết Deadlock kịp thời.
+Sử dụng kỹ thuật phân tích đồ thị tài nguyên:
Sử dụng kỹ thuật phân tích đồ thị tài nguyên để phân tích các tương tác giữa các quy
trình và tài nguyên, từ đó đưa ra các biện pháp ngăn chặn Deadlock.
- Lưu ý rằng không có cách ngăn chặn Deadlock hoàn toàn, nhưng việc áp dụng các
phương pháp trên sẽ giúp giảm nguy cơ xảy ra Deadlock trong hệ thống. . T
Ⅳ ránh deadlock:
- Ngăn deadlock sử dụng tài nguyên không hiệu quả
- Tránh deadlock vẫn đảm bảo hiệu suất sử dụng tài nguyên tối đa tới mức có thể
- Yêu cầu mỗi tiến trình khai báo số lượng tài nguyên tối đa cần để thực hiện công việc
- Giải thuật tránh deadlock sẽ kiểm tra “Trạng thái cấp phát tài nguyên” để đảm bảo
hệ thống không rơi vào deadlock
- Trạng thái cấp phát tài nguyên được định nghĩa dựa trên số tài nguyên còn lại, số tài
nguyên đã được cấp phát và yêu cầu tối đa của các tiến trình. Link tham khảo:
https://websitehcm.com/ngan-chan-deadlock-trong-he-dieu-hanh/
https://bkhost.vn/blog/deadlock/