[Philosophers] Philosophers과제 총 정리

채명석·2021년 8월 6일

42Seoul

목록 보기

1/45

philosophers는 CPU의 병행제어와 관련해서 자주 나오는 문제입니다.

그렇기 때문에 프로세스, 스레드, 스케쥴링 등의 사전지식이 많이 필요합니다.
공부를 하지 않는다면 과제에 손도 못 대게 됩니다..
관련 내용은 이전 글에 정리를 해 놨으니 참고하시길 바랍니다!

[Philosophers] Philosophers과제 총 정리
멀티 프로세싱, 멀티 스레딩, 멀티 프로그래밍, 멀티 태스킹에 대해서 알아보자
프로그램, 프로세스, 스레드에 대해서 알아보자

과제 설명

규칙

한 명 이상의 철학자가 둥근 테이블에 앉아 다음과 같은 세 행동 중 하나를 취합니다 : 먹기, 생각하기, 잠자기
철학자가 밥을 먹는 도중에는, 생각하거나 잠을 자지 않습니다. 마찬가지로 잠자는 도중에는 밥을 먹거나 생각할 수 없으며, 생각하는 도중에는 밥을 먹거나 잠들 수 없습니다.
철학자들은 둥근 테이블에 앉아있으며, 가운데에는 아주 큰 스파게티 그릇이 놓여 있습니다.
탁자 위에는 몇 개의 포크가 올려져 있습니다.
스파게티는 포크 하나만으론 집거나 먹기가 어렵기 때문에, 철학자들은 반드시 양 손에 포크를 쥐고 (2개의 포크를 사용하여) 먹어야 합니다.
철학자는 절대로 굶고 있으면 안 됩니다.
모든 철학자는 먹어야 합니다.
철학자들은 서로와 대화할 수 없습니다.
각 철학자는 다른 철학자가 언제 죽는지 알아챌 수 없습니다.
철학자가 밥을 다 먹었으면, 포크를 내려놓고 잠자기 시작합니다.
철학자가 잠을 다 잤으면, 생각하기 시작합니다.
철학자가 한 명이라도 사망하면 시뮬레이션이 종료됩니다.
각 철학자에게는 1부터 'number_of_philosophers' 만큼의 고유 번호가 부여됩니다.
철학자 1번은 철학자 'number_of_philosophers'번 옆에 앉습니다. 그 외에, N번 철학자는 N-1번 철학자와 N+1번 철학자 사이에 앉습니다.
철학자의 상태는 다음과 같은 형식으로 출력되어야 합니다. (X는 철학자의 고유 번호로 대체되어야 하며, timestamp_in_ms는 현재 타임스탬프가 밀리초 단위로 표시되어야 합니다.)
- timestamp_in_ms X has taken a fork
- timestamp_in_ms X is eating
- timestamp_in_ms X is sleeping
- timestamp_in_ms X is thinking
- timestamp_in_ms X died
철학자의 상태는 다른 철학자들의 상태와 뒤엉키거나 섞인 상태로 출력되면 안 됩니다.
철학자의 사망 시점과 이를 출력하기 까지의 틈이 10ms 이상이 되면 안 됩니다.
다시 말하지만, 철학자들이 최대한 죽지 않도록 설계해야 합니다!
두 철학자 사이에 한 개의 포크가 존재하므로, 철학자가 여러명일 경우 각 철학자의 왼쪽과 오른쪽에 포크가 하나씩 존재해야 합니다.
철학자가 포크를 복제하는 것을 막기 위해서, 각 포크의 현재 상태를 뮤텍스를 이용하여 보호해주어야 합니다.
각 철학자는 스레드로 구현되어 있어야 하고 한개의 스레드로 구성되어 있어야 합니다.

인자

