Explain the various techniques for Deadlock Prevention

Deadlocks are like a nightmare for the programmers who design and write the programs for the multitasking or multiprocessing systems. For them it is very important to know about how to design programs in such a way as to prevent the deadlocks. 

Deadlocks are a more common problem in the distributed systems which involve a use of the concurrency control and distributed transactions. The deadlocks that occur in these systems are termed as the distributed deadlocks. 

It is possible to detect them using either of the following means:

1. Building a global wait for graph from a local one through a deadlock detector.

2. Using distributed algorithms such as the edge chasing.

- An atomic commitment protocol similar to a two phase commit is used for automatically resolving the distributed deadlocks. 

- Therefore, there is no need for any other resolution mechanism or a global wait for graph. 

- But this is possible only in the commitment ordering based distributed environments. 

- For the environments that have 2 – phase locking, a similar automatic global deadlock resolution takes place.

- There is another class of deadlocks called the phantom deadlocks. 

- These are the ones detected in the system because of some internal delays but they actually do not exist during the detection time.

- Today, their exist a number of ways using which the parallelism can be increased where otherwise severe deadlocks might have been caused by the recursive locks. 

- But like for everything else, this also has a price.

- You either have to accept one of these or both i.e., the data corruption or the performance/ overhead. 

- Preemption and lock–reference counting, WFG or wait – for graph are some of the examples of this. 

- These can be followed either by allowing for the data corruption during the preemption or by using version.

- Apart from these heuristic algorithms and the algorithms that can track all the cycles causing the deadlocks can be used for preventing the deadlocks.

- These algorithms even though they don’t offer 100 percent parallelism, they prevent deadlocks by providing an acceptable degree of the performance overhead versus parallelism. 

This example will make it clearer: 

- Consider at a crossing junction there are 2 trains approaching each other. 

- Their collision can be prevented by some just-in-time prevention means. 

- This mean can be person at the crossing having a switch pressing which will allow only one of them to cross on to the succeeding track super passing the other trains that are also waiting. 

- There are following two types of deadlocks:

1. Recursive locks: In such locks, only one thread can pass through it. Any other threads or processes entering the lock need to wait for the initial one to pass through after its task is finished.
2. Non – recursive locks: Here only once a thread can enter the lock. If the same thread again tries to enter the lock without unlocking it, a deadlock can occur.

- There are issues with both of these. 

- The first one does not provides distributed deadlock prevention and the latter one has no concerns for the deadlock prevention. 

- In the first one, if the number of threads trying to enter the lock equals the number of locked threads, then one of the threads has to be assigned as the super one and then only one can execute it till completion. 

- After the execution of the super thread is complete, the condition reverts back from the recursive lock and the super thread removes its status of being super thread and sends a notification to the locker that the condition has to be re-checked. 

Explain briefly Deadlock Avoidance and Detection?

Deadlocks are a serious issue that needs to be avoided since it can cause the whole system to hang or crash.

What is Deadlock Avoidance?

- Avoiding a deadlock is possible only if certain information regarding the processes is available with the operating system.
- This information has to be made available to the OS just before the resources are allocated to the processes.
- These are the processes that are to be consumed by the process in its lifetime.
- For every resource request made by the process, any potential threats are checked by the system i.e., whether granting the request of the process will send it in to an unsafe zone or not.
- If it is so then there are possibilities that the system could enter a deadlock.
- Therefore, only those requests are granted by the process that will ensure a safe state of the process.
- It is important for the system to determine whether the next level of the process will be safe or unsafe.
- There are 3 things that the operating system must know at any before or after the execution of the process:
1. The currently available resources.
2. The resources currently allocated to the processes.
3. Resources to be required and released in the future by these processes.

- It is possible that a process might be in an unsafe state but still may not cause a deadlock.
- By the notion of the safe and unsafe state of the process we refer to the system’s ability of entering in to a deadlock.
An example will make it clearer:
- Consider a resource A requested by a process which would make the process state unsafe.
- At the same time it releases another resource say B preventing the circular wait of the resources.
- In such a situation, the system is said to be in an unsafe state though not necessarily in a deadlock.
- There are various algorithms that have been designed for deadlock avoidance and one such is the banker’s algorithm.
- To use this algorithm knowledge about the resource usage limit is required in advance.
-  It is impossible for most of the systems to know what a process will request for in advance.
- This only implies that the deadlock avoidance is also not possible here.
- There are other two algorithms for achieving this task namely wound/ wait and wait/ die algorithms.
- Each of them makes use of a symmetry breaking technique.

