1. 멘데토리

1.1 동작방식

철학자 과제는 philo프로세스 내부에 여러개의 철학자 스레드들을 생성하여 생존시키는 과제이다. 해당과제에서 메인스레드의 역할과 나머지 철학자 스레드들의 역할은 다음과 같다.

• 메인스레드는 die여부, full(음식을 다 먹음)상태를 바쁜대기를 통해 확인하는 역할을 한다. is_die데이터를 write한다.
• 추가 : 스케줄러에서는 restrict뮤텍스로 어떤 철학자가 포크를 양손에 들지 정하고, eat 뮤텍스를 통해 식사를 시작하는지 확인한다.
• 철학자 스레드들은 루틴(밥생각자기…)을 실행한다. 밥을 먹고 philo배열에서 자기 인덱스의 die예정 시간, full여부를 갱신(write)한다.

기본적으로 프로세스내 스레드들은 메모리에서 stack정도만 각자의 공간을 가지고 있고, heap, code공간 등은 공유한다. 이러한 heap의 특성을 이용해 뮤텍스를 최소화하기 위해 아래와 같이 heap영역의 데이터를 조작하였다.

• 메인 스레드만 is_die를 수정하고, 철학자 스레드들은 읽기만한다.
• 철학자 스레드들은 philo배열에서 각자의 인덱스의 데이터만 수정하고, 메인스레드는 읽기만한다.

추가적으로, printf하여 출력할때, 출력 도중 다른 스레드로 넘어가서 텍스트가 섞이는 현상이 간혹 발생했다. 따라서 announce라는 별도의 뮤텍스를 만들어 mutex_lock(announce)를 통과한 스레드만 출력할수 있게(한번에 하나씩) 하였다.

1.2 교착 회피

1.2.1 교착상태(데드락) 조건과 대응법

교착상태는 각 멀티 스레드/프로세스 환경에서 다음과 같은 조건을 모두 만족시 발생한다.

• 상호배제 : (교착을 유발하는)자원이 배타적이여아한다.
• 비선점 : 점유한 자원은 다른 프로세스가 뺏을수 없다.
• 점유와 대기 : 자원을 점유받고, 다른자원을 대기하고 있는 상태여야 한다.
• 원형대기 : 점유 및 대기하는 프로세스들의 관계가 원을 이루어야 한다.

이를 해당과제에 적용시켜보면, 모든 철학자가 자신의 왼쪽 포크만 들고 오른쪽 포크를 대기하고 있는 상태이다. 이 상태를 교착상태 필요조건을 파악하면 포크는 누가 집으면 집을수없고(상호배제), 뺏을수 없는(비선점) 특징을 지닌다. 그리고 모두 왼쪽포크를 들고 오른쪽포크를 기다리고 있으며(점유와 대기), 기다리는 오른쪽 포크는 오른쪽 철학자가 든 왼쪽포크이다(원형대기).

위와같은 교착상태에 대응하기 위해서 일반적으로 교착상태 예/회피/검출 및 회복 3가지 기법을 사용한다.

• 교착상태 예방 : 위의 교착상태 필요조건 4가지중 하나를 무효화 하는 방식.
  • 장점 : 구현이 쉬운편이다.
  • 단점 : 방법은 프로세스나 스레드가 자연스럽게 동작하지 않고 자원이 낭비되어 되어 잘 사용되진 않는다.
  • 과제에 적용 : 우선 상호배제, 비선점은 문제특성상 무효화할수 없다. 점유와 대기를 무효화하는 방법은 한번에 두 포크를 집을수 있을때만 집게하여 무효화할수 있다. 하지만 포크를 효율적으로 사용하지 못하게 되어 철학자가 굶어죽는다. 원형대기 무효화가 가장 적합한 예방법이다. 하나의 철학자만 왼-오 순서로 포크를 잡고 나머지는 오-왼 순서로 잡게 한다. 하지만 부자연스러운 자원 할당 방식이다.
• 교착상태 회피 : 자원을 어떻게 요청할지 요구하고, 그 정보를 바탕으로 자원을 적절하게 분배하여 교착상태를 예방하는 기법이다.
  • 장점 : 예방 방식에 비해 자원 사용이 더 효율적이다.
  • 단점 : 각 점유상태를 파악하고, 필요시 이를 줄지 말지 선택해야 한다. 즉 각 프로세스/스레드가 언제 어떤 자원을 요구할지 정확히 알아야한다.
• 교착상태 검출 및 회복 : 교착상태가 발생했는지 파악하고, 발생시 프로세스/스레드 중단 후 이를 회복하는 방식이다. 해당과제에서는 사용할수 없다.

따라서 사용할수 있는 방법은 예방 기법-원형대기무효화와 회피 기법두가지 뿐이다.

1.2.2 교착상태 대응

멘데토리 부분에서 고려할 사항을 다음과 같다.

1. 모든 포크는 철학자 사이에 있다(서로 다른 포크들이다).
2. 뮤텍스만을 사용한다.

