6.1 Deadlock Analysis


6.1 Deadlock Analysis

In the finite state model of a process, a deadlocked state is, simply, a state with no outgoing transitions. A process in such a state can engage in no further actions. In FSP this deadlocked state is represented by the local process STOP. An example of a process which can lead to a deadlocked state is depicted in Figure 6.1.

image from book
Figure 6.1: MOVE process.

The MOVE process of Figure 6.1 can engage in alternating north and south actions. However, an action sequence of north followed by north leads to a deadlocked state in which no further actions are possible. This can be seen using the Animator. We can ask the LTSA analyzer tool to find deadlock states and to produce a sample trace of how these states can be reached from the start state. By performing a breadth-first search of the LTS graph, the LTSA tool guarantees that the sample trace is the shortest trace to the deadlock state. In the example of Figure 6.1, LTSA produces the following output:

 Trace to DEADLOCK:      north      north

In general, the deadlocks which interest us are not those that are declared explicitly in primitive processes using STOP as above, but those that arise from the parallel composition of a number of interacting primitive processes. The deadlock check that the analyzer performs for composite processes is, of course, the same as the check it performs for primitive processes since a composition is also described by an LTS graph. The check remains a search for states with no outgoing transitions.

The example of Figure 6.2 is a system in which two processes, P and Q, perform the same task, that of scanning a document and printing it, by using a shared printer and shared scanner. Each process acquires both the printer and the scanner, performs the scanning and printing and then releases the scanner and printer resources. The LTS diagrams for process P and for the shared printer are given in Figures 6.3 and 6.4 respectively.

image from book
Figure 6.2: Printer–scanner system.

image from book
Figure 6.3: LTS for process P.

image from book
Figure 6.4: LTS for the shared printer process.

The only difference between the processes P and Q is that P acquires the printer first and Q acquires the scanner first. This system satisfies the four necessary and sufficient conditions for deadlock which were outlined in the introduction to this chapter: the scanner and printer resources are serially reused; each process holds on to either the scanner or printer while waiting to get the second resource it requires; these resources are not preempted; and the wait-for cycle is apparent from the following deadlock discovered by LTSA:

 Trace to DEADLOCK:      p.printer.get      q.scanner.get

This is the situation in which the process P has the printer and is waiting for the scanner and the process Q has the scanner and is waiting for the printer. The deadlock is easily fixed in the example by ensuring that both processes ask for the printer and the scanner in the same order. (The reader should verify, using LTSA, that if the model of Figure 6.1 is modified in this way, deadlock no longer occurs.) In fact, where processes share different classes of resources, such as printers and scanners, a general-purpose strategy for avoiding deadlock is to order the resource classes; i.e. if processes use resources from different classes, all processes acquire these resources in the same order. For our example, this can be achieved by, for example, always requesting printers before scanners.

Another solution to avoiding deadlock, in this example, is to set a timeout on waiting for the second resource. If the resource has not been acquired within the timeout period then the first resource is released and the process starts afresh as shown below:

 P          = (printer.get-> GETSCANNER), GETSCANNER = (scanner.get->copy->printer.put                          ->scanner.put->P              |timeout -> printer.put->P              ). Q          = (scanner.get-> GETPRINTER), GETPRINTER = (printer.get->copy->printer.put                          ->scanner.put->Q              |timeout -> scanner.put->Q              ).

This denies the second deadlock condition of incremental acquisition. The solution can be implemented in Java using a timed wait. However, it is not a good solution as both processes can continually acquire the first resource, time out and then repeat this cycle without making any progress towards accomplishing the copy action. LTSA detects this progress problem, returning the following:

 Progress violation for actions: {p.scanner.get, p.copy, p.scanner.put, q.printer.get, q.copy, q.printer.put}

We deal with this class of problems in the next chapter.




Concurrency(c) State Models & Java Programs
Concurrency: State Models and Java Programs
ISBN: 0470093552
EAN: 2147483647
Year: 2004
Pages: 162

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net