교착상태(Deadlock)

Concurrency Control, 병행제어

임계영역이란?

임계영역이란 프로세스가 공유자원에 동시에 접근하지 못하도록 한번에 하나의 프로세스만 이용하게끔 해주는 영역이다.

 

임계영역 보장 조건

임계영역을 보장해주기 위해서는 3가지 조건을 충족해야 한다.

 

1) Mutual exclution

하나의 프로세스가 임계영역에 진입시 다른 프로세스는 진입 불가

 

2) Progress

임계영역에 아무 프로세스가 없는 상태에서 들어가려는 프로세스가 여러개라면 어떤 프로세스가 먼저 들어갈지 결정해줘야 함.

 

3) Bounded waiting

다른 프로세스의 starvation 을 방지하기 위해 한번 임계영역에 들어간 프로세스는 다음번에 들어갈 때 제한을 둬야 함.

 

Concurrency Control, 병행 제어 or 프로세스 동기화 기법

이 조건을 충족해주기 위한 방법, 즉 프로세스의 동기화 기법은 아래와 같다.

 

1) Semaphores

세마포어 변수(S)를 하나 두고, 임계영역에 들어가기 전에 S를 0으로 둬서 다른 프로세스의 진입을 막는다. 임계영역에서 나올 때는 S를 1로 두고 다른 프로세스가 진입할 수 있게 함.

 

2) monitor

Semaphores 는 구현이 까다로워서 high-level 수준으로 구현한 방법. library, framework 수준에서 제공된다. 우리가 흔히 쓰는 syncrhonized 커맨드를 생각하면 된다.

 

---

교착상태 해결방법

교착상태란?

프로세스들이 상대방의 자원(하드웨어 or 소프트웨어)을 요청했지만 받지 못하고 전부 block 된 상태

* 프로세스는 자원을 요청 > 할당 > 반납 하는 단계를 거침.

 

교착상태 발생 4가지 조건(이론적...)

1. Mutual exclusion, 상호배제

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

 

2. No preemption (비선점)

자원을 빼앗기지 않음.

 

3. Hold and wait (보유대기)

프로세스가 보유 자원을 놓지 않으면서 다른 자원을 요청함.

 

4. Circular wait (순환대기)

자원을 기다리는 프로세스 사이에 사이클이 형성됨.

 

자원 할당 그래프

교착상태는 자원 할당 그래프(Resource-Allocation Graph)를 통해 알 수 있다. 자원 할당 그래프가 사이클이 있고 resource instance 가 하나면 deadlock 일 가능성이 있다. 아래 그림에서 왼쪽은 데드락이다. 오른쪽은 P2번 혹은 P4번이 자원을 반납하면 교착상태가 해결되므로 데드락이 아니다.

교착상태 처리방법

1. Deadlock Prevention (예방, 방지)

4가지 조건을 만족되지 않도록 미연에 방지

- Mutual Exclusion : 이 조건은 반드시 성립해야 함.

- Hold and Wait : 프로세스가 시작 시 모든 자원을 할당받게 하거나 자원이 필요한 경우 보유 자원을 모두 놓고 요청.

- No Preemption : 자원의 사용 상태를 save 하고 restore 할 수 있는 자원에 한해 뺏을 수 있게 함. 

- Circular Wait : 자원 할당 순서를 정해서 1번 자원을 획득해야만 3번 자원을 획득할 수 있도록 해서 사이클이 생기지 않게 함.

데드락을 미리 생각해서 제약조건을 달아놓기 때문에 utilization(자원이용률) 저하, throughput(시스템 성능) 감소, starvation 문제가 발생할 수 있다.

 

2. Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해 데드락의 가능성이 없는 경우에만 자원 할당.

프로세스가 시작될 때 프로세스가 쓸 자원의 최대량(부가정보)을 미리 파악해서 데드락을 피해감.

 

1) 자원 instance 가 1개 일 때, 자원할당 그래프를 이용해서 미리 파악. 점선 화살표를 추가해서 미래에 쓸 정보를 표시함.

즉, 최악의 상황을 가정해서 데드락의 가능성이 있으면 자원 할당 X.

 

2) 자원 instance 가 2개 이상일 때, Banker's Algorithm 을 이용함. 

위 그림은 5개 프로세스가 각각 10개, 5개, 7개의 instance 를 가진 자원 A, B, C 를 가지고 작업하는 상황이다. Allocation 은 할당 받은 자원, Max 는 평생 사용할 자원의 최대량, Avaliable 은 현재 가용가능한 자원, Need 는 추가로 요청할 수 있는 자원의 정보다.

 

만약 P1 이 A1, C2 개를 요청했다면 Need 를 Avaliable 로 해결할 수 있는지 보고 된다면 할당함. 만약 P0이 B2 를 요청했는데 Need 를 보니 Avaliable 만으로는 해결할 수 없으므로 할당 x.

 

이처럼 Banker's Algorithm 은 해당 시점에서는 이후 반환하는 것은 계산하지 않고, 요청하는 순간 최대 Need 를 Avaliable 자원으로 해결할 수 있는가만 봄. 단 Allocation 에서 Max 를 충족했다면 이후 반환한 것을 Avalicable 에 반영하고 계산함.

 

혹시 모르는 상황에 대비에 남아도는 자원을 이용하지 않으므로 비효율적인 방법.

 

3. Deadlock Detection and recovery

데드락 발생 허용하되 데드락 detection 루틴을 만들고 발견시 recover

데드락은 자주 발생하지 않는데 그것을 방지하려고 자원 가용률을 낮추는 건 비효율적이므로 발생했을 때 해결.

자원 할당 그래프를 이용하거나 테이블을 이용함.

 

- 자원 할당 그래프

여기서는 자원 최대 사용량을 미리 알 필요가 없으므로 점선이 없음.

그래프에서 사이클이 생겼는지 주기적으로 detection 함. 

 

- 테이블 이용

- recover

1) 데드락에 연루된 프로세스를 한꺼번에 죽이거나 하나씩 죽임.

2) 데드락에 연루된 프로세스 중 하나의 자원을 뺏음. 자원을 뺏는 패턴은 매번 달라져야할 필요가 있음.

 

4. Deadlock Ignorance

현대 OS 가 채택. 시스템이 책임지지 않음.