[운영체제] 교착 상태(Dead Lock)와 필요 조건

개요(Overview)

 
 다중 프로그래밍 환경에서 여러 프로세스들은 제한된 수의 자원을 사용하려고 서로 경쟁할 수 있습니다.

대기 중인 프로세스는 자 신이 필요로 하는 자원이 대기중인 또 다른 프로세스에 의해 점유되어 있다면 다른 상태로 영원히 변할 수 없는 상황이 발생하기도 합니다.

 

예를 들어, 4개의 테이프 구동기와 2개의 프로세스를 갖고 있는 시스템의 경우 각각의 프로세스는 다른 프로세스가 자신의 자원을 해제할 때까지 기다려야 하는데, 이러한 상황을 가리켜 교착 상태(Dead Lock)라고 합니다.

 

다중 프로그래밍 시스템에서는 이러한 상황을 사전에 방지하고 자원을 원활하게 공유되도록 하는 것이 모든 운영체제의 공통된 목적이기 때문에

각각의 프로세스들에게 할당된 특정 자원에 대하여 독점적인 권한을 가지고 있을 경우, 이로 인하여 다른 프로세스가 절대로 자신이 수행할 작업을 마칠 수 없는 상황이 발생하는 것을 방지해야 합니다.

 

이번 포스팅에서는 이러한 교착상태에 대한 정의와 그 필요조건에 대해 다루도록 하겠습니다.

 

---

 

1.1. 자원의 교착 상태

 운영체제에서 발생하는 교착 상태는 주로 전용 자원(=한 번에 하나의 프로세스 또는 사용자가 사용할 수 있는 자원)이나, 순차적으로 재사용하는 자원을 사용하다가 발생하는 경우가 많습니다.

 

이러한 자원의 사용 과정에서 발생하는 교착상태는 아래의 그림과 같이 표현할 수 있습니다.

 

 

<fig 1.1. 간단한 교착 상태의 예시>

 

 

위 그림을 살펴보면 서로 다른 프로세스(Process)와 자원(Resource) 사이에 할당(Allocation)과 요청(Request)에 대한 관계가 모식도로 표현되어 있고, 그림 속의 화살표는 그 자원이 가리키는 프로세스에 할당되었음을 의미합니다.

 

즉, 위 사례에서 Process A는 Resource 1을 할당(allocation) 받고 Process B는 Resource 2를 할당 받은 것입니다.

 

또한 그림에서 화살표에 ‘request’라고 표시된 부분은 화살표의 시작점에 있는 프로세스가 화살표의 끝 부분에 해당하는 자원을 요청(request)한 것을 의미합니다.

 

따라서 위 상황에서는 프로세스 A와 프로세스 B가 하나의 원을 형성하며 자기가 가진 자원을 놓아주지 않고 다른 자원을 요청하는 ‘환형 대기’의 교착상태(Dead Lock)이 발생한 것입니다.

 

오늘날의 컴퓨터 시스템은 어떤 프로세스가 수행할 작업을 위해 충분하지 않은 자원을 가지고 있는 경우가 많습니다. 여기서 말하는 자원은 가장 보편적으로 CPU와 같은 하드웨어 장치일 수도 있고, 파일의 입출력을 위한 보조 기억 장치, 실행중인 프로세스가 사용할 기억 공간을 관리하기 위한 주기억장치가 될 수도 있습니다.

 

따라서, 운영체제는 어떤 프로세스가 특정 종류의 자원을 요구한다면 여러 프로세스들에게 현재 필요로 하는 자원을 적절하게 할당 및 분배해야 합니다. 그리고 이렇게 서로 다른 프로세스들이 필요로 하는 자원을 적절히 관리하는 ‘능력’이 운영체제의 성능을 평가하는 중요한 평가 기준이 될 수 있습니다.

 

컴퓨터 시스템에서 한정된 자원을 사용하기 위해서는 운영체제의 적절한 관리도 중요하지만, 그 외에도 해당 자원을 사용하는 프로세스가 자신의 작업을 처리하기 위해 우선 자원을 ‘요청(Request)’해야 하며 모든 작업이 끝난 이후에는 이를 반납(Return)하는 것이 매우 중요합니다.

 

