Deadlock
In an operating system deadlock
arrived when two or more process want to access the same resource (resource may
include processors, memory, network modem, printers and files etc.) To compete their task or action.
Or when two
or more process waiting for each other to complete is called a deadlock
situation.
For example:
Process P0
using resource R0 and it need resource R1 to complete its task but at the same
time another process P1 is using resource R1 and it need the resource R0 which
is currently acquired by P0 to complete its own action so both processes wait
for each other to complete their task and they keep waiting for life time
because no one can complete its action. So we can say that the both processes
are in deadlock situation.
As you can
see in the figure given below.
Conditions when deadlock occur:
·
At one time a single process can use the a
resource (Mutual Exclusion)
·
A process holding a resource and also waiting
for another resource which is currently in use of other process (Hold and Wait)
·
A process can release resource when it completes
its execution (No Preemption)
·
When two or more processes waiting for one
another to release the resource so they can complete their task.
Solutions:
There
are three method to get rid of deadlocks
Deadlock prevention:
In this method it is ensured in
the Operating system that system will never enter in deadlock situation.
Every process have access to the shared resource at the
same time but not for the unshared resources,
Make sure when a process request for a resource it is not
holding any other resources. Process must request for resource and be allocated
before start its execution. Or allow the process to request for resource when
it has no resource allocated.
If a process request for resources and currently holding
some resources then cannot allocate the new resource until it release the
currently holding resources.
Restart the process when it regain the old resource and
the new one which was requested. Each process must request for resources in
increasing order.
Preempted resource should be added in to the required
resources list for which process are waiting.
Deadlock avoidance:
Ignore the deadlocks and pretend that deadlock never
occurs in the system. Most of the operating system use this method including
UNIX.
This method need some prior information available about
the processes and the resources.
In this each process which is currently loaded declare
the maximum number of resource which required by the process to complete its
task. Algorithm for deadlock avoidance check for resources allocation to ensure
that there is no process waiting for the resource which is currently in use or
it ensure that there is no circular waiting of processes. Maintains a state of
available resource and allocated resource, and also keep the record of
resourced demand by the processes.
Deadlock detection:
Allow
the system to go in the deadlock situation and then recover the system from
deadlock using different algorithms.
First allow the system to enter in a deadlock state then
define some detection algorithms to detect the deadlock in the system, and make
a recovery scheme to recover the system from deadlock condition.
To recover the system from a deadlock state select a
victim and reclaim the resource, or roll back the process which is most
recently started.
Deadlock recovery:
If
deadlock is occurred now what steps we should take.
Process termination:
·
Delete all the process which are in deadlock
condition but is expensive.
·
Delete one by one process until the deadlock is
broken.
·
Select a process which is recently start and
terminate it.
Resource preemption:
·
Select a resource to preempt.
·
Roll back to a previous safe state.
·
Prevent the one process which is always selected
as a victim.
System States:
·
Safe state
·
Unsafe state
·
Deadlock state
System can be in one of the states given above.
Safe state:
A
system is in a safe state if all the process are in a sequence and resource
required by a process are available at the time and not in use of any of the
other process. When a process request for the resources system must check that
after the allocation of these resource system can remain in safe state.
If a process need a resource which is currently in use so
this process can wait until the process release the required resource.
If a system is in safe state that means there is no
deadlocks.
Unsafe state:
A
system is in unsafe state when there is a chance of the occurrence of deadlock
or resources allocated which is currently in use of some other processes.
Deadlock state:
System
in deadlock state when two or more process want the same resources or two or
more process waiting for each other to complete their tasks.