들어가기에 앞서
-
philosophers(1)에서 언급한 스레드, 동기화, 임계 영역, 교착상태에 대해 개념 파악
-
CodeVault 유튜브 재생목록
Unix Threads in C영상 시청하는걸 강력추천!!! -
인자를 5개 또는 6개를 받습니다.
◦ number_of_philosophers: The number of philosophers and also the number
of forks.
◦ time_to_die (in milliseconds): If a philosopher didn’t start eating time_to_die
milliseconds since the beginning of their last meal or the beginning of the simulation, they die.
◦ time_to_eat (in milliseconds): The time it takes for a philosopher to eat.
During that time, they will need to hold two forks.
◦ time_to_sleep (in milliseconds): The time a philosopher will spend sleeping.
◦ number_of_times_each_philosopher_must_eat (optional argument): If all
philosophers have eaten at least number_of_times_each_philosopher_must_eat
times, the simulation stops. If not specified, the simulation stops when a
philosopher dies. -
식사하는 철학자 문제라고 불리는 운영체제에서는 유명한 문제입니다.
컴퓨터과학에서 동시성과 교착 상태를 설명하는 예시로, 여러 프로세스가 동시에 돌아갈 때 교착 상태가 나타나는 원인을 직관적으로 알 수 있습니다.
이전 포스트 philosophers(1)에서 작성한 임계 영역을 해결하기 위한 방법을 해당 프로젝트를 통해 풀어 설명하면,
상호 배제, 교착상태 방지(한정 대기), 진행 이라는 조건을 만족해야 합니다.
상호배제(Mutual Exclusion) : 한순간에 한 프로세스만 임계 영역에 진입할 수 있도록 제어합니다.
이를 위해 락(lock), 세마포어(Semaphore), 모니터(Monitor) 등의 도구를 사용할 수 있습니다.
=> 공유 자원에 mutex를 걸어 하나의 철학자(스레드)만 들어가게 합니다.
교착상태(Deadlock) 방지 : 교착상태는 두 개 이상의 프로세스가 서로 상대방이 점유한 자원을 기다리며 무한정 대기하는 상황을 말합니다.
이를 방지하기 위해서는 교착상태가 발생하지 않도록 자원 할당 순서를 결정하거나, 타임아웃(timeout)을 사용하여 대기 시간을 제한하는 등의 방법을 사용할 수 있습니다.
=> 저의 경우 동작 전에 짝수 번 철학자(스레드)에 usleep을 걸어 홀수 번 철학자들이 먼저 동작을 수행하며, 짝수 번 철학자와 홀수 번 철학자의 포크 집는 순서를 반대로 하여 실행 순서를 결정했습니다.
진행(Progress) 보장 : 한 프로세스가 임계 영역에 진입하려고 할 때, 다른 프로세스들이 계속해서 실행되도록 보장합니다.
이를 위해 프로세스들이 번갈아가며 임계 영역에 진입할 수 있도록 제어합니다.
=> 철학자(스레드)마다 time_to_die 시간이 있어 기아 상태에 빠지지 않게 모든 스레드들이 번갈아가며 임계 영역에 진입해 정상 동작 해야 합니다.
교착상태(Deadlock) 방지를 하기 위해선 교착상태가 발생하는 조건을 알아야 합니다.
교착상태(Deadlock)가 발생하기 위해서는 다음 4가지 조건이 모두 충족되어야 합니다.
상호배제(Mutual Exclusion) : 자원은 한 번에 하나의 프로세스만이 사용할 수 있습니다.
=> 철학자들은 포크를 공유할 수 없습니다. 하나의 포크를 동시에 사용이 불가능합니다.점유와 대기(Occupy and Wait) : 하나의 프로세스가 자원을 점유한 상태에서 다른 프로세스가 점유한 자원을 대기하고 있습니다.
=> 2명의 철학자가 마주 보고 있다 가정할 때, 1번 철학자가 왼쪽 포크를 잡고 2번 철학자가 오른쪽 포크(1번 입장에서는 왼쪽 포크)를 잡아야 하는데 이미 1번 철학자가 잡고 있는 상태이므로 포크를 내려놓을 때까지 계속 자원을 대기하고 있습니다.비선점(No Preemption) : 다른 프로세스가 점유한 자원을 강제로 빼앗아 사용할 수 없습니다.
=> 철학자가 이미 잡고 있는 포크를 다른 철학자가 빼앗아 사용할 수 없습니다.순환 대기(Circular Wait) : 두 개 이상의 프로세스가 서로가 점유한 자원을 대기하고 있습니다. 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 원형을 이루면서 대기하는 조건.
=> 각 철학자들은 자신의 왼쪽 철학자의 포크를 대기합니다.이 4가지 조건이 philosophers 프로젝트에서 만족되기 때문에 교착상태(데드락)이 발생 할 수 있습니다.
🖥️ Mandatory
📌 사용할 함수
pthread_create
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);특정 함수를 실행하는 스레드를 만드는 함수
1번 매개변수(pthread_t *thread)
스레드 식별자, 스레드 구분을 위한 id
2번 매개변수(const pthread_attr_t *attr)
스레드 특성을 지정하기 위해 이용하는 매개변수, 보통 NULL
3번 매개변수(void (start_routine)(void *))
thread가 실행되었을 때 시작할 스레드 함수
4번 매개변수(void *arg)
스레드가 분기할 함수에 보낼 입력 파라미터
pthread_join
int pthread_join(pthread_t th, void **thread_return)스레드가 종료되길 기다렸다가, 스레드가 종료되면 다음 명령어 진행
1번 매개변수(pthread_t th)
스레드 식별자, 스레드 구분을 위한 id
2번 매개변수(void **thread_return)
파라미터 리턴값
pthread_mutex_init
pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutex_attr *attr)1번 매개변수(pthread_mutex_t *mutex)
초기화시킬 mutex객체
2번 매개변수(const pthread_mutex_attr *attr)
mutex 특성 변경, 기본 시 NULL
우리는 attr 설정함수를 사용하지 못하므로 NULL 사용
pthread_mutex_destory
int pthread_mutex_destroy(pthread_mutex_t *mutex)1번 매개변수(pthread_mutex_t *mutex)
삭제할 mutex 객체
자원을 되돌려준다.
pthread_mutex_lock
int pthread_mutex_lock(pthread_mutex_t *mutex)1번 매개변수(pthread_mutex_t *mutex)
lock할 뮤텍스
해당 뮤텍스에 대해 잠금을 시도하는데, 이미 다른 스레드에 의해 잠겨있다면 잠금을 얻을 수 있을 때까지 무한대기.
pthread_mutex_unlock
int pthread_mutex_unlock(pthread_mutex_t *mutex);1번 매개변수(pthread_mutex_t *mutex)
unlock할 뮤텍스
📌 코드
typedef struct s_data t_data;
typedef struct s_info
{
pthread_t philosopher; // thread
int id; // 개개인의 id넘버
int left_fork;
int right_fork;
int eat_count;
long last_eat;
t_data *link_table; // philosophers에서 table정보 연결
} t_info; // philosophers 개인의 정보
struct s_data
{
t_info **link_philo; // table에서 philosophers 개인의 정보와 연결
int philo_num;
int time_to_die;
int time_to_eat;
int time_to_sleep;
int must_eat;
int stop_flag;
long time;
pthread_mutex_t *fork;
pthread_mutex_t print;
pthread_mutex_t last_ate; // 공유자원 mutex
}; // table, 들어오는 인자 정보헤더 파일은 위와 같습니다.
아마 해당 프로젝트를 하는데 가장 큰 어려움을 겪는 곳이 헤더라고 생각됩니다.
어떤 자원을 공유자원으로 하여 mutex lock을 걸어야 할지, pthead를 어떻게 사용해야 할지 등등
구조체끼리 자유롭게 참조가 가능하게 작성했습니다. t_info 구조체도 t_data를 참조할 수 있고, t_data도 t_info를 2중 포인터로 가리켜 각각의 pthread_t philosophers 참조가 가능합니다.
int main(int argc, char *argv[])
{
t_data table;
if (!(argc == 5 || argc == 6))
{
printf("argument error\n"); // 인자 개수 에러 체크
return (0);
}
if (init_data(argc, argv, &table)) // 들어온 문자열 인자들을 원하는 형태로 변환
return (0);
init_mutex(&table); // mutex 생성
run_philo(&table); // 동작
return (0);
}인자 개수가 5개나 6개가 아니면 에러 문구 출력 후 그대로 종료합니다.
제대로 된 인자가 들어 올 경우 문자열로 들어온 인자들을 형변환 해주고 mutex를 생성 해 준 다음 동작 함수로 넘어갑니다.
int init_data(int argc, char *argv[], t_data *table)
{
table->must_eat = -1;
table->philo_num = ft_atoi(argv[1]); // 철학자의 수
table->time_to_die = ft_atoi(argv[2]); // 죽기까지 걸리는데 시간
table->time_to_eat = ft_atoi(argv[3]); // 먹는데 걸리는 시간
table->time_to_sleep = ft_atoi(argv[4]); // 수면시간
if (argc == 6)
table->must_eat = ft_atoi(argv[5]); // 최소한의 식사 회수
if (table->philo_num < 1 || table->time_to_die < 1 || table->time_to_eat < 1 \
|| table->time_to_sleep < 1 || (argc == 6 && table->must_eat < 1))
{
printf("argument error\n");
return (1);
}
table->time = get_time(0); // 현재 시간 입력
table->link_philo = malloc(sizeof(t_info *) * table->philo_num); // 철학자 수 만큼 동적할당
return (0);
}
long get_time(long time)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return ((tv.tv_sec * 1000) + (tv.tv_usec / 1000) - time);
}들어오는 인자가 1보다 작은 값 (0 또는 음수)가 들어오면 저는 종료를 시키기로 결정했습니다.
현재 시간을 입력할 때는 gettimeofday 내장 함수를 사용하며, 이를 ms로 변환해서 사용합니다.
void init_mutex(t_data *table)
{
int i;
i = 0;
table->fork = malloc(sizeof(pthread_mutex_t) * table->philo_num);
while (i < table->philo_num)
{
pthread_mutex_init(&table->fork[i], NULL);
i++; // 포크 수 만큼 mutex 생성
}
pthread_mutex_init(&table->print, NULL); // printf의 특성 상 mutex 생성
pthread_mutex_init(&table->last_ate, NULL); // 스레드 별 먹은 회수 mutex 생성
}공유자원인 포크를 개수만큼 mutex 생성하고, 먹는 횟수도 스레드가 변경됨에 따라 달라질 수 있기 때문에 mutex로 관리해 줍니다.
print의 경우 printf 함수가 버퍼에 쌓여있는 입력값들을 개행문자('\n')가 나오면 버퍼를 비워주며 출력하는 함수입니다.
즉 mutex를 걸어주지 않으면 개행문자가 나오기 전까지 여러 스레드에서 동시 접근이 가능하여 입력과 출력의 결과가 달라질 수 있기 때문에 mutex를 걸어줍니다.
void run_philo(t_data *table)
{
t_info **philo;
int i;
i = 0;
philo = malloc(sizeof(t_info *) * table->philo_num); // 인자로 들어온 철학자의 수 만큼 동적할당
while (i < table->philo_num)
{
philo[i] = malloc(sizeof(t_info));
init_philo(i, philo[i], table); // 각 철학자 마다 정보 입력
table->link_philo[i] = philo[i]; // 구조체끼리 연결
pthread_create(&philo[i]->philosopher, \
NULL, &routine, (void *) philo[i]); // 스레드 생성 하며 routine 함수 동작
i++;
}
monitoring(table); // 메인 스레드에서 모니터
delete_all(table, philo); // free와 mutex_destroy
}철학자마다 정보를 입력해 준 다음에 각 철학자들을 routine 함수를 수행하는 스레드로 생성해 줍니다.
스레드들이 routine 함수를 수행하는 동안,
메인 스레드에서는 monitoring 함수를 수행하면서 스레드들의 상태를 관찰합니다.
void *routine(void *argument)
{
t_info *philo;
philo = argument;
if (!(philo->id & 1))
usleep(1000);
while (1)
if (ft_operate(philo) == 0)
break ;
return (0);
}
int ft_operate(t_info *philo)
{
if (take_fork(philo))
if (eating(philo))
if (sleeping(philo))
if (thinking(philo))
return (1);
return (0);
}routine 함수 안에서는 스레드들의 동시 접근을 막기 위해 짝수 번 철학자에 usleep을 걸어 지연시켜 진행합니다.
- 포크 2개 잡기
- 먹기
- 자기
- 생각하기 (대기)
int take_fork(t_info *philo)
{
int fork;
fork = 0;
while (fork < 2)
{
if (check_stop_flag(philo)) // stop flag 발생 시 탈출
return (0);
if (fork == 0) // 첫번째 포크
{
if (philo->id & 1)
get_fork(philo, philo->left_fork); // fork를 mutex lock 해줍니다.
else
get_fork(philo, philo->right_fork);
}
else if (fork == 1) // 두번째 포크
{
if (philo->id & 1)
get_fork(philo, philo->right_fork);
else
get_fork(philo, philo->left_fork);
}
fork++;
}
return (1);
}철학자들은 2개의 포크를 집어야 eating 동작 함수에 진입할 수 있습니다.
첫 번째 포크 : 홀수 번 철학자는 왼쪽 포크를, 짝수 번 철학자는 오른쪽 포크를 집게 합니다.
두 번째 포크 : 홀수 번 철학자는 오른쪽 포크를, 짝수 번 철학자는 왼쪽 포크를 집게 합니다.
만약 잡는 포크를 지정해 주지 않고 모든 철학자들이 특정 방향의 포크를 잡는다면, 두 번째 포크를 잡을 때 서로 포크를 요청하는 데드락 상태에 빠집니다.
int eating(t_info *philo)
{
int result;
result = 1;
if (check_stop_flag(philo)) // stop flag 발생 시 lock 상태의 mutex를 unlock하고 종료
{
pthread_mutex_unlock(&philo->link_table->fork[philo->left_fork]);
pthread_mutex_unlock(&philo->link_table->fork[philo->right_fork]);
return (0);
}
mutex_printf("is eating", philo, 1); // 식사중 문구 출력
pthread_mutex_lock(&philo->link_table->last_ate); // 공유 자원을 관리하기 위한 mutex lock
philo->last_eat = get_time(0); // 현재 시간을 마지막 먹은 시간에 기입
philo->eat_count++; // 먹은 회수 증가
if (philo->eat_count == philo->link_table->must_eat)
result = 0; // 먹은 회수가 6번째 인자인 최소 식사수와 같으면 종료
pthread_mutex_unlock(&philo->link_table->last_ate);
msleep(philo->link_table->time_to_eat);
pthread_mutex_unlock(&philo->link_table->fork[philo->left_fork]);
pthread_mutex_unlock(&philo->link_table->fork[philo->right_fork]);
return (result);
}
void msleep(int time)
{
long temp;
temp = get_time(0);
while (get_time(0) - temp < time)
usleep(100);
}eating 함수에서는 현재 시간을 마지막 식사를 한 시간으로 변경해 주고, 먹은 횟수를 증가시킵니다.
여러 철학자가 동시에 한 변수를 쓰려고 할 때, 데이터 레이스가 발생할 수 있습니다.
이를 예방하기 위해 last_ate 변수를 mutex lock을 걸고 진행합니다.
식사 회수 증가 및 마지막 식사 시간을 변경 후엔 time_to_eat 시간만큼 msleep을 걸고 지금껏 mutex lock 했던 변수들을 모두 unlock 해주고 종료합니다.
usleep(philo->link_table->time_to_eat)이 아닌 msleep이라는 함수를 만든 것은 usleep 자체에 딜레이가 존재하기 때문입니다.
이를 해결하기 위해 while()로 작은 단위의 usleep을 반복하는 형식으로 지연시간을 처리했습니다.
int sleeping(t_info *philo)
{
if (check_stop_flag(philo))
return (0);
mutex_printf("is sleeping", philo, 4);
msleep(philo->link_table->time_to_sleep);
return (1);
}
int thinking(t_info *philo)
{
if (check_stop_flag(philo))
return (0);
mutex_printf("is thinking", philo, 8);
usleep(500);
return (1);
}sleeping에서는 time_to_sleep 만큼 지연시키고 현재 상태를 출력합니다.
thinking에서는 현재 상태를 출력하며, 홀수 명의 철학자가 존재할 경우 지연 없이 바로 스레드를 동작시키면 다른 스레드가 동작하기 전에 다시 실행하여 기아 상태가 될 수 있기 때문에 적당한 시간을 지연시켰습니다.
ex) 3명의 철학자가 있다 가정하겠습니다.
포크의 개수 관계상 1번이 먼저 동작 이후 3번 다음에 2번이 동작해야 합니다.
한 번씩 다 먹은 후 만약 thinking에 딜레이가 없다면, 특정 두 철학자 끼리만 번갈아 먹을 수 있기 때문에 한 명의 철학자는 먹지 못하고 죽게 됩니다.
스레드들은 위의 동작들을 계속 반복하며 동작하고 있습니다.
void monitoring(t_data *table)
{
int i;
i = table->philo_num;
while (1)
{
if (++i >= table->philo_num) // 철학자들의 인덱스를 반복 확인
i = 0;
pthread_mutex_lock(&table->last_ate);
if (get_time(table->link_philo[i]->last_eat) >= table->time_to_die) // 현재 시간에서 마지막 식사시간을 뺀 시간이 time_to_die보다 크면 stop_flag를 발생시킵니다.
{
if (table->link_philo[i]->eat_count != table->must_eat) // 먹은 횟수가 must_eat이 아니라면 철학자가 죽은 상태
{
pthread_mutex_lock(&table->print);
table->stop_flag = 1;
printf("%ld %d died\n", get_time \
(table->time), table->link_philo[i]->id); // stop_flag를 1로 변경하고 스레드가 죽었음을 출력
if (table->philo_num == 1)
pthread_mutex_unlock(&table->fork[0]); // 만약 철학자가 1명이라면 포크를 1개 잡은 상태에서 죽은 상태이니 포크를 unlock해줍니다.
pthread_mutex_unlock(&table->print);
}
pthread_mutex_unlock(&table->last_ate);
break ;
}
pthread_mutex_unlock(&table->last_ate);
}
}생성한 스레드들이 routine 함수를 반복하고 있는 동안 메인 스레드는 monitoring 함수를 반복합니다.
여기서도 데이터 레이스를 방지하기 위해 mutex lock 하고 변수들을 확인합니다.
(현재 시간) - (마지막 식사를 시작한 시간) >= (time_to_die)는 time_to_die 시간이 흐를 동안 식사를 하지 못했다는 뜻이니 철학자의 상태를 확인 후 반복문을 탈출합니다.
철학자들의 먹은 횟수가 최소한의 식사 횟수와 같다면 정상 종료이고, 그 외의 경우는 철학자가 죽었다는 상태입니다.
철학자가 사망했다면 stop_flag를 1로 만들어 스레드들을 종료시키고 특정 철학자가 죽었다고 출력합니다.
만약 철학자가 1명일 경우에는 routine 함수에서 포크를 1개 잡고 두 번째 포크를 잡지 못해 사망할 테니, 잡고 있는 포크를 mutex unlock 해주고 종료합니다.
void delete_all(t_data *table, t_info **philo)
{
int i;
i = 0;
while (i < table->philo_num)
{
pthread_join(philo[i]->philosopher, NULL);
pthread_mutex_destroy(&table->fork[i]);
free(philo[i]);
i++;
}
pthread_mutex_destroy(&table->print);
pthread_mutex_destroy(&table->last_ate);
free(table->link_philo);
free(table->fork);
free(philo);
}메인 스레드에서 동작하는 monitoring 함수가 stop_flag를 발생시키고 종료되면, 스레드와 mutex를 반납하고 종료합니다.
✅ 배운점
이전 포스트는 pipex에서는 프로세스와 프로세스 간 통신 IPC에 대해 직접 코딩을 해보며 어떻게 동작하는지를 배웠다면, 이번에는 멀티 스레드와 동기화 방식 등 그 과정에서 발생할 수 있는 문제점들을 직접 겪고 코딩해 보는 과정에서 많은 걸 배웠습니다.
공유자원을 mutex로 생성하지 않아 임계 영역을 통제하지 못할 때 생기는 현상,
처음 스레드 동작 시 순서와 포크 잡는 순서를 정해주지 않으면 발생하는 교착상태(데드락) 현상,
홀수 개의 스레드일 때 대기 상태에서 지연을 걸어주지 않으면 생기는 기아 상태에 빠지는 현상,
스레드가 변경될 수 있는 상황에서 변수를 확인할 때, mutex를 걸어주지 않아 -fsanitize=thread로 확인해 보니 발생한 데이터 레이스 현상 등
학부 운영체제 수업 때 이론으로만 배운 것들을 직접 코딩해 보며 잊었던 내용들을 상기시키고, 내부적으로 어떻게 동작하는지 직접 확인하니 더욱 뇌리에 깊게 박히는 프로젝트였습니다.
