Resource-Allocation Graph Algorithm
● Claim edge Pi → Rj indicated that process Pj may request resource Rj; represented by a dashed line.
● Claim edge converts to request edge when a process requests a resource.
● When a resource is released by a process, assignment edge reconverts to a claim edge.
● Resources must be claimed a priori in the system.
EXPLANATION:
A set of vertices V and a set of edges E.
● V is partitioned into two types:
- P = {P1, P2, …, Pn}, the set consisting of all the processes in the system.
- R = {R1, R2, …, Rm}, the set consisting of all resource types in the system.
● request edge – directed edge P1 Rj
● assignment edge – directed edge Rj Pi
----
● Process
● Resource Type with 4 instances
● Pi requests instance of Rj
● Pi is holding an instance of Rj
● The Resource Allocation Graph (RAG) above is composed of 3 processes and four resources.
● R1 or resource 1 is composed of only one instance
● R2 has 2 instances
● R3 has one instance
● R4 has 3 instances
● P1 requests instance of R1
● P2 is holding an instance of R1
● P2 requests instance of R3
● P3 holds an instance of R3
● There is no deadlock found
EXPLANATION:
If graph contains a cycle
=> if only one instance per resource type, then deadlock.
=> if several instances per resource type, possibility of deadlock.
● The Resource Allocation Graph (RAG) above is composed of 3 processes and four resources.
● R1 or resource 1 is composed of only one instance
● R2 has 2 instances
● R3 has one instance
● R4 has 3 instances
● P1 requests instance of R1
● P2 is holding an instance of R1
● P2 requests instance of R3
● P3 holds an instance of R3
● P3 requests an instance of R1
● There is deadlock based of the RAG no. 2 because all of the instances of R2 are held by the P1 and P2, then P3 is requesting for instances of R2. R2 cannot give any instances to P3 that is why a deadlock occurred.
EXPLANATION:
If graph contains no cycles => no deadlock.
● The Resource Allocation Graph (RAG) above is composed of4 processes and 2 resources.
● R1 and R2 has composed of 2 instances
● P1 requests instance of R1
● P2 is holding an instance of R1
● P3 also holds an instance of R1
● P3 requests an instance of R2
● P4 holds an instance of R2
● P1 also holds an instance of R2
● There is no deadlock.
EXPLANATION:
If a system is in safe state => no deadlocks.
If a system is in unsafe state => possibility of deadlock.
Avoidance => ensure that a system will never enter an unsafe state.
EXPLANATION:
Requires that the system has some additional a priori information available.
● Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.
● The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.
● Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.
● The Resource Allocation Graph (RAG) above is composed of 2 processes and 2 resources.
● P1 holds an instance of R1
● P2 requests an instance of R1
● P1 and P2 may request an instance of R2
EXPLANATION:
● Basic fact:
If a system is in unsafe state => possibility of deadlock.
● The RAG above is compose of 2 resources and 2 processes
● P1 holds an instance of R1
● P2 is requesting an instance of R1
● P2 holds an instance of R2
● P1 may request an instance of R2
EXPLANATION:
Single Instance of Each Resource Type
● Maintain wait-for graph
- Nodes are processes.
- Pi → Pj if Pi is waiting for Pj.
● Periodically invoke an algorithm that searches for a cycle in the graph.
● An algorithm to detect a cycle in a graph requires an order of n^2 operations, where n is the number of vertices in the graph.
Several Instances of a Resource Type
● Available: A vector of length m indicates the number of available resources of each type.
● Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process.
● Request: An n x m matrix indicates the current request of each process. If Request [ij] = k, then process Pi is requesting k more instances of resource type. Rj.
additional...
A Wait-For Graph in computer science is a directed graph used for deadlock detection in operating systems and relational database systems.
In Computer Science, a system that allows concurrent operation of multiple processes and locking of resources and which does not provide mechanisms to avoid or prevent deadlock must support a mechanism to detect deadlocks and an algorithm for recovering from them.
One such deadlock detection algorithm makes use of a Wait-For Graph to track which other processes a process is currently blocking on. In a Wait-for Graph, processes are represented as nodes, and an edge from process Pi to Pj implies Pj is holding a resource that Pi needs and thus Pi is waiting for Pj to release its lock on that resource.
0 comments:
Post a Comment