philosophers[철학자] - 룰 그리고 쓰레드, 뮤텍스, 세마포어, 프로세스

0. 프로젝트 목표

쓰레드와 뮤텍스를 사용하여 공유 메모리에 대한 처리 하기

쓰레드와 세마포어를 사용하여 공유 메모리에 대한 처리 하기

프로세스와 세마포어를 사용하여 프로세스간 동기화에 대한 처리 하기

 

 

 

1. 기본 룰

dining philosophers problem : https://selvarajahkesavan.medium.com/the-dining-philosophers-problem-de586df365bc

1) 철학자들이 둥근 테이블에 앉아 있음

2) 3가지 상태가 존재함 (eat, sleep, think : 동시상태는 없음)

3) 중앙에 스파게티 접시가 있고, 철학자 수만큼의 포크가 존재

4) 한 철학자당 포크 2개로 식사를 함

5) 각 철학자들은 서로 말도 못하고, 상태확인도 하지 못함 (포크만 보는 것)

6) 철학자는 먹고 나서 포크를 두고 잠 (eating -> sleeping)

7) 철학자는 자고 나서 생각함 (sleeping -> thinking)

8) 이 시뮬레이션은 한명의 철학자가 죽으면 끝남

9) 혹은 인자로 [모든 철학자가 꼭 먹어야하는 식사 수]를 만족하면 시뮬레이션은 멈춤

10) 인자는 다음과 같음

 ex) 철학자수 수명 먹는시간 자는시간 [모든 철학자의 식사 수]

 ex)   5 800 200 200 [7]

11) 각 철학자는 고유번호를 1부터 받음

12) N - 1, N, N + 1 순으로 앉아 있음

13) 상태변화시에 출력이 되어야하고, 출력이 섞이면 안됨

 ex) 시간 철학자고유번호 상태

 ex) 800 1 is eating

14) 죽은 상태와 죽었다는 프린트가 10ms을 초과할 수 없음

 

-> 과제의 목표는 쓰레드, 뮤텍스, 세마포어, 프로세스를 활용하여

-> 언제 철학자들이 상태변화를 하고, 철학자가 죽었는지 안죽었는지 파악하며 시뮬레이션 함

 

 

 

2. 사용하는 함수들

시간함수, 쓰레드함수, 뮤텍스함수, 세마포어함수가 존재

malbongcode.tistory.com/160

philosophers - 외부함수 정리하기

 

3. philo_one VS philo_two VS philo_three

philo_one

1) 각 철학자는 쓰레드로 구성

2) 포크는 양쪽 옆에 있음

2) 포크는 뮤텍스로 보호함

-> 뮤텍스로 쓰레드가 접근하는 것을 제어할 수 있냐?

 

philo_two

1) 각 철학자는 쓰레드로 구성

2) 포크는 테이블 중간에 있음

3) 포크는 세마포어로 보호함

-> 세마포어로 쓰레드가 접근하는 것을 제어할 수 있냐?

 

philo_three

1) 각 철학자는 프로세스로 구성

2) 포크는 테이블 중간에 있음

3) 포크는 세마포어로 보호함

-> 프로세스와 세마포어로 동기화 할 수 있냐?

 

 

 

4. 쓰레드와 뮤텍스

쓰레드

출처: https://developerhenrycho.tistory.com/17

 - 스레드는 어떠한 프로그램 내에서, 특히 프로세스 내에서 실행되는 흐름의 단위를 말한다 (위키)

 - 예시) 입력만 받는 쓰레드, 출력만하는 쓰레드

 - 처리량을 올릴 수 있음

 - 동시에 여러개의 쓰레드를 만들어서 여러가지일을 한번에 처리할 수도 있음

 - 허나, 쓰레드가 하나의 메모리를 동시에 접근한다면?

  -> A쓰레드는 전역변수a를 10으로 수정하는데

  -> 그와 동시에 B쓰레드가 전역변수a를 0으로 수정한다면?

  -> 공유메모리 문제 -> 그것을 뮤텍스로 보호

 

 

뮤텍스

