교착상태(Deadlock)

프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로, 교착상태라고도 하며 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생합니다.

데드락의 발생조건

교착상태는 한 시스템 내에서 다음의 네가지 조건이 동시에 성립 할 때 발생한다. 따라서 아래의 4가지 조건중 하나라도 성립하지 않도록 만든다면 교착상태를 해결할 수 있다.

상호배제(Mutual exclusion) : 최소한 하나의 자원은 비공유방식(nonsharable mode)으로 점유되어야한다.
- 비공유 방식 점유 : 한번에 하나의 프로세스만 자원을 사용할 수 있음을 의미.
- 예방법 ) 상호배제 부정 :여러개의 프로세스가 공유자원을 사용할 수 있도록 한다.
점유 대기(Hold and wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다. 예방법 ) 점유대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
비선점(No preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다. 예방법) 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
순환 대기(Circular wait) : 프로세스의 집합 {P0,P1,...,Pn에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2...Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다. 예방법 ) 순환대기 부정 : 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

프로세스와 자원간의 관계를 나타내는 그래프.

방향이 있는그래프
정점(vertex)들과 정점을 연결하는 간선(edge)들로 이루어짐
간선의 두 형태
- 요청선(request edge) : 프로세스 정점에서 자원 정점으로 연결된선 :
- 할당선(assignment edge) : 자원 정점에서 프로세스 정점으로 연결 된 선.

사이클이 있으면 데드락은 존재할수도고 안할수도 있다.

아래의 경우는 사이클은 존재하지만 데드락은 존재하지 않는다.

교착상태 예방 및 회피 : 교착상태가 되지 않도록 보장하기 위하여 교착상태를 예방하거나 회피하는 프로토콜을 이용하는 방법
- 데드락 예방(Deadlock prevention)
- 데드락 회피(Deadlock avoidance) : 추가적인 정보(시간, 최대치 개수)를 받아서 deadlock 생길지 안생길지 확인해서 deadlock 안생기게 지연or 할당.
교착상태 탐지 및 회복 :교착상태가 되도록 허용한 다음에 회복시키는 방법(교착상태로부터 회복이란 교착상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복하는 거을 의미한다.)
- 프로세스 종료(Process termination) 방법.
  - 교착상태에 속한 프로세스를 모두 중지 : 프로세스 재실행 비용이 크다.
  - 교착상태가 제거될 때까지 한 프로세스 씩 중지 - 교착상태 탐지 알고리즘 수행 오버헤드가 크고 중지할 프로세스 선택 문제가 복잡하다.
- 자원 선점 (Resource preemption) 방법.
  - 교착상탤가 제거될 때까지 자원을 선점하여 다른 프로세스에게 할당 해주는 방식.
  - 희생자 선택(selection of victim), 롤백(rollback), 기아(starvation)를 모두 고려하여야 한다.
교착 상태 무시 : 대부분의 시스템은 교착상태가 잘 발생하지 않으며, 교착상태 예방, 회피, 탐지, 복구하는 것은 비용이 많이 든다.

Last updated 5 years ago

Was this helpful?