7. Deadlocks (2) - 1 (~Deadlock Prevention)

• 진행을 못하고 있는(blocked) 프로세스들 각각이, 다른 프로세스가 진행할 때 꼭 필요한 자원들을 움켜쥐고 있으면서 안 놓고, 다른 프로세스가 움켜쥐고 있는 자원을 기다리는 상황이다. 결국 모두가 다같이 옴짝달싹 못하게 된다
• 예시
  • 시스템이 2개의 테이프 드라이브를 가지고 있다.(자원)
  • P1과 P2 각각이 하나의 테이프 드라이브를 움켜쥐고 있고, 각각 서로의 테이프 드라이브가 필요한 경우.
• 예시
  • 1로 초기화 된 세마포어(동기화 메커니즘) A, B -> P(A)가 호출되면 0이 됨. 다른 프로세스에서 P(A)를 마딱뜨렸는데 0이면 1이 될 때까지 대기해야함.

다음 4가지 조건이 동시에 만족해야 Deadlock이 발생할 가능성이 있음(필요조건).

• Mutual exclusion: 한번에 하나의 프로세스만 해당 자원을 사용할 수 있음.(공유가 불가능)
• No preemption: 외부의 힘으로 자원을 뺏을 수 없고, 오로지 스스로 업무를 끝마쳤을 때 자원을 놓는다.
• Hold and wait(움켜쥐고 기다리다): 하나 이상의 자원을 쥔 채로 다른 프로세스가 잡고있는 자원을 기다린다.
• Circular wait(선형 대기): P0가 P1이 잡고있는 자원을 기다리고, P1도 P2를 기다리고, ... , 마지막 프로세스 Pn이 P0의 자원을 기다리는 형태로 꼬리를 무는 원형의 상태일 경우.

Resource-Allocation Graph(자원-할당 그래프)

 

노드(Vertice)의 집합 V와 간선(Edge)의 집합 E

• V(노드)는 두 가지 타입으로 나뉨
  • P = {P1, P2, ..., Pn}, 시스템을 구성하는 모든 프로세스의 집합.
  • R = {R1, R2, ..., Rn}, 시스템을 구성하는 모든 자원들의 집합.
• request edge(요청 엣지) - 프로세스에서 자원으로 향하는 엣지(directed edge)
• assignment edge(할당 엣지) - 자원에서 프로세스로 향하게 엣지(directed edge)

instance 개수만큼 프로세스가 해당 자원에 붙을 수 있음.

 

R2자원이 P1과 P2에게 할당되어있고, P1이 R1에게 자원을 달라고 요청하고 있음.

R2 자원의 instance 개수는 2임.

 

• 만약에 그래프에 사이클이 없으면 -> Deadlock 발생 절대 안함 (바로 위 그래프에서는 사이클이 없었음. 방향 고려 필수)
• 만약 그래프에 사이클이 있으면 ->
  • 자원마다 instance(조그만 검은 네모 혹은 동그라미)가 하나면, 무조건 deadlock.
  • 자원의 instance가 여러개면, deadlock의 가능성이 있음.

위의 경우는 R2의 instance가 2개이기 때문에 무조건 deadlock이 발생하는 첫 번째 경우는 아님.

잘 보면 제일 바깥쪽으로 사이클이 있고, 오른쪽에 작은 사이클이 있음. 

이 경우는 deadlock임. 아마도 두개의 사이클이 R1, R2, R3의 모든 instance를 다 차지하고 있어서 옴짝달싹 못하게 되는 것 같음.

 

사이클이 있다고 무조건 deadlock은 아니다. 위 그래프를 통해 확인할 수 있다.

가운데에 사이클이 있긴 하다.

그러나 P4가 할 일을 다 마치고, R2 할당이 풀리면 P3가 아래의 인스턴스를 할당받을 수 있다. 꽉 막히게 되지 않는다.

 

Deadlock에 대처하는 방법들

 

• 시스템이 deadlock 상황에 절대 들어가지 않도록 보장한다. (prevent, avoid. 두 개는 서로 다름)
• 시스템이 deadlock 상황에 들어가는 것을 허락함. 만약 발생한다면 복구해주기.(after detection)
• 그냥 문제를 무시해버리고 시스템에 deadlock이 절대 발생하지 않는 것 처럼 행동함. UNIX와 같은 대부분의 운영체제에서 사용하는 방법임. -> 워낙 deadlock이 일어날 확률이 낮기 때문.

Deadlock Prevention (Deadlock 예방)

다음 4가지 상황(Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait)중 하나를, 아예 발생하지 못하도록 만들어버리는 방법임. -> 4가지 상황이 동시에 발생하면 deadlock의 가능성이 생기기 때문. 최대 3가지만 발생하면 deadlock 안생김

• Mutual Exclusion (한 시점에 하나의 프로세스만 자원에 접근)
  • 이걸 없애려면 자원을 무조건 공유 가능하도록 허용해야 하는데, 이건 자원 자체의 특성인거라 어떻게 할 수가 없음.
  • 이걸 없애는건 불가능
• Hold and Wait (움켜쥐고 기다리기)
  • 자원을 움켜쥔 상태에서는 다른 자원에 요청을 절대 할 수 없도록 만들기.
  • 프로세스가 실행하기 전에 아예 자원을 전부 할당받아 버리거나, 아니면 아무것도 들고있지 않은 상황에서만 자원요청을 할 수 있도록 만들기.(한꺼번에 전부 갖거나, 그렇지 않다면 모두 버리거나)
  • 자원 활용률이 매우 떨어짐, starvation의 가능성이 있음. -> "어 아까는 1번 있고 3번 없었는데, 지금은 3번 있고 1번 없네?" 
• No Preemption (외부에서 강제로 끊기 불가능. 스스로 task를 완료하는 것만이 빠져나갈 수 있는 유일한 길)
  • 프로세스가 어떤 자원을 잡고 기다리는 것 까지는 허용해줘.(Hold and Wait)
  • 그러나 쥐고 있는 상황에서 다른 자원에게 요청을 보냈는데, 즉시 할당받을 수 없는 상황이라면 -> 잡고있는 모든 자원을 강제로 뺏어가기
  • Hold and Wait과 결과는 같지만, 과정이 다름. -> 발생되는 문제도 비슷함.
• Circular Wait (선형대기. 꼬리물기)
  • 모든 자원에게 순서를 부여함. (R1, R2, ..., Rn)
  • 프로세스가 자원을 요청할 때에는 요청하는 자원의 순서가 오름차순이 되도록 강제함. (기다리기는 허용해줌)
  • 이러면 꼬리물기가 안생김 (그래프를 그려보는 것을 추천)
  • 이것도 마찬가지로 자원 활용률이 떨어지는 문제가 발생함.

 

위 방법들 중 Mutual Exclusion은 말이 안되고, 나머지 3개의 방법 모두 자원의 활용률을 떨어뜨려서 시스템 전체의 throughput을 떨어뜨리는 문제가 존재함.

 

Deadlock Avoidance 부분 부터는 다음 글에서 이어서 작성할 예정. (그러나 미정. 시험 공부용인데 생각보다 작성 시간이 너무 오래걸림)