§
We
can use a protocol to prevent or avoid deadlock
ensuring that the system will never enter to a deadlock state.
§ We can allow the
system to enter a deadlock state, detect it and recover.
§ We can ignore the
problem all together.
To ensure that deadlock never occur the system can use either a deadlock
prevention or deadlock avoidance scheme.
Deadlock Prevention:
Deadlock prevention is a set of methods
for ensuring that at least one of these necessary
conditions cannot hold.
§
Mutual Exclusion:
The mutual exclusion condition holds for non sharable. The example is a printer cannot be simultaneously shared by several processes.
Sharable resources do not require mutual exclusive access and thus cannot be involved in a dead lock.
The example is read only files which are in sharing condition.
If several processes attempt to open the read only file at the same time they can be guaranteed simultaneous access.
The mutual exclusion condition holds for non sharable. The example is a printer cannot be simultaneously shared by several processes.
Sharable resources do not require mutual exclusive access and thus cannot be involved in a dead lock.
The example is read only files which are in sharing condition.
If several processes attempt to open the read only file at the same time they can be guaranteed simultaneous access.
§
Hold
and wait:
To ensure that the hold and wait condition never occurs in the system, we must guaranty that whenever a process requests a resource it does not hold any other resources.
There are two protocols to handle these problems such as one protocol that can be used requires each process to request and be allocated all its resources before it begins execution.
The other protocol allows a process to request resources only when the process has no resource.
These protocols have two main disadvantages. First, resource utilization may be low, since many of the resources may be allocated but unused for a long period.
To ensure that the hold and wait condition never occurs in the system, we must guaranty that whenever a process requests a resource it does not hold any other resources.
There are two protocols to handle these problems such as one protocol that can be used requires each process to request and be allocated all its resources before it begins execution.
The other protocol allows a process to request resources only when the process has no resource.
These protocols have two main disadvantages. First, resource utilization may be low, since many of the resources may be allocated but unused for a long period.
§
No
Preemption:
To ensure that this condition does not hold, a protocol is used. If a process is holding some resources and request another resource that cannot be immediately allocated to it.
The preempted one added to a list of resources for which the process is waiting.
The process will restart only when it can regain its old resources, as well as the new ones that it is requesting.
Alternatively if a process requests some resources, we first check whether they are available.
If they are, we allocate them. If they are not available, we check whether they are allocated to some other process that is waiting for additional resources.
§ Circular Wait:
We can ensure that this condition never holds by ordering of all resource type and to require that each process requests resource in an increasing order of enumeration.
Let R= {R1, R2, …….Rn}be the set of resource types.
We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering.
Formally, we define a one to one function F: R ® N,
where N is the set of natural numbers.
For example, if the set of resource types R includes tape drives, disk drives and printers, then the function F might be defined as follows:
F (Tape Drive) = 1,
F (Disk Drive) = 5,
F (Printer) = 12.
We can now consider the following protocol to prevent deadlocks: Each process can request resources only in an increasing order of enumeration.
That is, a process can initially request any number of instances of a resource type, say Ri. After that, the process can request instances of resource type Rj if and only if F (Rj) > F (Ri). If several instances of the same resource type are needed,
defined previously, a process that wants to use the tape drive and printer at the same time must first request the tape drive and then request the printer.
Deadlock Avoidance
Safe State
To ensure that this condition does not hold, a protocol is used. If a process is holding some resources and request another resource that cannot be immediately allocated to it.
The preempted one added to a list of resources for which the process is waiting.
The process will restart only when it can regain its old resources, as well as the new ones that it is requesting.
Alternatively if a process requests some resources, we first check whether they are available.
If they are, we allocate them. If they are not available, we check whether they are allocated to some other process that is waiting for additional resources.
§ Circular Wait:
We can ensure that this condition never holds by ordering of all resource type and to require that each process requests resource in an increasing order of enumeration.
Let R= {R1, R2, …….Rn}be the set of resource types.
We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering.
Formally, we define a one to one function F: R ® N,
where N is the set of natural numbers.
For example, if the set of resource types R includes tape drives, disk drives and printers, then the function F might be defined as follows:
F (Tape Drive) = 1,
F (Disk Drive) = 5,
F (Printer) = 12.
We can now consider the following protocol to prevent deadlocks: Each process can request resources only in an increasing order of enumeration.
That is, a process can initially request any number of instances of a resource type, say Ri. After that, the process can request instances of resource type Rj if and only if F (Rj) > F (Ri). If several instances of the same resource type are needed,
defined previously, a process that wants to use the tape drive and printer at the same time must first request the tape drive and then request the printer.
Deadlock Avoidance
Requires additional information about how resources are to be used.
Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.
The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.
Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.
Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.
The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.
Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.
Safe State
When a process
requests an available resource, system must decide if immediate allocation leaves the system
in a safe state.Systems are in safe state if there exists a safe sequence of
all process. A sequence <P1, P2, …, Pn>
of ALL the processes is the system such that for each Pi, the
resources that Pi can still request
can be satisfied by currently available resources + resources held by all the Pj, withj <i.That is:
· If Pi resource needs are not immediately available, then Pi can wait until all Pjhave finished.
· When Pj is finished, Pi can obtain needed resources, execute, return allocated
resources, and terminate.
· When Pi
terminates, Pi +1 can obtain its needed resources, and so on.
· If system is in
safe state => No deadlock
· If system in not
in safe state => possibility of deadlock
· OS cannot prevent processes
from requesting resources in a sequence that leads to deadlock
· Avoidance => ensue that system will never enter
an unsafe state,
prevent getting into deadlock
⏪Previous Next⏩
- What is an Operating System ?
- Discuss the structure off OS ?
- Explain type of OS?
- Explain Function of OS?
- Explain OS Services ?
- What do mean by system call ?List different type ofsystem call available ?
- what is process ? and Characteristics ?
- What is different process state? explain the same in details?
- write short note on user level and kernal level threads?
- explain what is thread and its type ?
- explain scheduler ? (short term,medium term,and long term)
- state and explain scheduling criteria ?
- Explain scheduling algorithm ? [ FCFS,SJF,PRIORITY,ROUND ROBINE.]
- What is process synchronization ? explain critical section problem and race condition ?
- what is Race Condition ?
- what is critical section problem?
- explain classical problem of synchronization?
- explain bounded - buffer problem?
- explain reader - writer problem ?
- explain Dining Philosophers Problem ?
- explain semaphores ? its type ?
- What is deadlock ?
- What are the 4 condition to produce deadlock ?
- explain methods of handling deadlock ?
- explain in detail deadlock prevention ?
- write short note on deadlock avoidance ?
- explain deadlock detection ?
- explain Banker algorithm with example ?
- What are memory management ?
- what is contiguous memory allocation and non - contiguous memory allocation ?
- explain concept of paging with neat diagram?
- differentiate contiguous and non - contiguous memory allocation ?
- explain in details various partitioning memory management?
- explain the concept of Segmentation ?
- what is Thrashing explain in details ?
0 Comments