Bài giảng Hệ điều hành - Chương 4: Deadlock - Lê Ngọc Minh

uyên có nhiều thực thể ⇒ có thể xảy ra
 deadlock.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.8-
 4
 Các p.p giải quyết deadlock
 Dùng một giao thức (protocol) để ngăn chặn hoặc
 tránh deadlock, bảo đảm rằng hệ thống không bao
 giờ bị rơi vào tình trạnh deadlock.
 – Deadlock prevention
 – Deadlock avoidance
 Hệ thống có thể rơi vào trạng thái deadlock, sau đó
 phát hiện deadlock và phục hồi hệ thống.
 Bỏ qua mọi vấn đề, xem như không bao giờ có
 deadlock xảy ra trong hệ thống
 ☺ Khá nhiều hệ điều hành sử dụng p.p này.
 – Deadlock không phát hiện, giải quyết ⇒ 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.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.9-
 Deadlock Prevention
 Tìm cách ngăn chặn sao cho ít nhất một trong 4 điều
 kiện gây deadlock không xảy ra.
1) Mutual Exclusion: không cần thiết đối với sharable 
 resource nhưng bắt buộc phải thỏa mãn đối với non-
 sharable resource ⇒ không hạn chế được.
2) Hold and Wait: sử dụng cơ chế “all-or-none”
 – Cách 1: bắt buộc mỗi process phải 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ì process phải bị block 
 – Cách 2: khi yêu cầu tài nguyên, process không được sở hữu bất
 kỳ tài nguyên nào. Nếu đang có thì phải trả lại trước khi yêu cầu
 – Khuyết điểm:
  Hiệu suất sử dụng tài nguyên rất thấp
  Có khả năng bị starvation
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.10-
 5
 Deadlock Prevention (t.t)
3) No Preemption: nếu process A có sở hữu 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 đáp ứng được thì.
 – Cách 1: A phải trả cho hệ thống mọi tài nguyên đang sở hữu
  A phải bắt đầu lại từ đầu, yêu cầu các tài nguyên đã bị đoạt
 lại và cả tài nguyên đang yêu cầu
 – Cách 2: Hệ thống sẽ kiểm tra tài nguyên mà A yêu cầu
  Nếu tài nguyên là sở hữu của process đang yêu cầu và đợi
 thêm tài nguyên, tài nguyên này được hệ thống đoạt lại và
 cấp phát cho A.
  Nếu tài nguyên là sở hữu của process không đợi tài nguyên, 
 A phải đợi và tài nguyên của A bị đoạt lại. Tuy nhiên hệ
 thống chỉ đoạt lại các tài nguyên mà process khác yêu cầu
  Thường áp dụng cho tài nguyên có thể dễ dàng lưu và khôi phục
 trạng thái như CPU register, bộ nhớ, ...
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.11-
 Deadlock Prevention (t.t)
