Philosophers

chez_bono·2022년 3월 16일
0

42cursus

목록 보기
7/17
post-thumbnail

개요

  • 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);
  • 전달해야 하는 인자 구조체 timevaltimezone은 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_detach와 pthread_join 참고

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, 실패 시 오류 번호 리턴
  • 현재 스레드가 점유하고 있지 않은 뮤텍스에 대해 이 함수를 호출하는 경우에 대한 동작은 정의되어 있지 않음

pthread_mutex_lock, pthread_mutex_unlock 참고


구현

  • 프로그램명: philo
  • 제출 파일: philo/
  • 각 철학자는 스레드
  • 어떤 스레드가 포크를 쓰고 있으면 다른 스레드에서는 쓰지 못하도록 해야 함
  1. 인자 유효성 검사 (0 이상 INT_MAX 이하)
  2. 구조체 초기화
    구조체를 서로 참조하려면 위에 이름만 선언하고 아래에서 정의하면 됨 (참고)
  3. 스레드 생성 및 실행 (짝수 번은 대기, 홀수 번부터 식사)
  4. 모니터링 함수 생성
    종료 조건
    마지막 식사 또는 시작 시간으로부터 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
비주얼라이저
테스터

profile
목표는 행복한 베짱이

0개의 댓글