철학자 문제

728x90

Philosophers (notion.site)

Philosophers

프로젝트 소개

tall-crustacean-783.notion.site

문제설명

Concepts

The basics of threading a process (프로세스 스레딩에 대한 기본 개념)
How to work on the same memory space (공유 메모리 공간을 어떻게 작업하는지)
How to make threads (스레드 만드는 방법)
Mutex / semaphore / shared memory (뮤텍스 / 세마포어 / 공유 메모리)
기본 개념들을 숙지한 채로, 동일한 기본 규칙을 가진 세 개의 개별 프로그램 작성하기

Basic Rules

원형 테이블에 둘러 앉은 몇 명의 철학자들은 식사를 하거나, 생각하거나, 자고 있다.
철학자들은 동시에 하나의 행동만 한다. 이를 테면 식사를 하고 있을 때는 생각하거나, 자지 않는다.
원형 테이블 중앙에는 스파게티가 든 큰 접시가 있다.
스파게티가 포크 하나로 먹기 어려워서, 철학자들은 양 손에 포크를 들고 스파게티를 먹는다.
철학자들은 굶어 죽으면 안 된다.
모든 철학자들은 스파게티를 먹고 싶다.
한 명의 철학자가 식사를 끝내면, 그는 포크를 내려놓고 잠자기 시작한다.
철학자가 잠자기를 끝내면, 생각하기를 시작한다.
한 철학자가 죽으면 시뮬레이션이 끝난다.
개별 프로그램은 다음과 같은 동일한 옵션들을 가져야 한다.
- number_of_philosophers : 철학자의 수, 즉 포크의 갯수
- time_to_die : 밀리세컨 단위. 한 철학자가 식사를 시작하지 않으면, 그가 마지막 식사를 시작하거나 시뮬레이션이 시작된지 ‘time_to_die’ 초 내에 그는 죽는다.
- time_to_eat : 밀리세컨 단위. 철학자가 식사를 하는 시간. 이 시간동안 철학자는 포크 두 개를 들고 있다.
- time_to_sleep: 밀리세컨 단위. 철학자가 자는 시간.
- number_of_times_each_philosopher_must_eat: (optional argument). 만약 모든 철학자들이 최소한 이 횟수만큼 식사를 했다면, 시뮬레이션은 끝난다. 만약 이 인자가 설정되지 않았다면, 철학자가 죽었을 때만 시뮬레이션이 끝난다.

Deadlock(교착) 상태를 설명, 해결하기 위한 문제

위와같이 철학자 5명이 있고 철학자는 양손에 포크를 들어야만 식사를 할 수 있다.

- 시나리오

1. 왼쪽 포크가 사용 가능해질 때까지 생각을 한다. 만약 사용 가능해지면 집어든다.

2. 오른쪽 포크가 사용 가능해질 때까지 생각을 한다. 만약 사용 가능해지면 집어든다.

3. 양쪽의 포크를 잡으면 정해진 시간만큼 식사를 한다.

4. 오른쪽 포크를 내려놓는다.

5. 왼쪽 포크를 내려놓는다.

6. 다시 1번으로 돌아간다.

간단하게, 만약 모든 철학자(process)들이 동시에 자신의 왼쪽 포크(공유 자원)를 잡는다면,

모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다.

그런데 모든 철학자들이 그러고 있다.

이 상태에서는 모든 철학자가 영원히 2번 상태에 머물러있어 음식을 먹을 수 없는 상태가 교착(Deadlock)상태이다.

---

필수 개념

Semaphore / Mutex

멀티 프로그래밍에서 공유 자원을 관리하는 해법들
쓰레드 혹은 프로세스들이 Critical Section(임계 구역)에 접근할 때 발생할 수 있는 문제를 관리하는 방법

무택스가 세마포어의 작은 영역이라고 볼 수 있다.

Critical Section

쓰레드 혹은 프로세스들의 처리 단위가 함께 접근해서는 안되는 공유 영역을 뜻한다. (=간단히 변수라고 생각하면 편하다.)

Semaphore

설명