4) Circular Wait: các tài nguyên trong hệ thống được đánh
 số thứ tự tuyến tính
 – Ví dụ: F(tape drive) = 1, F(disk drive) = 5, F(Printer) = 12
  F là hàm định nghĩa thứ tự dựa trên hiệu suất sử dụng của
 tài nguyên.
 – Cách 1: Bắt buộc mỗi process yêu cầu tài nguyên theo thứ tự
 tuyến tính tăng dần. Ví dụ
  Chuỗi yêu cầu hợp lệ: tape drive → disk drive → Printer
  Chuỗi yêu cầu không hợp lệ: disk drive → tape drive
 – Cách 2: Khi một process yêu cầu một tài nguyên Rj thì phải trả
 lại các tài nguyên Ri với F(Ri) > F(Rj)
 p1 p1-request
 R1 R2 R3 R4 R5 R6
 p2 p2
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.12-
 6
 Deadlock Avoidance
 Deadlock prevention sử dụng tài nguyên không hiệu quả. 
 Deadlock avoidance chỉ dựa trên điều kiện thứ 4 để
 tránh deadlock mà 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 process 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 deadlock-avoidance sẽ kiểm tra trạng thái cấp
 phát tài nguyên (resource-allocation state) để bảo đảm
 hệ thống không bao giờ 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 cực đại của các process
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.13-
 Trạng thái “safe” và “unsafe”
 Một trạng thái được gọi là “safe”nếutồntạiítnhấtmộtcách
 mà trong một khoảng thời gian hữu hạn nào đó, hệ thống có
 thể cấp phát tài nguyên thỏa mãn cho tất cả process thực thi
 hoàn tất .
 Khi một process yêu cầu một tài nguyên đang sẵn có, hệ
 thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình
 trạng unsafe thì sẽ cấp phát ngay.
 maximum maximum 
 holding holding
 need need
 A 1 4 A 8 10
 B 4 6 B 2 5
 C 5 8 C 1 3
 Available = 2 Available =1
 Trạng thái safe Trạng thái unsafe
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.14-
 7
 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ókhảnăng
 dẫn đến deadlock.
 Deadlock avoidance ⇒ bảo đảm hệ thống không bao giờ
 đi đến trạng thái “unsafe”. 
 deadlock unsafe
 safe
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.15-
 Giải thuật Banker
 Áp dụng cho hệ thống cấp phát tài nguyên trong
 đó mỗi loại tài nguyên có thể có nhiều instance.
 Mô phỏng nghiệp vụ ngân hàng (banking)
 Mộtsốgiảthiết
 – Mỗi process phải khai báo số lượng tối đa tài nguyên
 mỗi loại mà process đó cần để hoàn tất công việc.
 – Khi process yêu cầu một tài nguyên thì có thể phải
 đợi mặc dù tài nguyên được yêu cầu đang có sẵn
 – Khi process đã có được đầy đủ tài nguyên thì phải
 hoàn trả trong một khoản thời gian hữu hạn nào đó.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.16-
 8
 Giải thuật Banker (t.t)
Một số giả thiết trong giải thuật Banker:
 n = số processes hạn chế của
 giải thuật Banker
 m = số loại tài nguyên
 Max[n, m] 
  Max[ i, j ] = k ⇔ số instance cực đại mà Pi yêu cầu đối với Rj.
 Available[m]
  Available[j] = k ⇔ loại tài nguyên Rj đang sẵn có k instance.
 Allocation[n, m] 
  Allocation[i,j] = k ⇔ Pi đã được cấp phát k instance của Rj.
 Need: ma trận n x m . 
  Need[i,j] = k ⇔ Pi cần thêm k instance của Rj. 
 Need [i,j] = Max[i,j] – Allocation [i,j].
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.17-
 Giải thuật kiểm tra trạng thái
 1. Gọi Work và Finish là hai vector kích thước tương ứng
 là m, n. Khởi tạo ban đầu
 Work[i] := Available[i]
 Finish[j] = false, ∀j
 2. Tìm i thỏa điều kiện sau
 (a) Finish [i] = false Độ phức tạp
 của giải thuật
 (b) Needi ≤ Work (hàng thứ i của Need)
 Nếu không tồn tại i thoả điều kiện, đến bước 4. O(m.n2)
 3. Work := Work + Allocationi
 Finish[i] := true
 quay về bước 2.
 4. Nếu Finish[i] = true ∀i, hệ thống đang ở trạng thái safe
 Y ≤ X ⇔ Y[i] ≤ X[i], ví dụ (0, 3, 2, 1) ≤ (1, 7, 3, 2)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.18-
 9
 Giải thuật cấp phát tài nguyên
Gọi Requesti[m] là request vector của process Pi. 
Requesti [j] = k ⇔ Pi cần k instance của tài nguyên Rj.
1. Nếu Requesti ≤ Needi ⇒ đến bước 2. Ngược lại, báo lỗi vì process 
 đã vượt quá giới hạn yêu cầu cực đại.
2. Nếu Requesti ≤ Available ⇒ qua bước 3. Ngược lại, Pi phải chờ vì
 tài nguyên không còn đủ để cấp phát.
