다중 프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁하는 상황이 발생할 수 있습니다. 마치 아래의 그림과 같은 상황을 말합니다. 이를 Deadlock (교착상태)이라고 합니다.

Deadlock

Deadlock 발생 상황

1. 시스템은 유한한 개수의 자원들로 이루어져 있습니다.

   (자원(resource) : CPU나 파일들, 또는 입출력 장치)

2. 프로세스들은 이런 자원들을 사용하고자 할 때 요청(Request)을 보내야하고, 사용을 완료하면 방출(Release)을 해 주어야 합니다.

3. 요청을 했을 때 자원이 이미 다른 프로세스에 의해 사용되고 있는 등의 이유로 허용이 되지 않으면, 자원을 얻을 수 있을 때까지 대기해야 합니다. 요청 시에는 open(), malloc(), wait()등의 함수들이 사용되고, 방출 시에는 close(), free(), signal()등의 함수가 사용됩니다.

Deadlock 정의

• 정의 : 한 세트 내의 모든 프로세스들이 동일한 세트 내의 다른 프로세스들로 인해 발생할 수 있는 이벤트를 기다리고 있는 경우

모든 프로세스들이 서로의 이벤트가 일어나기 만을 기다리고 있어서 결국 아무 프로세스도 실행되지 못하는 상태를 뜻합니다.

Deadlock 발생 조건

Deadlock 상황에서는 프로세스들은 실행을 끝낼 수도 없으며, 다른 자원들을 사용할 수도 없기 때문에 다른 작업을 수행하는 것도 불가능합니다.

조건 (모두 성립 시 Deadlock)

1. Mutual Exclusion (상호 배제): 하나의 자원은 한 번에 하나의 프로세스만 사용할 수 있어야 합니다.

2. Hold and Wait (점유하며 대기): 프로세스는 최소 하나의 자원을 가진 채, 현재 다른 프로세스에 의해 점유되어 있는 자원을 추가로 얻기 위해 반드시 대기하고 있어야 합니다.

3. No Preemption (비선점): 자원들을 선점할 수 없어야 합니다. 모든 자원들은 프로세스가 작업을 완료한 뒤 자발적으로 방출하는 경우에만 방출될 수 있습니다.

4. Circular Wait (순환 대기): n개의 프로세스가 있다면, 1번 프로세스는 2번 프로세스의 자원을 대기하고, 2번 프로세스는 3번 프로세스의 자원을 대기하며, n번 process는 1번 프로세스의 자원을 대기하는 형태를 띄어야 합니다.

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

Deadlock은 이 자원 할당 그래프를 이용해 더 정확하게 표현할 수 있습니다. 이 자원 할당 그래프는 방향 그래프 (Directed Graph)로서, 일반적인 그래프와 같이 정점(vertex)들과 간선(edge)들로 이루어져 있습니다.

• P vertex : Process / R vertex : Resource
• P → R 간선: Request Edge
• R → P 간선 : Assignment Edge

데드락이 아닌 상황

이 그래프에서 cycle이 생기지 않는 다면 Deadlock 일 가능성은 0입니다.

Deadlock

아래 그림은 현재 Deadlock 상황이 맞습니다. 세 개의 프로세스가 서로 자원을 방출하기를 기다리고 있기 때문입니다.

Cycle이 존재하지만 Deadlock 이 아닌 상황

위 그림에서 분명히 P1-R1-P3-R2-P1의 cycle이 존재합니다. 하지만 P4가 R2를 방출하여 주면 자연히 해결이 되기 때문에 Deadlock으로 볼 수 없습니다.

그래프에 cycle이 존재하지 않으면 절대 Deadlock이 발생할 수 없고, cycle이 존재한다면 Deadlock 상황일 수도 있고 아닐 수도 있습니다.

Deadlock 처리 방법

1. Deadlock을 예방하거나 피하는 프로토콜들을 사용한다.

2. Deadlock이 걸리고 나면 이를 탐지하고, 회복시키는 방법을 사용한다.

3. Deadlock에 관한 사항을 무시하고, Deadlock이 일어나지 않기를 바란다.

• Window, Linux 등의 대부분 운영체제가 채택
• 빈번하게 일어나지 않기 때문
• Deadlock 문제는 응용 프로그래머들의 몫..

Deadlock이 발생하지 않도록 하기 위해 시스템은 Deadlock을 예방(Deadlock Prevention)하거나 회피(Deadlock Avoidence)할 수 있습니다.

Deadlock Avoidance는 프로세스가 자원을 요구할 때 일종의 제한을 두어 Deadlock을 방지하는 방법입니다. 우선 Deadlock Prevention에 대해 먼저 공부해 보도록 하겠습니다.

Deadlock Prevention (교착상태 예방)

Deadlock을 성립시키는 4가지 조건 중 적어도 하나를 성립하지 않도록 보장하는 방법

Deadlock이 발생하려면 4가지 필요조건이 모두 성립해야 합니다. 그래서 이 조건들 중 하나라도 성립이 되지 않도록 만들면 Deadlock이 발생하는 것을 예방할 수 있습니다.

