운영체제 시간에 진행했던 식사하는 철학자 알고리즘에 대한 정리를 잘한 거 같아 벨로그에도 정리해보고자 했다 !
1. 주제
수업시간에 다룬 알고리즘 중에서 식사하는 철학자 문제 (Dining Philosophers Problem)를 택했다.
우선 이 문제에 대해 간단히 설명하고자 한다.
철학자가 원형 식탁에서 식사를 하려할 때, 각 철학자 사이에는 포크가 하나씩 놓여 있다. 따라서 철학자의 인원 수만큼 존재하고, 식사 하기 위해선 철학자 양 옆의 포크를 잡아야 식사를 할 수 있다. 각 철학자는 먹기, 생각하기, 잠자기의 3가지 상태를 가질 수 있으며 먹기 뒤엔 잠자기가 진행되며 일정시간 뒤 생각하기 상태로 바뀌며 먹기를 기다린다.
이 알고리즘의 문제점:
- 철학자가 식사 진행을 위해 포크를 하나씩 동시에 집는다고 했을 때 2개의 포크를 모두 잡지 못해 Deadlock(교착상태)에 빠지는 모습이 생길 수 있다.
해결방법:
- 포크 수보다 적은 수의 철학자를 유지
- 양쪽 포크 모두 잡기가 가능할 때 두 포크 동시에 잡기
i번째 철학자를 짝, 홀수로 구분하기
홀수 인덱스 -> i번 포크, 짝수 인덱스 -> i+1번 포크를 집기
2. 구현된 프로그램
1) 프로그램의 구조
includes 폴더 (헤더파일 저장)
(1) philo.h
src 폴더
(1) main.c
- (2) philo.c
- (3) action.c
- (4) util.c
철학자 5명일 때, thread와 mutex 구조도
- 메인스레드에서 파생된 철학자 스레드들은 같은 뮤텍스를 공유하고 있다.
1. main.c
int main(int ac, char* av[])
{
t_info info;
memset(&info, 0, sizeof(info));
if (ac != 5 && ac != 6)
return (print_err("ERROR: wrong argc"));
if (init_philo(ac, av, &info))
return (1);
if (start_philo(&info))
return (1);
return (0);
}
1- 1) init philo
int init_philo(int ac, char* av[], t_info* info)
{
if (check_args(ac, av))
return (print_err("ERROR: wrong argc"));
else
{
if (init_philo_info(ac, av, info))
return (1);
if (init_philo_mutex(info))
return (1);
if (init_philo_philos(info))
return (1);
}
return (0);
}1) check_args 호출 ( util. c- > check args 에서 용도 설명)
2) init_philo_info
3) init_philo_mutex
4) init_philo_philos
1-2) init_philo_info
int init_philo_info(int ac, char* av[], t_info* info)
{
info->num_of_philo = ft_atoi(av[1]);
info->time_to_die = (uint64_t)ft_atoi(av[2]);
info->time_to_eat = (uint64_t)ft_atoi(av[3]);
info->time_to_sleep = (uint64_t)ft_atoi(av[4]);
info->num_of_must_eat = -1;
if (ac == 6)
info->num_of_must_eat = ft_atoi(av[5]);
return (0);
}1) 각각의 argv 값들을 int 형태로 변환
- 만약에 optional인 argv[6]이 들어온 경우에도 변환해준다는 예외처리
2) 최소 먹어야할 횟수 초기값 : -1
3) ft_atoi 호출 (util.c -> ft_atoi 에서 용도 설명)
1-3) init_philo_mutex
int init_philo_mutex(t_info* info)
{
int i;
info->forks = (pthread_mutex_t*)malloc \
(sizeof(pthread_mutex_t) * info->num_of_philo);
if (info->forks == NULL)
return (print_err("ERROR: memory allocation failed"));
i = -1;
while (++i < info->num_of_philo)
pthread_mutex_init(&info->forks[i], NULL);
pthread_mutex_init(&info->moniter, NULL);
pthread_mutex_init(&info->print, NULL);
return (0);
}
철학자 사이 한 개씩 포크가 존재 = 철학자 수만큼 포크 존재
1) numof philo 변수 사이즈 만큼 mutex 배열 생성
2) NULL 처리 => 동적할당 처리 검사
3) pthread_mutex_init
mutex 특징을 정의 => 기본 mutex 사용시, null을 작성함
필요한 mutex들을 모두 초기화 => forks, moniter, print
1-4) init_philo_philos
int init_philo(int ac, char* av[], t_info* info)
{
if (check_args(ac, av))
return (print_err("ERROR: wrong argc"));
else
{
if (init_philo_info(ac, av, info))
return (1);
if (init_philo_mutex(info))
return (1);
if (init_philo_philos(info))
return (1);
}
return (0);
}1) t_philo : 철학자 한명을 나타내는 구조체
=> num of philo 만큼 t_philo 배열 생성
2) NULL 처리-> 동적할당 검사
3) 철학자 구분을 위해 ID 용도로 번호를 부여,
0이 아닌 1번 철학자부터로 번호를 매기기 위해 i+1로 값을 부여함
4) left, right => 포크 번호에 해당, philos[i]의 왼쪽 포크, 오른쪽 포크
5) info->philos[i].info = info; <- t_info 전역변수처럼 사용하기 위해 선언
2. philo.c
2-1) start_philo
int start_philo(t_info* info)
{
int i;
info->time_to_start = get_time();
i = -1;
while (++i < info->num_of_philo)
{
info->philos[i].last_eat = info->time_to_start;
info->philos[i].last_sleep = info->time_to_start;
info->philos[i].num_of_eat = 0;
if (pthread_create(&info->philos[i].thread, NULL,
do_philo, &info->philos[i]))
return (print_err("ERROR: create thread failed"));
}
check_philo_done(info);
free_philo(info);
return (0);
}1) info->time_to_start => 현재 시간부터 시작함, 메인 스레드만 작동 중
2) num_of_philo 만큼 스레드를 생성
3) 마지막으로 먹은 시간, 마지막 잔 시간, optional을 위한 먹은 횟수 초기화
4) pthread_create 로 philos수만큼 스레드 생성
- 생성할 스레드 변수의 주소, 특성 설정
(기본스레드는 NULL , do_philo (어느 함수로 가야할지를 알려주는 인자), do_philo에 넣어줘야 할 인자(3번째 인자에게 넘겨줄 인자)) 형태로 넘김
- 3, 4번째 인자는 void pointer이기에 구조체 t_philo를 void로 타입 캐스팅 필요
5) 이후 메인 스레드는 check_philo_done 실행,
철학자들의 스레드들은 do_philo 실행
2-2) check_philo_done
void check_philo_done(t_info* info)
{
int i;
while (!info->done)
{
i = -1;
while (++i < info->num_of_philo && !info->dead)
{
pthread_mutex_lock(&info->moniter);
if (get_time() - info->philos[i].last_eat > info->time_to_die)
{
print_state(&info->philos[i],
get_time() - info->time_to_start, "died");
info->dead = 1;
}
pthread_mutex_unlock(&info->moniter);
}
if (info->dead)
break;
i = 0;
while (info->num_of_must_eat != -1 && i < info->num_of_philo
&& info->philos[i].num_of_eat >= info->num_of_must_eat)
i++;
if (info->num_of_philo == i)
info->done = 1;
}
}1) info->done = 1로 변하면 작업이 끝난 것이므로 이것이 아닐 때까지 반복문 실행
2) 철학자 한 명씩 확인함
3) 동시에 죽지 않았을 경우, 철학자가 죽었는지 확인하는 값인 dead에 접근하면 프로그램에 문제가 생기기 때문에 이것을 critical section으로 설정
4) 따라서, 접근 전에 moniter_mutex_lock 하고, 체크가 다 끝나면 unlock하는 방식으로 작동. 이때, 다른 스레드들은 lock된 상태이기 때문에 접근 불가
-> 현재시간 - 마지막으로 먹은 시간 => 얼마만큼의 시간이 지났는지 확인이 가능
-> time_to_die만큼 크면 먹어야 할 시간이 지난 거기 때문에 philo가 죽었다는 것을 확인 할 수 있음, dead = 1 로 바꾸거나 unlock하게 됨.
-> 다 먹었거나 죽기 전까지 메인 스레드는 무한 루프 작동 중
5) 계속 철학자 모니터 중 안 죽었으면 혹은 6번째 인자(optional)가 안 들어오면
초기값이 -1 and philo 1개씩 and
지금 보고 있는 i번째 철학자가 먹은 횟수 >= 최소 먹어야 하는 횟수
=> 다 먹었는지 확인
6) 최종적으로 벗어나면(num_of_philo가 방금 검사한 i와 같으면) 메인 스레드는 info_done을 1로 변경해서 무한 루프를 탈출
2-3) free_philo
void free_philo(t_info* info)
{
int i;
i = -1;
if (info->num_of_philo == 1)
pthread_detach(info->philos[0].thread);
while (++i < info->num_of_philo)
pthread_join(info->philos[i].thread, NULL);
free(info->philos);
i = -1;
while (++i < info->num_of_philo)
pthread_mutex_destroy(&info->forks[i]);
free(info->forks);
pthread_mutex_destroy(&info->moniter);
pthread_mutex_destroy(&info->print);
}만약 philo가 한명인 경우, 강제 종료가 필요
–> pthread_detach, philo에 관계없이 메인 스레드를 종료
2) 만약 philo가 한명이 아닌 경우, 반복해서 pthread_join
-> 메인스레드가 다른 스레드들 종료
3) philos => free
4) 포크 삭제도 필요 => destroy
포크를 free 한 뒤에 moniter_mutex, print_mutex => destroy
2-4) do_philo
void* do_philo(void* void_philo)
{
t_philo* philo;
philo = (t_philo*)void_philo;
if (philo->id % 2 == 0)
usleep(philo->info->time_to_eat * 1000);
while (!philo->info->dead)
{
take_forks(philo);
eating(philo);
if (philo->info->done)
break;
sleeping_and_thinking(philo);
}
return (0);
}1) void pointer 자료형이기 때문에 t_philo로 타입 캐스팅
2) 홀수 철학자들을 먼저 먹게 해주고 싶은 경우 -> usleep
3) 짝수 철학자들은 홀수 철학자가 먹는 시간 동안 쉼
4) 만약 한 명이라도 안 죽었으면 philo는 take_forks 하고 eating
5) 모니터링에서 다 끝났다고 done할 때까지 반복한 뒤 break하고
6) 0을 return
3. action.c
3-1) take_forks
void take_forks(t_philo* philo)
{
if (philo->id % 2 == 0)
pthread_mutex_lock(&philo->info->forks[philo->left]);
else
pthread_mutex_lock(&philo->info->forks[philo->right]);
print_state(philo,
get_time() - philo->info->time_to_start, "has taken a fork");
if (philo->id % 2 == 0)
pthread_mutex_lock(&philo->info->forks[philo->right]);
else
pthread_mutex_lock(&philo->info->forks[philo->left]);
print_state(philo,
get_time() - philo->info->time_to_start, "has taken a fork");
}1) 철학자가 짝수일 경우 왼쪽 오른쪽 순으로 fork를 lock
철학자가 홀수일 경우 오른쪽 왼쪽 순으로 fork를 lock
2) print_state (util.c -> print_state 에서 설명)
3) print_mutex_lock이 필요한 이유
- 글자를 한번에 프린트하게 하면 안되기 때문. 한 사람씩 상태를 프린트 할 수 있게 lock을 거는 것이다. 프린트가 완료되면 unlock한다.
3-2) eating
void eating(t_philo* philo)
{
pthread_mutex_lock(&philo->info->moniter);
philo->last_eat = get_time();
print_state(philo,
philo->last_eat - philo->info->time_to_start, "is eating");
pthread_mutex_unlock(&philo->info->moniter);
while (get_time() < philo->last_eat + philo->info->time_to_eat)
;
philo->num_of_eat++;
pthread_mutex_unlock(&philo->info->forks[philo->left]);
pthread_mutex_unlock(&philo->info->forks[philo->right]);
}1) 중요한 변수들을 바꾸는 구간
2) 먹었는지 안 먹었는지 체크한 다음 모니터에 lock을 걺.
3) 마지막으로 먹은 시간을 체크하고 현재 시간을 알고 있어야 함.
4) print_state : 마지막으로 먹은 시간 -시작한 시간
현재 먹고 있다는 것 알려준다.
5) 모니터를 unlock
6) 현재시간 >= 마지막으로 먹기 시작한 시간 + 먹은 시간
=> 다 먹었다는 뜻, 계속하여 get_time을 받아야 함
7) Philo가 num_of_eat 증가
8) 포크를 unlock
3-3) sleeping_and_thinking
void sleeping_and_thinking(t_philo* philo)
{
philo->last_sleep = get_time();
print_state(philo,
philo->last_sleep - philo->info->time_to_start, "is sleeping");
while (get_time() < philo->last_sleep + philo->info->time_to_sleep)
;
print_state(philo,
get_time() - philo->info->time_to_start, "is thinking");
usleep(200);
}1) 마지막으로 잔 시간을 get_time으로 받아옴
2) “is sleeping”이라고 print_state 출력문 넘김
3) 시간을 보내고 print_state에 "is thinking＂ 출력문 넘김
4) Deadlock을 방지하기 위해 usleep(200)
-> 적어도 바로 lock 되어있는 mutex(포크)에 접근을 막기 위해서 이다.
4. util.c
4-1) ft_atoi
int ft_atoi(char* str)
{
long long num;
int sign;
num = 0;
sign = 1;
while ((*str >= 9 && *str <= 13) || *str == 32)
str++;
if (*str == '+' || *str == '-')
{
if (*str == '-')
sign *= -1;
str++;
}
while (*str >= '0' && *str <= '9')
num = num * 10 + (*(str++) - '0');
return (num * sign);
}기존의 atoi 함수 기능을 수행하되,
음수가 아닌 양수 값만 받아 string to int를 실행
4-2) check_args
int check_args(int ac, char* av[])
{
int i;
int j;
i = 0;
while (++i < ac)
{
j = -1;
while (av[i][++j])
if (av[i][j] < '0' || av[i][j] > '9')
return (1);
}
return (0);
}main에서는 args의 개수가 정확한지만 확인
argv가 number 형태로 잘 들어왔는지 확인하는 함수
숫자가 아닌 경우 1을 반환
check_args에서 “ERROR: wrong args” 출력
4-3) print_err
int print_err(char* err)
{
printf("%s\n", err);
return (1);
}에러일 경우 출력
1을 반환
4-4) get_time
uint64_t get_time(void)
{
struct timeval curr;
gettimeofday(&curr, NULL);
return ((curr.tv_sec * 1000) + (curr.tv_usec / 1000));
}timeval
gettimeofday (sys/time.h 라이브러리에 존재)
-> timeval을 받아올 변수를 주소를 넘겨주고,
null을 쓰면 현재 시간을 받아온다.
두개의 변수로 이루어져 있음 (초단위, 마이크로초단위) : 현재 시간을 마이크로 초로 표현 후 반환한다.
4-5) print_state
void print_state(t_philo* philo, uint64_t time, char* state)
{
pthread_mutex_lock(&philo->info->print);
if (!philo->info->dead)
printf("%lld\t%d\t%s\n", time, philo->id, state);
pthread_mutex_unlock(&philo->info->print);
}print_mutex_lock 필요한 이유: 글자를 한번에 프린트하게 하면 안되기 때문
한 사람씩 상태를 프린트 할 수 있게 lock을 거는 것, 프린트가 완료되면 unlock
4. 프로그램 결과
