14. deadlock2

• Banker's Algorithm

 

* 가정

        * 모든 프로세스는 자원의 최대 사용량을 미리 명시

        * 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.

* 방법

        * 기본 개념 : 자원 요청시 safe 상태를 유지할 경우에만 할당

        * 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택

           (그런 프로세스가 없으면 unsafe 상태)

        * 그런 프로세스가 있으면 그 프로세스에게 자원을 할당

        * 할당받은 프로세스가 종료되면 모든 자원을 반납

        * 모든 프로세스가 종료될 때까지 이러한 과정 반복

 

• Deadlock Detection and Recovery

* Deadlock Detection

        * Resource type 당 single instance인 경우

                * 자원할당 그래프에서의 cycle이 곧 deadlock을 의미

        * Resource type 당 multiple instance인 경우

                * Banker's algorithm과 유사한 방법 활용

        * Wait - for graph 알고리즘

                * Resource type 당 single instance인 경우

        * Wait-for graph

                * 자원할당 그래프의 변형

                * 프로세스 만으로 node 구성

                * Pi가 가지고 있는 자원을 Pk가 기다리는 경우 Pk->Pi

        *Algorithm

                * Wait-for graph에 사이클이 존재하는지를 추가적으로 조사

                *O(n^)

 

• Deadlock Detection and Recovery

        * Recovery

                *Process termination

                * Abort all deadlocked processes

                * Abort one process at a time until the deadlock cycle is elminated

 

        * Resource Preemption

                *  비용을 최소화할 victim의 선정

                * safe state로 rollback하여 process를 restart

        * Starvation 문제

                - 동일한 프로세스가 계속해서 victim으로 선정되는 경우

                - cost factor에  rollback 횟수도 같이 고려

 

• Deadlock Ignorance

* Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음

 * Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음

 * 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처

 * UNIX, Windows 등 대부분의 범용 OS가 채택