교착 상태 — 네 조건, 예방·회피·탐지와 은행원 알고리즘

1. 서로를 기다리며 멈추다

앞 글에서 두 번 멈췄습니다. 락을 쥔 채 잠든 소비자와 그 락을 기다리는 생산자, 그리고 왼쪽 젓가락만 든 철학자 다섯입니다. 둘 다 서로가 가진 것을 기다리며 아무도 나아가지 못했습니다. 이것이 교착 상태입니다. 이 글은 교착 상태가 언제 생기는지 조건을 정확히 세우고, 그것을 미리 막는 법, 들어가지 않도록 피하는 법, 생긴 뒤에 찾아내 푸는 법을 차례로 봅니다.

정의부터 세웁니다. 스레드 몇이 한 무리를 이룹니다. 이 무리의 모든 스레드가, 무리 안의 다른 스레드만 일으킬 수 있는 일을 기다리고 있으면 이 무리는 교착 상태에 있습니다. 여기서 기다리는 일은 대개 자원을 얻는 것입니다.

가장 단순한 예를 봅니다. 락이 둘 있습니다. 스레드 T0는 첫째 락을 잡고 둘째 락을 잡으려 합니다. 스레드 T1은 거꾸로 둘째 락을 먼저 잡고 첫째 락을 잡으려 합니다. T0가 첫째를 잡은 직후 T1이 둘째를 잡으면, T0는 T1의 둘째를, T1은 T0의 첫째를 기다립니다. 둘 다 영원히 멈춥니다.

2. 네 조건이 모두 맞아야 생깁니다

교착 상태는 네 조건이 동시에 맞을 때만 생깁니다.

1. 상호 배제 — 자원을 한 번에 한 스레드만 쓸 수 있어야 합니다.
2. 점유 대기 — 자원을 하나 이상 쥔 채로 다른 스레드가 쥔 자원을 더 기다려야 합니다.
3. 비선점 — 쥔 자원은 스레드가 스스로 내놓을 때까지 빼앗을 수 없어야 합니다.
4. 순환 대기 — T0는 T1이 쥔 것을, T1은 T2가 쥔 것을 기다리고, 그렇게 이어지다 마지막이 다시 T0가 쥔 것을 기다리는 원이 있어야 합니다.

방금 본 락 둘의 예는 네 조건을 모두 갖췄습니다.

3. 자원 할당 그래프

교착 상태는 자원 할당 그래프로 그리면 잘 보입니다. 스레드는 원으로, 자원 종류는 사각형으로 그립니다. 같은 자원이 여러 개면 사각형 안에 점을 그 수만큼 찍습니다. 화살표는 두 가지입니다. 스레드에서 자원으로 가는 화살표는 요청입니다. 그 자원을 달라고 기다리는 중이라는 뜻입니다. 자원의 점에서 스레드로 가는 화살표는 할당입니다. 그 스레드가 쥐고 있다는 뜻입니다. 요청이 받아들여지면 요청 화살표가 할당 화살표로 방향을 바꿉니다.

원이 보이면 교착인가

그래프에 원이 없으면 교착 상태는 없습니다. 원이 있으면 경우가 갈립니다. 원 위의 자원이 모두 하나씩뿐이면 틀림없이 교착 상태입니다. 원 안의 누구도 다른 곳에서 자원을 얻을 길이 없습니다. 자원이 여러 개인 종류가 섞여 있으면 교착일 수도 있고 아닐 수도 있습니다. 원 바깥의 스레드가 같은 종류의 다른 하나를 쥐고 있다가 끝나며 내놓으면, 원이 풀릴 수 있기 때문입니다.

4. 다루는 방법은 셋입니다

1. 무시 — 교착 상태가 드물게 일어난다고 보고 아무것도 하지 않습니다. 실제로 많은 운영체제가 이 길을 택하고 응용 프로그램에 맡깁니다.
2. 처음부터 들어가지 않게 하기 — 네 조건 중 하나를 아예 깨 버리는 예방, 그리고 자원을 줄 때마다 위험한지 따져 보는 회피가 있습니다.
3. 탐지와 복구 — 들어가는 것을 허락하되, 찾아내서 풉니다.

5. 예방 — 조건 하나를 깨기

예방은 네 조건 중 하나가 절대 성립하지 않게 만듭니다.

• 상호 배제를 깨려면 자원을 함께 쓸 수 있게 해야 합니다. 읽기만 하는 파일 같은 것은 되지만 프린터나 락처럼 본래 하나만 쓸 수 있는 자원은 안 됩니다.
• 점유 대기를 깨려면 필요한 자원을 시작할 때 한꺼번에 받거나, 아무것도 쥐지 않았을 때만 요청하게 합니다. 대신 자원이 오래 놀고, 많이 필요한 스레드는 굶을 수 있습니다.
• 비선점을 깨려면, 원하는 자원을 바로 못 받는 스레드가 쥐고 있던 것을 모두 내놓게 합니다.
• 순환 대기를 깨는 방법이 가장 흔합니다. 모든 자원에 번호를 매기고, 번호가 커지는 순서로만 요청하게 합니다.

