patternMinor
Falsifying the "Circular Wait" Condition - Deadlock Prevention
Viewed 0 times
falsifyingtheconditionwaitdeadlockcircularprevention
Problem
In the Circular Wait condition for
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
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.Solution
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.
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.
Context
StackExchange Computer Science Q#54732, answer score: 2
Revisions (0)
No revisions yet.