[운영체제] 8. 교착상태

1. 교착상태

1) 교착상태의 정의

자원을 소유한 채, 모두 상대방이 소유한 자원을 기다리면서 무한 대기에 빠지는 상태이다. 교착상태하면 항상 나오는 문제로 식사하는 철학자 문제가 있다.

---

2. 식사하는 철학자 문제

1) 식사하는 철학자 문제

조건은 다음과 같다.

1. 5명의 철학자가 원탁에서 식사한다.

2. 자리마다 스파게티 1개와 양 옆에 포크가 있다.

3. 식사를 하기 위해서는 양 옆의 포크가 동시에 들려야 한다.

4. 왼쪽 포크를 먼저 들고 다음 오른쪽 포크를 드는 순서이다.

 

저 조건이라면 누구 한 명은 식사를 할 수 없다..! 그럼 왜 못하는 걸까..?

 

• 원인 : 환형 요청/대기 : 원으로 앉아 있기에 스스로 해체 불가능하다.
• 해결 : 원형 상태로 안 만들면 되지!

2) 컴퓨터 시스템에서의 교착 상태

식사하는 철학자의 문제과 거의 유사하다. 자원을 소유한 쓰레드들 사이에서 각 쓰레드는 다른 쓰레드가 소유한 자원을 요청하여 무한정 대기하고 있는 현상이다. 여기서 철학자가 프로세스이고 포크가 자원이고 스파게티는 프로세스가 해야할 일로 비유할 수 있다. 지연이 일어난다는 점에서 기아와 유사할 수 있다고 생각하지만 차이점이 있다. 바로 기아는 운영체제의 잘못된 정책으로 생기는 문제임에 반해 데드락은 여러 프로세스가 작업을 하다보니 일어나는 자연적인 문제이다. 

3) 교착 상태의 잠재적 요인들

1. 자원 : 이게 사실 발생지라 봐도 무방하다... 교착 상태의 원인이 한정된 자원이기에...

2. 자원과 쓰레드 : 한 쓰레드가 여러 자원을 동시에 필요로 할 때

3. 자원과 운영체제 : 한 번에 하나씩 자원을 할당하는 운영체제의 정책이 원인이다.

4. 자원 비선점 : 할당된 자원은 쓰레드가 자발적으로 내놓기 전에 강제로 뺏지 못하는 정책이 요인이다.

 

하지만 이거를 직접적으로 막을 수 없다. Cost가 상당하기 때문이다. 그래도 방법이 아예 없는 것은 아니다.

---

3. 교착상태 해결

1) 교착상태의 발생 필요충분조건

- 다음 4가지 상황이 허용되는 시스템은 언제든 교착상태가 발생 가능하다. (이 중 한 가지라도 성립되지 않으면 교착상태는 발생하지 않는다)

- 상호 배제

: 한 프로세스가 자원을 쓰면 다른 사람은 사용하지 못한다.

- 비선점

: 자원을 강제로 뺏을 수 없다.

- 점유와 대기

: 한 프로세스가 여러 자원을 다 점유하거나 다 대기할 수도 있다.

- 환형 대기

2) 해결 방법

1. 교착상태 예방 : 4가지 조건 중 하나를 깨트리기 위한 시스템으로 구성 : 자원적 특성을 제한하기 어렵다

2. 교착상태 회피

3. 교착상태 감지 및 복구 

4. 교착상태 무시 : 가장 일반적인 방법

3) Banker's 알고리즘

다익스트라가 개발한 알고리즘으로 자원 할당 전에 미래에 교착상태가 일어날 것에 대한 여부를 알고리즘으로 표현한 것이다.

- 알고리즘

1. 각 프로세스가 실행 시작 전에 필요한 전체 자원의 수를 운영체제에게 알린다.

2. 자원을 할당할 때마다 자원을 할당해주었을 때 교착상태가 발생하지 않을 만큼 안전한 상태인지 판단하여 안전한 상태일 때만 자원을 할당한다.

3. 각 프로세스가 필요한 자원의 개수, 현재 각 프로세스가 할당 받은 자원을 개수, 시스템 내에서 할당 가능한 자원의 개수를 토대로 데드락 발생 여부를 판단한다.

 

하지만 이 알고리즘은 현실적으로 불가능하다. 예측이 불가능하기 때문이다.