[CS] 식사하는 철학자 C언어로 해결하기

※ 이 포스트에서는 Command Pattern을 이용해 문제를 해결하는 방식을 썻고

철학자가 1명인 경우는 제외했습니다.

 

교착 상태(Dead Lock)와 경합 조건(Race Condition)에 관해 배우는 대표적인 주제인 식사하는 철학자 입니다.

 

식사하는 철학자 문제를 간단하게 설명드리자면

1. 각각의 철학자는 스레드이다.
2. 철학자는 스파게티를 먹고 자고 생각하는 루틴을 반드시 지켜야 한다.
3. 각각의 철학자는 다른 철학자의 상태를 확인할 수 없다.
4. 포크는 철학자 수 만큼 주어지고 각 포크는 철학자 사이에 있다.
5. 철학자가 식사할 때는 포크가 반드시 2개가 필요하다.
6. 각 철학자는 생명 시간이 있다.
7. 철학자는 먹고 자는 루틴에 생명을 담보로한 소요 시간이 있다.
8. 자고 난 뒤에는 생명 시간이 연장 된다.
9. 만약 하나의 철학자라도 죽었다면 모든 철학자는 행동을 멈춰야 한다.
10. 각각의 철학자는 루틴을 반복해야 한다.

즉 철학자가 밥먹을 때 포크 2개를 사용하기 때문에 양 옆에있는 철학자는 다른 철학자가 밥먹는 동안 기다린 후 밥을 먹고

밥을 먹은 철학자는 자고 생각한 뒤 먹을 준비를 해야합니다.

그 과정에서 기다리는 철학자는 루틴을 실행하지 못한 채 생명시간이 계속해서 깎이게 됩니다.

 

철학자 수가 짝수면 홀수, 짝수 번갈아 가면서 먹으면 되지만 홀수인 경우 1명의 철학자는 반드시 기다려야 하는 상황이 되는 겁니다.

 

이번 포스트에서는 식사하는 철학자 문제를 C언어로 해결하는게 목적이고 C언어가 아니더라도 비슷한 방식으로 풀 수 있습니다.

 

1. 교착 상태란?

---

두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태

무한히 다음 자원을 기다리게 되는 상태

 

예시로는 좁은 골목길에 두 차량이 서로 마주보고 올 때 두 차량이 서로 양보를 안해줘서 이도저도 못하는 기싸움같은 현상이라고 할 수 있습니다.

 

교착 상태가 발생하기 위해서는 4가지 조건이 필요합니다.4가지 중 한가지라도 충족되지 않으면 교착 상태가 발생하지 않습니다.

1. 상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 베타적인 통제권을 요구한다.
2. 점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
3. 비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
4. 순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

2. 경합 조건이란?

---

다중 프로그래밍 시스템이나 다중 처리기 시스템에서 두 명령어(이상)가 동시에 같은 기억 장소를 엑세스할 때 그들 사이의 경쟁에 의해 수행 결과를 예측할 수 없게 되는 상황

 

식사하는 철학자가 행동을 한다면 해당 행동에 관해서 로그를 찍게 되는데 멀티 스레드 환경에서는 그 로그가 저희가 생각한것과 달리 순차적으로 나오지 않습니다.

 

송금 과정을 예로 들면

1. 송금할 돈이 내 계좌에 충분히 있는 경우 (없으면 종료)

2. 임시 DB로 돈을 옮긴다

3. 상대방이 돈을 받을 준비가 된 경우 (못받는 경우면 3-1)

3-1. 임시 DB에서 내 계좌로 돈을 옮긴 후 종료

4. 임시 DB에서 상대방 계좌에 돈을 옮기는데 오류가 없었다면 종료 (오류가 있었다면 3-1)

 

 

이런 순서가 될텐데 만약

나는 송금을 했는데 오류가 발생해서 상대방은 내 돈을 못받고

내 계좌에서 돈이 빠져나간 상황이 나오게 되는 심각한 상황이 발생할 수 있습니다.

 

