Introduction to Deadlock in Operating System

Introduction

Numerous processes—programs now being run—are constantly active in an operating system. The computer's operation depends on each of these processes. It outlines the fundamental task that the system must carry out. Processes execute sequentially.

Some resources are needed for these procedures to operate or complete their execution. Here, the sequence is sequential. The process initially makes a resource request. The OS assigns the resource if it's available. If not, the procedure must be delayed. The resource is released once the process has consumed it. When there is difficulty during the waiting and release, a stalemate occurs.

What is Deadlock?

In an operating system, a deadlock occurs when a process waiting for a resource cannot be executed because the help is being used to complete another process that is now holding the resource. Additionally, many other processes can also be awaiting the delivery of a resource. There is a deadlock situation.

Assume that P1 and P2 are the names of two processes. They are given resources R1 and R2, respectively. Therefore, if P1 wants R2 to finish its execution, but P2 is holding onto it, P1 must wait. Similar to P1, P2 might be anticipating R1, who is held by P1. P2 must hold off until P1 releases the resource. As a result, there is a deadlock scenario, and neither process can finish running. The system can stop responding while the processes are halted.

Deadlock Requirements

For there to be a deadlock, several requirements must be met. These are what they are:

1. Mutual Exclusion

In other words, resources might be employed in mutually exclusive ways. As a result, two processes won't be able to access the same resource simultaneously. A process must acquire at least one resource in a non-shareable mode. If not, many processes won't be able to access a resource simultaneously.

2. Wait and Hold

A process must hold at least one resource for its execution in this situation. Another resource being held by another process is awaited by this one.

3.No Pre-emption

This implies that a resource cannot be preempted if assigned to a certain process. The resource cannot be assigned to another process unless it is relinquished. For another process to use the resource, it must be released voluntarily.

4. Circular Wait

Several processes are awaiting a resource that has been assigned to one process in this scenario. The final process waits for the first process to release a resource during this cycle of waiting. For instance, process P1 waits for process P2, which is waiting for resource P3, which is allotted to process P1. P4 is now holding a resource that P3 is awaiting. P4 is awaiting the release of a resource from P1.

We'll now concentrate on the various methods for breaking deadlocks.

Operating System Deadlock Detection

In deadlock detection, the operating system anticipates the occurrence of a deadlock condition and then identifies it. Here, no techniques for preventing or avoiding deadlocks are used. The OS then determines whether a stalemate exists. If found, recovery techniques are used. By using the Resource Allocation graph, deadlocks are located. A stalemate will unquestionably happen if a process cycle is discovered for resources with a single instance. Cycle detection is insufficient to guarantee the detection of a stalemate if the resources have numerous instances. In this situation, a safety algorithm must be applied. This algorithm divides the resource allocation graph into two: a request matrix and an allocation matrix.

Deadlock Avoidance

By stifling the initial conditions that lead to a stalemate, an OS can avoid one. As follows:

1) Through Mutual Exclusion

A resource will not be mutually exclusive if it may be used by many processes simultaneously. There won't be a need for the process to wait for a resource. As a result, a deadlock can be avoided. A technique called spooling can stop mutual exclusion.

Printers will function with spooling. The tasks that various processes have submitted to the printer are stored in memory. The printer completes the tasks following the FCFS (First Come First Serve) principle.

Thus, there is no need for the procedures to wait for the printer. This technique may prevent mutual exclusion, but not for all resources.

Therefore, reciprocal exclusion cannot be effectively avoided.

2) Doing away with waiting and holding

By allocating all necessary resources to the processes before they begin to run, the problem can be avoided. In this manner, once a process begins execution, it does not need to wait for any resources. In this manner, once a process begins execution, it does not need to wait for any resources. But this could result in minimal system resource utilization.

Let's say a procedure calls for a printer to complete a task at a separate time. However, it currently has that printer allocated to it. As a result, until the operation is complete, that printer will be restricted. In addition, several resources could need more than one resource at once. Starvation is another danger. This is because after a process has been granted a resource, it may retain it for a long time before using it. Thus, it is impossible to avoid the hold and wait.

3) Avoiding Pre-emption

A deadlock may result when a process cannot be terminated once it has begun running. Certain procedures may be preempted in terms of resources. You can do this when a process with a greater priority needs the resource. However, you can only accomplish this if you save the state of the process from which the resource is being taken. At a later time, you might restart that procedure. However, this approach could be difficult.

4) Removal of Circular Waiting

By numbering the resources, the disease can be cured. The process won't be allowed to request a resource with a lower priority. Thus this priority number will be helpful. Therefore, it is impossible to request a resource that is already in use by another process.

5) Avoiding Deadlock

Using Banker's algorithm, deadlocks might be avoided. Here, the process needs to alert each sort of resource that it needs. The algorithm examines the requests for processes. The resources will be distributed in the event of a safe state. If not, no allocation will be made.

The following inputs will supply the algorithm:

  • The total amount of resources used by processes
  • The greatest quantity of freely accessible resources
  • The resources currently allotted to the processes

It will be approved if the requested resource is less than or equal to the process's maximum requirement. Resources will also be provided if the requested number of resources is less than or equal to the maximum number of free resources

Ostrich Algorithm for Deadlock Ignorance

An algorithm known as the Ostrich algorithm ignores deadlocks. The operating system assumes no chances of running into a stalemate when using this method. It's comparable to how an ostrich will bury its head in the ground and act as if nothing is wrong. This approach is employed when preventing deadlocks is expensive, and they don't happen often.

The Windows and Unix operating systems use this algorithm. Restarting the system resolves the deadlocks.

Conclusion

Operating system deadlocks are a frequent source of issues. Some operating systems treat them differently, while others take the Ostrich approach and disregard them. The system may save the states of the processes and roll back to the previous checkpoint if a stalemate is possible. It will distribute resources in a different way to prevent repeated deadlocks.