위와 같은 특성때문에 회피 기법을 통해 자원(포크)를 억제하기 위해서는 다음과 같은 문제들이 있다고 판단하였다. 1. 각포크와 철학자마다 뮤텍스를 할당해서 접근을 제어해야한다. 2. 어떤 포크 사용을 수락할지 제어하는 스레드도 따로 만들어서 돌려야하는 작업이 필요하다.3. 이렇게 한다고 해도, 제어하는 스레드가 포크를 집기전에 동작하여 교착상태를 막을수 있을지도 보장할수 없다. 따라서 약간의 어색함이 있지만 더 확실한 예방기법의 원형대기 무효화를 사용하여 각 스레드에 적용하였다.

위의 내용들은 과제를 잘못 구현하여서 적용한 내용들이다. 멘데토리 과제에서는 교착상태를 회피하더라도 철학자들이 굶어죽을수 있다. 따라서 **스케줄링**을 통해 포크를 들을 철학자 순서를 정한다.

짝수인경우 모든 포크가 놀지 않게 스케줄링 할 수 있어서 다음과 같은 순서로 스케줄링 하면 된다.

1. 짝수 철학자들 식사
2. 홀수 철학자들 식사

홀수인경우 최소 하나의 포크가 놀 수 밖에 없다. 따라서 노는 포크의 위치를 회전하게 하여 최대한 공평하게 식사하게 한다. 7명의 철학자가 있다고 가정하자. 그러면 철학자는 0번부터 6번까지 있다.

1. 0 2 4 번 철학자 식사(5번 포크 놂)
2. 1 3 5 번 철학자 식사(6번 포크 놂)
3. 2 4 6 번 철학자 식사(1번 포크 놂)
4. 3 5 0 번 철학자 식사(2번 포크 놂)
5. 4 6 1 번 철학자 식사(3번 포크 놂)…

위와 같은 규칙성을 가지고 있다. 위를 코드로 표현하면 짝수에서도 적용 가능한 하나의 수식으로 표현된다. 이러한 수식을 스케줄러 스레드에 적용하여 정해신 순서의 스레드의 restriction을 unlock해주어서 동작하게 한다.

이후 스케줄러는 eat뮤텍스를 통해 정한 철학자들이 포크를 다 집었는지 확인하고, 다음 순서의 철학자들의 restriction을 unlock해준다.

2. 보너스

2.1 동작방식

보너스에서 철학자는 별도의 프로세스들이므로 어떠한 메모리도 공유되지 않는다. 또한 해당 과제에서 허용되는 함수중 kill을 제외한 어떠한 signal관련 함수도 사용 불가하다. 따라서 세마포어의 점유(wait) 및 해제(post)를 통해서만 다른 프로세스에게 상태를 전달할수 있다.

동작방식을 구현하면서 가장 중요하게 작용한 개념은 다음과 같다. 세마포어의 수량이 부족하여 대기하는 프로세스/스레드의 경우 대기 큐에 들어가서 대기상태로 전환되기 때문에, CPU 점유에 영향을 미치치 않는다. 또한, 뮤텍스와 달리 세마포어를 선점(wait)하지 않은 프로세스에서 풀수 있다.

이러한 개념들을 최대한 활용하여 바쁜 대기를 최소화 해보는 방식으로 코드를 작성했다.

1. 우선 상태를 확인하기위한 세마포어를 할당 및 점유시킨다. 철학자 수만큼 die와 full 세마포어를 할당하고, fork 이전에 이를 전부 점유시킨다.
2. 이후 메인 프로세스(philo_bonus)의 [die], [full]스레드는 각각 sem_wait(die), sem_wait(full)코드에 의해 대기큐 상태로 빠진다. -> 바쁜대기 회피

이후는 아래 이미지에서 설명.

보너스에서 포트는 중앙에 놓여있다. 사용 가능한 포크가 생기면, sem_wait에 의해 block되었던 프로세스 중 하나가 (OS에 의해) run state로 집입하게 되에 먹고자고생각하고… 를 수행하게 된다. 당연히 먹고 나서는 포크를 반환한다.

1. 각 철학자들은 지정된 회수만큼 식사하면 sem_post(full)하여 점유를 하나씩 푼다.
2. 메인 프로세스(philo_bonus)의 [full]스레드는 철학자 개수만큼 sem_wait(full)한다.
3. 철학자 수를 만족시키면 그 이후엔 sem_post(die)된다(이때 die출력은 하지 않음.). 모든 철학자 프로세스들을 kill하고 할당된 값들을 반환하며 프로그램을 끝낸다.

1. 철학자 프로세스의 [die_check]스레드는 하나의 die_check세마포어에 의해 한번에 하나씩 돌아가면서 상태를 확인한다. -> 바쁜 대기를 통한 CPU부하 최소화
2. [die_chekc]스레드에서 죽음이 확인되면 die출력을 하고, sem_post(die)를 한다.
3. 메인 프로세스(philo_bonus)의 [die]스레드가 깨어나고 모든 철학자 프로세스들을 kill하고 할당되었던 자원들을 반환후 프로세스를 종료한다.

2.2 교착 회피 기법

보너스과제는 멘데토리와 달리 세마포어를 통해 포크의 접근을 제한한다. 이때 세마포어는 뮤텍스와 달리 자원의 개수를 정할수 있다. 그러므로 모든 철학자들이 한손에 포크를 들고있는 상황만 피하면 교착상태를 막을수 있다. 이런 상황은 식권을 통해 첫포크를 들고있는 철학자의 수를 **모든 철학자의 수 - 1**로 제한하여 회피하였다(교착 회피 기법).