다시 본론으로 돌아가자면 철학자의 행동을 찍는 로그가 순차적으로 실행되지 않아서

먹고 자고 생각하는 루틴이 자고 생각하고 먹는 루틴으로 변질될 수 있다는 겁니다.

 

이런 경합 조건이 나오는 상황을 막기위해 원자성을 보장하게 해야합니다.

 

교착 상태인 경우에도 똑같이 원자성을 보장하게 하기위해 레드존을 보호해야 합니다.

 

3. Mutex란?

---

프로세스 혹은 스레드 간 메시지를 전송하거나, 공유메모리를 통해 공유된 자원에 여러 개의 프로세스가 동시에 접근하면 Critical Section 문제가 발생할 수 있다.

 

이를 해결하기 위해 데이터를 한 번에 하나의 프로세스 혹은 스레드만 접근할 수 있도록 제한을 두는 동기화 방식을 취해야 한다.

 

동기화 방식에는 Mutex와 Semaphore 가 있는데 여기서는 Mutex를 사용하겠습니다.

 

 

Mutex는 임계구역(Critical Section)을 가진 스레드들의 실행시간(Running Time)이 서로 겹치지 않고 각각 단독으로 실행되도록 하는 기술입니다.

 

이를 이용해 4가지 조건 중 하나인 상호배제 못하게해서 교착 상태를 해결할 수 있습니다.

 

4. Command Pattern이란?

---

디자인 패턴 중 하나인 Command Pattern이란 

명령의 실행을 요청한 시점과 명령을 처리하는 시점을 분리하는 패턴입니다.

 

비유하자면 관리자가 직원에게 오늘은 이거해 저거해 하고 자기 할일 하러가는것과 같습니다.

이 과제에서는 각각의 스레드(철학자)가 중앙 스레드에게 나 먹을게 잘게 하는 행동(함수)를 던지고

이후의 코드를 실행하러 가는것과 같습니다.

 

커맨드 패턴은 주로 큐를 사용해서 각 스레드가 넘긴 함수를 실행시켜 주면

경합 조건이 발생하지 않고 실행시켜 주는 주체가 하나이기 때문에 교착상태가 발생하지 않습니다.

또한 실행 시키는게 하나의 스레드이기에 임계 구역을 칠 필요가 없어 시간적으로 단축이 되는 장점도 있습니다.

 

그렇다면 Command Pattern을 왜 사용하는가?에 의문이 듭니다.

 

만약 각각의 철학자가 각 루틴의 로그를 찍는 코드를 직접 실행한다고 칩시다.

그 코드들은 함수로 되어있을 거고 각각의 행동을 직접 실행하면

Mutex로 먼저 임계 구역에 들어간 스레드를 기다려야 합니다.

 

이 부분에서 아무런 행동도 하지않고 가만히 기다리는게 굉장히 치명적이죠

n번째로 로그를 찍는 스레드는 n - 1만큼의 스레드가 모두 로그를 찍은 뒤 임계구역에 들어갈 수 있고

mutex로 lock을 하는 코드를 실행하는데 운이 나쁘면 50(ms)마이크로 초가 걸립니다.

 

최악의 경우 50ms * n으로써 200명이라 치면 모든 스레드가 로그를 출력하는데 1미리초가 걸리게 됩니다.

 

그래서 Command Pattern을 사용하게 되었습니다.

 

5. 코드 리뷰

---

이 포스트에서는 

• 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

위와 같은 형식으로 로그를 출력합니다.

ms는 미리초단위로 프로그램이 시작된 이후의 시간이고 X는 각 철학자의 ID입니다.

 

argv 인자로

철학자 수, 생명 시간, 먹는 시간, 자는 시간, (선택) 최소 먹어야 하는 횟수를 받습니다.

 

각종 구조체를 담고있는 헤더 파일입니다.

눈여겨 볼건 가장 밑에 있는 구조체 3개입니다.

저 구조체들이 각 노드로서 큐에 담기게 될것입니다.

