13. 교착상태 ( Deadlock)

프로세스는 실행을 위해 여러 자원을 필요로 한다.

 

 

하드웨어들을 자원들이라고 하고 이 자원들을 사용하는 프로그램들이 Applications 들이다. 

 

중간에 O/S는 자원을 App에 잘 나누어 주도록 도와준다.

 

한정된 자원에 프로세스는 많으니 O/S는 잘 나누어 주어야 하고 잘 나누어주지 않는다면

 

교착상태에 빠질 수 있다. 어떤 자원은 갖고 있으나 다른 자원은 갖지 못하여 대기하는 것

(이와 동시에 다른 프로세스 역시 다른 자원을 가지려고 대기)

 

 

교착 상태에 일어나는 조건을 살펴보니 이 4가지 조건을 모두 만족해야 교착 상태가 일어날 수 있다.

 

1. Mutual exclusion ( 상호 베타 )

>한 프로세스가 사용 중이라면 다른 프로세스는 기다려야 한다는 것. 상호 배타적

 

식사하는 철학자 예)

한 젓가락을 사용 시 다른 젓가락을 사용할 수 없다.

 

2. Hold and wait ( 보유 및 대기 )

>한 자원을 소유한 채로 다른 자원을 기다리는 것

 

식사하는 철학자 예)

왼쪽 젓가락을 소지한 채로 오른쪽 젓가락을 기다림.

 

3. No Preemption ( 비선점 )

> 강제로 뺏을 수 없는 상태. 완료될 때까지 기다려야만 한다.

 

식사하는 철학자 예)

젓가락을 강제로 뺏는 것이 불가능하다.

 

4. Circular wait ( 환형 대기 )

 

식사하는 철학자 예)

하나의 원을 이루면서 젓가락을 요구하고 있음.

 

 

이 4가지 조건을 만족해야지 교착 상태가 일어날 수 도 있는 것

 

 

컴퓨터에서 교착 상태는 언제 일어나며 일어난다면 어떻게 해결해야 할까?

 

O/S에서는 데드락이 일어나지 않도록 자원들(하드웨어들)을 잘 나누어 주어야 한다.

 

프로세스들은 자원 필요시 OS에게 요청한다. OS가 허용된다면 자원을 쓰고 다시 OS에게 자원을

 

반납한다.

 

똑같은 자원은 여러 개 일 수 있다. 예 ) 동일 CPU 4개, 동일 프린터 2개 등

 

자원 할당도

자원 1은 프로세스 1에게 할당되어있고 프로세스 2는 자원 1을 기다리고 있다.

 

식사하는 철학자의 자원 할당도

식사하는 철학자의 상태는 데드락이 일어날 수 있는 상태이다. 환형 대기까지 만족하기 때문

 

교착 상태를 제거하기 위해 원이 만들어지지 않으려면 어떻게 해야 할까?

 

-홀수번째 프로세스는 왼쪽부터 들고 오른쪽을 든다면 짝수번째 프로세스는 오른쪽부터 들고

왼쪽을 들도록 한다.

 

그렇다면 교착상태 처리 방법은 ?

 

4가지

 

1. 교착상태 방지

- Deadlock Prevention

2. 교착상태 회피

- Deadlock Avoidance

3. 교착상태 검출 및 복구

- Deadlock Detection & Recovery

4. 교착상태 무시

- Don't Care

 

1. 교착상태 방지 ( Deadlock Prevention )

 

-교착상태가 일어나는 것을 방지한다. 교착상태는 앞 4가지(상호 베타, 보유 및 대기, 비선점, 환형 대기)

 

조건을 모두 만족해야 일어나는데 이 4가지 중 하나를 깨버리는 것.

 

1. 상호 베타를 깨버리기? ( Mutual Exclusion )

 

애초에 자원은 한 프로세스가 가지고 있다면 다른 프로세스는 가질 수 없다. 상호 베타를 깨려면

 

이 자원을 공유 가능하게 만들어야 한다. 하지만 이 방법은 한 젓가락을 동시에 둘이 들 수는 없듯이

 

원천적으로 불가능하다.

 

2. 보유 및 대기를 깨버리기 ( Hold & Wait )

 

자원을 가지고 있으면서 다른 자원을 기다릴 수 없게 만든다면 가능하다. 즉 동시에 두 개를 잡거나

 

아예 잡지 않도록 만든다면 가능하다. 왼쪽 젓가락을 잡고 오른쪽 젓가락을 잡았을 시 오른쪽

 