락 둘의 예에서 첫째 락을 1번, 둘째 락을 5번으로 정하면, T1도 첫째부터 잡아야 하니 원이 생길 수 없습니다.

6. 회피 — 안전한지 따지고 주기

회피는 스레드마다 앞으로 각 자원을 최대 몇 개까지 쓸지 미리 신고하게 합니다. 운영체제는 자원을 줄 때마다, 주고 난 뒤의 상태가 안전한지 따져 봅니다.

안전 상태란 모든 스레드를 어떤 순서로 하나씩 끝까지 돌릴 수 있는 상태입니다. 그 순서를 안전 순서라고 합니다. 순서 안의 각 스레드는, 지금 남은 자원에 앞 순서 스레드들이 끝나며 돌려줄 자원을 더하면 필요한 만큼을 다 받을 수 있어야 합니다. 안전 상태이면 교착 상태는 생기지 않습니다. 안전하지 않은 상태가 곧 교착 상태는 아니지만, 그리로 갈 수 있습니다. 그래서 회피는 불안전 상태로 가는 요청을 들어주지 않고 기다리게 합니다.

7. 은행원 알고리즘

자원이 종류마다 여러 개일 때 쓰는 회피 방법이 은행원 알고리즘입니다. 은행이 대출해 줄 때 모든 손님의 최대 한도를 끝내 채워 줄 수 있는지 따지는 것과 같습니다. 표가 넷 필요합니다.

• 가용 — 지금 남은 자원 수
• 최대 — 스레드마다 신고한 최대 요구량
• 할당 — 지금 쥐고 있는 양
• 필요 — 앞으로 더 받아야 할 양. 최대에서 할당을 빼서 구합니다.

예를 봅니다. 스레드는 T0부터 T4까지 다섯, 자원 종류는 A, B, C 셋입니다. 지금 가용은 A 3, B 3, C 2입니다.

안전 검사 절차

1. 작업 칸을 두고 가용 값으로 채웁니다.
2. 아직 안 끝난 스레드 중에서 필요가 작업 칸 이하인 스레드를 하나 찾습니다.
3. 찾으면 그 스레드가 필요한 것을 다 받아 끝까지 돌고, 쥐고 있던 할당을 모두 돌려준다고 봅니다. 작업 칸에 그 스레드의 할당을 더하고, 끝났다고 표시합니다.
4. 이것을 되풀이합니다. 모든 스레드에 끝났다는 표시가 붙으면 안전 상태이고, 끝난 순서가 안전 순서입니다. 도중에 조건에 맞는 스레드가 하나도 없으면 불안전 상태입니다.

8. 연습문제 1 — 이 상태는 안전한가

위 표에서 가용은 A 3, B 3, C 2입니다. 안전 검사 절차를 따라가서 이 상태가 안전한지 판단하고, 안전하다면 안전 순서를 하나 찾아 보십시오. 순서는 하나만 있는 것이 아닙니다. 작업 칸이 어떻게 늘어나는지 적어 가며 풀면 됩니다.

풀이

작업 칸은 3, 3, 2로 시작합니다. T0는 A가 7 필요해 안 되고, T1의 필요 1, 2, 2는 작업 칸 안에 들어갑니다. T1이 끝났다고 보고 할당 2, 0, 0을 더하면 작업 칸은 5, 3, 2가 됩니다. 다음은 T3입니다. 필요 0, 1, 1이 조건에 맞으니 할당 2, 1, 1을 돌려받아 7, 4, 3이 됩니다. 이어서 T4의 필요 4, 3, 1도 맞습니다. 돌려받으면 7, 4, 5입니다. T2의 필요 6, 0, 0도 맞아서 돌려받으면 10, 4, 7입니다. 마지막으로 T0의 필요 7, 4, 3이 맞습니다.

모두 끝났으니 안전 상태이고, 안전 순서 하나는 T1, T3, T4, T2, T0입니다. T1, T3, T0, T2, T4처럼 다른 순서도 가능합니다.

9. 요청이 오면 — 연습문제 2

스레드가 자원을 요청하는 순간, 은행원 알고리즘은 세 단계로 따집니다.

1. 요청이 그 스레드의 필요를 넘지 않는지 봅니다. 넘으면 신고한 최대를 어긴 것이니 오류입니다.
2. 요청이 가용을 넘지 않는지 봅니다. 넘으면 지금은 줄 것이 없으니 기다립니다.
3. 요청만큼 준 척하고 표를 고쳐 봅니다. 가용에서 빼고, 할당에 더하고, 필요에서 뺍니다. 그 상태로 안전 검사를 돌려서 안전하면 실제로 주고, 불안전하면 되돌리고 기다리게 합니다.

