Bài giảng Điều độ các tiến trình - Nguyễn Thị Thùy Linh

ờ: Một quá trình đang giữ ít nhất là một tài nguyên 
 và đang chờ để đạt được một tài nguyên khác đang bị giữ bởi 
 quá trình khác. 
 Không đòi lại tài nguyên từ quá trình đang giữ chúng: một 
 tài nguyên có thể được giải phóng một cách tự nguyện bởi quá 
 trình đang giữ nó, sau khi quá trình này hoàn thành. 
 Tồn tại chu trình trong đồ thị cấp phát tài nguyên: tồn tại 
 một tập hợp {P0, P1, , Pn} các quá trình đang chờ đợi như 
 sau: P0 đang đợi tài nguyên mà P1 đang giữ, P1 đang đợi tài 
 nguyên mà P2 đang giữ, , Pn–1 đang đợi tài nguyên mà Pn 
 đang giữ và Pn lại đang chờ đợi tài nguyên mà P0 đang giữ 
 81 
2. Đồ thị cấp phát tài nguyên 
Bao gồm tập hợp các đỉnh V và tập hợp các cạnh E. 
 V được chia làm 2 kiểu: 
  P = {P1, P2, , Pn}, là tập hợp các quá trình đang tồn tại trong 
 hệ thống. 
  R = {R1, R2, , Rm}, là tập hợp các tài nguyên đang tồn tại trong 
 hệ thống. 
 Cạnh yêu cầu: Pi Rj. 
 QT Pi yêu cầu 1 kiểu thể hiện của kiểu tài nguyên Rj 
 Cạnh cấp phát: Rj Pi 
 Một thể hiện của kiểu tài nguyên Rj đã được cấp cho QT 
 Pi 
 82 
 (Resource-Allocation Graph - RAG) 
Các ký hiệu: 
 Tập các quá trình Pi 
 P=(P1, P2, Pn) 
 Tài nguyên với 4 thể hiện Rj 
 P 
 Pi yêu cầu một thể hiện của Rj i Rj 
 Pi đang giữ một thể hiện của Rj P 
 i Rj 
 83 
Nếu đồ thị không có chu trình thì sẽ không xảy ra deadlock 
 84 
85 
Không deadlock vì: 
-P4 hoặc P2 có thể 
tự động giải phóng 
tài nguyên. 
-Nên P1 và P3 kết 
thúc được 
 86 
 Nếu đồ thị không có chu trình không có 
 deadlock. 
  Nếu đồ thị có một chu trình 
  – Nếu một tài nguyên chỉ có một thể 
 hiện thì chắn chắn deadlock xảy ra. 
  – Nếu một tài nguyên có vài thể hiện 
 thì có thể có deadlock. 
 87 
 Có 3 phương pháp xử lý Deadlock 
 1. Söû duïng quy taéc Ngaên chaën (Prevention) 
 hoaëc Traùnh (Avoidance) ñeå Deadlock khoâng 
 bao giôø xaûy ra. 
 2. Cho pheùp heä thoáng bò Deadlock, sau ñoù Xaùc 
 ñònh (Detection) vaø tìm caùch Khaéc phuïc 
 (Recover). 
 3. Khoâng xeùt vaán ñeà Deadlock, coi nhö khoâng 
 bao giôø xaûy ra, coøn neáu xaûy ra thì Khôûi ñoäng 
 laïi heä thoáng (Caùch naøy coù theå coù yù nghóa 
 thöïc teá vì khoâng caàn ñöa vaøo HÑH caùc 
 phöông tieän xöû trí thöôøng tröïc). 88 
PP xử lý Deadlock: 
 1. Để đảm bảo deadlock không xảy ra, hệ thống có thể sử 
 dụng: sơ đồ phòng ngừa hoặc sơ đồ tránh deadlock 
  Phòng ngừa deadlock (deadlock prevention): các giải 
 pháp để đảm bảo ít nhất 1 điều kiện cần không xảy ra. 
  Tránh deadlock (deadlock advoidance): dựa trên thông 
 tin: 
  Yêu cầu giải phóng tài nguyên trong tương lai của 
 mỗi QT. 
  Các tài nguyên hiện đang bị chiếm giữ bởi mỗi QT 
  Các tài nguyên hiện sẵn có trong hệ thống 
  quyết định 1 yêu cầu tài nguyên của QT sẽ được 
 đáp ứng ngay hay phải chờ. 
 89 
