Bài giảng Hệ điều hành - Chương VI: Deadlock (Khóa chết) - Trần Công Án

Nội dung text: Bài giảng Hệ điều hành - Chương VI: Deadlock (Khóa chết) - Trần Công Án

1. CT107. Hệ Điều Hành Chương 6. Deadlock (Khóa Chết) Giảng viên: Trần Công Án (tcan@cit.ctu.edu.vn) Bộ môn Mạng máy tính & Truyền thông Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ 2014
2. [CT107] Ch6. Deadlock Mục Tiêu I Mô tả tình trạng deadlock của hệ thống – một trạng thái mà các tiến trình không thể tiến triển để hoàn thành các tác vụ của chúng. I Trình bày các phương pháp để ngăn chặn hoặc tránh deadlock; và các biện pháp để phát hiện và phục hồi hệ thống một khi deadlock xảy ra. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 2
3. [CT107] Ch6. Deadlock Nội Dung TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 3
4. [CT107] Ch6. Deadlock Giới thiệu Deadlock Deadlock là gì? Deadlock Là Gì? I Deadlock là một trạng thái của hệ thống trong đó: I một tập hợp các tiến trình đang bị nghẽn I mỗi tiến trình đang giữ một tài nguyên và cũng đang chờ một tài nguyên đang bị giữ bởi một tiến trình khác trong tập các tiến trình đang bị nghẽn. I Ví dụ 1: I Giả sử 1 hệ thống có 2 tiến trình P và Q và F1, F2 là 2 tập tin. I Tiến trình P đang giữ F1 và cần truy xuất thêm F2. I Tiến trình Q đang giữ F2 và cần truy xuất thêm F1. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 4
5. [CT107] Ch6. Deadlock Giới thiệu Deadlock Deadlock là gì? Ví Dụ 2 – Traffic Deadlock 342 Chapter 7 Deadlocks • • • • • • • • • • • • Figure 7.10 Traffic deadlock for Exercise 7.11. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 5 7.14 In Section 7.4.4, we describe a situation in which we prevent deadlock by ensuring that all locks are acquired in a certain order. However, we also point out that deadlock is possible in this situation if two threads simultaneously invoke the transaction() function. Fix the transaction() function to prevent deadlocks. 7.15 Compare the circular-wait scheme with the various deadlock-avoidance schemes (like the banker’s algorithm) with respect to the following issues: a. Runtime overheads b. System throughput 7.16 In a real computer system, neither the resources available nor the demands of processes for resources are consistent over long periods (months). Resources break or are replaced, new processes come and go, and new resources are bought and added to the system. If deadlock is controlled by the banker’s algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances? a. Increase Available (new resources added). b. Decrease Available (resource permanently removed from system). c. Increase Max for one process (the process needs or wants more resources than allowed). d. Decrease Max for one process (the process decides it does not need that many resources).
6. [CT107] Ch6. Deadlock Giới thiệu Deadlock Điều kiện phát sinh deadlock Điều Kiện Phát Sinh Deadlock 1. Loại trừ hỗ tương: ít nhất một tài nguyên được giữ ở chế độ không chia sẻ (nonsharable mode). 2. Giữ và chờ: 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 đang bị giữ bởi tiến trình khác. 3. Không trưng dụng tài nguyên: không trưng dụng tài nguyên cấp phát tiến trình, trừ khi tiến trình tự hoàn trả. 4. Chờ đợi vòng tròn: tồn tại một tập các tiến trình P0, P1, , Pn { } đang chờ đợi như sau: P0 đợi một tài nguyên P1 đang giữ, P1 đợi một tài nguyên P2 đang giữ, . . . , Pn đang đợi một tài nguyên P0 đang giữ. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 6
7. [CT107] Ch6. Deadlock Giới thiệu Deadlock Mô hình hóa hệ thống Mô Hình Hóa Hệ Thống I Hệ thống gồm một tập các loại tài nguyên, kí hiệu R1, R2, , Rm I Ví dụ: CPU cycles, memory space, I/O devices, . . . I Mỗi loại tài nguyên Ri có một tập các thể hiện (instances) Wi I Tiến trình sử dụng tài nguyên theo các bước: 1. Yêu cầu (request) – phải chờ nếu không được đáp ứng ngay. 2. Sử dụng (use) 3. Giải phóng (release) I Các tác vụ yêu cầu và hoàn trả được thực hiện bằng các lời gọi hệ thống. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 7
8. [CT107] Ch6. Deadlock Giới thiệu Deadlock Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên – RAG I Là đồ thị có hướng, với tập đỉnh V và tập cạnh E I Tập đỉnh V gồm 2 loại: I Tập P = P1, P2, , Pn : tập các tiến trình trong hệ thống { } I Tập R = R1, R2, , Rm : tập các tài nguyên của hệ thống { } I Tập cạnh cũng gồm 2 loại: I Cạnh yêu cầu (request edge): có hướng từ Pi đến Rj I Cạnh cấp phát (assignment edge): có hướng từ RJ đến Pi TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 8
9. [CT107] Ch6. Deadlock Giới thiệu Deadlock Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Ký Hiệu Pi I Tiến trình: ● ● ● ● I Loại tài nguyên (với 4 thể hiện): ● ● Pi ● ● Rj I Pi yêu cầu 1 thể hiện của Rj : ● ● Pi ● ● Rj I Pi đang giữ 1 thể hiện của Rj : TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 9
10. [CT107] Ch6. Deadlock Giới thiệu Deadlock Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 1 320 Chapter 7 Deadlocks I Đồ thị cấp phát tài nguyên (không có chu trình và không deadlock): R R 1 3 I P = P1, P2, P3 { } I R = R1, R2, R3, R4 { } I E = P1 R1, P2 R3, R1 P2, { → → → P P P R2 P2, R2 P1, R3 P3 1 2 3 → → → } I Thể hiện của các loại tài nguyên: R1 : 1; R2 : 2; R3 : 1; R4 : 3. I Trạng thái của các tiến trình: I P1: giữ (R2, 1); chờ (R1, 1) R2 I P2: giữ (R1, 1), (R2, 1); chờ (R3, 1) R4 I P3: giữ (R3, 1) TS.Figure Trần 7.1 CôngResource-allocation Án (Khoa CNTT&TT) graph.[CT107] Ch6. Deadlock 10 R = R , R , R , R ◦ { 1 2 3 4} E = P R , P R , R P , R P , R P , R P ◦ { 1 → 1 2 → 3 1 → 2 2 → 2 2 → 1 3 → 3} • Resource instances: One instance of resource type R ◦ 1 Two instances of resource type R ◦ 2 One instance of resource type R ◦ 3 Three instances of resource type R ◦ 4 • Process states: Process P is holding an instance of resource type R and is waiting for ◦ 1 2 an instance of resource type R1. Process P is holding an instance of R and an instance of R and is ◦ 2 1 2 waiting for an instance of R3. Process P is holding an instance of R . ◦ 3 3 Given the definition of a resource-allocation graph, it can be shown that, if the graph contains no cycles, then no process in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist. If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred. Each process involved in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient condition for the existence of deadlock. If each resource type has several instances, then a cycle does not necessarily imply that a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a sufficient condition for the existence of deadlock. To illustrate this concept, we return to the resource-allocation graph depicted in Figure 7.1. Suppose that process P3 requests an instance of resource
11. [CT107] Ch6. Deadlock Giới thiệu Deadlock Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 2 7.2 Deadlock Characterization 321 I Đồ thị cấp phát tài nguyên với chu trình và deadlock: R1 R3 I Trạng thái của các tiến trình: I P1: giữ (R2, 1); chờ (R1, 1) P1 P2 P3 I P2: giữ (R1, 1), (R2, 1); chờ (R3, 1) I P3: giữ (R3, 1); chờ (R2, 1) I 2 chu trình nhỏ nhất (minimal cycles): P1 R1 P2 R3 P3 R2 P1 → → → → → → P2 R3 P3 R2 P2 R2 → → → → I Deadlock: cả 3 tiến trình P1, P2, P3 R4 Figure 7.2 Resource-allocation graph with a deadlock. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 11 type R2.Sincenoresourceinstanceiscurrentlyavailable,weaddarequestedge P3 R2 to the graph (Figure 7.2). At this point, two minimal cycles exist in the system:→ P1 R1 P2 R3 P3 R2 P1 P → R → P → R → P → → 2 → 3 → 3 → 2 → 2 Processes P1, P2,andP3 are deadlocked. Process P2 is waiting for the resource R3,whichisheldbyprocessP3.ProcessP3 is waiting for either process P1 or process P2 to release resource R2.Inaddition,processP1 is waiting for process P2 to release resource R1. Now consider the resource-allocation graph in Figure 7.3. In this example, we also have a cycle: P R P R P 1 → 1 → 3 → 2 → 1 P2 R1 P3 P1 R2 P4 Figure 7.3 Resource-allocation graph with a cycle but no deadlock.
12. 7.2 Deadlock Characterization 321 R1 R3 P1 P2 P3 R2 R4 Figure 7.2 Resource-allocation graph with a deadlock. type R2.Sincenoresourceinstanceiscurrentlyavailable,weaddarequestedge P3 R2 to the graph (Figure 7.2). At this point, two minimal cycles exist in the system:→ P1 R1 P2 R3 P3 R2 P1 P → R → P → R → P → → 2 → 3 → 3 → 2 → 2 Processes P1, P2,andP3 are deadlocked. Process P2 is waiting for the resource R3,whichisheldbyprocess[CT107] Ch6. DeadlockP3.ProcessP3 is waiting for either process P1 or process P2 to release resourceGiới thiệu DeadlockR2.Inaddition,processP1 is waiting for process Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) P2 to release resource R1. Now consider the resource-allocation graph in Figure 7.3. In this example, we also have a cycle:Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 3 P R P R P 1 → 1 → 3 → 2 → 1 I Đồ thị cấp phát tài nguyên có chu trình nhưng không deadlock: P2 R1 P3 I Chu trình: P P1 R1 P3 R2 P1 1 → → → → I Tại sao không deadlock? R2 P4 Figure 7.3 Resource-allocation graph with a cycle but no deadlock. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 12
13. [CT107] Ch6. Deadlock Giới thiệu Deadlock Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG) Đồ Thị Cấp Phát Tài Nguyên & Deadlock I Nếu đồ thị không có chu trình: chắc chắn không có deadlock I Nếu đồ thị có chu trình: I Nếu mỗi loại tài nguyên chỉ có một thể hiện: chắc chắn có deadlock. I Nếu mỗi loại tài nguyên có nhiều thể hiện: có thể có deadlock. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 13
14. [CT107] Ch6. Deadlock Các cách tiếp cận với vấn đề deadlock Các Cách Tiếp Cận Đối Với Vấn Đề Deadlock 1. Đề ra các giao thức để đảm bảo cho hệ thống không bao giờ rơi vào trạng thái deadlock. 2. Cho phép hệ thống rơi vào trạng thái deadlock, sau đó sử dụng các giải thuật để phát hiện deadlock và phục hồi. 3. Không quan tâm và không xử lý vấn đề deadlock trong hệ thống I Khá nhiều hệ điều hành sử dụng phương pháp này. I Tuy nhiên, nếu deadlock không được phát hiện và xử lý sẽ 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. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 14
15. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Ngăn chặn và tránh deadlock I Có hai biện pháp để đảm bảo hệ thống không rơi vào trạng thái deadlock: 1. Ngăn chặn deadlock (deadlock prevention): không cho phép (ít nhất) một trong bốn điều kiện cần cho deadlock xảy ra. 2. Tránh deadlock (deadlock avoidance): các tiến 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. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 15
16. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Ngăn chặn deadlock Ngăn Chặn Deadlock – Điều kiện 1 Ngăn một trong bốn điều kiện cần của deadlock – thắt chặt cách thức yêu cầu tài nguyên của tiến trình. 1. Ngăn Loại trừ hỗ tương (mutual exclusion): I Tài nguyên có thể chia sẻ: không cần thiết. I Tài nguyên không thể chia sẻ: không thể thực hiện được do một số tài nguyên không thể được chia sẻ đồng thời cho nhiều tiến trình. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 16
17. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Ngăn chặn deadlock Ngăn Chặn Deadlock – Điều Kiện 2 2. Ngăn Chờ và giữ (wait & hold): phải đảm bảo khi một tiến trình yêu cầu một tài nguyên, nó không đang giữ một tài nguyên nào khác. I Cách 1: mỗi t/trình yêu cầu toàn bộ tài nguyên cần thiết một lần. I Cách 2: khi yêu cầu tài nguyên, tiến trình không đang giữ bất kỳ tài nguyên nào. Nếu đang giữ thì phải trả lại trước khi yêu cầu. I Ví dụ: xét một tiến trình P copy dữ liệu từ băng từ sang đĩa từ, sau đó sắp xếp dữ liệu trên đĩa từ rồi in kết quả ra máy in. I Cách 1: P → {băng từ, đĩa từ, máy in} ngay khi t/trình bắt đầu. I Cách 2: P → {băng từ, đĩa từ} → P; P → {đĩa từ, máy in} I Khuyết điểm: hiệu suất sử dụng t/nguyên thấp + có thể bị đói t/nguyên TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 17
18. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Ngăn chặn deadlock Ngăn Chặn Deadlock – Điều Kiện 3 3. Ngăn Không trưng dụng (no prermption): nếu một tiến trình A có đang giữ tài nguyên và yêu cầu thêm tài nguyên đang giữ bởi tiến trình khác thì: I Cách 1: hệ thống lấy lại mọi tài nguyên A đang giữ và A sẽ khởi động lại khi cả tài nguyên cũ và mới sẵn sàng cho nó. I Cách 2: hệ thống xem tài nguyên mà A yêu cầu: I Nếu tài nguyên đó đang được giữ bởi một tiến trình B cũng đang đợi thêm tài nguyên, hệ thống sẽ lấy lại tài nguyên của B và cấp phát cho A. I Nếu tài nguyên đó đang được giữ bởi một tiến trình không đang đợi thêm tài nguyên thì A phải đợi (⇒ tài nguyên của A đang giữ sẽ bị thu hồi nếu có tiến trình khác cần – trường hợp 1). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 18
19. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Ngăn chặn deadlock Ngăn Chặn Deadlock – Điều Kiện 4 4. Ngăn Chờ đợi vòng tròn (circular wait): I Mỗi tài nguyên sẽ được gán một thứ tự toàn cục. I Các tiến trình khi yêu cầu tài nguyên phải theo đúng thứ tự. I Thông thường, một hàm one-to-one được định nghĩa để thực hiện gán thứ tự toàn cục: F : R N; với R là tập các tài nguyên. → I Một tiến trình đầu tiên có thể yêu cầu bất kỳ tài nguyên Ri nào. I Sau đó, một yêu cầu tài nguyên Rj chỉ được đáp ứng nếu F (Rj ) > F (Ri ), hoặc nó phải trả lại tài nguyên Ri trước khi xin tài nguyên Rj . TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 19
20. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Tránh Deadlock I Cách tiếp cận tránh deadlock cho phép sử dụng tài nguyên hiệu quả hơn ngăn chặn deadlock, bằng cách: I 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. I 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 trạng thái deadlock. I Trạng thái cấp phát tài nguyên được định nghĩa bởi số lượng 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. I Các giải thuật: giải thuật Đồ thị cấp phát tài nguyên và giải thuật Banker. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 20
21. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Trạng Thái An Toàn (Safe State) I Một hệ thống ở trạng thái an toàn nếu tồn tại một chuỗi an toàn. I Một chuỗi tiến trình P1, P2, , Pn là một chuỗi an toàn nếu: h i I Với mọi Pi , i = 1 n, mọi yêu cầu về tài nguyên của Pi có thể được thỏa mãn bởi các tài nguyên đang sẵn sàng hoặc các tài nguyên đang bị giữ bởi Pj , với j < i (! ngăn chờ đợi vòng tròn). I Một hệ thống ở trạng thái không an toàn nếu không tồn tại chuỗi an toàn. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 21
22. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Ví Dụ Về Chuỗi An Toàn I Cho một hệ thống có 12 băng từ và 3 tiến trình P0, P1, P2. I Trạng thái và nhu cầu sử dụng tài nguyên của 3 tiến trình tại thời điểm t0 được cho trong bảng sau: 7.5 Deadlock Avoidance 329 Maximum Needs Current Needs P0 10 5 P1 42 P2 92 I ChuỗiAt timeP1t,0,thesystemisinasafestate.ThesequenceP0, P2 là chuỗi an toàn hệ thống an toàn satisfies the safetyh condition.i Process P1 can immediately⇒ be allocated all its tape drives IandGiả then sử tại return thời them điểm (thet1, P system2 yêu cầu will và then được have cấp five phát available 1 băng tape từ drives);hệ ⇒ thenthống process cònP 20 băngcan get từ all sẵn its sàng tape drives và hệand thống return trở nên them không (the system an toàn will. (?) then have ten available tape drives); and finally process P2 can get all its tape drives and return them (the system will then have all twelve tape drives available). TS. Trần CôngAsystemcangofromasafestatetoanunsafestate.Supposethat,attime Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 22 t1,processP2 requests and is allocated one more tape drive. The system is no longer in a safe state. At this point, only process P1 can be allocated all its tape drives. When it returns them, the system will have only four available tape drives. Since process P0 is allocated five tape drives but has a maximum of ten, it may request five more tape drives. If it does so, it will have to wait, because they are unavailable. Similarly, process P2 may request six additional tape drives and have to wait, resulting in a deadlock. Our mistake was in granting the request from process P2 for one more tape drive. If we had made P2 wait until either of the other processes had finished and released its resources, then we could have avoided the deadlock. Given the concept of a safe state, we can define avoidance algorithms that ensure that the system will never deadlock. The idea is simply to ensure that the system will always remain in a safe state. Initially, the system is in a safe state. Whenever a process requests a resource that is currently available, the system must decide whether the resource can be allocated immediately or whether the process must wait. The request is granted only if the allocation leaves the system in a safe state. In this scheme, if a process requests a resource that is currently available, it may still have to wait. Thus, resource utilization may be lower than it would otherwise be. 7.5.2 Resource-Allocation-Graph Algorithm If we have a resource-allocation system with only one instance of each resource type, we can use a variant of the resource-allocation graph defined in Section 7.2.2 for deadlock avoidance. In addition to the request and assignment edges already described, we introduce a new type of edge, called a claim edge. AclaimedgePi Rj indicates that process Pi may request resource Rj at some time in the future.→ This edge resembles a request edge in direction but is represented in the graph by a dashed line. When process Pi requests resource Rj ,theclaimedgePi Rj is converted to a request edge. Similarly, when a resource R is released→ by P ,theassignmentedgeR P is reconverted to a j i j → i claim edge Pi Rj . Note that→ the resources must be claimed a priori in the system. That is, before process Pi starts executing, all its claim edges must already appear in the resource-allocation graph. We can relax this condition by allowing a claim edge P R to be added to the graph only if all the edges associated with i → j process Pi are claim edges.
23. 328 Chapter 7 Deadlocks algorithm that ensures that the system will never enter a deadlocked state. A deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that a circular-wait condition can never exist. The resource- allocation state is defined by the number of available and allocated resources and the maximum demands of the processes. In the following sections, we explore two deadlock-avoidance algorithms. 7.5.1 Safe State Astateissafe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe sequence.Asequenceofprocesses is a safe sequence for the current allocation state if, for each Pi ,theresourcerequeststhatPi can still make can be satisfied by the currently available resources plus the resources held by all Pj ,withj < i. In this situation, if the resources that Pi needs are not immediately available, then Pi can wait until all Pj have finished. When they have finished, Pi can obtain all of its needed resources, complete its designated task, return its allocated resources, and terminate. When Pi terminates, Pi 1 can obtain its needed resources, and so on. If no such sequence exists, then the+ system state is said to be unsafe. Asafestateisnotadeadlockedstate.Conversely,adeadlockedstateis an unsafe state. Not all unsafe states are deadlocks, however (Figure 7.6). [CT107] Ch6. Deadlock An unsafe state may lead to a deadlock. As long as the state is safe, the Ngăn chặn và tránh deadlock operating system can avoid unsafe (and deadlocked) states. In an unsafe state, Tránh deadlock the operating system cannot prevent processes from requesting resources in such a way that a deadlock occurs. The behavior of the processes controls unsafe states. Trạng Thái An Toàn VàTo illustrate, Deadlock we consider a system with twelve magnetic tape drives and three processes: P0, P1,andP2.ProcessP0 requires ten tape drives, process P1 may need as many as four tape drives, and process P2 may need up to nine tape drives. Suppose that, at time t0,processP0 is holding five tape drives, process I Nếu hệ thống đang trong trạngP1 is thái holding an two toàn tape drives,không anddeadlock process P2 is. holding two tape drives. (Thus, there are three free tape⇒ drives.) I Nếu hệ thống đang ở trạng thái không an toàn có thể có deadlock. ⇒ I Ý tưởng cho giải pháp tránh deadlock: unsafe đảm bảo hệ thống không rơi vào trạng thái deadlock không an toàn bằng cách: safe I Khi một tiến trình yêu cầu một tài nguyên đang sẵn sàng, hệ thống sẽ kiểm tra nếu việc cấp phát không dẫn đến trạng thái không an toàn thì sẽ cấp phát ngay. Figure 7.6 Safe, unsafe, and deadlocked state spaces. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 23
24. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Đồ Thị Cấp Phát Tài Nguyên I Được áp dụng cho hệ thống chỉ có 1 thể hiện cho mỗi loại tài nguyên. I Bổ sung thêm 1 loại cạnh, “cạnh dự định” yêu cầu, Pi Rj : Pi có thể → yêu cầu Rj , được330 biểuChapter diễn bằng 7 Deadlocks đường ngắt khúc trên đồ thị. I Việc yêu cầu tài nguyên phải được dự tính R1 trước trong hệ thống các cạnh dự định phải xuất hiện sẵn trong⇒ đồ thị. P1 P2 R2 Figure 7.7 Resource-allocation graph for deadlock avoidance. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 24 Now suppose that process Pi requests resource Rj .Therequestcanbe granted only if converting the request edge P R to an assignment edge i → j Rj Pi does not result in the formation of a cycle in the resource-allocation graph.→ We check for safety by using a cycle-detection algorithm. An algorithm for detecting a cycle in this graph requires an order of n2 operations, where n is the number of processes in the system. If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is found, then the allocation will put the system in an unsafe state. In that case, process Pi will have to wait for its requests to be satisfied. To illustrate this algorithm, we consider the resource-allocation graph of Figure 7.7. Suppose that P2 requests R2.AlthoughR2 is currently free, we cannot allocate it to P2, since this action will create a cycle in the graph (Figure 7.8). A cycle, as mentioned, indicates that the system is in an unsafe state. If P1 requests R2,andP2 requests R1,thenadeadlockwilloccur. 7.5.3 Banker’s Algorithm The resource-allocation-graph algorithm is not applicable to a resource- allocation system with multiple instances of each resource type. The deadlock- avoidance algorithm that we describe next is applicable to such a system but is less efficient than the resource-allocation graph scheme. This algorithm is commonly known as the banker’s algorithm. The name was chosen because the algorithm could be used in a banking system to ensure that the bank never R1 P1 P2 R2 Figure 7.8 An unsafe state in a resource-allocation graph.
25. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Đồ Thị Cấp Phát Tài Nguyên I Sự chuyển đổi của các cạnh trong đồ thị: I Khi tiến trình yêu cầu tài nguyên: cạnh dự định cạnh yêu cầu. → I Khi tài nguyên được cấp phát: cạnh yêu cầu cạnh cấp phát . → I Khi tài nguyên được giải phóng: cạnh cấp phát cạnh dự định yêu cầu. → I Nguyên tắc cấp phát tài nguyên: một yêu cầu tài nguyên Rj của tiến trình Pi chỉ được cấp phát khi việc chuyển từ Pi Rj (cạnh yêu → cầu) sang Rj Pi (cạnh cấp phát) không tạo thành chu trình trong đồ thị cấp phát→ tài nguyên. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 25
26. 330 Chapter 7 Deadlocks R1 P1 P2 R2 Figure 7.7 Resource-allocation graph for deadlock avoidance. Now suppose that process Pi requests resource Rj .Therequestcanbe granted only if converting the request edge P R to an assignment edge i → j Rj Pi does not result in the formation of a cycle in the resource-allocation graph.→ We check for safety by using a cycle-detection algorithm. An algorithm for detecting a cycle in this graph requires an order of n2 operations, where n is the number of processes in the system. If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is found, then the allocation will put the system in an unsafe state. In that case, process Pi will have to wait for its requests to be satisfied. To illustrate this algorithm, we consider the resource-allocation graph of Figure 7.7. Suppose that P2 requests R2.AlthoughR2 is currently free, we cannot allocate it to P2, since this action will create a cycle in the graph (Figure 7.8). A cycle, as mentioned, indicates that the system is in an unsafe state. If P1 requests R2,andP2 requests R1,thenadeadlockwilloccur. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock7.5.3 Banker’s Algorithm Tránh deadlock The resource-allocation-graph algorithm is not applicable to a resource- Giải Thuậtallocation Đồ Thị system Cấp with Phát multiple Tài instances Nguyên of each resource type. The deadlock- avoidance algorithm that we describe next is applicable to such a system but is less efficient than the resource-allocation graph scheme. This algorithm is I Ví dụ: Yêu cầucommonly tài nguyên known của P2 asđối the vớibanker’sR2 sẽ không algorithm. được cấpThe phát name – was chosen because mặc dù R2 đangthe algorithm sẵn dùng – could vì nó becóused thể tạo in ra a banking chu trình system (nếu sau to đó ensure that the bank never 330 Chapter 7 Deadlocks P1 lại yêu cầu R2) có thể dẫn đến deadlock. ⇒ R1 R1 P2 requests R2 P1 P2 P1 P2 −−−−−−−−−→ R2 R2 Figure 7.7 TS.Resource-allocation Trần Công Án (Khoa CNTT&TT) graph for deadlock[CT107]Figure Ch6. avoidance. 7.8 DeadlockAn unsafe state in a resource-allocation26 graph. Now suppose that process Pi requests resource Rj .Therequestcanbe granted only if converting the request edge P R to an assignment edge i → j Rj Pi does not result in the formation of a cycle in the resource-allocation graph.→ We check for safety by using a cycle-detection algorithm. An algorithm for detecting a cycle in this graph requires an order of n2 operations, where n is the number of processes in the system. If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is found, then the allocation will put the system in an unsafe state. In that case, process Pi will have to wait for its requests to be satisfied. To illustrate this algorithm, we consider the resource-allocation graph of Figure 7.7. Suppose that P2 requests R2.AlthoughR2 is currently free, we cannot allocate it to P2, since this action will create a cycle in the graph (Figure 7.8). A cycle, as mentioned, indicates that the system is in an unsafe state. If P1 requests R2,andP2 requests R1,thenadeadlockwilloccur. 7.5.3 Banker’s Algorithm The resource-allocation-graph algorithm is not applicable to a resource- allocation system with multiple instances of each resource type. The deadlock- avoidance algorithm that we describe next is applicable to such a system but is less efficient than the resource-allocation graph scheme. This algorithm is commonly known as the banker’s algorithm. The name was chosen because the algorithm could be used in a banking system to ensure that the bank never R1 P1 P2 R2 Figure 7.8 An unsafe state in a resource-allocation graph.
27. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Banker I Áp dụng cho hệ thống có nhiều thể hiện cho mỗi loại tài nguyên. I Dựa trên ý tưởng của các nghiệp vụ ngân hàng. I Điều kiện: I Mỗi tiến trình phải khai báo số lượng thể hiện tối đa của mỗi loại tài nguyên mà nó cần. I Khi tiến trình yêu cầu tài nguyên thì nó có thể phải đợi (ngay cả khi tài nguyên được yêu cầu đang sẵn sàng). I Khi một tiến trình đã có được đầy đủ tài nguyên thì phải hoàn trả không một khoảng thời gian hữu hạn. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 27
28. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Banker – Cấu Trúc Dữ Liệu Cho n = số lượng tiến trình, m = số lượng các loại tài nguyên, P: tập các tiến trình, R: tập các loại tài nguyên. I Avaiable: vector có chiều dài m. Available[j] = k có k thể hiện của Rj đang sẵn sàng. ⇒ I Max: ma trận n m. × Max[i, j] = k tiến trình Pi yêu cầu tối đa k thể hiện của Rj . ⇒ I Allocation: ma trận n m. × Allocation[i, j] = k Pi đã được cấp phát k thể hiện của Rj . ⇒ I Need: ma trận n m. × Need[i, j] = k Pi có thể yêu cầu thêm k thể hiện của Rj . ⇒ (Need[i, j] = Max[i, j] Allocation[i, j]) − TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 28
29. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Banker – Tìm Chuỗi An Toàn 1. Cho Work và Finish là hai vector độ dài là m và n. Khởi tạo: Work = Available Finish[i] = false, for i = 0 (n 1) − 2. Tìm i thỏa hai điều kiện: a. Finish[i] = false Cho hai vector X, Y có độ dài n: b. Need[i] Work X Y X [i] Y [i], i = 1 n ≤ ≤ ⇔ ≤ ∀ Nếu không tồn tại i thỏa điều kiện, nhảy đến bước 4. 3. Work = Work + Allocation[i] Finish[i] = true Quay lại bước 2. 4. Nếu Finish[i] == true với mọi i thì hệ thống ở trạng thái an toàn. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 29
30. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Banker – Cấp Phát Tài Nguyên I Cho Requesti là vector yêu cầu của tiến trình Pi . Requesti [j] = k tiến trình Pi cần k thể hiện của Rj . ⇔ I Khi một tiến trình Pi yêu cầu tài nguyên, thực hiện các bước sau: 1. Nếu Requesti Needi , sang bước 2. Ngược lại, báo≤ lỗi vì tiến trình yêu cầu quá định mức tối đa. 2. Nếu Requesti Available, sang bước 3. ≤ Ngược lại, Pi phải chờ vì hiện không đủ tài nguyên để cấp phát. 3. (next slide) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 30
31. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Banker – Cấp Phát Tài Nguyên 3. Giả định cấp phát tài nguyên cho Pi bằng cách cập nhật trạng thái của hệ thống như sau: Available = Available Requesti − Allocationi = Allocationi + Requesti Needi = Needi Requesti − Áp dụng giải thuật kiểm tra trạng thái an toàn cho trạng thái trên: I Nếu hệ thống an toàn: cấp tài nguyên cho Pi . I Ngược lại, Pi phải đợi và phục hồi lại trạng thái của hệ thống (i.e. nghịch đảo lại các cập nhật giả định bên trên). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 31
32. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Banker – Ví Dụ I Cho một hệ thống có: I 5 tiến trình P0, , P4. I 3 loại tài nguyên: A (10 thể hiện), B (5 thể hiện), C (7 thể hiện). I Trạng thái cấp phát tài nguyên tại thời điểm T0: Allocaon Max Available Need A B C A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 7 4 3 P 2 0 0 3 2 2 1 2 2 1 ⇒ P2 3 0 2 9 0 2 6 0 0 P3 2 1 1 2 2 2 0 1 1 safe?? P4 0 0 2 4 3 3 4 3 1 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 32
33. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Banker – Ví Dụ I Dùng giải thuật Banker để k/tra tính an toàn của hệ thống tại T0: Allocaon Need Work A B C A B C i A B C P0 0 1 0 7 4 3 3 3 2 Banker P1 2 0 0 1 2 2 1 5 3 2 P2 3 0 2 6 0 0 3 7 4 3 P3 2 1 1 0 1 1 4 7 4 5 P4 0 0 2 4 3 1 2 10 4 7 0 10 5 7 I Tồn tại chuỗi an toàn: P1, P3, P4, P2, P0 hệ thống an toàn. h i ⇒ TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 33
34. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Banker – Ví Dụ I G/sử tại thời điểm T1, P1 yêu cầu (1, 0, 2). Yêu cầu có được đáp ứng? 1. (Request1 Available) = true vì (1, 0, 2) (3, 3, 2) ≤ ≤ 2. Trạng thái giả định tồn tại chuỗi an toàn P1, P3, P0, P2, P4 hệ thống ở trạng thái an toàn cấp phát ngayh lập tức. i ⇒ ⇒ Allocaon Need Work A B C A B C i A B C P0 0 1 0 7 4 3 2 3 0 Banker P1 3 0 2 0 2 0 1 5 3 2 P2 3 0 2 6 0 0 3 7 4 3 P3 2 1 1 0 1 1 0 7 5 3 P4 0 0 2 4 3 1 2 10 5 5 Available = (2, 3, 0) 4 10 5 7 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 34
35. [CT107] Ch6. Deadlock Ngăn chặn và tránh deadlock Tránh deadlock Giải Thuật Banker – Bài Tập 1. Yêu cầu (3, 3, 0) của P4 có được đáp ứng không? 2. Yêu cầu (0, 2, 0) của P0 có được đáp ứng không? TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 35
36. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phát hiện deadlock Phát Hiện Deadlock I Trong cách tiếp cận “phát hiện và phục hồi” đối với vấn đề deadlock: I Chấp nhận cho deaclock xảy ra trong hệ thống. I Sử dụng các giải thuật để phát hiện deadlock. I Nếu có deadlock thì sẽ tiến hành phục hồi hệ thống, dùng 1 sơ đồ phục hồi thích hợp. I Các giải thuật phát hiện deadlock thường sử dụng RAG. I Có 2 loại giải thuật: I Cho trường hợp mỗi loại tài nguyên chỉ có 1 thể hiện. I Cho trường hợp mỗi loại tài nguyên có nhiều thể hiện. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 36
37. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phát hiện deadlock Mỗi Loại Tài Nguyên Chỉ Có 1 Thể Hiện I Sử dụng 1 biến thể của RAG – đồ thị wait-for: I Các nút: là các tiến trình. I Các cạnh: Pi Pj nếu Pi đang đợi Pj . → I Deadlock tồn tại trong hệ thống nếu và chỉ nếu đồ thị wait-for tồn tại chu trình. I Giải thuật xây dựng đồ thị wait-for và tìm kiếm chu trình sẽ được thực hiện định kỳ trong hệ thống. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 37
38. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phát hiện deadlock Đồ Thị Cấp Phát Tài Nguyên & Wait-for 334 Chapter 7 Deadlocks 334I MộtChapter đồ thị 7 CấpDeadlocks phát tài nguyên và đồ thị Wait-for tương ứng: P5 P5 R1 R3 R4 R1 R3 R4 P5 P5 P1 P2 P3 P1 P2 P3 P1 P2 P3 P1 P2 P3 P4 P4 P4 R2 R5 P4 R2 (a) R5 (b) (a) (b) Figure 7.9 (a) Resource-allocation graph. (b) Corresponding wait-for graph. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 38 Figure 7.9 (a) Resource-allocation graph. (b) Corresponding wait-for graph. In the following discussion, we elaborate on these two requirements as they pertainIn the to following systems with discussion, only a single we elaborate instance of on each these resource two requirements type, as well as to they systemspertain with to systems several instances with only of asingle each resource instance type. of each At resourcethis point, type, however, as well we as to notesystems that a detection-and-recovery with several instances of scheme each resourcerequires type. overhead At this that point, includes however, not we onlynote the that run-time a detection-and-recovery costs of maintaining scheme the necessaryrequires information overhead andthat executing includes not theonly detection the run-time algorithm costs but of also maintaining the potential thenecessary losses inherent information in recovering and executing from adeadlock.the detection algorithm but also the potential losses inherent in recovering from adeadlock. 7.6.1 Single Instance of Each Resource Type 7.6.1 Single Instance of Each Resource Type If all resources have only a single instance, then we can define a deadlock- detectionIf all resources algorithm have that onlyuses a variant single instance, of the resource-allocation then we can define graph, a deadlock- called a wait-fordetectiongraph. algorithm We obtain that uses this a graph variant from of the the resource-allocation resource-allocation graph, graph called by removinga wait-for thegraph. resource We nodes obtain and this collapsing graph from the the appropriate resource-allocation edges. graph by removingMore precisely, the resource an edge nodes from andPi collapsingto Pj in a the wait-for appropriate graph edges. implies that processMorePi is waiting precisely, for an process edgeP fromj to releasePi to P aj resourcein a wait-for that Pi graphneeds. implies An edge that P processP existsP isin waiting a wait-for for process graphP if andto release only if a resourcethe corresponding that P needs. resource- An edge i → j i j i allocationP P graphexists contains in a wait-for two edges graphP ifi andRq onlyand ifRq the correspondingPj for some resource resource- i → j → → Rq .InFigure7.9,wepresentaresource-allocationgraphandthecorrespondingallocation graph contains two edges P R and R P for some resource i → q q → j wait-forRq .InFigure7.9,wepresentaresource-allocationgraphandthecorresponding graph. wait-forAs before, graph. a deadlock exists in the system if and only if the wait-for graph containsAs a before, cycle. To a deadlock detect deadlocks, exists in the the system system if needs and only to maintain if the wait-forthe wait- graph forcontains graph and a cycle. periodically To detectinvoke deadlocks, an algorithm the systemthat needs searches to maintain for a cyclethe wait- in thefor graph. graph An and algorithm periodically to detectinvoke a cycle an algorithm in a graphthat requires searches an order for a cycleof n2 in operations,the graph. where An algorithmn is the number to detect of vertices a cycle in in the a graph graph. requires an order of n2 operations, where n is the number of vertices in the graph. 7.6.2 Several Instances of a Resource Type 7.6.2 Several Instances of a Resource Type The wait-for graph scheme is not applicable to a resource-allocation system withThe multiple wait-for instances graph scheme of each is resource not applicable type. We to a turn resource-allocation now to a deadlock- system with multiple instances of each resource type. We turn now to a deadlock-
39. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phát hiện deadlock Mỗi Loại Tài Nguyên Có Nhiều Thể Hiện I Cấu trúc dữ liệu của giải thuật: I Available: vector có chiều dài m Số thể hiện còn sẵn dùng của mỗi loại tài nguyên. I Allocation: ma trận n m Số thể hiện đã cấp phát× cho mỗi tiến trình. I Request: ma trận n m Yêu cầu tài nguyên× hiện tại của các tiến trình. Nếu Request[i, j] = k, Pi đang yêu cầu thêm k thể hiện của Rj . TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 39
40. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phát hiện deadlock Mỗi Loại Tài Nguyên Có Nhiều Thể Hiện I Giải thuật phát hiện deadlock bao gồm 4 bước: 1. Cho Work và Finish là 2 vector kích thước tương ứng là m và n. Khởi tạo: a. Work = Available b. for i = 0, 1, , (n − 1) if Allocation[i] 6= 0 then Finish[i] = false else Finish[i] = true 2. (next slide) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 40
41. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phát hiện deadlock Mỗi Loại Tài Nguyên Có Nhiều Thể Hiện 2. Tìm i [0, n 1] thỏa mãn hai điều kiện sau: ∈ − a. Finish[i] = false b. Request[i] ≤ Work Nếu không tồn tại, nhảy đến bước 4. 3. Work = Work + Allocation[i] Finish[i] = true Quay về bước 2. 4. Nếu tồn tại i với Finish[i] = false: I Hệ thống đang ở trạng thái deadlock. I Nếu Finish[i] = false ⇒ Pi đang bị deadlock. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 41
42. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phát hiện deadlock Mỗi Loại Tài Nguyên Có Nhiều Thể Hiện I Ví dụ 1: Cho hệ thống có I 5 tiến trình P0, , P4 I 3 loại tài nguyên: A (7 thể hiện), B (2 thể hiện), C (6 thể hiện) I Hiện trạng của hệ thống tại T0: Allocaon Request I Thực hiện giải thuật, ta tìm được A B C A B C chuỗi P0, P2, P1, P3, P4 sẽ dẫn đến h i P0 0 1 0 0 0 0 Finish[i] = true với mọi i = 0 4 P 2 0 0 2 0 2 1 hệ thống không deadlock tại T0. ⇒ P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Available = (0, 0, 0) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 42
43. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phát hiện deadlock Mỗi Loại Tài Nguyên Có Nhiều Thể Hiện I Ví dụ 2: Giả sử giữa thời điểm T0 và T1, P2 yêu cầu thêm một thể hiện của tài nguyên loại C. Trạng thái của hệ thống tại T1 là gì? I Hiện trạng của hệ thống tại T1: Allocaon Request I Chạy giải thuật p/hiện deadlock: A B C A B C I Finish[0] = true P0 0 1 0 0 0 0 I Finish[1 4] = false P1 2 0 0 2 0 2 Hệ thống deadlock P 3 0 3 0 0 1 ⇒ 2 (P1, P2, P3, P4) P3 2 1 1 1 0 0 I Nhận xét: tài nguyên thu hồi từ P0 P4 0 0 2 0 0 2 vẫn không đủ đáp ứng cho các Available = (0, 0, 0) t/trình khác. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 43
44. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phát hiện deadlock Sử Dụng Giải Thuật Phát Hiện Deadlock I Khi nào/Tần suất thực hiện phát hiện deadlock phụ thuộc vào: 1. Deadlock có thường xảy ra không? 2. Có nhiều tiến trình tham gia vào deadlock hay không? I Nếu kiểm tra deadlock thường xuyên trong hệ thống ít deadlock sẽ làm hao phí tài nguyên (CPU) của hệ thống. I Tuy nhiên, nếu thực hiện phát hiện deadlock với tần suất thấp: I Nếu deadlock diễn ra thường xuyên: nhiều chu trình trong đồ thị không biết chính xác tiến trình nào gây ra deadlock. ⇒ I Nếu có nhiều tiến trình tham gia vào deadlock: hiệu suất sử dụng tài nguyên hệ thống giảm. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 44
45. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phục hồi deadlock Phục Hồi Deadlock I Các giải pháp để phục hồi deadlock: 1. Bằng tay (manual): người sử dụng/điều hành sẽ giải quyết 2. Phục hồi tự động bằng cách “phá” deadlock, có 2 giải pháp: I Ngưng tiến trình: ngưng (terminate) 1 hoặc một vài tiến trình tham gia vào deadlock. I Lấy lại tài nguyên: trưng dụng 1 hoặc một vài tài nguyên của các tiến trình bị deadlock. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 45
46. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phục hồi deadlock Ngưng Tiến Trình 1. Ngưng tất cả các tiến trình bị deadlock: I Chi phí lớn, đặc biệt khi ngưng các tiến trình “già” 2. Ngưng lần lượt từng tiến trình cho đến khi không còn deadlock: I Kết hợp với giải thuật phát hiện deadlock phải xét đến chi phí. ⇒ I Các yếu tố chọn tiến trình cần ngưng: I Độ ưu tiên I Thời gian thực thi, thời gian còn lại I Loại tài nguyên tiến trình đang sử dụng I Tài nguyên cần thêm I Số lượng tiến trình sẽ bị ngưng I Loại tiến trình TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 46
47. [CT107] Ch6. Deadlock Phát hiện và phục hồi deadlock Phục hồi deadlock Lấy Lại Tài Nguyên I Lần lượt lấy lại tài nguyên của các tiến trình, cấp phát cho tiến trình khác cho đến khi không còn deadlock. I Các vấn đề khi thu hồi tài nguyên: I Chọn “nạn nhân”: chọn tài nguyên và tiến trình cần thu hồi (dựa trên số tài nguyên sở hữu, thời gian đã thực thi, . . . ) I Cuộn lại (rollback): I cuộn lại đến một trạng thái an toàn, khởi động lại từ vị trí đó I đòi hỏi hệ thống phải lưu lại thông tin về trạng thái của các tiến trình đang thực thi. I Đói tài nguyên: tránh trình trạng một tiến trình luôn bị chọn làm nạn nhân. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 47
48. [CT107] Ch6. Deadlock Tổng kết Tổng Kết I Dealock: là trạng thái các tiến trình chờ vòng tròn lẫn nhau, không thể tiến triển. I Đồ thị cấp phát tài nguyên: mô hình trạng thái cấp phát, sử dụng tài nguyên của các tiến trình trong hệ thống. I Có 2 cách tiếp cận đối với vấn đề deadlock: I Ngăn chặn và tránh deadlock: đảm bảo trạng thái deadlock không bao giờ xảy ra. I Phát hiện và khôi phục deadlock: cho phép deadlock xảy ra, dùng giải thuật kiểm tra trạng thái deadlock theo định kỳ và thực hiện khôi phục deadlock nếu có. I Các giải thuật ngăn chặn, tránh và phát hiện deadlock cơ bản dựa vào đồ thị cấp phát tài nguyên. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch6. Deadlock 48