리소스에 접근 가능한 카운트를 갖고 카운트만큼 동시에 임계구역에 접근할 수 있는 개념이 된다. 카운트가 전부 차면 다른 쓰레드 혹은 프로세스들은 대기해야 한다.
세마포어 카운트는 1 이상이며 카운트를 조절하여 진입 가능한 프로세스/스레드의 수를 조절할 수 있다.
세마포어는 mutex 와 달리 소유할 수 없다.
세마포어는 시스템 범위에 걸쳐져 파일 시스템 상의 파일로 존재한다.
해당 방법은 모든 교착 상태에 대한 해답을 제시해 줄 수는 없다.

작동 원리

세마포어의 작동 원리는 상호 배제 알고리즘(Mutual Exclusion)에 기반한다. 세마포어는 원자적으로 제어되는 정수 변수로, 일반적으로 세마포어의 값이 0이면 자원에 접근할 수 없도록 블럭을 하고 0보다 크면 접근함과 동시에 세마포어의 값을 1 감소시킨다. 반대로 종료하고 나갈 때에는 세마포어의 값을 1 증가시켜 다른 프로세스가 접근할 수 있도록 한다. 여기서 접근되는 자원은 임계구역으로 이 설정에 따라서 프로그램의 퍼포먼스가 극단적으로 하락할 수 있어 사용에 세심한 주의가 필요하다.

Busy Waiting

바쁜 대기란 아무 것도 하지 않는 빈 반복문을 계속 돌다가 임계구억에 진입할 수 있을 때 진입하는 방식이다. 빈 반복문을 반복하기 때문에 계속적으로 컨택스트 교환이 발생하며 이로 인하여 처리 효율이 떨어지는 단점이 있다. 또한, 어떠한 프로세스가 먼저 임계 구역에 진입을 할 수 있을 지에 대한 처리를 할 수 없다는 단점 또한 존재한다.

뮤텍스(Mutex)

설명

뮤텍스(Mutex)는 상호 배제(Mutual Exclusion)의 약자이다.
lock과 unlock으로 문제를 해결하는 방법이다. 임계구역이 lock 되어 있을 경우 unlock이 될 때까지 기다려야 하는 방법이다.
세마포어를 뮤텍스처럼 이용할 수 있다. 뮤텍스는 상태가 0, 1 두 개 뿐인 binary Semaphore 이다.
뮤텍스는 소유가 가능한 개념이며, 소유주가 이에 대한 책임을 진다.
뮤텍스를 소유 중인 쓰레드가 해당 뮤텍스를 해제할 수 있다.
뮤텍스는 프로세스 범위를 갖고 프로세스가 종료될 때 자동으로 사라진다.

데이터 레이스란?

멀티 쓰레드 혹은 멀티 프로세스 환경에서 일어나는 오류이다.
여러 쓰레드 혹은 여러 프로세스가 동시적으로 공유 자원에 접근할 때 발생할 수 있는 상황이다.
멀티 프로그래밍에서 여러 쓰레드 혹은 여러 프로세스는 실행 순서가 정해져 있지 않다. 이러한 이유로 발생하는 오류

교착 (Deadlock)

두 개 이상의 쓰레드 혹은 프로세스들이 상대방이 가진 자원을 기다리느라 아무런 작업도 진행하지 못한 상태로 무한 대기를 하는 문제

철학자에서의 교착

만일 모든 철학자들이 자기 왼쪽의 포크를 쥐고 있다면, 모든 철학자들은 오른쪽의 포크를 쥘 수 있을 때까지 기다려야 한다. 위의 과정을 생각해보면 철학자들은 영원히 오른쪽 포크를 기다리고 있을 것이다. 이것이 교착상태이다.

데드락 발생 조건

상호 배제(Mutual Exclusion) : 한 자원에 대한 여러 프로세스의 동시 접근 불가
점유 대기(Hold and Wait) : 한 프로세스가 할당된 자원을 가진 상태에서 다른 프로세스가 사용하고 있는 자원의 반납을 기다림
비선점(No preemption) : 다른 프로세스가 이미 점유한 자원을 강제로 뺏어 오지 못함
순환 대기(Circular Wait) : 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있는 것

데드락 해결법