PP xử lý Deadlock: (tt) 
2. Cho phép deadlock xảy ra rồi phục hồi: 
  Cần có một thuật toán kiểm tra trạng thái của hệ 
 thống để phát hiện deadlock 
  Và một thuật toán khôi phục deadlock 
3. Bỏ qua deadlock: 
  Có thể làm hệ thống rơi vào tình trạng ngưng vận 
 động. Trường hợp như vậy giải pháp là khởi động lại 
 hệ thống bằng tay. 
 90 
Baèng caùch sao cho ít nhaát 1 trong 4 ñieàu kieän caàn keå treân khoâng xaûy ra. 
 Loại trừ hỗ tương (Mutual Exclusion) – không yêu cầu đối với các 
tài nguyên chia sẻ, chỉ áp dụng đối với các tài nguyên không thể 
chia sẻ. 
 Giữ và chờ (Hold and Wait) – phải đảm bảo rằng mỗi khi một quá 
trình yêu cầu một tài nguyên, nó không có giữ một tài nguyên 
khác. 
 - Yêu cầu quá trình yêu cầu và được cấp tất cả các tài 
 nguyên nó cần sau đó mới được thực thi, hoặc là yêu cầu 
 rằng quá trình chỉ có thể yêu cầu một tài nguyên khi nó hiện 
 không giữ một tài nguyên nào cả. 
 - Giải pháp này làm giảm đáng kể hiệu xuất sử dụng tài 
 nguyên, và có thể gây ra tình trạng chết đói 
 91 
 Không đòi lại tài nguyên từ quá trình đang giữ chúng 
( không trưng dụng - No Preemption): 
 Nếu một quá trình đang giữ một số tài nguyên lại yêu cầu thêm 
 một tài nguyên mới, nhưng tài nguyên mới này không thể được cấp 
 phát cho quá trình đó được, thì quá trình đó phải ngay lập tức giải 
 phóng tất cả các tài nguyên nó đang có. 
 Các tài nguyên vừa được trưng dụng được thêm vào danh sách 
 các tài nguyên mà quá trình đang cần. 
 quá trình sẽ bị khởi động lại chỉ khi nó không thể xin lại được các 
 tài nguyên cũ cũng như tài nguyên mới nó đang cần. 
 Tồn tại chu trình trong đồ thị cấp phát tài nguyên 
Circular Wait (chờ đợi vòng tròn): phải bày ra thứ tự toàn cục của 
tất cả các tài nguyên và yêu cầu rằng mỗi quá trình phải yêu cầu các tài 
nguyên theo thứ tự đã cho. 
 92 
Yêu cầu HĐH phải có một số thông tin ưu tiên: 
 Mô hình đơn giản và hữu dụng nhất yêu cầu rằng mỗi quá 
 trình phải khai báo số lượng tối đa các tài nguyên mà nó 
 có thể cần đến. 
 Giải thuật tránh deadlock tự động xem xét trạng thái cấp 
 phát tài nguyên của hệ thống để đảm bảo rằng không bao 
 giờ có tình trạng chờ đợi vòng tròn. 
 Trạng thái cấp phát tài nguyên được định nghĩa dựa trên 
 số lượng tài nguyên đã được cấp phát và chưa được cấp 
 phát, và số lượng tối đa các yêu cầu của các quá trình. 
 93 
 Khi một quá trình yêu cầu một tài nguyên đang sẵn dùng, 
 hệ thống phải quyết định xem việc cấp tài nguyên này tức 
 thời có đưa hệ thống đến trạng thái an toàn hay không. 
 Hệ thống ở trạng thái an toàn nếu tồn tại một dãy an toàn 
 đối với tất cả quá trình. 
 Chuỗi được gọi là an toàn nếu với mỗi 
 quá trình Pi, các tài nguyên mà Pi có thể còn yêu cầu có 
 thể được làm thõa mãn bởi các tài nguyên đang sẵn dùng + 
 các tài nguyên đã bị chiếm bởi tất cả quá trình Pj, với j<i. 
  Nếu các nhu cầu tài nguyên của Pi không được làm thõa mãn 
 ngay tức thì, thì Pi có thể đợi đến khi tất cả Pj hoàn thành. 
  Khi Pj hoàn thành, Pi có thể lấy các tài nguyên cần thiết, thực thi 
 tiếp, trả lại số tài nguyên đã chiếm và sau cùng là kết thúc. 
  Khi Pi kết thúc, Pi+1 có thể lấy các tài nguyên mà nó cần, và cứ 
 như thế 94 