또한 각각의 프로세스는 자기 자신이 작업을 할 때에 ‘필요한 만큼’ 자원을 요청해야 하며 요청된 자원의 개수는 그 시스템에서 현재 사용 가능한 전체 자원의 총 합을 넘을 수 없습니다. 즉, 어떤 컴퓨터 시스템에서 연결된 ‘프린터 장치’가 총 2개라고 했을 때, 모든 프로세스는 2개 이상의 프린터 장치를 운영체제에게 요구할 수 없다는 것을 의미합니다.

 

따라서, 컴퓨터 시스템에서 프로세스가 정상적으로 동작하는 상황일 때, 모든 프로세스들은 다음과 순서로 자원을 사용하게 됩니다. 

 

1) 요청

• 운영체제로부터 현재 필요한 자원을 할당해 달라고 요구하는 것입니다.
• 요청은 즉각적으로 수용되지 않을 수 있으며, 이 경우에는 요청하려는 자원을 받을 때까지 기다려야 합니다.

 

2) 사용

• 각 프로세스들은 운영체제로부터 할당 받은 자원을 작동, 즉 ‘사용(Use)’할 수 있습니다.
• 예컨대, 어떤 프로세스가 ‘프린터 장치’를 요청했다면 해당 프로세스는 프린터 장치를 통해 문서 등을 ‘출력’할 수 있습니다.

 

3) 해제

• 각 프로세스는 요청에 의해 할당(allocation) 받은 자원을 작업이 끝난 후에 되돌려 주어야 합니다.

 

임의의 프로세스 집합에서 그 집합 내에 각각의 프로세스가 그 집합 내의 다른 프로세스에 의해서만 발생될 사건(event)을 기다리고 있을 때, 교착 상태가 발생할 수 있습니다.

 

아래와 같이 프로세스 A가 프로세스 B가 통보할(Notified) 사건(event)를 기다리고 있다면

이로 인해 프로세스 C는 A가 점유한 자원을 사용하지 못해 교착 상태(Dead Lock)에 빠질 수 있습니다.

 

<fig 1.2. 이벤트(event)를 기다리는 교착 상태(Dead Lock)>

 

 

이외에도 어떤 프로세스들 사이에 현재 보유한 자원과 앞으로 필요로 하는 자원이 서로 상호 의존적일 때에도 교착 상태(Dead Lock)가 발생할 수 있습니다.

 

<fig 1.3. 서로 다른 자원의 점유로 인한 교착 상태(Dead Lock)>

 

 위 그림에서 프로세스 P는 프로세스 Q가 가진 판독기(Reader)가 필요하고, 프로세스 Q는 프로세스 P가 가진 프린터(Printer)가 필요합니다. 이처럼 서로 다른 프로세스가 상호 의존적인 자원을 요청하게 되는 상황에서도 교착상태가 발생할 수 있습니다.

 

---

 

1.2. 스풀링 시스템과 교착 상태

 

 컴퓨터 시스템에는 스풀링 시스템(spooling system)이라는 것이 존재합니다. 이는 시스템 상에 존재하는 다양한 주변 기기, 즉 자원들이 각각의 역할을 일을 수행하는데 걸리는 속도의 차이를 극복하기 위해 만들어진 시스템입니다.

 