예방 : 시스템 처리량이나 효율성이 떨어질 수 있다.
- 상호 배제 조건 예방
  - 여러 프로세스가 공유 자원을 한 번에 사용할 수 있게 한다.
  - 문제점 : 동기화 관련 문제가 발생할 수도 있다.
- 점유 대기 조건 예방
  - 프로세스 수행 시 필요 자원을 모두 요구하고 해당 자원들을 모두 점유하기 전에는 작업을 실행하지 않는 방법
  - 문제점 : 프로세스에 필요한 자원 확인에 필요한 비용, 자원에 대한 내용 저장 및 복원을 위한 비용, 무한 대기 등의 문제가 생긴다.
- 비선점 조건 예방
  - 다른 프로세스에 할당된 자원에게 선점권이 없을 때, 우선 순위가 높은 프로세스가 해당 자원을 선점할 수 있게 한다.
- 순환 대기 조건 예방
  - 자원을 순환 형태로 대기하게 하지 않고 한 쪽 방향으로만 자원을 요구할 수 있도록 한다.
  - 자원에 고유 번호를 할당하여 그 순서대로 자원을 요구한다.
회피
- 데드락이 발생할 가능성이 있는 지 없는 지 운영체제가 검사하고 가능성이 없을 경우에만 자원을 할당해 문제 발생을 피하는 방법이다.
- 안전 상태(Safe State)
  - 시스템이 프로세스들의 요구 자원의 데드락을 발생시키지 않으며 차례로 모두 할당할 수 있는 상태이다.
- 안전 순서(Safe Sequence)
  - 프로세스들에게 자원을 할당할 때 데드락이 발생하지 않는 순서를 찾을 수 있는 상태이다.
- 불안전 상태(Unsafe State)
  - 데드락이 발생할 수 있는 상태이다.
- 은행원 알고리즘
  - 기본적으로 안전 상태를 유지할 수 있는 요구만을 수락하며 불안전 상태를 초래할 사용자의 요구는 거절하는 상태이다.
  - 은행은 항상 최소 한 명의 고객에게 대출해줄 수 있는 금액을 보유하고 있어야 한다는 개념의 알고리즘이다.
  - 예시
    - 42은행이 대출해줄 수 있는 금액 900만원을 보유 중이다.
      - 고객 A, B, C가 42은행을 찾아와 대출을 요구한다.
      - A는 600만원의 대출이 필요하다.
      - B는 500만원의 대출이 필요하다.
      - C는 400만원의 대출이 필요하다.
    - 은행이 A, B, C 모두에게 200만원 씩 대출해준다.
      - 은행은 300만원을 보유 중이다.
      - A는 400만원의 대출이 더 필요하다.
      - B는 300만원의 대출이 더 필요하다.
      - C는 200만원의 대출이 더 필요하다.
    - 여기서 은행은 두 가지 선택을 한다.
      1. B에게 300만원을 빌려준 뒤 상환 받는다. → 상환 받은 돈을 A, C에게 적절히 빌려준다.
      2. C에게 200만원을 빌려준 뒤 상환 받는다. → 상환 받은 돈을 A, B에게 적절히 빌려준다.
    - 이처럼 모든 고객에게 빌려준 뒤 다시 돌려받을 수 있을 때를 안전상태 라고 한다.
    - 만약 처음 상황에서 A에게만 350만원을 대출해줬다면 은행은 B, C가 요구하는 돈을 빌려줄 수 없게 된다. 이는 불안전 상태 혹은 데드락 상태이다.
  - 은행원 알고리즘의 단점
    - 할당할 수 있는 자원의 수가 일정해야 한다.
    - 사용자의 수가 일정해야 한다.
    - 항상 불안전 상태를 방지해야 하기 때문에 자원 이용도가 낮다.
    - 최대 자원 요구량을 미리 알아야 한다.
    - 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.
탐지하여 회복
- 예방이나 회피법을 사용하지 않았을 때엔 데드락이 발생했을 때 이를 탐지하고 회복하는 방법을 사용했다.
- 탐지 기법
  - Allocation, Request, Avilable 등으로 데드락이 발생했는 지 여부를 탐색한다. 은행원 알고리즘과 유사하게 현재 시스템 자원 할당 상태를 가지고 파악한다.
  - 자원 할당 그래프를 이용하여 탐지한다.
