개요
- 1명 이상의 철학자가 원형 테이블에 앉아 있음
- 테이블 가운데에는 스파게티가 있음
- 각 철학자는 먹거나 / 생각하거나 / 잠
- 각각의 행동은 한 번에 한 가지만 할 수 있음
- 먹기 👉 잠자기 👉 생각하기
- 먹을 때는 포크를 두 개(양손에 하나씩)를 들고 먹어야 함
- 철학자가 사망하면 프로그램 종료
- 먹지 않으면 굶어죽음
- 서로 언제 죽을지 알 수 없음
- 죽는 걸 피해야 함
규칙
인자
프로그램이 받아야 하는 인자들 (모든 시간은 밀리세컨드 단위)
1. number_of_philosophers: 철학자의 수 == 포크의 수
2. time_to_die: 마지막 식사 또는 프로그램 시작 후 이 시간 동안 먹지 못하면 사망
3. time_to_eat: 철학자가 식사하는 데 걸리는 시간 == 포크 두 개를 가지고 있는 시간
4. time_to_sleep: 철학자가 자는 데 걸리는 시간
5. number_of_times_each_philosopher_must_eat: 선택. 모든 철학자가 이 수만큼 식사를 마치면 프로그램 종료. 정의되지 않는 경우 철학자의 사망 시에만 프로그램 종료
- 각 철학자는
1부터number_of_philosophers까지 번호를 부여받음 - 1번 철학자는
number_of_philosophers번 철학자 옆에 앉음
(이외에N번 철학자는N-1번 철학자와N+1번 철학자 사이에 앉음)
로그
- 철학자 상태가 바뀌면 로그를 남겨야 함
- 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
- 철학자 사망 후 10 밀리세컨드 안에 로그를 남겨야 함
개념
프로세스(Process)
컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램
메모리에 올라와 실행되고 있는 프로그램의 인스턴스
- code, data, stack, heap의 구조로 된 독립적인 메모리 영역을 할당받음
- 각 프로세스는 별도의 주소 공간에서 실행되기 때문에, 한 프로세스는 다른 프로세스의 변수나 자료구조에 접근 불가
- 다른 프로세스의 자원에 접근하려면 프로세스 간의 통신(IPC, Inter-Process Communication)을 사용해야 함 (예: 파이프, 파일, 소켓 등)
스레드(Thread)
프로세스 내에서 실행되는 여러 흐름의 단위
- 프로세스는 최소 1개의 스레드(메인 스레드)를 가짐
- 스레드는 프로세스 내에서 각각의 stack 공간만 따로 할당받으며, code, data, heap 영역을 공유
- 한 스레드가 프로세스의 공유 자원을 변경하면, 다른 스레드도 그 변경 결과를 즉시 볼 수 있음
문맥 교환(Context Switching, 컨텍스트 스위칭)
- 컨텍스트 스위칭이 일어날 때 CPU는 다른 작업을 하지 못하기 때문에, 컨텍스트 스위칭이 잦아지면 성능이 떨어짐
프로세스 컨텍스트 스위칭
CPU에서 여러 프로세스를 돌아가면서 처리하는 것
동작 중인 프로세스가 대기를 하면서 해당 프로세스의 상태(Context)를 보관하고, 다음 우선 순위의 프로세스가 동작하면서 이전에 보관했던 프로세스의 상태를 복구하는 작업
스레드 컨텍스트 스위칭
프로세스에서 여러 스레드를 돌아가면서 처리하는 것
- 스레드는 공유하는 영역이 많기 때문에 교체해야 할 컨텍스트가 적으므로 프로세스 컨텍스트 스위칭보다 빠르다.
데이터 경쟁(Data Race)
여러 스레드가 같은 데이터를 공유할 때 발생
- 데이터 동기화 문제가 발생할 수 있음
뮤텍스(MutEx)
Mutual Exclusion, 상호배제
여러 스레드가 공유하는 자원을 보호하기 위해 사용되는 도구 (데이터 경쟁 방지)
- 특정 스레드에서만 단독으로 실행되어야 하는 코드 구간인 임계 영역(critical section)에서 동기화를 위해 사용
허용함수
memset printf malloc free write
usleep()
주어진 시간 동안 스레드의 실행을 지연시킴
#include <unistd.h>
int usleep(useconds_t microseconds);- 인자는 마이크로세컨드 단위
gettimeofday()
그리니치 표준시와 타임존을 구조체에 세팅해주는 함수
#include <sys/time.h>
int gettimeofday(struct timeval *restrict tp, void *restrict tzp);- 전달해야 하는 인자 구조체
timeval과timezone은 sys/time.h에 아래와 같이 정의되어 있음 NULL을 전달하면NULL이 아닌 포인터만 세팅됨
둘 다NULL이면 아무것도 하지 않음- 성공 시
0, 실패 시-1리턴
struct timeval {
time_t tv_sec; /* seconds since Jan. 1, 1970 */
suseconds_t tv_usec; /* and microseconds */
};
struct timezone {
int tz_minuteswest; /* of Greenwich */
int tz_dsttime; /* type of dst correction to apply */
};tv_sec: 초 단위tv_usec: 마이크로세컨드 단위 (초로 표현할 수 없는 상세한 정보)
👉(tv_sec * 1000) + (tv_usec / 1000): 밀리세컨드로 현재 시각 계산
아래
pthread_함수들은 모두 pthread.h에 정의됨
pthread_create()
새 스레드 생성
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);pthread_t *thread: 생성한 스레드를 저장할 포인터pthread_attr_t *attr: 스레드에 지정할 속성.NULL이면 기본 속성 사용void *(*start_routine)(void *)- 스레드는
start_routine에 전달된 함수를 실행하며 생성됨 - 이 함수의 리턴값은 암묵적으로
pthread_exit()의 인자로 전달되어 스레드를 종료
- 스레드는
void *arg:start_routine함수에 전달할 인자- 성공 시
0, 실패 시 오류 번호 리턴
❗️ 여기서 생성된 스레드의 메모리는 다른 스레드에서 pthread_join이나 pthread_detach를 통해 회수되어야 함 (그렇지 않으면 누수 발생!)
pthread_detach()
스레드가 종료될 때 메모리를 회수하도록 지정하는 함수
(타겟 스레드를 메인 스레드에서 분리시킴으로써 타겟 스레드가 종료되는 즉시 자원을 반환하는 동작을 보증)
👉 스레드 생성 후 호출
int pthread_detach(pthread_t thread);- 성공 시
0, 실패 시 오류 번호 리턴 - 같은 스레드에 대해 여러번 이 함수를 호출했을 때의 동작은 정의되어 있지 않음
pthread_join()
타겟 스레드가 종료될 때까지 현재 스레드의 실행을 지연시키는 함수
(타겟 스레드가 종료될 때 메모리를 회수하는 함수)
👉 타겟 스레드를 종료하고 싶을 때 호출
int pthread_join(pthread_t thread, void **value_ptr);void **value_ptr:NULL이 아닌 값이 전달된 경우, 종료된 스레드에 의해pthread_exit()에 전달된 값(스레드의 리턴값)이 여기에 저장됨- 성공 시
0, 실패 시 오류 번호 리턴 - 타겟 스레드가 이미 종료된 경우 아무것도 하지 않음
- 성공적으로 리턴된 경우 타겟 스레드가 종료됨
- 같은 스레드에 대해 여러번 이 함수롤 호출했을 때의 동작은 정의되어 있지 않음
- 이 함수를 호출한 스레드가 취소된 경우? 타겟 스레드의 메모리는 회수되지 않음
pthread_mutex_init()
뮤텍스 생성
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);pthread_mutex_t *mutex: 생성된 뮤텍스를 저장할 포인터const pthread_mutexattr_t *attr: 뮤텍스에 지정할 속성.NULL이면 기본 속성 사용- 성공 시
0, 실패 시 오류 번호 리턴
pthread_mutex_destroy()
뮤텍스에 할당된 메모리 반환
int pthread_mutex_destroy(pthread_mutex_t *mutex);- 성공 시
0, 실패 시 오류 번호 리턴
pthread_mutex_lock()
뮤텍스 잠금
int pthread_mutex_lock(pthread_mutex_t *mutex);- 성공 시
0, 실패 시 오류 번호 리턴 - 뮤텍스가 이미 다른 스레드에 의해 잠겨 있는 경우, 뮤텍스가 다시 사용 가능해질 때까지 스레드의 작동이 멈춤
pthread_mutex_unlock()
뮤텍스 잠금 해제
int pthread_mutex_unlock(pthread_mutex_t *mutex);- 성공 시
0, 실패 시 오류 번호 리턴 - 현재 스레드가 점유하고 있지 않은 뮤텍스에 대해 이 함수를 호출하는 경우에 대한 동작은 정의되어 있지 않음
구현
- 프로그램명:
philo - 제출 파일:
philo/ - 각 철학자는 스레드
- 어떤 스레드가 포크를 쓰고 있으면 다른 스레드에서는 쓰지 못하도록 해야 함
- 인자 유효성 검사 (
0이상INT_MAX이하) - 구조체 초기화
구조체를 서로 참조하려면 위에 이름만 선언하고 아래에서 정의하면 됨 (참고) - 스레드 생성 및 실행 (짝수 번은 대기, 홀수 번부터 식사)
- 모니터링 함수 생성
종료 조건
마지막 식사 또는 시작 시간으로부터time_to_die이상 경과된 경우
모든 철학자가must_eat만큼 식사를 마친 경우
공유 자원
포크, 프린트
👉 뮤텍스 타입으로 변수 선언
출력을 할 때 뮤텍스를 사용하지 않으면 시간 순서가 뒤죽박죽으로 출력되는 경우가 발생함
교착 상태 (deadlock)
교착 상태를 만드는 조건
모든 조건을 만족해야 함
- 상호 배제: 사용 중인 포크는 공유 불가
- 점유 대기: 왼쪽 포크를 들고 다른 스레드가 오른쪽 포크를 다 쓸 때까지 대기
- 선점 불가: 다른 스레드에서 포크를 쓰는 동안 뺏어올 수 없음
- 순환 대기: 1번 스레드부터 오른쪽 포크를 얻기 위한 작업이 순환 형태로 대기 (1번은 2번의 포크를, 2번은 3번의 포크를, ...)
👉 모든 조건을 만족할 가능성이 있으므로 교착 상태 발생 가능
교착 상태 해결
상호 배제와 선점 불가는 없으면 안 되는 조건
- 양쪽 포크가 있을 때만 양쪽 포크를 들어 식사를 하도록 하면 점유 대기 해소
👉 경쟁 상태에 있기 때문에 기아 현상이 발생할 수 있음 - 홀수 번은 왼쪽 포크, 짝수 번은 오른쪽 포크를 쥐도록 하면 순환 대기 해소
👉 누군가가 먼저 식사를 하게 되어 데드락은 해소되지만 이후에는 경쟁 상태에 있기 때문에 기아 현상이 발생할 수 있음
홀수 번부터 양쪽 포크가 있는 경우 식사를 하게 하고, 짝수 번은 잠시 대기하도록 하면 기아 현상을 예방할 수 있음
👉 스레드가 홀수 개인 경우 대기 시간이 조금 더 발생하게 되지만 스레드의 홀짝에 상관 없이 식사를 하는 순서가 보장됨
참고
https://bigpel66.oopy.io/library/42/inner-circle/9
https://youtu.be/YAP0Bv_aQl8
비주얼라이저
테스터
