교착 상태 - (1) 정의 및 필요조건

교착 상태란?

2개 이상의 프로세스가 서로의 작업이 끝나기만 기다리며 작업을 진행하지 못하는 상태를 말한다.

발생 원인

시스템 자원

다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다. 아래 그림은 2개의 프로세스가 프린터와 레코더로 인하여 교착 상태가 된 상황을 그림으로 나타낸 것이다. 서로 자원을 하나씩 할당받은 상태이지만, 다른 하나를 할당받지 못하여 진행되지 못하는 상황이다.

공유 변수

공유 변수가 서로의 실행을 막는 경우도 존재한다. 아래 그림은 교착 상태를 발생시키는 임계구역 코드를 나타낸 것이다. 2개의 lock이 동시에 true가 된 이후 while 문이 실행되면 서로의 lock에 의하여 두 프로세스가 실행되지 못하는 것이다.

응용 프로그램

여러 프로세스가 데이터에 접근할 때에도 데이터의 일관성을 유지하기 위해 데이터베이스에서도 lock을 사용한다. 이 lock으로 인하여 교착 상태가 발생할 수 있다.

자원 할당 그래프(Resource Allocation Graph)

프로세스가 어떤 자원을 사용 중이고 기다리고 있는지를 표현하는 그래프이다. 그리는 규칙은 다음과 같다.

a. 프로세스는 원으로, 자원은 사각형으로 그린다.
b. 자원을 사용 중인 경우 "자원 -> 프로세스" 방향의 실선, 자원을 기다리는 경우 "프로세스 -> 자원" 방향의 점선으로 나타낸다.
c. 자원 안에는 수용할 수 있는 프로세스의 수만큼의 작은 원을 그린다.

예시

교착 상태 필요조건

다음 4가지 조건을 모두 만족해야 교착 상태가 발생한다.

조건	설명
상호 배제	한 프로세스가 할당받은 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
비선점	한 프로세스가 할당받은 자원은 중간에 다른 프로세스가 뺏을 수 없는 비선점 자원이어야 한다.
점유와 대기	프로세스가 한 자원을 할당받았으면서 다른 자원을 기다리는 상태여야 한다.
원형 대기	점유와 대기를 하는 프로세스들 간의 관계가 원을 이루어야 한다.

위의 두 그래프 중 두번째는 아래 조건을 모두 충족하기 때문에 교착 상태인 것을 확인할 수 있다.

교착 상태와 아사 상태

아사 상태는 스케줄링 등의 정책상 결함, 오류로 인해 특정 프로세스가 실행되지 않는 것이고, 교착 상태는 여러 프로세스가 서로의 작업을 방해하여 실행되지 못하는 상태를 말한다.

Reference

쉽게 배우는 운영체제