[운영체제] 교착상태 (Deadlock) 및 기아상태(Starvation)

교착상태 (Deadlock)

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태

데드락이 일어나는 경우

P0과 P1이 S와 Q를 모두 얻어야 하는 경우에

P0이 S를 얻고 그 후 context switching이 일어나 P1이 Q를 얻었다.

그리고 다시 context switching이 일어나고 P0은 Q자원을 얻기 위해 기다리게 되고 P1은 S자원을 얻기 위해 기다리게 된다.

즉 서로가 원하는 자원이 상대에게 있어 아무것도 진행되지 못하고 둘 다 기다리고 있는 상황이 되는 것이다.

 

교착상태의 발생 조건 - 모두 성립해야 발생

- 상호 배제 : 하나의 프로세스가 자원을 사용중일 때 다른 프로세스는 그를 사용할 수 없다.

- 점유 대기 : 최소 하나의 자원을 점유하고 있으면서 다른 프로세스가 사용중인 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재한다.

- 비선점 : 다른 프로세스가 자원을 사용중인 경우 그 사용이 끝날 때 까지 강제로 뺏을 수 없다.

- 순환 대기 : 프로세스의 집합에서 순환형태로 자원을 대기하고 있어야 한다.

 

교착상태의 예방 및 회피

예방

교착상태의 발생 조건 중 하나를 제거하면서 예방.

- 상호 배제 부정 : 여러 프로세스가 공유 자원 사용

- 점유 대기 부정 : 프로세스 실행 전 모든 자원 할당

- 비선점 부정 : 점유중인 자원을 다른 프로세스가 요구하는 경우 그를 반납

- 순환 대기 부정 : 자원에 고유 번호를 할당한 후 순서대로 자원 요구

회피

- 은행원 알고리즘

프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 미리 검사하여 교착 상태를 회피한다.

안정 상태인 경우만 자원을 할당하고 그렇지 않은 경우 다른 프로세스들의 자원 해지시 까지 대기한다.

 

 

반응형

 

교착상태의 회복 및 발견

회복

- 교착상태를 일으킨 프로세스를 종료

• 교착 상태의 프로세스 모두 중지
• 교착 상태가 제거될 때까지 하나씩 프로세스 중지

 

- 할당된 자원을 회수해 회복하는 기법

• 교착상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당
• 우선 순위가 낮거은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

발견

자원할당 그래프를 통해 교착 상태 탐지

 

식사하는 철학자 (Dining Philosophers)

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

철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.

1. 일정 시간 생각을 한다. 
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다. 
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

만약 모든 철학자들이 자신의 왼쪽포크를 잡는다면, 모든 철학자들이 오른쪽 포크가 사용 가능해질 때까지 기다려야한다.

해결 방법

1) 타임아웃 설정 : 철학자가 포크를 집고 일정 시간 내에 다른 쪽 포크를 획득하는데 실패한다면, 포크를 반납하게 한다. 가장 간단하지만 타임아웃에 따른 딜레이가 있다.

2) 철학자들 중 하나는 포크를 오른쪽부터 잡게함 : 예를 들어 1번 철학자는 왼쪽부터, 2번 철학자는 오른쪽부터 잡는다. 1번 철학자가 왼쪽 포크만 잡은 상태에서 행동권이 2번 철학자에게 넘어간다고 하더라도, 2번 철학자는 자신의 오른쪽 포크가 현재 사용 불가능하기 때문에, 첫번째 포크를 잡으려는 상황에서 멈춰 있게 된다. 이 상황에서 1번 철학자로 다시 행동권이 넘어오게 되면 1번 철학자는 자신의 오른쪽 포크를 잡고 다시 식사를 할 수 있게 된다.

 

기아 상태(Starvation)

특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태를 말함.

 

교착 상태와의 차이

교착상태는 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태를 말하고 기아 상태는 프로세스가 원하는 자원을 계속 할당 받지 못하는 상태이다. 즉 교착 상태는 여러 프로세스가 동일한 자원 점유를 원할 때 발생하고 기아 상태는 여러 프로세스가 자원을 점유하기 위해 경쟁 할 때 특정 프로세스는 영원히 자원 할당을 받지 못하는 것이다.