교착상태
일부 자원을 가진 상태로 상대방에게 자원을 요구하고, 상대방도 자원을 가진 상태로 요구할 때 일어나는 것이 교착상태이다.
위 그림은 한 방향의 차가 해당 방향을 점유하면서 다른 방향을 점유하려고 하는 상태이다.
DeadLock
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
Resource
- I/O device와 같은 하드웨어일수도 semaphore와 같은 소프트웨어일 수도 있다.
- 프로세스가 자원을 사용하는 절차에는 (Request, allocate, use, release)가 존재한다.
Deadlock 발생의 4가지 조건
- Mutual exclusion(상호 배제): 매 순간 하나의 프로세스만이 자원을 사용할 수 있음. -> 일단 자원을 획득하면 획득한 프로세스만 사용이 가능
- No preemption(비선점): 자원을 빼앗기지 않는다.
- Hold and wait(보유대기): 자원을 보유한 상태로 대기 -> 보유하지 않은 상태로 대기한다면 어느시점에 다른프로세스가 자원을 획득할 수 있기 때문
- (Circular wait)순환대기: 자원을 기다리는 프로세스간에 사이클이 형성되어야 한다. -> A는 B의 자원을 B는 C의 자원을 C는 A의 자원을 요구하는 상태가 이뤄져야 교착상태가 발생가능.
Deadlock을 확인하는 자원 할당 그래프
사각형은 자원, 원은 프로세스를 의미한다. 프로세스에서 자원으로의 화살표는 자원을 요청하고 있는 것이고 자원에서 프로세스로의 화살표는 자원을 소유하고 있다는 뜻이다.
- 그래프에 cycle이 없으면 deadlock이 아니다.
- 그래프에 cycle이 있다면 만약 하나의 인스턴스가 하나의 자원을 의미하면 deadlock이다.
- 만약 몇개의 인스턴스들이 하나의 자원을 의미하면 deadlock의 가능성이 있다.
위의 그림에서 첫 번째 그림은 deadlock이 존재한다. R2가 두개의 인스턴스를 가지고 있는데 P3가 자원을 요청하고 있는 형태로 사이클이 존재하기 때문이다.
반면에 두 번째 그림은 deadlock이 아니다.
비록 R2의 자원 인스턴스가 다른 프로세스에 점유되어있지만 P4가 사이클을 형성하고있지는 않기 때문에 어느시점에 자원을 내어주게 된다. 그럼 이후에 P3가 자원을 획득할 수 있게 되기에 deadlock이 발생하지 않는다.
Deadlock 처리 방법
- Deadlock Prevention: 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것.
- Deadlock Avoidance: 자원 요청에 대한 부가적인 정보를 이용해 deadlock의 가능성이 없는 경우에만 자원을 할당. 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당.
- Deadlock Detection and recovery: Deadlock 발생을 허용하되 그에 대한 detection 루틴을 만들어 deadlock발견시 recover
- Deadlock Ignorance: Deadlock을 시스템이 책임지지 않음. UNIX를 포함한 대부분의 OS가 채택
1️⃣ Deadlock Prevention
데드락이 일어나는 것을 예방하는 방법이다. 다음 4가지는 데드락이 일어나는 조건들에 대해 예방하는 방법을 설명한다.
- Mutual Exclusion
- 하나의 자원에는 하나의 프로세스만 점유할 수 있다는 것을 무시한다. 즉 하나의 자원에 두 개의 프로세스가 점유 가능
- Hold and Wait
- 프로세스 시작 시 모든 자원을 할당받게 한다. 모든 것 갖고 시작하니 요청할 때 데드락이 나오는 상황이 발생이 일어나지 않는다. (점유받지 못한 다른 프로세스가 많이 기다리는 일이 생길 것 같다)
- 자원이 필요할 경우 보유 자원을 놓고 다시 요청
- No Preemption
- 점유되어있는 자원을 process가 뺐을 수 있다.
- CPU나 Memory처럼 쉽게 save하고 restore할 수 있는 하드웨어 자원들에서 주로 사용된다.
- Circular Wait
- 모든 자원유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
- 예시로 순서가 3인 자원R3을 보유 중인 프로세스가 순서가 1인 자원 R1을 할당받기 위해서는 우선 R3을 release하고 R1을 할당받아야 한다.
-> Utilization 저하, throughput 감소, starvation 문제
2️⃣ Deadlock Avoidance
Deadlock Prevention처럼 데드락을 미연에 방지하는 방법이다.
자원 요청에 대한 부가정보를 이용해 현재 이 자원 할당이 데드락으로부터 안전한지 동적으로 조사해서 안전한 경우에만 할당한다.
이는 자원 인스턴스 수에 따라 두 가지 avoidance 알고리즘으로 나뉜다.
- 단일일 때: 자원할당그래프 사용
- 다중일 때: 은행원 알고리즘 사용
자원할당 그래프
점선은 프로세스에서 자원을 향하며 언젠가는 이 자원을 사용할 것이다를 의미한다. 만약 위 그림의 경우 점선일 때는 현재 사용하고 있지는 않아서 cycle이 생기지 않지만 최악의 경우에 cycle이 생길 수 있으니 할당하지 않는 것이다.
은행원 알고리즘
프로세스가 P0~P4까지 5개 존재하고 3가지 종류의 자원이 다음의 인스턴스 수를 가진다고 가정해보자.(A(10), B(5), C(7) instances)
현재 Allocation column에 해당하는 수만큼 자원 인스턴스들이 할당되어있다. 그럼 가용자원(Available)은 A:3, B:3, C:2가 될 것이다.
Max column은 평생 사용할 자원의 수를 의미한다. P0의 경우 A자원 인스턴스를 7번, B를 5번, C를 3번 사용할 것을 의미한다. (한 번에 모든 자원을 할당받을 가능성이 높지 않지만 한 번에 7, 5, 3의 자원을 사용할 수도 있다.)
Need column은 (최대로 사용할 자원 - 현재 가용자원)을 의미한다.
P1이 A자원 1개와 C자원 2개를 요청했다고 가정해보자. 이는 Need테이블을 봤을때 1, 2, 2로 되어있고 A 1개, C 2개를 할당한다고 하더라도 가용자원이 3, 3, 2이기 때문에 충분히 있는 자원으로 할당할 수 있다. 추가로 봐야할 것은 가용자원이 Need보다 높은지에 대한 여부이다. 이 경우에는 남아있는 것이 앞으로 필요한 자원보다 크기 때문에 문제가 없지만 다음의 경우에는 문제가 생긴다.
P0에서 C를 2개 요청한다면, 가용자원이 C 2개보다 많으니 현재는 잘 동작할 수 있다. 하지만 P0의 Need는 Available보다 많기 때문에 현재는 C 2개를 할당할 수 있지만 미래에는 가용자원이 필요한 자원보다 적으니까 데드락이 일어날 수 있어! 그러니까 C 2개조차 할당안할 거야. 만약 할당하고 싶으면 가용자원을 늘려! 라고 하는 것이다.
-> 가용자원 >= 현재 요청한 자원의 수 && 가용자원 >= 앞으로 필요한 자원인 경우에 할당.
-> sequence < P1, P3, P4, P2, P0 >가 존재하므로 시스템은 safe state
3️⃣ Deadlock Detection and Recovery
데드락이 일어난 이후에 회복하는 방법
deadlock avoidance와 같이 자원당 인스턴스에 따라 자원할당그래프와 테이블을 이용하는 방법으로 나뉠 수 있다.
자원 할당 그래프
wait-for 그래프는 자원할당 그래프를 더 간단히 만든 그래프이다.
자원을 표시하지 않는 그래프이며 위 그림의 경우 P1이 자원을 점유하고있고 P4는 그 자원을 요구하고 있는 상태이다.
테이블
은행원 알고리즘과 다르게 Max column이 존재하지 않는다.
은행원 알고리즘은 보수적으로 자원을 할당하지만 이 테이블은 낙관적으로 자원을 할당하기 때문이다.
예를 들어 위의 테이블에서 P0와 P2는 현재 요청하는 자원이 없기 때문에 자신이 점유하고 있는 자원을 언젠가는 내어줄 것이다. 그래서 그 자원을 Available에 포함시키는 것이다.
그리고 그 Available한 자원들은 또 다른 프로세스의 요청에 응답하며 할당해주고 요청하는 자원이 없으면 또 내어주는 것을 반복한다.
그렇기에 이 방법은 은행원 알고리즘보다는 자원의 이용률이 높지만 데드락이 발생할 가능성이 있다. 이때 사용하는 것이 Recovery이다.
Recovery 방법
- Process termination
- 데드락과 연관된 모든 프로세스를 종료한다.
- 데드락 사이클이 종료될떄까지 하나의 프로세스씩 종료한다.
- 자원 선점
- 비용을 최소화할 victim을 설정
- safe state로 rollback하여 prcoess를 restart
자원을 선점하는 경우에는 동일한 희생자가 계속 발생할 수 있기 때문에 얼마나 사용되었는지, 작업시간은 어떠한지를 고려해서 선점하는 알고리즘이 필요하다.
4️⃣ Deadlock Ignorance
Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 하지 않음.
- 드물게 일어나는 deadlock에 대한 조치자체가 더 큰 overhead일 수 있다.
- 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 방법으로 대처
참고자료
