The wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each resource type. We need a deadlock detection algorithm that is applicable to such a system. The algorithm employs several time-varying data structure that are similar to those used in the banker’s algorithm. Available. A vector of length ? indicates the number of available resources of each type. Allocation: An ? × ? matrix defines the number of resources of each type currently allocated to each thread Request: An ? × ? matrix indicates the current request of each thread. If Request[i][ j] equals ?, then thread ?i is requesting ? more instances of resource type ?j The ≤ relation between two vectors denotes as follows: Let ? and ? be vectors of length ?. We say that ? ≤ ? if and only if ?[?] ≤ ?[?] for all ? = 1,2, . . , ?. For example, if ? = (1,7,3,2) and ? = (0,3,2,1), then ? ≤ ?. In addition, ? < ? if ? ≤ ? and ? ≠ ?. We can treat each row in the matrices ?????????? and ??????? as vectors and refer to them as ??????????? and ????????. The vector ??????????? specifies the resources currently allocated to thread ?i; the vector ???????? specifies the resources requested by thread ?i. This detection algorithm simply investigates every possible allocation sequence for the threads that remain to be completed. The following is the Deadlock Detection algorithm we want to study in this assignment. 1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available. For i = 0, 1, ..., n-1, if Allocation, # 0, then Finish i] = false. Otherwise, Finish|i] = true. 2. Find an index i such that both a. Finishi] == false b. Request; ≤ Work If no such i exists, go to step 4. 3. Work = Work + Allocation; Finish il = true Go to step 2. 4. If Finish[i] == false for some i, 0
The wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each
resource type. We need a deadlock detection
several time-varying data structure that are similar to those used in the banker’s algorithm.
Available. A vector of length ? indicates the number of available resources of each type.
Allocation: An ? × ? matrix defines the number of resources of each type currently allocated to each
thread
Request: An ? × ? matrix indicates the current request of each thread. If Request[i][ j] equals ?, then
thread ?i is requesting ? more instances of resource type ?j
The ≤ relation between two vectors denotes as follows:
Let ? and ? be vectors of length ?. We say that ? ≤ ? if and only if ?[?] ≤ ?[?] for all ? = 1,2, . . , ?. For example,
if ? = (1,7,3,2) and ? = (0,3,2,1), then ? ≤ ?. In addition, ? < ? if ? ≤ ? and ? ≠ ?.
We can treat each row in the matrices ?????????? and ??????? as vectors and refer to them as ???????????
and ????????. The vector ??????????? specifies the resources currently allocated to thread ?i; the vector ????????
specifies the resources requested by thread ?i.
This detection algorithm simply investigates every possible allocation sequence for the threads that remain to be
completed. The following is the Deadlock Detection algorithm we want to study in this assignment.
1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available. For i = 0, 1, ..., n-1, if Allocation, # 0, then Finish i] = false. Otherwise, Finish|i] = true.
2. Find an index i such that both
a. Finishi] == false
b. Request; ≤ Work
If no such i exists, go to step 4.
3. Work = Work + Allocation;
Finish il = true
Go to step 2.
4. If Finish[i] == false for some i, 0 <i < n, then the system is in a deadlocked state. Moreover, if Finish i] == false, then thread T, is deadlocked.
1. Solve the following problem. Consider a system with five threads ?? through ?? and three resource types
A, B, and C. Resource type A has seven instances, resource type B has two instances, and resource type C has
six instances.
?????????? ??????? ?????????
A B C A B C A B C
?0 0 1 0 0 0 0 0 0 0
?1 2 0 0 2 0 2
?2 3 0 3 0 0 0
?3 2 1 1 1 0 0
?4 0 0 2 0 0 2
1) Answer whether the system below is in the deadlock state. If there does not exist a deadlock state, solve the problem using the algorithm presented above and write down the process in detail and find the sequence in which the system works without a deadlock. If there exists a deadlock, write down all the threads, consisting of the deadlock.
2) Suppose now that ?2 makes one additional request for an instance of type C. That is, the ??????? matrix is modified as follows:
???????
A B C
?0 0 0 0
?1 2 0 2
?2 0 0 1
?3 1 0 0
?4 0 0 2
Answer whether the system below is in the deadlock state. If there does not exist a deadlock state, solve
the problem using the algorithm presented above and write down the process in detail and find the
sequence in which the system works without a deadlock. If there exists a deadlock, write down all the
threads, consisting of the deadlock
Trending now
This is a popular solution!
Step by step
Solved in 9 steps
