재미있게 했던 과제인 Philosophers 과제에 대해 기제하고자 합니다.
근데 과제 끝낸지 4개월 됨; 그치만 저 보너스도 했어용
- 서브젝트 한글 번역본
https://github.com/42seoul-translation/subject_ko/blob/master/philosophers/philosophers.ko.md
서론
- 이번학기에 쓰레드 배우면서 뮤텍스랑 세마포어를 보니 반가워서
- 보너스에 대한 지문이 별로 없어서
- 다른 분들도 보너스를 하시길 바라며 !
Dining philosopher problem
과제 해결을 위해 꼭 알아야하는 내용들!
- Thread
프로세스 내에서 작업을 실행하는
주체
두개 이상의 쓰레드를 가진 프로세스 = 멀티 쓰레드 프로세스 (multi-threaded process)
프로세스는 메모리 공간을 할당받아 실행되나, 쓰레드는 한 프로세스 안에서 실행되며 쓰레드끼리같은 힙 공간을 공유함
-
Deadlock (교착상태)
멀티 쓰레드 프로세스에서
동일한 자원을 여러곳에서 동시에 접근 할 때, 두개의 쓰레드가 서로의 락 해제를 무한정 기다리는 상황
Deadlock 발생 조건 4가지중, 하나라도 충족하지 않으면 데드락이 발생하지 않음! -> 우리는 deadlock을 해결하기위해 mutext와 semaphore를 이용할 것. -
Mutex & Semaphore
뮤텍스의 접근을 lock, unlock으로 관리 =>
하나의 쓰레드만 접근
Semaphore는접근할 수 있는 수를 지정하여 여러 쓰레드의 접근이 가능
멘데토리 : mutext 이용, 보너스 : semaphore 이용 -
Context Switching (컨텍스트 스위칭)
여러개의 프로세스가 실행되고 있을 때, 기존에 실행되던 프로세스를 중단하고 다른 프로세스를 실행하는 것.
프로세스를 예시로 들었지만, 실제로 Context가 포괄하는 범위는 넓어용
왜 필요해요 ? : 철학자 쓰레드가 200명정도 된다고 가정했을때, 컨텍스트 스위칭을 발생시켜주어 시간 지연을 최소화합니다. 안 해주면 시간이 밀려서 원래 죽지않아야 할 철학자도 죽습니다.
Mandatory
로직
- 입력 파싱
- 철학자들이 각각의 쓰레드에서 활동하게 함
- 메인 쓰레드에서 철학자들의 종료 조건을 검사
0. 구조
입력 인자를 저장하는 구조체와 각 철학자들이 하나씩 가지고있는 구조체
각각의 철학자들은 모두 입력 구조체의 인자들을 참조 할 수 있음.
typedef struct s_arg
{
int philo_num; // 철학자 수
int life_time; // 철학자 생명 시간
int eat_time; // 식사 소요 시간
int sleep_time; // 수면 소요 시간
int eat_num; // 식사 횟수
/* pthread_mutex_t 무더기들 중략 */
int monitor; // 종료 flag
} t_arg;
typedef struct s_philo
{
int id; // 철학자 넘버
int eat_count; // 철학자 식사 횟수
int left; // 왼쪽 포크 넘버
int right; // 오른쪽 포크 넘버
long last_eat; // 마지막 식사 시간
long last_time; // 쓰레드의 시작시간 (작명센스 ㅈㅅ)
pthread_t thread; // 쓰레드 ID
t_arg *arg; // 입력 인자 값
} t_philo;1. 파싱
별 거 없이 argv를 변환하여 넣어준다.
철학자의 식사횟수가 입력으로 들어오는 경우와 들어오지 않는 경우를 분리해주어야한다. 평가를 다녀보니 처리를 따로 해주지않아 쓰레기값이 들어오는 경우들이 있더라
int init_argv(t_arg *arg, int argc, char **argv)
{
arg->philo_num = ft_atoi(argv[1]);
arg->life_time = ft_atoi(argv[2]);
arg->eat_time = ft_atoi(argv[3]);
arg->sleep_time = ft_atoi(argv[4]);
arg->monitor = 0;
if (arg->philo_num <= 0 || arg->life_time < 0 || \
arg->eat_time < 0 || arg->sleep_time < 0)
return (1);
if (argc == 6)
{
arg->eat_num = ft_atoi(argv[5]);
if (arg->eat_num <= 0)
return (1);
}
else
arg->eat_num = 0;
return (0);
}마찬가지로 각각의 철학자들도 초기화 해주어야한다. 설명이 필요없을 것 같아 줄인다.
int init_philo(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].id = i + 1;
(*philo)[i].eat_count = 0;
(*philo)[i].left = i;
(*philo)[i].right = (i + 1) % arg->philo_num;
(*philo)[i].last_eat = 0;
(*philo)[i].last_time = 0;
(*philo)[i].arg = arg;
i++;
}
return (0);
}2. 뮤텍스
내가 선언한 뮤텍스들
pthread_mutex_t *fork;
pthread_mutex_t print;
pthread_mutex_t mutex_monitor;
pthread_mutex_t mutex_eat_cnt;
pthread_mutex_t mutex_last_eat;아래로는 사용할 뮤텍스 함수들
//뮤텍스 생성 함수, 성공하면 0 리턴
int pthread_mutex_init(pthread_mutex_t * mutex, const pthread_mutex_attr *attr);
// mutex : 뮤텍스 객체
// attr : 뮤텍스 속성, 객체의 주소, NULL (우리는 NULL)
// 뮤텍스 잠금, 잠금해제 함수, 성공하면 0 리턴
int pthread_mutex_lock(pthread_mutex_t *mutex); //사용중
int pthread_mutex_unlock(pthread_mutex_t *mutex); //사용 가능 상태
// mutex : 뮤텍스 객체
//뮤텍스 해제 함수, 성공하면 0 리턴
int pthread_mutex_destroy(pthread_mutex_t *mutex);
// mutex : 뮤텍스 객체그래서 어떻게 쓰냐고요?
우선 먼저 뮤텍스를 생성해주자. 귀찮으니 포크 뮤텍스 할당하는것만 올린다
arg->fork = malloc(sizeof(pthread_mutex_t) * arg->philo_num);
if (!arg->fork)
return (1);
while (i < arg->philo_num)
{
if (pthread_mutex_init(&(arg->fork[i]), NULL) == -1)
return (1);
i++;
}
이 뮤텍스를 어디에 쓰느냐? 동시에 접근 할 것 같은 변수 앞뒤로 써주면 된다. 한번에 한 쓰레드만 변수에 접근 권한을 주어 데드락을 막는것이다.
3. 쓰레드
사용하는 함수
#include <pthread.h>
// 쓰레드 생성 함수
int pthread_create(pthread_t * thread, pthread_attr_t *attr, void * (*start_routine)(void *), void * arg);
// thread : thread ID (thread의 주소)
// attr : thread의 속성을 저장하는 구조체 (NULL로 셋팅)
// start_routine : thread와 함께 호출되는 함수 포인터 (thread가 실행하는 함수)
// arg : start_routine에 전달되는 매개변수 (없으면 NULL)
// 쓰레드의 종료를 기다리는 함수, 성공시 0 리턴
int pthread_join(pthread_t th, void **thread_return);
// thread : thread ID
// retval : thread가 종료하면서 반환하는 값에 접근할 수 있는 더블 포인터main process는 thread의 종료를 기다려주지않고 종료되기때문에, 메인 프로세스에서 thread의 종료를 pthread_join를 이용하여 기다려 줄 것이다.
while (i < arg->philo_num)
{
pthread_mutex_lock(&philo->arg->mutex_last_eat);
philo[i].last_eat = get_time();
pthread_mutex_unlock(&philo->arg->mutex_last_eat);
philo[i].last_time = get_time();
if (pthread_create(&(philo[i].thread), NULL, thread_f, &philo[i]))
return (1);
i++;
}나는 이런식으로 쓰레드를 생성할 수 있게 해주었다.
지금보니 참 거지같은 코드다. 실제로 200명 이상 돌리면 시작시간이 밀리는 경우가 발생한다. 뮤텍스 하나를 더 사용하여 동시에 시작할 수 있도록 해줄 걸 그랬다.
4. 먹고 자고 생각하는 철학자들
진짜 개그지같은 코드지만. 철학자 쓰레드의 함수다.
void *thread_f(void *data)
{
t_philo *philo;
philo = data;
if (philo->id % 2 == 0)
usleep(100);
while (!checking(philo->arg)) // 죽었는지 살았는지 체크
{
if (get_fork(philo)) //포크 잡다 죽었으면 종료
break ;
if (checking(philo->arg))
{
pthread_mutex_unlock(&(philo->arg->fork[philo->left]));
pthread_mutex_unlock(&(philo->arg->fork[philo->right]));
break ;
}
philo_eating(philo); // 식사
if (checking(philo->arg)) // 다 먹었는데 누구 죽었음 종료
break ;
philo_printf(philo, philo->id, "is sleeping");
ft_usleep(philo->arg->sleep_time);
if (checking(philo->arg)) // 자고 일났는데 누구 죽었음 종료
break ;
philo_printf(philo, philo->id, "is thinking");
}
return (0);
}과하다. 근데 데이터 레이스를 잡다보니 이렇게 되었다 머 어쩌겠어요
아래는 포크 잡는 함수. 1명일때 예외처리 해놓은 부분때문에 작성함
int get_fork(t_philo *philo)
{
if (philo->arg->philo_num == 1) //한명일 때 예외처리
{
pthread_mutex_lock(&(philo->arg->fork[philo->left]));
philo_printf(philo, philo->id, "has taken a fork");
pthread_mutex_unlock(&(philo->arg->fork[philo->left]));
return (1);
}
pthread_mutex_lock(&(philo->arg->fork[philo->left]));
philo_printf(philo, philo->id, "has taken a fork");
pthread_mutex_lock(&(philo->arg->fork[philo->right]));
philo_printf(philo, philo->id, "has taken a fork");
return (0);
}오잉 잠깐. 여기서 philo_eating함수 보기전에 우리는 데이터 레이스에 대해 알아야해요
5. 데이터 레이스
여러 쓰레드/프로세스가 공유자원에 동시에 접근하려 할 때 일어납니다. 우리 같은 경우, 두 철학자가 동시에 포크에 접근하는 경우나, 모니터링 함수와 철학자 쓰레드에서 동시에 last_eat 변수에 접근하는 경우를 예시로 들 수 있어요.
어떻게 막아용 ??
어떡하긴여 뮤텍스로 잘 막아줘야조 ^^
이팅 함수로 예시를 들어보겠습니다
void philo_eating(t_philo *philo)
{
philo_printf(philo, philo->id, "is eating");
pthread_mutex_lock(&philo->arg->mutex_last_eat);
philo->last_eat = get_time();
pthread_mutex_unlock(&philo->arg->mutex_last_eat);
ft_usleep(philo->arg->eat_time);
pthread_mutex_lock(&philo->arg->mutex_eat_cnt);
philo->eat_count++;
pthread_mutex_unlock(&philo->arg->mutex_eat_cnt);
pthread_mutex_unlock(&(philo->arg->fork[philo->left]));
pthread_mutex_unlock(&(philo->arg->fork[philo->right]));
}여기서 어떤 부분이냐
pthread_mutex_lock(&philo->arg->mutex_last_eat);
philo->last_eat = get_time();
pthread_mutex_unlock(&philo->arg->mutex_last_eat);last_eat에 write하기전에, 앞 뒤를 뮤텍스로 막아준 것이 보이는가? 왜냐하면 나는 이 last_eat변수를 모니터링 함수에서 철학자가 죽었는지 확인 할 때 사용한다. 동시에 접근하는 상황을 막기위해 만들어 주었다.
최근에 필로 평가가면 데이터레이스 검사를 안 해보셨거나 잘못 검사하신 분들이 많다. cflag에
-g -fsanitize=thread옵션을 추가하여 함께 컴파일 해보길 바란다.
왜냐면 딱 봐도 데이터 레이스 날 것 같은데 어 안났는데용? 사람들이 있따 ^^,,, 제대로 컴파일 안 했으먼서!! 아무튼 꼭 해라
그리고 데이터 레이스가 어디서 발생했는지 상세히 알려주니 에러를 읽어보면 쉽게 고칠 수 있다.
6. 시간
우리가 사용할 구조체
# include <sys/time.h>
struct timeval
{
long tv_sec; // 초
long tv_usec; // 마이크로초
}나는 모든 시간을 long 으로 바꾸어 가지게 해주었다. 종종 timeval구조체를 들고다니시기도 하더라. 머 똑같다.
long get_time(void)
{
struct timeval time;
long result;
gettimeofday(&time, NULL);
result = ((size_t)time.tv_sec * 1000) + ((size_t)time.tv_usec / 1000);
return (result);
}중요한 부분이다. 나는 ft_usleep 함수를 만들어 usleep()을 100usec씩 나누어서 해주었다 왜일까요 ?
void ft_usleep(long sleep_time)
{
long start;
start = get_time();
while (start + (sleep_time * 1) > get_time())
usleep(100);
}시작 전 컨텍스트 스위칭에 대해 언급하였다. 그 사유니까 다시 올라가서 읽으면 된다. 이 부분은 현진님께서 가르쳐주셨당 최고의 개발자~
7. 모니터링 함수
다 왔다 진짜 마지막!! 메인 함수에서 죽은 철학자들이 없는지 검사해주는 함수이다. 모니터링 함수는 (https://techdebt.tistory.com/32) 블로그를 참조했다. 그치만 저는 데이터레이스를 막기위해 더 더러운 함수가 되었어용
void monitoring(t_philo *philo, t_arg *arg)
{
int i;
long now_time;
while (!checking(arg))
{
if (arg->eat_num != 0 && check_eat_cnt(philo, arg) == arg->eat_num)
{
change_monitor(arg);
break ;
}
i = 0;
while (i < arg->philo_num)
{
now_time = get_time();
if ((now_time - last_eat(&philo[i])) > arg->life_time)
{
philo_printf(&philo[i], philo[i].id, "died");
change_monitor(arg);
break ;
}
i++;
}
usleep(10);
}
}여기서 checking(arg)함수만 잠깐 살펴보면,,
int checking(t_arg *arg)
{
pthread_mutex_lock(&arg->mutex_monitor);
if (arg->monitor == 1)
{
pthread_mutex_unlock(&arg->mutex_monitor);
return (1);
}
else
{
pthread_mutex_unlock(&arg->mutex_monitor);
return (0);
}
}머 데이터 레이스를 막으려고 모두 함수화 한 부분이다. 내 모든 뮤텍스들은 이렇게 일 하고있다. 개인의 코드마다 데이터 레이스 나는 부분은 다르니, 컴파일 해보시며 뮤텍스를 적절히 넣기를 바랍니다.
멘데토리는 이게 끝이다. 그치만 여기에 지치지마시고 보너스도 하셨음 좋겠다. 왜냐면 ㄹㅇ 학교에서 배운다. 보너스도 읽어줘라 왜냐면 내 보너스 뿌듯함 ㅇㅇ
Bonus
보너스 진짜 생각보다 안 어려움
그런데 멘데로티에서 가져올 코드는 거의 없습니다. 새로운 세미 과제를 하나 더 클리어 한다는 느낌으로 시작해야함 ^^ 하하하 가지마세요 ㅜ
시작하기전에 잠시만여
멘데토리에서는 철학자를 thread로 만들어주고 mutex를 이용하여 데드락을 막았다. 보너스에서는 철학자가 각각의 process여야하고, semaphore를 이용하여 데드락을 막아 줄 것이다.
0. 구조
typedef struct s_philo
{
int philo_num;
int life_time;
int eat_time;
int sleep_time;
int eat_num;
/* sem_t 세마포어들 생략 */
int id;
int eat_count;
long start_time;
pthread_t thread;
struct timeval time;
} t_philo;이 구조체 하나면 됨. 와~
1. 파싱
int init_argv(t_philo *philo, int argc, char **argv)위에서 쓴 init 함수만 그대로 가져다 쓸 수 있다. 나머진 다 다르다. 울지마세용 ㅜㅜ
2. 세마포어
제가 선언한 세마포어들입니다. 얘는 다 세마포어 포인터입니다. 개수가 몇개든
sem_t *fork;
sem_t *print;
sem_t *die;아래로 세마포어 함수
# include <semaphore.h>
// 세마포어 생성 함수
sem_t *sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
// name : 세마포어 이름
// oflag : 세마포어 특징 (O_RDWR, O_RDONLY, O_CREAT, O_EXCL)
// mode : 권한 정보 (chmod 777 그거)
// value : 세마포어 초기값 (ex. 포크가 5개 필요하면 5)
// 세마포어에 접근하고, 반납하는 함수, 성공하면 0 리턴
int sem_wait(sem_t *sem); // 접근 제한
int sem_post(sem_t *sem); // 반납
// sem : 세마포어 포인터
int sem_unlink(const char *name); // 세마포어 제거
int sem_close(sem_t *sem);v // 세마포어 종류헷갈리면 코드를 보며 이해해보자.
void init_sem(t_philo *philo)
{
sem_unlink("sem_fork"); // 겹치는 이름이 있을수 있으니 삭제
sem_unlink("sem_print");
sem_unlink("sem_die");
philo->fork = sem_open("sem_fork", O_CREAT, 0644, philo->philo_num);
philo->print = sem_open("sem_print", O_CREAT, 0644, 1);
philo->die = sem_open("sem_die", O_CREAT, 0644, 1);
}open의 인자를 한번 더 설명하자면, "sem_fork" 이름, O_CREAT 옵션, 접근권한 0644, philo->philo_num 개수만큼 변수값 설정.
O_CREAT옵션은 해당 이름의 객체가 존재하지 않을 경우, 새로운 객체를 생성하는 옵션이다.
포크는 철학자 수 만큼 필요하니 philo_num으로 설정해주었다.
이제 이 세마포어를 어떻게 쓰는지 알아보자.
int get_fork(t_philo *philo)
{
if (philo->philo_num == 1)
{
sem_wait(philo->fork);
philo_printf(philo, philo->id, "has taken a fork");
sem_wait(philo->fork);
return (1);
}
sem_wait(philo->fork);
philo_printf(philo, philo->id, "has taken a fork");
sem_wait(philo->fork);
philo_printf(philo, philo->id, "has taken a fork");
return (0);
}보면 알겠지만 멘데토리의 포크 함수와 똑같다. 다만 pthread_mutex_lock -> sem_wait 의 차이
사실뮤텍스와 세마포어의 가장 큰 차이는 repeat부분에서 나온다. 그 전에, fork()에 대해 알아보자.
3.fork()
이거 철학자들이 집는 포크 아니다. 자식 프로세스를 생성하는 함수에용
#include <unistd.h>
pid_t fork(void);
// 부모 프로세스의 리턴값 : 자식 프로세스의 pid
// 자식 프로세스의 리턴값 : 0minishell 해결한사람에게는 껌이겠고, 아닌 사람은 미칠 것이다. 본인은 미니셸을 해결한 후 필로 보너스를 했기에 ^^
간단히 설명하자면, 철학자 수 만큼 자식 프로세스를 생성 할 것이다.
자식 프로세스는 fork되는 순간, 부모 프로세스의 모든 정보를 복사한 독립적인 메모리 영역이 생성된다. 이후 각각의 프로세스는 독립적으로 실행된다.
int make_child(t_philo *philo)
{
pid_t *pid;
int i;
i = -1;
pid = (pid_t *)malloc(philo->philo_num * sizeof(pid_t));
if (!pid)
return (1);
philo->start_time = get_time();
while (++i < philo->philo_num)
{
pid[i] = fork(); // 자식 프로세스 생성
if (pid[i] < 0) // 에러 처리
return (1);
if (pid[i] == 0) // 자식이면
{
philo->id = i; //철학자 넘버 지정
break ;
}
}
if (pid[philo->id] == 0 && !child(philo)) //자식이면 자식 함수 실, norm맞춘다구 이모양!
return (1);
else
parents(philo, pid); //부모 함수 실행
free(pid);
return (0);
}대충 감이오나여?
이제 부모 프로세스가 실행하는 함수와 자식 프로세스가 실행하는 함수의 구현부를 볼 것.
int child(t_philo *philo)
{
philo->id += 1; // 0부터 시작해서 +1
philo->eat_count = 0; //횟수 초기화
gettimeofday(&philo->time, NULL);
if (pthread_create(&(philo->thread), NULL, monitoring, philo)) // 모니터링 쓰레드 생성
return (1);
repeat(philo); // 먹고 자고 생각하고 반복하는 함수
exit(0);
return (0);
}이거 좀 정신 나갈 것 같죠
여기서 부터 다른점!!!!!!!!
이렇게 생성된 자식 프로세스 = 한명의 철학자
이 모든 철학자 프로세스의 함수에서 반복적인 활동을 함
그럼 이 철학자들이 죽었는지 체크하는 역할은 누가하냐? 쓰레드가 함.
정리 : 자식 프로세스 하나 = 철학자 한명, 철학자 한명 당 모니터링 쓰레드 하나
철학자가 200명이면 메인프로세스 포함 201개, 쓰레드 200개가 생성됨 ㅋㅋㅋ 느려요 진짜 느림. 그치만 200명 안 죽고 돌아갑니다 우하하!!
그럼 철학자 한명이라도 죽으면 어떻게 동작하느냐? 이제 볼거임
void parents(t_philo *philo, pid_t *pid)
{
int status;
int i;
i = 0;
while (i < philo->philo_num)
{
waitpid(-1, &status, 0); // 자식 프로세스 기다림
if (status != 0) // 오류나면
{
i = 0;
while (i < philo->philo_num)
{
kill(pid[i], SIGKILL); // 전부 다주겨
i++;
}
}
i++;
}
}화긴? 중요한 부분은 waitpid(-1, &status, 0); 입니다.
임의의 자식의 종료를 기다림. 정상 종료된 철학자들의 수 (i)가 철학자 수 만큼 될 때까지 기다림.
그럼 오류는 언제 나느냐? 철학자가 한명이라도 죽었을때. 오잉 그건 어떻게 아나요? 모니터링 쓰레드에서 알아보아요
4. repeat 함수
모든 철학자 프로세스가 실행하는 함수.
void repeat(t_philo *philo)
{
if (philo->id % 2 == 0)
usleep(200);
while (1)
{
if (get_fork(philo))
break ;
philo_eating(philo);
if (philo->eat_num != 0 && philo->eat_count == philo->eat_num)
exit (0);
philo_printf(philo, philo->id, "is sleeping");
ft_usleep(philo->sleep_time);
philo_printf(philo, philo->id, "is thinking");
}
}멘데토리보다 훨씬 간단하다. 저기보면 exit(0)보이시나요? 밥 다 먹었으면 정상종료 (0) 하겠다는 뜻입니다. 그럼 비정상종료는 어떻게 하느냐?
5. 모니터링 쓰레드
훨씬 함수가 간단하고 많이 줄었다. 따로 더 구현할 함수도 없다.
void *monitoring(void *data)
{
t_philo *philo;
long now_time;
long last_time;
philo = data;
while (1)
{
now_time = get_time();
sem_wait(philo->die);
last_time = ((size_t)philo->time.tv_sec * 1000) + \
((size_t)philo->time.tv_usec / 1000);
if (now_time - last_time > philo->life_time)
{
philo_printf(philo, philo->id, "died");
exit(1);
}
sem_post(philo->die);
usleep(100);
}
}exit(1)로 비정상 종료
가 되면, 위에 있는 부모 프로세스에서 kill을 이용하여 모든 자식 프로세스를 강제종료한다. 와~ 끗. 간단하죠 ?
진심 보너스 별거 없음 마음만 먹으면 하루만에 뚝딱!! 가능하다구!!
하 근데 오ㅐ케 기냐
멘데토리는 정리하지 말걸
아무튼 제 점수 보고가세요 안녕
