운영체제 - 식사하는 철학자 문제와 교착상태에 대해 알아보기

식사하는 철학자 문제 (Dining Philosophers Problem)

운영체제 수업 시간에 식사하는 철학자 문제와 교착상태를 배우게 되었다.

교착상태는 티비에서도 가끔 나오고 그래서 대충 알고 있었는데 이번에 제대로 알게되었다.

 

식사하는 철학자 문제는 1965년 네덜란드의 대학교에서 병렬처리에서의 동기화 이슈와 해결 방법을 설명하려고 학생들에게 냈던 시험 문제라고 한다. 

 

1. 5명의 철학자가 원탁에서 식사를 하려고 자리에 앉았있다.
2. 각각의 철학자들 앞에는 스파게티가 1접식씩 있고 철학자들 사이에 포크가 하나씩 있다. 즉 포크는 5개
3. 각 철학자는 옆의 철학자에게 말을 할 수 없으며, 두 가지 행동을 한다. 스파게티를 먹거나 생각하거나
4. 철학자는 식사를 하기 위해서 자신의 양옆에 있는 2개의 포크를 모두 잡아야 식사를 할 수 있다.

이 때 식사하는 데 어떤 문제가 생길까?

 

만약 모든 철학자들이 거의 동시에 왼쪽 포크를 집어들고 오른쪽 포크를 집으려고 한다면?

5개의 포크는 각각이 하나씩 들어서 결국 아무도 두개의 포크를 얻지 못해 식사를 할 수 없게 된다. 

이것이 무한 대기가 발생하는 교착상태라고 한다.

 

이걸 해결하는 방법이 있을까?

-> 철학자들에게 우선순위를 부여하여 마지막 철학자만 항상 오른쪽 포크를 먼저 들도록 하고 나머지 철학자는 왼쪽 포크를 먼저 들도록 하게 한다.

 

이러한 교착 상태는 다중프로그래밍 시스템 초기에 노출된 문제점이라고 한다.

 

교착상태

교착상태는 자원을 요청, 대기에 의해 발생하며 아래 문장들로 정의할 수 있다.

자원을 소유한채 모두 상대방이 가진 자원을 기다리면서 무한대기하는 현상
자원을 소유한 스레드들에서 각 스레드는 다른 스레드가 소유한 자원을 요청하여 무한정 대기하는 현상

 

교착상태가 발생하는 위치는?

정교하지 못한 코딩에서 비롯하므로 사용자가 작성한 멀티스레드 응용프로그램 또는 커널 내부에서 발생한다.

 

교착상태 유발 요인

교착상태는 식사하는 철학자 문제로 잠깐 알아봤는데 컴퓨터 시스템에서 교착상태가 발생되는 요인은 무엇일까?

 

1. 멀티스레드가 자원을 동시에 사용하려는 충돌이 요인이다.

2. 한 스레드가 여러 자원을 동시에 필요로 하는 상황이 요인이다.

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

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

 

코프만 조건(Coffman Condition)

코프만 조건이란 교착상태가 발생하는 4가지 필요충분조건이다.

 

1. 상호배제 (Mutual Exclusion) -> 각 자원은 한 번에 하나의 스레드에게만 할당

2. 소유하면서 대기 (Hold & Wait) -> 스레드가 한 자원을 소유하면서 다른 자원을 기다리기

3. 강제 자원 반환 불가 (No Preemption) ->스레드에게 할당된 자원을 강제로 뺏지 못함

4. 환형 대기 (Circular Wait) -> 한 그룹의 스레드들에 대해, 각 스레드는 다른 스레드가 요청하는 자원을 소유하는 환형 고리 형성

 

이러한 4가지 조건 중 하나라도 성립되지 않으면 교착상태는 발생되지 않는다.

 

위 요인을 보고 코프만 조건을 배우게 되면 뭔가 유사한점이 보이게 된다.

 

그렇다면 교착상태는 해결될 수 없을까?

우리는 윈도우 운영체제를 사용하면서 교착상태에 빠졌다고 생각이 들 때 가 있었을까?

우선 컴퓨터를 하다보면 응답없음이라는 상황은 자주 겪에되는데 이것과 교착상태는 다르다고 한다.

내가 인지 못하는 상황이 아니라면 나는 겪어보지 못했는데 그렇다면 윈도우는 교착상태를 잘해결했을까?

 

교착상태를 해결하는 방법

교착상태를 해결하는 방법에는 4가지가 있다.

 

