교착상태(Deadlock)

교착상태

서로 다른 프로세스가 각자 상대방이 자원을 내놓을때까지 작업을 멈추고 기다리는 상태

교착상태의 필요조건

1971년에 E. G. 코프만 교수는 교착상태가 일어나려면 다음과 같은 네 가지 필요 조건을 충족시켜야 함을 보였다.

상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.

점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.

순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

이 조건 중에서 한 가지라도 만족하지 않으면 교착 상태는 발생하지 않는다. 이중 순환대기 조건은 점유대기 조건과 비선점 조건을 만족해야 성립하는 조건이므로, 위 4가지 조건은 서로 완전히 독립적인 것은 아니다.

by 위키피디아

상호배제 : 한번에 한 프로세스만이 하나의 자원을 사용할 수 있고, 다른 프로세스는 그 자원이 반환될 때까지 기다려야 한다.

점유대기 : 프로세스는 최소한 하나의 자원을 점유한 채로 다른 프로세스에 의해 점유된 자원을 얻기위해 대기해야 한다.

비선점 : 자원들을 선점할 수 없어야 함. 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 테스크를 종료한 후 그 프로세스에 의해 자발적으로 방출해야 한다.

순환대기 : 대기 프로세스의 집합에서 각각의 프로세스가 다음 프로세스가 가지고 있는 자원을 얻기위해 대기하고 있고, 마지막 프로세스는 처음의 프로세스가 가진 자원을 얻기위해 대기하고 있어야 한다.

교착상태의 관리 및 처리방법론

현재의 대부분의 운영 체제들은 교착 상태를 막는 것은 불가능하다. 교착 상태가 발생하면 여러 운영 체제들은 제각기 다른 비표준 방식들로 이러한 교착 상태에 대응한다. 대부분의 접근들은 4가지 코프먼 조건들 가운데 하나(특히 4번째 것)를 막음으로써 동작한다. 주요 접근 방식은 다음과 같다.

교착 상태의 예방

  상호배제 조건의 제거 : 교착 상태는 두 개 이상의 프로세스가 공유 불가능한 자원을 사용하니 발생하는 것이므로 공유 불가능한, 즉사 상호 배제 조건을 제거하면 교착 상태를 해결할 수 있다.

  

  점유와 대기 조건의 제거 : 한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법이다. 자원 과다 사용으로 인한 효율성, 프로세스가 요구하는 자원을 파악하는 데에 대한 비용, 자원에 대한 내용을 저장 및 복원하기 위한 비용, 기아상태, 무한 대기 등의 문제점이 있다.

  비선점 조건의 제거 : 비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어 준다.

  환형 대기 조건의 제거 : 자원 유형에 따라 순서를 매긴다.

이 교착 상태의 해결 방법들은 자원 사용의 효율성이 떨어지고 비용이 많이 드는 문제점이 있다.

교착 상태의 회피

교착 상태의 무시

교착 상태의 발견

by 위키피디아

1. 시스템이 결코 교착상태가 되지 않도록 하기 위해 교착상태를 예방하거나 회피하는 프로토콜을 사용

  교착상태 예방(prevention) 기법 : 교착 상태의 필요조건중 적어도 하나가 성립하지 않도록 자원 요청에 대해 제한을 둠

  교착상태 회피(avoidance) 기법 : 시스템은 현재 요청이 만족되는지 혹은 지연해야 하는지를 결정하기 위해 현재 사용 가능한 자원들과 각 프로세스에 할당된 자원 프로세스의 요청과 해제를 고려하는 방법

2. 시스템이 교착상태가 되도록 허용한 다음에 회복시키는 방법

  교착상태 탐지 알고리즘, 교착상태로부터의 회복 알고리즘

3. 문제를 무시하고, 교착상태가 시스템에서 결코 발생하지 않는 척 한다.

  성능저하 -> 시스템 중단 -> 인위적인 재시작

  대부분의 운영체제에서 선택 된 방법