[ 운영체제 ] 교착상태

1. 교착상태

 

1.1 식사하는 철학자 문제 

 

식사하는 철학자 문제

식사하는 철학자 문제는 교착상태를 설명하는 아주 유명한 문제이다. 

동그란 원탁에 다섯명의 철학자가 앉아 있다. 

앞에는 음식이 놓여있고 음식은 포크가 두개 있어야 먹을 수 있다.

철학자는 왼쪽포크를 집고 오른쪽 포크를 집고 두개를 집어서 일정시간 식사를 한다.

다먹으면 오른쪽을 내려놓고 왼쪽을 내려놓는다.

 

이때, 모든 철학자가 동시에 왼쪽 포크를 집으면 아무도 식사할 수 없다.

모두 오른쪽 포크가 생기기를 기다리기만 할 것이다. 하지만 오른쪽 포크는 영영 생기지 않는다.

 

이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상을 교착상태라고 한다.

일명 deadlock!!

 

교착상태는 다양한 상황에서 발생한다.

예를 들어 뮤텍스락에서 프로세스A는 lock1를 잠구고 lock2를 기다리고

프로세스B는 lock2를 잠구고 lock1를 기다리면 이는 교착상태가 된다.

 

1.2 자원 할당 그래프

 

교착상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다. 

아래 규칙을 따라 그리면 된다.

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.
2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.
3. 프로세스가 어떤 자원을 할당받아 사용중이라면 프로세스를 향해 화살표를 표시한다. 
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다. 

자원 할당 그래프

위 규칙을 따라 그래프를 그려보았다. 

그래프를 그리면 한눈에 관계를 파악하기 좋다

deadlock

위 그림은 교착상태의 그래프이다. 

 

 

1.3 교착 상태 발생 조건

 

교착 상태가 발생할 조건에는 상호배제, 점유와 대기, 비선점, 원형대기로 네가지가 있다.

네가지 조건을 모두 만족하면 교착상태가 발생할 가능성이 생긴다.

 

상호배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태를 의미한다.

점유와 대기 : 자원을 하나 보유한 상태로 다른 자원을 기다리는 상태를 의미한다.

비선점 : 프로세스는 사용중인 자원을 강제로 뺏지 못한다.

원형대기 : 자원할당 그래프가 원의 형태로 그려지면 교착상태가 발생할 수도 있게된다.

 

2. 교착 상태 해결 방법

 

2.1 교착 상태 예방 

 

위에 나온 교착상태 발생조건을 방지하는 것이 즉 예방법이다. 

네가지 조건을 하나하나 어떻게 예방하는지 보자.

 

상호배제 : 이 문제를 해결하려면 모든 자원을 공유가능하게 해야한다. 현실적으로 불가능하다.

점유와 대기 : 필요한 자원을 동시에 할당해주거나 아예 할당해주지 않는 방법이 있다. 하지만 이는 자원의 활용률을 낮춘다. 많은 자원을 필요로하는 프로세스가 기아가 될 수도 있다.

비선점 : CPU는 대표적인 선점형 지원이다. 하지만 모든 자원이 그럴 수 있는 것이 아니라서 범용성이 떨어진다.

원형대기 : 원형대기가 생기지 않으려면 모든 자원에 번호를 붙이고, 오른차순으로 자원을 할당하면된다. 

 

 

2.2 교착상태 회피

 

교착 상태 회피는 교착 상태가 발생하지 않을 정도만 조심조심 자원을 할당하는 방식이다.

이는 교착상태를 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다.

 

교착상태가 발생하지 않고 모든 프로세스가 정산적으로 자원을 할당 받고 종료할 수 있는 상태를 안전상태라고 하고

교착상태가 발생할수도 있는 상황을 불안전상태라고 한다. 

안전 순서열은 교착상태없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미한다.

안전 순서열이 있으면 안정상태고, 없으면 불안정 상태가 된다. 

 

교착상태를 회피하기 위해서는 시스템 상태가 안전상태로 움직이는 경우에만 자원을 할당하면 된다. 

즉, 안전상태를 유지하도록 유도한다고 이해하면 된다. 

 

 

2.3 교착상태 검출 후 회복

 

이미 교착상태가 일어났다면 얼른 검출한 후 회복해야한다.

회복하는 방법은 두가지가 있다.

 

선점을 통한 회복

이는 교착상태가 해결 될 때까지 한 프로세스씩 자원을 몰아주는 방식이다.

다른 프로세스로부터 자원을 빼앗고 한 프로세스에게 주는 방식이다.

 

프로세스 강제 종료를 통한 회복

프로세스를 강제 종료하는 것은 가장 간단하고 확실한 방법이다.

그냥 전부다 종료시켜 버릴수도 있고, 문제가 해결 될 때까지 하나씩 종료시킬수도 있다.