Afterwards, a new deadlock detection algorithm is presented. First, the two predominant deadlock models in these systems and the four different distributed deadlock detection approaches are discussed. Incrementally preempt and re-allocate resources until the circular wait is broken.This paper attempts a comprehensive study of deadlock detection in distributed database systems. How many processes will need to be terminated? How many more resources will the process need to complete? How many and what type of resources has the process used? How long has it executed? how much more time does it need? How to determine which process to terminate? minimize cost Preempt some resources from one or more of the processes to break the circular waitĪborting a process is not easy involves clean-up (e.g., file, printer).Ībort all deadlocked processes (disadvantage: wasteful)Ībort one process at a time until the circular wait is eliminatedĭisadvantage: lot of overhead must re-run algorithm after each kill Let the system recover from the deadlock automatically:Ībort or more of the deadlocked processes to break the circular wait Inform operator and let them decide how to deal with it manually Moreover, if finish = false, then process P i is deadlocked.Įxample: consider a system with 5 processes (P 0. Then the system is in a deadlocked state. Let finish be a boolean array of length n.įor all i, if allocation != 0, then finish = false įinish = false // P i is currently not involved in a deadlock Multiple instances of a resource type: use an algorithm similar to Banker's, which simply investigates every possible allocation sequence for the processes which remain to be completed. If finish = true for all i, then the system is in a safe state, otherwise unsafe.Įxample: consider a system with 5 processes (P 0. Let finish be a boolean array of length n, initialized to false. Let work be an integer array of length m, initialized to available. Safety algorithm (to check for a safe state): If unsafe, the process must wait and the old resource-allocated state is restored. Once the resources are allocated, check to see if the system state is safe. Otherwise, pretend to allocate the requested resources to P i :Īvailable = available - request allocation = allocation + request need = need - request If request available, then the process must wait. Request: describes the current outstanding requests of all processes (e.g., request = 3) Need: describes the remaining possible need (i.e., need = max - allocation) Max: describes the maximum demands of each process (e.g., max = 2)Īllocation: describes the current allocation status ( e.g., allocation = 3) Let n be the number of processes in the system, and m be the number of resource types.Īvailable: the number of units of R currently unallocated (e.g., available = 2) We call Banker's algorithm when a request for R is made. If the system is in an unsafe state, there is the possibility of deadlock.Įxample: consider a system with 12 magnetic tapes and 3 processes (P 0, P 1, and P 2): If the system is in a safe state, there can be no deadlock. The resources held by all of the P j's, where j < i. Sequence is safe for the current allocation state if, for each P i, the resources which P i can still request can be satisfied by The system is in a safe state if there exists a safe sequence of all processes: When a process requests an available resource, the system must decide if immediate allocation leaves the system in a safe state. The system's resource-allocation state is defined by the number of available and allocated resources, and the maximum possible demands of the processes. Dynamically examine the resource allocation state to ensure that there can never be a circular-wait condition. Each process declares the maximum number of resources of each type which it may need. This requires that the system has some information available up front. Usually a deadlock prevention approach is simply unreasonable. Only allow requests in an increasing order Some resources cannot be feasibly preempted (e.g., printers, tape drives) When a process must wait, it must release its resources Prevent no preemption (i.e., allow preemption, and permit the OS to take away resources from a process) Request disk file and printer (no guarantee data will still be there) Use only sharable resources (e.g., a read-only file)ĭo not pick up one chopstick if you cannot pick up the otherįor a process that copies data from DVD drive to a file on disk and then prints it from there:Īll system calls requesting resources must proceed all other system callsĪ process can request resources only when it has none Restrain the ways resource requests are made so to prevent one of the four conditions necessary for deadlock.
0 Comments
Leave a Reply. |