Deadlock 2: Deadlock Avoidance with the Banker's Algorithm

if we disallow one of the three conditions that make that lock possible then that will prevent deadlock from ever occurring so if mutual exclusion no preemption or hold in white is simply not possible then we'll never have deadlock however it's useful to have those features it generally makes code more efficient and easier to write so another way to assure that deadlock does not occur is to avoid it which means that we do not allow a circular wait condition to arise though effective this approach requires some extra information that you may not always have specifically the operating system has to know what the future resource requests of each process in the system will be specifically we assume we have the following information R is a resource vector and this tells us the total amount of each type of resource that the system has available V is the available vector this is the amount of each type of resource that is currently available in the system we also require C which is a claim matrix the entries in this matrix indicate how much of a given resource type each process will need at some point lastly we have a which is an allocation matrix this is the amount of each type of resource currently possessed by each process if we have all of this information then we can apply an algorithm called the bankers algorithm in order to determine if it's possible to run all of our processes to completion without deadlock occurring and if so what order we should run them in to demonstrate this right out an example of values for each of these variables and we'll see how the bankers algorithm can find a path to execute the processes in I've written out the state of a system in the middle of execution so we have three types of resources in this system this is the resource vector R and these could be things like units of memory file handles interrupt channels semaphore value the point is we have three types and four resource type one we have six units overall eight units of resource type two and seven units of resource type three now this is the claim matrix C and here are four processes so when these processes enter the system they had to state to the system in advance this is the total number of each of these resource types that I need to hold in order to complete my computation so at some point between starting and finishing process one will need to simultaneously hold four units of resource one five units of resource two and three units of resource three it doesn't necessarily need all of this throughout the entirety of computation it just needs to have them at some point during its computation and we also have similar information for the other processes now this matrix is the allocation matrix so this is going to constantly change as the processes execute this information is fixed for each process in is the system and this resource vector is simply fixed for the system but the allocation matrix says for example that process one currently has two units of resource type 1 2 units of resore type two and zero units of resource type three so something that will be important in determining which process to execute first is seeing how many more units of each resource type can be claimed by a process so this process currently has two units of resource type 1 but it eventually needs for now something that I haven't drawn yet is the available vector so this vector V represents the units of each resource type that are currently unclaimed in the system and we can actually compute this based off of r and a all we do is add up all of the values in a given column here to find out how many units of that resource are currently allocated and then we subtract that from the resource vector which is the total amount of that resource in the system so for resource type 1 there are 1 2 3 4 5 6 units currently claimed out of a total of 6 so 6 minus 6 is 0 meaning 0 units of resource type 1 are currently available in the system a resource 2 we have 1 2 3 4 5 allocated units out of a total of 8 so 8 minus 5 means there are 3 units of resource type to left to be claimed for 3 we have 1 2 3 4 5 units that are allocated out of 7 7 minus 5 is 2 and so now we have our available vector there are zero units of resource type 1 available 3 of type 2 and 2 of type 3 the next thing we need to compute is called the need matrix the need matrix is simply the matrix C minus the matrix a so to compute this first row we would do 4 minus 2 is 2 5 minus 2 is 3 and 3 minus 0 is 3 and you can fill the rest out on your own to get the following and having computed this need matrix we can determine whether it's possible to execute a process and avoid deadlock by comparing the rows in the need matrix to the available vector specifically if the amount of each resource type that is needed for a given process is less than or equal to the corresponding available values of each resource then that particular resource can be safely run to completion additionally if we can find a way to execute all of these processes and sequence assuming that every completed process returns its claimed resources to the system then that means we can execute all the processes and avoid deadlock so first we'll consider Row 1 for process 1 process 1 still needs two units of resource 1 to finish there are 0 units of resource 1 available therefore we cannot execute process 1 it might run for a few steps if we attempted to execute it but eventually it would attempt to claim those resources which would be potentially to deadlock so we're going to avoid that and consider other processes process 2 requires 0 units of resource 1 which is good because there's none available and requires 0 units of resource 2 which is less than three that are available but it requires three units of resource type three and we do not have that many available therefore it is not safe to run this process either because when it attempts to claim that third unit of resource type three it will block potentially leading to deadlock now Row 3 only requires zero one and zero units of resource types one two and three respectively and zero is less than or equal to zero one is less than or equal to 3 and zero is less than equal to 2 therefore it is safe to run process 3 to completion and you can confirm on your own that it is not safe to run process 4 so it is not always the case that there will only be one viable option but in this particular example the one and only option that is safe to run is process 3 so if we run process 3 to completion then it will be eliminated from our calculations and importantly all of its allocated resources will be returned to the system here so the new available vector would be 0 plus 1 is 1 3 plus 1 is 4 and 2 plus 3 is 5 so with more resources available we are now able to run certain processes that we did not have enough resources to safely run before for example it is now safe to run process 4 because 1 is less than equal to 1 and these zeros are clearly less than 4 and 5 so we will run process four to completion and that will mean that its resources are reclaimed leading to the following available vector given this available vector and you two processes left to run the only one that is safe to run is process two since three is less than seven and zeros or less than these values so let's run it to completion and reclaim its resources and now with this available vector we finally have enough resources to run process 1 because 2 is less than 4 3 is less than 6 and 3 is less than 7 so we run this to completion we add back the allocated resources to the available vector and get the following and now the available vector equals the resource vector which is one way of checking that you've done all your computations correctly naturally because there are no processes running no resources are allocated so the number of units of available resource of each type should match the total available resources in the system so the fact that we were able to carry out this process all the way to completion shows that there was a way to run these processes without causing deadlock if we had ever had a situation where none of the rows in the need matrix had a resource need less than what was available then that would have been a problematic situation however if your system is running this algorithm from the time it boots up until the time you're done running all your processes then it will assure that such a situation never arises

Channel: Jacob Schrum

Views: 14,527

Rating: 4.939394 out of 5

Keywords: deadlock, mutual exclusion, no preemption, hold and wait, circular wait, deadlock avoidance, banker's algorithm, claim matrix, allocation matrix, concurrency

Id: WzBlKJ4pF5c

Length: 12min 58sec (778 seconds)

Published: Thu Aug 04 2016