이러한 스풀링 시스템은 주로 프린터(Printer) 장치와 같이 어떤 작업에 대한 처리 속도가 CPU와 같은 장치의 처리 속도와 비교하여 현저히 차이를 보일 때 주로 사용됩니다.

 

 예컨대 임의의 어떤 프로세스 A가 수행하는 작업이 CPU를 통해 어떤 ‘자료(Data)’를 생성하고, 이를 출력하기 위해 프린터(Printer) 장치를 필요로 할 때, 스풀링 시스템은 프로세스 A의 작업 처리로 인해 프린터가 출력을 완료할 때까지 CPU와 같은 고속 장치의 오랜 점유를 방지하여, 전체적인 작업의 처리 효율을 높여줍니다.

 

 하지만, 이러한 스풀링 시스템도 모든 경우에 대하여 완벽히 대응하지 못할 수도 있습니다. 예컨대 어떤 스풀링 시스템에서 실제 인쇄가 시작되기 전에 이미 출력이 만들어져야 하는 경우, 인쇄할 데이터를 만들어 스풀링 파일로 보내고 미완료된 작업들을 처리하는 도중에 스풀링 파일을 담아두는 기억 공간 자체가 가득 차버려서 오히려 스풀링 시스템으로 인해 교착 상태가 발생할 수도 있습니다.

 

 이러한 교착 상태를 해결하기 위해 스템을 재시작(Restart)하게 된다면, 지금까지 수행된 모든 작업 과정을 잃어버리는 결과가 나타날 수도 있습니다.

 

 이와 같은 문제 상황을 예방하기 위해서는 우선 스풀링 시스템에서 필요할 것으로 예상되는 공간보다 더 많은 공간을 스풀링 시스템에 사용할 수 있도록 하는 방법이 있습니다. 그러나 이 방법은 만약 기억 공간의 단가가 높은 경우에는 좋은 방법이 아닐 수 있습니다.

 

 그러므로 이보다 더 보편적인 방법으로는 입력 스풀링 처리부(input spooler)에서 스풀링 파일이 일정 포화 임계치(saturation threshold), 예컨대 약 75% 정도 점유하게 되면 새로운 작업을 읽지 않도록 막는 방법이 있습니다.

 

 비록 이로 인해 시스템의 처리 효율이 저하될 수 있다는 단점이 존재하지만 교착 상태(Dead Lock)라는 치명적인 문제 상황의 발생을 방지한다는 관점에서는 합리적인 선택이 될 수 있습니다.

 

 오늘날 컴퓨터 시스템은 앞서 설명한 스풀링 시스템보다 훨씬 복잡 하게 설계되어 있습니다. 시스템에서 작업이 끝나기 전에 인쇄를 시작할 수 있도록 하여, 작업이 계속 실행 중일 지라도 완전히 또는 거의 포화된 스풀링 파일을 일부 또는 전체를 비우도록 할 수도 있습니다.

 

 그리고 이처럼 오늘날의 대부분의 컴퓨터 시스템에서는 스풀링 공간의 할당이 동적으로 이루어지기 때문에, 만약 스풀링 공간이 부족하다면 새로운 공간이 추가되기도 합니다.

 

---

 

1.3. 자원의 개념

 

 운영체제의 가장 큰 존재 의미는 ‘자원의 관리’ 입니다. 따라서, 운영체제를 다른 말로 표현한다면 ‘자원 관리자’라고 할 수 있습니다. 이처럼 운영체제는 다양한 종류 그리고 수많은 자원에 할당에 대한 책임을 맡고 있습니다. 그리고 이들 자원의 형태는 서로 상이하기 때문에 운영체제는 그만큼 각 자원에 대해 분석하고 관심을 가지는 것이 매우 중요합니다.

 

 비교적 익숙한 사례로 중앙 처리 장치(CPU)나 주 기억장치와 같이 ‘중단 가능한(Preemptible)’ 자원을 고려해보겠습니다. 만약 현재 주기억장치의 일부를 차지하는 사용자 프로그램이 있다면 이는 다른 프로그램에 의해 주기억장치로부터 제거되거나 대체될 수 있습니다.

 

 또한, 사람의 인지 능력을 아득히 넘어서는 작업 효율을 가진 중앙 처리 장치(CPU)는 아마도 컴퓨터 시스템 전체에서 가장 중단 가능성이 높은 자원일 것입니다.

 

 중앙 처리 장치와 같이 시스템에서 서비스를 받기 위해 다양한 프로세스들이 경쟁하는 자원을 빠르게 전환하여 관리하는 것을 멀티플렉스(multiplex)라고 합니다. 그리고 이 속도는 실제 프로세스의 작업 수행 속도에 영향을 주기 때문에 최대한 빠르고 효율적인 속도로 진행하여 작업의 속도를 저하시키지 않도록 빠르게 처리됩니다.

 

 사용자 프로그램 같이 실제 사람과 상호 작용을 필요로 하는 프로세스는 이러한 과정이 필요 없는 다른 프로세스보다 훨씬 오래 자원을 점유하게 될 수 있습니다.

 

 따라서 운영체제는 사용자 프로그램이 CPU가 필요로 하는 작업을 마치고, 입출력을 받는 작업 등을 처리하고 있는 상황이라고 판단된다면 CPU 자원을 빠르게 가져와서 사용자 프로그램이 입출력 과정을 처리하는 동안 다른 프로세스가 CPU를 사용할 수 있도록 관리합니다.

 

 그리고 이러한 중단 방식(preemption)은 다중 프로그램 컴퓨터 시스템의 성능을 평가할 수 있는 매우 중요한 지표가 될 수 있습니다.

 

 반면에 어떤 자원은 그 자원이 일단 한 번 할당이 되면 다시 돌이킬 수 없는, 즉 비중단성(nonpreemptible)인 경우도 있습니다. 예컨대 과거에 많이 사용하던 테이프 드라이브는 몇 분 또는 몇 시간 동안 일정한 프로세스에게 할당되는 것이 일반적입니다. 그리고 이러한 자원은 작업이 진행중인 동안 다른 프로세스에게 권한이 넘겨질 수 없습니다.

 

