Bài giảng Hệ điều hành - Chương 6: Deadlocks - Trường Đại học Công nghệ thông tin

HỆ ĐIỀU HÀNH
Chương 6 – Deadlocks
14/03/2017
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 1
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?
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 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ệ
 Tránh
 Kiểm tra
 Phục hồi
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 3
Nội dung chương 6
 Vấn đề deadlock
 Mô hình hệ thống
 Các tính chất của deadlock
 Phương pháp giải quyết deadlock
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 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 trên đĩa
 P1 và P2 mỗi tiến trình mở một file và yêu cầu mở file kia
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
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 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 ngay
 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
 Wail/ signal
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 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 
deadlock
 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 đáp ứng cho 
những tiến trình 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
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 7
Điều kiện cần để xảy ra deadlock
 Loại trừ tương hỗ: ít nhất một tài nguyên được giữ theo 
nonsharable mode
 Ví dụ: printer read-only files (sharable)
 Giữ và chờ cấp thêm tài nguyên: 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ữ
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 8
Điều kiện cần để xảy ra deadlock (tt)
 Không trưng dụng: 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: tồn tại một tập (P0,,Pn} các quá trình đang 
đợ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ữ
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 9
Đồ thị cấp phát tài nguyên - RAG
 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
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 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
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 11
Ví dụ RAG
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 12
Đồ thị cấp phát tài nguyên với một deadlock
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 13
Đồ thị chứa chu trình nhưng không deadlock
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 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
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 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 hoặc tránh 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
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 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 và phục hồi hệ thống
 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
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 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ẻ (printer): không làm được
 Đối với tài nguyên chia sẻ (read-only file): không cần thiết
 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
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 18
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