07-DeadLock

1.     Bridge Crossing Example

-       Real-world에서는 traffic을 deadlock의 개념으로 생각

 

2.     Deadlock problems

-       Block 된 process가 하나의 자원을 가지고 있는데, 다른 프로세스가 이 자원을 필요로 하는데 사용하지 못함. => 멈춰버린다

-       Dining-Philosopher problem : 5명의 학자들이 둥근 테이블에 앉아있는데 음식을 먹으려면 동시에 수저 2개를 들어야한다. Eat (C.S.) -> 2개의 수저 필요. 한번에 하나의 수저만 집을 수 있다. 동시에 같은 수저를 잡지 못한다. 

-        왼쪽 손으로 수저를 모두 동시에 집으면 오른손에 집을 수저가 없어 다들 waiting상태로 기다린다. 어떠한 사람도 식사를 할 수 없다.

-       자원을 무한히 기다린다 => dead lock 

 

3.     System Model

-       Physical resource types : 물리적인 장치들 (I/O device, memory space, CPU cycles)

-       Logical resource types : semaphore, mutex lock, files

-       각 resource type은 identical instance 정확히 동일한 기능을 한다

-       Process는 특정 type의 instance를 요구하고 instance가 identical(동일)하면 아무거나 내준다. 같은 type의 resource를 요구하면 아무거나 사용해도 상관이 없다. 각각 다른 resource type이면 다른 것들을 공유할 수는 없다. 

-       하나의 프로세스는 resource type을 사용하기 전에 request를 받아야한다. 

-       사용한 후에는 release를 해주어야한다. 

 

4.     System Model – System call

-       Request : resource 사용하기 전에 요청하는 것

Ex. Open(), malloc(), wait(), acquire() -> 다양한 타입이 있다.

-       Use : 허락 맡은 resource를 사용하는 것

-       Release : 사용하고 난 뒤에 해제

Ex. Close(), free(), signal(), release()

 

5.     Deadlock state

-       다양한 프로세스가 자원을 공유하는데, 한 프로세스가 resource를 요청했을때 가능하지 못하다면 waiting state로 가서 기다린다.

-       Waiting process가 자원을 받지 못하고 state 가 바뀌지 않으면  deadlock 이 발생한다

-       모든 process가 Waiting state 에서 deadlock이 발생한다

-       Process가 미래에 일어나지 않을 event를 기다리는 것 

-       Waiting process 가 요청한 resource가 다른 프로세스에 의해서 잡혀있기 때문에 빠져나갈 수가 없고 deadlock이 발생한다.

-       Process,system -> deadlock state

 

6.     Deadlock characterization (deadlock 발생 조건 4가지) -> 4가지 중 하나라도 모두 만족시키지 않으면 deadlock이 발생되지 않는다

1)     Mutual exclusion : 한번에 하나의 프로세스만 resource에 접근해서 사용할 수 있다. 

2)     Hold and wait : 하나를 붙잡고 있으면서 다른 추가적인 resource를 기다리는 중 

3)     No preemption : 선점이 일어나면 안된다. 강제로 빼앗을 수 없고 자발적으로 내놓아야 한다. 스스로 놓는다 = process를 complete 하는 것

4)     Circular wait : 서로가 서로를 기다리는 관계로 되어야 한다. (원형모양)

 

7.     Resource-Allocation Graph

-       Graph : node 와 edge로 구성된 것 

-       A directed Graph : node (V) 와 edge (E)의 방향이 정해진 것

 

8.     Cycle 과 deadlock 의 관계

-       Cycle 이 없으면 반드시 dead lock 이 발생하지 X

-       Cycle 이 있더라도 반드시 발생하는 것은 아니다. 모든 resource가 하나의 자원만 가지고 있다면 이것은 deadlock이 발생하지만, resource 당 여러개의 자원을 가지고 있으면 deadlock 이 발생하지 않을 수도 있다!! 잘 확인하기

 

9.     Deadlock 을 Handling 하는 방법

-       Deadlock 이 발생하지 않도록 보장 : Deadlock prevention, deadlock avoidance

-       Deadlock 이 발생하였을 때 : deadlock detection, deadlock recovery

-       Deadlock 을 무시하는 것 : Ostrich Algorithm, 많은 OS들이 무시하는 방법을 사용하고 있다. Application 개발자가 발생하지 않도록 주의한다

 

10.  Deadlock prevention  (예방) deadlock이 발생하지 않도록 보장

-       Deadlock 이 발생하는 4가지 조건을 하나라도 만족시키지 못하게 하는것

1)     No Mutual exclusion : 하나의 자원만 사용하게 하도록. -> 모든 자원에 대해서 동시에 사용 가능 하도록 만든다. Printer 같은 경우는 동시에 사용을 못한다. Read-only는 동시에 사용가능

2)     No Hold and Wait : 두개의 자원이 필요하지만 하나의 프로세스를 가지고 있을때 다른 자원을 요청하지 못하도록 보장하는 것

n  Total allocation : 하나의 프로세스가 필요한 모든 resource를 한번에 동시에 할당 되게끔 해주는 것. 하나라도 동시에 할당 못 하면 프로세스는 계속 기다려야함. 

n  Alternative protocol : resource를 아무것도 가지고 있지 않을때 request를 하는 것을 허용해주는 것