What is Deadlock Detection?

- Deadlocks are free to occur under the implementation of this concept.
- Then through the state of the system, the occurrence of the deadlock is confirmed and subsequently mended.
- Here, the resource allocation activities are tracked along with the process states by certain algorithms.
- After this, the algorithm is used for removing the deadlock.
- Deadlock detection is quite easy since the OS scheduler knows about the resources that have been locked by the processes.
- Model checking is one of the techniques used for deadlock detection.
- In this a finite state model is created up on which a progress analysis of the process is carried out and all the terminal sets of the model are found.
- Each of these stands for a deadlock.
- Correction of the deadlock can be done by any of the below mentioned methods after the deadlock has been detected:
1. Process termination: This is about aborting one or more of the processes that cause the deadlock thus ensuring a certain and speedy removal of the deadlock. But this method might prove to be a little expensive because of the loss of the partial computations.
2. Resource preemption: This is about a successive preemption of the allocated resources until the breakdown of the deadlock.

Overview Of Mutual Exclusions in Operating Systems

A way of making sure that if one process is using a shared modifiable data, the other processes will be excluded from doing the same thing.
Formally, while one process executes the shared variable, all other processes desiring to do so at the same time moment should be kept waiting; when that process has finished executing the shared variable, one of the processes waiting; while that process has finished executing the shared variable, one of the processes waiting to do so should be allowed to proceed. In this fashion, each process executing the shared data (variables) excludes all others from doing so simultaneously. This is called Mutual Exclusion.
Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code where a process or thread accesses a common resource. The critical section by itself is not a mechanism or algorithm for mutual exclusion. A program, process, or thread can have critical section in it without any mechanism or algorithm, which implements mutual exclusion.
Examples of such resources are fine-grained flags, counters or queues, used to communicate between code that runs concurrently, such as an application and its interrupt handlers. The problem is acute because a thread can be stopped or started at any time.

How Mutual Exclusion is Done ?
We need to stop the two threads from working on the same data at the same time. The most common way to do this today is by using locks. A lock can be either locked or unlocked. As long as you do not forget to lock or unlock the door, this algorithms guarantees mutual exclusion and protects the so called critical region.
C:
1. omp_set_lock (&my_lock);
2. i++;
3. omp_unset_lock (&my_lock);
Actually, the lock needs to be initialized beforehand and destroyed sometime afterwards as well, but that's not too difficult either.
C:
1. #pragma omp critical
2. {
3. i++;
4. }
Or even simpler, like this:
C:
1. #pragma omp atomic
2. i++;
This basically does the same thing, except you do not need to worry about initialization and destruction of the lock and you cannot forget to unlock the mutex accidentally.

Overview of Race Conditions in Operating Systems

A race condition happens when a system depends on something being done outside of its control before the system reaches a point where it needs to use the results of that something, and there's no way to guarantee that that something will actually be finished when the system needs it.
For example, suppose there's a person who runs a program every morning that prints letters that have been queued throughout the previous day. There's another person in another department who runs a program that queues a letter, and then offers to let the person modify it while it's sitting in the printing queue. If the person runs this program too early in the day (before the printing program gets run), they're essentially in a "race" to finish their work before the printing program runs.

Symptoms Of Race Condition :

The most common symptom of a race condition is unpredictable values of variables that are shared between multiple threads. This results from the unpredictability of the order in which the threads execute. Sometime one thread wins, and sometime the other thread wins. At other times, execution works correctly. Also, if each thread is executed separately, the variable value behaves correctly.
While many different devices are configured to allow multitasking, there is still an internal process that creates a hierarchy of functions. In order for certain functions to take place, other functions must occur beforehand. While the end user perceives that all the functions may appear to be taking place at the same time, this is not necessarily the case.
One common example of a race condition has to do with the processing of data. If a system receives commands to read existing data while writing new data, this can lead to a conflict that causes the system to shut down in some manner. The system may display some type of error message if the amount of data being processed placed an undue strain on available resources, or the system may simply shut down. When this happens, it is usually a good idea to reboot the system and begin the sequence again. If the amount of data being processed is considerable, it may be better to allow the assimilation of the new data to be completed before attempting to read any of the currently stored data.