<hide/>
#ifndef STRUCTS_H
# define STRUCTS_H

# include <pthread.h>
# include "Queue.h"
# include <stdbool.h>

typedef struct s_cmd	t_cmd;
typedef struct s_q		t_queue;

// philo state
typedef enum
{
	ALIVE,
	DIE,
	FINISH,
}	t_state;

// time struct
typedef struct
{
	long	die;
	long	eat;
	long	sleep;
}	t_time;

typedef struct s_data	t_data;

// philo struct
typedef struct
{
	long	id;
	long	eat_cnt;
	long	last_eat_time;
	long	left;
	long	right;
	t_state	state;
	t_data	*data;
}	t_philo;

// data
typedef struct
{
	pthread_mutex_t	push;
	pthread_mutex_t	lock;
	pthread_mutex_t	*forks;
	t_time			time;
	t_state			state;
	long			num_of_philo;
	long			start_time;
	long			least_eat_cnt;
	long			ate_philo_cnt;
	t_queue			*job_queue;
	t_philo			*philos;
	bool			die;
}	t_data;

// print msg type
typedef enum
{
	FORK,
	EAT,
	SLEEP,
	THINK,
	DIED,
}	t_msg_type;

// print state of philo
typedef struct s_t1
{
	t_cmd		base;
	long		time;
	long		id;
	t_msg_type	type;
	t_data		*data;
}	t_print_msg;

// if philo finish, data->ate_philo_cnt++
typedef struct s_t2
{
	t_cmd	base;
	t_state	state;
	t_data	*data;
}	t_check_state;

// change data state to die
typedef struct s_t3
{
	t_cmd	base;
	t_data	*data;
}	t_change_state_to_die;

#endif

 

Queue 헤더파일 입니다.

보시면 t_cmd 라는 구조체를 Structs 헤더에 있는 3개 구조체에 하나씩 집어넣어서 인터페이스로써 사용했습니다.

execute라는 함수로 중앙 스레드가 편하게 실행할 수 있게 만들었습니다.

<hide/>
#ifndef QUEUE_H
# define QUEUE_H

typedef struct s_cmd
{
	void	(*execute)(struct s_cmd *);
}	t_cmd;

typedef struct s_node
{
	t_cmd			*cmd;
	struct s_node	*next;
	struct s_node	*prev;
}	t_node;

typedef struct s_q
{
	void	(*push)(struct s_q *, t_cmd *);
	t_node	*(*pop)(struct s_q *);
	t_node	*head;
	t_node	*tail;
}	t_queue;

void	print_msg(t_cmd *cmd);
void	push(t_queue *job_queue, t_cmd *cmd);
t_node	*pop(t_queue *job_queue);

#endif

 

create_philos 함수에서 각 철학자를 생성해 start_routine으로 넘겨주고 main 스레드는 check_philos로 빠집니다.

큐를 지속적으로 POP해서 함수들을 실행시켜주기만 하고 그 과정을 철학자 모두가 온전히 살아있을 때까지 반복합니다.

 

각 철학자는 start_routine으로 빠진뒤 홀짝을 한번 분리 시켜줍니다.

이 과정에서 교착상태 조건 4번째인 순환 대기를 막아줍니다.

 

어느 철학자가 중앙 스레드에게 자신이 죽었음을 알리는 함수를 큐에 넣었다면 그 함수를 execute한 뒤 data->state가 변해

무한 루프에서 빠져나와 프로그램이 종료됩니다.

<hide/>
#include "../Header/Philo.h"

void	*start_routine(t_philo *philo)
{
	t_data	*data;

	data = philo->data;
	philo->last_eat_time = get_time();
	if (philo->id % 2 == 0)
		usleep(data->time.eat * 800);
	while (philo->state == ALIVE)
	{
		t_philo_eat(data, philo);
		t_philo_sleep(data, philo);
		t_philo_think(data, philo);
		usleep(200);
	}
	_push_2(data, philo->state);
	return (NULL);
}

