각자 일부 자원을 가지고 있으면서 상대방이 가지고 있는 다른 자원도 원하는 경우 데드락 발생.
데드락이 발생하는 조건 4가지가 있다. 이를 모두 만족해야 데드락이 발생한다.
- Mutual exclusion(상호 배제)
- 가지고 있는 동안에는 내가 독점적으로 쓴다.
- No preemption(비선점)
- 비선점. 자원을 가지고 있을 때 빼앗기지 않는다.
- 빼앗기지 않기 때문에 데드락 안 생긴다.
- Hold and wait(보유대기)
- 내가 가진 것을 내어놓지 않으면서 자원을 더 원하니까 데드락 발생
- Circular wait(순환대기)
- 필요로 하는 자원들이 꼬리에 꼬리를 물고, 서로가 원하는 자원을 가지고 있어서 사이클을 생성하는 경우.
데드락이 일어났는지 확인하는 방법
자원 -> 프로세스 의미: 자원이 해당 프로세스에 속해있다. 프로세스가 자원을 가지고 있다.
프로세스 -> 자원 의미: 이 프로세스가 자원을 요청했는데 아직 획득하지 못했다.
사각형 안에 작은 점들이 있는데, 이는 자원의 수(인스턴스)를 의미한다.
위 그림은 데드락일까 아닐까?
그래프에 사이클 없으면 데드락 아니다. 사이클 있으면 데드락 있을 수도 있고 아닐 수도 있다. 만약 자원당 인스턴스가 하나씩밖에 없다면 사이클은 곧 데드락을 의미한다. 만약 자원 인스턴스가 여러개 있는 상황이라면 데드락일수도 있고 아닐 수도 있다.
왼쪽 그림은 데드락. 오른쪽 그림은 P2나 P4가 자원을 내려놓으면 데드락 안 생김. 자원이 여러개 있기 때문에 사이클이 있지만 데드락이 생기지 않는 경우.
위 그림은 데드락 아니다.
위의 두가지 방식은 데드락이 생기지 않도록 미연에 방지하는 것.
밑에 두가지 방식은 데드락이 생기도록 놔두는 것.
현대 운영체제는 대부분 Deadlock Ignorance
데드락이 발생하는 조건 중 하나를 원천 차단해서 데드락이 발생하지 않도록 하는 것.
Mutual Exclusion 방식은 우리가 막을 수 있는 조건은 아님. 한번에 여러 프로세스가 공유해서 쓸 수 있는 자원이 있다? 그렇다면 Deadlock 얘기 조차 나오지 않았음.
Hold and Wait 자원을 기다리는 상황에서는 자원을 보유하고 있지 않으면 된다. 프로세스가 시작될 때 이 프로세스가 필요로 하는 자원들을 모두 할당하도록 한다. 그런데 이 방식은 문제가 있다. 효율적이지 않음!
두번째 방법은 자원은 그때그때 할당받지만, 만약 내가 Hold하면서 기다려야 한다면 Hold한 자원을 다 뱉어내고 기다려야 하는 자원을 기다린다.
자진반납해서 문제를 해결한다.
No Preemption은 데드락이 생기는 이유가 가지고 있는 자원을 빼앗을 수 없기 때문이다. 자원을 Preemption 할 수 있게 하면 데드락이 안 생긴다. CPU 자원은 Preemption한 자원이다(time interrupt). CPU나 메모리 같은 자원은 자원의 현재 상태를 저장하고 다시 불러올 수 있는 자원. 그래서 Preemption하게 데드락을 막을 수 있다.
일부 자원은 Preemption을 허용해서 데드락을 막으면 이미 실행하는 것들이 엉망이 되기도 한다.
Circular Wait 은 필요한 자원들이 꼬리에 꼬리를 물어서 사이클이 만들어지는 경우이다. 이를 막기 위해서는 자원 순서를 정해두는 것. 1,3,5번 자원을 내가 획득해야 한다면, 항상 낮은 번호부터 획득하고 높은 번호를 획득하도록 하는 것이다.
누구는 1번을 가지고 있으면서 3번을 기다리고, 누구는 3번을 가지고 있으면서 1번을 기다리면 데드락 발생.
이렇게 4가지 경우는 Prevention으로 미리 예방하는 것.
자원 이용률 낮아지고, 시스템 전체 성능이 낮아짐. 생기지도 않을 데드락을 생각해서 미리 여러 조건들을 달아둔다.
프로세스가 시작될 때, 이 프로세스가 쓸 총 자원을 알고 있다고 가정하고 데드락이 생길 경우를 피한다.
자원에 대한 인스턴스가 하나밖에 없다면 위 방식으로 데드락 피해간다. 점선 화살표가 추가된다.
점선 화살표는 프로세스로부터 자원으로 가는 경우만 있다. 프로세스가 적어도 한번은 해당 자원을 사용할 일이 있다는 의미이다.
마지막 그림은 데드락이 아니다. 아직 1번 프로세스가 2번 자원을 요청하지 않았기 때문이다. 2번 프로세스가 반납을 한 뒤에 자원을 요청하면 데드락 발생하지 않는다. 하지만 최악의 상황은 데드락이 될 수도 있다. 데드락 위험성 있으면 자원을 주지 않는다.
이 경우는 자원당 인스턴스가 하나밖에 없는 경우이다.
자원당 인스턴스가 여러개 있다면 위 알고리즘으로 데드락을 막는다.
Allocation는 현재 할당. Max는 프로세스가 총 사용할 자원들.
P0의 요청은 가용자원 (3,3,2) 내에서 해결이 안된다. 그래서 자원 할당을 해주지 않는다. Banker's Algorithm은 데드락이 절대 생기지 않도록 하는 방식이라 보수적이기 때문이다.
P1이 요청을 하면 앞으로 최대 요청할 수 있는 자원이 (1,2,2)이고 이를 가용자원(3,3,2) 내에서 할당해줄 수 있기 때문에 바로 할당해준다.
할당 가능성이 있는 자원보다 가용자원이 많을 때 할당해주기 때문. 각 프로세스의 최대 요청자원을 다 충족할 수 있는 sequence가 존재한다면 safe한 system. 프로세스들이 한꺼번에 최대 요청을 하더라도 데드락이 생기지 않는 요청에 대해서만 받아들인다. 굉장히 비효율적. 자원이 남아도 혹시 모를 일 때문에 자원 할당을 안해준다. 데드락은 사실 거의 안 생긴다.
safe한 상태에서 가용자원만으로 충족되지 않는 프로세스에 자원을 줬다고 해서 데드락은 아니다.
자원당 인스턴스가 하나일 때는 그래프로 해결 가능. 사이클이 있으면 데드락인 상황이다.
자원이 하나가 있고 거기에 연류되어 있는 프로세스가 2개인 상황. 자원을 빼버리고 wait-for 그래프를 그린다. 훨씬 더 간결하게 판단할 수 있다. 사이클이 있는지 확인하면 된다.
wait-for 알고리즘에서 사이클 찾는 알고리즘은 O(n*n)
자원당 인스턴스가 여러 개 있는 경우는 위처럼 Detection 가능하다.
데드락인지 아닌지 판단할 때는 낙관적으로!
만약 위처럼 P2가 C자원을 하나 더 요청했다면?
데드락! 왜냐면 Request 없는 프로세스는 P0뿐. P0가 자신이 가진 B 자원을 내놓는다 하더라도 다른 프로세스들이 원하고 기다리는 자원은 A, C이다. 데드락!
데드락을 탐지할 때 일단 가용자원 몇 개 있는지 본다. 가용자원으로 처리 가능한게 있는지 보는 것. 요청하지 않은 프로세스의 것은 다 가용자원으로 합치고 이때 처리 가능한 게 있는지 본다. 이렇게 쭉 처리해나갈 수 있으면 데드락 발생 안한다.
탐지하고 회복은 어떻게 할까?
첫번째는 데드락에 연루된 프로세스를 모두 죽인다. 두번째는 데드락에 연루된 프로세스를 하나씩 죽여보고 데드락이 해소되는지 아닌지 살펴본다.
프로세스를 종료시키기도 하고, 데드락에 연루된 프로세스에게 자원을 뺏기도 한다. 누구한테 뺏을지 정하고 자원을 뺏어서 데드락 해소한다.
safe state로 rollback해서 process를 restart한다.
문제는 자원을 뺏었는데 다른 프로세스가 갖기 전에 해당 자원이 또 할당 받으면 문제가 발생할 수 있다. 데드락 발생 상황이 또 재연된다. 그리고 기아 문제도 해결해야 한다.
데드락 일어나든 아니든 상관하지 않는다. 데드락이 발생하면, 시스템이 느려지거나 프로세스가 정지되는 등 사용자가 이상함을 발견하게 된다. 사용자가 알아서 처리하도록 한다. 운영체제는 데드락에 대처하지 않는다.
