[42Seoul] 식사하는 철학자들

이 과제를 풀 던 당시, 노션에 정리한 내용을 옮긴 것이다. 이상한 점을 발견한다면 알려주세요!

목표

• 운영체제의 교착(Deadlock)상태를 설명하기 위한 문제인 식사하는 철학자를 이해하고 구현해보자.
• 스레드란 무엇인가를 말할 수 있다.
• 뮤텍스란 무엇인가를 말할 수 있다.
• 교착상태란 무엇인가를 말할 수 있다.

문제 설명

• 한 명 이상의 철학자가 둥근 테이블에 앉아 다음과 같은 세 행동 중 하나를 취합니다 : 먹기, 생각하기, 잠자기
• 철학자가 밥을 먹는 도중에는, 생각하거나 잠을 자지 않습니다. 마찬가지로 잠자는 도중에는 밥을 먹거나 생각할 수 없으며, 생각하는 도중에는 밥을 먹거나 잠들 수 없습니다.
• 철학자들은 둥근 테이블에 앉아있으며, 가운데에는 아주 큰 스파게티 그릇이 놓여 있습니다.
• 탁자 위에는 몇 개의 포크가 올려져 있습니다.
• 스파게티는 포크 하나만으론 집거나 먹기가 어렵기 때문에, 철학자들은 반드시 양 손에 포크를 쥐고 (2개의 포크를 사용하여) 먹어야 합니다.
• 철학자는 절대로 굶고 있으면 안 됩니다.
• 모든 철학자는 먹어야 합니다.
• 철학자들은 서로와 대화할 수 없습니다.
• 각 철학자는 다른 철학자가 언제 죽는지 알아챌 수 없습니다.
• 철학자가 밥을 다 먹었으면, 포크를 내려놓고 잠자기 시작합니다.
• 철학자가 잠을 다 잤으면, 생각하기 시작합니다.
• 철학자가 한 명이라도 사망하면 시뮬레이션이 종료됩니다.
• 각 프로그램은 같은 옵션을 가져야 합니다 : 철학자의 수, 철학자의 수명, 밥을 먹는데 걸리는 시간, 잠자는 시간, [각 철학자가 최소한 밥을 먹어야 하는 횟수] (number_of_philosophers time_to_die time_to_eat time_to_sleep [number_of_times_each_philosopher_must_eat])
  • 철학자의 수 (number_of_philosophers): 테이블에 앉아 있는 철학자의 수와 포크의 수
  • 철학자의 수명 (time_to_die): 밀리초 단위로, 철학자가 마지막으로 밥을 먹은 지 'time_to_die' 시간만큼이 지나거나, 프로그램 시작 후 'time_to_die' 시간만큼이 지나면 해당 철학자는 사망합니다.
  • 밥을 먹는데 걸리는 시간 (time_to_eat) : 밀리초 단위로, 철학자가 밥을 먹는 데 걸리는 시간입니다. 해당 시간동안, 철학자는 두 개의 포크를 소유하고 있어야 합니다.
  • 잠자는 시간 (time_to_sleep) : 밀리초 단위로, 잠을 자는 데 소모되는 시간입니다.
  • 각 철학자가 최소한 밥을 먹어야 하는 횟수 (number_of_times_each_philosopher_must_eat) : 해당 인자값은 선택사항입니다. 모든 철학자가 'number_of_times_each_philosopher_must_eat' 횟수만큼 밥을 먹었다면, 시뮬레이션이 종료됩니다. 해당 값이 명시되어 있지 않다면, 철학자가 한 명이라도 사망할 때까지 시뮬레이션은 계속됩니다.
• 각 철학자에게는 1부터 'number_of_philosophers' 만큼의 고유 번호가 부여됩니다.
• 철학자 1번은 철학자 'number_of_philosophers'번 옆에 앉습니다. 그 외에, N번 철학자는 N-1번 철학자와 N+1번 철학자 사이에 앉습니다.
• 철학자의 상태는 다음과 같은 형식으로 출력되어야 합니다. (X는 철학자의 고유 번호로 대체되어야 하며, timestamp_in_ms는 현재 타임스탬프가 밀리초 단위로 표시되어야 합니다.)
  • 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
• 철학자의 상태는 다른 철학자들의 상태와 뒤엉키거나 섞인 상태로 출력되면 안 됩니다.
• 철학자의 사망 시점과 이를 출력하기 까지의 틈이 10ms 이상이 되면 안 됩니다.
• 다시 말하지만, 철학자들이 최대한 죽지 않도록 설계해야 합니다!

회고

식사하는 철학자 문제는 멀티 스레드의 공유 자원을 관리하는 방법에 대해서 배울 수 있는 과제이다.