void	finish_routine(t_data *data, pthread_t *philos)
{
	long	i;

	i = 0;
	while (i < data->num_of_philo)
	{
		pthread_join(philos[i], NULL);
		i++;
	}
}

void	check_philos(t_data *data)
{
	t_node	*job;

	while (data->state == ALIVE)
	{
		usleep(100);
		pthread_mutex_lock(&data->push);
		job = data->job_queue->pop(data->job_queue);
		pthread_mutex_unlock(&data->push);
		if (job == NULL)
			continue ;
		job->cmd->execute(job->cmd);
		free(job->cmd);
		free(job);
	}
}

void	create_philos(t_data *data)
{
	pthread_t	*philos;
	int			i;

	philos = (pthread_t *)malloc(sizeof(pthread_t) * data->num_of_philo);
	if (!philos)
		occur_exception(data);
	i = 0;
	while (i < data->num_of_philo)
	{
		if (pthread_create(&philos[i], NULL, (void *)start_routine, \
					&data->philos[i]) != 0)
			occur_exception(data);
		i++;
	}
	check_philos(data);
	finish_routine(data, philos);
	free(philos);
}

 

철학자의 루틴함수들이 있는 routine.c 파일입니다.

 

eat, sleep 부분에서 check_time으로 시간을 확인하면서 루틴을 도는 동안 자신의 상태를 확인합니다.

만약 생명 시간보다 루틴 시간이 더 많은 경우 중앙 스레드에 자신이 죽었음을 알리고

중앙 스레드는 누군가 죽었음을 알고 프로그램을 종료하게 됩니다.

 

만약 eat한 횟수가 least_eat_cnt인 경우 즉 최소 먹어야 하는 횟수를 충족시킨 경우

철학자 자신은 더 이상 행동할 필요 없게 만들었습니다.

<hide/>
#include "../Header/Philo.h"

void	check_time(t_data *data, t_philo *philo, long time_of_wait, \
long last_eat_time)
{
	long	start;
	long	cur_time;

	start = get_time();
	while (1)
	{
		cur_time = get_time();
		if (time_of_wait <= cur_time - start)
			break ;
		if (cur_time - last_eat_time >= data->time.die)
			break ;
		usleep(100);
	}
	if (cur_time - last_eat_time >= data->time.die)
	{
		philo->state = DIE;
		_push_1(data, get_time(), philo->id, DIED);
		_push_3(data);
	}
}

void	t_philo_eat(t_data *data, t_philo *philo)
{
	pthread_mutex_lock(&data->forks[philo->left]);
	_push_1(data, get_time(), philo->id, FORK);
	pthread_mutex_lock(&data->forks[philo->right]);
	_push_1(data, get_time(), philo->id, FORK);
	_push_1(data, get_time(), philo->id, EAT);
	philo->last_eat_time = get_time();
	check_time(data, philo, data->time.eat, philo->last_eat_time);
	pthread_mutex_unlock(&data->forks[philo->right]);
	pthread_mutex_unlock(&data->forks[philo->left]);
	philo->eat_cnt++;
	if (philo->eat_cnt == data->least_eat_cnt)
		philo->state = FINISH;
}

void	t_philo_sleep(t_data *data, t_philo *philo)
{
	if (philo->state != ALIVE)
		return ;
	_push_1(data, get_time(), philo->id, SLEEP);
	check_time(data, philo, data->time.sleep, philo->last_eat_time);
}

void	t_philo_think(t_data *data, t_philo *philo)
{
	if (philo->state != ALIVE)
		return ;
	_push_1(data, get_time(), philo->id, THINK);
}

 

철학자들의 행동들을 압축시켜 큐에 집어 넣는 함수들이 있는 Push.c 파일입니다.

_push 함수에 mutex_lock이 있는 이유는 중앙 스레드에서 pop을 할 때 경합 조건이 일어나지 않게 하기위해서 입니다.

나머지 push1, 2, 3 함수에 cmd->base.execute 부분에 중앙 스레드가 실행시킬 함수를 명시해 줍니다.