- 회복 기법
  - 탐지 기법을 통해 발견했다면 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용한다.
  1. 프로세스를 1개 이상 중단시키기
    - 교착 상태에 빠진 모든 프로세스를 중단 : 계속 연산 중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기되는 부작용이 생길 수도 있다.
    - 프로세스를 하나 씩 중단 시킬 때 마다 탐지 알고리즘으로 데드락을 탐지하며 회복 : 매 번 탐지 알고리즘을 호출 및 실행해야 하기 때문에 부담이 된다.
  2. 자원 선점하기
    - 프로세스에 할당된 자원을 선점, 교착 상태를 해결할 때까지 해당 자원을 다른 프로세스에 할당해 주는 방법이다.

LiveLock

두 쓰레드가 락의 해제와 획득을 무한히 반복하는 상태이다.
보통 데드락을 피하려는 의도에서 수정한 코드가 불완전해질 때 발생
현재 자원으로 실행할 수 없어 내려 놓았다가 다시 다른 자원을 가져오는 상황이 똑같이 반복되는 경우 일어난다.

---

실재 알고리즘

동시성 프로그래밍의 가장 큰 숙제는 ‘공유자원 관리’일 것이다. 공유자원을 안전하게 관리하기 위해서는 상호배제(Mutual exclusion)를 달성하는 기법이 필요하다.

뮤텍스와 세마포어는 이를 위해 고안된 기법으로 서로 다른 방식으로 상호배제를 달성한다.

이 기법들을 쓰더라도 데이터 무결성을 보장할 수 없으며 데드락이 발생할 수도 있다.

// 처음 인자를 초기화
int	ft_philo_input(t_game *game, char *argv[], int argc)
{
//철학자 수
	game->philo_num = ft_atoi(argv[1]);
    // 죽는데 걸리는 시간
	game->time_to_die = ft_atoi(argv[2]);
    // 먹는데 걸리는 시간
	game->time_to_eat = ft_atoi(argv[3]);
    // 자는데 걸리는 시간
	game->time_to_sleep = ft_atoi(argv[4]);
    // 모든 철학자가 반드시 먹어야 하는 양
	game->must_eat_num = 0;
    // 죽은 철학자 수
	game->die = 0;
    // 먹은 철학자 수
	game->eat_check = 0;
    // 시작 시간 측정
	game->start_time = 0;
    // 인자가 정상적으로 들어왔는지 체크
    // 철학자는 2명 이상 200명 이하
    // 죽는 시간은 60 이상
    // 먹는 시간은 60 이상
    // 자는 시간은 60 이상
	if (ft_check_init(game))
		return (-1);
    // 반드시 먹어야 하는 숫자가 들어온경우
	if (argc == 6)
	{
		game->must_eat_num = ft_atoi(argv[5]);
		if (game->must_eat_num <= 0)
			return (-1);
	}
    // 뮤택스락 초기화
	if (ft_mutex_init(game))
		return (-1);
    // 각각의 철학자객체형으로 생성
	if (ft_philo_init(game))
		return (-1);
	return (0);
}

// 뮤택스락 초기화
int	ft_mutex_init(t_game *game)
{
	int	idx;
    // write 뮤택스락 초기화, NULL은 특성인데 여기에서는 넣지 않음
	if (pthread_mutex_init(&(game->write), NULL))
		return (-1);
    // eating 뮤택스락 초기화, NULL은 특성인데 여기에서는 넣지 않음
	if (pthread_mutex_init(&(game->eating), NULL))
		return (-1);
    // 게임의 포크를 철학자의 수만큼 초기화
	game->forks = malloc(sizeof(pthread_mutex_t) * game->philo_num);
	if (!(game->forks))
		return (-1);
	idx = 0;
    // 각 철학자들의 포크의 뮤택스락 초기화, 이렇게 해야 사용할 수 있으니
	while (idx < game->philo_num)
	{
		if (pthread_mutex_init(&(game->forks[idx]), NULL))
			return (-1);
		idx++;
	}
	return (0);
}

