Deadlock

Starvation vs Deadlock

- Starvation vs Deadlock -

- 발생위치가 다름 

- 발생 가능성의 확률이 다름

 

 * Starvation: Process가 자원을 얻을 수 있는 즉, 발생할 수 있는 가능성이 존재 

 * Deadlock: Process가 자원을 얻을 수 있는 확률 0% 

---

Deadlock(교착상태)

- Process가 발생가능성이 없는 이벤트를 기다리는 경우, 또는 자원을 얻지 못해 다음 처리를 하지 못하는 상태를 말한다. 

- 현재 서로 원하는 자원이 상대방 프로세스에 할당되어 있어서 두 프로세스가 무한정 Wait 상태에 빠진 상태를 말한다. 

 

< 예시 >

  1. Process-1이 자원 1을 얻음 / Process-2가 자원 2를 얻음 

  2. Process-1은 자원 2를 기다림 / Process-2는 자원 1을 기다림 

  3. 두 Process는 무한정 Wait상태에 빠짐 -> 교착상태

 

자원이라는 말이 계속적으로 등장하는 만큼, Deadlock은 자원과 굉장히 밀접하다. 

 

자원의 분류

1. 선점 가능 여부에 따른 분류 

 가. Preemptive resource (선점)

  - 선점을 당해도 문제가 발생하지 않는 자원, 대신 기다려야 함 

  - Processor, Memory 등 

 나. Non-Preemptive resource (비선점)

  - 선점 당하면 이후 진행에 문제가 발생하는 자원

  - Disk drive 등 

 

2. 할당 당위에 따른 분류 

 가. Total allocation resource 

  - 자원 전체를 Process에 할당

  - Processor, Disk drive 등 

 나. Partitioned allocation resource 

  - 하나의 자원을 여러 조각으로 나누어 여러 Process들에게 할당 

  - Memory 등 

 

3. 동시 사용가능 여부에 따른 분류 

 가. Exclusive allocation resource (상호배제) 

  - 한 순간에 한 프로세스만 사용가능한 자원 

  - Processor, Memory, Disk drive 등 

 나. Shared allocation resource 

  - 여러 프로세스가 동시에 사용가능한 자원 

  - Program 등

 

4. 재사용 가능 여부에 따른 분류 

 가. SR(Serially reusable resource) 

  - 시스템 내에 항상 존재하는 자원 

  - 사용이 끝나면 다른 프로세스가 사용가능 

  - Processor, Memory, Disk drive, Program 등 

 나. CR(Consumable resource)

  - 한 프로세스가 사용한 후에 사라지는 자원 

  - Signal, Message 등 

 

Deadlock을 발생시킬 수 있는 자원의 형태 

1. Non-Preemptive resource (비선점)

2. Exclusive allocation resource (상호배제) 

3. SR(Serially reusable resource) 

4. Partitioned allocation resource

 

Deadlock 발생 예시 

- Deadlock 발생 예시 -

 

Deadlock 발생 필요 조건 

1. 자원의 특성 

 - Exclusive allocation resource (상호배제) 

 - Non-Preemptive resource (비선점)

2. 프로세스의 특성 

 - Hold and wait (점유대기)

 * 점유대기: 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스 

 - Circular wait (순환 대기)

 

Deadlock 해결 방법 

1. Deadlock prevention method (예방)

2. Deadlock avoidance method (회피)

3. Deadlock detection and recovery method (탐지 및 회복) 

Deadlock prevention method (예방)

Deadlock 발생 필요조건 4개중 1개를 없애는 방법

가. 실행 방법

 - Exclusive allocation resource (상호배제) => 현실적으로 불가능

 - Non-Preemptive resource (비선점) => 현실적으로 불가능

 - Hold and wait (점유대기) => 필요하지 않는 순간에도 자원을 갖고 있다보니 자원 낭비 발생, 그럼으로 인해 무한대기 현상 발생 

 - Circular wait (순환 대기) => 자원들에게 순서를 부여함으로써 프로세스는 순서의 증가 방향으로만 자원을 요청을 할 수 있음 -> 자원낭비 발생 

 

나. 결과 

 - 자원낭비가 심각하고 비현실적이라는 의견이 대다수임 

 

Deadlock avoidance method (회피)

시스템의 상태를 계속 감시하면서 Deadlock 상태가 될 가능성이 있는 프로세스의 할당되는 자원을 보류시키는 방법, 시스템을 항상 Safe state로 유지시켜야 함 

 

* Safe state? 

- 모든 프로세스가 정상적으로 종료가능한 상태를 말하며, Safe sequnce가 존재한다. 

 

