Deadlock and Starvation

Intro

The flow is as follows:

1. Ensured process isolation.
2. Ensured isolation, but there is a need to communicate between processes.
3. Provides semaphore.
4. Given exclusive rights to resources, there are cases where processes are sometimes blocked when they have resources.
5. Resources are limited.
6. As it builds up, the system doesn't work properly.

Deadlock

The permanent blocking of a set of processes that either compete for system resources
or communicate with each other.

Cases

It is a diagram illustrating a typical deadlock case.

picture [1] permanent deadlock

But it doesn’t really look as pretty as the picture above.

picture [2] The load: illustrate of deadlock

It’s a different situation this time.

In the case of a car on the road, it can be solved by reversing.
But the program can’t reverse.

Suppose there are processes P and Q .
And look at the next picture.
The part where the arrow progression is deflected to 90 degrees is the context switching .

picture [3] deadlock example

If process goes to the red arrow path, deadlock does not occur.
If process goes to the blue arrow path, deadlock will always occur.
Get corresponds to semWait ,
Rel corresponds to semSignal .

Resources categories

To avoid deadlocks, you need to know the nature of the resource.
There are two main categories.

reusable

It is a resource that continues to be used a time quantum.
Like cpu, memory, i/O, etc …

consumable

created and destroyed resources.
Representatively, there is communication.
Like interrupt, message, etc …

Condition

These are the conditions for the occurrence of deadlocks.
The computer is deadlocked only when all conditions are met.

1. mutual exclusion
Only one process may use a resource at a time.

2. hold-and-wait
A process may hold allocated resources while awaiting assignment of others.

3. no pre-emption
No resource can be forcibly removed from a process holding it.

4. circular wait
A closed chain of processes exists,
such that each process holds at least one resource needed by the next process in the chain

Approach:prevention

It prevents deadlocks from occurring.
The programmer make the program to prevent deadlocks from occurring. (static)
Resolving at the Application Layer

Approach:avoidence

Running a program and the OS does not allocate resources in anticipation of a deadlock.
Resolving at the OS Layer. (dynamic)

Define two states for determination in os.
Safe-state that is safe from deadlocks and unsafe-state that may cause deadlocks.

It does not allocate resources to processes by comparing resources that have not yet been allocated,
resources currently allocated to processes, and resources that are needed for each process, or Not initialize them in the case of new processes.

Approach:detection

It is to detect deadlocks.
(Deadlock has occurred.)
Kill and rerun processes involved in deadlocks.