다양한 운영체제 문제들 중 '식사하는 철학자'문제에 대해 알아보며 더 나아가 스레드,뮤텍스,세마포에 대해 정리해보려고 합니다.
데드락과 식사하는 철학자
식사하는 철학자문제는 운영체제의 데드락 상태를 설명하기 위한 문제입니다.
그림 1. 식사하는 철학자 문제5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다. 식사순서는 다음과 같다.
1. 일정시간 생각을 한다.
2. 왼쪽 포크를 사용할 수 있을때까지 대기한다. 사용 가능하다면 집어든다.
3. 오른쪽 포크를 사용할 수 있을때까지 대기한다. 사용 가능하다면 집어든다.
4. 양쪽 포크를 잡으면 일정시간만큼 식사한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번부터 수행한다.왼쪽 포크와 오른쪽 포크를 한번에(atomic) 가져오는 것이 아니라 순서대로(sequentially) 가져오기 때문에, 모두가 왼쪽 포크부터 집어드는 이런 단순무식한 알고리즘을 가지고 있으면 문제가 생길 수밖에 없습니다. 5명의 철학자 전부 왼쪽 포크를 들고 있다면 오른쪽 포크를 얻으려고 할 때 오른쪽 포크는 이미 상대방이 가져간 상태이고, 오른쪽 철학자의 오른쪽 역시 가져간 상태이고.. 이렇게 원탁을 한 바퀴 돌아 자기 자신까지 돌아오면 모든 철학자들이 3번 상태에 머무르며 자기 오른쪽 포크가 사용 가능해질 때까지 영원히 기다리고만 있는 교착(deadlock) 상태에 빠지게 되는거죠.
또한 어떤 경우에는 계속해서 양쪽 포크를 집을 수 없어 식사를 하지 못하는 기아 상태가 발생할 수도 있고, 몇몇 철학자가 다른 철학자보다 식사를 적게 하는 경우가 발생하기도 합니다.
위에 철학자 예시처럼 잘못된 자원관리로 인하여 둘 이상의 프로세스 혹은 스레드들이 아무것도 진행하지 않는 상태로 서로 영원히 대기하는 상황을 데드락(교착상태)라고 합니다.
데드락의 발생조건을 정리하자면 다음과 같이 요약할 수 있습니다.
- 상호 배제 : 한번에 하나의 프로세스만 해당 자원을 사용할 수 있다. (위에선 포크가 자원)
- 점유 상태로 대기 : 자원하나를 붙잡은 상태에서 다른 자원을 기다리는 것. (왼쪽 포크를 잡고 오른쪽 포크를 잡기위해 대기)
- 선점불가 : 다른 프로세스의 자원을 못 뺏는것.
- 순환대기 : 모든 프로세스가 자원을 기다리는 상황에서 마지막 프로세스가 첫 프로세스가 사용중인 자원을 쓰기 위해 대기중인 상황 (위에선 5번 철학자가 왼손포크를잡고 1번 철학자가 식사를 마치기를 기다림)
데드락의 해결법은 크게 3가지로 나눌 수 있습니다.
- 데드락이 발생하지 않도록 예방
- 데드락이 발생할 수 있지만 적절하게 회피
- 데드락이 발생할 수 있지만 이를 탐지하여 회복
저는 식사하는 철학자 시뮬레이션을 구현하면서, 데드락을 예방하는 식으로 구현을 했습니다.
식사하는 철학자에선 순환대기시에 데드락이 걸리게되는데, 이를 피하기 위해 홀수번의 철학자들을 먼저 식사를 시켰습니다. 만약 식사기간이 5초라면 5초뒤에 식사를 시작하도록 하는거죠. (다만 약간의 비효율 발생)
이런식으로하여 순환대기를 발생시키지 않도록 했습니다.
그림2. 철학자 시뮬레이션 결과뮤텍스를 이용하여 구현을 했고 실행하시면 타임스탬프가 위에 이미지처럼 찍히게 됩니다.
뮤텍스를 이용하여 구현했다고 했는데.. 뮤텍스는 무엇이고, 다른 방법은 뭐가 있을까요?
뮤텍스
Mutual Exclusion의 합성어입니다.
Mutual은 상호작용을, Exclusion은 제외를 의미합니다. 합치면 상호배제가 됩니다.
데드락 발생조건에서 1번 조건입니다. 왜 상호배제를 구현하느냐? 아시다시피 하나의 프로세스안의 스레드들은 자원을 공유하게됩니다. 이때, 마구잡이로 공유자원에 접근하게 되면 race condition(경쟁상태)이 되어 데이터의 일관성이 없어지게 됩니다. ex) 1번 스레드에서 a++했는데, b에서 이를 모르고 a를 사용하는 상황
그래서 상호배제라는 개념을 통해 스레드 혹은 프로세스들이 안전하게 자원을 공유하는거죠.
그림 3. 경쟁조건 이미지상호배제를 구현하기위한 동기화 기법중 하나인 뮤텍스는 공유자원에 대한 접근을 동시에 하나의 스레드만 가능하게 제한하는겁니다. 철학자를 예시로보면, 포크를 하나의 뮤텍스로 보는거죠. 포크는 한명의 철학자만 들 수 있도록 하여 경쟁상태를 막을 수 있게 되는 겁니다. 뮤텍스는 key를 기반으로 구현되어, key를 소유한 프로세스만이 공유자원에 접근할 수 있습니다. 이때 key를 가지고 있다는걸 뮤텍스 lock을 할 수 있다고 표현합니다. 모두사용하면 unlock이라고 메인 프로세스에 알리게 됩니다. 참고로 공유존재하는 영역을 임계구역(Critical Section)이라고 합니다. (네트워크의 토큰링느낌)
그림 4. 뮤텍스 이미지세마포
Semaphore라는 단어입니다.
깃발이란 뜻이며, 철도용어로 쓰이는 단어라고합니다.
여러 대의 기차가 하나의 철로를 공용하여 쓸 때, 오직 하나만 지나갈 수 있도록 하기 위해 양쪽 끝 선에 깃발 표시를 하여 사고가 안나게 하였던 장치이다.라고 하네요.
프로그래밍에서 세마포도 비슷하지만, 좀 다른게 오직 하나만 지나가는 건 아닙니다.
세마포는 사용하는 스레드나 프로세스 수를 공통으로 관리하는 하나의 값을 이용해 상호배제를 구현합니다. 최대 허용치만큼 스레드가 접근할 수 있습니다. 대기 큐를 이용하여 기다리는식으로 작동합니다. (초기는 busy-waiting의 스핀락기법) 뮤텍스랑 얼핏보면 비슷하죠? 비슷한거 맞습니다. 동시에 접근하는 수가 하나인 세마포를 뮤텍스라고 부릅니다. (이진 세마포)
다만 세마포는 공유자원을 소유(lock)하진 않습니다.
그림 5. 세마포 이미지
정리
- 식사하는 철학자문제는 데드락을 설명하는 문제이다.
- 데드락은 자원을 공유하는 상황에서 발생할 수 있다.
- 프로세스간 통신 IPC (Inter Process Communication)중 데이터를 보호하기 위해 세마포 & 뮤텍스 기법을 사용한다.
- 임계구역이라는 데이터 공유공간에 접근가능한 스레드 수에 따라 뮤텍스(접근가능수가 1), 세마포(접근가능수가 1이상)라고 한다.
참고자료
