What is a deadlock
4 conditions
Hence , the way to prevent deadlock is to ensure that at least one of these conditions do not hold :
Deadlock Prevention
Mutual exclusion Deny: If 1 resource is non- shareable , then mutual exclusion condition must hold.
Hold And wait Deny: For Hold and wait condition to never occur, it should be made sure that whenever a process requests a resource, it does not hold any other resource.
There can be many protocols implemented
- One protocol could be Allocating all resources to a process before its execution .
- Other Could be, A process can request resource only when it has no resource.
No Preemption of resources Deny: Allow preemption of resources from process when resources are acquired by high priority process.
Circular wait Deny : To prevent this, impose a total ordering of all resources types and every process should request resource in increasing order.
Deadlock Avoidance
Deadlock prevention causes low device utilization and reduced system throughput.
To avoid deadlocks, one requires additional information about how resources all to be requested.
one instance of each resource type
Resource Allocation Graph Algorithm is used.
multiple instances of each resource type, Banker’s Algorithm is used.
Deadlock Detection
If resources have a single instance
- wait-for graph
In this case for Deadlock detection, we can run an algorithm to check for the cycle in the Resource Allocation Graph. The presence of a cycle in the graph is a sufficient condition for deadlock.
If there are multiple instances of resources
- Banker's Algorithm
Detection of the cycle is necessary but not sufficient condition for deadlock detection, in this case, the system may or may not be in deadlock varies according to different situations.
** instatnce
실행 중인 임의의 프로세스, 클래스의 현재 생성된 오브젝트
응용 프로그램 (application) 을 메모리에 띄운 것
Deadlock Recovery
Killing the process
Killing all the processes involved in the deadlock. Killing process one by one. After killing each process check for deadlock again keep repeating the process till the system recovers from deadlock. Killing all the processes one by one helps a system to break circular wait condition.
Resource Preemption
Resources are preempted from the processes involved in the deadlock, preempted resources are allocated to other processes so that there is a possibility of recovering the system from deadlock. In this case, the system goes into starvation.
ref
https://yoongrammer.tistory.com/67
ref
https://www.geeksforgeeks.org/cpu-scheduling-criteria/
https://www.guru99.com/cpu-scheduling-algorithms.html
https://vsonwalkar3.medium.com/scheduling-algorithms-in-operating-system-bade5f192ca4
https://www.javatpoint.com/multilevel-queue-scheduling-in-operating-system
https://www.guru99.com/cpu-scheduling-algorithms.html
