What is deadlock?

When a group of processes get stuck because they are each holding a resource and waiting to obtain a resource that is being held by another process, this is known as a deadlock in the system. As a result, there is a cyclic dependency that prevents any further processing.

What are the necessary conditions for a deadlock to occur?

If all four of the following conditions are met at the same time, a deadlock may result:

• Mutual Exclusion: One resource must be kept in a non-shareable state at all times.
• Wait and Hold: When a process has at least one resource, it waits to obtain more resources that are being held by other processes.
• No Preemption: A process that is in possession of resources cannot have them taken away by force.
• Circular Wait: A set of processes are waiting for each other in a circular chain.

How can deadlocks be prevented?

Preventing deadlock entails making sure that at least one of the conditions for deadlock is not met:

• Mutual Exclusion: Whenever feasible, make use of resources that can be shared.
• Hold and Wait: Make sure that all necessary resources are requested at once by processes.
• No Preemption: Permit resource preemption.
• Circular Wait: To avoid circular dependencies, enforce an ordering on resource requests.

What is a resource allocation graph (RAG)? How is it used to detect deadlocks?

A directed graph that shows how resources are distributed within a system is called a resource allocation graph:

• Circles are used to symbolize processes.
• Squares are used to symbolize resources.
• A request is indicated by an edge from a process to a resource, and allocation is indicated by an edge from a resource to a process.
• A deadlock occurs if there is a cycle in the graph and resources cannot be shared.

What is deadlock avoidance? How does the Banker’s Algorithm work?

Deadlock avoidance makes ensuring that a system never gets into an unsafe scenario where deadlocks could occur.

• A strategy that dynamically evaluates resource requests is the Banker’s Algorithm, which does this by: Confirming whether the request can be approved while maintaining system security.
• A state is “safe” if there exists a sequence of process execution such that each process may complete utilizing currently available and requested resources.

How does the operating system detect deadlocks?

• The operating system periodically looks for cycles in a wait-for graph in systems that use deadlock detection.
• Collapsing resource nodes in the resource allocation graph yields the wait-for graph.
• There is a deadlock if a cycle is found.

What are the differences between deadlock and starvation?

• Deadlock: Every process in the group waits endlessly for resources that are shared by all of them.
• Starvation: When higher-priority processes are repeatedly served, a process waits endlessly.
• Key Difference: While starving results from uneven distribution of resources, deadlock requires a loop of dependency.

How can a system recover from a deadlock?

Recovery techniques consist of:

Termination of Process:

• End all processes that are stuck in a deadlock.
• Stop each process in turn until the stalemate is fixed.

Resource preamption:

• To break the loop, preempt resources from processes and assign them to other users.

Is it possible to design a system completely free of deadlocks? Why or why not?

Theoretically, yes, by rigorously implementing tactics like avoidance or deadlock prevention. But in reality, it is difficult because:

• It might result in less system efficiency.
• Since resource requirements are frequently erratic, strict ordering or preallocation is impossible.

Can deadlocks occur in single-threaded systems? Why or why not?

No, deadlocks cannot occur in single-threaded systems because there’s no inter-process dependency or waiting on shared resources by multiple threads or processes.

Explain the concept of a “safe state” in deadlock avoidance.

safe state is a state of the system where it is possible to allocate resources to all processes in some order and still avoid a deadlock.

• If granting a resource request results in an unsafe state, the request is denied.

What are the trade-offs between deadlock prevention and deadlock detection?

Deadlock Prevention:

• Pros: Prevents deadlocks entirely.
• Cons: May lead to under-utilization of resources due to strict rules.

Deadlock Detection:

• Pros: Better resource utilization.
• Cons: Overhead in detecting deadlocks and recovering from them.

What is a livelock, and how is it different from a deadlock?

• Livelock: No process advances despite the fact that other processes are causing them to actively change their states.
• Deadlock: Circular dependencies cause processes to remain in a waiting state indefinitely.
• Important Distinction: Processes are passive in deadlock and stay active but ineffective in livelock.

How can priority inversion lead to deadlocks? How is it resolved?

Priority Inversion: Occurs when a higher-priority process is waiting for a resource held by a lower-priority process.This can escalate into a deadlock if intermediate processes are involved.

Solution: Use priority inheritance, where the lower-priority process temporarily inherits the higher priority to release the resource quickly.

Given this resource allocation table, determine if the system is in a deadlock state.

Walk through steps like:

1. Calculate available resources.
2. Check if each process can finish with the available resources.
3. Identify any remaining processes that cannot proceed.
   If no processes can proceed and a circular dependency exists, the system is in deadlock.