Home Philosophers ② 배경 지식
Post
Cancel

Philosophers ② 배경 지식

Posted Oct 6, 2022 Updated Nov 17, 2022
By Taehoon
15 min read

식사하는 철학자들 문제 (Dining philosophers problem)

개요

Untitled

철학자 5명이 원탁에 앉아있고, 각자의 앞에는 스파게티가 있고 양옆에 포크가 하나씩 있다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없다. 이때 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다.

참고

고려 사항

  1. Data Consistency (데이터 정합성)
  2. Deadlock (교착 상태)
  3. Starvation (기아 상태)
  4. Concurrency (동시성)

교착 상태

모든 철학자가 한번에 왼쪽 포크를 들고 오른쪽 포크를 드는 알고리즘을 갖고 있다면, 모두가 동시에 왼쪽 포크를 들고 오른쪽 포크를 기다리는 교착 상태에 빠지게 될 수 있다.

발생 조건

  • Mutual exclusion
  • Hold and wait
  • Non-preemption
  • Circular wait

위 네 가지 조건을 모두 만족한다면 교착 상태가 발생한다.

해결책

  • 다익스트라의 해결책
    • 각 철학자들을 P1~P5라고 하고 왼쪽 포크를 f1~f5라고 하자. P1~P4 철학자는 f(n)을 먼저 집은 후에 f(n+1)을 집는다. 반면 P5는 f1을 먼저 집은 후에 f5를 집는다.
  • 양쪽 젓가락을 모두 사용할 수 있을 때 두개를 한번에 집는다.
  • 홀수와 짝수로 나눠서 각각 왼쪽 오른쪽 젓가락을 집도록 한다.
  • 이러한 해결책들은 교착 상태의 발생 조건 중 한 가지 이상을 제거하여 교착 상태를 방지한다. 하지만 기아 상태의 가능성은 제거할 수 없으므로 추가적인 해결책이 필요하다.

과제 허용 함수

pthread 함수

  • 헤더 : #include <pthread.h>

pthread_create

  • 함수 원형
    • int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);
  • 설명
    • 새로운 스레드를 생성하고 해당 스레드가 인자로 받은 함수를 호출한다.
    • attr이 NULL인 경우 : 기본 속성이 사용된다.
  • 매개변수
    • thread : 생성할 스레드
    • attr : 스레드 속성
    • start_routine : 생성될 스레드가 호출할 함수
    • arg : 호출될 함수가 받을 인자
  • 리턴값
    • 성공한 경우 : 0 반환
    • 실패한 경우 : 오류 번호 반환

pthread_join

  • 함수 원형
    • int pthread_join(pthread_t thread, void **value_ptr);
  • 설명
    • 타겟 thread가 아직 종료되지 않았다면 종료될 때까지 호출한 스레드의 실행을 멈춘다.
    • 메인 thread나 부모 thread가 자식 thread가 종료될 때까지 대기한다.
  • 매개변수
    • thread : 생성한 스레드의 ID
    • value_ptr : 스레드가 종료되면 리턴받을 변수. 없다면 NULL로 사용
  • 리턴값
    • 성공한 경우 : 0 반환
    • 실패한 경우 : 오류 번호 반환

pthread_detach

  • 함수 원형
    • int pthread_detach(pthread_t thread);
  • 설명
    • 스레드를 분리시킨다.
    • 보통은 pthread_create으로 스레드를 생성한 뒤에 해당 스레드를 호출한 위치에서 pthread_join을 사용해 스레드의 자원을 해제하고 종료한다.
    • 반면 스레드를 생성한 후에 pthread_detach 함수를 호출하면 종료할 때 스레드가 알아서 자원을 해제한다.
  • 리턴값
    • 성공한 경우 : 0 반환
    • 실패한 경우 : 오류 번호 반환
      • errno를 변경하지는 않는다.

pthread_mutex_init

  • 함수 원형
    • int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);
  • 설명
    • 새로운 뮤텍스를 생성한다.
  • 매개변수
    • mutex : 새 뮤텍스의 ID가 담길 변수
    • attr : 뮤텍스를 생성할 때 사용할 속성. NULL로 들어온 경우 기본 속성을 적용한다.
  • 리턴값
    • 성공한 경우 : 0 반환. 새로운 mutex ID를 mutex에 저장한다.
    • 실패한 경우 : 오류 번호 반환

