스미스요원

교착 상태(Deadlock) 개념

• 교착상태란? 시스템 자원에 대한 요구가 뒤엉킨 상태

• 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한정 대기 상태에 빠지는 상황

• 데드락 발생 조건 (하나라도 성립하지 않으면 이는 해결 가능한 상황)

    ◦  상호 배제(Mutual exclusion)

          -  자원은 한번에 한 프로세스만 사용할 수 있음

    ◦  점유 대기(Hold and wait)

          -  최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 있는 자원을 추가로 점유하기 위해 대기하고 있는 상태

    ◦  비선점(No preemption)

          -  다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 수 없음

    ◦  순환 대기(Circular wait)

          -  각 프로세스가 순환하는 형태로 다음 프로세스가 요구하는 자원을 가지고 있음

교착 상태를 해결하는 방법

예방(prevention)

• 데드락 발생 조건 중 하나를 제거함으로써 해결하는 방법

    ◦  상호배제 부정 : 여러 프로세스가 공유 자원을 사용할 수 있도록 허용

    ◦  점유대기 부정 : 프로세스 실행 전 모든 자원을 할당

    ◦  비선점 부정 : 자원을 점유 중인 프로세스가 다른 자원을 요구할 때, 가진 자원은 반납하도록 제한

    ◦  순환대기 부정 : 자원에 고유번호 할당하여 순서대로 자원을 요구하도록 제한

• 단점

    ◦  시스템 처리량 및 효율성을 떨어트린다

회피(avoidance)

• 데드락이 발생하지 않도록 알고리즘을 설계하는 방법

