Philosophers → 식사하는 철학자 문제

date

Mar 23, 2023

slug

philo

author

status

Public

philo_one (스레드와 뮤텍스 이용)

포크들은 철학자 옆에 놓여있다. 무슨 말이냐면 철학자 - 포크 - 철학자 - 포크 - ... 순으로 놓여있어 철학자 양 옆에 포크가 위치한다는 말이다.

mutex를 사용해서 제한된 포크 개수로 모든 철학자들이 굶어 죽는 일이 없도록 한다.

철학자는 스레드로 동작한다.

사용 가능한 함수

memset
printf
malloc
free
write
usleep
gettimeofday
pthread_create
pthread_detach
pthread_join
pthread_mutex_init
pthread_mutex_destroy
pthread_mutex_lock
pthread_mutex_unlock

philo_two (스레드와 세마포어 이용)

포크들은 모두 테이블 중앙에 있다.

semaphore를 사용해서 제한된 포크 개수로 모든 철학자들이 굶어 죽는 일이 없도록 한다.

철학자는 스레드로 동작한다.

사용 가능한 함수

memset
printf
malloc
free
write
usleep
gettimeofday
pthread_create
pthread_detach
pthread_join
sem_open
sem_close
sem_post
sem_wait
sem_unlink

philo_three (자식 프로세스와 세마포어 이용)

포크들은 모두 테이블 중앙에 있다.

semaphore를 사용해서 제한된 포크 개수로 모든 철학자들이 굶어 죽는 일이 없도록 한다.

철학자는 자식 프로세스로 동작한다.

사용 가능한 함수

memset
printf
malloc
free
write
usleep
gettimeofday
fork
kill
exit
waitpid
pthread_create
pthread_detach
pthread_join
sem_open
sem_close
sem_post
sem_wait
sem_unlink

gettimeofday()

gettimeofday 시스템 콜은 settimeofday와 함께 널리 쓰이는 시스템 시간을 구하는 (settimeofday는 시스템 시간을 설정하는) 시스템 콜이다.

컴퓨터에서의 내부적인 시간(년월일)은 보통 유닉스 시간 (POSIX 시간이라고도 부름)을 기준으로 한다. 유닉스 시간은 1970년 1월 1일 0시 0분 0초를 기준(그리니치 표준시 기준)으로 현재 시간까지의 차를 초로 표현한 것이다.

예를 들면 2021년 4월 12일 am 2시는 1618161487로 나타낼 수 있으며 이 수치는 1970년부터 현재까지의 지난 초 수치를 나타낸 것이다.

gettimeofday이든 settimeofday이든 유닉스 시간 기준으로 시간을 다룬다.

인수로 주어지는 구조체에 현재 시간과 시간 위치 정보 (타임존)를 이용해서 시간을 읽거나 쓴다. timezone은 잘 사용하지 않으므로 NULL로 넣어도 괜찮다.

이 시스템 콜을 이용해서 타이머처럼 사용한다. (코드와 코드 사이 간 절대적인 시간으로 얼마나 흘럿는지 파악한다.)

usleep()

메뉴얼 (man 3 sleep)을 참조하면 usleep 함수는 suspend thread execution for an interval measured in microseconds 라고 설명되어 있다. 인수로 주어진 초 만큼 스레드의 실행을 잠시 중단한다는 의미이다.

여러 포럼 등을 참조해 보면 sleep는 절대 정확하지 않다. 괄호 내 이상의 시간을 sleep 시켜주는 것을 보증해 줄 뿐이며 스레드의 실행을 늦추는 것이기 때문에 다른 스레드에 밀려 더 늦게 실행되는 경우도 있는 것 같다.

sleep 함수의 자세한 구현방식은 운영체제나 라이브러리마다 다른것 같으며 너무 방대한 내용이기 때문에 위 영어 설명 정도로만 이해하면 될 듯 하다.

아마도 이 함수는 철학자들이 소비하는 시간에서 busy waiting을 사용하지 않기 위해 사용하는 듯 하다. 하지만 이 함수는 부정확하기 때문에 slack 포럼을 참조해본 결과 큰 오차로 인해 그냥 busy waiting을 사용하는 분들도 계시는 듯 하다.

pthread

pthread는 posix thread이다. 유닉스나 리눅스에서 표준적으로 스레드를 생성할 때 사용하는 라이브러리이다.

컴파일을 할 때 스레드 라이브러리를 링크해야 한다.

FSM (Finite-State Machine / 유한 상태 기계)

기계 혹은 프로그램 혹은 함수 등이 어떠한 사건으로 인해 상태가 변환이 되고 그 순간에 하나의 상태를 가지게 되는 것을 유한 상태 기계라고 한다.

FSM은 보통은 FPGA 등을 이용해 논리회로를 설계할 때 주로 사용하는 개념이다.

학부생 때 논리회로 시간에 배운 개념이 생각나서 철학자는 특정 순간의 특정 상태를 가지며 특정 사건에 따라 상태가 변화하므로 FSM이 연상되어 FSM처럼 구현하였다.

Deadlock 회피 방법

만약 철학자들이 같은 시간에 같은 방향의 포크를 든다면 바로 교착 상태에 빠지게 될 것이며 모든 철학자들은 굶어 죽을 것이다. 식사하는 철학자 문제에서 가장 기본적으로 교착 상태를 회피하는 방법은 철학자 순서를 짝/홀수 그룹으로 구분하여 한 그룹이 왼쪽 포크를 먼저 집는다면 다른 그룹은 오른쪽 포크를 집게 한다. 이 방법으로는 교착 상태는 회피할 수 있다. (당연히 포크를 집고 놓는 행동은 원자화해야 한다.)