// 처락자 초기화
int	ft_philo_init(t_game *game)
{
	int	idx;

	idx = 0;
    // 게임의 philo 초기화
	game->philo = malloc(sizeof(t_game) * game->philo_num);
	if (!(game->philo))
		return (-1);
    // 게임에 있는 철학자들 초기화
	while (idx < game->philo_num)
	{
		game->philo[idx].id = idx;
		game->philo[idx].left_fork = idx;
		game->philo[idx].right_fork = (idx + 1) % game->philo_num;
		game->philo[idx].check_d_time = 0;
		game->philo[idx].eat_cnt = 0;
		game->philo[idx].game = game;
		idx++;
	}
	return (0);
}

---

// 실재 함수의 시작
int	ft_philo_start(t_game *game, t_philo *philo)
{
	int		i;
	void	*v_philo;

	i = 0;
	// 시작시간 측정
	game->start_time = ft_time();
	while (i < game->philo_num)
	{	
        // 죽는 시간을 측정하기 위한 시작 시간 측정
		philo[i].check_d_time = ft_time();
        // philo를 직접 건들기 위한 포인터
		v_philo = (void *)&(philo[i]);
        // 스레드를 만들어서 실행
		if (pthread_create(&(philo[i].thread_id), NULL, ft_pthread, v_philo))
			return (-1);
		i++;
	}
	ft_death_check(game, game->philo);
	ft_end_philo(game, game->philo);
	return (0);
}

// pthread_create로 스레드가 생성되고 실행되는 함수
void	*ft_pthread(void *philo)
{
	t_game	*game;
	t_philo	*philo_copy;

    // 철학자나 게임 모두 복제품을 사용
	philo_copy = (t_philo *)philo;
	game = philo_copy->game;
    // 짝수 철학자는 잠시 대기 0.01 초
    // 이 방식으로 붙어 있는 철학자가 한번에 critical section에 들어가는 걸 막는다
	if (philo_copy->id % 2)
		usleep(10000);
    // 게임이 끝나지 않은 한 반복하며 스레드 사용
	while (!(game->die))
	{
        // 밥먹으러 간다
		if (ft_philo_do(game, philo_copy))
			break ;
		ft_printf(game, "is sleeping", philo_copy->id);
        // 다 먹었으면 잔다
		ft_sleeping_time(game);
		ft_printf(game, "is thinking", philo_copy->id);
	}
	return (0);
}

// 밥먹으러가기
int	ft_philo_do(t_game *game, t_philo *philo)
{
    // 왼쪽 포크 들기
	pthread_mutex_lock(&(game->forks[philo->left_fork]));
	ft_printf(game, "has taken a fork", philo->id);
    // 오른쪽 포크 들기
	pthread_mutex_lock(&(game->forks[philo->right_fork]));
	ft_printf(game, "has taken a fork", philo->id);
    // 밥 먹기
	ft_philo_eat(philo->game, philo);
    // 왼쪽 포크 내리기
	pthread_mutex_unlock(&(game->forks[philo->left_fork]));
    // 오른쪽 포크 내리기
	pthread_mutex_unlock(&(game->forks[philo->right_fork]));
	if (game->eat_check)
		return (-1);
	return (0);
}

// 밥처먹기
void	ft_philo_eat(t_game *game, t_philo *philo)
{
    // 밥 먹는 상태 잠그기
	pthread_mutex_lock(&(game->eating));
	ft_printf(game, "is eating", philo->id);
    // 내가 이제 곧 죽을테니 미리 현재 시간 기록하기
	philo->check_d_time = ft_time();
    // 밥 그만 먹기
	pthread_mutex_unlock(&(game->eating));
    // 내가 밥 먹은 횟수 올리기
	(philo->eat_cnt)++;
    // 밥 다 처먹을때까지 대기
	ft_eating_time(game);
}

---

