[OS]데드락(Dead Lock), 교착 상태

데드락(Dead Lock)은 교착 상태라고도 불립니다.

 

 

 

1. 교착 상태가 뭘까요?

 

교착 상태란 자원이 한정적인 상황에서 두 개 이상의 프로세스가 각자 먼저 확보한 자원을 가진 채 상대방의 자원을 필요로 할 경우, 외부 조치가 없는 한 프로세스들이 아무 일도 하지못하고 계속 기다려야 하는 상황 을 말합니다.

 

 

잠깐 주의!

 

무한 대기와 교착 상태의 차이점

- 무한 대기는 프로세스가 자원을 할당 받는데 오랜 시간이 걸리는 것뿐 언젠간 할당 받을 수 있는 상태.

- 교착 상태는 아무리 오랜 시간이 흘러도 프로세스가 자원을 할당 받지 못하고 마비된 상태.

 

 

그렇다면 교착 상태가 일어나면 어떤 문제점이 발생될까요? 2가지가 있습니다.

 

① 해당 프로세스들이 더 이상 실행되지 못하여 사용자들에게 응답해 주지 못한다는 점.

② 보유된 자원들이 교착 상태에서 벗어나기 전까지는 전혀 활용되지 못한다는 점.

 

이렇게 교착 상태가 안겨주는 문제점은 시스템 성능 저하로 이어질 수밖에 없습니다.

 

 

 

2. 교착 상태가 발생하는 근본적 원인 4가지

 

조건을 알아보기 전에 먼저 생각해볼게 있습니다. 교착 상태는 왜 생기는 걸까요?

 

한정된 자원의 갯수보다 사용하고자 하는 프로세스의 갯수가 더 많기 때문입니다.

 

교착 상태가 발생하는 근본적 원인은 4가지가 있고, 이 조건중 하나라도 발생하지 않는다면 교착 상태를 해결할 수 있습니다.

 

① 자원의 배타적 사용

 배타적으로 사용할 수 있는 자원이 존재하고, 이를 얻기 위해 프로세스들은 경쟁하기 때문에 교착상태의 원인이 됩니다. 여기서 배타적 사용이란 1번 자원이 있다고 했을 때, 하나의 프로세스가 1번 자원을 할당받았다면 다른 프로세스들은 할당 받은 프로세스가 작업을 완료하기 전까지 1번 자원을 사용할 수 없는 것을 말합니다.

 

② 자원의 부분 할당 (보유와 대기 - Hold and wait)

 프로세스가 자신을 실행하기 위해 자원을 일부분씩 확보 및 실행해 나가다가 어느 순간 할당 불가능한 자원을 만나게 되고 현재까지 확보한 자원을 모두 소유한 채 대기 상태에 빠지게 되는 것을 말합니다. 교착 상태에 빠질 가능성을 높인다고 볼 수 있습니다.

 

③ 자원의 비선점성

 한 프로세스가 사용하고 있는 자원을 다른 프로세스가 필요하다고 하여도 그 자원을 선점해서 쓸 수 없습니다. 현재 사용중인 프로세스가 끝나길 기다려야 합니다.

 

④ 자원 대한 환형대기

자원에 대한 환형 대기

프로세스들이 각자의 자원은 점유한 채로 상대가 가진 자원을 요구하는 상황입니다. 그래프 이론에서 사이클이 형성되는 모습을 볼 수 있습니다. 결과적으로 이 프로세스들은 대기 상태가 되어버리고 교착 상태가 일어납니다.

 

 

 

 

3. 교착 상태의 해결

해결책은 예방, 회피, 탐지, 복구 기법 총 4가지가 있고, 탐지 기법은 교착 상태를 탐지한 후 복구 작업을 수반하므로 탐지와 복구 방법은 하나로 묶어서 봐도 됩니다.

 

●예방 기법

위에서 언급한 원인들을 각각 없애는 방법으로 교착 상태를 예방 할 수 있습니다.

① 자원의 배타적인 사용 -> 모든 자원을 공유 가능 자원으로 바꾸는 경우

  프린터나 테이프 같은 차례대로 사용해야 하는 자원은 사용할 수가 없기 때문에 불가능하다.

 

② 자원의 부분 할당 -> 필요한 자원을 한 번에 모두 할당

 일부 자원만 있으면 실행 가능한 프로세스들이 모든 자원을 할당받기 위해 계속 기다려야 하고, 이미 할당 받은 자원을 쓰지도 못해 심각한 자원 낭비 현상이 발생한다.

 

③ 자원의 비선점성 -> 자원을 선점 가능하도록 바꾼다.

한 프로세스에 할당 중이던 자원을 선점하여 다른 프로세스가 가지게 되면 프로세스가 비정상적으로 종료될 뿐만 아니라 처음부터 다시 시작해야 하는 불상사를 겪게 된다. 이 말은 지금까지 프로세스가 실행되며 했던 작업들은 모두 무효가 되어버려 심각한 자원 낭비로 이어진다. 또한, 계속해서 비정상적인 종료가 될 경우 "처음부터 다시 해야 하는 " 무한 대기도 겪게 될 가능성이 높아진다.

 

④ 자원에 대한 환형 대기 -> 자원을 할당하는 순서를 두어 제어한다.