이후 함수를 실행시킬 떼 필요한 자원을 설정시켜 주면 됩니다.

<hide/>
#include "../Header/Philo.h"

void	_push(t_data *data, t_cmd *cmd)
{
	pthread_mutex_lock(&data->push);
	data->job_queue->push(data->job_queue, (t_cmd *)cmd);
	pthread_mutex_unlock(&data->push);
}

void	_push_1(t_data *data, long time, long id, t_msg_type type)
{
	t_print_msg	*cmd;

	cmd = (t_print_msg *)malloc(sizeof(t_print_msg));
	if (!cmd)
		exit(1);
	cmd->base.execute = print_msg;
	cmd->id = id;
	cmd->time = time;
	cmd->type = type;
	cmd->data = data;
	_push(data, (t_cmd *)cmd);
}

void	_push_2(t_data *data, t_state state)
{
	t_check_state	*cmd;

	cmd = (t_check_state *)malloc(sizeof(t_check_state));
	if (!cmd)
		exit(1);
	cmd->base.execute = check_finished_philo_state;
	cmd->state = state;
	cmd->data = data;
	_push(data, (t_cmd *)cmd);
}

void	_push_3(t_data *data)
{
	t_change_state_to_die	*cmd;

	cmd = (t_change_state_to_die *)malloc(sizeof(t_change_state_to_die));
	if (!cmd)
		exit(1);
	cmd->base.execute = change_state_to_die;
	cmd->data = data;
	_push(data, (t_cmd *)cmd);
}

 

 

push.c에서 execute에 들어가는 함수들입니다.

큐에 집어 넣을 때는 t_cmd로 임시 캐스팅한 뒤 각 함수에서는 기존 구조체로 다시 캐스팅 시켜

함수에서 쓰일 인자를 온전히 사용할 수 있게 했습니다.

 

각 함수들의 목적을 print_msg 함수부터 설명하자면

• 철학자의 상태를 출력
• 모든 철학자가 최소 먹어야 하는 횟수를 충족한 경우 무한루프 종료
• 어느 철학자가 죽은 경우 무한루프 종료

이러한 목적으로써 사용했습니다.

<hide/>
#include "../Header/Philo.h"

void	print_msg(t_cmd *_cmd)
{
	t_print_msg	*cmd;

	cmd = (t_print_msg *)_cmd;
	printf("%ld %ld ", cmd->time - cmd->data->start_time, cmd->id);
	if (cmd->type == FORK)
		printf("has taken a fork\n");
	else if (cmd->type == EAT)
		printf("is eating\n");
	else if (cmd->type == SLEEP)
		printf("is sleeping\n");
	else if (cmd->type == THINK)
		printf("is thinking\n");
	else if (cmd->type == DIED)
	{
		cmd->data->die = true;
		printf("die\n");
	}
}

void	check_finished_philo_state(t_cmd *_cmd)
{
	t_check_state	*cmd;

	cmd = (t_check_state *)_cmd;
	if (cmd->state == FINISH)
		cmd->data->ate_philo_cnt++;
	if (cmd->data->ate_philo_cnt == cmd->data->num_of_philo)
		cmd->data->state = FINISH;
}

void	change_state_to_die(t_cmd *_cmd)
{
	t_change_state_to_die	*cmd;

	cmd = (t_change_state_to_die *)_cmd;
	cmd->data->state = DIE;
}

 

 

나머지 보이지 않는 함수들은 짜잘한 것들입니다.

맨 처음 init해주거나 힙에 할당한 변수들을 free해주는 함수들이니 신경쓰지 않으셔도 됩니다.

 

위 코드로 ram 32gb intel 맥으로 실행시켜봤는데

200명의 철학자로 410의 생명시간, 200의 먹는 시간, 200의 자는 시간을 인자로 줘봤는데도 문제없이 잘 작동했고

print할 때의 시간이 거의 밀리지 않았습니다.

 

중앙 스레드가 전부 대신 실행시켜주기 때문이죠