Recents in Beach

Deadlock Detection

 ⏪Previous                                                          Next⏩

                          If a system doesn’t employ either a deadlock prevention or deadlock avoidance, then deadlock situation may occur. In this environment the system must provide :

·  An algorithm to recover from the deadlock.
·  An algorithm to remove the deadlock is applied either to a system which pertains single in instance each resource type or a system which pertains several instances of a resource type.

Single Instance of each Resource type

If all resources only a single instance then we can define a deadlock detection algorithm which uses a new form of resource allocation graph called “Wait for graph”. We obtain this graph from the resource allocation graph by removing the nodes of type resource and collapsing the appropriate edges. 


Several Instances of a Resource type

The wait for graph scheme is not applicable to a resource allocation system with multiple instances of reach resource type. For this case the algorithm employs several data structures which are similar to those used in the banker’s algorithm like available, allocation and request.
·  Available: A vector of length m indicates the number of available resources of each type.
·  Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process.
·  Request: An n x m matrix indicates the current request of each process. If Request [ij] = k, then process Pi is requesting k more instances of resource type. Rj.
1.   Let Work and Finish be vectors of length m and n, respectively Initialize:

(a)  Work = Available
(b)  For i = 1,2, …, n, if
 Allocationi¹ 0, then
Finish[i] = false;
otherwise, 
Finish[i] = true.

 2.  Find an index i such that both:
(a)  Finish[i] == false
(b)  Requesti <= Work

 If no such i exists, go to step 4.
 1.Work = Work+Allocation Finish [i] = true
Go to step 2

 2.  If Finish [i] = false, for some i, 1£ i£ n, then the system is in a deadlock state. Moreover, if Finish
[i] = false, then process Pi is deadlocked.

Recovery from Deadlock

When a detection algorithm determines that a deadlock exists, several alternatives exist. One possibility is to inform the operator that a deadlock has occurred, and to let the operator deal with the deadlock manually. The other possibility is to let the system recover from the deadlock automatically. There are two options for breaking a deadlock. One solution is simply to abort one or more processes to break the circular wait. The second option is to preempt some resources from one or more of the deadlocked processes.

Process Termination:

To eliminate deadlocks by aborting a process, we use one of two methods. In both methods, the system reclaims all resources allocated to the terminated processes.
·  Abort all deadlocked processes: This method clearly will break the deadlock cycle, but at a great expense; these processes may have computed for a long time, and the results of these partial computations must be discarded and probably recomputed later.
·  Abort one process at a time until the deadlock cycle is eliminated:This method incurs considerable overhead, since after each process is aborted, a deadlock detection algorithm must be invoked to determine whether any processes are still deadlocked.


Resource Preemption:

To eliminate deadlocks using resource preemption, we successively preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken. If preemption is required to deal with deadlocks, then three issues need to be addressed.
·  Selecting a victim: Which resources and which processes are to be preempted? As in process termination, we must determine the order of preemption to minimize cost. Cost factors may include such parameters as the numbers of resources a deadlock process is holding, and the amount of time a deadlocked process has thus far consumed during its execution.
·  Rollback: If we preempt a resource from a process, what should be done with that process? Clearly, it cannot continue with its normal execution; it is missing some needed resource. We must rollback the process to some safe state, and restart it from that state.
Starvation:
In a system where victim selection is based primarily on cost factors, it may happen that the same process is always picked as a victim. As a result, this process never completes its designated task, a starvation situation that needs to be dealt with in any practical system. Clearly, we must ensure that a process can be picked as a victim only a small finite number of times. The most common solution is to include the number of rollbacks in the cost factor.

⏪Previous                                                          Next⏩

  1. What is an Operating System ?
  2. Discuss the structure off OS ?
  3. Explain type of OS?
  4. Explain Function of OS?
  5. Explain OS Services ?
  6. What do mean by system call ?List different type ofsystem call available ?

  1. what is process ? and Characteristics ?
  2. What is different process state? explain the same in details?
  3. write short note on user level and kernal level threads?
  4. explain what is thread and its type ?
  5. explain scheduler ? (short term,medium term,and long term)
  6. state and explain scheduling criteria ?
  7. Explain scheduling algorithm ? [ FCFS,SJF,PRIORITY,ROUND ROBINE.]    

  1. What is process synchronization ? explain critical section problem and race condition ?
  2. what is Race Condition ?
  3. what is critical section problem?
  4. explain classical problem of synchronization?
  5. explain bounded - buffer problem?
  6. explain reader - writer problem ?
  7. explain Dining Philosophers Problem ?
  8. explain semaphores ? its type ?

  1.  What is deadlock ?
  2. What are the 4 condition to produce deadlock ?
  3. explain methods of handling deadlock ?
  4. explain in detail deadlock prevention ?
  5. write short note on deadlock avoidance ?
  6. explain deadlock detection ? 
  7. explain Banker algorithm with example ? 

Post a Comment

0 Comments