서론
이번 과제는 생각보다 오래 걸려서 8~9일 정도 소요되었던 것 같다. 완성은 해놓고 집에 내려갔다 오느라 블랙홀 2일 남기고 평가를 받았는데, 내 코드를 4일 만에 다시 봄 + 평가에 문제 생기면 블랙홀 12시간 남기고 재평가받아야 함이라는 두 가지 요소로 인해 평가 내내 정신이 나갈 것 같았다. 다음부터는 이런 식으로 평가받지 말아야겠다.
철학자 과제는 운영체제에서 유명한 문제인 "식사하는 철학자 문제"를 직접 구현해보는 과제이다. 식사하는 철학자 문제는 대표적인 “동시성 제어” 문제로 하나의 젓가락(또는 포크)를 두 명이 동시에 잡지 못하도록 하면서(상호 배제), 각자 하나의 젓가락을 들고 다른 사람의 젓가락을 요구하는 데드락을 피해야 한다.
상호 배제는 뮤텍스를 통해서 구현하고, 데드락은 예방하거나 적절히 회피하거나 탐지해서 해제하는 방향으로 구현함. 더 자세한 설명은 이 유튜브 영상을 참조 https://youtu.be/YAP0Bv_aQl8
서브젝트 정리
둥근 테이블에 앉아있는 한 명 이상의 철학자가 둥근 테이블에 앉아 먹거나 생각하거나 잠들거나, 이렇게 셋 중 하나의 행동을 한다.(한 번에 하나의 행동만을 한다)
둥근 테이블 한가운데에는 아주 큰 스파게티 그릇이 있으며, 철학자는 양쪽의 포크를 모두 사용하여 밥을 먹어야 한다.
모든 철학자는 서로 대화할 수 없으며(서로의 정보와 언제 죽는지를 알 수 없음), 수명 이상으로 굶는다면 철학자는 죽는다.
이 프로그램은 철학자의 수, 수명, 밥 먹는 시간, 잠자는 시간, [총 식사 횟수]를 인자로 받는다.
해당 옵션이 있다면 총 식사 횟수를 채우거나, 하나의 철학자라도 죽으면 10ms안에 프로그램이 종료되어야 한다.
철학자가 밥을 다 먹으면 포크를 내려놓고 잠들며, 잠을 다 자면 생각을 한다. 생각하는 도중에 밥을 먹을 수 있으면 밥을 먹는다.
철학자의 상태는 다음과 같은 형식으로 출력된다. 다른 철학자의 상태와 뒤엉키거나 섞인 상태로 출력이 되면 안 된다.
- 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
철학자는 각각 한 개의 스레드로 구성이 되어있어야 하며 포크가 복제되지 않도록 포크를 뮤텍스로 보호해야 한다.
왜인지는 모르겠지만 philo/ 안에 Makefile, *.h, *.c 파일을 넣어서 제출해야 한다.
이론 정리
허용 함수 정리
memset, printf, malloc, free, write는 기존 과제에서 많이 사용해봤을 테니 설명 생략
usleep - suspend thread execution for an interval measured in microseconds
#include <unistd.h>
int usleep(useconds_t microseconds);microseconds 만큼 프로세스를 재운다. 마이크로 초는 1/1000 밀리 초를 의미하며, 밀리 초는 1/1000 초이다. 따라서 1초를 대기하려면 usleep(1000*1000); 을 하면 된다.
재운다는 의미는 Sleep 상태를 의미하며, Sleep 상태가 종료되면 Ready 상태가 된다.(즉 usleep 함수가 끝난다고 해서 바로 Running이 되지 않는다.)
프로세스는 New, Ready, Sleep, Running, Terminated의 다섯 가지 상태를 가지고 있을 수 있다. 실행할 준비가 되면 Ready 상태가 되며, 스케쥴러가 큐에서 실행시키면서 Running 상태가 된다.
반환 값은 성공 시 0, 실패 시 -1
gettimeofday - get date and time
#include <sys/time.h>
int gettimeofday(struct timeval *restrict tp, void *restrict tzp);
_STRUCT_TIMEVAL
{
__darwin_time_t tv_sec; /* seconds */
__darwin_suseconds_t tv_usec; /* and microseconds */
};tzp는 현대에 이르러서는 거의 사용하지 않기 때문에, NULL로 넣어주면 된다.
timeval을 미리 선언한 이후에 gettimeofday(&time, NULL)과 같은 형태로 사용한다.
반환 값은 성공 시 0 실패 시 -1
#include <pthread.h>
pthread_create - create a new thread
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);스레드를 만들고 문제없이 생성되었을 때 특정 함수를 실행한다.
첫 번째 인자는 스레드를 담을 주소이며 미리 pthread_t를 선언한 다음 주소를 넣어주면 된다.
두 번째 인자는 스레드 속성으로 이번 과제에서 사용하지 않으므로 NULL을 넣어준다.
세 번째 인자는 스레드에서 동작할 함수의 포인터이다.
네 번째 인자는 세 번째 인자에서 불러온 함수 포인터에서 사용할 인자이다.
반환 값은 성공 시 0 실패 시 0이 아닌 다른 숫자
pthread_join - wait for thread termination
int pthread_join(pthread_t thread, void **value_ptr);특정 스레드의 작업이 종료될때까지 기다린 다음 해당 쓰레드의 자원을 반납한다.
첫 번째 매개변수는 기다릴 스레드의 id, 두 번째는 쓰레드의 리턴값이 된다. 두번째 값은 사용하지 않을 거라면 NULL을 넣어주면 된다.
반환 값은 성공 시 0 실패 시 0이 아닌 다른 숫자
pthread_detach - detach a thread
int pthread_detach(pthread_t thread);특정 스레드를 즉시 종료시킨다.
매개변수는 중지할 스레드의 id이며 join과 detach를 잘 구분해서 사용해야 한다. 자세한 내용은 https://probe29.tistory.com/48 참조
반환 값은 성공 시 0 실패 시 0이 아닌 다른 숫자.
pthread_mutex_init - create a mutex
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);뮤텍스를 만드는 함수
첫 번째 인자는 뮤텍스의 주소, 두번째 값으로는 뮤텍스의 속성을 넣는데 이번 과제에서 속성은 사용하지 않는다.(따라서 NULL)
반환 값은 성공 시 0 실패 시 0이 아닌 다른 숫자
pthread_mutex_destroy - free resources allocated for a mutex
int pthread_mutex_destroy(pthread_mutex_t *mutex);뮤텍스에 할당한 메모리를 해제하는 함수.
인자는 해제할 뮤텍스의 주소이며, 해제할 뮤텍스는 반드시 unlock상태여야 한다(lock 된 상태의 뮤텍스에 대한 해제는 UB)
반환 값은 성공 시 0 실패 시 0이 아닌 다른 숫자
pthread_mutex_lock - lock a mutex
int pthread_mutex_lock(pthread_mutex_t *mutex);뮤텍스를 잠가서 다른 스레드에서 해당 뮤텍스에 접근할 수 없도록 한다.
인자는 잠글 뮤텍스의 주소.
반환 값은 성공 시 0 실패 시 0이 아닌 다른 숫자
pthread_mutex_unlock - unlock a mutex
int pthread_mutex_unlock(pthread_mutex_t *mutex);잠근 뮤텍스를 해제한다. 잠그지 않은 스레드 외 다른 스레드에서 해제 시 UB이다.
인자는 해제할 뮤텍스의 주소
반환 값은 성공 시 0 실패 시 0이 아닌 다른 숫자
데드락
데드락에 대한 대책은 예방, 회피, 탐지와 회복, 무시가 있다.
데드락의 조건
- 상호 배제 ( mutual exclusion ) : 자원에 대한 배타적 통제권
- 점유 대기( hold and wait ) : 할당된 자원을 점유한 상태로 다른 자원을 대기
- 비선점 ( no preemtion ) : 자원이 점유 해제되기 전에 선점할 수 없음
- 순환 대기 ( circular wait ) : 객체가 필요한 다음 자원을 다음 객체가 점유
예방은 이 4가지 조건중 하나 이상을 비틀어서 데드락을 피하는 방법이다. 다만 예방은 효용에 비해 자원을 지나치게 많이 사용한다(데드락은 드물게 발생할 텐데, 확인하는 작업은 매번 포함되므로)
회피는 데드락이 발생하는 환경을 확인한 후에 해당 환경을 피하는 방식이다. 이 과제에서는 짝수번호 철학자와 홀수번호 철학자가 번갈아가며 밥을 먹는 것으로 구현한다.
탐지와 회복은 데드락이 발생하였는지를 확인하고 그것을 푸는 알고리즘을 코드에 포함하는 방식이며, 무시는 데드락을 해제하지 않는 방식이다.
뮤텍스
스레드는 코드 영역과 데이터 영역을 다른 스레드와 공유한다. 따라서 데이터 영역의 내용을 여럿이 동시에 사용할 수 있는데, 같은 포크를 여러 명이 잡을 수 없어야 하므로 한 번에 한 명만 포크를 잡을 수 있게 뮤텍스로 포크를 보호해야 한다.
인자 처리 및 변수 초기화
int main(int argc, char *argv[])
{
t_arg arg;
t_philo *philo;
int errno;
if (argc != 5 && argc != 6)
return (print_error("error argc", 3));
// argc는 무조건 5개 아니면 6개이므로 에러 처리
memset(&arg, 0, sizeof(t_arg));
errno = ft_arg_init(&arg, argc, argv);
if (errno)
return (print_error("error arg init", errno));
// argv를 구조체에 저장하고 필요한 변수들을 할당하고 초기화해준다
errno = ft_philo_init(&philo, &arg);
if (errno)
return (print_error("error philo init", errno));
// 철학자별로 들어갈 변수들을 초기화한다.
errno = ft_philo_start(&arg, philo);
if (errno)
return (print_error("error philo start", errno));
// 철학자를 시작하고 종료될때까지 동작한다
return (0);
}메인에서는 함수를 하나씩 실행하면서 에러 상황 시 에러 문 출력과 함께 프로그램을 종료한다
int ft_arg_init_mutex(t_arg *arg)
{
int i;
if (pthread_mutex_init(&(arg->print), NULL))
return (1);
arg->forks = malloc(sizeof(pthread_mutex_t) * arg->philo_num);
if (!(arg->forks))
return (1);
i = 0;
// 철학자의 현재 상태 표시를 섞이게 나오면 안되므로 출력 권한에 뮤텍스 부여
while (i < arg->philo_num)
{
if (pthread_mutex_init(&(arg->forks[i]), NULL))
return (1);
i++;
}
return (0);
}
int ft_arg_init(t_arg *arg, int argc, char *argv[])
{
arg->philo_num = ft_atoi(argv[1]);
arg->time_to_die = ft_atoi(argv[2]);
arg->time_to_eat = ft_atoi(argv[3]);
arg->time_to_sleep = ft_atoi(argv[4]);
arg->start_time = ft_get_time();
if (arg->philo_num <= 0 || arg->time_to_die < 0 || arg->time_to_eat < 0
|| arg->time_to_sleep < 0)
{
return (5);
}
if (argc == 6)
{
arg->eat_times = ft_atoi(argv[5]);
if (arg->eat_times <= 0)
return (6);
}
if (ft_arg_init_mutex(arg))
return (1);
return (0);
}특별한 내용은 없고 인자를 가져와서 구조체에 넣어준다. 처음에는 함수 두 개였다가, memset으로 0으로 초기화하는 걸 줄여서 한 함수에 담았는데, 이후에 함수 에러 처리 한 줄씩 추가하다 보니 다시 함수 두 개로 나눠야 했다.
시작 시간을 철학자 스레드를 만들기 전에 지정해줘야한다. 철학자 시작 이후에 넣으면 쓰레드를 만드는 데에도 시간이 소요되므로 많은 철학자를 만들 때에 출력 순서가 뒤죽박죽인 거처럼 보이는(실제로는 순서가 맞는데 시간이 다르게 나오는) 현상이 발생한다.
int ft_philo_init(t_philo **philo, t_arg *arg)
{
int i;
i = 0;
*philo = malloc(sizeof(t_philo) * arg->philo_num);
if (!(philo))
return (1);
while (i < arg->philo_num)
{
(*philo)[i].arg = arg;
(*philo)[i].id = i;
(*philo)[i].left = i;
(*philo)[i].right = (i + 1) % arg->philo_num;
// 원형 테이블이므로 오른쪽 포크는 이렇게 처리.
(*philo)[i].last_eat_time = ft_get_time();
(*philo)[i].eat_count = 0;
i++;
}
return (0);
}철학자에서 사용할 구조체를 초기화하면서 앞에서 만든 구조체의 주소도 넣어준다.
원형 테이블이므로 오른쪽 포크 뒤에 “% arg->philo_num” 를 붙여줘야 함 (ex. 철학자가 5명일 때 philo [4]의 오른쪽 포크는 5가 아닌 0)
철학자 동작 구현
void ft_pass_time(long long wait_time, t_arg *arg)
{
long long start;
long long now;
start = ft_get_time();
while (!(arg->finish))
{
now = ft_get_time();
if ((now - start) >= wait_time)
break ;
usleep(10);
}
}
int ft_philo_printf(t_arg *arg, int id, char *msg)
{
long long now;
now = ft_get_time();
if (now == -1)
{
return (-1);
}
pthread_mutex_lock(&(arg->print));
if (!(arg->finish))
{
printf("%lld %d %s \n", now - arg->start_time, id + 1, msg);
}
pthread_mutex_unlock(&(arg->print));
return (0);
}
int ft_philo_action(t_arg *arg, t_philo *philo)
{
pthread_mutex_lock(&(arg->forks[philo->left]));
ft_philo_printf(arg, philo->id, "has taken a fork");
if (arg->philo_num != 1)
{
pthread_mutex_lock(&(arg->forks[philo->right]));
ft_philo_printf(arg, philo->id, "has taken a fork");
ft_philo_printf(arg, philo->id, "is eating");
philo->last_eat_time = ft_get_time();
philo->eat_count = philo->eat_count + 1;
ft_pass_time((long long)arg->time_to_eat, arg);
pthread_mutex_unlock(&(arg->forks[philo->right]));
}
pthread_mutex_unlock(&(arg->forks[philo->left]));
return (0);
}포크를 집고, 음식을 먹고, 포크를 내려놓는 과정까지 함수로 구현한다.
왼쪽 포크와 오른쪽 포크를 순서대로 집은 다음 음식을 먹고 조금이라도 빠르게 락을 해제하기 위해 오른쪽 포크부터 내려놓는다.
철학자가 한 명일 때는 어차피 포크도 하나여서 왼쪽 포크를 집으면 오른쪽 포크를 집을 수가 없기 때문에 해당 부분들은 예외처리를 해둔다.
출력 부분은 구조체에 출력 담당 뮤텍스를 하나 만들어서 서로 엉키지 않게 한다.
스레드 구현
void *ft_thread(void *argv)
{
t_arg *arg;
t_philo *philo;
philo = argv;
arg = philo->arg;
if (philo->id % 2)
usleep(1000);
while (!arg->finish)
{
ft_philo_action(arg, philo);
if (arg->eat_times == philo->eat_count)
{
arg->finished_eat++;
break ;
}
ft_philo_printf(arg, philo->id, "is sleeping");
ft_pass_time((long long)arg->time_to_sleep, arg);
ft_philo_printf(arg, philo->id, "is thinking");
}
return (0);
}
int ft_philo_start(t_arg *arg, t_philo *philo)
{
int i;
i = 0;
while (i < arg->philo_num)
{
philo[i].last_eat_time = ft_get_time();
if (pthread_create(&(philo[i].thread), NULL, ft_thread, &(philo[i])))
return (1);
i++;
}
ft_philo_check_finish(arg, philo);
i = 0;
while (i < arg->philo_num)
pthread_join(philo[i++].thread, NULL);
// 조인을 안하면 프로그램이 먼저 종료되서 쓰레드가 진행되지 않는다.
ft_free_thread(arg, philo);
return (0);
}철학자가 자리에 앉기 전에 밥을 한 끼씩 하고 앉았다고 가정하고 그 시간을 마지막에 밥 먹은 시간으로 지정해둔다.
그다음 철학자가 시작되면 홀수와 짝수를 다르게 usleep을 걸어준다. 짝수만 걸어도 큰 문제는 없다. 데드락을 회피하기 위해서 홀수와 짝수가 번갈아 가면서 밥을 먹게 하였다.
죽음(혹은 완료) 구현
void ft_philo_check_finish(t_arg *arg, t_philo *philo)
{
int i;
long long now;
while (!arg->finish)
{
if ((arg->eat_times != 0) && (arg->philo_num == arg->finished_eat))
{
arg->finish = 1;
break ;
}
i = 0;
while (i < arg->philo_num)
{
now = ft_get_time();
if ((now - philo[i].last_eat_time) >= arg->time_to_die)
{
ft_philo_printf(arg, i, "died");
arg->finish = 1;
break ;
}
i++;
}
}
}철학자가 먹는 횟수를 전부 채웠을 때와 철학자 중 누군가가 죽었을 때까지 반복문을 돌리면서 검사한다.
철학자가 먹는 횟수를 전부 채웠을 때에 바로 코드의 의미를 이해할 수 있게 일부러 break 도 넣고 arg->finish = 1 도 넣었는데 평가할 때 보니 왜 두 개가 같이 있냐는 질문을 두 번이나 받았다. 별로 의미는 없는 코드였다.
예외처리
코드를 작성한 이후에 알고 해결한 내용들은 따로 적었다. 위에서도 적은 내용들도 있다.
1. usleep 밀림 현상 해결
- usleep을 자는 시간이나 먹는 시간 그대로 입력하면 점점 시간이 밀리게 된다. 이유는 위에 usleep 함수에서 설명했고, 해결을 위해서 usleep 시간을 잘게 쪼갠다음 조건문을 걸어서 해결했다.
now = ft_get_time();
if ((now - start) >= wait_time)
break ;
usleep(10);
2. 철학자가 1명일 때 프로그램이 종료되지 않고 중단되는 현상
- 철학자가 1명이면 포크도 1개여서 왼손의 포크(뮤텍스)와 오른손의 포크가 동일한 포크여서 왼손으로 잡은 포크를 놓지 않는 데드락이 발생한다. 위에서 적은 것처럼 철학자가 1명일 때 포크를 집는 행동 이후의 행동을 안 하도록 처리해서 예외처리했다.
3. 출력 순서가 뒤죽박죽으로 나오는 현상
- 철학자가 시작하기 전에 현재 시간을 구조체에 저장해 두지 않고 철학자 안에서 시작하게 되면 기준이 되는 시작 시간이 다르게 되면서 순서대로 출력하지만 시간이 다르게 나오는 버그가 있다. 사실 이건 나는 모르고 지나쳤던 문제인데 다른 카뎃의 과제를 구경하다가 알게 되었다. 따라서 위 코드에는 이미 수정되어있다.
4. 에러처리 문제
- 과제에서 exit perror 등의 함수를 지원하지 않아서 에러를 처리하는게 난감했다. 뮤텍스 락에서 에러가 발생한다면 그걸 상위 스레드에서 알 방법이 없다보니 처리를 하지 못했다. 이건 고민해보면 해결할 수 있을것 같은데... 하면서도 해결하지 못하고 과제를 제출한게 아쉽다.
결론
이전의 과제들과는 다르게 명확하게 어떻게 해야 한다를 쉽게 전달하지 못한 글인 것 같아서 아쉽다. 사실 코드적인 부분은 그렇게 어렵지는 않은데, 왜 이렇게 해야 하는지를 전달하려고 하면 글이 너무 길어지고 중언부언해서 어느정도 쳐내고 나니 뭔가 좀 부족한 글이 된 것 같다.
아마도 내가 과제를 정말 공들여서 깊게 파서 공부하지 않아서 생긴 부작용인 것 같다. 내가 피상적으로 아는 내용을 설명하려니 설명도 피상적이 되거나 지나치게 복잡하게 되거나인 것 같다.
그래서 내가 참조한 글들의 링크를 마지막에 첨부하였다. 다른 카뎃들은 과제를 좀 더 깊게 이해하고 다른 카뎃에게 좀 더 쉽게 설명할 수 있게 되면 좋겠다.
레퍼런스
https://bigpel66.oopy.io/library/42/inner-circle/9
Philosophers
Subjects
bigpel66.oopy.io
https://velog.io/@meong9090/Philosophers-Philosophers과제-총-정리
[Philosophers] Philosophers과제 총 정리
Philosophers과제 총 정리
velog.io
https://42kchoi.tistory.com/301
42 Philosophers(철학자 문제) 필수지식 정리 - 1
Philosophers 필요한 변수: number_of_philosophers 철학자 수(+ 포크의 수) time_to_die 지난 번 식사로부터 식사를 마칠 때까지 남은 시간. time_to_eat 밥 먹는 데 걸리는 시간. 두 개의 포크를 사용해야 한다...
42kchoi.tistory.com
https://probe29.tistory.com/48
Pthread - create, exit, join, detach, mutex
#Pthread 리눅스에서 Thread를 생성하고 관리하는 함수 - thread 표준 API POSIX 스레드 또는 Pthread 라고 부른다. - Pthread API 저수준 API로 100 여개의 함수 제공 복잡하지만 유닉스 시스템 핵심 스..
probe29.tistory.com
https://nafuka11.github.io/philosophers-visualizer/
Philosophers visualizer
Very simple web visualizer for Philosophers
nafuka11.github.io
'프로그래밍' 카테고리의 다른 글
| [42서울] 넷프랙티스(netpractice). 놀랄 만큼 쉽고 믿기 힘들 만큼 재미있는 과제. (0) | 2022.06.27 |
|---|---|
| [42서울] 미니쉘(minishell) 파싱, 그 후회와 참회의 기록. (0) | 2022.06.19 |
| [42서울] pipex 심플 가이드 (2) | 2022.04.26 |
| [42 서울] so_long을 빠르게 끝내보자 (1) | 2022.04.01 |
| [42 서울] push_swap을 케이크처럼 쉽게 먹는 법 - 2 (0) | 2022.01.18 |
