Bài giảng Hệ điều hành - Chương 6, Phần 1: Deadlocks - 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ất 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 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 
 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,,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ữ 
 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 
 Ngăn deadlock (tt) 
 Ngăn Circular wait: gán một 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) 
 Ví dụ: Có 3 tài nguyên tape drive, disk drive và printer. Và 
 hàm F ví dụ như sau: 
 F(tape drive) = 1 
 F (disk drive) = 5 
 F (printer) = 12 
 Deadlocks 
 21 
 Ngăn deadlock (tt) 
 Ngăn Circular wait (tt): 
Dựa vào hàm F như trên, một cách như sau có thể được sử dụng để 
ngăn Circular wait: 
 Mỗi tiến trình có thể yêu cầu thực thể của một loại tài nguyên 
 chỉ theo thứ tự tăng dần (định nghĩa bởi hàm F). 
 Cụ thể, một process đầu tiên yêu cầu thực thể Ri nào đó. Sau 
 đó, process này chỉ có thể yêu cầu thêm thực thể Rj nếu và chỉ 
 nếu F(Rj) > F(Ri) 
(Tất nhiên, người lập trình có thể chọn cách khác, ví dụ process sau khi 
đã có Ri, chỉ có thể yêu cầu Rj nếu và chỉ nếu F(Rj) ≤ F(Ri) 
 Deadlocks 
 22 
 Ngăn deadlock (tt) 
 Ngăn Circular wait (tt): 
Chứng minh cơ chế này có thể ngăn Circular wait bằng phản chứng: 
  Giả sử tồn tại 4 process (P1, P2, P3, P4) với 4 thực thể tài nguyên (R1, 
 R2, R3, R4) tạo thành một chu trình bị deadlock như hình. 
  Một process Pi sẽ giữ thực thể tài nguyên Ri-1 (Với P0 thì P0 giữ thực 
 thể tài nguyên R4) và đang yêu cầu thực thể tài nguyên Ri 
  Giả sử yêu cầu tài nguyên từ P1 tới P4 đều thỏa (sẽ tạo ra deadlock), 
 theo quy ước của cơ chế trên, phải có: 
 F(R4) < F(R1) 
 F(R1) < F(R2) 
 F(R2) < F(R3) 
 F(R3) < F(R4) 
 Vậy F(R4) < F(R4) mâu thuẫn 
 Deadlocks 
 23 
 Ngăn deadlock (tt) 
 Ngăn Circular wait (tt): 
Lưu ý rằng: Việc tạo ra hàm F và cấp phát theo thứ tự tự bản thân 
nó không thể ngăn deadlock, mà phụ thuộc vào cách mà người lập 
trình lập trình như thế nào. 
 Deadlocks 
 24 
 Trá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 đến 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 
 Deadlocks 
 25 
 Trạng thái safe và unsafe 
 Một trạng thái của hệ thống được gọi là an toàn (safe) nếu 
 tồn tại một chuỗi thứ tự an toàn 
 Một chuỗi quá trình là một chuỗi an toàn 
 nếu 
  Với mọi i = 1, , n yêu cầu tối đa về tài nguyên của Pi 
 có thể được thỏa bởi: 
 Tài nguyên mà hệ thống đang có sẵn sàng 
 Cùng với tài nguyên mà tất cả các Pj (j<i) đang giữ 
 Một trạng thái của hệ thống được gọi là không an toàn 
 (unsafe) nếu không tồn tại một chuỗi an toàn 
 Deadlocks 
 26 
 Trạng thái safe và unsafe (tt) 
 Ví dụ: hệ thống có 12 tape drive và 3 tiến trình P0, P1, P2 
  Tại thời điểm to 
 Cần tối đa Đang giữ Cần thêm 
 P0 10 5 5 
 P 4 2 2 
 1 
 P2 9 2 7 
 Còn 3 tape drive sẵn sàng 
 Chuỗi là chuỗi an toàn hệ thống là 
 an toàn 
 Deadlocks 
 27 
 Trạng thái safe và unsafe (tt) 
 Giả sử tại thời điểm t1, P2 yêu cầu và được cấp phát 1 tape 
 drive 
  Còn 2 tape drive sẵn sàng 
 Cần tối đa Đang giữ 
 P0 10 5 
 P 4 2 
 1 
 P 9 3 
 2 
 Hệ thống còn an toàn không? Không 
 Deadlocks 
 28 
 Trạng thái safe/unsafe và deadlock 
 Nếu hệ thống đang ở trạng thái safe không deadlock 
 Nếu hệ thống đang ở trạng thái unsafe có thể dẫn đến 
 deadlock 
 Tránh deadlock bằng cách bảo đảm hệ thống không đi 
 đến trạng thái unsafe 
 deadlock unsafe 
 safe 
 Deadlocks 
 29 
 Ôn tập 
 Khái niệm deadlock 
 Các tính chất của deadlock 
 Đồ thị cấp phát tài nguyên 
 Các phương pháp giải quyết deadlock 
 Ngăn deadlock 
 Tránh deadlock 
 Deadlocks 
 30