WikiGalaxy
Deadlock Avoidance in Operating Systems
Overview:
Deadlock avoidance is a strategy used by operating systems to ensure that a system will never enter a deadlock state. It requires that the system has some additional information in advance about how resources are to be requested.
- Preemptive and non-preemptive resource allocation.
- Ensures that resources are allocated safely.
- Requires knowledge of future requests.
Banker's Algorithm
Concept:
The Banker's Algorithm is a deadlock avoidance algorithm that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources and then makes an "s-state" check to test for possible activities before deciding whether allocation should continue.
- Works like a bank lending system.
- Checks if the system is in a safe state after allocation.
- Prevents unsafe allocations.
// Example of Banker's Algorithm
int[] available = {3, 3, 2};
int[][] max = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};
int[][] allocation = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
int[][] need = new int[5][3];
// Calculating Need matrix
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
need[i][j] = max[i][j] - allocation[i][j];
}
}
Explanation:
The Banker's Algorithm calculates the need for each process and checks if the system can satisfy the need with the available resources. If it can, the system is in a safe state, and the resources are allocated.
Safe State
Concept:
A system is in a safe state if there exists a safe sequence of all processes such that for each process, the resources that it can still request can be satisfied by the currently available resources plus the resources held by all preceding processes in the sequence.
- Ensures no deadlock occurs.
- All processes can complete without waiting indefinitely.
- Determined by the Banker's Algorithm.
// Checking Safe State
boolean isSafe(int[] available, int[][] max, int[][] allocation) {
int[] work = available.clone();
boolean[] finish = new boolean[allocation.length];
int[][] need = calculateNeed(max, allocation);
int count = 0;
while (count < allocation.length) {
boolean found = false;
for (int i = 0; i < allocation.length; i++) {
if (!finish[i]) {
int j;
for (j = 0; j < work.length; j++) {
if (need[i][j] > work[j]) break;
}
if (j == work.length) {
for (int k = 0; k < work.length; k++) {
work[k] += allocation[i][k];
}
finish[i] = true;
found = true;
count++;
}
}
}
if (!found) return false;
}
return true;
}
Explanation:
The above code checks if the system is in a safe state by simulating resource allocation and verifying that all processes can complete without causing a deadlock.
Resource Allocation Graph
Concept:
A Resource Allocation Graph (RAG) is a directed graph used to represent the state of a system in terms of processes and resources. It is useful for detecting deadlocks in systems with a single instance of each resource type.
- Vertices represent processes and resources.
- Edges represent allocation and request relationships.
- Cycle detection can indicate a potential deadlock.
// Example of Resource Allocation Graph
class Graph {
private final Map> adjList = new HashMap<>();
void addEdge(String start, String end) {
adjList.computeIfAbsent(start, k -> new ArrayList<>()).add(end);
}
boolean hasCycle() {
Set visited = new HashSet<>();
Set recStack = new HashSet<>();
for (String node : adjList.keySet()) {
if (hasCycleUtil(node, visited, recStack)) {
return true;
}
}
return false;
}
private boolean hasCycleUtil(String node, Set visited, Set recStack) {
if (recStack.contains(node)) return true;
if (visited.contains(node)) return false;
visited.add(node);
recStack.add(node);
if (adjList.containsKey(node)) {
for (String neighbor : adjList.get(node)) {
if (hasCycleUtil(neighbor, visited, recStack)) {
return true;
}
}
}
recStack.remove(node);
return false;
}
}
Explanation:
The code represents a Resource Allocation Graph and checks for cycles using depth-first search. If a cycle is detected, it indicates a potential deadlock in the system.
Wait-Die and Wound-Wait Schemes
Concept:
The Wait-Die and Wound-Wait schemes are preemptive techniques used to handle deadlocks in systems by ordering processes based on timestamps.
- Wait-Die: Older process waits; younger process is aborted.
- Wound-Wait: Older process preempts younger process; younger waits.
- Both schemes prevent circular wait conditions.
// Example of Wait-Die and Wound-Wait Scheme
class Process {
int id;
int timestamp;
Process(int id, int timestamp) {
this.id = id;
this.timestamp = timestamp;
}
}
boolean waitDie(Process p1, Process p2) {
if (p1.timestamp < p2.timestamp) {
// p1 is older
return true; // p1 waits
} else {
// p1 is younger
return false; // p1 is aborted
}
}
boolean woundWait(Process p1, Process p2) {
if (p1.timestamp < p2.timestamp) {
// p1 is older
return false; // p2 is aborted
} else {
// p1 is younger
return true; // p1 waits
}
}
Explanation:
The code implements the Wait-Die and Wound-Wait schemes by comparing timestamps of processes to decide whether a process should wait or be aborted, thus preventing deadlocks.
Priority-based Resource Allocation
Concept:
Priority-based resource allocation assigns priorities to processes and resources, allowing higher-priority processes to preempt lower-priority ones, thus avoiding deadlock situations.
- Processes are assigned priority levels.
- High-priority processes can preempt resources.
- Prevents deadlocks by avoiding circular wait.
// Example of Priority-based Resource Allocation
class Process implements Comparable {
int id;
int priority;
Process(int id, int priority) {
this.id = id;
this.priority = priority;
}
@Override
public int compareTo(Process other) {
return Integer.compare(this.priority, other.priority);
}
}
void allocateResources(List processes) {
Collections.sort(processes);
for (Process process : processes) {
// Allocate resources based on priority
System.out.println("Allocating resources to process: " + process.id);
}
}
Explanation:
In this example, processes are sorted based on their priority, and resources are allocated accordingly, ensuring that higher-priority processes can proceed without being blocked by lower-priority ones.
Circular Wait Prevention
Concept:
Circular wait prevention is a method to avoid deadlocks by ensuring that a circular chain of processes, each waiting for a resource held by the next process in the chain, does not exist.
- Imposes a total ordering on resource acquisition.
- Prevents the formation of a circular wait condition.
- Ensures resources are acquired in a specific order.
// Example of Circular Wait Prevention
class Resource {
int id;
Resource(int id) {
this.id = id;
}
}
class Process {
int id;
void acquireResources(Resource... resources) {
Arrays.sort(resources, Comparator.comparingInt(r -> r.id));
for (Resource resource : resources) {
System.out.println("Process " + id + " acquiring resource " + resource.id);
}
}
}
Explanation:
The code demonstrates circular wait prevention by sorting resources based on their IDs and acquiring them in a specific order, thereby avoiding the possibility of forming a circular wait condition.
Resource Preemption
Concept:
Resource preemption involves temporarily taking resources away from one process and allocating them to another to resolve deadlock situations. This approach requires careful handling to ensure system stability.
- Allows resources to be reallocated to prevent deadlocks.
- Requires rollback and process state management.
- Used as a last resort in deadlock resolution.
// Example of Resource Preemption
class ResourceManager {
Map> processResources = new HashMap<>();
void preemptResource(int resourceId, int fromProcessId, int toProcessId) {
if (processResources.containsKey(fromProcessId)) {
List resources = processResources.get(fromProcessId);
if (resources.remove((Integer) resourceId)) {
System.out.println("Resource " + resourceId + " preempted from Process " + fromProcessId + " to Process " + toProcessId);
processResources.computeIfAbsent(toProcessId, k -> new ArrayList<>()).add(resourceId);
}
}
}
}
Explanation:
This code snippet shows how a resource can be preempted from one process and given to another. This is useful in resolving deadlocks but must be done with caution to maintain system integrity.