예를들어 자원 R1, R2 가 있을 때 R2를 할당받기 위해서는 반드시 R1이 있어야한다는 순서를 만들어보자. 즉, R1을 할당박고 난 이후에 R2를 할당받을 자격이 생기게 되는 것이다. 이 방법 또한 교착 상태를 예방할 순 있지만 현재 필요도 없는 자원을 먼저 할당(자원 낭비)받아야하고, 이러한 하위 자원들을 할당받느라 시간이 오래 걸리게 된다.

 

 

 

●회피 기법

 

- 다익스트라의 은행가 알고리즘

 

이 알고리즘을 사용하기 위해선 시스템에 대한 몇 가지 가정이 요구된다.

 

---

① 자원의 수가 고정되어 있어야한다.

② 프로세스 수가 고정되어 있어야한다.

③ 각 프로세스가 자원을 요구하는 최대 개수를 알아야한다.

④ 각 프로세스는 할당받은 자원을 사용 후 반드시 반납한다.

---

은행가 알고리즘은 시스템의 상태가 '안정 상태'에 대해 판단을 내리는 알고리즘이다. 현 상태에서 모든 프로세스가 정상적으로 종료할 수 있는 길이 적어도 하나 이상 있다면 그 시스템은 안정 상태라고 할 수 있다.

 

안정 상태로 판단된 시스템

여유량이 2 이기 때문에 P2에게 2의 자원을 할당해 성공적인 종료를 유도(안정 상태)하면 총 6개 자원을 더 쓸 수 있게 된다. 이 6개의 자원으로 P1, P3 어느 프로세스에게 할당되어도 성공적인 종료를 유도할 수 있으므로 안정상태라고 판단한다.

 

불안전 상태로 판단된 시스템

여유량인 1을 어느 프로세스에게 할당을 해도 성공적인 종료를 유도할 수 없다.(불안정 상태다.)

 

 

●탐지 기법

 

RAG(Resource Allocation Graph)로 교착 상태를 탐지한다. RAG는 어떤 프로세스들이 어떤 자원을 가지고 있고, 어떤 프로세스가 어떤 자원에 의해 대기 상태가 되었는지를 나타내는 그래프이다.

 

 여기서 싱크(Sink)라는 개념이 중요합니다! RAG 에서 실행할 수 있는 프로세스를 말하는 것입니다.

 

① Edge를 제거하여 찾기

 

싱크를 찾고 난 뒤 이 싱크로 들어오는 방향의 모든 에지를 제거합니다. 왜 이런 일을 할까요? 싱크는 실행할 수 있는 프로세스이기 때문에 할당된 자원을 반납할 수 있습니다. 즉 "만약 이 싱크가 가지고 있는 자원들을 모두 반납한다면 RAG 의 결과는 어떻게 될까?"를 실제로 적용시키는 것입니다.

 

이러한 작업을 계속하여 최종적으로 남은 에지가 없다면 교착 상태가 없는 것이 되고,  지워지지 않는 에지들이 있다면 그 에지에 연결되어 있는 프로세스들은 교착 상태에 있다는 결론을 얻을 수 있습니다.

 

 

② 그래프 탐색으로 찾기

 

대기 상황을 나타내는 에지로부터 방향을 따라 경로(Path)를 탐색해보면

첫째, 싱크가 발견된다. 싱크가 발견되면 교착 상태는 없는 것으로 판단한다.

둘째,  사이클이 발견된다. 사이클이 발견 됐을 때 교착 상태라고 보는 것은 하나의 자원 형에 자원이 하나씩 들어있을 때만 가능하다. 그렇지 않으면 사이클의 발견은 단지 교착 상태의 가능성을 높이는 필요 조건일 뿐이다.

 

교착 상태 탐지

위 그림에서 P2가 R1에게 자원을 요구하게 되면 대기가 발생할 것이다. 이때 경로를 따라가다보면 1번의 경우 바로 싱크를 만나게 되고 교착 상태가 아님을 판단한다. 2번의 경로로 가게되면 자기 자신으로 돌아오는 사이클을 발견하게 된다. 1번에서 싱크를 발견했기 때문에 최종적으로 교착 상태가 일어나지 않았음을 알 수 있다.

 

 

 

●복구 기법

복구 기법은 총 2가지로 나뉜다.

 

① 프로세스의 종료

교착 상태를 형성한 프로세스들 중 몇 개를 골라 강제로 종료시켜 이들로부터 반납된 자원으로 복구를 하게 된다. 문제는 어떤 프로세스를 종료시킬 것인가인데 강제로 종료되었을 때 재시작의 비용이 많이 드는 즉, 종료 비용이 작은 것들을 종료시킨다. 재시작 비용의 기준은 프로세스 우선순위나 실행된 시간 크기, 남은 시간 등으로 잡을 수 있다.

 

② 자원의 선점에 의한 방식

 교착 상태와는 상관이 없는 프로세스에서 할당된 자원을 선점하는 방식으로 해결할 수 있다. 물론 이 방식에서도 선점 시의 최소 비용은 따져야한다.

 

 

프로세스 종료 같은 경우에는 복구 비용이 크게 늘어나고, 특정 프로세스에서 반복적인 종료 현상을 겪을 수 있다. 따라서 검사점 지정(checking Pointing)을 두어 복구 비용을 줄이게 됩니다.

 

프로세스 실행 중간 중간 마다 그 시점까지의 결과를 보전하고 표시를 해두는데 이를 Checkpoint라고 합니다. 그래서 만약 이 프로세스가 교착 상태를 유발해 종료하기로 결정되면 이 Checkpoint를 돌려가며 복구 지점을 찾습니다.