[OS] 5. Concurrency : Deadlock and Starvation

본 게시글은 PC버전에 최적화 되어 있습니다.

 

Operating Systems, Internals and Design Principles (9th Ed.), William Stallings, Pearson, 2017

1. Principles Of Deadlocks

컴퓨터의 자원이 한정되어 있고 이것을 여러 프로세스가 원하므로 이 과정에서 발생할 수 있다.

 

Resource Allocation Graph

P1이 Ra를 요청하고 커널에 의해 Ra가 P1에 할당된다. (화살표 방향 주의)

 

Circular Wait

(c)의 경우 P1은 Ra를 요청했지만 P2에 할당되었고, P2는 Rb를 요청했지만 P1에 할당되었다.

따라서 데드락이 발생한다.

 

(d)의 경우 (c)와 같은 형태이지만 자원의 개수가 많기 때문에 데드락이 발생하지 않는다.

2. Condition for Deadlock

1. Mutual Exclusion : 상호배제

하나의 프로세스만 한 가지 자원에 접근이 가능하다.

-> 하나의 자원에 둘 이상의 프로세스가 접근이 가능하면 데드락 걱정 없지.

 

2. Hold and Wait : 붙잡고 기다림(?)

자원을 요청할 떄 가지고 있던 자원을 내려놓는다.

-> 미리 내려놓는 것이 아니라 새로운 자원을 요청하면 그제서야 들고 있던 걸 내려놓는다. (욕심쟁이)

 

3. No Preemption : 강탈 금지

상대방에게 할당된 자원은 Dont touch

-> 상식적으로 불가능. 약육강식이 되버린다.

 

4. Circular Wait : 귀속

꼬리물기

 

그렇다면 어떻게 해야지 데드락을 예방할 수 있을까?

3. Method for handling Deadlocks

1. 사전 예방 : 운영체제가 미리 탐지하여 예방

데드락의 4가지 조건을 깨버리면 되는거 아닌가? -> 비싸고 불가능에 가까움.

Bankers Algorithm : 데드락이 발생하지 않는 안전한 상태를 미리 판별하는 알고리즘.

요청한 자원, 할당된 자원, 필요한 자원, 주어진 자원, 이용 가능한 자원을 모두 이용하여 탐색(?)을 해야하므로

오버헤드가 상당히 크다. 하나라도 안전한 상태가 존재하면 자원을 할당.

 

2. 직접 해제 : 데드락이 발생하면 직접 해제

 

3. 아무것도 안함 -> 이 방법 채택

4. Dining Philosophers Problem

데드락에 관한 매우 유명한 문제

 

Dining Philosophers Problem

 

각자 자기 앞에 포크와 음식이 있다.

음식을 먹기 위해선 옆사람의 포크도 필요하다. (? ㅋㅋㅋㅋ)

 

아무튼 코드를 살펴보면

 

Incorrect DPP

생각을 하고, 포크를 집어든다.

철학자들이 배가 고팠는지 다들 자기 포크를 집었다.

옆사람 포크도 필요한데 서로 내려놓지 않다가 그냥 다 굶어 죽는다.

 

Correct DPP

이를 해결하기 위해 세마포어를 하나 추가한다.

4개의 사이즈를 가진 room 변수를 추가하면 끝.

한 명은 항상 기다리게 되니 데드락을 해결할 수 있다.