OS Part 10: Deadlock Detection, Recovery and Avoidance in Operating System

hello my name is Kindson Munonye and in this video I’m
going to be talking about resource allocation and deadlock this is a concept in
operating system I’m just going to try to be very very
clear brief and to the point what do we mean by resource allocation let me just
give it a little brief overview of what we are talking about when we say resource allocation. of course you know that in the operating system they are processes
and there are resources. Of course processes is program that is executing like running Microsoft Word and saving it to disc. What happens when you click on file Save
As and you are saving to disk, you want to use a resource, the disk, If the disk is not
there, how do you save? so you can have several users trying to use or several
processes trying to to use a resource at the same time so how resources
are allocated? Maybe you have just one printer and you have a number of things trying to print ok that is the concept of resource allocation normally is going to be something like the
sequence here you have 1. Request a Resource, 2. Use the Resource and 3. Release okay that’s normal thing but if you
have two processes and each of them is requesting for resource that is
exclusively held by the other process none of them can continue. Maybe an
example is going to help us to understand as we move along. For a
deadlock to happen we need this 4 condition their most mutual
exclusion condition, each resource is either called currently assigned to one
process or is available. What it means resource is exclusively held by one
process. Two processes cannot share a resource If is not held by one process then it is
available so that is the definition mutual exclusion Hold and Wait, a process is having a
resource and it stops executing and waiting for another process, that is Hold and Wait. No Preemption means you
can’t possibly take away a resource from a process that it has been granted ok so a process most explicitly release
the resource before it can be used Then we have Circular Wait, Two or more
processes waiting for a resource held by the next member of the chain so let’s model resource allocation.
Resource Allocation is modelled using the Resource Allocation Graph, RAG, Its a graph that shows processes either a requesting for a resource or is already holding the
resource okay, so the nodes can be round or it can be square. If it is
round it means it is a process, is it’s square, it means it is a resource. so it contains
directed edges. A directed edge from a resource so process means
that this process has been assigned this resource or in another way, process1 is
holding resource1. Then here we have process1 is requesting ok for resource1. so this is
the direction. The direction of the directed edge is from resources process or process to
resource. From resource the process means the process is holding this resource. From
process to resource, it means the process is requesting. so let’s look at these
examples here. Here we have No Deadlock process1 is assigned resource1 and
2 meaning that it has the two resources it needs to complete. Process2 is
requesting for Resource2. OK, and now process1 is not requesting for anything
meaning that process1 can complete successfully, release the resource2 and
allow process process2 to use the resource2. No Deadlock here. So
let’s look at this place we have process2 requesting for resource1, resource1
is being held by process1, process1 is requesting for resource2, resource2
is being held by process1. Now get it clear, get it clear why we say it is a
deadlock this resource is held by process1, okay, it can’t be released until it finishes
and now for process1 to finish is asking for resource2, OK, the same thing is
happening between process2 and resource2 process2 is holding resource2 and is
not releasing and for it to finish it needs is resource1, so there is a complete
deadlock so how do we handle deadlock? We have
four strategies: 1. Ignore the problem, the deadlock completely. That’s why it’s
called “Ostrich Algorithm”, to stick your head in the sand and pretend that
nothing is happening just ignore it. That is not going to be feasible because the
system ultimately is going to crash. 2. Detect the Occurrence of Deadlock and Recover From it. 3. Prevent the Deadlock by Denying one of the four conditions. then
Strategy number 4, Dynamic Avoidance by careful Resource Allocation.
Here we are going to look at this Dijkstra’s Banker’s Algorithm. Let’s look at the first one, Detect and Recover, So here the Operating System monitors the request and release, so each time a resource is requested and released the
Resource Allocation Graph is Updated to see if there is cycles. ok. if there is
any cycle then the Operating System kills one process to break the
cycle. If it doesn’t break, it kills another process. It does it until the
deadlock is is recovered from. So we have deadlock prevention, we prevent deadlock
by making sure one of those four conditions we discussed earlier doesn’t hold. Mutual Exclusion, Hold and Wait, No Preemption and Circular Wait.
Just ensure that one of them doesn’t hold. In case of Mutual Exclusion ensure
that resources were never assigned exclusively to one single process ok thats remove the Mutual Exclusion condition.
Hold and Wait condition: it means a process is holding a
resource and holding not releasing it and asking for more so what you can do is to make sure that
the processes request all the resources they need before they start ok so you don’t start until get
everything you need. So that halfway inside the execution you don’t stop and start requesting, so request for everything you need and acquire them before you proceed your execution. Then the second thing you can do, is that the process
requesting for results must release everything he has first. You get it. if
you want to request for a resource, give away, release, temporarily the resources
been held. then number 3, If a process requests for resource and the
resource is not available release the currently held resources.
Maybe you just pause this video and take your time to understanding it. No Preemption
of course is very clear, ensure there is preemption by making sure that esources can be taken from process by the CPU or by the OS. Circular
Wait: Require that processes are not entitled to resource just one so help deadlock avoidance
algorithms. We had Dijkstra Banker’s Algorithm. I’ll like to just look at the
demonstration so that it becomes clear So we have this bankers algorithm. It
means that there are customers who are asking for loans in the bank and they
can get a certain maximum. Now there are four customers here: Saffron, Othniel, Adaku and Osondu, ok, so the maximum resource that can be given to Saffron is
6, that can be given to Othniel, the maximum is 5 that, can be given to
Adaku, the maximum is 4, that can be given to Osondu, the maximum
is 7. So currently they have not asked for anything, any loan, so they are
having 0 0, so it’s safe. now in the middle of transaction all of them have acquired
certain resources but they can acquire more before they reach their maximum
like in case of saffron has 1, ok, she needs 5 more to get her maximum, meaning
that if Saffron request for resource there might be the problem If Othniel requests for a resource, there
might be a problem because we have available only 2 but this state is safe.
Why do we say this state is safe? is because Adaku that has 2 and has
2 more to reach maximum, the 2 available resources can be provided and it reaches
its maximum and after it can then release the whole resources ok or complete its task and in case of
processes and then 4 resources will be available to service maybe Osondu or Othniel, so he’s safe is safe because this request can be satisfied. Here well, it’s not a deadlock in (c) but
it’s not safe because if any of the customers ask for more you can’t provide it, it’s gonna be
deadlock completely so this is how the Dijkstra Banker’s algorithm work, so
please you may just go back, read up then understanding it, pause this video and
understand it a little more. This is the explanation i was making before now. So I
like to thank you for viewing. I hope this video has been informative for you.
Give me a thumbs up on this video please subscribe to my channel if you have not
done so and maybe leave a comment to tell me what you don’t understand what
you like me to discuss once again thank you for viewing