또한, 자원들은 서로 공유 가능할 수도 있지만 특정 프로세스만이 독점적으로 점유하게 되는 즉, 전용되는 경우도 있습니다. 예컨대 디스크 드라이브는 가끔 한 프로세스에 의해 전용되기도 하지만, 다수의 프로세스에 의해 공용될 수 있는 파일을 가지고 있기도 합니다.

 

파일의 사례를 조금 더 살펴보자면, 이떤 컴퓨터 시스템에서 많은 사용자가 동시에 편집 프로그램, 즉 에디터(Editor)를 통해 쓰고자 하는 경우가 있을 수 있습니다.

이때 사용자들마다 하나씩 편집 프로그램을 복사하여 주기억장치에 올려 놓고 사용하는 방법은 다소 비효율적일 수 있습니다. 대신 하나의 프로그램 코드가 존재하고, 각 사용자마다 별도의 데이터 섹션(Section)을 가지도록 하여 관리하는 방법이 더 합리적일 것입니다.

이와 같이 설계하는 이유는 편집기(Editor)라는 프로그램이 동시에 다수의 사용자가 쓸 수 있더라도 그 프로그램 자체가 변해서는 안 되기 때문입니다.

 

이처럼 사용자가 사용중인 상황에서는 내용이 변하지 않는 코드(Code)를 ‘재진입 가능(reentrant) 하다’라고 말합니다.

 

그리고 사용중 일 때, 그 내용이 변하기는 하나 사용할 때마다 다시 초기화 작업을 해야하는 코드를 ‘순차적으로 재사용 가능(serialbly reusable) 하다’ 라고 합니다.

 

재진입 가능한 코드(reentrant code)는 동시에 여러 프로세스에 공용될 수 있지만,

순차적으로 재사용 가능한 코드(serialbly reusable code)는 한 순간에 오직 한 프로세스만이 사용할 수 있습니다.

 

---

 

1.4. 무기한 연기(indefinite postponement)

 

 어떤 시스템에서든 자원의 할당 및 프로세스의 스케줄링을 결정하는 동인 다른 프로세스를 기다리게 할 경우, 해당 시스템에 의하여 프로세스의 스케줄링이 무기한으로 연기될 수 있습니다.

 

이러한 상황을 ‘무기한 연기(indefinite postponement)’ 라고 하며,