// 밥 처먹은 시간
void	ft_eating_time(t_game *game)
{
	long long	eat_time;
	long long	start_e_time;
	long long	now_e_time;

    // 게임에서 원래 먹기로 한 시간
	eat_time = (long long)(game->time_to_eat);
    // 현재 먹는 시간 측정
	start_e_time = ft_time();
	while (!(game->die))
	{
        // 현재의 먹는 시간 측정
		now_e_time = ft_time();
        // 먹는시간이 충족되면 종료
		if ((now_e_time - start_e_time) >= eat_time)
			break ;
        // 0.00001 초 대기
		usleep(10);
	}
}

// 처 자는 시간
void	ft_sleeping_time(t_game *game)
{
	long long	sleep_time;
	long long	start_s_time;
	long long	now_s_time;

    // 게임에서 원래 자기로 한 시간
	sleep_time = (long long)(game->time_to_sleep);
    // 현재 자는 시간 측정
	start_s_time = ft_time();
	while (!(game->die))
	{
        // 현재의 자는 시간 측정
		now_s_time = ft_time();
        // 자는시간이 충족되면 종료
		if ((now_s_time - start_s_time) >= sleep_time)
			break ;
        // 0.00001 초 대기
		usleep(10);
	}
}

---

// 메인 프로세스에서 하는 일 1
void	ft_death_check(t_game *game, t_philo *philo)
{
	int		i;

	while (!(game->eat_check))
	{
		i = 0;
        // 모든 필로소퍼를 돌아다니며 체크
		while ((i < game->philo_num) && (!(game->die)))
		{
			pthread_mutex_lock(&(game->eating));
            // 죽는 시간을 넘겨버리면 죽여버리기
			if ((ft_time() - philo[i].check_d_time) > game->time_to_die)
			{
				ft_printf(game, "died", i);
				game->die = 1;
			}
			pthread_mutex_unlock(&(game->eating));
			i++;
		}
		if (game->die)
			break ;
		ft_eat_check(game, game->philo);
	}
}

// 메인 프로세스가 해야하는 일 2
void	ft_eat_check(t_game *game, t_philo *philo)
{
	int	i;

	i = 0;
    // 최대 식사 횟수가 정해져 있을때
    // 이미 다 먹지 않은 철학자 골라내기
	while (game->must_eat_num != 0 && i < game->philo_num
		&& philo[i].eat_cnt > game->must_eat_num)
		i++;
    // 만약 모든 철학자가 식사 횟수를 채웠다면 끝내기
	if (i == game->philo_num)
		game->eat_check = 1;
}

---

테스트

5 800 200 200 7

4 410 200 200

외부에서 건들이지만 않으면 왠만해서는 안죽는다.

time_to_sleep 만큼 재울경우는 결국 죽게 되므로 좋은 선택이라고 볼 수 없다.

10000도 간혹가다 죽는다.

4 310 200 100

왼오 -> 왼오

오히려 금방 죽은것을 볼 수 있었다.

짝수에 대해 쉬는 시간에 제한을 두었지만 금방 죽었다.

728x90

저작자표시 비영리 변경금지

'Others > 42Seoul' 카테고리의 다른 글

push_swap 개발회고 (0)	2022.04.09
push_swap (0)	2022.03.11
Alumni Board 만들기 (0)	2022.02.18
[42] minitalk_2022 코드 복기 (0)	2022.02.17
BLIND CLONE CODING 4일차 (0)	2022.01.30

Bongsun's Cloud

철학자 문제

Philosophers (notion.site)

문제설명

Concepts

Basic Rules

필수 개념

Semaphore / Mutex

Critical Section

Semaphore

뮤텍스(Mutex)

데이터 레이스란?

교착 (Deadlock)

철학자에서의 교착

데드락 발생 조건

데드락 해결법

LiveLock

실재 알고리즘

테스트

'Others > 42Seoul' 카테고리의 다른 글

티스토리툴바

철학자 문제

Philosophers (notion.site)

문제설명

Concepts

Basic Rules

필수 개념

Semaphore / Mutex

Critical Section

Semaphore

뮤텍스(Mutex)

데이터 레이스란?

교착 (Deadlock)

철학자에서의 교착

데드락 발생 조건

데드락 해결법

LiveLock

실재 알고리즘

테스트

'Others > 42Seoul' 카테고리의 다른 글

관련글

티스토리툴바