Deadlocks in Computing

A deadlock is a situation in which two or more processes become stuck, each waiting for resources held by the other, preventing further progress. Without external intervention, these processes remain indefinitely blocked.


1. Conditions for Deadlock

A deadlock occurs when the following four conditions hold simultaneously (Coffman’s Conditions):


1. Mutual Exclusion – Some resources can only be used by one process at a time.

2. Hold and Wait – A process holding a resource is waiting for additional resources held by other processes.

3. No Preemption – Resources cannot be forcibly taken from a process; they must be released voluntarily.

4. Circular Wait – A set of processes is waiting in a circular chain, where each process holds a resource needed by the next process in the cycle.


2. Preventing Deadlocks

To prevent deadlocks, at least one of the four conditions must be eliminated:


- Avoid Mutual Exclusion: Where possible, allow multiple processes to share resources (e.g., read-only files).

- Eliminate Hold and Wait: Require processes to request all needed resources at once before execution begins.

- Enable Preemption: Allow resources to be forcibly taken from processes when necessary.

- Break Circular Wait: Impose a strict ordering on resource allocation, preventing circular dependencies.


3. Deadlock Avoidance

Rather than outright prevention, deadlock avoidance ensures that resource allocation does not lead to a deadlock.


- Banker’s Algorithm: A process is allowed to proceed only if granting its requested resources leaves the system in a "safe state" (i.e., a state where all processes can eventually complete).

- Resource Allocation Graph (RAG): Tracks resource dependencies and prevents circular waits by blocking unsafe allocations.


4. Detecting and Resolving Deadlocks

When prevention and avoidance are not feasible, the system must detect and recover from deadlocks.


- Detection Techniques:


Periodically examine resource allocation graphs to identify circular waits.

Check available and allocated resources to determine if any processes are indefinitely waiting.

- Recovery Strategies:


Terminate Processes: Kill one or more processes to break the deadlock.

Preempt Resources: Temporarily take resources from certain processes and reallocate them to allow execution to continue.


Comments

Post a Comment

Popular posts from this blog

Absolute and relative path in HTML pages

HTML documents can have relative or absolute links to other web pages. Relative links keeps a visitor on the same web site. Relative links are pointers to other web pages on the same web site. They just contain this page filename. Absolute links on other hand contain full path including protocol and domain name to access the page. Absolute links can point to the same web site or they can point to a different web site.
Read more

Errors

It is a good idea to send errors in production environment to error log. Errors may contain sensitive information. Even so errors maybe helpful to development team or to QA team, errors need to be suppressed in production environment for viewing by everyone. Errors are good way to troubleshoot an issue therefore only trusted people can have access to this information. If not a trusted person get an access to this information, this information maybe used against the company and for a personal benefit. What to do in a case when there are more servers than one? Even so it is possible to inspect the log files in a single server, however it is impossible to do so when there is more than one server is available and web traffic is redirected to a different server each time. Log aggregation is needed in this case. All of the logs will be send to a central location. Logs may contain sensitive information. Please consult your company lawyer of how long logs can be stored, because logs can be use...
Read more

goto PHP operator

goto operator will skip execution of code and continue execution of a code that follows a label to which goto operator points to. If code has many goto operators, than this code probably needs a revision. It is possible to write code that executes without goto operators.
Read more