0
What are the main limitations to the resource allocation graph used in deadlock detection. explain?
Wiki User
∙ 10y ago
time Stamp
Wiki User
∙ 10y ago
Add your answer:
Earn +20 pts
What is deadlock and explain it?
A deadlock is when both sides can't agree on a decision or when something is stuck and can't move. In technology, a deadlock is a situation where a group of processes are permanently blocked as a result of each process having acquired a subset of the resources needed for its completion and waiting for release of the remaining resources held by others in the same group-thus making it impossible for any of the process to proceed.
What is difference between starvation and deadlock?
Deadlock: Two processes are said to be in deadlock situation if process A holding onto resources required for process B and where as B holding onto the resources required for process A. Starvation: This is mostly happens in time sharing systems in which the process which requires less time slot is waiting for the large process to finish and to release the resources, but the large process holding the resources for long time (almost for forever) and the process that requires small time slot goes on waiting. Such situation is starvation for small process
Discuss methods for handling deadlocks?
ignore the problem altogether ie. ostrich algorithm it may occur very infrequently, cost of detection/prevention etc may not be worth it.detection and recoveryavoidance by careful resource allocationprevention by structurally negating one of the four necessary conditions.Deadlock PreventionDifference from avoidance is that here, the system itself is build in such a way that there are no deadlocks. Make sure atleast one of the 4 deadlock conditions is never satisfied.This may however be even more conservative than deadlock avoidance strategy.Attacking Mutex conditionnever grant exclusive access. but this may not be possible for several resources.Attacking preemptionnot something you want to do.Attacking hold and wait conditionmake a process hold at the most 1 resource at a time.make all the requests at the beginning. All or nothing policy. If you feel, retry. eg. 2-phase lockingAttacking circular waitOrder all the resources.Make sure that the requests are issued in the correct order so that there are no cycles present in the resource graph. Resources numbered 1 ... n. Resources can be requested only in increasing order. ie. you cannot request a resource whose no is less than any you may be holding.Deadlock AvoidanceAvoid actions that may lead to a deadlock. Think of it as a state machine moving from 1 state to another as each instruction is executed.Safe StateSafe state is one whereIt is not a deadlocked stateThere is some sequence by which all requests can be satisfied.To avoid deadlocks, we try to make only those transitions that will take you from one safe state to another. We avoid transitions to unsafe state (a state that is not deadlocked, and is not safe) eg.Total # of instances of resource = 12(Max, Allocated, Still Needs)P0 (10, 5, 5) P1 (4, 2, 2) P2 (9, 2, 7) Free = 3 - SafeThe sequence is a reducible sequencethe first state is safe.What if P2 requests 1 more and is allocated 1 more instance?- results in Unsafe stateSo do not allow P2's request to be satisfied.Banker's Algorithm for Deadlock AvoidanceWhen a request is made, check to see if after the request is satisfied, there is a (atleast one!) sequence of moves that can satisfy all the requests. ie. the new state is safe. If so, satisfy the request, else make the request wait.How do you find if a state is safen process and m resources Max[n * m]Allocated[n * m]Still_Needs[n * m]Available[m]Temp[m]Done[n]while () {Temp[j]=Available[j] for all jFind an i such thata) Done[i] = Falseb) Still_Needs[i,j]
What is a shared resource?
Well, a shared resource is something that is like a natural resource but it is shared so that makes it a "Shared Resource".
Which access control model allows the owner of the resource to choose who can access the resource?
Discretionary access controlnswer Explanation: The discretionary access control (DAC) model permits the owner of a resource to identify the users who can access the resource. You become the owner of the resource by either creating the resource or by being granted ownership of that resource. You grant access to the resources using access control lists (ACLs).
Can resource allocation graph have cycles without a deadlock?
yes resource allocation graph have cycles without a deadlock existing.
What are the various strategies are used to handle deadlock and what is centralized and distributed deadlock detection and prevention?
There are four strategies of dealing with deadlock problem:1. The Ostrich ApproachJust ignore the deadlock problem altogether.2. Deadlock Detection and RecoveryDetect deadlock and, when it occurs, take steps to recover.3. Deadlock AvoidanceAvoid deadlock by careful resource scheduling.4. Deadlock PreventionPrevent deadlock by resource scheduling so as to negate at least one of the four conditions.
Can deadlock be resolved without selecting a victim?
Yes, deadlock can be resolved by avoiding the conditions that lead to it, breaking the circular wait, or using deadlock prevention techniques like resource allocation graph, timeouts, or priority-based techniques. In some cases, deadlock can also be prevented by ensuring a single thread holds all resources simultaneously or by using a deadlock detection algorithm to preemptively handle it.
What is the difference between resource allocation graph and wait for graph?
In Wait for Graph the request edge is a directed edge Pi → Pj which indicates that process Pj is holding a resource that process Pi needs and thus Pi is waiting for Pj to release its lock on that resource. It does not have any allocation edge.In case of Resource Allocation Graph the request edge is a directed edge Pi → Rj which indicates that process Pi is requesting resource Rj. It has an allocation edge from Rj→Pk when the resource Rj is allocated to process Pk.The way the graphs are drawn are also different but both of them are used in deadlock detection.
What is difference between in deadlock prevention and deadlock avoidance and?
Deadlock PreventionDifference from avoidance is that here, the system itself is build in such a way that there are no deadlocks.Make sure atleast one of the 4 deadlock conditions is never satisfied.Deadlock AvoidanceAvoid actions that may lead to a deadlock.Think of it as a state machine moving from 1 state to another as each instruction is executed. moreoverDeadlock detection is a technique to handle deadlocks which tries to find out if the system is in deadlock and then works to recover it from the deadlock if any exists. It is used as an afterthought and is not coordinated with the resource allocating procedures.Deadlock avoidance is a technique which works hand-in-hand with the resource allocation and tries to ensure that a resource request made in a non-deadlocked state is granted only if it will not lead to a deadlock in the future. This technique however makes unrealistic demands about the kind of information it needs from process, in that, it requires the entire pattern of resource requests, past & future.
What are the deadlock detection algorithms?
Deadlock is a scenario where two or more processes are blocked, each waiting for the other to release the necessary resources to complete their execution. This situation can cause the entire system to become unresponsive, leading to reduced performance and potentially crashing the system. To avoid this, it is essential to have an effective deadlock detection algorithm in place. Several deadlock detection algorithms are used in modern computer systems. These algorithms use different approaches to detect deadlocks, and each algorithm has its strengths and weaknesses. Wait-for Graph Algorithm: The wait-for graph algorithm is a commonly used deadlock detection algorithm. In this algorithm, a directed graph is created, where the nodes represent the processes, and the edges represent the resources they are waiting for. The algorithm checks if there is a cycle in the graph. If there is a cycle, there is a deadlock in the system. The wait-for-graph algorithm has a few limitations. It can only detect deadlocks and does not provide any mechanism to recover from them. Also, the algorithm may only work well in large systems with a few resources. Resource Allocation Graph Algorithm: The resource allocation graph algorithm is another widely used deadlock detection algorithm. This algorithm creates a graph where the nodes represent the processes and the resources they hold or need. The algorithm checks for cycles in the graph. If there is a cycle, there is a deadlock in the system. The resource allocation graph algorithm is easy to implement and provides an efficient way to detect deadlocks. However, the algorithm requires considerable memory to store the graph, and it can be slow in large systems. Banker's Algorithm: The Banker's algorithm is a resource allocation and deadlock avoidance algorithm. In this algorithm, each process is given a maximum limit on the number of resources it can use. The algorithm checks if granting the requested resources will result in a safe state or not. If the state is safe, the resources are allocated to the process. If the condition is unsafe, the process is put on hold. The Banker's algorithm is an efficient way to prevent deadlocks. However, it requires considerable overhead to maintain the system's state, and it may only work well in systems with a few resources. Ostrich Algorithm: The Ostrich algorithm is a dynamic deadlock detection algorithm. This algorithm assumes a process is deadlocked if it does not progress for a specified period. The algorithm periodically checks the progress of each method and detects if any process is deadlocked. The Ostrich algorithm is efficient in detecting deadlocks in dynamic systems. However, it may not work well in systems where the processes are short-lived, and the algorithm may not detect deadlocks that occur over a short period. Timeout-based Algorithm: The timeout-based algorithm is another dynamic deadlock detection algorithm. This algorithm sets a timer for each resource request made by a process. If the requested resource is not allocated within the specified time, the process is assumed to be deadlocked. The timeout-based algorithm is an efficient way to detect deadlocks in dynamic systems. However, the algorithm may not work well in systems where the processes are short-lived, and it may produce false positives if the time-out period is too short.
What are the differences between deadlock avoidance and deadlock prevention in operating systems?
Deadlock Prevention: o Preventing deadlocks by constraining how requests for resources can be made in the system and how they are handled (system design). o The goal is to ensure that at least one of the necessary conditions for deadlock can never hold. * Deadlock Avoidance: o The system dynamically considers every request and decides whether it is safe to grant it at this point, o The system requires additional apriori information regarding the overall potential use of each resource for each process. o Allows more concurrency. Similar to the difference between a traffic light and a police officer directing traffic. * Deadlock deduction:- 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.
How do you prevent deadlock in Linux?
Deadlock is not really anything a user has to worry about. Deadlock is merely what happens when two objects want to make the use of each other's resource, but won't release the resource they have until they get the resource they want. How this is usually prevented is to have an object drop ANY resource it no longer needs before trying to get a new resource. This is just one approach, as it doesn't stop deadlock if both objects need the resource they have but need a resource the other object needs.
Which of the nine resource allocation strategies is best?
Which of the nine resource allocation strategies is best in your opinion*
What are resource allocation name graphs?
What are the dominate method of resource allocation?Discuss with the help of example?
What is difference between resource allocation graph and resource allocation graph algorithm?
The graph is the the actual picture that shows the resource allocation; the algorithm is the method used to produce that graph.
Difference between resource allocation and resource utilization?
Resource allocation refers to setting aside resources. Resource utilization refers to how resources are used.
