[운영체제] ep5) Concurrency: Deadlock and Starvation

ㅁDeadlock의 발생 조건 4가지

① Mutual Exclusion(상호배제)

② Hold-and-Wait

③ No preemption(비선점)

④ Circular Wait: 여러 프로세스가 자원을 할당받은 후, 다른 프로세스가 점유하고 있는 자원을 추가로 요청하면서 서로 대기하는 상황이 순환 형태로 이루어지는 것

 

 

ㅇ자원 할당 그래프(Resource Allocation Graphs)

P1이 Ra 타입의 리소스를 달라고 OS에게 요청

 

 

Ra 리소스가 P1에게 할당(allocation)된 상태

 

 

대부분의 데드락은 두 프로세스 사이에서 발생한다

 

 

 

ㅁ데드락 해결방법 3가지

1. Deadlock Prevention: 자원할당 규칙을 만든다(사전에 차단)

④ Circular Wait를 깨기 위해 자원에 번호를 매긴다 - 자원을 요청할 때 번호 순서대로 요청

데드락이 발생하지 않는 것을 증명하는 그림

 

- 낭비 多, 실제로 사용은 x

데드락이 발생하면 큰일이 나는 시스템이 아닌 이상 데드락 prevention보다는

데드락 avoidance를 사용한다

 

 

2. Deadlock Avoidance: 규칙 x, 그때그때 데드락 가능성을 검사(유동적)

2가지 방법

① Process Initiation Denial: 아예 프로세스 시작을 거절(프로세스를 suspend)

[현재 프로세스 자원 + new 프로세스가 먹을 자원 <= 총 자원] 조건식 체크

 

② Resource Allocation Denial a.k.a. 뱅커 알고리즘(은행원 알고리즘): 일단 실행은 하는데 자원할당 고려

safe 상태: 프로세스들이 순차적으로 종료할 수 있는 sequence가 존재

unsafe 상태: 어떤 순서로 실행시켜도 데드락이 걸리는 상태

 

<safe 상태인지 확인하는 절차>

safe 상태

 

P2 종료 -> 자원 반납

 

P1 종료 -> 자원 반납

 

P3 종료 -> 자원 반납

 

 

<unsafe 상태인지 확인하는 절차>

 

 

 

(코드)

 

 

문제점)

1. 사전에 자원의 최대치를 알아낼 수가 없다 (과연 이게 최대치일까)

2. 자원 개수가 고정되어야만 정확한 계산이 가능 (e.g. 세마포는 유동적이라 활용 불가)

따라서 극소수의 프로세스만 Deadlock Avoidance를 쓰고 웬만하면 Deadlock Detection을 쓴다

 

 

3. Deadlock Detection: 방치하다 데드락이 발생하면 해결

- 언제든지 Resource Request 보장

- 주기적으로 데드락 검사

 

똑같이 allocation matrix A, available vector V, resource vector R 사용

여기에 claim matrix C 대신 request matrix Q를 사용 

 

 

ㅁ데드락이 detection 됐을 때 시스템을 recovery 하는 4가지 전략

1. 전부 한꺼번에 폐기

2. 프로세스를 백업 -> 데드락 직전 프로세스부터 재시작

3. 하나씩 순차적으로 폐기

4(2 + 3). 하나씩 순차적으로 폐기 + (프로세스를 백업 -> 데드락 직전 프로세스부터 재시작)

 

 

ㅇDining Philosophers Problem(식사하는 철학자 문제)

데드락에서 가장 유명한 문제 중 하나

 

- 철학자는 포크 2개로 식사해야 한다

- 철학자 둘이서 한 포크를 못쓴다 (Mutual Exclusion)

- 데드락이 발생하면 철학자들은 굶어 죽는다 (Starvation)

 

 

 

세마포 사용 - 일반적인 안좋은 코드

데드락 발생 O

 

 

세마포 사용 - 공간을 분리한다!

데드락 발생 X

 

모니터 사용

- true: 포크 사용가능

- false: 포크 이용중

데드락 발생 X

 

 

 

 

 

ㅁUNIX의 병행성 기법

- Pipe

- Message Passing

- Shared Memory

- Semaphore

- Signal

 

 

ㅁSolaris의 Thread 동기화 기법

- Mutex locks: 한 번에 하나의 Process만 공유자원에 접근할 수 있도록 Process가 자원을 사용할 때 잠금을 걸고, 사용이 끝나면 잠금을 해제하는 기법

- Semaphore

- Multiple readers, single writers locks

- Condition variable

 

 

ㅁWindows의 병행성 기법

- Mutex: Binary Semaphore

- Semaphore: Counting semaphore

- Waitable timer

- Event

- Reader-Writer locks

 

 

 

 

 

 

참고 및 출처: Operating Systems: Internals and Design Principles(William Stalling), Operating System Concepts(Silberschatz, Abraham)