pthread_mutex_destroy

  • 함수 원형
    • int pthread_mutex_destroy(pthread_mutex_t *mutex);
  • 설명
    • 뮤텍스에 할당된 자원을 해제한다.
  • 리턴값
    • 성공한 경우 : 0 반환
    • 실패한 경우 : 오류 번호 반환

pthread_mutex_lock

  • 함수 원형
    • int pthread_mutex_lock(pthread_mutex_t *mutex);
  • 설명
    • 뮤텍스를 잠근다.
    • 뮤텍스가 이미 잠겨있다면 뮤텍스가 가용할 때까지 호출한 스레를 막는다.
  • 매개변수
    • mutex : 잠그려는 뮤텍스
  • 리턴값
    • 성공한 경우 : 0 반환
    • 실패한 경우 : 오류 번호 반환

pthread_mutex_unlock

  • 함수 원형
    • int pthread_mutex_unlock(pthread_mutex_t *mutex);
  • 설명
    • 뮤텍스의 잠금을 해제한다.
    • 만약 현재 스레드가 뮤텍스를 잠그고 있다면 이 함수가 뮤텍스를 잠금 해제한다.
    • 호출한 스레드가 갖고있지 않은 뮤텍스에 함수를 호출한다면 undefined behavior이 발생한다.
  • 매개변수
    • mutex : 잠금 해제할 뮤텍스
  • 리턴값
    • 성공한 경우 : 0 반환
    • 실패한 경우 : 오류 번호 반환

semaphore 함수

  • 헤더
    • #include <semaphore.h>

sem_open

  • 함수 원형
    • sem_t *sem_open(const char *name, int oflag, ...);
  • 설명
    • 이름이 name인 세마포어를 초기화하고 oflag에 명시된대로 연다.
  • 매개변수
    • name
      • 세마포어의 이름
      • 이름은 /somename 형태여야 한다.
    • oflag
      • O_CREAT : 세마포어가 존재하지 않으면 새로 생성한다.
      • O_EXCL : 세마포어가 이미 존재하면 에러를 발생시킨다.
    • mode
      • 세마포어의 권한을 명시해준다.
      • 프로세스의 umask 값을 수정해준다.
    • value
      • 세마포어의 초기값
      • SEM_VALUE_MAX 이하의 값
  • 반환값
    • 성공한 경우 : 세마포어 디스크립터가 반환된다.
    • 실패한 경우 : SEM_FAILED 반환. errno가 설정됨.
  • 기타
    • 세마포어를 처음 여는 것임을 보장하기 위해 sem_open 전에 sem_unlink를 호출할 수 있다.

sem_close

  • 함수 원형
    • int sem_close(sem_t *sem);
  • 설명
    • sem이 참조하는 세마포어가 할당 해제되고 디스크립터가 무효화된다.
  • 반환값
    • 성공한 경우 : 0
    • 실패한 경우 : -1

sem_post

  • 함수 원형
    • int sem_post(sem_t *sem);
  • 설명
    • sem이 참조하는 세마포어가 잠금해제된다.
    • 세마포어의 값이 증가한다.
    • 세마포어에서 대기하는 모든 스레드를 깨운다.
  • 반환값
    • 성공한 경우 : 0
    • 실패한 경우 : -1 반환. errno가 설정됨.
  • 실패하는 경우
    • EINVAL : sem이 유효한 세마포어 디스크립터가 아닌 경우

sem_wait

  • 함수 원형
    • int sem_wait(sem_t *sem);
  • 설명
    • sem이 참조하는 세마포어가 잠긴다.
    • 이 함수를 호출했을 때 세마포어의 값이 0이라면 잠금이 획득되거나 시그널에 의해 인터럽트될 때까지 블락된다.
  • 반환값
    • 성공한 경우 : 0
    • 실패한 경우 : -1 반환. errno가 설정됨. 세마포어의 상태가 변경되지 않는다.
  • 실패하는 경우
    • EAGAIN : 세마포어가 이미 잠긴 경우
    • EDEADLK : 데드락이 감지된 경우
    • EINTR : 호출이 시그널에 의해 인터럽트된 경우
    • EINVAL : 유효한 세마포어 디스크립터가 아닌 경우
  • 함수 원형
    • int sem_unlink(const char *name);
  • 설명
    • 이름이 name인 세마포어가 제거된다.
    • 만약 다른 프로세스가 해당 세마포어를 사용중이라면 name과 세마포어와의 연결을 끊는다. 또한 모든 참조가 완료되기 전까지는 제거되지 않는다.
    • 이후에 name으로 다시 sem_open함수를 호출한다면 새로운 세마포어를 참조하거나 생성한다.
  • 반환값
    • 성공한 경우 : 0
    • 실패한 경우 : -1 반환. errno가 설정됨. 세마포어의 상태가 변경되지 않는다.