뮤텍스 출처: https://frontjang.info

 - 상호 배제(mutual exclusion, Mutex, 뮤텍스)는 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 것 (위키)

 - 예시) 전역변수a에 해당하는 뮤텍스를 A쓰레드가 가지고 있다면 수정하고, B쓰레드는 전역변수a에 대한 뮤텍스를 가질 때까지 대기함

 - 나는 권한, 소유권이라고 생각하고 사용함

 - philosophers에서 각각의 포크가 뮤텍스로 보호되고 있으므로, 두 철학자가 하나의 포크를 두고 싸우지 않게 뮤텍스로 보호하는 것

 

 

 

5. 쓰레드와 세마포어

출처: https://sycho-lego.tistory.com/11

세마포어

 - philosophers에서는 named semaphore를 사용함 (이름있는 세마포어), 파일로 관리되는 듯

 - 기본적으로 공유자원에 대한 접근을 제어한다는 면에서 뮤텍스와 동일

 - 세마포어는 뮤텍스와 달리 공유자원에 대한 접근을 "value개 만큼 접근"하게 해줌 (뮤텍스는 하나)

 - 세마포어는 뮤텍스와 달리 쓰레드뿐만아니라 프로세스 동기화에도 영향을 미침

 - 세마포어는 뮤텍스와 달리 자신 가지고 있지 않은 것을 unlock해도 됨

  -> philo_one에서는 포크마다 뮤텍스를 두고, 각 철학자에게 l_fork, r_fork를 두어 왼쪽오른쪽 포크에 대한 뮤텍스 검사를 했다면 (양쪽에  포크가 있어야 하므로)

  -> philo_two에서는 포크 세마포어로 두고 value값을 포크 수만큼으로 설정하여, 각 철학자가 포크를 가져가면 됨 (포크들이 중앙에 있으므로)

 

 

 

6. 프로세스와 세마포어

 - 프로세스는 메모리 자원을 그대로 복제하고 독립하기 때문에 전역변수나 메모리로 동기화flag를 설정할 수 없음

 - 프로세스끼리 통신은 pipe를 주로 이용함

 - 여기서는 심지어 pipe도 이용하지 못함

 - 그래서 세마포어로 통신함

  -> "뮤텍스는 메모리, 세마포어는 파일"로 생각하면 프로세스끼리 세마포어로 통신할 수 있다는 것을 알게 됨

 - philo_three에서는 철학자들을 프로세스로 두고, 자신이 죽거나 [모든 철학자가 꼭 먹어야하는 식사 수]를 마치면

   세마포어를 unlock함 (post) -> 메인 프로세스에서 해당 세마포어를 얻어서 처리해주면 됨

 

 

7. 마무리 - 어려웠던점, 나만의 해결방법(옳은 방법이 아닐 수도)

 - 전반적인 쓰레드, 뮤텍스, 세마포어, 프로세스에 대한 이해가 부족하면 어려운 문제임

 - 또한 "어떻게 상태에 대한 동기화를 할 것인가"에 생각도 매우 중요한 과제

 - 시뮬레이션을 종료해야하는 상황이 발생하면(죽거나 다먹거나)

   -> 종료상태를 출력하고, 더 이상 출력을 막기위해 out에 대한 lock을 풀지 않음

 - 시뮬레이션을 계속 돌려보면, 오차가 발생하여 안죽어야 하는 상황에 죽는 경우를 늦추기 위해서 die체크를 3ms여유분을 둚

 - usleep()의 오차 문제를 해결하기 위해 많은 노력을 했고, 그 중에 가장 좋은 것은 usleep()함수를 나눠서 사용하는 것임

usleep(time * 1000); /* 이런식으로 사용하면 오차 발생 !!! */
 
/* 나눠서 사용하기 */
start = get_cur_time();
while (get_cur_time() - start < time)
    usleep(100);

 

philo_one

 - philo_one에서 어려웠던 점은 애초에 구조의 첫걸음이라서 구조잡기가 가장 힘들었음

 - 또한, 쓰레드에는 인자가 하나가 들어가는데 인자를 어떤식으로 넘겨야하는지에 대한 고민도 많이 함 (전역변수 사용하지 않음)

  -> 왜냐하면, 철학자가 자신의 넘버가 몇인지 알아야 하기 때문 (포크도 마찬가지)

  -> 결국 인자를 담고있는 구조체A와, 뮤텍스정보를 담고있는 구조체B를 만들고

  -> philos구조체 배열을 만들어서 philos[i]에 구조체A와 구조체B를 참조하는 변수를 둚