95 
 Nếu hệ thống ở trong trạng thái an toàn không có 
 deadlocks. 
 Nếu hệ thống ở trong trạng thái không an toàn có 
 thể có deadlock. 
 Tránh deadlock đảm bảo rằng hệ thống sẽ không 
 bao giờ rơi vào trạng thái không an toàn. 
 Giải pháp: 
 - Mỗi tài nguyên có một thể hiện: dùng giải thuật đồ thị 
 cấp phát tài nguyên. 
 - Mỗi loại tài nguyên có nhiều thể hiện:dùng giải thuật 
 Banker. 
 96 
 Cạnh “muốn yêu cầu (claim edge)” Pi → Rj chỉ ra 
 rằng quá trình Pi có thể yêu cầu tài nguyên Rj; cạnh 
 này được biểu diễn bởi một đường đứt nét. 
 Cạnh muốn yêu cầu chuyển thành cạnh yêu cầu khi 
 quá trình yêu cầu một tài nguyên. 
 Khi một tài nguyên được giải phóng bởi một quá 
 trình, cạnh yêu cầu chuyển thành cạnh muốn yêu cầu. 
 Các tài nguyên phải được dự tính yêu cầu trước trong 
 hệ thống 
 97 
98 
99 
 Một tài nguyên có nhiều thể hiện. 
 Mỗi quá trình phải dự tính trước số tài nguyên tối 
 đa mà mình cần dùng. 
 Khi một quá trình yêu cầu một tài nguyên, nó có 
 thể phải chờ đợi. 
 Khi một quá trình có được tất cả tài nguyên mà nó 
 cần, nó phải trả lại hết các tài nguyên trong một 
 khoảng thời gian hữu hạn. 100 
Đặt n = số quá trình, m = số loại tài nguyên. 
 Available: Vector có chiều dài m. Nếu available [j] = k, có k 
 thể hiện của tài nguyên Rj đang sẵn dùng. 
 Max: ma trận n x m. Nếu Max [i,j] = k, thì quá trình Pi có 
 thể yêu cầu tối đa k thể hiện của tài nguyên Rj. 
 Allocation: ma trận n x m. Nếu Allocation[i,j] = k thì Pi 
 đang giữ k thể hiện của Rj. 
 Need: Ma trận n x m. Nếu Need[i,j] = k, thì Pi có thể cần 
 thêm k thể hiện của tài nguyên Rj để có thể hoàn thành công 
 việc của nó. 
 Need [i,j] = Max[i,j] – Allocation [i,j]. 
 101 
1.Đặt Work và Finish là các vectors có độ dài tương ứng là 
 m và n. Khởi tạo: 
 Work = Available 
 Finish[i] = false for i =1,2,3, , n. 
2. Tìm i để cả hai điều kiện sau thõa: 
 (a) Finish[i] = false 
 (b) Need[i] Work[i] 
 Nếu không tồn tại i, nhảy đến bước 4. 
3. Work = Work + Allocation[i] 
 Finish[i] = true 
 nhảy đến bước 2. 
4. Nếu Finish [i] == true với mọi i, thì hệ thống đang ở 
 trạng thái an toàn. 
 102 
 5 quá trình từ P0 , P4 
 3 loại tài nguyên A (10 thể hiện), B (5 thể hiện), và C (7 
 thể hiện). 
 Hiện trạng tại thời điểm T0: 
 Allocation Max Available 
 A B C A B C A B C 
 P0 0 1 0 7 5 3 3 3 2 
 P1 2 0 0 3 2 2 
 P2 3 0 2 9 0 2 
 P3 2 1 1 2 2 2 
 P4 0 0 2 4 3 3 
 103 
 Need Allocation Max Work Available 
 A B C A B C A B C A B C A B C 
 P0 7 4 3 0 1 0 7 5 3 10 5 7 3 3 2 
 P1 1 2 2 2 0 0 3 2 2 5 3 2 
 P2 6 0 0 3 0 2 9 0 2 10 4 7 
 P3 0 1 1 2 1 1 2 2 2 7 4 3 
 P4 4 3 1 0 0 2 4 3 3 7 4 5 
 Nội dung của ma trận Need = Max – Allocation. 
 Hệ thống đang ở trạng thái an toàn do dãy < P1, P3, P4, P2, 
 P0> thõa mãn tiêu chí về an toàn. Nên không bị deadlock. 
 Vì hệ thống có đủ TN để cấp cho các QT theo thứ tự trên. 
 104 
 P1 YÊU CẦU THÊM 1 TN LOẠI A, 2 TN LOẠI C 
 HỎI CÓ CẤP PHÁT NGAY LẬP TỨC KHÔNG? 
 Thực thi giải thuật yêu cầu tài nguyên đối với p1 (slide 
 32) 
 Hiện trạng mới của hệ thống đã thay đổi đối với p1 
 Thực thi gỉai thuật an toàn (slide 28) 
 Nếu dãy cũ vẫn an toàn => cấp phát ngay lập tức cho p1 
 Nếu dãy cũ không an toàn => tìm ra dãy mới theo giải 
 thuật an toàn => cấp phát cho P1 theo thứ tự mới 
 Nếu không tìm được dãy nào an toàn cả => p1 chờ 
