뮤텍스를 사용하는 과제

방법 구상

스레드, 뮤텍스 관련 개념 및 함수 숙지
시간 관련 함수 사용 방법 숙지
명령행 인자를 구조체에 저장
교착 상태와 기아 상태를 어떻게 해결할 방법
뮤텍스로 임계구역을 보호
- 어떤 변수를 보호해야하는가?
- → reader, writer가 동시에 존재할 수 있는 변수
모니터링을 위한 별도의 스레드 설정
종료 상황의 인지 방법

구현 순서

인자 파싱
구조체 초기화
스레드 생성
스레드 종료 대기
자원 해제

구현 과정

순서도

문제 해결 방법

과제에서 신경써야 할 문제는 크게 세 가지로 나눌 수 있다.

경쟁 상태 (Race condition)
- 읽기와 쓰기가 동시에 일어날 수 있는 변수의 경우 mutex lock을 통해 한 번에 한 스레드만이 접근하도록 하였다.
교착 상태 (Deadlock)
- 홀수 철학자와 짝수 철학자가 포크를 집는 순서를 다르게 하여 모두가 같은 방향의 포크를 들고 대기하는 교착상태가 발생하지 않도록 해주었다.
기아 상태 (Starvation)
- 포크마다 마지막으로 사용한 철학자의 정보를 저장하여 식사를 마치고 생각중인 철학자가 식사를 못 한 철학자보다 포크를 먼저 집어 식사를 연이어 하는 일이 없도록 해주었다.

인자 파싱

인자의 개수 체크 : 4개 또는 5개인가?
인자의 값 체크 : int형이며 양수인가?
마지막 인자(식사 최소 횟수)의 처리 방법
- 별도의 플래그를 설정하여 마지막 인자의 존재 여부를 확인

구조체 초기화

뮤텍스 (mutex)

여러 스레드가 공유하는 변수 중 그 값을 수정할 변수나 한번에 한 스레드의 접근만을 허용해야 하는 함수는 mutex lock을 통해 보호
- 포크
- 사망 체크
- 출력 함수
- …

시간 관리

gettimeofday 함수를 사용하는 경우
- 시간의 초기값을 저장하는 용도
  - 이 함수는 1970년을 기준으로 한 시간을 반환한다. 프로그램의 시작시간을 기준으로 시간을 관리하려면 프로그램이 시작될 때의 gettimeofday의 반환값을 저장해야 한다.
- 각 철학자들의 식사 시간을 저장하는 용도
- 철학자의 상태를 출력하는 용도
- 기타 시간 관련 사용자 정의 함수에 사용하는 용도
현재 시간 확인
- 조건 : 밀리초로 표현해야함
- 문제 : gettimeofday()는 초, 마이크로초로 나타냄
  - 마이크로초 : 1/1,000,000 초
  - 밀리초 : 1/1,000 초
- 해결방법1 : 초 * 1000 + 마이크로초 / 1000과 같이 ms 형태로 만들어서 저장
- 해결방법2
  - 시간 구조체(struct timeval) 자체를 저장
  - 구조체의 초(tv_sec)와 마이크로초(tv_usec)를 각각 따로 연산해도 된다.
시간을 저장하는 위치
- 시간의 초기값 : 프로그램이 시작되는 시점에 1회 저장
- 철학자의 식사 시간 : 각 철학자 스레드가 생성될 때 1회, 매 식사를 시작할 때마다 저장

철학자 스레드 생성

뮤텍스를 먼저 만들고 철학자 스레드를 생성해준 이유
- 철학자 스레드가 시작되자마자 뮤텍스를 통해 경쟁상태를 방지해야하기 때문.

생성한 뮤텍스

fork : 포크를 한번에 하나씩 들도록 보호
print : 한번에 하나씩 결과가 출력되도록 보호
dead : 모니터링 스레드와 각 철학자가 동시에 접근하지 못하도록 보호

생각할 점

포크 자체를 뮤텍스로 설정하는 방식
(원문)
To prevent philosophers from duplicating forks, you should protect the forks state with a mutex for each of them.
(번역)
철학자들이 포크를 복제하는 것을 방지하기 위해 당신은 포크의 상태를 뮤텍스로 각각 보호해야 한다.
- 과제에서는 위와 같이 뮤텍스는 포크의 상태를 보호하기 위한 도구로써 사용하라고 명시되어 있기 때문에 포크 자체를 뮤텍스로 설정하는 것은 적절한 방법이 아니다.
해결 방안
- is_occupied와 같이 포크의 상태를 나타내는 변수를 설정
- 뮤텍스는 위 변수를 보호하는 용도로 사용

스레드

생성
- pthread_create으로 생성
함수
- 호출할 함수 지정
스레드 종류
- 철학자 스레드
- 철학자의 상태를 관찰할 스레드 (monitoring thread)

시뮬레이션

각 루틴의 소요시간

