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.

What are the various Desk Scheduling methods?

About Disk Scheduling

The I/O system has got the following layers:

1. User processes: The functions of this layer including making I/O calls, formatting the I/O and spooling.
2. Device independent software: Functions are naming, blocking, protection, allocating and buffering.
3. Device drivers: Functions include setting up the device registers and checking their status.
4. Interrupt handlers: These perform the function of waking up the I/O drivers up on the completion of the I/O.
5. Hardware: Performing the I/O operations.

- Disk drives can be pictured as large 1 – D array consisting of logical blocks that are smallest unit of transfer.  

- These blocks are mapped in to the disk sectors in a sequential manner. 

- Mapping is done in the same manner. 

- The responsibility of using the hardware efficiently is the duty of the operating system for the disk drives for increasing the speed of access and bandwidth of the disk. 

Algorithms for Scheduling Disk Requests

There are several algorithms existing for the scheduling of the disk requests:

Ø  SSTF: 

- In this method the request having the minimum seek time is selected from the present head position. 

- This method is a modification of the SJF (shortest job first) scheduling and therefore contains some possibility of process starvation.

Ø  SCAN: 

- From one end of the disk, the disk arm starts and continues in the direction of the other end, serving to the requests till the opposite end. 

- At this end the head is reversed and the process continues. 

- This is sometimes called as the elevator algorithm.

Ø  C – SCAN: 

- A better algorithm then the previous one. 

- This one offers a more uniform waiting time than the previous one. 

- The movement of the head is from one end to another while it services the requests encountered along the way. 

- However, the difference is that when it comes to the other it straightaway goes to the beginning without heeding to any of the requests in the way and then again starts. 

- The cylinders are treated as the circular list wrapped around last and the first cylinder.

Ø  C – Look: 

- This is a modified version of the C – SCAN. 

- Here the arm or the head travels only up to the last request rather than going till the far end. 

- Then immediately the direction is reversed and the process continues.

- For disk scheduling it is important that the method be selected as per the requirements only. 

- The first one is the most commonly used and appeals to the needs naturally. 

- For a system where often there is a heavy load on the disk, the SCAN and C- SCAN methods can help. 

- The number as well as the kind of requests affects the performance in a number of ways.

- On the other hand, the file – allocation method influences the requests for the disk services. 

- These algorithms have to be written as an individual module of the OS so that if required it can be replaced with a different one easily. 

- As a default algorithm, the LOOK or the SSTF is the most reasonable choice. 

Ways to attach to a disk

There are two ways of attaching the disk:

Ø  Network attached: This attachment is made via a network. This is called the network attached storage. All such connected storage devices together form the storage area network.

Ø  Host attached: This attachment is made via the I/O port.

All these disk scheduling methods are for the optimization of the secondary storage access and for making the whole system efficient. 

What is meant by Deadlock? List the necessary conditions for arising deadlocks?

Consider two competing processes or actions in a situation where both of them wait for each other to be done and so neither of them ever finish. Such a situation is called a deadlock. 

- When the number of competing processes is exactly two, then it is said to be a ‘deadly embrace’. 

- The two involved competing actions tend to move towards some sort of tragedy which might be mutual extinction or mutual death. 

"In operating systems a situation occurs where two threads or processes enter the waiting state at the same time because of the resource that they both want is being used by some other process that also in waiting state for some resource being held by another process in waiting state and so on". 

- It so happens that the process is then unable to change its state since the resources it requires are being used by the other processes which is then keeping the process in waiting state indefinitely. 

- The system is now in a deadlock. 

- Systems such as the distributed systems, parallel computing systems, multi-processing systems face the problem of being in a deadlock quite often. 

- This is so because here the hardware and software locks are purposed for handling the resources that are shared and implementing the process synchronization. 

- Deadlocks may also occur in telecommunication systems because of the corrupt signals and their loss rather than resource contention. 

- A deadlock situation can be compared to problems such as that of the catch-22 or chicken or egg problem. 

- A deadlock can also occur in a circular chain pattern. 

- For example, consider a computer having 3 processes and corresponding 3 CD drives i.e., one held by each process. 

- Now all the three processes would be in a deadlock if they all request another drive.

Conditions for a Deadlock to arise

There are certain conditions that should be there for a deadlock to arise:

1. Mutual exclusion: There has to be at least one resource that cannot be shared. So that only one process would use at any given time.
2. Resource holding (or hold and wait): There should be at least one resource held by a process that in turn should be request more resources that are being held by other processes.
3. No preemption: Once the resources have been allocated, they should not de-allocated by the operating system. The condition is that the process holding the resource must release it voluntarily.
4. Circular wait: A circular chain of processes must be formed as explained in the earlier example.

"These 4 conditions for deadlock are collectively called the ‘Coffman conditions’. If any of these conditions is not met, a deadlock can’t occur".

- Handling a deadlock is an important capability of the operating systems. 

- However, there are many modern operating systems that still cannot avoid deadlocks. 

- On occurrence of a deadlock many non-standard approaches are followed by different operating systems for handling it. 

- Many of these approaches try to avoid at least one of the Coffman conditions (generally the 4^th one). 

- Below we discuss some of the approaches:

1. Ignoring deadlock
2. Detection
3. Prevention
4. Avoidance

- There is a second kind of deadlocks called the ‘distributed deadlock’ and it is common where concurrency control is used or we can say in the distributed systems. 

Introduction to Monitors

Monitors :
- Consist of private data and operations on that data.
- It can contain types, constants, variables and procedures.
- Only the procedures explicitly marked can be seen outside the monitor.
- The monitor body allows the private data to be initialized.
- The compiler enforces mutual exclusion on a particular monitor.
- Each monitor has a boundary queue, and processes wanting to call a monitor routine
join this queue if the monitor is already in use.
- Monitors are an improvement over conditional critical regions because all the code
that accesses the shared data is localized.

To allow a process to wait within the monitor, a condition variable must be declared, as: condition x,y.
Condition variable can only be used with the operations wait and signal.
The operation x.wait()means that the process invoking this operation is suspended until another process invokes. Also called delay function.
The operation x.signal()resumes exactly one suspended process. If no process is suspended, then the signal operation has no effect.Also called resume function.

Monitor Implementation using Semaphores
- For each condition variable x, we have:
semaphore x-sem; // (initially = 0)
int x-count = 0;
- The operation x.wait can be implemented as:
x-count++;
if (next-count > 0)
signal(next);
else
signal(mutex);
wait(x-sem);
x-count--;
- The operation x.signal can be implemented as:
if (x-count > 0)
{
next-count++;
signal(x-sem);
wait(next);
next-count--;
}