typedef struct        s_philo
{
   pthread_t         tid;
    int               num;
    int               r_fork;
    int               l_fork;
    int               eat_cnt;
    struct s_rule     *rule;
    struct s_mutex    *mutex;
    struct timeval    start_tv;
    struct timeval    life_tv;
}                     t_philo;

 

philo_two

- philo_two는 philo_one에서 사용한 뮤텍스를 세마포어로 변경해주면 문제를 해결함

  -> 허나, 세마포어에 대한 전반적인 이해가 없다면 작성하면 안됨

- 포크를 세마포어로 두면 philo_one보다 로직이 간단하다라는 것을 알 수 있음

 

philo_three

 - philo_three는 철학자를 프로세스로 사용한다는 점이 골치아픔

  -> 왜냐하면 프로세스끼리 통신은 파이프로 하는 것으로 알고 있기 때문

  -> 허용된 함수엔 pipe가 없고, 메모리는 복제되어 독립해서 존재하기 때문에 사용할 수도 없음

  -> 결국 남아 있는 것은 세마포어임

 - 그럼 어떻게 메인프로세스에서 철학자들의 죽음과, must_eat인자에 대한 캐치를 할 수 있냐면

  -> 자식 프로세스(철학자)에서 자신의 상태를 모니터하는 쓰레드를 만들고

  -> 만약, 그 쓰레드에서 철학자 수명이 다 되었으면 sem_post(die_semaphore)로 함

  -> 메인 프로세스에서는 sem_wait(die_semaphore)로 캐치하면 철학자의 죽음을 캐치할 수 있음

  -> 근데, "must_eat인자가 들어오면 must_eat캐치도 하고 die캐치도 해야한다면 어떻게 하지?" 라는 고민을 하게 됨

  -> 일단, must_eat캐치는 철학자 프로세스의 모니터하는 쓰레드에서 must_eat만큼 먹었다면 sem_post(eat_semaphore)를 함

  -> 메인 프로세스에서는 sem_wait(eat_semaphore)를 철학자 수만큼 세마포어를 잡으면 되는 것

 - 그럼 sem_wait(die_semaphore)도 하고, sem_wait(eat_semaphore)도 하려면 메인 프로세스에서 쓰레드를 만들어야 함

  -> 허나, 만약 각각의 쓰레드를 join해서 종료할 때까지 대기한다면, 죽음을 캐치하더라도 must_eat쓰레드가 아직 wait중이라서 종료가 되지 않는 문제가 있음

  -> 그래서 나는 다음과 같이 해결함

  -> join은 die를 캐치하는 쓰레드만 join함

  -> eat을 캐치하는 쓰레드는, 만약 eat을 철학자 수만큼 캐치했다면, wait_post(die_semaphore)로 풀어줘서

  -> die도 캐치하게 하여 종료시킴

void        *wait_for_die(void *philos)
{
    t_philo    *phs;
 
    phs = (t_philo *)philos;
    sem_wait(phs->sem->die);
    return (philos);
}
 
void        *wait_for_eat(void *philos)
{
    int        i;
    t_philo    *phs;
 
    phs = (t_philo *)philos;
    i = 0;
    while (i < phs->rule->ph_num)
    {
        sem_wait(phs->sem->eat);
        i++;
    }
    sem_wait(phs->sem->out);
    printf("%ld\t\tall philos ate it!!!\n", get_time(phs->start_tv));
    sem_post(phs->sem->die);
    return (philos);
}
 
int            make_wait_thread(t_philo *phs)
{
    pthread_t    die;
    pthread_t    eat;
 
    if (pthread_create(&die, NULL, wait_for_die, (void *)phs))
        return (clear_all(phs, -1));
    if (pthread_create(&eat, NULL, wait_for_eat, (void *)phs))
        return (clear_all(phs, -1));
    pthread_join(die, NULL);
    return (SUCCESS);
}