기타 함수

gettimeofday

  • 함수 원형
    • #include <sys/time.h>
    • int gettimeofday(struct timeval *restrict tp, void *restrict tzp);
  • 설명
    • 현재 시간을 얻는 함수
    • 1970년 7월 1일 자정 이후로 흐른 시간을 초나 마이크로초로 나타낸다.
    • tp : NULL, tzp : non-NULL -> tzp의 timezone 구조체가 채워진다.
    • tp : non-NULL, tzp : NULL -> tp의 timeval 구조체가 채워진다.
  • 구조체
    • tp, tzp가 가리키는 구조체는 sys/time.h에 선언
    • timeval 구조체
      • 시간 값을 초나 마이크로초로 나타낸다.
      1
2
3
4
5

        struct timeval
  {
      time_t	tv_sec;   /* seconds since Jan. 1, 1970 */
      suseconds_t	tv_usec;  /* and microseconds */
  };
    • timezone 구조체
      • 지역 표준시간대를 나타낸다.
      1
2
3
4
5

        struct timezone
  {
      int	tz_minuteswest; /* of Greenwich */
      int	tz_dsttime;     /* type of dst correction to apply */
  };
  • 리턴값
    • 호출에 성공한 경우 : 0
    • 에러 발생 시 : -1 반환. errno에 오류 코드가 저장된다.

fork

  • 헤더
    • #include <unistd.h>
  • 함수 원형
    • pid_t fork(void);
  • 설명
    • 새로운 프로세스를 생성한다.
    • 새로운 프로세스(자식 프로세스)는 호출한 프로세스(부모 프로세스)와 동일하지만 다음의 차이점을 가진다.
      • 자식 프로세스는 고유한 프로세스 ID를 갖는다.
  • 반환값
    • 성공한 경우
      • 자식 프로세스에게 0 반환.
      • 부모 프로세스에게 자식 프로세스의 프로세스 ID 반환
    • 실패한 경우
      • 자식 프로세스가 생성되지 않는다.
      • 부모 프로세스에게 -1 반환.

waitpid

  • 헤더
    • #include <sys/wait.h>
  • 함수 원형
    • pid_t waitpid(pid_t pid, int *stat_loc, int options);
  • 설명
    • 프로세스의 종료를 기다린다.
  • 매개변수
    • pid
      • 기다릴 자식 프로세스의 집합을 명시한다.
      • pid 인자를 -1로 설정하면 아무 자식 프로세스나 기다린다.
      • 인자가 0이라면 호출자의 프로세스 그룹에 있는 아무 자식 프로세스나 기다린다.
    • stat_loc
      • 프로세스의 상태(exit 값)를 가져오기 위해 사용된다.
      • 이 값이 NULL이 아니라면 해당 포인터가 가리키는 위치에 프로세스의 상태를 저장한다.
      • 매크로를 통해 상태정보를 검사할 수 있다.
    • options
      • 0 또는 아래 값을 비트연산자 OR을 사용해 설정한다.
        • WNOHANG
        • WUNTRACED
  • 반환값
    • 자식 프로세스의 프로세스 ID가 호출한 프로세스에게 반환.
      • 자식 프로세스가 종료된 경우 반환된다.
    • 이전에 기다리던 자식 프로세스가 없던 경우 : -1 반환. errno가 ECHILD로 설정.
    • 오류가 발생하거나 수신한 시그널이 호출을 종료시킨 경우 : -1 반환. errno가 설정.

Ref.

https://ko.wikipedia.org/wiki/식사하는_철학자들_문제
https://www.morenice.kr/75

42Seoul, Philosophers
c os deadlock
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents

네트워크 - 02. Application Layer

Line Feed (LF)와 Carriage Return (CR)의 차이점