3. Giả định cấp phát tài nguyên đáp ứng yêu cầu của Pi thử cập nhật
 trạng thái hệ thống như sau:
 Available := Available - Requesti;
 Allocationi := Allocationi + Requesti;
 Needi := Needi – Requesti; 
 Nếu trạng thái là safe ⇒ tài nguyên được cấp thực sự cho Pi. 
 Nếu unsafe ⇒ Pi phải đợi. Phục hồi trạng thái
 Available := Available + Requesti;
 Allocationi := Allocationi - Requesti;
 Needi := Needi + Requesti;
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.19-
 Giải thuật Banker – Ví dụ (t.t)
 Có 5 process P0 – P4
 Có 3 loại tài nguyên: A (có 10 instance), B (5 instance) 
 và C (7 instance).
 Sơ đồ cấp phát trong hệ thống tại thời điểm T0
 Allocation Max Available Need
 A BAC A B C B C A B C
 P0 0 1 0 7 5 3 3 3 2 7 4 3 
 P1 2 0 0 3 2 2 1 2 2 
 P2 3 0 2 9 0 2 6 0 0 
 P3 2 1 1 2 2 2 0 1 1 
 P4 0 0 2 4 3 3 4 3 1 
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.20-
 10
 Kiểm tra sự an toàn
 Chuỗi cấp phát an toàn 
 Allocation N eed Available
 A B CA B C A B C
 P0 0 1 07 4 33 3 2
 P 2 0 0 1 2 2
 1 5 3 2
 P2 3 0 26 0 0
 7 4 3
 P3 2 1 1 0 1 1
 P4 0 0 24 3 1 7 4 5
 10 4 7 10 5 7
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.21-
 Ví dụ: 
 Yêu cầu (1,0,2) của P1 có thỏa được không? Kiểm tra điều
 kiện Request ≤ Available 
 (1,0,2) ≤ (3,3,2) = TRUE
 Kiểm tra trạng thái hiện tại có phải là safe hay không?
 Allocation Need Available
 A BAC A B C B C
 P0 0 1 0 7 4 3 2 3 0
 P1 2 0 0 0 2 0
 P2 3 0 2 6 0 0
 P3 2 1 1 0 1 1
 P4 0 0 2 4 3 1
 BT: yêu cầu (3,3,0) của P4, yêu cầu (0,2,0) của P0 cóthểthỏa
mãn hay không?
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.22-
 11
 Deadlock Detection
 Chấp nhận xảy ra deadlock trong hệ thống, 
 kiểm tra trạng thái hệ thống bằng giải thuật
 phát hiện deadlock. 
 Nếu có deadlock thì tiến hành phục hồi hệ
 thống
 Các giải thuật phát hiện deadlock thường sử
 dụng mô hình RAG.
 Có hai mô hình hệ thống cấp phát tài nguyên
 được khảo sát
 1. Single-Instance: mỗi loại tài nguyên chỉ có một
 instance
 2. Multiple-Instance: mỗi loại tài nguyên có thể có nhiều
 instance
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.23-
 Mô hình Single-Instance
 Sử dụng wait-for graph (một biến thể của RAG), trong
 đó, các node của graph là các process.
 – Wait-for graph được dẫn xuất từ RAG bằng cách bỏ các node 
 biểu diễn tài nguyên và ghép các cạnh tương ứng. 
 –Pi → Pj ⇔ Pi đang chờ tài nguyên từ Pj
 Một giải thuật được gọi định kỳ (!) để kiểm tra có tồn tại
 chu kỳ (cycle) trong wait-for graph hay không? Giải thuật
 phát hiện chu kỳ có độ phức tạp là O(n2), với n là số
 đỉnh của graph.
 P5 P5
 R1 R3 R4
 P1 P2 P3
 P1 P2 P3
 R2 P4 R5 P4
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.24-
 12
 Mô hình Multiple-Instance
 Mô hình wait-for graph không áp dụng được cho
 trường hợp mỗi loại tài nguyên có nhiều instance.
 Các cấu trúc dữ liệu dùng trong giải thuật phát
 hiện deadlock 
 – Available[m]: # instance sẵn có của mỗi loại tài
 nguyên
 – Allocation[n,m]: # instance đã cấp phát cho mỗi
 process
 – Request[n,m]: yêu cầu hiện tại của process. Request 
 [i,j] = k ⇔ Pi đang yêu cầu thêm k instance của Rj
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.25-
 Detection Algorithm
1. Gọi Work và Finish là vector kích thước m và n:
 (a) Work := Available
 (b) Với i = 1,2, , n, nếu Allocationi ≠ 0 ⇒ Finish[i] = false 
 ngược lại ⇒ Finish[i] = true