usleep()함수를 통해 해당 시간동안 딜레이를 준다.

문제점
- sleep 계열 함수는 프로세스 상에 CPU를 사용하는 스레드가 여러 개 존재하며 usleep의 시간이 짧은 경우 정확한 시간동안 sleep한다는 것을 보장할 수 없다.

해결방법

while 루프를 돌며 시간을 체크해가며 조금씩 usleep을 호출하는 함수를 통해 원하는 시간이 될 때까지 스레드를 대기시킨다.

함수 구현방법 1

어느정도의 시간(전체 시간의 80%)동안 usleep을 한 뒤에 남은 시간을 usleep(300)으로 채워나간다.

  
  void    msleep(useconds_t milliseconds)
  {
      uint64_t    begin_time;
        
      begin_time = get_time();
      usleep((milliseconds * 0.8) * K);
      while (begin_time + milliseconds > get_time())
          usleep(300);
  }

함수 구현방법 2

다음과 같이 남은 시간의 절반씩 usleep을 해나가다가 1ms가 남았을 때 남은 시간동안 usleep(100)으로 채워나간다.

  
  void    msleep(useconds_t milliseconds)
  {
      uint64_t    begin_time;
        
      begin_time = get_time();
      while (begin_time + milliseconds - get_time() > 1)
          usleep((begin_time + milliseconds - get_time()) * 0.5 * K);
      while (begin_time + milliseconds > get_time())
          usleep(100);
  }

Eating

포크 들기

기존 방법
- 철학자들이 mutex_lock에 블락된 채로 포크를 기다린다.
문제점
- mutex_lock에서 포크를 기다리는 동안 죽은 경우 제대로 처리하지 못한다.

해결책

포크의 상태를 나타내는 변수의 위, 아래에 mutex를 설정하여 상호배제를 보장해준다.
각 철학자는 while 루프가 시작되면 우선 entry section에서 블락되어 있는다.
이후 포크 mutex의 lock을 획득하면 critical section으로 진입한다.
그 후 조건문을 확인하여 포크를 현재 다른 철학자가 사용중이거나 자신이 제일 최근 사용자라면 mutex의 lock을 반환한다.
- 포크를 집을 수 있을 때까지 이 과정을 반복한다.
포크를 집을 수 있다면 포크의 상태 변수들을 변경하고 mutex를 unlock해준다.

  
  int pick_up_fork()
  {
      while (TRUE)
      {
          pthread_mutex_lock(&mutex);
          if (is_occupied == FALSE && recent_user != number)
          {
              is_occupied = TRUE;
              recent_user = number;
              pthread_mutex_unlock(&mutex);
              break ;
          }
          pthread_mutex_unlock(&mutex);
          usleep(500);
      }
      return (EXIT_SUCCESS);
  }

상태 출력
- 각 루틴을 수행할 때 철학자는 자신의 상태를 출력해야한다.
- 만약 어떤 철학자가 죽은 상황이라면 다른 철학자는 상태를 출력해서는 안된다.
- 따라서 함수의 시작부분에 누군가 죽었는지를 확인하는 조건문을 확인한다.
정해진 시간동안 usleep
포크 내려놓기

Sleeping

정해진 시간동안 usleep

Thinking

일어나서 먹기 전까지 대기하는 동안은 전부 thinking

모니터링 스레드

while 루프를 돌며 철학자가 죽었거나 다 먹었는지를 체크한다.

Dead 체크

반복문을 돌며 한명이라도 굶어죽었는지(포크를 기다리는 경우)를 확인한다.

Full 체크

반복문을 돌며 모든 철학자의 상태가 full인지를 체크한다.

메시지 출력

full 메시지

다른 메시지와 다르게 전체 철학자를 다 확인해야해서 print_state(t_philo *philo, t_state *state)로 넘기기엔 어려움이 있다.

방법 1 : 새로운 함수를 정의
방법 2 : 기존 함수를 활용
- 정적변수를 활용 : static pthread_mutex_t *mutex_print와 같이 설정하여 뮤텍스 주솟값을 변수에 저장해두어 해결
- 다 먹었다는 처리를 하기 전에 최소 한번은 philo 스레드에서 print_state함수를 호출(pick fock, eat 등)할 것이기 때문
  - 문제점 : must_eat_time 인자가 0회로 들어온 경우 philo 스레드가 pick fork 등의 출력을 하기 전에 모니터 스레드가 출력을 해야한다.
  - 해결방법 : 프로세스가 시작할 때 초기화 과정에서 출력 함수를 최초 1회 호출하여 뮤텍스의 주솟값을 저장해둔다.

에러 처리

방법

print_error 함수를 정의하고 각 구조체 안에 errno 멤버를 설정하여 구조체를 통해 에러 메시지 출력 후 할당받은 자원을 해제한다.

처리한 경우