1. Mutual Exclusion (상호 배제)

자원들을 공유 가능하게 만들어주면 Mutual Exclusion이라는 조건을 만족시키지 않을 수 있습니다.

예를 들면 읽기 전용 파일 (Read-only File)은 여러 프로세스가 동시에 접근할 수 있도록 허용해주는 방법 등입니다.

하지만 Mutex lock과 같이 본질적으로 공유가 불가능한 자원들이 존재하기 때문에 일반적으로 사용하기는 어려운 면이 있습니다.

2. Hold and Wait (점유하며 대기)

프로세스가 어떤 자원을 점유하고 있다면, 다른 자원을 요청하지 못하게 만드는 방법을 사용할 수 있습니다.

1. 프로세스는 작업을 시작하기 전에 작업에 필요한 모든 자원에 먼저 요청하고 할당을 받는 방법
2. 자신이 가지고 있는 모든 자원을 방출하고 나서야, 새로운 자원을 요청할 수 있게 만드는 방법

이 방법들에는 두 가지 단점이 존재합니다.

1. 자신이 사용할 자원들을 모두 할당받아 놓고 오랫동안 사용하지 않을 수 있기 때문에 자원의 이용도가 낮아질 수 있다
2. 자주 쓰이는 자원들을 여러 개 필요로하는 프로세스라면, 해당 자원들을 모두 모으지 못하면 실행할 수 없기 때문에 기아 문제(starvation)가 발생할 수도 있다

3. No Preemption (비선점)

다음 프로토콜을 사용합니다.

• 우선 몇 개의 자원을 확보하고 있는 프로세스가 만일 다른 자원을 할당받기 위해 대기를 해야 하는 상황이 발생하면, 자신이 가지고 있는 모든 자원들은 선점될 수 있습니다.
  • 즉, 현재 대기해야 하는 프로세스가 무의미하게 자원들을 확보하고 있는 것을 예방하는 것입니다.
• 반대로 한 프로세스가 필요한 자원이 생겼는데, 해당 자원이 다른 자원을 위해 대기하고 있는 프로세스가 가지고 있는 자원이라면, 그 자원을 뺏어올 수 있습니다.

이 프로토콜은 CPU와 같이 선점 가능한 자원일 때만 사용 가능합니다.

4. Circular Wait (순환 대기)

모든 자원들에게 전체적인 순서를 부여하여, 각 프로세스들이 순서에 따라 오름차순으로만 자원을 요청할 수 있도록 만드는 것입니다.

내가 지금 필요로 하는 자원이 내가 지금 확보하고 있는 자원보다 부여된 순서가 낮다면, 확보하고 있는 자원을 방출해야만 필요로 하는 자원에 요청을 할 수 있는 것입니다.

Deadlock Avoidance (교착상태 회피)

핵심 아이디어

어떤 자원을 요청할 때, 추가적인 정보를 제공하도록 요구하는 것.

각각의 프로세스들이 어떤 자원을 어떤 순서로 사용할 것이라는 것을 이미 시스템이 알고 있다면, 미래에 Deadlock이 발생하지 않기 위해 어떤 프로세스가 대기를 해야 하는지 결정할 수 있을 것입니다.

이러한 방법으로 Deadlock의 발생 조건 4가지 중 적어도 하나 이상을 성립하지 않게 만들어줄 수 있습니다.

Safe State & Unsafe State

시스템이 안전한 상태이다

• = 시스템이 어떤 순서로든 프로세스들이 원하는 모든 자원을 Deadlock 없이 차례대로 모두 할당해 줄 수 있다
• 시스템이 안전 순서 (Safe Sequence)를 찾을 수 있다면 그 시스템은 안전한 상태라고 말할 수 있습니다. 이는 현재 남아있는 자원과 또 앞으로 방출될 자원들을 이용해 시간에 따라 모든 프로세스들이 자신이 원하는 자원들을 모두 확보할 수 있다는 뜻입니다.

시스템이 불안전한 상태이다.

• ≠ 데드락에 걸려있다.
• = Deadlock으로 가게 될 수도 있다
• 시스템이 안전 상태에 머무르고 있다면, Deadlock을 완벽히 예방할 수 있지만, 일단 불안전 상태에 들어가게 되면, 프로세스는 Deadlock이 발생할 수도 있는 자원 할당을 막을 수 있는 방법은 없습니다.

즉, 시스템이 불안전한 영역으로 가지 않도록 하는 알고리즘을 생성하는 것이 교착상태 회피의 목표입니다. 최초의 시스템은 당연히 안전 상태에서 시작하므로, 그 후에 프로세스들의 자원 요청을 받아들일지 여부를 판단하는 과정에서 반드시 시스템이 안전한 상태를 유지하도록 하는 결정만을 하게 만들어 주면 됩니다.

물론 이러한 알고리즘들을 이용하면 자원이 남아 있더라도 상황에 따라 프로세스에게 할당을 못해주는 경우가 생길 수 있기 때문에 자원이 이용률은 하락할 수밖에 없습니다.

자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm)