철학자의 수 (number_of_philosophers)
테이블에 앉아 있는 철학자의 수와 포크의 수
철학자의 수명 (time_to_die)
밀리초 단위로, 철학자가 마지막으로 밥을 먹은 지 'time_to_die' 시간만큼이 지나거나, 프로그램 시작 후 'time_to_die' 시간만큼이 지나면 해당 철학자는 사망합니다.
밥을 먹는데 걸리는 시간 (time_to_eat)
밀리초 단위로, 철학자가 밥을 먹는 데 걸리는 시간입니다. 해당 시간동안, 철학자는 두 개의 포크를 소유하고 있어야 합니다.
잠자는 시간 (time_to_sleep)
밀리초 단위로, 잠을 자는 데 소모되는 시간입니다.
각 철학자가 최소한 밥을 먹어야 하는 횟수(number_of_times_each_philosopher_must_eat)
해당 인자값은 선택사항입니다. 모든 철학자가 'number_of_times_each_philosopher_must_eat' 횟수만큼 밥을 먹었다면, 시뮬레이션이 종료됩니다. 해당 값이 명시되어 있지 않다면, 철학자가 한 명이라도 사망할 때까지 시뮬레이션은 계속됩니다.

프로그램 정보

프로그램 명
philo
제출해야할 파일
philo/
Makefile
필요
인자
참고
사용 가능한 함수
memset, printf, malloc, free, write, usleep, gettimeofday, pthread_create, pthread_detach, pthread_join, pthread_mutex_init, pthread_mutex_destroy, pthread_mutex_lock, pthread_mutex_unlock
참고
Libft 사용
불가능

구현

구현 방법에는 다양한 방법이 있겠지만 이번 글에서는 제가 사용한 방법을 위주로 글을 쓰겠습니다.

시작하기에 앞서 주의해야하는 부분부터 알아보고 갑시다.

주의해야 할 점

philosophers에서 가장 주의해야 할 점은 교착상태(Deadlock), 기아상태(Starvation)가 되지 않도록 해야합니다.

교착상태는 모든 철학자가 동시에 한쪽 포크를 들고 다른쪽 포크를 기다리는 등 오지않는 이벤트를 영원히 기다리게 되는 것을 말합니다.

기아상태는 말 그대로 식사를 못 해서 죽게되는 것을 말하구요.

교착상태가 일어나려면 다음과 같은 조건들을 충족시켜야 합니다.

상호배제(Mutual exclusion) : 스레드가 자원을 갖고 있으면 다른 스레드는 해당 자원을 점유하지 못합니다.
점유대기(Hold and wait) : 다른 스레드의 자원을 기다리는 상태입니다.
비선점(No preemption) : 스레드가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없습니다.
순환대기(Circular wait) : A스레드가 갖고있는 자원이 B스레드에게 있고, B스레드에게 필요한 자원이 A스레드에게 있어서 서로가 서로의 자원을 기대리는 상황을 말합니다.

왼쪽에 있는 포크를 먼저 들고 오른쪽 포크를 든다고 한다면

상호배제 : 각 포크는 뮤텍스로 보호되고 있습니다.
점유대기 : 왼쪽 포크를 먼저 들고 오른쪽 포크를 대기하게 됩니다.
비선점 : 뮤텍스로 보호중인 포크를 뺏어올 수 없습니다.
순환대기 : 각 철학자는 이전 철학자가 필요한 포크를 갖고있습니다.

모든 조건이 충족되기 때문에 교착상태가 발생합니다.

이 조건들 중 하나라도 충족하지 못 한다면 교차상태는 발생하지 않는다고 합니다.

제가 사용한 해결 방법은 짝수, 혹은 홀수번의 철학자가 먼저 식사를 시작한 후 남은 철학자가 식사를 시작하게되는 구조입니다.
이렇게 된다면 포크를 들지 않고 대기를 하고 양쪽의 포크가 사용가능할 때 식사를 하기 때문에 점유대기 및 순환대기를 충족시키지 못하기 때문에 교착상태는 발생하지 않습니다.