인자 에러
- 1~4번 인자가 0 이하의 값이 들어온 경우
- 인자의 값이 int형의 범위를 넘어선 경우
- 인자의 개수가 4개 또는 5개가 아닌 경우
기타
- mutex init/destroy, thread create/join, malloc 등
  - 에러 메시지 출력 후 자원 해제

처리하지 않은 경우

pthread_mutex_lock
- 이유
  - 에러가 발생하는 원인을 확인해본 결과, 충분히 예방 가능하다고 판단하였다.
- 에러가 발생하는 경우
  - EAGAIN
    - mutex의 재귀 락 최대 횟수를 초과한 경우.
  - EINVAL
    - 프로토콜 속성 값을 PTHREAD_PRIO_PROTECT로 해서 mutex를 생성했으며 호출 스레드의 우선순위가 뮤텍스의 현재 우선순위 상한보다 높은 경우.
  - ENOTRECOVERABLE
    - 뮤텍스가 보호하는 상태가 복구 가능하지 않은 경우.
  - EOWNERDEAD
    - 뮤텍스가 견고 뮤텍스이며 이전 소유자 스레드를 포함한 프로세스가 뮤텍스 락을 잡은 채로 종료된 경우. 이 경우 호출 스레드가 뮤텍스 락을 획득하게 되며 상태를 정상으로 만드는 것은 새 소유자의 몫이다.
  - EDEADLK
    - 뮤텍스 유형이 PTHREAD_MUTEX_ERRORCHECK이며 현재 스레드가 이미 그 뮤텍스를 소유하고 있는 경우.
- 에러가 발생할 수도 있는 경우
  - EOWNERDEAD
    - 뮤텍스가 견고 뮤텍스이며 이전 소유자 스레드가 뮤텍스 락을 잡은 채로 종료힌 경우. 이 경우 호출 스레드가 뮤텍스 락을 획득하게 되며 상태를 정상으로 만드는 것은 새 소유자의 몫이다.
  - EDEADLK
    - 교착 조건을 탐지한 경우.

결과물

인자가 4 410 200 200 6인 경우
인자가 5 610 200 200 6인 경우
인자가 10 610 300 300 5인 경우

체크사항

코드 체크

경쟁 상태
교착 상태
기아 상태

예외 처리 체크

일정 시간이 지나도 살아있는지
1명이 들어올 경우
인자 전체 or 일부가 0으로 들어온 경우

실행 테스트

일반 케이스
- 철학자 짝수인 경우 : 죽는 시간이 먹는 시간의 2배
- 철학자 홀수인 경우 : 죽는 시간이 먹는 시간의 3배
특수 케이스
- 철학자 한명인 경우
- 철학자 199명인 경우
- 3분간 동작이 가능한지 여부
기본 테스트
- 죽는 경우
  - 1 800 200 200
  - 4 310 200 100
  - 4 200 205 200
- 안죽는 경우
  - 5 800 200 200 7
  - 4 410 200 200 10
  - 5 800 200 200
  - 5 600 150 150
  - 4 410 200 200
죽은 뒤에 출력이 안되는지
시간이 밀리지 않는지
Data race 발생 여부(-fsanitize=thread -g)
Memory leak 체크

문제점

인자가 3 310 100 100 3일 때 다음과 같은 메모리 접근 오류 발생
- 원인
  - full 상태에서 메시지를 출력하는 과정에서 문제가 발생
  - full인 상태에서는 monitor_thread에서 philo 매개변수에 NULL을 넣어서 print_state(NULL, FULL); 와 같이 출력 함수를 호출하는데 해당 함수에서 pthread_mutex_lock(&philo→info→mutex_print) 와 같이 NULL에 접근하여 발생하는 문제였다.
- 해결 방법
  - 출력 함수에서 NULL에 접근하지 못하도록 조건문을 설정해주고 뮤텍스 주솟값은 정적 변수로 처리하여, 인자가 들어오지 않았을 때도 뮤텍스 lock을 설정할 수 있도록 해결.
인자가 5 800 200 200 7일 때 다 먹었다고 출력 후에 끝나지 않는 문제
- 철학자 구조체 안에 full 출력 여부 플래그를 추가하여 해결
식사 시간이 긴 경우, 한 철학자가 죽은 후에도 오랜 시간 프로세스가 종료되지 않는 문제
- 원인
  - 식사 시간 또는 수면시간 동안 usleep 함수로 스레드를 대기시키기 때문에 발생하는 문제이다.
- 해결 방법
  - 직접 정의한 sleep 함수 내부의 while문에서 짧은 usleep을 1회 호출할 때마다 종료 여부를 확인한다.

Ref.

https://wariua.github.io/man-pages-ko/pthread_mutex_lock(3)/
https://stackoverflow.com/questions/38843556/is-it-suitable-to-use-usleep-as-timer-in-c

Philosophers ③ 구현 과정 (Mandatory part)