Bài giảng Hệ điều hành - Chương 6: Deadlocks (Phần 1) - Trần Thị Như Nguyệt
Chương 6: Deadlocks
04/2015
Câu hỏi ôn tập chương 5
Phân biệt semaphore với monitor? Nêu ứng dụng
của từng giải pháp?
Áp dụng semaphore vào bài toán reader-writer, giải
thích rõ hoạt động?
Deadlocks
2
Mục tiêu chương 6
Hiểu được vấn đề bài toán deadlock và các tính chất
của deadlock
Hiển được các phương pháp giải quyết deadlock
Bảo vệ Ngăn (Deadlock prevention)
Tránh (Deadlock avoidance)
Kiểm tra (Deadlock detection)
Phục hồi (Deadlock recovery)
Deadlocks
3
Nội dung
Bài toán deadlock
Mô hình hệ thống
Các tính chấcủa deadlock
Phương pháp giải quyết deadlock
Deadlocks
4
Vấn đề deadlock
Tình huống: Một tập các tiến trình bị block, mỗi tiến
trình giữ tài nguyên và đang chờ tài nguyên mà tiến
trình khác trong tập đang giữ
Ví dụ 1:
Hệ thống có 2 file A và B trên đĩa
P1 và P2 mỗi tiến trình mở một file và yêu cầu mở file kia.
P1 đã mở, đang nắm giữ file A và yêu cầu file B; trong khi P2 đã
mở, đang nắm giữ file B và yêu cầu mở file A.
P1 muốn hoàn tất thì phải có cả file A và B, P2 cũng vậy.
Ví dụ 2:
Bài toán các triết gia ăn tối
Mỗi người cầm 1 chiếc đũa và chờ chiếc còn lại
Deadlocks
5
Mô hình hóa hệ thống
Các loại tài nguyên, kí hiệu R1, R2,…,Rm, bao gồm:
CPU cycle, không gian bộ nhớ, thiết bị I/O, file, semaphore,..
Mỗi loại tài nguyên Ri có Wi thực thể
Giả sử tài nguyên tái sử dụng theo chu kỳ
Yêu cầu: tiến trình phải chờ nếu yêu cầu không được đáp ứng ngày
Sử dụng: tiến trình sử dụng tài nguyên
Hoàn trả: tiến trình hoàn trả tài nguyên
Các tác vụ yêu cầu và hoàn trả đều là system call. Ví dụ:
Request/release device
Open/close file
Allocate/free memory
Wait/signal
Deadlocks
6
Định nghĩa
Một tiến trình gọi là deadlock nếu nó đang đợi một sự
kiện mà sẽ không bao giờ xảy ra
Thông thường, có nhiều hơn một tiến trình bị liên quan trong
một deadl
Một tiến trình gọi là trì hoãn vô hạn định nếu nó bị trì
hoãn một khoảng thời gian dài lặp đi lặp lại trong khi
hệ thống đákhác
Ví dụ: Một tiến trình sẵn sàng để xử lý nhưng nó không bao
giờ nhận được CPU
Deadlocks
7
Điều kiện cần để xảy ra deadlock
Loại trừ hỗ tương (Mutual exclusion): ít nhất một
tài nguyên được giữ theo nonsharable mode
Giữ và chờ cấp thêm tài nguyên (Hold and wait):
Một tiến trình đang giữ ít nhất một tài nguyên và
đợi thêm tài nguyên do quá trình khác giữ
Deadlocks
8
Điều kiện cần để xảy ra deadlock (tt)
Không trưng dụng (No Preemption): tài nguyên
không thể bị lấy lại mà chỉ có thể được trả lại từ
tiến trình đang giữ tài nguyên đó khi nó muốn
Chu trình đợi vòng tròn (Circular wait): tồn tại một
tập (P0,…,i sao cho
P0 đợi một tài nguyên mà P1 giữ
P1 đợi một tài nguyên mà P2 giữ
…
Pn đợi một tài nguyên mà P0 giữ
Deadlocks
9
Đồ thị cấp phát tài nguyên - RAG
RAG: Resource-Allocation Graph
Là đồ thị có hướng, với tập đỉnh V và tập cạnh E
Tập đỉnh V gồm 2 loại:
P = {P1, P2,…,Pn} (All process)
R = {R1, R2,…,Rn} (All resource)
Tập cạnh E gồm 2 loại:
Cạnh yêu cầu: Pi Rj
Cạnh cấp phát: Rj Pi
Deadlocks
10
Đồ thị cấp phát tài nguyên – RAG (tt)
Process i
Loại tài nguyên Rj với 4 thực thể
Pi yêu cầu một thực thể của Rj
Pi đang giữ một thực thể của Rj
Deadlocks
11
Ví dụ RAG
Deadlocks
12
Đồ thị cấp phát tài nguyên với một deadlock
Deadlocks
13
Đồ thị chứa chu trình nhưng không deadlock
Deadlocks
14
RAG và deadlock
RAG không chứa chu trình không có deadlock
RAG chứa một (hay nhiều) chu trình
Nếu mỗi loại tài nguyên chỉ có một thực thể
deadlock
Nếu mỗi loại tài nguyên có nhiều thực thể
có thể xảy ra deadlock
Deadlocks
15
Các phương pháp giải quyết deadlock
Bảo đảm rằng hệ thống không rơi vào tình trạng deadlock
bằng cách ngăn (Prevention) hoặc tránh (Avoidance) deadlock
Khác biệt
Ngăn deadlock: không cho phép (ít nhất) một trong 4 điều
kiện cần cho deadlock
Tránh deadlock: các quá trình cần cung cấp thông tin về tài
nguyên nó cần để hệ thống cấp phát tài nguyên một cách
thích hợp
Deadlocks
16
Các phương pháp giải quyết deadlock (tt)
Cho phép hệ thống vào trạng thái deadlock, nhưng sau đó phát
hiện deadlock (Detection) và phục hồi hệ thống (Recovery)
Bỏ qua mọi vấn đề, xem như deadlock không bao giờ xảy ra
trong hệ thống
Khá nhiều hệ điều hành sử dụng phương pháp này
Deadlock không được phát hiện, dẫn đến việc giảm hiệu
suất của hệ thống. Cuối cùng, hệ thống có thể ngưng hoạt
động và phải khởi động lại
Deadlocks
17
Ngăn deadlock
Ngăn deadlock bằng cách ngăn một trong 4 điều kiện
cần của deadlock
Ngăn mutual exclusion
Đối với tài nguyên không chia sẻ (ví dụ: printer):
không làm được
Đối với tài nguyên chia sẻ (ví dụ: read-only file):
không cần thiết
Deadlocks
18
Ngăn deadlock (tt)
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 một 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 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
Deadlocks
19
Ngăn deadlock (tt)
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
cùng với 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 một 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 của A bị lấy lại. Tuy nhiên hệ thống
chỉ lấy lại các tài nguyên mà tiến trình khác yêu cầu
Deadlocks
20
Tải về để xem bản đầy đủ
30 trang
20000
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 6: Deadlocks (Phần 1) - Trần Thị Như Nguyệt", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_he_dieu_hanh_chuong_6_deadlocks_phan_1_tran_thi_nh.pdf