하지만 이러한 Safe state가 되기위해서는 몇가지 필수조건이 존재하는데 다음과 같다. 

 1) 프로세스의 수가 고정되야한다. 

 2) 자원의 종류와 수가 고정되야한다. 

 3) 프로세스가 요구하는 자원과 최대 수량을 알고 있어야 한다. 

 4) 프로세스는 자원을 사용 후 반드시 반납해야 한다. 

 

그러나 이러한 4가지 필수조건은 Practical 하지 않았다. 왜냐하면 시스템에서는 생각지도 못한 변수들이 매번 발생하기 때문이다. 이러한 문제점을 풀기위한 방법이 등장하였으니, 모두가 잘 알고 있는 Banker's 알고리즘이다. 

 

가. 실행방법 (Dijkstra's banker's 알고리즘)

 * 일상생활에서 일어날 수 있는 상황들 적용하여 기록하겠습니다. 

- banker's 알고리즘 -

 1) 여기서 3명의 친구들은 믿을만한 친구들이다. 

 2) 현재 3명의 친구들은 나에게 돈을 빌리려고 한다. 

 3) Step 1에서 친구들에게 돈을 빌려주면 Step2가 시작되기 전 각 친구들은 빌려준 순서대로 돈을 갚는다.

 

Q. 누구부터 돈을 빌려주는게 맞을까?

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

<정답>

- Available resource unit: 2만원 -> Step 1이 끝났을 때 

- 실행 종료 순서: 친구1 => 친구3 => 친구2 ( Safe sequnce 존재)

- Safe state 유뮤: 안전 상태 

 

즉, Safe sequnce가 하나이상 존재하면 Safe state(안전 상태)이다. 

 

결론적으로 Deadlock avoidance method에서는 Banker's 알고리즘을 통해 시스템의 상태를 계속 감지하면서, Safe state가 적용되지 않는 프로세스들은 할당되는 자원을 보류 시킨다.  

 

나. 결과 

 - High overhead 발생 -> 항상 시스템을 감시해야하기 때문에

 - Low resource utilization 존재 -> Safe state를 유지하기 위해 사용되지 않는 자원이 존재하기 때문에 

 

Deadlock detection and recovery method (탐지 및 회복) 

1. Deadlock detection

Deadlock 방지를 위한 사전작업이 없이 확인하는 절차 => RAG (Resource Allocation Graph) 사용

 

* RAG 그림 및 설명 필요 

 

Deadlock avoidance vs Deadlock detection 

<Deadlock avoidance>

- 최악의 경우를 생각하고 앞으로 일어날 일을 고려한다. 

- Deadlock 자체가 발생하지 않는다. 

 

<Deadlock detection>

- 최선의 경우를 생각하고 현재 상태만 고려한다. 

- Deadlock이 발생하는 것을 탐지하고 이후 Recovery 과정을 고려한다.

 

2. Deadlock recovery 

Deadlock detection 이후에 필수적으로 거쳐야하는 과정, Deadlock 상태를 해결한다. 

 

 가. 해결 방법

  1) Process termination (프로세스 종료)

   - Deadlock 상태인 프로세스 중 일부를 종료시킨다. 

   - Termination Cost를 고려해 종료시킬 Deadlock 상태의 프로세스를 선택한다. 

    * What is included in Termination Cost? 우선순위, 종류, 총 수행시간, 남은 수행시간, 종료 비용 등  

   

<예시>

 가. Lowest-termination cost process first

   - 단순한 로직이고, Overhead가 낮지만, 불필요한 프로세스들이 종료될 가능성이 높음 

 나. Minimum cost process first 

   - 최소비용으로 deadlock 상태를 해결할 수 있는 프로세스를 선택해야하는 만큼 모든 경우의 수를 고려해야 하기 때문에 로직이 복잡하고 Overhead가 높지만, 불필요한 프로세스들이 종료될 가능성이 낮음

 

   2) Resource preemption (자원 선점)

   - Deadlock 상태 해결을 위해 선점할 자원을 선택한다. 

   - Deadlock 상태의 프로세스가 점유하고 있는 자원을 선점해서 다른 프로세스에게 할당을 한다. 

   - 해당 프로세스는 처음부터 다시 시작되며, Deadlock 상태가 아닌 프로세스가 종료될 수도 있는 위험성이 있다. 

 

   3) Checkpoint - restart method

- 기존 프로세스 Terminated -

   

- Checkpoint - restart method -

- 프로세스의 수행 중 특정지점마다 Context를 저장한다. 

- 만약 Deadlock 상태인 프로세스가 강제 종료되었을때 가장 최근의 Checkpoint에서 재 시작을 할 수 있다. (Rollback) 

---

  < 참고자료 >

 

https://www.youtube.com/watch?v=EdTtGv9w2sA&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4

[도서] 컴퓨터구조  - 김형근, 손진곤 지음 -

 

<Computer structures> chapter 17, Deadlock(교착상태) end>

---