자원 할당 그래프 알고리즘은 각각의 자원 타입들이 하나의 인스턴스만을 가질 때 사용할 수 있습니다.

자원 할당 그래프에서 예약 간선(claim edge)이라는 개념을 도입하여 사용할 수 있습니다. 이 예약 간선은 아래의 그림에서 점선으로 표시된 edge이며, 미래에 해당 프로세스가 가리키고 있는 자원을 요청할 것이라는 뜻입니다.

• Claim edge를 그려봤는데 cycle이 탐지되지 않는다면, 해당 자원은 할당해줘도 시스템은 안전 상태에 머무를 수 있게 됩니다.
• 반대로 Claim edge를 추가한 그래프가 cycle을 포함하고 있다면, 당장 해당 자원을 할당해 주는 것은 시스템을 불안전하게 만들 수 있습니다. 당연히 아래의 그림과 같은 상황이라면, P1은 R2를 할당받아서는 안됩니다.

은행원 알고리즘 (Banker's Algorithm)

자원 할당 그래프 알고리즘은 각각의 자원이 여러 개 씩 존재한다면 (여러 개의 인스턴스를 가진다면) 사용할 수가 없게 됩니다. 아래 그림에서는 R3와 R4가 둘 이상의 인스턴스를 가지기 때문에 (각각 2개, 3개) 자원 할당 그래프 알고리즘을 사용할 수 없습니다.

이러한 상황에서 사용할 수 있는 것이 바로 은행원 알고리즘입니다.

1. 은행원 알고리즘에서는 새로운 프로세스가 시작할 때 자신이 가지고 있어야 할 자원의 최대 개수를 먼저 선언해주어야 합니다.
2. 시스템은 이 요청을 들어주었을 때 시스템이 그대로 안전한 지를 판단하고, 안전하다면 해당 요청을 들어주게 됩니다.
3. 불안전하게 변하게 된다면, 프로세스는 다른 프로세스가 끝날 때까지 대기해야 합니다.

은행원 알고리즘을 사용하기 위해서는 몇 가지 자료구조를 사용해야 합니다. (n은 프로세스의 수, m은 자원의 종류)

Available

• 각 종류 별로 사용 가능한 자원의 개수를 나타내는 벡터이며, 길이는 m이다.

• Available[j] = k라는 뜻은 현재 j라는 자원을 k개 사용할 수 있다는 뜻이다.

Max

• 각 프로세스가 최대로 필요로 하는 자원의 개수를 나타내는 행렬. 크기는 n x m.

• Max[i,j] = k 라면, i라는 프로세스가 j라는 자원을 최대 k개까지 요청할 수 있다는 뜻이다.

Allocation

• 각 프로세스들이 현재 사용하고 있는 자원의 개수를 나타내는 행렬. 크기는 n x m.

• Allocation[i, j] = k라면 현재 i라는 프로세스가 j라는 자원을 k개 사용하고 있다는 뜻이다.

Need

• 각 프로세스가 사용할 수 있는 남은 자원의 개수. 크기는 n x m.

• Need[i,j] = k 라면 i라는 프로세스가 j라는 자원을 k개까지 더 요청할 수 있다는 뜻이다.

• Need[i,j] = Max[i,j] - Allocation[i,j].

1. 안정성 알고리즘 (Safety Algorithm)

현재 시스템이 안전한 지를 검사하는 알고리즘은 다음과 같습니다. 참고로 Work는 크기가 m, Finish는 크기가 n인 벡터입니다.

1. Work = Available로 초기화해주고, 모든 i에 대해 Finish[i] = false로 초기화해줍니다.

2. Finish[i] == false이고, Need[i] <= Work인 i를 찾습니다. 만약 찾을 수 없다면 4번째 단계로 넘어갑니다.

3. Work = Work + Allocation[i], Finish[i] = true를 해준 뒤, 2번째 단계로 돌아갑니다.

4. 모든 i에 대해 Finish[i]==true라면, 해당 시스템은 안전하다고 할 수 있습니다.

2. 자원 요청 알고리즘 (Resource-Request Algorithm)

Request[i]는 i라는 프로세스의 요청 벡터입니다.

• Request[i][j] == k : i라는 프로세스가 j라는 자원을 k개 요청

프로세스 i가 자원을 요청하게 되면 다음과 같은 과정을 거칩니다.

1. 만일 Request[i] <= Need[i]라면 2번째 단계로 갑니다. 그렇지 않다면 이미 시스템에 남아있는 개수보다 더 많은 요청이므로 오류로 처리합니다.

2. 만일 Request[i] <= Available이면 3단계로 갑니다. 그렇지 않다면 현재 요청한 자원이 당장은 없으므로 프로세스는 대기해야 합니다.

3. 시스템이 자원을 할당해 줄 수 있으므로, 다음과 같이 상태를 변경해줍니다.

Available = Available - Request[i]

Allocation[i] = Allocation[i] + Request[i]Need[i] = Need[i] - Request[i]

이렇게 변경한 상태가 안전하다면, 프로세스 i에게 요청받은 자원들을 할당해줍니다. 그렇지 않다면, 다시 원래의 상태로 되돌려줍니다.