데드락이란
deadlockl, 우리 말로는 교착상태 라고도 한다. 앞선 프로세스 동기화 챕터에서 공유 자원을 여러 프로세서가 접근하는 상황에서 발생하는 race condition에 대해 알아보았다. 교착상태는 서로 다른 프로세스가 서로가 가진 자원을 기다리며 block된 상태를 의미한다.
자원 : 하드웨어, 소프트웨어 등을 모두 포함하는 개념이다. (예: I/O device, CPU 사이클, 메모리 공간, 세마포 등)
데드락의 개념도
데드락의 발생 조건
다음 4가지를 모두 만족하여야 교착상태가 발생할 수 있다.
1.
상호 배제 (mutual exclusion)
•
프로세스가 자원을 사용할 때 다른 프로세스와 동시에 사용할 수 없는 조건을 의미한다.
2.
점유 및 대기 (hold and wait)
•
한 자원을 점유한 상태에서 다른 자원을 요청하기 위해 대기할 수 있는 조건을 의미한다.
3.
비선점 (nopreemption)
•
한 프로세스가 자원을 할당 받으면 작업이 끝날 때 까지 시스템에서 제어권을 뺏을 수 없는 조건을 의미한다.
4.
순환 대기 (circular-wait)
•
여러개의 프로세스가 서로의 자원을 요청하고 있는 상태를 의미한다.
데드락의 처리 방법
주로 4가지의 처리방식이 있다.
•
예방(prevention)
◦
위 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것. 비효율적이라 잘 활용되진 않는다.
•
회피(avoidance)
◦
교착 상태의 발생 가능성을 인정하고, 자원이 요청될 때마다 시스템의 상태를 판단하고 회피하는 전략이다.
◦
은행원 알고리즘이 대표적이다.
◦
비효율이 초래될 가능성이 높아 현실적으로 사용되지 않는다. 탐지와 복구는 교착된 것 같다고 판단될 때 시행하는데, 회피는 자원 요청시마다 항상 실행되어야 하므로 오버헤드가 크다.
•
탐지와 복구(detection and recovery)
◦
데드락 발생을 허용 하되 탐지(detection) 루틴을 두어 데드락 발견시 회복(recovery)하도록 하는 것
•
무시(ignorance)
◦
데드락 발견시 무시함
◦
데드락 예방, 탐지, 복구에 대한 오버헤드가 더 클 수 있기에 대처하지 않음.
◦
Unix 및 대부분 운영체제에서 채택하고 있는 방식
예방(Prevention)
예방을 위해선 어느 하나를 만족하지 않도록 해야한다고 위에서 이야기 했다. 그렇다면 4가지 방법이 있을 것이다.
1.
Mutual Exclusion
a.
공유 해서는 안되는 자원의 경우 반드시 성립해야 함 (예방을 위해 빼놓을 수 없다.)
2.
Hold and wait
a.
프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
b.
방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
c.
방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
3.
No Preemption
a.
프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨.
b.
모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
c.
상태를 쉽게 저장하고 복구할 수 있는 자원에서 주로 사용(CPU, memory)
4.
Circular Wait
a.
모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
b.
예를 들어 순서가 3인 자원 R1을 보유 중인 프로세스가 순서가 1인 자원 R2를 할당받기 위해선 우선 R1을 release해야 한다.
→ Utillization 저하 throughput 감소, starvation 문제!
회피 (Avoidance)
가장 단순한 방법은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방식이다.
•
safe sequence
◦
프로세스의 시퀀스(자원을 필요로하는 프로세스들)가 safe하려면 먼저 특정 프로세스의 자원 요청이 프로세스들이 할당받은 자원들 + 가용 자원에 의해 충족될 수 있어야 한다. (한 프로세스의 요청이 자원의 전체 총량보다 크면 안된다)
◦
조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장한다.
▪
i번째 프로세스의 자원 요청이 즉시 충족될 수 없으면 i 보다 앞선 프로세스가 종료될 때 까지 기다린다.
▪
앞의 프로세스가 종료되면 i번째 프로세스의 자원요청을 만족하여 수행한다.
•
safe state
◦
시스템 내의 프로세스 들에 대한 safe sequence가 존재하는 상태
시스템이 safe state에 있으면 데드락이 없다. unsafe state에 접어들면 데드락 가능성이 존재하는데, 데드락 예방은 시스템이 unsafe state에 들어가지 않도록 보장하는 것이다.
해당 방식은 가용 자원이 모자라 데드락이 발생할 가능성이 있다면 프로세스의 진입 자체를 허용하지 않기 때문에, 비효율이 초래될 수 있다.
회피 알고리즘
•
자원이 하나인 경우
•
자원이 여러개인 경우
탐지 및 회복 (detection and recovery)
자원당 인스턴스가 하나만 있는 경우
예방에서 본 자원 할당 그래프를 활용해도 탐지할 수 있지만, 예방과 달리 자원의 최대 사용량에 대해서 알 필요가 없으므로 간소화한 그래프를 활용할 수 있다.
데드락의 원인이 되는 사이클을 찾는 데 드는 비용은 O(n^2)이다. (나를 제외한 프로세스 모두를 탐색한다고 가정하면 n * n -1)
자원당 인스턴스가 여러개인 경우
은행원 알고리즘과 달리, 낙관적으로 데드락을 판단한다. 요청에서 주어진 자원이 없다면, 기 할당되어있는 자원을 모두 반납할 것이라 전제한다.
즉 위 표에서 P2는 자원을 요청하지 않았기에 가지고 있던 모든 자원을 반납할 것이라 예상하고, P1, P3이 요청한 A를 줄 수 있을거라 가정한다. 이와 달리 P2에서 무언가 요청을 하여서, 남은 자원으로 여러 요청에 필요한 만큼 할당해 줄 수 없는 상황이라면 데드락이라고 본다.
회복 방법
1.
Process termination (프로세스 kill)
A 방식 : 모든 프로세스를 죽인다.
B 방식 : 데드락이 해소될 때 까지, 하나씩 죽여나간다.
2.
Resource Preemption
a.
비용을 최소화할 victim을 선정한다.
b.
safe state로 rollback 해서 프로세스를 다시 시작한다.
c.
기아 문제가 발생할 수 있다.
i.
동일한 프로세스가 계속해서 victim으로 선정되는 경우
ii.
cost factor에 rollback 횟수도 같이 고려