젓가락을 이용할 수 없다면 왼쪽 젓가락도 놓아 버리는 방법이다.

 

- 단점: 자원 활용을 저하시키고 기아 ( starvation )가 일어나서 프로세스가 진행을 못할 수 있다.

 

3. 비선점을 깨자 

 

자원을 강제로 뺏을 수 있도록 만들자. 일방적으로는 불가능하다. CPU 같은 경우 강제 context switching

 

은 가능할 수 있겠지만 프린터 등 중간에 선점해버린다면 원치 않은 결과가 나올 것

 

4. 환형 대기를 깨자

 

일방적으로 환형 대기를 깨는 방법은 자원에 번호를 부여하여 오름차순으로 자원을 요청하는 방식이다.

 

식사하는 철학자를 예로 다른 모든 철학자는 왼쪽부터 집은 후 오른쪽 젓가락을 집게 되지만

 

마지막 철학자는 오른쪽 젓가락부터 집게 되므로 환형 대기를 깰 수 있다.

( 0 1 // 1 2 // 2 3 // 3 4 // 0 4 ) 이므로

 

-단점 : 일방적으로 자원에 활용률이 떨어지게 된다.

 

 

 

따라서 교착상태 방지의 주 2가지 방법은 Hold & Wait을 깨버리는 방법 혹은

Circular Wait을 깨버리는 방법이 있겠다.

 

 

 

2. 교착상태 회피 ( Deadlock Avoidance )

Application 들은 전부 자원이 필요하다. 이 자원들을 골고루 나누어 주는 역할을 OS가 한다고

 

했다. ( Resource Manager 역할 ) 

 

이렇게 자원을 나눠주게 되는데 이때 자원을 잘못 나누어 주어서 교착 상태가 일어났다고 보고

 

즉 자원 요청에 대한 잘못된 승인으로 보고 안전한 할당을 해주는 것이 교착상태 회피이다.

 

 

각 프로세스에게 current needs 만큼 나누어준다.

 

P1부터 보자면 P1는 또다시 5개를 요구할 것이다. max needs가 10이므로

 

그때 5개를 더 주게 되면 남아있는 3개를 초과하게 되니 줄 수가 없다.

 

 

P2로 보자면 P2는 또다시 2개를 요구하게 되고 이는 남아있는 3개를 초과하지도 않고 모두 요구했으니 종료

 

하게 된다. OS에게 반환한다면 이제 5개가 남게 된다. 5개가 있으면 P1도 돌릴 수 있다. 그러면

 

10개가 되고 P2도 가능하므로 안전한 할당이 된다.

 

다음 경우를 보면 5 + 2 + 3개면 2개가 남게 된다. 이렇게 원하는 대로 나누어주면 2개가 남게 되는데

 

이는 안전한 할당이라 할 수 있을까?

 

P1은 초과가 되니 줄 수 없고 P2는 2개를 더 줄 수 있으니 반환 후 4개가 된다. 4개에서 P1은 여전히

 

돌 수없다. P3 역시 6개가 필요하니 돌 수 없다. OS는 4개는 가지지만 아무것도 할 수 없는 상태이다.

 

 

즉 불안전한 할당이 교착상태로 이어지므로 안전한 할당만 되도록 해주는 방식이다. (Banker's Algorithm)

 

3. 교착상태 검출 및 복구

 

필요하다면 자원을 모두 나누어 준다. 이는 어쩌다 교착 상태를 초래하고 더 이상 동작하지 않게 된다.

 

OS는 교착상태가 일어나는지를 주기적으로 검사한다.  이는 검사에 따른 추가 부담이 있을 수 있다.

 

발생 시 복구는 한 프로세스를 일부 강제 종료시키거나 자원을 강제로 선점하여 일부 프로세스에게 할당하는 식이 되겠다.

 

4. 교착상태 무시

 

교착상태는 4가지 모두 일어나야 하므로 실제로는 거의 일어나지 않는다. 따라서 무시하고 사용하는 것

 

 

정리 ) 

 

 

컴퓨터에서 제일 중요한 것은 CPU고 이를 관리하는 부서가 OS에 Process Management 부서이다.

 

CPU 시간을 제어해주는 부서는 PM안에 CPU scheduling이다. 프로세스들이 자원을 요청할 적에 순서를

 

정해주는 부서를 Process synchronization부서라고 한다. 프로세스 동기화 부서 안에 교착상태를

 

어떻게 해결해야 할 것인가 를 처리하는 부서가 있는 것.