#프로세스 #스레드 #뮤텍스 #세마포어 #데드락 #임계영역
5명의 철학자가 원탁에 앉아있습니다.
철학자들은 다음 작업을 반복합니다.
포크 들기 -> 식사하기 -> 포크 내려놓기 -> 잠자기 -> 생각하기
철학자는 포크 2개로 식사하고 원탁에 포크는 철학자 수만큼 존재합니다.
이때 포크 위치는 1. 철학자 양옆 2. 원탁 가운데 바구니
각 두가지 경우를 가정해 프로그램을 작성합니다.
1. 철학자 구현하기
철학자 5명은 각자 작업을 동시에 반복합니다.
작업을 동시에 실행하기위해 프로세스 또는 스레드를 구현합니다.
프로세스
위키백과에서 프로세스는 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램이라고 정의했습니다.
또한 컴퓨터 프로그램은 위키백과에서 명령어들의 모음이라고 정의했습니다.
종합해보면 컴퓨터에서 실행되고 있는 명령어들을 프로세스라고 하는 것이네요.
프로세스로 철학자 구현하기
int i;
pid_t philo;
i = 0;
while (i < 5)
{
philo = fork();
if (philo == 0)
{
routine();
exit(0);
}
i++;
}
메인 프로세스에서 fork 함수를 호출해 자식 프로세스를 생성합니다.
자식 프로세스에게 철학자가 반복해서 할 작업들이 담긴 routine 함수를 호출시킵니다.
자식 프로세스들은 routine 함수가 끝나면 종료됩니다.
스레드
스레드는 위키백과에서 프로세스 내에서 실행되는 흐름의 단위를 말한다라고 정의했습니다.
프로세스들은 각각 메모리를 할당받고 프로세스끼리 메모리를 공유하지 않습니다.
스레드들끼리는 자기가 속해있는 프로세스가 할당받은 메모리를 공유합니다.
스레드로 철학자 구현하기
int i
pthread_t philo;
i = 0;
while (i < 5)
{
if (pthread_create(&philo, NULL, &routine, (void *)&common) != 0)
return (1);
if (pthread_detach(philo) != 0)
return (1);
i++;
}
2. 포크 구현하기
철학자가 포크를 들고 있으면, 다른 철학자는 그 포크를 사용할 수 없습니다.
다른 포크를 사용하거나, 사용할 수 있는 포크가 없다면 대기합니다.
포크는 뮤텍스 또는 세마포어로 구현합니다.
뮤텍스
뮤텍스는 상호 배제의 약자 입니다.
상호 배제는 공유 자원을 동시에 사용하지 못하게 하는 알고리즘입니다.
뮤텍스로 포크 구현하기
pthread_mutex_t *init_forks()
{
pthread_mutex_t *forks;
int i;
if (!(forks = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t) * 5)))
return (NULL);
i = 0;
while (i < 5)
{
if (pthread_mutex_init(&forks[i], NULL) < 0)
{
free(forks);
return (NULL);
}
i++;
}
return (forks);
}
뮤텍스 사용하기
void take_forks(t_philo *p)
{
pthread_mutex_lock(p->lfork);
pthread_mutex_lock(p->rfork);
}
void sleep_philo(t_philo *p)
{
pthread_mutex_unlock(p->lfork);
pthread_mutex_unlock(p->rfork);
}
철학자들이 원탁에 앉아있고,
철학자 양 옆에 포크가 놓여져 있어서
철학자는 양 옆에 있는 포크 두개를 집어서 식사를 한다면
각 철학자 스레드가 lock을 거는 뮤텍스는 정해져있어야합니다.
t_philo *init_philo()
{
t_philo *philo;
pthread_mutex_t *forks;
int i;
if (!(philo = (t_philo *)malloc(sizeof(t_philo) * 5)))
return (NULL);
if (!(forks = init_forks()))
return (NULL);
i = 0;
while (i < 5)
{
philo[i].rfork = &forks[(i + 1) % 5];
philo[i].lfork = &forks[i];
i++;
}
return (philo);
}
각 스레드의 철학자 구조체를 만들고 해당 스레드에서 사용할 수 있는 뮤텍스 주소를 저장해 사용합니다.
각 스레드가 작업을 반복할 때 내가 lock 걸 뮤텍스가 다른 스레드에 의해 lock이 먼저 걸렸다면
unlock이 될때까지 대기했다가 unlock이 되면 lock을 걸고 다음 작업을 수행합니다.
세마포어
세마포어 또한 공유 자원에 대한 접근을 제한하는 방법입니다.
뮤텍스는 하나의 스레드만 공유자원에 접근이 가능하지만,
세마포어는 동시에 접근 가능한 프로세스를 제한해 접근할 수 있습니다.
세마포어로 포크 구현하기
sem_t *init_forks()
{
sem_t *forks;
sem_unlink("forks");
if ((forks = sem_open("forks", O_CREAT, 0777, 5)) == SEM_FAILED)
return (NULL);
return (forks);
}세마포어의 값은 wait이 가능한 수 입니다.
만약 세마포어의 수를 5로 생성했다면 프로세스들은 최대 5번 wait을 호출 할 수 있습니다.
그 다음 wait을 수행하는 프로세스는 먼저 wait을 호출한 프로세스가 post를 호출 하기 전까지 대기합니다.
post를 호출한 만큼 wait을 호출할수 있는 수가 회복됩니다.
세마포어 사용하기
void take_forks(t_philo *p)
{
sem_wait(p->info->forks);
sem_wait(p->info->forks);
}
void sleep_philo(t_philo *p)
{
sem_post(p->info->forks);
sem_post(p->info->forks);
}
이번에는 포크 위치가 철학자 양 옆에 하나씩 놓여져있는게 아니라,
원탁 가운데 바구니에 포크가 들어있고, 각 철학자들이 식사를 하기위해 포크를 두개씩 꺼냅니다.
각 프로세스 모두 같은 세마포어를 파라미터에 넣고 두번 wait을 호출합니다.
철학자가 식사를 마치고 잠에 들때 포크를 떨어뜨리므로 post도 두번 호출해줍니다.
교착상태 (Deadlock)
데드락은 자원을 획득하기 위해 무한 대기하는 상태입니다.
1971년에 E. G. 코프만 교수가 상호배제, 점유대기, 비선점, 순환대기를 모두 만족할 때 발생한다고 정리했습니다.
식사하는 철학자 문제는 데드락 발생의 4가지 필요조건을 모두 만족합니다.
1. 상호 배제
포크를 뮤텍스 또는 세마포어로 구현함.
2. 점유 대기
포크를 점유하면 이 포크를 점유하기 위해 대기하는 철학자가 존재함.
3. 비선점
뮤텍스는 다른 스레드가 unlock할 수 없고 세마포어가 전부 wait일때 강제로 post 할 수 없음.
4. 순환 대기
스레드에서 사용한 뮤텍스는 철학자가 원탁에서 서로 양 옆 포크 두개를 사용해 식사하는걸 가정했으므로
각 스레드가 가지고 있는 2개의 뮤텍스 주소가 스레드끼리 겹쳐지게 할당했기때문에
각 스레드는 주소가 겹치는 뮤텍스를 서로서로 대기할 수 있다.
프로세스에서 사용한 세마포어도 철학자만큼 개수를 할당하고 각 철학자는 포크 두개로 식사하기 때문에
각 프로세스 전부가 동시에 wait을 한다면 세마포어가 남아있지않아 전부 계속 대기하게 된다.
데드락은 데드락 발생의 4가지 중 하나만 만족하지 않아도 해결할 수 있습니다.
데드락의 해결법은 많지만 저는 간단하게 짝수 번호는 일정시간 대기하게 했습니다.
if (philo_num % 2)
usleep(15000);
이 방법은 순환 대기를 방해해 데드락을 예방하는데,
usleep이 정확하지 않아 지연시간이 쌓이면 데드락이 생길 수도 있어 완벽한 방법은 아닙니다.
3. 모니터링 구현하기
철학자 문제 프로그램을 실행할때 각 작업에 걸리는 시간과 철학자가 죽는 시간을 입력받습니다.
철학자가 죽는 시간은 철학자가 마지막 식사로부터 죽는 시간이 지나도록 식사를 하지 못하면 해당 철학자가 죽게되는 시간입니다.
이를 위해서 철학자가 마지막으로 식사한 시간을 저장하고,
현재 시간과 마지막 식사 시간을 비교해서 죽는 시간에 다다르도록
식사를 하지 못한다면 프로그램을 종료합니다.
3-1. 스레드에서 구현하기
철학자가 죽으면 프로그램 종료하기
스레드의 작업이 종료되지 않아도 메인 프로세스의 작업이 끝난다면 프로그램은 종료합니다.
철학자가 죽기전까지 메인 프로세스는 종료하지 않고 대기해야합니다.
t_common_info *init_check_died_mutex()
{
pthread_mutex_t *check_died;
if (!(check_died = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t))))
return (NULL);
pthread_mutex_lock(check_died);
return (check_died);
}check_died 뮤텍스를 생성하고 메인 프로세스에서 바로 lock을 호출합니다.
int start_pthread(t_philo *p)
{
int i;
i = 0;
while (i < 5)
{
if (pthread_create(&(p[i].pthread), NULL, &routine, (void *)&(p[i])) != 0)
return (1);
if (pthread_detach(p[i].pthread) != 0)
return (1);
i++;
}
pthread_mutex_lock(p->info->check_died);
pthread_mutex_unlock(p->info->check_died);
return (0);
}
메인 프로세스에서 철학자 스레드를 모두 생성하고 check_died의 lock을 호출하면
이전에 먼저 lock을 호출한 상태기 때문에 check_died 뮤텍스를 unlock하기 전까지 대기합니다.
철학자들의 죽음을 체크하는 모니터링 구현하기
int start_pthread(t_philo *p)
{
int i;
i = 0;
while (i < p->info->num_philo)
{
if (pthread_create(&(p[i].pthread), NULL, &routine, (void *)&(p[i])) != 0)
return (1);
if (pthread_detach(p[i].pthread) != 0)
return (1);
i++;
}
if (pthread_create(p->info->monitor, NULL, &monitoring, (void *)p) != 0)
return (1);
if (pthread_detach(*p->info->monitor) != 0)
return (1);
pthread_mutex_lock(p->info->check_died);
pthread_mutex_unlock(p->info->check_died);
return (0);
}모니터 스레드를 생성하고 모니터링 함수를 호출합니다.
void *monitoring(void *philo)
{
t_philo *p;
int i;
long long last_meal_ms;
struct timeval time_now;
p = (t_philo *)philo;
while (1)
{
i = -1;
usleep(50);
while (++i < 5)
{
last_meal_ms = change_to_ms(p[i].last_meal);
gettimeofday(&time_now, NULL);
if (last_meal_ms + p->info->time_to_die < change_to_ms(time_now))
{
print_state(&p[i], STATE_DIED);
pthread_mutex_unlock(p->info->check_died);
return ((void*)0);
}
}
}
return ((void*)0);
}스레드는 다른 스레드와 메모리를 공유하므로 하나의 모니터링 스레드가 모든 스레드의 데이터에 접근할 수 있습니다.
그래서 하나의 모니터 스레드에서 모든 스레드의 마지막 식사 시간과 죽는 시간을 비교해 철학자가 죽었는지 계속 체크합니다.
철학자가 죽었다면 check_died 뮤텍스를 unlock 시켜, 메인프로세스가 check_died를 lock 걸 수 있게 되므로 대기를 끝내고 프로그램이 종료됩니다.
3-2. 프로세스에서 구현하기
철학자가 죽으면 프로그램 종료하기
스레드는 메인 프로세스에서 모든 스레드를 체크하는 모니터링 스레드 하나만 생성했지만,
프로세스끼리는 메모리를 공유하지 않기 때문에 메인 프로세스에서 자식 프로세스들의 작업 타임 스탬프를 알 수 없으므로
스레드처럼 메인에서 전부 체크할 수 없었습니다.
그래서 각 프로세스에서 모니터링 스레드를 만들어 작업 타임 스탬프를 체크합니다.
void *routine(void *philo)
{
t_philo *p;
p = (t_philo *)philo;
if (pthread_create(p->info->child_monitor, NULL, &monitoring_philo_died, (void *)p) != 0)
return ((void*)1);
if (pthread_detach(*p->info->child_monitor) != 0)
return ((void*)1);
while (1)
{
take_forks(p);
eat_spaghetti(p);
sleep_philo(p);
think_philo(p);
}
return ((void*)0);
}
자식 프로세스가 호출하는 routine에서 스레드를 생성하고 모니터링 합니다.
void *monitoring_philo_died(void *philo)
{
t_philo *p;
long long last_meal_ms;
struct timeval time_now;
p = (t_philo *)philo;
usleep(p->info->time_to_die * 1000);
while (1)
{
usleep(50);
last_meal_ms = change_to_ms(p->last_meal);
gettimeofday(&time_now, NULL);
if (last_meal_ms + p->info->time_to_die < change_to_ms(time_now))
{
sem_post(p->info->check_die);
return ((void*)0);
}
}
return ((void*)0);
}
모니터링은 자기 타임스탬프만 검사하고 스레드에서 check_died 뮤텍스를 unlock 하듯이,
프로세스에서는 check_died 세마포어에 sem_post를 호출합니다.
메인 프로세스가 종료되어도 자식프로세스는 종료되지 않아 작업을 계속 수행하지만
철학자가 죽었을때 다른 프로세스도 모두 종료시켜주기 위해서 메인 프로세스를 대기시킵니다.
스레드와 같은 방식이지만 뮤텍스 대신 세마포어로 check_died를 생성합니다.
sem_t *init_check_die()
{
sem_t check_die;
sem_unlink("check_die");
if ((check_die = sem_open("check_die", O_CREAT, 0777, 0)) == SEM_FAILED)
return (NULL);
return (check_die);
}
forks 세마포어와는 다르게 값을 0로 초기화하면 wait 함수에서 대기하게 됩니다.
int start_process(t_philo *p)
{
int i;
i = 0;
while (i < 5)
{
p[i].pid = fork();
if (p[i].pid == 0)
{
routine(&p[i]);
exit(0);
}
i++;
}
sem_wait(p->info->check_die);
kill_all_process(p);
return (0);
}
자식 프로세스 중 하나가 철학자가 죽어서 post를 호출하면 세마포어 값이 1 증가하고,
메인 프로세스에서 wait 함수를 호출할수 있게 되어 kill_all_process 함수를 호출해 모든 프로세스를 종료시킨 뒤 프로그램을 종료합니다.
void *monitoring(void *philo)
{
t_philo *p;
long long last_meal_ms;
struct timeval time_now;
p = (t_philo *)philo;
usleep(p->info->time_to_die * 1000);
while (1)
{
usleep(50);
last_meal_ms = change_to_ms(p->last_meal);
gettimeofday(&time_now, NULL);
if (last_meal_ms + p->info->time_to_die < change_to_ms(time_now))
{
sem_post(p->info->check_die);
return ((void*)0);
}
}
return ((void*)0);
}
4. 작업 상태 출력하기
각 작업을 타임스탬프와 같이 출력합니다.
스레드 또는 프로세스는 차례대로 작업을 출력해야합니다.
그리고 철학자가 죽었을때 died를 출력한 이후로는 다른 철학자의 작업의 출력되지 않아야 합니다.
void print_state(t_philo *p, int state)
{
long long created_ms;
long long current_ms;
long long timestamp_ms;
created_ms = p->created;
current_ms = now_time();
timestamp_ms = current_ms - created_ms;
if (state == STATE_FORK)
printf("%llu %d has taken a fork\n", timestamp_ms, p->philo_num);
else if (state == STATE_EAT)
printf("%llu %d is eating\n", timestamp_ms, p->philo_num);
else if (state == STATE_SLEEP)
printf("%llu %d is sleeping\n", timestamp_ms, p->philo_num);
else if (state == STATE_THINK)
printf("%llu %d is thinking\n", timestamp_ms, p->philo_num);
else if (state == STATE_DIED)
printf("%llu %d died\n", timestamp_ms, p->philo_num);
}
각 철학자는 각자의 작업을 반복하는데 이 작업들은 동시에 이루어집니다.
하지만 각 작업의 출력은 동시에 이루어지는게 아니라 차례대로 출력해야합니다.
동시에 호출하게되면, 타임스탬프에 맞지 않게 섞여서 출력이 될 수 있습니다.
또한 died를 출력한 뒤에는, 살아있는 다른 철학자가 작업을 출력하는 것을 멈춰야합니다.
이렇게 한번에 하나의 스레드만 접근해야하는 상태를 출력하는 코드 영역을 임계 영역(Critical Section)이라고 합니다.
void print_state(t_philo *p, int state)
{
long long created_ms;
long long current_ms;
long long timestamp_ms;
created_ms = p->created;
current_ms = now_time();
timestamp_ms = current_ms - created_ms;
pthread_mutex_lock(p->info->print_m);
if (state == STATE_FORK)
printf("%llu %d has taken a fork\n", timestamp_ms, p->philo_num);
else if (state == STATE_EAT)
printf("%llu %d is eating\n", timestamp_ms, p->philo_num);
else if (state == STATE_SLEEP)
printf("%llu %d is sleeping\n", timestamp_ms, p->philo_num);
else if (state == STATE_THINK)
printf("%llu %d is thinking\n", timestamp_ms, p->philo_num);
else if (state == STATE_DIED)
{
printf("%llu %d died\n", timestamp_ms, p->philo_num);
return ;
}
pthread_mutex_unlock(p->info->print_m);
}
이전에 check_died 뮤텍스 또는 세마포어를 먼저 lock, wait을 호출해서 다른 철학자가 죽을때까지 메인 프로세스를 대기하게 했는데
이번에는 출력 영역에 접근할때 먼저 도착해 lock을 호출하고 출력하는 동안은 다른 스레드 또는 프로세스는 대기시킵니다.
출력이 끝나면 unlock을 호출해 다음 철학자가 또 lock을 호출하고 출력합니다.
이렇게 각자 동시에 작업을 하고 있더라도 뮤텍스, 세마포어를 이용해 동기화가 가능합니다.
뮤텍스를 이용해서 차례대로 출력하고,
died를 출력하면 unlock을 호출하지 않고 return 해서 다른 철학자의 출력을 대기 시킨 뒤 프로그램을 종료합니다.
식사하는 철학자 문제의 프로그램 작성을 1. 스레드와 프로세스 사용, 2. 뮤텍스와 세마포어 사용, 3. 데드락과 예방, 4. 모니터링으로 각 스레드, 프로세스 종료, 5. 임계영역인 작업 출력 다섯가지로 나누어서 정리했습니다.
프로그램을 작성하면서 생기는 문제를 다른 사람의 해결 코드를 검색해 수정해가며 완성했습니다.
기본적으로 정보가 많아서 문제를 해결하기 어렵진 않았습니다.
직접 프로그램을 작성해보고 정리해보니 전에는 이런게 있구나 정도에서 어느정도 개념을 깨우친 것 같습니다.
다음에는 c++ 개념을 천천히 정리하면서 연습해보겠습니다 ~
'C' 카테고리의 다른 글
| C언어 데이터 타입의 크기 (2) | 2020.11.23 |
|---|