● 교착 상태 (Deadlock)
두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
위의 그림은 사거리가 막혀있는 상황이다. Deadlock이란 일련의 프로세스들이 서로가 가진 자원을 기다리면서 잠들어 있는 상태를 의미한다.
자원이라는 것은 하드웨어 자원일 수도 있고 소프트웨어 자원일 수도 있다.
예를 들어, 하드웨어 자원일 경우 tape drive 두 개가 있다고 했을 때, 하나의 tape drive에서 읽어 다른 tape drive에다가 copy를 하고 싶다고 하자.
두 프로세스가 각각 tape 두 개의 자원을 가져야 읽고 쓰는 행위를 할 텐데, 상대방이 가진 자원을 서로 계속 요구하게 되면 프로세스 진행이 되지 않는다.
소프트웨어 자원일 경우에는 프로세스 0 은 자원 A를 얻은 후, 자원 B를 얻고, 프로세스 1은 자원 B를 얻은 후 자원 A를 얻게 되면 Deadlock 상태에 빠진다.
프로세스가 자원을 사용하는 절차는 크게 4 단계이다. 자원 요청 → 자원 획득 → 자원 사용 → 자원 반납
● Deadlock 문제
- Deadlock : 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
- Resource (자원) : 하드웨어 ,소프트웨어 등을 포함하는 개념 Ex) I/O device, CPU cycle, memory space, semaphore 등 ..
- 프로세스가 자원을 사용하는 절차 : Request, Allocate, Use, Release
✓ Deadlock Example 1
시스템에 2개의 tape drive가 있다.
프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.
✓ Deadlock Example 2
Binary semaphores A and B
● Deadlock 발생의 4가지 조건
- Mutual exclusion : 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
- No preemption : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.
- Hold and wait : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다.
- Circular wait : 자원을 기다리는 프로세스간에 사이클이 형성된다.
프로세스 P0, P1, ... , Pn이 있을 때, 프로세스 0은 프로세스 1이 가진 자원을 기다리고 프로세스 1은 프로세스 2가 가진 자원을 기다리고...
프로세스 n은 프로세스 0가 가진 자원을 기다리는 상태
● 자원 할당 그래프 (Resource-Allocation Graph)
아래 그림에서 동그라미는 프로세스, 사각형은 자원, 사각형 안에 작은 점은 자원의 수를 나타낸다.
프로세스에서 자원으로 나가는 화살표의 의미는 프로세스가 해당 자원을 요청했는데 아직 획득하지는 못한 상태이며,
자원에서 프로세스로 나가는 화살표의 의미는 프로세스가 자원을 갖고 있다는 의미이다.
자원의 수가 두 개 또는 세 개가 있다는 건 그들 중 아무거나 갖다 써도 상관이 없는 상황이다.
지금 현재의 상황은 프로세스 1은 2번 자원을 가지고 있으면서 1번 자원을 기다리는데, 1번 자원은 프로세스 2가 갖고 있는 상황이다.
현재 상황이 Deadlock이냐 아니냐를 그래프를 보면서 확인하는 방법은 화살표를 따라가서 사이클이 있으면 데드락이고,
사이클이 없으면 데드락이 아니라고 판단한다.
위의 두 그래프는 사이클을 가지고 있다. 자원 당 instance가 한 개밖에 없고 사이클이 있으면 Deadlock이라고 판단한다.
그런데 만약 자원에 instance가 여러 개 있으면 Deadlock일 수도 Deadlock이 아닐 수도 있다.
첫 번째 그림은 R2에 자원이 두 개가 있지만 사이클이 두 개가 만들어진 상황이기 때문에 데드락에 걸릴 수 있다.
두 번째 그림은 Deadlock이 아니다. 사이클이 만들어져 있기는 하지만 사이클과 관련된 자원이 두 개씩 있다.
그 자원들이 모두 할당이 되어있기는 하지만 데드락은 아니다.
프로세스 1은 자원 1번을 요청했는데 그 자원이 하나는 프로세스 3에 가 있고 또 다른 자원은 프로세스 2가 갖고 있다.
프로세스 2와 프로세스 4는 데드락에 연루된 프로세스가 아니다.
● Deadlock 처리 방법
- Deadlock Prevention : 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
- Deadlock Avoidance : 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원 할당, 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
- Deadlock Detection and recovery : Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
- Deadlock Ignoreance : Deadlock을 시스템이 책임지지 않고, UNIX를 포함한 대부분의 OS가 채택
Deadlock Prevention과 Deadlock Avoidance는 애초에 데드락이 발생하지 않게 하는 것이고 Deadlock Detection and Recovery와 Deadlock Ignoreance는 데드락이 발생하도록 놔두는 방법이다.
Deadlock Detection and Recovery는 시스템이 느려졌을 때, Deadlock Detecting을 한 후 Recovery 하는 방법이다.
Deadlock Ignoreance는 Deadlock이 발생해도 아무런 조치를 취하지 않으며, 운영체제가 관리를 안 하면 사용자가 알아서 프로세스를 죽이던지 해서 Deadlock을 해결한다. Deadlock은 빈번히 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해서 훨씬 더 많은 오버헤드를 들이는 것이 비효율적이기 때문에 현대적인 시스템에서는 이 방법을 사용한다.
① 교착 상태 예방 (Deadlock Prevention)
Deadlock에 들어가지 못하게 하는 방법이다. Mutual Exclusion은 막을 수 있는 조건이 아니다.
자원을 한 번에 여러 프로세스가 공유해서 쓸 수 있는 자원이라고 하면 애초에 데드락에 대한 얘기도 나오지 않았을 것이다.
Hold and Wait을 없애려면 자원을 기다려야 하는 상황에서는 자원을 보유하고 있지 않으면 된다.
첫 번째 방법은 어떤 프로세스가 실행될 때, 중간에 추가로 필요한 자원이 없을 때 자원을 모두 할당받게 한다.
그런 다음 다 쓰고 나서 프로세스가 종료될 때 자원을 반납한다.
처음부터 Hold 하고 시작하기 때문에 wait 할 일이 없어서 Deadlock이 생기지 않는다.
하지만 이렇게 되면 매 시점마다 필요로 하는 자원이 다를 텐데 미리부터 그 자원들을 다 보유하고 있으면 자원에 대한 비효율성이 생긴다.
두 번째 방법은 자원이 필요할 때 할당받는 방법이다. 만약 내가 어떠한 자원을 Hold 하고 있는데 다른 자원을 기다려야 하는 상황이 된다면 이미 Hold 한 자원도 다 반환을 하고 기다린다. 필요한 자원을 모두 다 얻거나 모두 다 얻지 못하거나 한다.
No Preemption은 자원을 Preemption 할 수 있게 한다면 데드락에 걸리지 않는다. Preemption에서는 CPU나 메모리는 자원을 빼앗아 올 수 있는데, 왜 아무 때나 뺏어도 되냐면 현재 자원의 사용상태를 save 하고 restore 할 수 있는 자원이기 때문이다. CPU를 쓰다가 빼앗겼다가 다시 CPU 제어권을 얻었을 때 그 바로 다음 지점부터 실행하는 것이 가능하다. 이러한 자원들은 빼앗는 걸 통해서 Deadlock을 막을 수 있다. 그런데 어떠한 자원은 빼앗으면 문제가 생겨 Preemption을 허용하기 어려운 자원이 있다. 그럴 때에는 이 방법을 사용하기 어렵다.
Circular Wait을 막거나 자원마다 순서를 정해놓는 방법이 있다. 자원 1, 2, 3, 4, 5의 자원이 필요하다고 하면 낮은 번호를 먼저 획득해야 높은 자원을 획득할 수 있도록 한다. 원천적으로 Deadlock을 막을 수는 있지만 자원에 대한 이용률이 낮아지고 전체 시스템이 나빠지는 Starvation 문제가 발생할 수 있다. 생기지도 않을 Deadlock을 미리 생각해서 제약 조건을 많이 달아 놓는 것은 상당히 비효율적이다.
✓ Mutual Exclusion
- 공유해서는 안되는 자원의 경우 반드시 성립해야 함
✓ Hold and Wait : 프로세스가 자원을 요청할 때 다른 어떤 자원을 할당받게 하는 방법
- 방법 1 : 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
- 방법 2 : 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
✓ No Preemption
- 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점 됨.
- 모든 필요한 자원을 얻을 수 있을 때, 그 프로세스는 다시 시작 됨.
- state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, memory)
✓ Circular Wait
- 모든 자원 유형에서 할당 순서를 정하여 정해진 순서대로만 자원 할당.
- 예를 들어, 순서가 3인 자원 Ri을 보유중인 스로세스가 순서가 1인 자원 Rj을 할당받기 위해서는 우선 Ri을 release 해준다.
→ Utilization 저하, Throughout 감소, Starvation 문제
② Deadlock Avoidance (교착 상태 회피)
이 방법도 데드락을 애초에 막는 방법이다. 프로세스가 시작될 때 이 프로세스가 쓸 자원의 최대량을 미리 알고 있다고 가정하고 데드락을 피해 가는 방법이다.
평생 쓸 자원의 양을 알고 있기 때문에 어떤 프로세스가 자원을 요청했을 때, 그 자원을 주게 되면 데드락 발생 가능성이 있겠다고 생각이 들면 자원이 있는데도 불구하고 자원을 내어주지 않는다.
자원 요청에 대한 부가정보를 이용해서 자원 할당이 Deadlock으로부터 안전한 지 동적으로 조사해서 안전한 경우에만 할당을 한다.
- safe state : 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
- safe sequence : 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
✓ 프로세스의 sequence <P1, P2, ... , Pn >이 safe 하려면..
Pi(1≤i≤n)의 자원 요청이 가용 자원 + 모든 Pj (j<i)의 보유자원에 의해 충족되어야 함.
조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
- Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다린다.
- Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.
Deadlock Avoidance는 두 가지 알고리즘이 있다. 한 개씩밖에 없을 경우에는 자원 할당 그래프를 보고 알 수 있고,
자원의 instance가 여러 개 있으면 banker's 알고리즘을 통해 알 수 있다.
● Resource Allocation Graph Algorithm (자원 할당 그래프 알고리즘)
점선 화살표는 항상 프로세스로부터 자원으로 가는 방향만 있고, 평생에 한 번은 해당 자원을 사용할 일이 있다는 의미이다.
만약 프로세스 2가 해당 자원을 요청하게 되면 점선 화살표가 실선으로 변경된다.
두 번째 그림을 보면 프로세스 1은 R1을 갖고 있고 프로세스 2는 1번 자원과 2번 자원을 요청한 상태이다.
이때 2번 자원은 아무도 갖고 있지 않기 때문에 요청한 프로세스에게 줄 수 있다. 프로세스 2에게 줄 수 있으니 주게 되면 세 번째 그림처럼 된다.
하지만 세 번째 그림은 점선을 포함해 원형이 만들어지기 때문에 Deadlock의 가능성이 있다.
Deadlock 가능성이 있는 자원 요청에 대해서는 애초부터 받아들이지 않고 그대로 내버려 두므로 프로세스 2가 2번 자원을 요청해도 자원을 주지 않는다.
하지만 프로세스 1이 2번 자원을 요청할 경우에는 Deadlock의 가능성이 없기 때문에 자원을 할당해 준다.
● Banker's 알고리즘
자원 당 instance가 여러 개 있는 경우에 Deadlock을 막는 방법이다.
프로세스들이 자원을 요청했을 때, 그 요청을 받아들일 것인지 아니면 받아들이지 않을 것인지만 결정한다.
Banker's 알고리즘은 굉장히 보수적이어서 절대로 Deadlock이 생기지 않도록 한다.
항상 프로세스들이 최대 요청을 할 것이라고 가정을 한 후, 그 최대 요청이 현재 가용 자원을 가지고 충족을 하는지를 본다.
충족이 되면 어떤 요청이든 요청을 받아들이고 충족이 되지 않으면 받아들이지 않는다.
현재 가용자원(Available)과 각 프로세스들이 작업을 완료하기 위해 필요한 자원(Need)을 비교하여 당장 작업을 마칠 수 있는 프로세스부터 자원을 할당하여 그 프로세스가 작업을 완료하고 반환하는 자원을 다른 프로세스에게 다시 할당한다.
위 그림에서 다섯 개의 프로세스와 세 종류의 자원이 있으며 자원 종류별로 각각 10개, 5개, 7개가 존재한다.
프로세스 0은 B자원을 한 개 가지고 있고, 프로세스 1은 A자원을 두 개 갖고 있는 상황(Allocation)이다.
Deadlock Avoidence는 프로세스가 시작될 때 평생 사용할 Maximum 자원을 미리 정해 놓는다.
예를 들어 프로세스 2는 평생 동안 A자원은 9개, C자원은 2개를 사용하며 B자원은 쓸 일이 없다고 정해놓는다.
전체 자원 Instance에서 할당된 자원을 빼면 가용 자원은 A 3개(10-(2+3+2)=3), B는 3개(5-(1+1)=3), C 2개(7-(2+1+2)=2)이다.
프로세스들이 자원을 요청하면 남아있는 자원은 줄 수 있지만 무조건 주는 건 아니고 문제가 발생할 가능성이 있다면 자원을 주지 않는다.
Need는 최대 요청 가능한 양에서 현재 할당된 양을 뺀 추가 요청할 수 있는 양이다.
이 알고리즘은 Deadlock에는 걸리지 않지만 굉장히 비효율적인 방식이다.
자원이 남아있는데도 혹시 모를 상황에 대비해 자원을 내어주지 않기 때문이다.
예를 들어, 프로세스 1이 자원 a 한 개, 자원 c 두 개를 요청했다고 했을 때, 자원 a 세 개, 자원 c 두 개가 남아있기 때문에 가용 자원에서 줄 수 있지만, 프로세스 1이 추가 요청할 수 있는 양이 가용 자원을 가지고 모두 충족이 가능한가를 보고 Deadlock으로부터 안전하다고 판단될 때 자원을 할당해 준다.
✓ 가정
- 모든 프로세스는 자원의 최대 사용량을 미리 명시
- 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.
✓ 방법
- 기본 개념 : 자원 요청 시 safe 상태를 유지할 경우에만 할당
- 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택
그런 프로세스가 없으면 unsafe 상태
그런 프로세스가 있으면 그 프로세스에게 자원 할당
→ 할당받은 프로세스가 종료되면 모든 자원 반납 → 모든 프로세스가 종료될 때까지 이러한 과정 반복
③ 교착 상태 탐지 및 복구 (Deadlock Detection and Recovery)
● 자원당 인스턴스가 하나뿐일 때 데드락을 검사하는 방법 : 자원할당 그래프
✓ Deadlock Detection
- Resource Type Single Instance인 경우 : 자원 할당 그래프에서의 Cycle이 곧 Deadlock을 의미
- Resource Type Multiple Instance인 경우 : Banker's Algorithm과 유사한 방법 활용
✓ Wait-for Graph 알고리즘
- Resource Type Single Instance인 경우
- 자원 할당 그래프의 변형이며 프로세스만으로 node 구성
- Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk→Pj
- Wait-for-Graph에 Cycle이 존재하는지를 주기적으로 조사 : O(n^2)
● 자원당 인스턴스가 여러 개 일 때, 데드락을 검사하는 방법
Deadlock Detection은 어떤 프로세스가 자원을 최대로 얼마나 요청할지 미리 알 필요가 없으며 프로세스가 자원을 요청하면 자원을 할당한다.
현재 요청한 자원이 없는 프로세스들이 갖고 있는 자원들은 반납한다고 가정한다.
프로세스 0은 자원 b를 한 개 갖고 있으며, 프로세스 2는 자원 a 세 개, 자원 c 세 개를 갖고 있다.
프로세스 0은 현재 요청한 자원이 없기 때문에 낙관적으로 보면 프로세스 0과 프로세스 2는 자원을 반납할 것이라고 가정한다.
그럼 가용 자원은 총 자원 a는 세 개, 자원 b는 한 개, 자원 c는 세 개가 된다. 이 반납한 자원을 가지고 프로세스 3에게 자원을 줄 수 있다.
이러한 식으로 자원들을 가지고 처리 가능한 프로세스들에게 자원을 주고받는 과정을 체크해야 한다.
Deadlock이 발견되면 Recovery를 해야 한다. Recovery는 크게 두 가지 방법이 있다.
첫 번째 방법은 Deadlock에 연루된 프로세스들을 모두 종료시키거나, Deadlock이 없어질 때까지 Deadlock과 연루된 프로세스들을 하나씩 종료시키는 방법이 있다.
두 번째 방법은 Deadlock에 연루된 프로세스들의 자원을 뺏는 방법이다.
어느 프로세스에게서 자원을 빼앗을지 정한 다음, 그 프로세스의 자원을 빼앗아 Deadlock을 없앤다.
Safe state로 Rollback을 해서 프로세스를 restart 시키면 Deadlock이 없어질 수 있으나, 어떤 프로세스에게서 자원을 빼앗았는데 다른 프로세스가 갖기 전에 Deadlock을 유발한 프로세스가 해당 자원을 또 요청해서 자원을 가져갈 수 있다.
Deadlock을 없애놨는데 똑같은 패턴이 또 반복될 수 있다는 소리이다. 그래서 자원을 빼앗은 다음에 패턴을 조금씩 바꿔서 실행해야 Deadlock이 없어질 수 있다.
✓ Recovery 방법
Process termination
- abort all deadlocked processes
- abort one process at a time until the deadlock cycle is eliminated
Resource Preemption
- 비용을 최소화할 victim의 선정
- safe state로 rollback하여 process를 restart
- Starvation 문제 : 동일한 프로세스가 계속해서 victim으로 선정되는 경우, Cost factor에 rollback 횟수도 같이 고려
● 교착 상태 무시(Deadlock Ignoreance)
Deadlock이 일어나지 않는다고 생각하고 아무런 조치를 취하지 않는 방법이다.
Deadlock은 매우 드물게 발생하기 때문에 Deadlock에 대한 조치 자체가 더 큰 overhead일 수 있다.
결론적으로 Deadlock이 생기지 않게 하는 것도 자원을 비효율적으로 쓰게 되고 Deadlock을 Detection 하는 것도 오버헤드가 크다.
그렇게 때문에 만약 시스템에 Deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 인지한 후, 직접 프로세스를 죽이는 등의 방법으로 대처를 한다. UNIX, Windows 등 대부분의 범용 OS가 채택한 방식이다.
