[운영체제] Deadlock 1 : 데드락 발생 4 조건, 자원할당그래프, 데드락 처리 방법, Deadlock Avoidance : Resource Allocation Graph algorithm,

데드락

• 일련의 프로세스들이 서로가 가진 자원을 기다리면 block된 상태

자원

• 하드웨어, 소프트웨어 자원을 포함하는 개념
• 예 ) I/O device, CPU cycle, memory space, semaphore
• 프로세스가 자원 사용하는 절차
  - Request => Allocate => Use => Release

데드락이 뭐다?
서로 다른 프로세스가 서로가 가진 자원을 기다리며 무한 대기하는 block 상태다!

데드락 발생의 4가지 조건

다음 4가지 조건을 모두 만족해야 데드락이 발생한다.

1. Mutual Exclusion (상호 배제)

• 매 순간 하나의 프로세스만 자원을 사용할 수 있음

2. No Preemption (비선점)

• 프로세스는 자원을자발적으로만 내놓지 강제로 내놓게 못함

3. Hold and Wait(보유 대기)

• 프로세스가 다른 자원 기다릴 때, 보유 자원을 놓지 않고 기다림

4. Circular wait(순환대기)

• 자원 기다리는 프로세스간 사이클이 형성되있어야
  (뒤에 그림나옴)

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

화살표 방향이 프로세스 => 자원이면 요청, 자원 => 프로세스면 할당이다.
자원할당 그래프를 만들어서 보면 circular wait이 맞는지 확인할 수 있다.

화살표를 따라가서 제자리로 안 온다? 데드락 아니다.
제자리로 돌아온다? 만약 인스턴스가 1개면 데드락, 여러 개면 또 따져봐야 한다.

결국 위 방법은 도움 안되고 직접 추론까지 해봐야 한다.
위 그림을 보자.
1번 그림. R2에 인스턴스가 2개다. 따라서 2개의 사이클이 생긴다. 이건 데드락이다.

2번 그림. R2 => P1 => R1 => P3 => R2 사이클이 생기긴 한다.
근데 R2와 R1에 한 인스턴스가 각각 P2, P4에게 할당되어 있다.
P2, P4는 더 이상 다른 자원이 필요 없다. 언젠간 놔 줄 것이다.
그럼 데드락이 아닌 것이다.

데드락 처리 방법

데드락을 어떻게 처리할 것인가? 애초에 발생을 못하게 예방할 것인가, 발생은 할 수 있되 대처를 할 것인가. 이렇게 여러 방법이 있을 수 있겠지?

1. Deadlock Prevention

• 자원 할당시 deadlock 4가지 조건 중 하나를 만족 못하게 하는 것

'원천 봉쇄'

2. Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보 이용해서 가능성이 없는 경우에만 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

'미래를 보고 가능성 있으면 봉쇄'

3. Deadlock Detection and recovery

• 발생 허용하되, 그에 대한 detection 루틴을 두어 발견시 recover

'대처 수단을 마련'

4. Deadlock Ignorance

• 시스템이 책임 안짐
• 대부분의 OS가 채택 중

'냅둬 ~ 알빠노? 인간 니가 중지하셈'

컴퓨터 하다가 프로그램 멈춰서 직접 프로세스 중지해본 경험있는가?
대츠롸잇.
데드락이 자주 발생하는 이벤트가 아니기에, 이걸 방지하려고 많은 오버헤드를 두는 것을 비효율적으로 판단해, 이 방법을 쓴다.

이제 각각 방법을 자세히 살펴보자.

---

Deadlock Prevention

4가지 발생 조건 중 하나를 만족 못하게 한다.
그렇다면 4가지 방법이 있겠지?

1. Mutual Exclusion

• 이건 막기 빡세다. 하나의 자원을 동시에 접근하도록 허용하는게 가능하냐?
  물론 여러 인스턴스가 있다면 허용해야 겠지만 말이다.

2. Hold and Wait

• 자원을 요청할 때, 다른 어떤 자원도 가지고 있지 않아야 한다.
• 방법 1 : 프로세스 시작시 모든 필요한 자원을 할당받게
• 방법 2 : 자원 필요시 보유 자원을 모두 놓고 다시 요청

방법1은 딱봐도 비효율적이다.
방법2를 보면, 내가 A를 가지고 있고 B를 요청할 시에, 자진해서 A를 놓고 A,B를 요청하는 방식이다. 만약 누군가 A를 쓰고 싶다면 채갈 것이고, 아무도 관심없으면 난 A,B를 동시에 사용 가능하다.

3. No Preemption

• CPU, memory에서 사용 가능(강제로 뺏어도 save, restore가 가능하니까)
• 모든 필요한 자원을 얻을 수 있을 때 프로세스가 다시 시작

강제로 뺏질 못하니까 데드락이 걸린 거 아니겠는가?
그럼 강제로 뺏을 수 있는 CPU, Memory 자원은 이 방법을 쓸 수 있는 것이다.

4. Circular wait

• 자원 유형에 할당 순서를 정해 정해진 순서대로만 자원 할당
• 예를 들어 P0이 1,3,5번 자원을 원할 경우, 1번을 먼저 획득하고 3번, 그 다음 5번을 획득하는 순서를 강제하는 것이다.

데드락은 자주 발생하지 않는다고 했다.
이 대처 방법들은 결국 오버헤드를 키우는 비효율적인 방법이라고 한다.
(그냥 냅두면 인간들이 알아서 해주는데)

2. Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보 이용해서 가능성이 없는 경우에만 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

쉽게 말하면 자원 할당 이전에, 할당했을 경우 데드락 발생 가능성이 있으면 주지 않는 것이다.

시스템이 safe state에 있으면 : no deadlock
시스템이 unsafe state : possibility of deadlock

결국 Deadlock Avoidance는 unsafe state에 들어가지 못하게 하는 것이다.

두 가지 방법이 있다.

• 자원이 싱글 인스턴스인 경우 => Resource Allocation Graph algorithm
• 자원이 여러 인스턴스 => Banker's Algorithm

Resource Allocation Graph algorithm

화살표에 종류가 추가되었다. 점선은 미래에 요청할 수 있는 자원을 표시한 것이다.

맨 마지막 그림을 보자. 저 상황에서, 점선에 해당하는 요청이 들어왔을 때,
점선을 포함했을 때 사이클이 그려진다. 이러면 할당을 거부하는 것이다.

Banker's Algorithm

각 프로세스마다

• 현재 할당받고 있는 자원을 표시하는 Allocation
• 언젠가 각 자원이 필요한 최대 양인 Max
• 현재 남아있는 자원 Avaliable (얘는 공통임)
• 미래에 최대로 요청할 수 있는 자원 Need

가 있다.
말로만 들으면 어려우니 예시를 보자.

먄약 p1이 (1,0,2)를 요청했다. p1이 쓸 MAX를 요청한 것이다.
남아있는 Avaliable이 (3,3,2)다. 다 줘도 된다. P1은 더 이상 요청하지 않을 것이니까.

이제 P0이 (0,2,0)을 요청했다.
남은 자원은 (2,3,0)이니까 줄 수는 있다.
근데 P0은 MAX가 (3,2,2)다. 줬는데 언젠가 미래에 (1,1,2)를 요청할 수 있는 것이다.
근데 (1,1,2)를 이미 다른 프로세스가 쓰고 있다면?
preemptive라고했다. 강제로 못 뺐는다. 데드락 걸려버리는 거다 그냥.