OS: Deadlock Avoidance

Deadlock Avoidance: Motivation

Deadlock Avoidance:Motivation

          > '///' 와 '\\\'는 두 프로세스가 동시에 IO를 접근함

                    > 모든 path는 위 혹은 오른쪽

          > 'Unsafe' : OS 가 이 box에 들어오게 되면, 결국 deadlock이 발생함으로 들어가선 안된다.

                    > state t 일때, unsafe 한 공간은 피해야 한다(위가 아닌 오른쪽으로 감으로써)

          > State t 일때, OS는 request를 허락할 지 정해야 한다

                    > Good choice: Avoid Deadlock

                    > 이를 수행하기 위해선, 미리 어떤 자원들이 필요할 지 알아야 한다.

 

Deadlock Avoidance: Safe and Unsafe States

          > (a) 는 safe 한 상태: 할당되는 순서가 deadlock 없이 모든 프로세스가 완료될 수 있음

                    > B 프로세스 실행 >> resource 2개 더 가져감 >> 1 free

                              >> B 프로세스 완료 >> 할당된 resource 반납, 5 free

                    > C 프로세스 실행 >> resource 5개 더 가져감 >> 0 free

                              >> C 프로세스 완료 >> 할당된 resource 반납 >> 7 free

                    > A 프로세스 실행 >> resource 6개 더 가져감 >> 모든 프로세스 완료

 

          > (a) 상태에서 시작해 (b) 상태로 간다고 가정 ( A 에게 추가 자원을 할당 함으로 써)

                    > 프로세스 B 가 실행 >> 자원 2개 더 요청 >> free

                    > 프로세스 C 는 실행 불가능 >> 자원 5개 더 필요(same with A)

          > (b) 상태는 unsafe 하다 : 결국 deadlock이 발생할 수 있음

                    > B가 다 돌고 자원을 반납해도 다른 프로세스가 돌아갈 만큼의 자원이 없음

                    > A 가 자원을 더 요청하기 전 반납할 수도 있으므로 deadlock이 발생하지 않을수도 있음

 

The Banker's Algorithm

              > 자원이 한정적이지만 모든 프로세스가 동시에 모든 자원을 요청하는것은: highly unlikely

              > 그러므로 프로세스들에게 자원을 "대출" 해줌

              > state (b) 까지는 safe state

              > 하지만 프로세스 B에 자원을 하나 더 할당하게 되면, state (c) 가 되는데, 이때는 unsafe state 이다

 

          > Algorithm

                    > 자원 요청이 들어오면, 자원을 할당하는 것이 safe state 일지 아닐지 결정

                              >> safe --> allocated

                              >> unsafe --> postponed

                    > safe 인지 확인하기 위해, some process를 돌릴 수 있는 만큼의 자원이 있는지 확인

         

          > Advantages

                    > Roll - back state 와 자원 선점이 필요치 않다

                    > 덜 제한적이다 (deadlock prevention 보다)

          > Disadvantages

                    > 각 프로세스가 필요한 최대 자원을 미리 알아야 한다

                    > 각 프로세스는 독립적이어야 한다

                    > There must be fixed number of processes and resources

                    > 오버해드가 크다

 

Deadlock Avoidance Evaluation

          > The Ostrich Approach: 문제 무시

                    >> Deadlock이 자주 일어나지 않을 경우 효율적

          > Deadlock Prevention: Deadlock Condition 하나 제거

                    >> 너무 제한적일 수 있음

          > Deadlock Detection and Recovery: Deadlock 감지시 deadlock break

                    >> 감지빈도와 성능간의 tradeoff

          > Deadlock Avoidance: Deadlock 이 일어나지 않을 요청만 수행

                    >> 사전에 알아야 할 정보가 너무 많고 동적임