2. Tìm i thỏa mãn:
 Finish[i] = false và Request ≤ Work, 
 i Độ phức tạp
 Nếu không tồn tại i , đến bước 4. của giải thuật
3. Work = Work + Allocationi O(m.n2)
 Finish[i] = true
 quay về bước 2.
4. ∃i,1≤ i ≤ n: Finish[i] = false ⇒ hệ thống đang ở trạng thái
 deadlock. Hơn thế nữa, Finish[i] = false ⇒ Pi bị deadlock.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.26-
 13
 Detection Algorithm – Ví dụ
 Có 5 processes P0 – P4
 3 loại tài nguyên A (7 instance), B (2 instance), C (6 instance).
 Allocation Request Available
 A BAC A B C B C
 P0 0 1 0 0 0 0 0 0 0
 P1 2 0 0 2 0 2
 P2 3 0 3 0 0 0
 P3 2 1 1 1 0 0
 P4 0 0 2 0 0 2
  Cấp phát theo thứ tự sẽ có kết quả
 là ∀i Finish[i] = true ⇒ hệ thống không bị deadlock.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.27-
 Detection Algorithm – Ví dụ (t.t)
 P2 yêu cầu thêm một instance của C. Ma trận Request 
 như sau:
 Request
 A B C
 P0 0 0 0
 P1 2 0 1
 P2 0 0 1
 P3 1 0 0 
 P4 0 0 2
 Trạng thái của hệ thống là gì?
 – Có thể thu hồi tài nguyên đang sở hữu bởi process P0 nhưng vẫn
 không đủ đáp ứng yêu cầu của các process khác.
 ⇒ Tồn tại deadlock, bao gồm các processe P1, P2, P3, và P4.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.28-
 14
 Deadlock Recovery
 Phục hồi hệ thống bị deadlock chủ yếu là bẻ gãy chu kỳ
 wait-for của các process bị deadlock.
 – Hủy bỏ tất cả process bị deadlock .
 – Hủy bỏ lần lượt từng process và thu hồi tài nguyên cho đến khi
 không còn deadlock.
 Dựa trên cơ sở nào để hủy process ?
 – Độ ưu tiên của process ?
 – Thời gian đã thực thi của process và thời gian còn lại ?
 – Loại tài nguyên mà process đã sử dụng ?
 – Tài nguyên mà process cần để hoàn tất công việc ?
 – Số lượng processes cần hủy bỏ ? 
 – Process là interactive process hay batch process?
 – ...
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.29-
 Thu hồi tài nguyên
 Đoạt tài nguyên từ một process, cấp phát cho
 process khác cho đến khi không còn deadlock 
 nữa.
 Các vấn đề trong chiến lược thu hồi tài nguyên:
 – Chọn “nạn nhân” – tối thiểu chi phí (có thể dựa trên
 số tài nguyên sở hữu, thời gian CPU đã tiêu tốn,...)
 – Rollback – quay trở về trạng thái safe, bắt đầu các
 process từ trạng thái đó. Gồm có total rollback và
 check-point rollback
  Hệ thống cần lưu giữ một số thông tin về trạng thái
 các process đang thực thi
 – Starvation – phải bảo đảm không có process sẽ luôn
 luôn bị đoạt tài nguyên mỗi khi deadlock xảy ra
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.30-
 15
 Phương pháp tổng hợp
 Phân hoạch tài nguyên thành các nhóm có phân cấp
 ⇒ dùng phương pháp linear ordering để phòng chống
 deadlock đối với các nhóm. Trong mỗi nhóm, dùng giải
 thuật phù hợp nhất để giải quyết deadlock.
 Một số ví dụ
 – Swappable space: khối bộ nhớ hoặc thiết bị lưu trữ phụ dùng
 làm bộ nhớ tráo đổi tạm (swap memory) 
  Hold-and-Wait Prevention + Avoidance
 – Process resource: assignable device như tape drive, file,...
  Avoidance hoặc Resource Ordering
 – Main memory: memory page/segment
  Preemption
 – Internal resource: PCB, I/O channel,
  Resource Ordering
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -8.31-
 16