01 교착 상태의 개념과 발생 원인

본 설명은 책 “그림으로 배우는 구조와 원리 운영체제 개정 3판”를 읽으며 제 나름대로 해석하고 정리해 보았습니다.

1. 교착 상태의 개념

다중 프로그래밍 시스템에서는 프로세스가 결코 일어나지 않을 사건을 기다리는 상태가 되면 교착상태(deadlock)에 빠졌다고 말한다. 만약 이 교착상태가 일어났음에도 운영체제가 해결하지 못할 경우 사용자 혹은 시스템 운영자가 작업을 교체하거나 외부 간섭으로 해결해야한다.

그렇다면 교착 상태는 언제 일어날까?

교착 상태는 시스템 자원에 요구가 뒤엉킨 상태로, 두 프로세스가 사용하는 자원을 서로 기다리고 있을 때 발생한다.

쉽게 말하자면, process 1이 resource1 을 갖고있고, process 2 는 resource 2 를 갖고 있다. 그런데 process 2는 resource 1 을 필요로하고 process 1은 resource 2를 필요로다. 그럼 서로에게 필요한걸 서로가 갖고 있지만 이 요구가 뒤엉킨 상태로 계속 서로가 갖고 있는 자원을 받을 떄 까지 무한정으로 대기 하게 되는 것이다.

일상생활에서 이 예를 생각해보자면, 아래와 같은 사진의 경우를 보면 쉽게 이해할 수 있을 것이다.

(참으로 끔찍하다… 😱)

즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 교착상태가 발생한다.

사실, 초기에 일괄 처리 시스템에서는 교착 상태가 자주 발생하지 않았지만, 시스템 효율성을 증가시키고 제한된 자원의 사용률을 높이기 위해 사용하는 병행 처리 기술과 자원 공유 기술로 교착상태의 부작용이 생긴 것이다.

그럼 잠깐, 먼저 프로세스의 순서를 잠깐 정리해보자.

• 자원요청: 프로세스가 필요한 자원을 요청한다. 해당 자원을 사용할 수 있으면 요청을 즉시 수락하지만, 해당 자원을 다른 프로세스가 사용 중이면 요청을 수락할 때 까지 기다려야한다.
• 자원 사용: 프로세스가 요청한 자원을 획득하여 사용한다. 예를들어, 요청한 자원이 프린터라면 프로세스는 프린터를 이용하여 출력한다.
• 자원 해제: 프로세스가 자원 사용을 마친 후 해당 자원을 되돌려(해제) 준다.

자원의 요청과 해제는 시스템 호출로 한다. 파일이나 입출력 장치 등 자원을 읽거나 쓰는 일도 시스템 호출로만 가능하다. 따라서 OS는 프로세스가 자원을 요청하면 할당받을 수 있도록 시스템 호출을 통해 이 사실들을 기록해야한다.

System Call (시스템 호출) Application Programmer가 OS와 소통하기 위한 방법이다. System call은 user program에게 os가 제공하는 service에 대한 API를 제공한다.

2. 교착 상태의 발생 조건

교착 상태는 시스템에서 다음 네 가지 조건을 만족할 때 발생한다. 이 중 1, 2, 3 번 조건만 만족해도 교착 상태가 발생할 수도 있고, 발생하지 않을 수도 있다. 4번 조건은 1, 2, 3, 조건을 만족할 때 발생할 수 있는 결과이므로 네 가지 조건이 모두 독립적이라고 할 수 없다.

1. 상호배제

자원을 최소 하나 이상 비공유 해야한다. 즉, 한 자원은 하나의 프로세스만 사용할 수 있어야 한다 (한 자원을 여러 프로세스가 사용 X). 따라서 다른 프로세스가 이 사용 중인 한 자원 을 사용하려면 한 자원이 해제될 때까지 기다려야한다.

2. 점유와 대기

어떤 프로세스가 자원을 최소 하나 이상 보유하고, 또 다른 프로세스에 할당된 자원을 얻으려고 기다리는 중이여야 한다.

3. 비선점

자원은 선점할 수 없다. 위에서 프로세스 순서를 잠깐 설명했을 때 자원 해제, 즉 프로세스가 자원 사용을 마친 후 자원을 되돌려(해제) 한다고 했었다. 즉, 자원을 강제로 빼앗는게 아니라, 자원을 점유하고 있는 프로세스가 해당 자원을 되돌려(해제)해야 한다는 것이다.

4. 순환(환형) 대기

위의 그림과 같이 대기 프로세스 집합 {P0,P1, P2 … Pn} 이 있을때 위의 그림과 같이 P0는 P1이 보유한 자원을, P1 은 P2, … Pn-1 은 Pn이 보유한 자원을, Pn은 P0이 보유한 자원을 각자 얻으려고 기다리는 것을 순환 대기라고한다.

그럼 위의 조건을 바탕으로, 다시 정리를 해보자.

위의 그림에서 사람은 프로세스, 그리고 아래의 검은색 다리를 하나의 자원이라고 생각해보자. 이제 사람이 덩실덩실 춤을 추면서 화살표 방향으로 자원을 하나씩 점유하기 위해 돌다리를 하나씩 건넌다고 생각해보자.

그렇게 다리를 건너다가, 반대편에서 오는 또다른 사람(프로세스)를 만나게 되고 만나게 되면 교착 상태가 발생했다고 할 수 있다. 여기서 돌 하나를 한 사람만 디딜 수 있으므로 상호배제가 성립한다.

그리고 각 사람은 돌 하나를 딛고, 다음 돌을 요구하므로 점유와 대기 조건도 만족한다. 또 사람이 딛고 있는 돌을 강제로 제거할 수 없으므로 비선점 조건 도 만족한다. 끝으로 반대편에서 오는 사람을 기다리고 또 반대편에 있는 사람은 나를 기다리므로 순환 대기 조건도 만족한다.

그렇다면 이러한 교착 상태는 어떻게 해결할까?

1. 둘 중 한사람이 되돌아간다.(복귀)
2. 징검다리 반대편을 먼저 확인하고 출발한다.
3. 강의 한편에 우선순위를 부여한다.

3. 교착 상태의 표현

이러한 교착 상태를 표현하는 방식이 있다. 이 부분은 자세히 다루지 않고, 어떻게 표현하는지만 잠깐 보도록 하자.

그래프적으로 표현했을때 아래와 같은 그래프일 경우 교착 상태에 있음을 나타낸다.

이 그래프를 좀 더 구체적으로 표현하자면, 아래와 같이 표현할 수 있다. 사각형 안의 회색 점은 자원의 수를 의미한다.