스레드와 프로세스는 공유자원에 동시에 접근해서는 안된다. 그래서 뮤텍스와 세마포어를 이용해서 공유자원에 접근 제한을 둬서 공유 자원을 관리하는 법을 배웠다. 뿐만 아니라, sleep 등을 사용하면서 스레드와 프로세스 상태에 대해서 배울 수 있는 시간이었다. 

개념

동시성 프로그래밍

동시성 프로그래밍이란 여러가지 작업들이 같은 시기에 함께 실행되도록 처리하는 것을 의미한다.

갑자기 운영체제를 하자면 컴퓨터는 여러작업을 동시(concurrency)에 처리하기 위한 작업이 필요하다.

여러분이 음악을 들으면서 타자를 치거나 게임을 하면서 알람앱을 키는것도 모두 동시성 프로그래밍의 증거이다.

상호배제

상호 배제란, 임계 구역을 어느 시점에서 단 한 개의 프로세스만이 사용할 수 있도록 하며, 다른 프로세스가 현재 사용 중인 임계 구역에 대하여 접근하려고 할 때 이를 금지하는 행위를 말합니다.

상호 배제를 하는 방법에는 잠금 방법이 있는데, 잠금은 하나의 프로세스가 임계구역(critical section)을 점유한 후에 다른 프로세스가 접근할 수 없도록 잠그는 것을 말한다. 뮤텍스가 바로 잠금에 해당한다.

 

뮤텍스로 아래 4가지 설정을 해서 교착상태를 해결하면서 과제를 진행해야한다.

 

1. 상호배타(Mutual Exclusion)

• 자원은 한 번에 하나의 프로세스에게만 할당될 수 있다.
• 철학자(Thread)는 식사를 하려면 포크(뮤텍스) 두개를 사용해야 한다. (뮤텍스가 상호베제 기법 중에 하나이다.)

2. 보유 및 대기(Hold and Wait)

• 프로세스가 어떤 자원을 가지고 있으면서, 다른 프로세스가 사용중인 또다른 자원을 대기하고 있다.
• 양쪽 철학자가 포크를 사용하고 있다면 포크를 다 쓸 때까지 대기하고 있어야한다.

3. 비선점(No Preemption)

• 다른 프로세스가 사용 중인 자원을 강제로 뺏을 수 없다.
• 다른 철학자가 사용 중인 포크를 강제로 뺏을 수 없다.

4. 환형대기(Circular Wait)

• 2번의 상황이 꼬리를 물고, 결국 맨 끝 프로세스가 맨 첫 프로세스에게 할당되어있는 자원을 대기하고 있는 원형의 상태.
• 데드락을 피하기 위해서는 환형대기를 피하게 설계를 해야한다. 그래서 짝수 스레드 먼저 실행을 시키고 usleep으로 약간의 시간 뒤에 홀수 스레드를 실행시키고 왼쪽 포크를 먼저 짚어야 오른쪽쪽 포크를 짚을 수 있게 하여 환형대기를 피하도록 하였다.

Mutext 뮤텍스

공유된 자원의 데이터 혹은 임계영역등에 하나의 프로세스 또는 스레드가 접근하는 것을 막아주는 상호배제 알고리즘 중에 하나이다. 임계구역(Critical Section)을 가진 스레드들의 실행시간(Running Time)이 서로 겹치지 않고 각각 단독으로 실행(상호배제_Mutual Exclution)되도록 하는 기술입니다.

한 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제 기법이고 Key에 해당하는 어떤 객체(Object)가 있으며, 이 객체를 소유한 스레드/프로세스만이 공유자원에 접근할 수 있습니다.다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 동기화(Synchronization) 또는 락(Lock)을 사용함으로써 뮤텍스 객체를 두 스레드가 동시에 사용할 수 없습니다.

Semaphore 세마포어

공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌 (동기화 대상이 하나 이상)

사용하고 있는 스레드/프로세스의 수를 공통으로 관리하는 하나의 값을 이용해 상호배제를 달성합니다. 공유 자원에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근할 수 있으며, 각 프로세스는 세마포어의 값을 확인하고 변경할 수 있습니다.

자원을 사용하지 않는 상태가 될 때, 대기하던 프로세스가 즉시 자원을 사용하고. 이미 다른 프로세스에 의해 사용중이라는 사실을 알게 되면, 재시도 전에 일정시간 대기해야 합니다.

일반적으로 비교적 긴 시간을 확보하는 리소스에 대해 사용하게 됩니다.

차이점

가장 큰 차이점은 동기화 대상의 개수 즉, 위에서 예시든 화장실의 갯수 입니다.

