17-03-2011, 04:09 PM
[attachment=10433]
DEADLOCK DETECTION USING JAVA
ABSTRACT
Recently low cost multi core processors have become readily available. In order to exploit this capability it is generally necessary to add multi-threading to exiting applications. Programmers need to understand the timing variability that now becomes an issue and to be aware of the possibility of getting into deadlock situations, common in multi-threaded code. The problem to be solved in this project was to detect deadlock in a java application. This also provided an introduction to the monitoring of application code
A deadlock is a situation wherein two or more competing actions are each waiting for the other to finish, and thus neither ever does. Often, neither avoidance nor deadlock prevention may be used. Instead deadlock detection and process restart are used by employing an algorithm that tracks resource allocation and process states, and rolls back and restarts one or more of the processes in order to remove the deadlock. Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the resource scheduler or OS.
Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario. However, in specific environments, using specific means of locking resources, deadlock detection may be decidable. In the general case, it is not possible to distinguish between algorithms that are merely waiting for a very unlikely set of circumstances to occur and algorithms that will never finish because of deadlock.
Deadlock detection techniques include, but is not limited to, Model checking. This approach constructs a Finite State-model on which it performs a progress analysis and finds all possible terminal sets in the model. These then each represent a deadlock.
INTRODUCTION
The main purpose of the project is the study of state-of-the-art techniques for run-time
deadlock detection and their application using java. This project is part of our efforts to
provide a satisfactory solution to the problem of deadlock prevention, avoidance, detection,
and resolution.
Deadlocks is a fundamental problem in distributed systems. A process may request resources in any order, which may not be known a priori and a process can request resource while holding others. If the sequence of the allocations of resources to the
processes is not controlled, deadlocks can occur. A deadlock is a state where a set of processes request resources that are held by other processes in the set.
EXISTING SYSTEM
The heart of the problem is that deadlocked processes don’t know they are deadlocked. Much of the early work on deadlock characterization is due to Dijkstra. There is no physical global clock in the system to which processes have instantaneous access.
The communication medium may deliver messages out of order, messages may be lost garbled or duplicated due to timeout and retransmission, processors may fail and communication links may go down.
Drawbacks
The systems have only reusable resources.
Processes are allowed to make only exclusive access to resources.
There is only one copy of each resource.
A process can be in two states: running or blocked. In the running state (also called active state), a process has all the needed resources and is either executing or is
ready for execution. In the blocked state, a process is waiting to acquire some
resource.
A limited number of a particular resource, this limited number is one, since a monitor is a mutual-exclusion lock (meaning only one thread can own a monitor at a time).
Proposed System
There are a number of algorithms available for preventing or avoiding deadlocks, two of which are discussed here. In order to create a deadlock it is necessary to fulfill all four of the Coffman conditions. Eliminating any one of the conditions will ensure that deadlock cannot occur
Resource allocation is used to assign the available resources in an economic way. It is part of resource management. In project management, resource allocation is the scheduling of activities and the resources required by those activities while taking into consideration both the resource availability and the project time
We will start off by reading a collection of articles related to the problem of runtime deadlock detection with particular focus on object-oriented techniques.
The second step is to acquire deep knowledge and understanding of OOP mechanism and its implementation. we will accomplish that by reading Deadlock detection-related articles. To design and efficiently implement the deadlock detection mechanism and integrate with OOP’s concepts
The proposed technique is known as the Bankers Algorithm [Dijkstra Undated]. It is assumed that there are multiple instances of each resource type. This implies that a resource-allocation graph can not be used. Processes are required to declare in advance the maximum need for each resource. Over time, processes make actual requests which cannot exceed the pre declared maximum quantity. If the allocation leaves the system in a “safe” state then the system grants the resource. If the system would be left in an “unsafe” state then the process is suspended until the system has adequate resources to grant the request. There is an algorithm defined that determines if a particular allocation would leave the system in an “unsafe” condition and therefore in danger of being deadlocked.
Objectives
A process makes a request for a resource and waits if it isn’t available.
The process will need to have use of all required resources before its work can be completed.
The process releases resources once they are no longer needed so that other
processes can use them.
To conduct review of different algorithms.
To Evaluate resource allocation algorithm using java.
To Implement the algorithm by OOP’s concepts
Scope of the work
- To Study of several algorithms for deadlock detection and their applicability to OOP’s,
- To Design and implementation of a suitable algorithm in OOP’s,
- Assessment of the proposed solution.
Conclusion:
The basic detection technique is to determine that a loop exists; that each process is waiting for a resource held by another process which in turn is waiting for a resource held by another process and that this ultimately constitutes a loop. This is a fairly simple system in that each process only requests two resources and that it does so in sequence, first the left chopstick and then the right one. A deadlock is visually detected by noting that all processes are waiting for their right processes. The problem is to instrument a monitor that detects the state of the java program and that detect that all processes are locked.
