Bài giảng Khoa học Máy tính Hệ điều hành - Chương 2: Quản lý tiến trình - Phạm Hải Đăng

Nội dung text: Bài giảng Khoa học Máy tính Hệ điều hành - Chương 2: Quản lý tiến trình - Phạm Hải Đăng

1. Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.5 Phòng tránh bế tắc Thuật toán yêu cầu tài nguyên Request[i] Vector yêu cầu tài nguyên của tiến trình Pi Request[3,2] = 2: Tiến trình P3 yêu cầu 2 đơn vị tài nguyên R2 Khi Pi yêu cầu tài nguyên, hệ thống thực hiện 1 if(Request[i]>Need[i]) Error(Yêu cầu vượt quá khai báo tài nguyên) 2 if(Request[i]>Available) Block(Không đủ tài nguyên, tiến trình phải đợi) 3 Thiết lập trạng thái phân phối tài nguyên mới cho hệ thống Available = Available - Request[i] Allocation[i] = Allocation[i] + Request[i] Need[i] = Need[i] - Request[i] 4 Phân phối tài nguyên dựa trên kết quả kiểm tra tính an toàn của trạng thái phân phối tài nguyên mới if(Safe(New Resource Allocation State)) Phân phối cho Pi theo yêu cầu else Tiến trình Pi phải đợi 187 / 201 Khôi phục lại trạng thái cũ (Available, Allocation,Need)
2. Yêu cầu được chấp nhận Thực hiện thuật toán an toàn Tiến trình P0 P1 P2 P3 P4 Finish TT Work Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.5 Phòng tránh bế tắc Ví dụ minh họa : P1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 7 4 3 P1 3 0 2 P1 0 2 0 P2 3 0 2 P2 6 0 0 P3 2 1 1 P3 0 1 1 P4 0 0 2 P4 4 3 1 Allocation Need 188 / 201
3. Yêu cầu được chấp nhận Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.5 Phòng tránh bế tắc Ví dụ minh họa : P1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 7 4 3 P1 3 0 2 P1 0 2 0 P2 3 0 2 P2 6 0 0 P3 2 1 1 P3 0 1 1 P4 0 0 2 P4 4 3 1 Allocation Need Thực hiện thuật toán an toàn Tiến trình P0 P1 P2 P3 P4 Finish FFFFF Work (2, 3, 0) 188 / 201
4. Yêu cầu được chấp nhận Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.5 Phòng tránh bế tắc Ví dụ minh họa : P1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 7 4 3 P1 3 0 2 P1 0 2 0 P2 3 0 2 P2 6 0 0 P3 2 1 1 P3 0 1 1 P4 0 0 2 P4 4 3 1 Allocation Need Thực hiện thuật toán an toàn Tiến trình P0 P1 P2 P3 P4 Finish FT FFF Work (5, 3, 2) 188 / 201
5. Yêu cầu được chấp nhận Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.5 Phòng tránh bế tắc Ví dụ minh họa : P1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 7 4 3 P1 3 0 2 P1 0 2 0 P2 3 0 2 P2 6 0 0 P3 2 1 1 P3 0 1 1 P4 0 0 2 P4 4 3 1 Allocation Need Thực hiện thuật toán an toàn Tiến trình P0 P1 P2 P3 P4 Finish FTFT F Work (7, 4, 3) 188 / 201
6. Yêu cầu được chấp nhận Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.5 Phòng tránh bế tắc Ví dụ minh họa : P1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 7 4 3 P1 3 0 2 P1 0 2 0 P2 3 0 2 P2 6 0 0 P3 2 1 1 P3 0 1 1 P4 0 0 2 P4 4 3 1 Allocation Need Thực hiện thuật toán an toàn Tiến trình P0 P1 P2 P3 P4 Finish FTFTT Work (7, 4, 5) 188 / 201
7. Yêu cầu được chấp nhận Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.5 Phòng tránh bế tắc Ví dụ minh họa : P1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 7 4 3 P1 3 0 2 P1 0 2 0 P2 3 0 2 P2 6 0 0 P3 2 1 1 P3 0 1 1 P4 0 0 2 P4 4 3 1 Allocation Need Thực hiện thuật toán an toàn Tiến trình P0 P1 P2 P3 P4 Finish TTTTT Work (10, 5, 7) 188 / 201
8. Tiến trình P0 yêu cầu thêm 2 đơn vị R1 Request[0]≤Available ((0, 2, 0) ≤ (2, 3, 0)) ⇒ Có thể cung cấp Nếu cung cấp : Available = (2 , 1, 0) Thực hiện thuật toán an toàn ⇒ Tất cả các tiến trình đều có thể không kết thúc ⇒ Nếu chấp nhận, hệ thống rơi vào trạng thái không an toàn ⇒ Đủ tài nguyên nhưng không cung cấp. P0 phải đợi Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.5 Phòng tránh bế tắc Ví dụ minh họa (tiếp tục) Tiến trình P4 yêu cầu thêm 3 đơn vị R0 và 3 đơn vị R2 Request[4] = (3, 0, 3) Available = (2, 3, 0) ⇒ Không đủ tài nguyên, P4 phải đợi 189 / 201
9. Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục 5 Bế tắc và xử lý bế tắc Khái niệm bế tắc Điều kiện xảy ra bế tắc Các phương pháp xử lý bế tắc Phòng ngừa bế tắc Phòng tránh bế tắc Nhận biết và khắc phục 190 / 201
10. Khắc phục bế tắc Kết thúc tiến trình Trưng dụng tài nguyên Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Giới thiệu Nguyên tắc Không áp dụng các biện pháp phòng ngừa hoặc phòng tránh, để cho bế tắc xảy ra Định kỳ kiểm tra xem bế tắc có đang xảy ra không. Nếu có tìm cách khắc phục Để thực hiện, hệ thống phải cung cấp Thuật toán xác định hệ thống đang bế tắc không Thuật toán chữa bế tắc Nhận biết bế tắc Thuật toán dựa trên đồ thị cung cấp tài nguyên Thuật toán chỉ ra bế tắc tổng quát 191 / 201
11. Kiểm tra hệ thống có bế tắc bằng cách kiểm tra chu trình trên đồ thị Nếu trên đồ thị có chu trình, hệ thống đang bế tắc Định kỳ gọi tới các thuật toán kiểm tra chu kỳ trên đồ thị Thuật toán đòi hỏi n2 thao tác (n: số đỉnh của đồ thị) Sử dụng đồ thị chờ đợi - phiên bản thu gọn của đồ thị cung cấp tài nguyên Chỉ có các đỉnh dạng tiến trình Cung chờ đợi Pi → Pj : Tiến trình Pi đang đợi tiến trình Pj giải phóng tài nguyên Pi cần Cung chờ đợi Pi → Pj tồn tại trên đồ thị đợi khi và chỉ khi trên đồ thị phân phối tài nguyên tương ứng tồn tại đồng thời cung yêu cầu Pi → R và cung sử dụngR → Pj Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Thuận toán dựa trên đồ thị cung cấp tài nguyên Áp dụng khi mỗi tài nguyên trong hệ thống có một đơn vị 192 / 201
12. Sử dụng đồ thị chờ đợi - phiên bản thu gọn của đồ thị cung cấp tài nguyên Chỉ có các đỉnh dạng tiến trình Cung chờ đợi Pi → Pj : Tiến trình Pi đang đợi tiến trình Pj giải phóng tài nguyên Pi cần Cung chờ đợi Pi → Pj tồn tại trên đồ thị đợi khi và chỉ khi trên đồ thị phân phối tài nguyên tương ứng tồn tại đồng thời cung yêu cầu Pi → R và cung sử dụngR → Pj Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Thuận toán dựa trên đồ thị cung cấp tài nguyên Áp dụng khi mỗi tài nguyên trong hệ thống có một đơn vị Kiểm tra hệ thống có bế tắc bằng cách kiểm tra chu trình trên đồ thị Nếu trên đồ thị có chu trình, hệ thống đang bế tắc Định kỳ gọi tới các thuật toán kiểm tra chu kỳ trên đồ thị Thuật toán đòi hỏi n2 thao tác (n: số đỉnh của đồ thị) 192 / 201
13. Đồ thị chờ đợi P4 P1 P2 P3 P5 Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Đồ thị chờ đợi: Ví dụ P4 R3 R4 R5 P1 P2 P3 R1 P5 R2 193 / 201
14. Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Đồ thị chờ đợi: Ví dụ P4 Đồ thị chờ đợi R3 R4 R5 P4 P1 P2 P3 P1 P2 P3 R1 P5 R2 P5 193 / 201
15. //Allocation= 0 không nằm trong chu trình đợi //Giả thiết tối ưu, đây là yêu cầu cuối //Finish[i] = false, tiến trình Pi đang bị bế tắc Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Thuật toán chỉ ra bế tắc tổng quát BOOL Deadlock(Current Resource-Allocation State){ Work←Available For (i : 1 → n) if(Allocation[i]6= 0) Finish[i]←false else Finish[i]=true; flag← true While(flag){ flag←false for (i : 1 → n) do if(Finish[i]=false AND Request[i] ≤Work){ Finish[i]← true Work ← Work+Allocation[i] flag← true }//endif }//endwhile for (i : 1 → n) if (Finish[i]=false) return true; return false; }//End function 195 / 201
16. //Finish[i] = false, tiến trình Pi đang bị bế tắc Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Thuật toán chỉ ra bế tắc tổng quát BOOL Deadlock(Current Resource-Allocation State){ Work←Available For (i : 1 → n) if(Allocation[i]6= 0) Finish[i]←false else Finish[i]=true;//Allocation= 0 không nằm trong chu trình đợi flag← true While(flag){ flag←false for (i : 1 → n) do//Giả thiết tối ưu, đây là yêu cầu cuối if(Finish[i]=false AND Request[i] ≤Work){ Finish[i]← true Work ← Work+Allocation[i] flag← true }//endif }//endwhile for (i : 1 → n) if (Finish[i]=false) return true; return false; }//End function 195 / 201
17. Hệ thống không bế tắc (P0, P2, P3, P1, P4) Tài nguyên hiện có (R0, R1, R2) =(0, 0, 0) Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish Work Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa 5 tiến trình P0, P1, P2, P3, P4; 3 tài nguyên R0, R1, R2 Tài nguyên R0 có 7 đơn vị, R1 có 2 đơn vị, R2 có 6 đơn vị Trạng thái cung cấp tài nguyên tại thời điểm t0 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 0 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request 196 / 201
18. Hệ thống không bế tắc (P0, P2, P3, P1, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa 5 tiến trình P0, P1, P2, P3, P4; 3 tài nguyên R0, R1, R2 Tài nguyên R0 có 7 đơn vị, R1 có 2 đơn vị, R2 có 6 đơn vị Trạng thái cung cấp tài nguyên tại thời điểm t0 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 0 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Tài nguyên hiện có (R0, R1, R2) =(0, 0, 0) Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish FFFFF Work (0, 0, 0) 196 / 201
19. Hệ thống không bế tắc (P0, P2, P3, P1, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa 5 tiến trình P0, P1, P2, P3, P4; 3 tài nguyên R0, R1, R2 Tài nguyên R0 có 7 đơn vị, R1 có 2 đơn vị, R2 có 6 đơn vị Trạng thái cung cấp tài nguyên tại thời điểm t0 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 0 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Tài nguyên hiện có (R0, R1, R2) =(0, 0, 0) Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish T FFFF Work (0, 1, 0) 196 / 201
20. Hệ thống không bế tắc (P0, P2, P3, P1, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa 5 tiến trình P0, P1, P2, P3, P4; 3 tài nguyên R0, R1, R2 Tài nguyên R0 có 7 đơn vị, R1 có 2 đơn vị, R2 có 6 đơn vị Trạng thái cung cấp tài nguyên tại thời điểm t0 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 0 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Tài nguyên hiện có (R0, R1, R2) =(0, 0, 0) Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish TFT FF Work (3, 1, 3) 196 / 201
21. Hệ thống không bế tắc (P0, P2, P3, P1, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa 5 tiến trình P0, P1, P2, P3, P4; 3 tài nguyên R0, R1, R2 Tài nguyên R0 có 7 đơn vị, R1 có 2 đơn vị, R2 có 6 đơn vị Trạng thái cung cấp tài nguyên tại thời điểm t0 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 0 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Tài nguyên hiện có (R0, R1, R2) =(0, 0, 0) Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish TFTTF Work (5, 2, 4) 196 / 201
22. Hệ thống không bế tắc (P0, P2, P3, P1, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa 5 tiến trình P0, P1, P2, P3, P4; 3 tài nguyên R0, R1, R2 Tài nguyên R0 có 7 đơn vị, R1 có 2 đơn vị, R2 có 6 đơn vị Trạng thái cung cấp tài nguyên tại thời điểm t0 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 0 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Tài nguyên hiện có (R0, R1, R2) =(0, 0, 0) Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish TTTT F Work (7, 2, 4) 196 / 201
23. Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa 5 tiến trình P0, P1, P2, P3, P4; 3 tài nguyên R0, R1, R2 Tài nguyên R0 có 7 đơn vị, R1 có 2 đơn vị, R2 có 6 đơn vị Trạng thái cung cấp tài nguyên tại thời điểm t0 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 0 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Tài nguyên hiện có (R0, R1, R2) =(0, 0, 0) Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish TTTTT Work (7, 2, 6) Hệ thống không bế tắc (P0, P2, P3, P1, P4) 196 / 201
24. P0 có thể kết thúc nhưng hệ thống đang bế tắc. Các tiến trình đang chờ đợi lẫn nhau (P1, P2, P3, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa (tiếp) P2 yêu cầu thêm 1 đơn vị tài nguyên R2 Trạng thái cung cấp tài nguyên tại thời điểm t1 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 1 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish FFFFF Work (0, 0, 0) 197 / 201
25. P0 có thể kết thúc nhưng hệ thống đang bế tắc. Các tiến trình đang chờ đợi lẫn nhau (P1, P2, P3, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa (tiếp) P2 yêu cầu thêm 1 đơn vị tài nguyên R2 Trạng thái cung cấp tài nguyên tại thời điểm t1 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 1 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish T FFFF Work (0, 1, 0) 197 / 201
26. P0 có thể kết thúc nhưng hệ thống đang bế tắc. Các tiến trình đang chờ đợi lẫn nhau (P1, P2, P3, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa (tiếp) P2 yêu cầu thêm 1 đơn vị tài nguyên R2 Trạng thái cung cấp tài nguyên tại thời điểm t1 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 1 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish TFF FF Work (0, 1, 0) 197 / 201
27. P0 có thể kết thúc nhưng hệ thống đang bế tắc. Các tiến trình đang chờ đợi lẫn nhau (P1, P2, P3, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa (tiếp) P2 yêu cầu thêm 1 đơn vị tài nguyên R2 Trạng thái cung cấp tài nguyên tại thời điểm t1 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 1 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish TFFFF Work (0, 1, 0) 197 / 201
28. P0 có thể kết thúc nhưng hệ thống đang bế tắc. Các tiến trình đang chờ đợi lẫn nhau (P1, P2, P3, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa (tiếp) P2 yêu cầu thêm 1 đơn vị tài nguyên R2 Trạng thái cung cấp tài nguyên tại thời điểm t1 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 1 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish TF FFF Work (0, 1, 0) 197 / 201
29. P0 có thể kết thúc nhưng hệ thống đang bế tắc. Các tiến trình đang chờ đợi lẫn nhau (P1, P2, P3, P4) Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Ví dụ minh họa (tiếp) P2 yêu cầu thêm 1 đơn vị tài nguyên R2 Trạng thái cung cấp tài nguyên tại thời điểm t1 R0 R1 R2 R0 R1 R2 P0 0 1 0 P0 0 0 0 P1 2 0 0 P1 2 0 2 P2 3 0 3 P2 0 0 1 P3 2 1 1 P3 1 0 0 P4 0 0 2 P4 6 0 2 Allocation Request Thực hiện thuật toán chỉ ra bế tắc Tiến trình P0 P1 P2 P3 P4 Finish TFFF F Work (0, 1, 0) 197 / 201
30. Hủy bỏ tất cả các tiến trình Nhanh chóng hủy bỏ bế tắc Quá tốn kém Các tiến trình bị hủy bỏ có thể gần kết thúc Hủy bỏ lần lượt tiến trình cho tới khi bế tắc không xảy ra Sau khi hủy bỏ, phải kiểm tra xem bế tắc còn tồn tại không Thuật toán kiểm tra bế tắc có độ phức tạp m ∗ n2 Cần chỉ ra thứ tự tiến trình bị hủy bỏ để phá vỡ bế tắc Độ ưu tiên của tiến trình. Tiến trình đã tồn tại bao lâu, còn bao lâu nữa thì kết thúc Tài nguyên tiến trình đang chiếm giữ, còn cần để kết thúc Vấn đề hủy bỏ tiến trình Tiến trình đang cập nhật file ⇒ File không hoàn chỉnh Tiến trình sử dụng máy in ⇒ Reset trạng thái máy in Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Khắc phục bế tắc: Phương pháp kết thúc tiến trình Nguyên tắc: Hủy bỏ các tiến trình đang trong tình trạng bế tắc và lấy lại tài nguyên đã cấp cho tiến trình bị hủy bỏ 198 / 201
31. Vấn đề hủy bỏ tiến trình Tiến trình đang cập nhật file ⇒ File không hoàn chỉnh Tiến trình sử dụng máy in ⇒ Reset trạng thái máy in Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Khắc phục bế tắc: Phương pháp kết thúc tiến trình Nguyên tắc: Hủy bỏ các tiến trình đang trong tình trạng bế tắc và lấy lại tài nguyên đã cấp cho tiến trình bị hủy bỏ Hủy bỏ tất cả các tiến trình Nhanh chóng hủy bỏ bế tắc Quá tốn kém Các tiến trình bị hủy bỏ có thể gần kết thúc Hủy bỏ lần lượt tiến trình cho tới khi bế tắc không xảy ra Sau khi hủy bỏ, phải kiểm tra xem bế tắc còn tồn tại không Thuật toán kiểm tra bế tắc có độ phức tạp m ∗ n2 Cần chỉ ra thứ tự tiến trình bị hủy bỏ để phá vỡ bế tắc Độ ưu tiên của tiến trình. Tiến trình đã tồn tại bao lâu, còn bao lâu nữa thì kết thúc Tài nguyên tiến trình đang chiếm giữ, còn cần để kết thúc 198 / 201
32. 1 Lựa chọn nạn nhân (victime) Tài nguyên nào và tiến trình nào được chọn? Trật tự trưng dụng để chi phí nhỏ nhất? Lượng tài nguyên nắm giữ, thời gian sử dụng 2 Quay lui (Rollback) Quay lui tới một trạng thái an toàn trước đó và bắt đầu lại Yêu cầu lưu giữ thông tin trạng thái của t/trình đang thực hiện 3 Đói tài nguyên (Starvation) Một tiến trình bị trưng dụng quá nhiều lần ⇒chờ đợi vô hạn Giải pháp: ghi lại số lần bị trưng dụng Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Khắc phục bế tắc: Phương pháp trưng dụng tài nguyên Nguyên tắc: Trưng dụng liên tục một vài tài nguyên từ một số tiến trình đang bế tắc cho các tiến trình khác đến khi bế tắc được hủy bỏ Các vấn đề cần quan tâm 199 / 201
33. 3 Đói tài nguyên (Starvation) Một tiến trình bị trưng dụng quá nhiều lần ⇒chờ đợi vô hạn Giải pháp: ghi lại số lần bị trưng dụng Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc 5.6 Nhận biết và khắc phục Khắc phục bế tắc: Phương pháp trưng dụng tài nguyên Nguyên tắc: Trưng dụng liên tục một vài tài nguyên từ một số tiến trình đang bế tắc cho các tiến trình khác đến khi bế tắc được hủy bỏ Các vấn đề cần quan tâm 1 Lựa chọn nạn nhân (victime) Tài nguyên nào và tiến trình nào được chọn? Trật tự trưng dụng để chi phí nhỏ nhất? Lượng tài nguyên nắm giữ, thời gian sử dụng 2 Quay lui (Rollback) Quay lui tới một trạng thái an toàn trước đó và bắt đầu lại Yêu cầu lưu giữ thông tin trạng thái của t/trình đang thực hiện 199 / 201
34. Chương 2: Quản lý tiến trình 5. Bế tắc và xử lý bế tắc Tổng kết Bế tắc là tình trạng 2 hay nhiều tiến trình cùng chờ đợi độc lập một sự kiện chỉ có thể xảy ra bởi sự hoạt động của các tiến trình đang đợi Bế tắc xảy ra khi hội đủ 4 điều kiện Tồn tại tài nguyên găng Phải chờ đợi trước khi vào đoạn găng Không tồn tại hệ thống phân phối lại tài nguyên Tồn tại hiện tượng chờ đợi vòng tròn Để xử lý bế tắc có 3 lớp thuật toán Phòng ngừa bế tắc Tác động vào các điều kiện xảy ra bế tắc Dự báo và phòng tránh Ngăn ngừa hệ thống rơi vào tình trạng có thể dẫn đến bế tắc Nhận biết và khắc phục Cho phép bế tắc xảy ra, chỉ ra bế tắc và khắc phục sau 200 / 201