Skip to main content

Deadlock: Cause and Prevention, All you need to know

Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

There are 4 conditions necessary for the occurrence of a deadlock.

1. Mutual Exclusion:

When two people meet in the landings, they can’t just walk through because there is space only for one person. This condition to allow only one person (or process) to use the step between them (or the resource) is the first condition necessary for the occurrence of the deadlock.

2. Hold and Wait:

When the 2 people refuse to retreat and hold their grounds, it is called holding. This is the next necessary condition for the deadlock.

3. No Preemption:

For resolving the deadlock one can simply cancel one of the processes for others to continue. But the Operating System doesn’t do so. It allocates the resources to the processors for as much time as needed until the task is completed. Hence, there is no temporary reallocation of resources. It is the third condition for deadlock.

4. Circular Wait:

When the two people refuse to retreat and wait for each other to retreat, so that they can complete their task, it is called circular wait. It is the last condition for the deadlock to occur.


There are two approaches to breaking a Deadlock:

1. Process Termination: To eliminate the deadlock, we can simply kill one or more processes. For this, we use two methods:

(a). Abort all the Deadlocked Processes:

Aborting all the processes will certainly break the deadlock, but with a great expense. The deadlocked processes may have computed for a long time and the result of those partial computations must be discarded and there is a probability to recalculate them later.

(b). Abort one process at a time until the deadlock is eliminated:

Abort one deadlocked process at a time, until the deadlock cycle is eliminated from the system. Due to this method, there may be considerable overhead, because after aborting each process, we have to run a deadlock detection algorithm to check whether any processes are still deadlocked.


2. Resource Preemption: To eliminate deadlocks using resource preemption, we preempt some resources from processes and give those resources to other processes. This method will raise three issues –

(a). Selecting a victim:

We must determine which resources and which processes are to be preempted and also the order to minimize the cost.

(b). Rollback:

We must determine what should be done with the process from which resources are preempted. One simple idea is total rollback. That means to abort the process and restart it.

(c). Starvation:

In a system, it may happen that the same process is always picked as a victim. As a result, that process will never complete its designated task. This situation is called Starvation and must be avoided. One solution is that a process must be picked as a victim only a finite number of times.
Labels:

Comments

Post a Comment

Popular posts from this blog

Postfix Evaluation(Single or Multi Digit) using STACK in C

POSTFIX EVALUATION WITH SINGLE OR MULTI DIGIT: Students find difficulties in finding the correct code for Postfix evaluation using Stack which works for Single as well for multidigit also; So here is the Question Format Given::- Question_2; Data_Structure:  Write a C program to evaluate the following POSTFIX expression. Use STACK to solve this problem.  INPUT: 5 6 2 + * 12 4 / -  OUTPUT: 37 Basic Understanding: Here is the Correct code:
1 comment
Read more

STACK in C

IMPLEMENTATION OF STACK USING ARRAY Here is Example of Source Code of Data Structure-1, Question 1: Data_structure :  Write a C program to implement STACK using an array. This program must include the following functions in it. Write a function for “Push” operation.   Write a function for “Pop” operation.  Write a function for “Display” operation which prints the content of the STACK.    Basic Understanding : Push and Pop Operation: Here is How to Implement:                                                   
4 comments
Read more

Combinatorics For Programmers and Coders

Hey! Computer Geeks! Here we will discuss two or more special numbers that made the way of coding easy, Introduction to Catalan Numbers: The Catalan numbers are a sequence of positive integers that appear in many counting problems in combinatorics. They count certain types of lattice paths, permutations, binary trees, and many other combinatorial objects. They satisfy a fundamental recurrence relation and have a closed-form formula in terms of binomial coefficients. The Catalan number Cn describes, among other things: The number of binary trees with n nodes, The number of ways in which parentheses can be placed in a sequence of n+ 1 numbers to be multiplied two at a time, The number of well-formed reverse Polish expressions with n operands and n + 1 operators, The number of paths in a grid from (0, 0) to (n, n), increasing just one coordinate by one at each step, without crossing the main diagonal,  The number of n-bit sequences that the number of 1s never exceeds the n...
1 comment
Read more