예를 들어 T1이 A 1, B 0, C 2를 요청합니다. 필요와 가용 모두 넘지 않습니다. 준 척하면 가용은 2, 3, 0이 되고, 안전 검사를 돌리면 T1, T3, T4, T0, T2 순서로 끝낼 수 있습니다. 안전하니 줍니다.

문제

T1의 요청을 들어준 뒤의 상태에서 시작합니다. 가용은 A 2, B 3, C 0입니다. T1의 할당은 3, 0, 2가 되었고 필요는 0, 2, 0이 되었습니다. 나머지는 그대로입니다. 이때 T0가 A 0, B 2, C 0을 요청합니다. 은행원 알고리즘의 세 단계를 따라가면, 이 요청을 들어주어야 합니까, 기다리게 해야 합니까.

풀이

첫째, T0의 필요는 7, 4, 3이니 요청 0, 2, 0은 넘지 않습니다. 둘째, 가용 2, 3, 0도 넘지 않습니다. 여기까지만 보면 줄 수 있어 보입니다. 셋째, 준 척하고 표를 고칩니다. 가용은 2, 1, 0이 되고, T0의 필요는 7, 2, 3이 됩니다.

이제 안전 검사입니다. 작업 칸 2, 1, 0으로 들어갈 수 있는 스레드를 찾습니다. T1은 B가 2 필요한데 1뿐이라 안 됩니다. T3는 C가 1 필요한데 0이라 안 됩니다. T2는 A가 6, T4는 A가 4 필요해 안 됩니다. T0도 A가 7 필요해 안 됩니다. 아무도 들어갈 수 없으니 불안전 상태입니다. 그래서 T0의 요청은 들어주지 않고 되돌린 뒤 기다리게 합니다. 지금 가용이 충분해도 줄 수 없는 경우가 있다는 것이 회피의 핵심입니다.

10. 탐지와 복구

탐지 — 생긴 뒤에 찾기

세 번째 길은 교착 상태를 허락하고, 생겼는지 찾아내는 것입니다. 자원이 종류마다 하나씩이면 간단합니다. 자원 할당 그래프에서 자원 사각형을 지우고, 스레드끼리 누가 누구를 기다리는지만 남깁니다. 이것을 대기 그래프라고 합니다. 이 그래프에 원이 있으면 교착 상태이고, 없으면 아닙니다. 운영체제는 이 그래프를 들고 있다가 가끔 원을 찾는 검사를 돌립니다.

자원이 여러 개인 종류가 섞여 있으면, 은행원 알고리즘의 안전 검사와 비슷한 절차로 끝낼 수 없는 스레드를 찾습니다. 언제 돌릴지는 교착 상태가 얼마나 자주 생기는지, 생기면 몇 개의 스레드가 묶이는지에 따라 정합니다. 요청을 바로 들어줄 수 없을 때마다 돌리면, 원을 만든 바로 그 스레드를 찾을 수 있습니다.

복구 — 원을 끊기

스레드는 프로세스에 속해 있으니 복구는 보통 프로세스 단위로 합니다. 방법은 둘입니다.

• 프로세스를 끝내기 — 원에 묶인 프로세스를 모두 끝내면 확실하지만 그동안 한 일이 다 날아갑니다. 그래서 하나씩 끝내 보며 원이 풀리는지 봅니다. 누구부터 끝낼지는 우선순위, 얼마나 오래 돌았는지, 얼마나 남았는지, 자원을 얼마나 쥐고 있는지 같은 기준으로 정합니다.
• 자원을 빼앗기 — 빼앗을 대상을 비용이 가장 적은 쪽으로 고르고, 그 프로세스를 안전했던 이전 상태로 되돌려 다시 시작하게 합니다. 이때 같은 프로세스만 계속 희생되지 않도록 조심해야 합니다. 앞에서 본 기아가 여기서도 생길 수 있습니다.

정리

교착 상태는 상호 배제, 점유 대기, 비선점, 순환 대기가 모두 맞을 때 생깁니다. 자원 할당 그래프에서 원으로 드러나고, 자원이 하나씩뿐이면 원이 곧 교착입니다. 예방은 네 조건 중 하나를 깨며, 자원에 번호를 매겨 차례로만 요청하게 하는 방법이 가장 흔합니다. 회피는 줄 때마다 안전한지 따지고, 은행원 알고리즘은 안전 순서를 찾아 봅니다. 탐지는 대기 그래프에서 원을 찾고, 복구는 끝내거나 빼앗아 원을 끊습니다. 지금까지 프로세스와 스레드가 프로세서를 어떻게 나눠 쓰는지 봤습니다. 다음 글부터는 또 하나의 큰 자원, 메모리를 어떻게 나눠 쓰는지 봅니다.