WikiGalaxy

Personalize

Introduction to Deadlocks

Definition:

A deadlock is a situation in operating systems where two or more processes are unable to proceed because each is waiting for the other to release resources.

Characteristics of Deadlocks:

Mutual Exclusion: Resources cannot be shared.
Hold and Wait: Processes holding resources are waiting for others.
No Preemption: Resources cannot be forcibly taken from processes.
Circular Wait: A closed chain of processes exists, where each process holds at least one resource needed by the next process in the chain.

Deadlock Prevention:

Strategies to ensure that at least one of the necessary conditions for deadlock cannot hold.

Deadlock Avoidance:

Dynamically examine the resource-allocation state to ensure that a circular wait condition can never exist.

Deadlock Detection and Recovery:

Allow the system to enter a deadlock state, detect it, and recover.

Resource Allocation Graph:

A directed graph used to represent the state of resources and processes.

Mutual Exclusion Example

Mutual Exclusion:

In this example, a printer resource cannot be shared between two processes simultaneously.


class Printer {
    private boolean isBusy = false;

    synchronized void print(String document) {
        while (isBusy) {
            try {
                wait();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
        isBusy = true;
        System.out.println("Printing: " + document);
        isBusy = false;
        notifyAll();
    }
}

Explanation:

The synchronized keyword ensures that only one process can use the printer at a time, demonstrating mutual exclusion.

Hold and Wait Example

Hold and Wait:

A process holding a resource waits for additional resources held by other processes.


class Resource {
    synchronized void useResource() {
        // Simulate resource usage
    }
}

class Process extends Thread {
    private Resource resource1;
    private Resource resource2;

    Process(Resource r1, Resource r2) {
        this.resource1 = r1;
        this.resource2 = r2;
    }

    public void run() {
        synchronized (resource1) {
            resource1.useResource();
            synchronized (resource2) {
                resource2.useResource();
            }
        }
    }
}

Explanation:

The process holds resource1 and waits for resource2, demonstrating hold and wait condition.

No Preemption Example

No Preemption:

Resources cannot be forcibly taken from a process; they must be released voluntarily.


class Resource {
    synchronized void requestResource() {
        // Simulate resource request
    }

    synchronized void releaseResource() {
        // Simulate resource release
    }
}

class Process extends Thread {
    private Resource resource;

    Process(Resource r) {
        this.resource = r;
    }

    public void run() {
        resource.requestResource();
        // Simulate processing
        resource.releaseResource();
    }
}

Explanation:

The process requests and releases resources voluntarily, illustrating no preemption.

Circular Wait Example

Circular Wait:

Each process in a set is waiting for a resource held by another process in the set, forming a circular chain.


class Resource {
    synchronized void acquire() {
        // Simulate acquiring resource
    }

    synchronized void release() {
        // Simulate releasing resource
    }
}

class Process extends Thread {
    private Resource resource1;
    private Resource resource2;

    Process(Resource r1, Resource r2) {
        this.resource1 = r1;
        this.resource2 = r2;
    }

    public void run() {
        synchronized (resource1) {
            resource1.acquire();
            synchronized (resource2) {
                resource2.acquire();
            }
        }
    }
}

Explanation:

The code demonstrates a circular wait condition where processes form a cycle by waiting on each other's resources.

Deadlock Prevention Strategy

Deadlock Prevention:

Implementing a strategy to prevent deadlocks by breaking one of the necessary conditions.


class Resource {
    synchronized void requestResource() {
        // Request resource with prevention strategy
    }

    synchronized void releaseResource() {
        // Release resource
    }
}

class Process extends Thread {
    private Resource resource;

    Process(Resource r) {
        this.resource = r;
    }

    public void run() {
        if (tryAcquireResource()) {
            // Use resource
            resource.releaseResource();
        }
    }

    private boolean tryAcquireResource() {
        // Implement prevention logic
        return true;
    }
}

Explanation:

This example uses a strategy to prevent deadlocks by ensuring that the resource acquisition order is maintained.