Request = vector yêu cầu cho quá trình Pi. Nếu Request[i,j] = 
 k thì quá trình Pi muốn k thể hiện của tài nguyên Rj. 
 1. Nếu Request[i,j] Need[i,j] nhảy sang bước 2. Ngược lại, báo lỗi 
 do quá trình đã vượt quá số tài nguyên nó đã dự định sử dụng. 
 2. Nếu Request[i,j] Available[j], nhảy sang bước 3. Ngược lại Pi 
 phải chờ, do các tài nguyên nó yêu cầu hiện không sẵn dùng. 
 3. Giả vờ như đang cấp tài nguyên cho Pi bằng cách sửa đổi trạng thái 
 như sau: 
 Available[j] = Available[j] – Request[i,j]; 
 Allocation[i,j] = Allocation[i,j] + Request[i,j]; 
 Need[i,j] = Need[i,j] – Request[i,j] 
  Nếu an toàn tài nguyên được cấp cho Pi. 
  Nếu không an toàn Pi phải đợi, và trạng thái cấp phát tài nguyên cũ được 
 phục hồi 
 106 
 Kiểm tra Request Available (nghĩa là, (1,0,2) (3,3,2)) true. 
 Allocation Need Available 
 A B C A B C A B C 
 P0 0 1 0 7 4 3 2 3 0 
 P1 3 0 2 0 2 0 
 P2 3 0 2 6 0 0 
 P3 2 1 1 0 1 1 
 P4 0 0 2 4 3 1 
 Sự thực hiện giải thuật an toàn cho thấy dãy thõa 
 mãn yêu cầu về an toàn. Vậy cấp phát ngay lập tức cho P1. Vì hệ 
 thống vẫn đủ tài nguyên để cấp phát liền cho P1 
 107 
BÀI TẬP 
 Giả sử hiện trạng hệ thống ở thời điểm T0 (slide 30) 
 Yêu cầu (3,3,0) của P4 có thể được cấp không? 
 hoặc 
 Yêu cầu (0,2,0) của P0 có thể được cấp không? 
 Cho phép hệ thống bước vào trạng thái 
 deadlock. 
 Phát hiện Deadlock 
  TN có 1 thể hiện thì dùng đồ thị chờ (wait-for), 
 khắc phục bằng cách gở bỏ 1 cạnh trong đồ thị chờ 
 tương đương 1 cạnh và 1 đỉnh tài nguyên trong đồ 
 thị cấp phát tài nguyên. 
  TN có nhiều thể hiện thì dùng giải thuật phát hiện 
 Deadlock (slide 38). Khắc phục bằng cách kết thúc 
 quá trình. 
 109 
 Duy trì đồ thị wait-for 
  Các nút là các quá trình. 
  Pi Pj nếu Pi đang đợi Pj 
 Thường xuyên thực hiện giải thuật tìm kiếm 
 chu trình trong đồ thị chờ. 
 Một giải thuật phát hiện chu trình trong đồ thị 
 yêu cầu theo thứ tự n2 thao tác, với n là số cạnh 
 trong đồ thị. 
 110 
Đồ thị cấp phát tài nguyên Đồ thị wait-for tương ứng 
 111 
 Available: Vector có chiều dài m chỉ ra số lượng thể 
 hiện còn sẵn dùng của mỗi loại tài nguyên. 
 Allocation: Một ma trận n x m định nghĩa số lượng 
 thể hiện của mỗi loại tài nguyên hiện đang được cấp 
 phát cho mỗi tiến trình. 
 Request: Một ma trận n x m chỉ ra lượng yêu cầu của 
 mỗi quá trình. Nếu Request [i,j] = k, thì quá trình Pi 
 đang yêu cầu thêm k thể hiện của tài nguyên loại Rj 
 112 