기아상태 억제 방법

하지만 위 방법으로 기아 상태를 충분히 방어하지 못한다. 예를 들면 철학자가 5명일 때 위 방법을 적용하면 얼마 안 가 어느 한 철학자는 굶어 죽을 것이다. 애초에 조건을 절대로 기아상태를 막을 수 없도록 주어지는 경우를 제외하고는 최대한 기아상태를 억제하여야 한다. (조건이 다양하고 자원이 한정되어 있는 동기화 문제에서 기아상태를 아예 방지하는 방법은 보통 없다고 한다. Trade-Off 하여야 한다.)

보통 이 상황에서 가장 좋은 방법은 철학자들에게 우선순위를 부여하여 기아상태가 비교적 오래 지속된 철학자에게 포크를 집을 권리를 부여한다. 하지만 이 과제에서 철학자들 간 소통은 불가하므로 이 방법은 사용하면 안된다.

C에서 thread를 생성하면 매우 빠른 속도로 생성되므로 거의 동시에 생성되는 것처럼 보인다. 그래서 철학자를 여러 명 만들 때 그 많은 철학자들이 거의 동시에 식사를 하려 할 것이다. 철학자가 홀수명일 때 데드락은 걸리지 않더라도 어느 한 철학자는 포크 집는 타이밍이 어긋나 잡지 못하게 될 것이다.

이를 최대한 억제하려면 철학자 스레드가 생성될 때 약간의 딜레이를 주어 철학자들이 약간의 간격을 가지고 생성하게 한다.

시행착오

데드락을 회피하기 위해 짝/홀수로 구분할 때 철학자들이 약간의 간격을 가지면 프로세스가 기아 상태에 빠질 확률이 커진다. 철학자들의 비대칭성과 철학자들의 생성 시간 차가 기아를 유발하게 된다. 만약에 철학자의 생성시에 딜레이를 주게 되면 철학자들이 데드락에 빠질 수 없기 때문에 이런 상황에서는 짝수/홀수 구분을 하면 안된다.

시행착오 2

위 시행착오를 겪고 다양한 테스트케이스에서 동작시켰다. 하지만 스레드 간 지연 혹은 문맥 전환에 따른 지연 등으로 데드락이 발생가는 문제가 발생한다. 이런 상황을 해결하기 위해 다시 짝/홀수를 구분하는 기능을 넣었다. 그리고 포크를 내려놓을 때 기존엔 하나씩 내려놓았지만 중간에 다른 스레드가 접근을 할 수도 있는 문제가 있어 스레드를 공통으로 묶어 완전히 한 순간에 내려 놓는 식으로 변경하였다. 또 딜레이를 유동적으로 부여하게 변경하였다.

philo_two 시행착오

philo_one은 한 스레드에서 감시까지 처리하게 하였다. 가능한 이유는 철학자 하나당 하나의 포크가 부여되기 때문이다. 하지만 philo_two는 포크의 개수를 세마포어로 관리해야 한다. 이게 왜 문제가 되냐면 만약에 포크를 모두 사용하고 있으면 블록킹이 되기 때문에 스레드 내에 별도의 감시용 스레드를 하나 더 만들어야 한다.

philo_three 시행착오

세마포어 S (sem_t 자료형)가 정수라고 해도 함부로 정수로 캐스팅해서 접근하면 안된다. 왜 안되는걸까? 커널단에서 거부하는건가? 아무튼 안된다. 모른다.

프로세스와 프로세스간의 통신은 세마포어만을 이용해서 동기화를 해야 하기 때문에 철학자간의 동기화는 1, 2번보다 더 까다롭다.

나는 부모 프로세스에서 자식 프로세스들 (철학자들)의 최소 식사 감지와 die 감지를 하는 스레드를 각각 만들어 감지하도록 했다. 철학자 프로세스는 die되면 종료되며 종료 여부는 waitpid로 판단하게 했다. 최소 식사 감지는 세마포어 blocking 여부로 확인하게 했다.

context switch와 usleep의 균형

스레드든 프로세스든 멀티태스킹을 할 때 context switch가 발생한다. context switch 자체로 당연히 오버헤드가 있지만 내가 보기엔 가장 문제가 되는 점은 태스크들을 운영체제가 관리하기 때문에 여러 개의 프로세스나 스레드들이 wait 상태로 빠질 때 정확히 언제 나올지 모른다는 것이다.

이게 이 과제에서 가장 큰 걸림돌이 되는 문제이다. 스레드나 프로세스를 조금만 생성하면 해결할 수 있지만 (하지만 이는 실행환경에 따라 큰 차이가 있다. 또 이는 근본적인 해결방안이 되지 않는다.) 스레드나 프로세스가 꽤 많이 생겨 그 프로세스들을 모두 실행하는데 지연이 생기는 것이 문제이다.

예를 들어 주기적으로 (10ms) 상태를 갱신해야 하는 프로세스가 여러 개 있으면 이 프로세스들을 스케줄링 하는 도중에 10ms를 초과하는 경우가 발생할 수도 있다.

시간을 측정하는 구문에서 보통은 while과 usleep을 조합해 비교적 정확하게 시간 측정을 되도록 할텐데 이런 경우에 조심해야 한다. 문맥 전환이 많을수록 오차가 심해질 수도 있다.