# Falsifying the “Circular Wait” Condition - Deadlock Prevention

In the Circular Wait condition for Deadlock Prevention section of this, it is described as follows:

One way to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration. To illustrate, we let R = {R1, R2, ..., Rm} be the set of resource types. We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering. Formally, we define a one-to-one function F: R → N, where N is the set of natural numbers.

For example, if the set of resource types R includes tape drives, disk drives, and printers, then the function F might be defined as follows: F (tape drive) = 1 F (disk drive) = 5 F (printer) = 12 We can now consider the following protocol to prevent deadlocks: Each process can request resources only in an increasing order of enumeration.

My question is that whether these numbers are assigned as fixed for all processes or when each process is called, it assigns a new number to each resource each time that process is called?

Because if these are fixed, then let suppose there is a process which requires disk drive first (whose number is let's say 5) and then it requires tape drive (whose number is 1 and which is less than 5); then how can it access tape drive? Because whenever it will run, it will find the same ordering / numbering of resources and it will never be able to access the tape drive.

It's fixed. Your example violates the protocol. If the process needs mutually exclusive access to both the tape drive and the disk drive, then it needs to take locks in increasing order, i.e. first the tape drive then the disk drive. If it wants to use the disk drive before the tape drive, that's fine, it will just be holding the tape drive lock in the mean time.

The ordering and protocol is a global invariant. All code everywhere at all times needs to follow the protocol to avoid deadlock. In practice, this is pretty difficult to enforce in realistic code unless there's a manager that handles resource access.

• So do you mean that "if a process requires more than one resources then it should request those resources in an increasing order of numbering, but if it requires only ONE resource then it can access resource with ANY number?" – swdeveloper Mar 21 '16 at 14:09
• @swdeveloper Yes. Also, if it locks one resource then releases it then locks another resource, there is no lock ordering requirement. It's only when a process is holding more than one lock at a time that the locks that its holding need to have been acquired in order. – Derek Elkins Mar 21 '16 at 14:31

With deadlocks, you need to distinguish between two situations: One, that a deadlock is possible. Two, that a deadlock actually occurs. For example, if process A locks X, then Y, and process B locks Y, then X, a deadlock is possible. But a deadlock only actually occors if process B manages to lock Y between X locking X and trying to lock Y, or vice versa. This may only happen very rarely. When a deadlock is possible, you can bet that there will be no actual deadlock occuring when the developer tests the software, but as soon as a customer uses it, the deadlock will occur.

Problems with software are no problem if they can be found through testing, because then they will be fixed. That's what this method achieves: It can demonstrate that when you ran the software, there was no possible deadlock.

What happens if you see that two resources were requested in the wrong order? You don't deadlock, but you notify the software developer. Then one of two actions are taken: It may be possible to fix the problem by changing the ordering of the deadlocks. Or this may not work, in which case you need to change the software.

A system could be in one of four states: 1. Proven that no deadlocks are possible. 2. No evidence that deadlocks are possible. 3. Evidence that deadlocks are possible. 4. Actual deadlocks happening. Instead of waiting for the fatal and rare (4) to happen, we detect the much less rare (3) and then modify the system to get into state (2). (1) would be really difficult to achieve.