1. Đặt Work và Finish là các vectors có chiều dài 
 tương ứng m và n, khởi tạo: 
 (a) Work = Available 
 (b) For i = 1,2, , n 
 if Allocation[i] 0 then Finish[i] = false; 
 else Finish[i] = true; 
2. Tìm ra chỉ số i để hai điều kiện sau được thõa: 
 (a) Finish[i] == false 
 (b) Request[i] Work[i] 
 Nếu không tồn tại i, nhảy đến bước 4 
 113 
3.Work = Work + Allocation[i] 
 Finish[i] = true 
 Nhảy đến bước 2. 
4. If Finish[i] == false, for some i, 1 i n, then hệ 
 thống đang ở trạng thái deadlock. Ngoài ra, if Finish[i] 
 == false, then Pi đang bị deadlock. 
 Giải thuật yêu cầu O(m x n2) thao tác để phát hiện ra 
 hệ thống có bị deadlock hay không 
 114 
 Năm quá trình P0 đến P4; có 3 kiểu tài nguyên 
 A (7 thể hiện), B (2 thể hiện), và C (6 thể hiện). 
 Hiện trạng tại thời điểm T0: 
 Allocation Request Available 
 A B C A B C A 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 
 Chuỗi sẽ dẫn đến Finish[i] = true với 
 mọi i. 
 115 
 P2 yêu cầu thêm một thể hiện của tài nguyên loại C. 
 Request 
 A B C 
 P0 0 0 0 
 P1 2 0 2 
 P2 0 0 1 
 P3 1 0 0 
 P4 0 0 2 
 Trạng thái của hệ thống? 
  P0 không yêu cầu thêm tài nguyên nào, nhưng hệ thống vẫn 
 không đủ tài nguyên để thõa mãn nhu cầu của các quá trình 
 khác. 
  Deadlock xảy ra, bao gồm các quá trình P1, P2, P3, và P4. 
 116 
 Sử dụng giải thuật khi nào và thường xuyên như 
 thế nào sẽ phụ thuộc vào: 
  Có deadlock có khả năng xảy ra thường xuyên như thế nào? 
  Bao nhiêu quá trình cần phải quay lại? 
 Một quá trình để mở một nút trong chu trình 
 Nếu giải thuật phát hiện deadlock xảy ra quá ít, 
 thì có thể sẽ có nhiều chu trình xuất hiện trong đồ 
 thị. Khi đó, khó có thể bảo rằng quá trình nào 
 trong số các quá trình bị deadlock đã gây ra 
 deadlock. 117 
 Hủy bỏ tất cả các quá trình bị deadlock 
 ( Finish[i]:=False) 
 Hủy bỏ một lần một quá trình cho đến khi chu trình deadlock bị loại 
 trừ. 
 Thế chúng ta nên hủy bỏ các quá trình theo thứ tự nào? 
  Độ ưu tiên của quá trình. 
  quá trình đã diễn ra lâu chưa và nó còn tiếp diễn bao lâu nữa? 
  Số tài nguyên mà quá trình đã sử dụng. 
  Số tài nguyên mà quá trình cần phải tranh chấp thêm. 
  Có bao nhiêu quá trình cần phải được dừng. 
  quá trình là quá trình tương tác hay theo quá trình bó? 
 118 
 Chọn một quá trình nạn nhân dựa vào giá trị nhỏ 
 nhất. 
 Rollback – quay lại trạng thái an toàn nào đó, khởi 
 động lại quá trình từ trạng thái đó. 
 Starvation – một quá trình có thể liên tục được chọn 
 là nạn nhân, làm nó không thể kết thúc. 
 Giải pháp: 
 119 
 Kết hợp 3 giải pháp cơ bản 
  Ngăn chặn - Prevention 
  Tránh - Avoidance 
  Phát hiện - Detection 
 cho phép áp dụng một giải pháp tối ưu cho một loại tài 
 nguyên trong hệ thống. 
 Phân chia các tài nguyên thành các lớp theo thứ tự phân 
 cấp. 
 Sử dụng kỹ thuật thích hợp nhất để khống chế deadlock 
 trong mỗi lớp tài nguyên. 
 120