• Mutex는 동기화 대상이 오직 1개일 때 사용하며, Semaphore는 동기화 대상이 1개 이상일 때 사용합니다.
• Mutex는 자원을 소유할 수 있고, 책임을 가지는 반면 Semaphore는 자원 소유가 불가합니다.
• Mutex는 상태가 0, 1 뿐이므로 Lock을 가질 수 있고, 소유하고 있는 스레드만이 이 Mutex를 해제할 수 있습니다. 반면 Semaphore는 Semaphore를 소유하지 않는 스레드가 Semaphore를 해제할 수 있습니다.
• Semaphore는 시스템 범위에 걸쳐 있고, 파일 시스템 상의 파일로 존재합니다. 반면, Mutex는 프로세스의 범위를 가지며 프로세스 종료될 때 자동으로 Clean up 됩니다.

 

 

구현 및 필요 개념 정리 및 에러 해결 과정 : )

pthread_join vs pthread_detach

pthread_join 함수를 쓰면 지정된 스레드가 종료될때까지 기다리며, 스레드가 이미 종료된 경우에는 즉시 반환됩니다. join을 사용했을 때 이점은 모든 스레드가 종료될 때까지 기다린 다음에

pthread_detach 함수는 쓰레드 식별자 thread를 가지는 쓰레드를 메인쓰레드에서 분리 시킨다. 이것은 thread를 가지는 쓰레드가 종료되는 즉시 쓰레드의 모든 자원을 되돌려(free)줄 것을 보증한다.

detach를 사용할 때 주의할 점은 메인 프로세서가 종료되면 모든 쓰레드 프로세서도 종료되어 버리기 때문에 메인 프로세서는 유지해줘야 한다.

그리고 한명의 필로소퍼만 있을 경우에는 join의 경우에는 따로 케이스를 분리해서 코드를 작성해줘야하지만 detach같은 경우에는 main문에서 죽은 것을 확인하고 return을 시켜주면 끝나기 때문에 따로 케이스를 분리할 필요가 없다.

둘 중에 아무거나 사용해도 이번 과제에서는 상관이 없을 것이다(현재 내 개념으로는). 그래서 다른 카뎃들의 결과물을 봐도 join, detach를 골고루 사용하는 것을 볼 수 있다.

 

 

delay 가 발생하는 이유와 예방 방법

usleep()을 해서 delay가 발생하는 경우는 이러하다.

usleep()을 하면 thread_A는 running상태에서 sleep상태로 가게 된다.

그러면 sleep을 하는 동안 ready에 다른 thread들이 쌓이게 된다. usleep이 짧은 시간동안만 동작을 한다면 ready에 쌓이는게 얼마 되지않아서 thread_A에 running 상태가 되기 위해서 얼마 기다리지 않아도 된다. 하지만 usleep()이 꽤 오래 동안 동작하면 thread_A는 running 상태를 들어가기 위해서는 오래기다려야하기 때문에 delay가 발생하게 되는 것이다.

그래서 시간 밀림 현상(delay)를 줄이기 위해서는

while (현재 시간 - usleep을 시작한 시간 > 실제 usleep해야하는 시간)
	usleep(1000);

짧은 시간 동안만 잠들게 하면서 딜레이를 줄이고 그나마 적게 생긴 딜레이조차 while문의 조건문으로 검열할 수 있게 된다.

예를 들어서 usleep(11000)은 usleep(1000)을 11번 해야한다. 근데 usleep(1000)의 평균 딜레이가 101us라고 하면 usleep이 10번 돌았을 때, delay까지 합치면 11010us가 된다. 이 뜻은 우리는 10번만 돌았지만 11번 usleep(1000)을 했을 때랑 같고 게다가 delay를 이용했기 때문에 delay를 줄이게 된 것이다.

엄청난 알고리즘이라고 생각한다.

 

 

critical section을 잘 보호했는지 확인

gcc %.c -fsanitize=thread

위와 같은 컴파일 옵션을 사용한다면 thread들이 동작할 때 같은 자원에 동시에 접근하는지 알 수 있다.

만약 에러가 뜬다면 mutex를 이용한 critical section을 잘 정의안해준 것이다. 공부하세유.

데드락 에러

pthread_mutex_lock(&(data->check_box_event));
if (data->done_check_box[i] == 0)
		return ;
pthread_mutex_unlock(&(data->check_box_event));

위에 무슨 오류가 있다고 생각하는가?

바로 critical section 사이에 return이 있는 것이다.

lock이 있으면 거의 무조건 unlock을 해줘야한다.(필요에 의해서 일부러 안할 수는 있다.)

근데 위 같은 코드의 경우에는 중간에 return 으로 함수가 종료되게 되면 unlock이 되지 않고 함수가 종료하게 되어서 다른 곳에서 다 꼬이기 시작한다. 이런 코드 실수를 주의하면서 코드를 짜길 바란다.

 

pthread_mutex_destroy 함수를 꼭 사용해야할까?

is it necessary to call pthread_mutex_destroy on a mutex?

위 글을 보면 사용한다에 지배적인 의견들이 있다.

그 이유는 잠재적인 메모리를 해제시켜줘야한다는 이유에서이다.