1. 교착상태 예방
2. 교착상태 회피
3. 교착상태 감지 및 복구
4. 교착상태 무시

 

교착상태 무시? 너무 옛날에 썼던 방법일까? 아니다. 오히려 현재까지 리눅스 또는 윈도우와 같은 운영체제에서 사용중인 방법이라고 한다. 그렇다면 교착상태를 해결하는 방법들에 대해 자세히 알아보자

 

1. 교착상태 예방

교착상태에 빠지는 4가지 코프만 조건 중 하나 이상의 조건이 성립되지 못하도록 시스템을 구성한다.

 

상호 배제를 없애고, 소유하면서 기다리지 않게 한다 즉, 필요한 모든 자원을 파악하고 한 번에 할당한다. 그리고 한 번에 반환한다. 자원의 선점을 허용하고, 모든 자원에 번호를 매기고 번호순으로 할당하여 환형 대기를 제거한다.

 

그런데 왜 이렇게 하지 않는가? 

시스템상 불가능하여 실제로 구현하지도 못할뿐더러 오버헤드가 매우크고 매우 비효율적이기 때문이다.

 

2. 교착상태 회피

자원 할당 시마다 미래의 교착 상태 가능성을 검사하여 교착 상태가 발생되지 않는 확신되는 경우에만 자원을 할당한다.

 

안전한 상태와 불안전한 상태로 구분한다. 환형 대기에 빠질 수 있다면 불안전한 상태라고 한다. 각 프로세스가 실행 시작 전에 필요한 자원의 개수를 계산하여 운영체제에게 알리고 교착상태에 빠지지 않을지 판단하여 자원을 할당한다.

 

그러나 이것도 비현실적인데 실행 시작 전에 필요한 자원의 개수를 아는 것은 불가능하다. 실제 프로세스의 개수는 동적으로 변하고 미리 프로세스 개수를 적적으로 고정하는것도 힘들기 때문이다.

 

3. 교착상태 감지 및 복구

교착상태를 감지하는 프로그램을 백그라운드에서 구동시키고 감지되면 교착상태를 해제한다.

 

그나마 이 방법이 내가 생각하기에는 사용될만한 방법이지만 여러 문제를 초래할 수 있다.

 

교착 상태를 감지하면 어떻게 복구시킬까 먼저 교착상태에 빠진 다른 스레드의 자원을 강제로 빼앗아야한다. 그리고 다른 스레드에게 할당하는데 빼앗긴 스레드는 어떻게 될까? 롤백 or 스레드 강제 종료 상태에 직면하게 된다.

 

롤백은 스레드를 주기적으로 저장하여 교착상태가 발생하면 마지막 저장 상태로 되돌린다. 그렇게 스케줄링 등 자원 할당 순서가 달라지는 것이다.

스레드 강제종료는 스레드를 그냥 강제 종료하는것인데 간단하면서 효과적이다. 하지만 그 피해는 어떻게 될까?

 

하지만 이 방법도 시간과 메모리 공간에 대한 부담이 크기 떄문에 잘 사용되지 않는다.

 

4. 교착상태 무시

교착상태는 없다고 단정하고 대비책이 없다. 

 

 

실제로 타조 알고리즘이라고 불리는데, 마다가스카의 팽귄에서 타조 캐릭터 셸리가 기억이 났다.

타조는 저렇게 땅에 머리를 박고 있는 모습이 연상이 되는데

 

타조의 이름을 따서 Ostrich 알고리즘이라고 불린다.

 

교착상태를 무시하는 이유는 바로 교착상태를 피하는 방법에는 정말 많은 비용이 소모되지만

교착상태가 발생되는 확률이 극히 적다는것이다.

 

실제로 유닉스, 리눅스, 윈도우 등등의 운영체제에서 사용되는 방법이다.

 

사용자나 관리자가 의심 가는 스레드를 종료시키거나 시스템을 재시작하는 방법으로 해결하도록 만드는것이다.

 

다시 말하면 교착상태 무시는 교착상태가 일어나지 않을 것으로 가정하고, 교착상태에 대한 아무 대책을 세우지 않는 것이다. 교착상태가 발생할 확률은 극히 적고, 교착상태 예방, 회피, 감지 및 복구에는 많은 비용이 소모되기 때문이다.

 

하지만 이 방법도 완전하지는 않는데 관련된 데이터를 잃어버릴 수 있기 때문이다.

그래서 매우 중요한 시설에 핵이나 전투 시스템 등등 에서는 다른 방법으로 사용될것이다.