A multi-unit (reusable) resource is a resource has a number of identical units. So it can serve many processes at the same time, in this system the deadlock must be happen.
At this system the cycle in Wait-For-Graph is not nessesary to detect deadlock. But the a knot is the nessesary and sufficient condition for deadlock.
My question is how i can design an effective algorithm to avoid a deadlock at this system.
the following are some solutions to avoid deadlock:
first way : Deadlock Prevention:follows that deadlock might be prevented by denying any one of the conditions.
1- Elimination of “Mutual Exclusion” Condition
2-Elimination of “Hold and Wait” Condition
The first alternative is that a process request be granted all of the resources it needs at once, prior to execution. The second alternative is to disallow a process from requesting resources whenever it has previously allocated resources.This strategy requires that all of the resources a process will need must be requested at once. This strategy can lead to serious waste of resources. also,This strategy can cause indefinite postponement (starvation). Since not all the required resources may become available at once.
3- Elimination of “No-preemption” Condition
The process must release its held resources and, if necessary, request them again together with additional resources. Implementation of this strategy denies the “no-preemptive” condition effectively. One serious consequence of this strategy is the possibility of indefinite postponement (starvation). A process might be held off indefinitely as it repeatedly requests and releases the same resources.
4- Elimination of “Circular Wait” Condition
The last condition, the circular wait, can be denied by imposing a total ordering on all of the resource types and than forcing, all processes to request the resources in order (increasing or decreasing). This strategy impose a total ordering of all resources types, and to require that each process requests resources in a numerical order (increasing or decreasing) of enumeration. With this rule, the resource allocation graph can never have a cycle. The problem with this strategy is that it may be impossible to find an ordering that satisfies everyone.
second way:Deadlock Avoidance:
This approach to the deadlock problem anticipates deadlock before it actually occurs. This approach employs an algorithm to access the possibility that deadlock could occur and acting accordingly. This method differs from deadlock prevention, which guarantees that deadlock cannot occur by denying one of the necessary conditions of deadlock. It is important to note that an unsafe state does not imply the existence or even the eventual existence a deadlock. What an unsafe state does imply is simply that some unfortunate sequence of events might lead to a deadlock
third way:Deadlock Detection:
Deadlock detection is the process of actually determining that a deadlock exists and identifying the processes and resources involved in the deadlock.
The basic idea is to check allocation against resource availability for all possible allocation sequences to determine if the system is in deadlocked state a. Of course, the deadlock detection algorithm is only half of this strategy. Once a deadlock is detected, there needs to be a way to recover several alternatives exists:
Temporarily prevent resources from deadlocked processes.
Back off a process to some check point allowing preemption of a needed resource and restarting the process at the checkpoint later.
Successively kill processes until the system is deadlock free.
These methods are expensive in the sense that each iteration calls the detection algorithm until the system proves to be deadlock free. Another potential problem is starvation; same process killed repeatedly.
for more information visit this website: http://www.personal.kent.edu/~rmuhamma/OpSystems/os.html
In time-based distributed systems such as distributed real-time systems, it is possible to detect potential deadlocks by using timeouts. Note, however, in contrast to the expensive algorithms of actually deterministically detect a deadlock (mentioned by Nada Alghamni), this is probabalistic. It may be the case that there is no deadlock, only a response that is too slow. However, it is possible to build a system so that it (a) assumes that a deadlock as has occurred and (b) starts to resolve it irrespective of that an actual deadlock has occurred. Note that this approach can still be expensive even though the detection process has been simplified by system design, since the resource must somehow be recovered (either backward (typically expensive) or forward (domain-dependent)).
Most approaches heads for eventual consistency rather than immediate consistency. Cf. the CAP theorem (https://en.wikipedia.org/wiki/CAP_theorem). In distributed real-time databases, I participated in seminal work on this topic (see publication). Essentially, we avoided (distributed) deadlocks at the cost of availability. Note that the application need to be fault-tolerant, but this is the case in many real-world situations anyway.
Article DeeDS Towards a Distributed and Active Real-Time Database System
You should make use of Semaphores. See explanations below.
Semaphores: In the year 1965, a man called Dijkstra introduced a mechanism called semaphores for controlling the order of execution of concurrent processes in a multiprocessor system.
A semaphore is an integer variable, say s, whose initial value can be set to 0, and then the following two operations, P(s) and V(s) performed on it as follows:-
initialize value of s to 0 (that is, s = 0)
P(s):
1. Decrement value of s by 1 (that is, s = s – 1)
2. If s is less than 0, WAIT(s)
V(s):
1. Increment value of s by 1 (that is, s = s +1)
2. If s is equal to 0, SIGNAL(s)
Explanations: Before a concurrent process acquires the use of a system resource, it first of all performs the operation, P(s). If the result of this operation is less than 0, it knows that the particular system resource is currently occupied, and so it has to WAIT until the resource is released when the process that is holding it performs the operation V(s) which increments the value of s to 1. Conversely, if the result of the operation, P(s) is equal to 0, it means that the required system resource is available, and so the requesting process can make use of it.