과제에서 허용하는 함수를 정리하고 나서, 이제 과제가 어떤 문제인지 공부가 필요할 것 같다. 식사하는 철학자(Dining Philosophers)는 전형적인 운영체제의 교착상태(Deadlock)를 설명하는 문제이다. 이번 과제는 교착상태를 뮤텍스와 세마포어를 활용해 해결하는 프로그램을 만드는 것이다.
🍽 Dining Philosophers
- 원형 테이블에 n명의 철학자가 있다. 포크 역시 n개가 있다.
- 양쪽에 포크가 놓여 있고, 테이블의 중앙에 스파게티가 있다.
- 철학자들은 반드시 양 손에 포크를 쥐고 스파게티를 먹어야 한다.
- 철학자들은 식사를 다 하면, 포크를 내려 놓고 잠을 자기 시작한다.
- 철학자들은 잠을 다 잤으면, 생각하기 시작한다.
- 모든 철학자들은 식사를 해야 하고, 일정 시간 동안 식사를 하지 못하면 죽는다.
- 철학자들은 서로 대화할 수 없고, 다른 철학자가 죽었는 지 알 수 없다.
- 한 철학자라도 사망하면, 종료된다.
여기서 철학자는 스레드, 프로세스이며 포크는 공유자원이 된다. 식사하는 철학자 문제는 교착상태(Deadlock)의 필요조건을 모두 만족한다.
🔁 교착상태(Deadlock)
교착상태란, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. 즉, 둘 이상의 스레드(혹은 프로세스)가 공유자원을 점유한 상태에서 다른 스레드(혹은 프로세스)가 점유하고 있는 자원을 줄 때까지 무한 대기하는 상태이다.
예를 들어, 철학자들이 식사를 하기 위해 동시에 오른쪽의 포크를 집어 든다면, 모든 철학자들은 왼쪽의 포크가 사용 가능해질 때까지 기다려야 한다. 모든 철학자들은 한 쪽 포크만 든 채로 반대쪽 포크를 무한 대기 상태로 기다려야 할 것이다. 이것이 교착상태, 데드락이다.
교착상태(Deadlock) 발생 조건
아래 4가지 조건을 모두 충족해야 교착상태가 발생한다. 하나라도 해당하지 않는다면 발생하지 않는다.
- 상호 배제 (Mutual exclusion)
하나의 자원은 하나의 프로세스(혹은 스레드)만 접근할 수 있다. - 점유와 대기 (Hold and wait)
프로세스(혹은 스레드)는 자원을 점유한 상태에서 다른 프로세스(혹은 스레드)가 사용하고 있는 자원을 기다린다. - 비선점 (No preemption)
다른 프로세스(혹은 스레드)의 자원을 강제로 빼앗을 수 없다. - 순환성 대기 (Circular wait)
각 프로세스(혹은 스레드)는 순환적으로 다음 프로세스(혹은 스레드)가 요구하는 자원을 가지고 있다.
🔮 뮤텍스(Mutex)와 세마포어(Semaphore)
공유자원에 여러 스레드(혹은 프로세스)가 접근한다면, 위와 같이 데드락이 발생할 뿐만 아니라, 서로 사용 중인 변수나 자료구조에 접근해 엉뚱한 값을 읽거나 수정하는 일이 발생할 수 있다.
따라서 운영체제는 공유자원에 여러 스레드(혹은 프로세스)가 접근해 문제가 발생하는 것을 막고자 동기화 기법을 만들었다. 동기화 기법을 통해 작업 처리 순서를 제어하고, 공유 자원에 대한 접근을 제어할 수 있다.
동기화 기법으로 뮤텍스, 세마포어가 있다. 둘의 차이점은 임계구역에 들어갈 수 있는 개수를 정할 수 있다는 것이다. 뮤텍스는 하나의 임계구역에 하나의 스레드(혹은 프로세스)가 들어갈 수 있지만, 세마포어는 여러 스레드(혹은 프로세스)가 들어갈 수 있다. 즉, 뮤텍스는 동기화 대상이 하나, 세마포어는 동기화 대상이 하나 이상이다.
❓임계 구역(critical section)
둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원에을 접근하는 코드의 일부이다. 따라서 임계구역에 들어가거나 빠져나올 때, 동기화 기법을 사용해 데이터 레이스를 피해야 한다.❓데이터 레이스(data race)
두 개 이상의 스레드가 같은 데이터를 이용하고 값을 바꾸려고 할 때, 발생하는 오류이다. 한 스레드는 값을 바꾸려고 하고, 다른 스레드에서 그 값을 참조 하려고 한다면 엉뚱한 값을 읽게 될 수 있다.