하지만 철학자의 수가 짝수일땐 문제가 없지만 홀수라면 문제가 발생합니다.

철학자의 수가 5명이라고 할 때 홀수번의 철학자 먼저 식사를 합니다.
그러면 1, 3, 5번의 철학자가 식사를 하게 되는데 1, 5번의 철학자의 포크가 겹치게 됩니다.
만약 1번 철학자가 먼저 식사를 시작하게 됐다면 그 다음에는 5번 철학자가 식사를 하게 됩니다.
그러면 4번 철학자는 식사를 해야되는 시간인데 5번철학자에게 포크를 빼앗겨서 식사를 제 시간에 하지 못하기 때문에 철학자가 짝수명일때와 동일한 time_to_die를 주게 된다면 기아상태가 발생하기 때문에 time_to_eat이상의 여유시간을 주도록 합시다.

알아두면 좋은 점

usleep은 컴퓨터의 상태에 따라서 편차가 굉장히 심합니다.
ms단위로 시간을 재야하는 이번 과제에서는 시간이 굉장히 중요합니다. 하지만 usleep은 편차가 너무 심해서 time_to_eat만큼의 지연시간을 줘도 그 이상 시간을 잡아먹습니다.
만약 시간이 계속 맞지 않는다면 usleep에 할당된 시간을 줄이고 다른 방법을 이용해보세요.
반복문을 길게 사용한다면 약간의 usleep을 걸어주세요.
필수적으로 사용해야하는 반복문이라면 어쩔 수 없지만 반복문이 오랫동안 계속되고, 반복문 안에 context swiching이 일어날만한 부분이 없다면 해당 스레드에 할당된 제한시간(약 10~100ms)동안 계속 돌게 됩니다.
그러면 그만큼 시간이 지연되겠죠.
그래서 단순히 대기, 지연시간을 위한 혹은 우선순위가 낮은 반복문에서는 usleep을 약간씩 걸어줘서 다른 스레드가 동작할 수 있도록 해주세요.
스레드는 동작 순서가 정해져있지 않습니다. 그래서 변수접근에 조심해야 합니다.
만약 철학자 스레드에서 초기화되는 변수가 있는데, 만약 그 변수가 초기화되기 전에 다른 스레드에서 접근하면 잘못된 값이 나올 수 있습니다. 그렇기 때문에 가능하다면 초기화는 스레드 만들기 전에 해 주세요.

나의 프로그램 구성

에러체크(인자에 숫자가 아닌 것, 인자 수, 잘못된 인자 등)를 하고 뮤텍스, 변수, 철학자 변수를 초기화 합니다.

그 다음 홀수, 혹은 짝수번 철학자의 스레드를 만들고 해당 철학자들이 모두 포크를 들고 식사를 할 수 있을 정도의 지연시간을 준 뒤 남은 스레드를 만들고 철학자 스레드의 종료조건을 확인하게 됩니다.
종료조건에 맞는다면 모든 자원을 해제합니다.

철학자 스레드를 확인해 봅시다.
철학자 스레드는 스레드를 생성한 순간부터 동작합니다.

철학자 스레드는 무한루프의 형태를 갖고 있습니다.
반복문 내부에 먹는 것, 자는 것, 생각하는 것의 형태를 갖고 있으며
먹는 것은 왼쪽포크를 집고 출력하고, 오른쪽 포크를 집고 출력하고, 먹고 출력하고 time_to_eat만큼 지연시간을 걸고 먹은 횟수를 체크합니다.
자는 것은 출력하고 time_to_sleep만큼 지연시간을 줍니다.
생각하는 것은 출력하고 넘어갑니다.
물론 행동마다 스레드를 종료해야하는 상황인지 아닌지 확인 한 후 정상이라면 동작합니다.

이런 식으로 먹고 자고 생각하는게 종료조건에 걸릴때까지 반복합니다.