경우에 따라서는 교착 상태만큼 위협적인 상황이 될 수도 있습니다.

 

 무기한 연기 현상은 시스템에서 자원을 분배하는 정책에서 발생하는 ‘편향성’ 또는 ‘편중성’ 때문에 발생합니다. 운영체제는 단순히 순차적 또는 무작위적으로 프로세스에게 자원을 할당하는 것이 아니라 어떠한 기준을 바탕으로 ‘우선순위(Priority)’를 평가하여 자원을 배분하게 됩니다.

 

 이러한 설계 방식에 기인하여 특정한 상황에서 어떤 프로세스가 무기한으로 자원의 할당을 기다리게 되는 상황이 발생할 수도 있는 것입니다. 따라서, 운영체제는 우선순위를 바탕으로 프로세스 간에 자원을 배분할 때에도 이들 간에 효율적이면서도 공평하게 다루도록 설계할 필요가 있습니다.

 

 일부 시스템에서는 프로세스가 자원을 받기 위해 기다린 시간에 가중치를 부과하여 이를 기반으로 공평하게 자원을 할당 받을 수 있도록 하기도 합니다. 그리고 이처럼 시간에 따라 우선순위에 가중치를 더해 자원을 방식을 ‘에이징(Aging)’ 기법이라고 합니다.

이러한 시스템에서는 처음에 낮은 우선 순위로 평가받았던 프로세스라도 시간이 지남에 따라 자연스럽게 우선순위가 높아져 공평하게 자원을 배분 받을 수 있습니다.

 

---

 

1.5. 교착 상태의 필요조건

 앞서 수많은 사례를 살펴보면서 운영체제에서 발생 가능한 다양한 교착 상태(Dead Lock)에 대하여 살펴보았습니다. 이러한 사례를 바탕으로 컴퓨터 시스템에서 교착 상태가 발생할 때에는 다음과 같은 4가지 필요 조건이 존재함을 알 수 있습니다.

 

• 프로세스들이 그들이 필요로 하는 자원에 대하여 배타적인 권한을 요구할 경우 [상호배제 조건]
• 프로세스가 다른 자원을 기다리면서 자신이 할당 받은 자원이 존재하는 경우 [대기 조건]
• 어떤 프로세스가 점유하고 있는 자원이 사용이 끝날 때까지 해당 프로세스로부터 강제로 반환하도록 하거나 제거할 수 없는 경우 [비중단 조건]
• 프로세스들 사이에 작업 처리 과정에서 어떤 의존적 관계가 발생하여, 시스템 상에서 어떤 원형의 사실을 구성해 자원의 할당 또는 반납이 불가한 경우 [환형대기조건]

 

 위 필요조건에서 상호배제란 한 번에 한 프로세스만이 자원을 사용할 수 있음을 의미합니다. 즉 다른 프로세스가 그 자원을 필요로 한다면, 해당 자원의 점유가 끝날 때까지 기다려야 한다는 것입니다. 그리고 이러한 조건들이 모두 만족될 때, 컴퓨터 시스템에서 교착상태가 발생할 수 있습니다.

 

교착상태는 컴퓨터 과학분야에서 다음과 같이 네 가지 세부 주제로 많은 연구가 수행되었습니다.

 

교착상태 관리 기법	설명
교착상태의 예방	- 교착상태의 발생 가능성을 제거하도록 시스템을 조절하는 것에 관심을 둡니다.
교착상태의 회피	- 교착상태의 예방보다 덜 엄격한 조건을 바탕으로 자원을 효율적으로 활용하는 것에 방점을 둡니다. - 모든 교착 상태의 발생 가능성을 제거하는 것보다, 교착상태가 일어날 수 있음을 상정하고 이를 피할 수 있도록 적절히 조절하는 것입니다. - 대표적인 사례로 다익스트라의 은행원 알고리즘이 있습니다.
교착상태의 발견	- 시스템에서 교착 상태의 발생을 허용합니다. - 교착상태가 발생하는 것을 허용함으로써 왜 일어났는지 판단하고, 이와 관련된 프로세스를 분석하여 시스템에서 제거할 수 있도록 합니다.
교착상태의 회복	- 시스템으로부터 교착 상태를 제거하여 시스템이 교착 상태의 발생 유무와 관계없이 잘 진행될 수 있도록 각 프로세스가 점유하던 자원을 회수하도록 합니다.

 

---

참고 자료

• 김완규, 고정국, 진광윤, 최신형, 하성권, 허덕행 | 핵심 운영 체제론 | 두양사