n  단점 : resource utilization이 낮아진다. 오랜 시간동안 사용되지 않는 resource가 있을 수도 있다. 

n  단점 : Starvation , 바쁜 resource 하나 때문에 다른 resource들이 실행 되지 못하고 기다리니깐 starvation (무한히 기다리게 하는 것)이 발생하게 된다.  

3)     Allow Preemption : 선점을 허용하도록 하는 것. 다른 프로세스가 사용 중이더라도 내가 필요하면 가져오는 것. .

n  CPU scheduling : RR (RoundRobin)

n  Printer 같은 경우는 preemption을 허용하도록 할 수는 없다

4)     No circular wait : 순환 방식을 만들지 않게 하는 것. total ordering을 주는 것이다. 필요한 우선순위를 정해주는 것. Request 할 수 있는 순서를 정해놓아야한다. 낮은 order를 들도록 하는 것이다  lower(i) higher(i)

-       Deadlock이 발생하지 않으려면 4가지 중 1라도 만족시키지 못하게 해야한다. Device utilization을 낮춰야한다. 비용이 많이 든다. => 완벽한 솔루션은 아니다. 

 

11.  Deadlock Avoidance – deadlock이 발생하지않도록 보장 

-       추가적인 정보로부터 deadlock이 발생하지 않게 한다. complete 한 sequence를 알고 있다고 가정. System은 어떤 프로세스에 할당해야 하는지 결정할 수 있고 deadlock의 발생을 피할 수 있다

-       Circular wait이 발생하지 않도록 한다

-       Process는 resources를 최대한 얼만큼 사용할지 알려줘야한다 (추가적인 정보)

 

12.  System Model

-       State에 있는 information & Resource Type State 

1)     Current available instance – 지금 사용가능한 instance 개수

2)     Current allocated to each process – 할당된 프로세스 개수

3)     Future needed by each process (maximum) – 필요로하는 프로세스몇개

-       가정 : current state를 알고 있다 (위의 정보를 알고 있다)

-       Deadlock이 발생하지 않도록 보장하는 것. Worst case 를 가정하고 시뮬레이션 한다.

-       모든 프로세스는 일이 끝날때까지 resource를 release 하지 않는다고 가정 (non-preemptive) , independent

-       하나가 블럭되고 충분한 자원을 준다면 프로세스는 끝낼 수 가 있다

-       Request – use – release!

-       프로세스는 필요한 자원의 개수가 모두 충족되어야지 실행을 할 수가 있다

 

13.  Safe Sequence

-       Safe : 다수의 프로세스들이 일을 끝내고 deadlock 을 발생시키지 않는 현상 

-       Safe sequence : deadlock이 발생하지 않고 프로세스에게 resource를 할당 할 수있는 순서

 

14.  Safe state vs Unsafe state

-       Safe state : 특정 순서대로 할당을 해준다면 deadlock이 발생하지 않고 진행 할 수 있다. Safe sequence가 하나라도 있으면 safe state 안에 있다. Deadlock이 발생하지 않고 진행 할 수있다. 

-       Unsafe state : deadlock이 발생할 수 있는 상황이 있지만 발생하지 않을 수도 있다. 반드시 발생하는 것은 아니다. 발생할 가능성이 있다는 것!

-       Avoidance : unsafe state로 시스템이 들어가지 않도록 하는 것

 

15.  Deadlock Avoidance Methods

-       Resource type에서 instance가 single 일 때 : Resource-Allocation Graph

-       Resource type에서 instance가 multiple 일 때 : Banker’s Algorithm

 

16.  Resource-Allocation Graph Algorithm

-       Claim : P(i)라는 프로세스가 R(j)를 요청할 것이다(미래). 점선으로 표현

-       Request가 되면 점선->직선으로 변한다

-       Assignment가 되면 직선의 방향이 바뀐다. Resource -> process

 

17.  Banker’s Algorithm

-       Multiple instance일 때, 모든 프로세스는 자신이 사용할 max resource를 나타내고 process 순서를 시뮬레이션 해본다

-       모든 필요한 자원을 할당 받으면 프로세스는 실행을 하고 끝내게 된다

-       Safety Algorithm + Resource-Request Algorithm

-       Available : m

-       Max [i,j] : 최대로 필요한 resource 개수

-       Need[i,j] : 지금 필요한 나머지 resource 개수

-       Allocation[i,j] : 할당된 resource 개수 

-       Need [i,j] = Max[i,j] – Allocation[i,j]

 

18.  Safety Algorithm

-       현재 상태에서 safe state(deadlock이 발생하지 않고 모든 프로세스를 끝내는 것)에 있는지 알아보는 알고리즘

-       Work : Availabe , m 사용가능한 자원의 개수 

-       Finish : n 일을 끝마치고 나간 프로세스의 개수 

 

19.  Conclusion

-       Deadlock concept 

-       4 necessary conditions for deadlock

-       Deadlock prevention

-       Deadlock avoidance : keep safe state 

1)     Resource allocation graph

2)     Banker’s algorithm

 

20.  Deadlock detection

-       Single instance : wait-for graph 사용. 

 

21.  Deadlock Recovery

1)     Process termination : 모든 프로세스를 정리한다. 필요 있는 프로세스를 삭제할 수도 있으니깐 

-       Partial Termination : 문제가 되는 최적의 프로세스를 찾아내서 종료시켜야한다.

2)     Resource preemption