• 은행원 알고리즘(Banker's Algorithm)

    ◦  은행이 항상 최소 한 명에게 대출해줄 금액은 보유하고 있어야 함에서 유래

    ◦  해당 고객이 대출금을 반환하면 생긴 돈으로 다른 사람의 대출을 해결할 수 있다.

    ◦  특정 프로세스에 자원을 할당해주고 반환받을 수 있는 상태 = 안전 상태

    ◦  프로세스에 자원을 할당해줄수도, 돌려 받을수도 없는 상태 = 불안전 상태

          -  교착상태는 불안전상태에 속한다. (T)

          -  불안전상태는 교착상태에 속한다 (F)

    ◦  안전상태면 자원을 할당하고, 불안전 상태면 다른 프로세스들이 자원을 반환할 때까지 대기함으로써 교착 상태가 발생하지 않는

         환경을 조성하는 방법이다.

    ◦  이 알고리즘이 제대로 수행되기 위해서는 아래의 3가지 정보가 필요하다.

          -  각 고객들이 최대 얼마의 돈을 요구할지 (Max) = 각 프로세스가 자원을 최대 얼마나 요청할 수 있는지

          -  고객들이 현재 빌린 돈이 얼마인지 (Allocated) = 각 프로세스가 현재 보유하고 있는 자원이 얼마인지

          -  은행이 보유한 돈이 얼마인지, 빌려줄 수 있는 돈이 얼마인지 (Available) = 시스템이 자원을 얼마나 보유하고 있는지.

• 단점

    ◦  할당할 수 있는 자원의 수가 일정해야 한다. (자원 이용도가 낮다.)

    ◦  사용자 수가 일정해야 한다.

    ◦  최대 자원 요구량을 미리 알아야 한다.

    ◦  프로세스들은 유한한 시간 안에 자원을 반납해야 한다.

    ◦  복잡하고, 자원 이용에 제약이 많고, 알고리즘 수행시 오버헤드가 발생할 수 있다.

    ◦  즉 실제 돌아가는 프로그램에 적용하기 상당히 어렵다. → 현재 주로 채택되는 방식이 아님

탐지(Detection), 회복(Recovery)

• 교착 상태의 발생을 허용한 다음 회복시키는 방법

• 탐지(Detection)

    ◦  Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색하는 방법

    ◦  은행원 알고리즘에서와 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악할 수 있다.

    ◦  자원 할당 그래프를 통해 교착 상태를 탐지하는 방법도 있다.

          -  단, 이 방법은 자원 할당 그래프를 만드는데 오버헤드가 발생할 수 있으니 주의가 필요하다.

• 회복(Recovery)

    ◦  교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복하는 방법

    ◦  프로세스 종료 방법은 아래의 두가지 종류가 있다.

          -  교착 상태에 놓인 프로세스 전체를 종료시키는 방법

          -  교착 상태가 제거될 때까지 프로세스를 하나씩 종료시키는 방법

    ◦   할당된 자원을 해제시켜 회복하는 방법 : 자원 선점

          -  교착 상태의 프로세스를 일시정지 시키고, 해당 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에 할당하는 방식이다.

          -  우선 순위가 낮은 프로세스 / 수행 횟수가 적은 프로세스가 우선적으로 선점된다.

무시

• 회복과정의 성능저하가 심하다면 해당 교착 상태를 무시하는게 오히려 좋을 수 있다.

• 무시된 교착상태의 프로세스들은 시간이 지나면 자연스럽게 time-out 되어 종료된다.

• 현대의 운영체제들이 가장 많이 채택하는 방법이라고 한다 (!)

식사하는 철학자 문제

• 교착 상태를 설명하는 대표적인 알고리즘 문제로, 문제의 내용은 아래와 같다.

    ◦   철학자가 생각에 빠져 있을 때는 아무런 액션을 취하지 않지만, 때때로 배가 고파진다. 밥을 먹기 위해서는 포크 두 개가 필요하다.

    ◦   왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.

    ◦   오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.

    ◦   포크 두 개를 잡으면 일정 시간 동안 밥을 먹을 수 있다.

    ◦   식사가 끝나면 사용한 포크 두 개를 내려놓는다.

    ◦   철학자는 다시 생각에 빠진다.

    ◦   배가 고픈데 일정 시간동안 식사를 못하면 철학자는 굶어죽는다!

• 이 때 만약 모든 철학자가 동시에 왼쪽 포크를 잡으면, 모두 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다.

    ◦   모든 철학자가 영원히 3번 상태에 머물러있는 교착 상태가 발생한다.

    ◦   무한 교착 상태로 인해 기아 현상이 발생하고, 철학자는 굶어 죽게된다!

• 몇가지 해결 방법

    ◦   왼쪽 포크를 들고나서 오른쪽 포크를 들 수 있나 보고, 안되면 포크를 내려놓는다.

          그리고 랜덤한 시간동안 기다린 다음 이를 다시 시도한다.

          -  모두가 동시에 왼쪽 포크를 잡아도 해도 서로 기다리는시간이 다르기 때문에 결국 누군가는 식사를 할 수 있지만,

              낮은 확률로 starvation이 발생할 수 있다.

          -  기아 현상이 절대 발생하면 안되는 환경(원자력발전소, 비행기 등)에서는 사용 불가능한 방법이다.

    ◦   식사할 수 있는 상황을 하나의 뮤텍스(Mutex)로 관리한다.

          -  한번에 한 명씩 반드시 식사를 할 수 있다. 하지만 한 명이 밥을 먹는 동안 맞은편의 철학자도 포크 두개를 잡을 수 있는 상황이다.

             즉 교착상태가 발생하지 않음이 보장되기는 하나, 자원의 낭비가 발생한다.

    ◦   세마포어와 몇가지 규칙을 잘 사용하면 식사하는 철학자 문제를 완벽하게 해결할 수 있다.

          -  간단히 설명하면 철학자의 상태를 식사 중, 식사 대기 중으로 표현하고, 자신의 양쪽이 식사 중이 아니면 식사를 할 수 있도록

             세마포어 형태로 관리하는 방법이다. 이 방법을 사용하면 주어진 상황에서 최대한 많은 철학자들이 교착상태 없이 식사를 할 수

             있다.

참고자료