Deadlock detection, Operating System

Deadlocks can be detected while the program is running, by running cycle detection algorithms on the graph that de?nes the current use of resources.

De?ne this graph as follows: it has one vertex for each resource (r1; : : : ; rm) and one vertex for each thread (t1; : : : ; tn). If a resource ri is held by thread tj , then we add an edge from vertex ri to vertex tj . If a thread tk is trying to acquire resource r', then we add an edge from vertex tk to vertex r'.

Given this graph, we can run a cycle detection algorithm. If a cycle is found, there is a deadlock. Detecting a deadlock ismuch easier than recovering froma deadlock. Several possible approaches might be to kill all of the threads in the cycle, or kill the threads one at a time, forcing them to release resources, and hope that this will break the deadlock.

While this may sound easy, it is not. Killing threads generally doesn't release their resources cleanly (locks,memory, ?les, etc). This is essentially the rollback problem, to back out all the actions of a thread. Databases usually include rollback mechanisms, which can be quite complicated, and it is not always possible to roll back all the actions of a thread (consider a thread which outputs hard-copy printed pages).

As a general guideline, do not use functions like pthread cancel(), which kills a thread, unless you really know what you are doing.

Posted Date: 3/12/2013 5:31:38 AM | Location : United States







Related Discussions:- Deadlock detection, Assignment Help, Ask Question on Deadlock detection, Get Answer, Expert's Help, Deadlock detection Discussions

Write discussion on Deadlock detection
Your posts are moderated
Related Questions
File allocation using I nodes. This method is used to decrease the size of the table in the above method. Every file will have an I-node list. Allow a file have 15 pointers a

Q. Explain the actions taken by a kernel to context switch between kernel level threads. Answer: Context switching among kernel threads classically requires saving the value

Define Overflow Chaining Another method will divide the pre-allocated table into two sections: the primary area to determine which keys are mapped and an area for collisions, g

Define the properties operating systems: Batch :- Jobs with similar needs are batched together and  run through the computer as a group by an operator or automatic job sequenc


Define logical address and physical address. An address formed by the CPU is referred as logical address. An address seen by the memory unit that is the single loaded into the

What is virtual memory? Virtual memory is a method that allows the execution of processes that might not be completely in memory. It is the separation of user logical memory fr


Determining the time quantum for a job is a critical task. Given the assumptions that the average switching time between processes is s, and the average amount of time an I/O bo

Q. Presume that you have coded the deadlock-avoidance safety algorithm as well as now have been asked to implement the deadlock-detection algorithm. Can you do thus by simply usin