1. 과제 해석

Mandatory part

• You will have to write one program for the mandatory part and one for the bonus part but they will have the same basic rules:
  당신은 필수 파트에 대한 하나의 프로그램과 보너스 파트에 대한 하나의 프로그램을 작성해야 하지만, 각 프로그램들은 다음과 같은 기본 규칙들을 가집니다:
• This project is to be coded in C, following the Norm. Any leak, crash, undefined behavior, or norm error means 0 to the project.
  이 프로젝트는 Norm을 따르면서 C로 코딩하는 것입니다. 어떤 누수와 오류, 비정상적인 행동, 놈에러도 허용되지 않습니다.
• One or more philosophers are sitting at a round table doing one of three things: eating, thinking, or sleeping.
  하나 이상의 철학자들은 다음과 같은 세 가지 행동을 하며 원형 테이블에 앉아 있습니다: 식사, 생각, 수면
• While eating, they are not thinking or sleeping, while sleeping, they are not eating or thinking and of course, while thinking, they are not eating or sleeping.
  식사하는 동안에 철학자들은 생각하지도 않고 수면하지도 않습니다. 수면 중에 철학자들은 식사하지도 않고 생각하지도 않습니다. 물론 생각하는 중에 철학자들은 식사하지도 않고 수면하지도 않습니다.
• The philosophers sit at a circular table with a large bowl of spaghetti in the center.
  철학자들은 중앙에 많은 스파게티가 담긴 접시가 있는 원형 테이블에 앉습니다.
• There are some forks on the table.
  몇 개의 포크가 테이블에 놓여있습니다.
• As spaghetti is difficult to serve and eat with a single fork, it is assumed that a philosopher must eat with two forks, one for each hand.
  스파게티는 하나의 포크로 가져와서 먹기 어렵기 때문에, 철학자는 양 손에 하나씩, 두 개의 포크를 이용하여 식사해야 하는 것으로 가정합니다.
• The philosophers must never be starving.
  철학자들은 절대 굶지 않습니다.
• Every philosopher needs to eat.
  모든 철학자는 식사해야 합니다.
• Philosophers don’t speak with each other.
  철학자들은 서로 말하지 않습니다.
• Philosophers don’t know when another philosopher is about to die.
  철학자들은 또 다른 철학자가 언제 죽을지 모릅니다.
• Each time a philosopher has finished eating, he will drop his forks and start sleeping.
  철학자가 식사를 마칠 때마다 포크를 놓고 수면을 시작합니다.
• When a philosopher is done sleeping, he will start thinking.
  철학자가 수면을 마칠 때 생각하기 시작합니다.
• The simulation stops when a philosopher dies.
  철학자가 죽었을 때 시뮬레이션이 멈춥니다.
• Each program should have the same options: number_of_philosophers time_to_die time_to_eat time_to_sleep [number_of_times_each_philosopher_must_eat]
  각 프로그램은 다음과 같은 옵션을 가집니다: time_to_die time_to_eat time_to_sleep [number_of_times_each_philosopher_must_eat]

1. number_of_philosophers: is the number of philosophers and also the number
   of forks
   number_of_philosophers: 철학자의 수와 포크의 수
2. time_to_die: is in milliseconds, if a philosopher doesn’t start eating ’time_to_die’ milliseconds after starting his last meal or the beginning of the simulation, it dies
   time_to_die: milliseconds 단위이고, 만약 철학자가 식사를 시작하지 않는다면, 마지막 식사나 시뮬레이션이 시작한 이후 time_to_die ms후에 철학자는 죽습니다.
3. time_to_eat: is in milliseconds and is the time it takes for a philosopher to eat. During that time he will need to keep the two forks.
   time_to_eat: milliseconds 단위이고, 철학자가 식사하는 데 사용하는 시간입니다. 이 시간동안에 철학자는 두 개의 포크를 필요로 합니다.
4. time_to_sleep: is in milliseconds and is the time the philosopher will spend sleeping.
   time_to_sleep: milliseconds 단위이고, 철학자가 수면하는 데 사용하는 시간입니다.
5. number_of_times_each_philosopher_must_eat: argument is optional, if all philosophers eat at least ’number_of_times_each_philosopher_must_eat’ the simulation will stop. If not specified, the simulation will stop only at the death of a philosopher.
   number_of_times_each_philosopher_must_eat: 선택적인 옵션입니다. 만약 모든 철학자들이 최소 number_of_times_each_philosopher_must_eat번 식사하였다면, 시뮬레이션은 멈춥니다. 만약 설정하지 않는다면, 시뮬레이션은 오직 철학자가 죽을 때에만 멈출 것입니다.

• Each philosopher should be given a number from 1 to ’number_of_philosophers’.
  각 철학자에게 1부터 number_of_philosophers까지 숫자가 주어집니다.
• Philosopher number 1 is next to philosopher number ’number_of_philosophers’.
  Any other philosopher with the number N is seated between philosopher N - 1 and philosopher N + 1
  1번 철학자는 number_of_philosophers번 철학자 옆에 있습니다. N번의 다른 철학자도 N-1번 철학자와 N+1철학자 사이에 앉아 있습니다.
• Any change of status of a philosopher must be written as follows (with X replaced with the philosopher number and timestamp_in_ms the current timestamp in milliseconds)
  철학자의 어떤 상태 변화도 다음과 같이 쓰여져야 합니다.(X는 철학자 번호, timestamp_in_ms는 현재 타임 스탬프 (milliseconds))

1. timestamp_in_ms X has taken a fork
2. timestamp_in_ms X is eating
3. timestamp_in_ms X is sleeping
4. timestamp_in_ms X is thinking
5. timestamp_in_ms X died

• The status printed should not be scrambled or intertwined with another philosopher’s status.
  출력된 상태는 다른 철학자의 상태와 뒤섞이거나 얽혀서는 안됩니다.
• You can’t have more than 10 ms between the death of a philosopher and when it will print its death.
  당신은 철학자의 죽음과 그 죽음을 출력하는 시간 사이에 10ms 이상을 가질 수 없습니다.
• Again, philosophers should avoid dying!
  다시, 철학자들은 죽음을 피해야 합니다.

Program name : philo
Turn in files : philo/
Makefile : Yes
Arguments : number_of_philosophers, time_to_die, time_to_eat, time_to_sleep, [number_of_times_each_philosopher_must_eat]
External functs. : 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
Libft authorized : No
Description : philosopher with threads and mutex

• In this version the specific rules are:
  해당 버전에서 설정된 규칙들은 다음과 같습니다:
• One fork between each philosopher, therefore if they are multiple philosophers, there will be a fork at the right and the left of each philosopher.
  각 철학자 사이에 하나의 포크가 있어서 만약 철학자가 다수라면, 포크는 각 철학자의 왼쪽과 오른쪽에 위치할 것입니다.
• To avoid philosophers duplicating forks, you should protect the forks state with a mutex for each of them.
  철학자가 포크를 중복사용하는 것을 피하기 위해 당신은 포크들의 상태를 각각의 뮤텍스로 보호해야 합니다.
• Each philosopher should be a thread.
  각 철학자는 스레드가 되어야 합니다.

Bonus
Program name : philo_bonus
Turn in files : philo_bonus/
Makefile : Yes
Arguments : number_of_philosophers, time_to_die, time_to_eat, time_to_sleep, [number_of_times_each_philosopher_must_eat]
External functs. : memset, printf, malloc, free, write, fork, kill, exit, pthread_create, pthread_detach, pthread_join, usleep, gettimeofday, waitpid, sem_open, sem_close, sem_post, sem_wait, sem_unlink
Libft authorized : No
Description : philosopher with processes and semaphore

• In this version the specific rules are:
  해당 버전에서 설정된 규칙들은 다음과 같습니다:
• All the forks are in the middle of the table.
  모든 포크는 테이블의 중앙에 있습니다.
• They have no states in memory but the number of available forks is represented by a semaphore.
  포크들은 메모리에 없지만, 이용가능한 포크의 수는 세마포어가 표시합니다.
• Each philosopher should be a process and the main process should not be a philosopher.
  각 철학자는 프로세스가 되어야 하고 메인 프로세스는 철학자가 되면 안됩니다.

2. 과제 수행 과정

A. 과제 설명

Philosophers 과제는 '식사하는 철학자' 프로그램을 작성하는 과제입니다.

• 식사하는 철학자 문제 : 원형 테이블에 둘러 앉아있는 여러 철학자가 공유 자원인 포크를 사용하여 굶어 죽지 않고 식사해야하는 문제입니다.

1) 조건

Philosophers 프로그램은 다음의 조건을 충족해야 합니다.

a) 철학자 식사 조건

1. 철학자는 반드시 두 개의 포크를 활용하여 식사해야 합니다.
2. 철학자는 다른 철학자가 쓰고 있는 포크를 뺏으면 안됩니다.

b) 철학자 죽는 조건

1. 각 철학자는 프로그램의 인자로 주어진 time_to_die 동안 식사하지 않으면 죽습니다.

c) 프로그램 종료 조건

1. 프로그램의 인자로 number_of_times_each_philosopher_must_eat이 주어졌을 경우, 모든 철학자가 주어진 인자만큼 식사했을 때 프로그램이 종료됩니다.
2. 한명의 철학자라도 죽게 된다면 프로그램이 종료됩니다.

d) 기타 조건

1. 각 철학자는 식사-수면-생각의 행동 패턴을 가집니다.
2. 각 철학자는 반드시 프로그램의 인자로 주어진 time_to_eat 동안 식사해야 하고, time_to_sleep 동안 수면해야 합니다.
3. 프로그램의 인자로 주어진 number_of_philosophers만큼 철학자를 생성해야 합니다.
4. 철학자는 서로 소통하지도 않고, 서로 죽었는지도 모릅니다.

2) 프로그램 작성 계획

1. 각 철학자는 thread나 process형태로 생성하여 과제에서 정의된 행동 패턴을 수행할 것입니다.
2. 각 철학자가 사용해야 하는 공유 자원인 포크는 mutex나 semaphore로 보호할 것입니다.
   : 각 철학자(thread, process)가 사용해야 하는 공유 자원인 포크가 mutex나 semaphore로 보호되지 않을 경우, 각 철학자가 공유 자원에 동시에 접근할 때 잘못된 결과가 출력되는 오류가 발생합니다.
3. 프로그램의 교착상태(deadlock)를 방지하기 위해 교착상태 4가지 조건 중 환형 대기조건을 충족시키지 않게끔 프로그램의 알고리즘을 설계할 것입니다.
4. 프로그램의 기아상태(starvation)을 방지하기 위해 다수의 스레드나 프로세스가 동작하면서 발생하는 시간 오차를 줄일 것입니다.

3) 허용 함수 정리

1. memset
   : 메모리를 원하는 값으로 원하는 만큼 setting
   (https://blockdmask.tistory.com/441)
2. usleep
   : 마이크로 초 단위로 대기
   (http://forum.falinux.com/zbxe/index.php?mid=C_LIB&document_srl=564661)
3. gettimeofday
   : 현재 시스템 시간을 가져옴
   (https://www.joinc.co.kr/w/man/2/gettimeofday)
4. pthread_create
   : 스레드 생성 후, 생성된 스레드는 인자로 입력된 함수 실행
5. pthread_detach
   : 메인 프로세스와 별개로 스레드를 비동기로 실행, 스레드의 동작이 끝나면 자동으로 할당된 자원 모두 해제
6. pthread_join
   : 메인 프로세스는 스레드의 종료를 대기, 스레드의 동작이 끝나면 자동으로 할당된 자원 모두 해제
7. pthread_mutex_init
   : mutex 객체 생성
8. pthread_mutex_destroy
   : mutex 객체 해제
   (https://nxmnpg.lemoda.net/ko/3/pthread_mutex_destroy)
9. pthread_mutex_lock
   : 공유 자원을 mutex를 활용하여 보호하기 위한 함수, 다른 스레드나 프로세스가 해당 함수를 실행 중일 때 다른 프로세스가 해당 함수를 실행하면 함수를 실행 중인 스레드나 프로세스가 unlock할 때까지 큐에서 대기
10. pthread_mutex_unlock
    : 공유 자원을 mutex를 활용하여 보호하기 위한 함수, 공유 자원 사용이 끝날 때 mutex를 반환하여 다른 스레드나 프로세스가 공유 자원으로의 접근을 허용
11. kill
    : 프로세스에 시그널 전달
    (https://inno1010.tistory.com/entry/%EC%BB%A4%EB%84%90-kill-%ED%95%A8%EC%88%98)
12. waitpid
    : 종료된 자식 프로세스의 상태 받아오기
    (https://codetravel.tistory.com/42?category=993122)

• status 반환값 확인
  https://decdream.tistory.com/39
• session and process group
  https://mug896.github.io/bash-shell/session_and_process-group.html

10. sem_open
    : 세마포어로 만들어진 파일명을 인자로 넣어 세마포어를 생성
    (https://noel-embedded.tistory.com/732)
    (https://blackinkgj.github.io/semaphore)
11. sem_close
    : 특정 프로세스에서 사용되고 있는 세마포어를 종료
    (http://neosrtos.com/docs/posix_api/semaphore_close.html)
12. sem_post
    : 공유 자원을 semaphore를 활용하여 보호하기 위한 함수, 세마포어를 반환
    (https://noel-embedded.tistory.com/732)
13. sem_wait
    : 공유 자원을 semaphore를 활용하여 보호하기 위한 함수, 다른 스레드나 프로세스가 해당 함수를 실행 중일 때 다른 프로세스가 해당 함수를 실행하면 함수를 실행 중인 스레드나 프로세스가 post할 때까지 큐에서 대기
    (https://noel-embedded.tistory.com/732)
14. sem_unlink
    : open된 세마포어를 모두 해제
    (http://neosrtos.com/docs/posix_api/semaphore_unlink.html)

B. 선수 지식

Philosophers 프로그램을 작성하기 전에 멀티스레딩 및 멀티프로세싱의 원리에 대해 파악해야 합니다.
양희재 교수님 운영체제 강의 참고 : https://www.youtube.com/watch?v=QwBe0iYZBEg&list=PLK4xviZcdB9ieuusJ5j1UYZMFTuAgZCq8&index=6

1) Multi Programming

멀티스레딩 및 멀티프로세싱을 공부하기 앞서 다수의 프로그램이 하나의 CPU를 활용하는 방법인 Multi Programming의 전반적인 구조에 대해 알아볼 것입니다.

1. 프로그램이 실행되면 하드디스크에서 Job Queue를 거쳐 메인메모리에 프로세스 형태로 생성됩니다. 메인메모리 용량이 부족할 경우, 프로그램은 Job Queue에서 실행을 대기하고 Job Scheduling에 의해 Job Queue에서 선택된 프로그램이 메인메모리에 프로세스 형태로 생성됩니다.
2. 메인메모리에서 실행이 준비된 프로세스는 CPU를 사용하기 위해 Ready Queue에서 대기합니다.
3. CPU Scheduling에 의해 Ready Queue에서 선택된 프로세스가 CPU에 의해 실행됩니다.
4. I/O 장치를 사용하기 위해 인터럽트가 발생하면 프로세스는 CPU 사용을 중지하고 Device Queue에서 I/O 장치 사용을 기다립니다. 프로세스가 I/O 장치 사용을 종료하면 다시 Ready Queue로 들어가 CPU 사용을 기다립니다.
5. Timesharing System의 Context Switching을 위한 루틴입니다. 프로세스의 CPU 점유 시간이 일정 시간을 지나면 CPU 사용을 중단하고 다시 CPU를 사용하기 위해 Ready Queue로 들어갑니다. 이를 통해 다수의 프로세스가 CPU를 Concurrent하게 사용할 수 있습니다.
6. 프로세스를 종료합니다.

2) 프로세스 상태 천이도

프로세스는 일반적으로 다음과 같은 상태 변화를 겪습니다.

• 프로세스 상태

1. new : 하드디스크에 있는 프로그램이 메인 메모리에 올라와 있는 상태
2. ready : 메인 메모리에 올라와 있는 프로세스가 모든 초기화 작업을 마치고 실행을 대기하는 상태
3. running : cpu에 의해 실행되고 있는 상태
4. waiting : I/O 장치 등에 의해 cpu 사용을 중지한 상태
5. terminated : 프로세스 종료 상태

3) 프로세스 vs 스레드

멀티스레딩과 멀티프로세싱을 알아보기 전에 프로세스와 스레드의 차이부터 간단히 짚고 넘어가겠습니다.

a) 프로세스

: 컴퓨터에서 실행되고 있는 프로그램

• 프로세스는 위 그림과 같이 각각 독립된 메모리 영역을 할당받습니다.
• 특징

1. 프로세스당 최소 1개의 메인 스레드가 있습니다.
2. 다른 프로세스의 메모리 영역에 접근하려면 프로세스간 통신 기법을 활용해야 합니다. (ex. pipe, socket, file 등)

b) 스레드

: 프로세스 내부 흐름의 단위

• 스레드는 위 그림과 같이 프로세스 내에서 Stack만 따로 할당받고 Code, Data, Heap 영역은 공유합니다.
• 특징

1. 같은 프로세스 내부의 스레드들은 서로 자원을 공유할 수 있습니다.

4) 멀티프로세싱 vs 멀티스레딩

하나의 프로세스나 스레드를 사용하여 프로세스를 실행시키면 CPU가 아무일도 안하고 있는 시간인 CPU 유휴시간(Idle time)이 길어지고 CPU의 자원이 낭비됩니다. CPU 자원을 효율적으로 사용하기 위해 멀티프로세싱 및 멀티스레딩 기법이 사용됩니다.

a) 멀티프로세싱

: 하나의 프로그램을 여러 프로세스로 구동시키는 기법입니다.

• 장점

1. 각 프로세스는 독립된 메모리 영역을 참조하므로 특정 프로세스에 이상이 생겨도 다른 프로세스에 영향을 미치지 않습니다.

• 단점

1. 프로세스는 각각 독립된 메모리 영역을 할당받았기 때문에 프로세스 사이에서 공유하는 메모리가 없어, Context Switching이 발생하면 캐시에 있는 모든 데이터를 모두 리셋하고 다시 캐시 정보를 불러와야 합니다. 그렇기 때문에 비교적 많은 시간이 소모되어 Context Switching Overhead가 발생합니다. (Context Switching은 밑에서 다루겠습니다.)
2. 프로세스간 통신 기법을 사용하지 않는 이상 프로세스간 자원을 공유할 수 없습니다.

b) 멀티스레딩

: 하나의 프로그램을 여러 스레드로 구동시키는 기법입니다.

• 웹서버가 대표적인 멀티스레딩 프로그램입니다.
• 장점

1. 프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어들어 자원을 효율적으로 사용할 수 있습니다.
2. 스레드간 데이터 공유가 간단해집니다.
3. 작업량이 적어 Context Switching 속도가 빨라집니다.

• 단점

1. 디버깅이 까다롭습니다.
2. 다른 프로세스에서 스레드를 제어할 수 없습니다.
3. 스레드간 자원을 공유하기 때문에 교착상태(Deadlock)와 같은 동기화문제가 발생합니다.
4. 특정 스레드의 문제가 전체 프로세스에 영향을 미칩니다.

5) Context Switching

Context Switching은 현재 진행중인 프로세스나 스레드의 상태를 PCB에 저장하고 다음 진행될 프로세스나 스레드의 상태를 PCB에서 불러오는 것을 말합니다.

a) PCB (Process Control Block)

: Context Switching을 위해 프로세스에 대한 정보를 담아놓은 자료구조입니다. 정보는 커널의 메모리 영역에 쌓이게 됩니다.

• PCB의 구조는 OS마다 다르지만 일반적으로 위 그림과 같은 구조를 가집니다.

1. pointer : 프로세스가 위치한 메모리 주소를 가리키는 포인터
2. process state : 위 프로그램 상태 천이도에서 언급했던 프로세스의 상태(create, ready, running, waiting, terminated)
3. process number : 프로세스 ID(PID)
4. program counter : 프로세스가 다음에 실행할 명령어의 주소
5. registers : 이전까지 수행했던 프로세스의 cpu register 정보(stack pointer 등)
6. memory limits : 프로세스가 차지하는 메모리의 범위
7. list of open files : 프로세스가 사용하는 파일 목록

b) Context Switching 원리

Context Switching은 OS의 Dispatcher에서 담당하게 되고, Interrupt에 의해 Dispatcher가 실행되면 Context Switching을 수행하게 됩니다.

• Preemptive Interrupt : 프로세스의 cpu 점유시간이 Time Quantum을 초과하여 운영체제가 CPU 점유를 중단시키면서 발생하는 Interrupt
• non-Preemptive Interrupt : I/O장치의 호출로 프로세스가 CPU 점유를 포기하면서 발생하는 Interrupt
• System Call : 요청에 따라 커널에 접근하기 위한 인터페이스

• Context Switching은 위 그림과 같은 흐름을 따라갑니다.

1. Interrupt가 발생하여 Context Switching이 시작됩니다. (System Call)
2. CPU 레지스터 값을 커널 스택영역에 저장합니다. 그 후, Context Switching이 발생하는 동안 CPU 레지스터는 커널 프로세스에 대한 정보를 가리키게 됩니다.
3. 커널 스택영역에 저장된 CPU 레지스터 값을 PCB에 저장합니다.
4. 다음 실행될 프로세스를 실행하여 프로세스에 해당하는 PCB 값을 불러옵니다. 그 후, CPU 레지스터는 다음 실행될 프로세스의 PCB의 레지스터 정보를 가리키게 됩니다.
5. 위와 같은 흐름이 반복되면서 Context Switching이 이루어집니다.

c) Context Switching Overhead

: 잦은 Context Switching 때문에 CPU 자원이 Context Switching에 많이 소모되는 문제입니다.

6) 교착상태 (Deadlock)

교착상태(Deadlock)는 모든 스레드 및 프로세스가 자원을 점유하는 동시에 사용을 대기하여 프로그램이 아무 동작도 안하는 상태입니다.
자원을 공유할 수 있는 멀티스레딩 기법을 활용하여 프로그램을 작성하거나 다수의 프로세스가 공용 데이터베이스에 접근하는 시스템을 설계하게 되면 주의해야 하는 동기화 문제입니다.

• 교착상태 필요조건

1. Mutual exclusion (상호 베타)
   : 각 스레드 및 프로세스는 공유 자원을 동시에 사용하지 못합니다.
2. Hold and wait (보유 및 대기)
   : 각 스레드 및 프로세스는 공유 자원 사용을 대기하면서 다른 공유 자원을 보유할 수 있습니다. -> 동시에 공유자원들을 점유하도록 하거나 공유자원들을 모두 점유하지 않으면, 점유하고 있던 공유자원은 해제(자원 활용률 저하, 기아 발생)
3. No preemption (비선점)
   : 각 스레드 및 프로세스는 다른 스레드나 프로세스가 사용하고 있는 자원을 뺏지 못합니다. -> 공유 자원을 강제로 뺏어옴(일반적인 컴퓨터에서는 불가능)
4. Circular wait (환형대기)
   : 각 스레드 및 프로세스가 공유 자원을 점유하면서 사용을 대기 하는 상태인데, 자원할당도상 원형을 이루는 상태입니다. -> 젓가락 번호가 작은 것부터 집게 하면 마지막 철학자는 오른쪽 젓가락부터 집게 되서 환형대기 해제 가능, 짝수 철학자는 왼쪽부터 홀수 철학자는 오른쪽부터 젓가락을 집게 하면 환형대기 해제 가능

• 교착상태 처리

1. 교착상태 방지
   : 교착상태 4가지 필요조건 중 한 가지 이상 불만족
2. 교착상태 회피
   : 교착상태를 다르게 해석(교착상태 : 자원을 잘못 나누어서 deadlock 발생), 각 프로세스가 필요한 자원을 전부 주지않고 분할해서 나누어 줌으로써 자원을 나누어줄 때마다 실시간으로 자원이 고갈될지 확인하여 각 프로세스가 필요한 자원을 모두 주지 않았는데 자원은 고갈되는 상태를 방지(banker's algorithm)
3. 교착상태 검출 및 복구
   : 교착상태를 허용. 프로세스 하나가 교착상태를 지속적으로 확인. 복구는 특정 프로세스를 강제 종료시켜 다른 프로세스에게 자원을 할당. 단점은 계산이나 메모리와 같은 비용이 많이 소모됨
4. 교착상태 무시
   : 아무런 대처도 하지 않음

7) Mutex

Mutex는 Mutual Exclusion의 약자로서 여러 스레드가 공유 자원을 상호 베타적으로 사용하기 위해 활용되는 도구입니다.

• Mutex 도구를 쓰지 않게 되면, 한정된 공유자원을 여러 스레드가 동시에 사용하게 되어 프로그램의 동작에 악영향을 미칠 수 있습니다.
• 여러 스레드 및 프로세스가 Mutex와 같은 동기화 도구를 잘못 쓰게되면, 교착상태(deadlock)에 빠질 수 있습니다.

a) Mutex 활용방법 및 원리

• 임계영역 : 다수의 프로세스나 스레드가 공유자원에 접근하는 영역
• 활용방법

1. Mutex를 획득하고 반환하는 함수로 임계영역을 감싸줍니다. 프로세스는 임계영역에 접근하기 전에 임계영역을 사용할 권리인 Mutex를 획득해야 합니다.
2. 만약, 다른 프로세스나 스레드가 Mutex를 가지고 있을 때 프로세스나 스레드가 임계영역에 접근하면 Mutex가 반환될 때까지 대기합니다.
3. 임계영역에 해당하는 동작이 완료되면 Mutex를 반환합니다.

• 원리

1. Mutex를 획득하게 되면 뮤텍스 인스턴스의 멤버변수 owner는 Mutex를 획득한 프로세스의 메모리주소를 가리키게 됩니다. (획득한 프로세스가 없다면 NULL 주소를 가리킵니다.)
2. Mutex가 반환되지 않은 상태에서 다른 프로세스가 임계영역에 접근한다면 뮤텍스 인스턴스의 owner를 체크할 것이고, owner는 다른 프로세스의 메모리주소를 가리키고 있기 때문에 임계영역에 접근한 프로세스는 대기합니다.

8) Semaphore

Semaphore는 Mutex와 마찬가지로 임계영역을 보호하기 위한 도구입니다. 하지만 Mutex와 다른 점은 임계영역에 여러 프로세스가 접근할 수 있다는 점이고 다른 프로세스에 의해 Semaphore를 해제할 수 있다는 점입니다.

a) Semaphore 원리

9) Monitor

최근 동기화 도구로서 모니터가 사용되고, 주로 java에서 많이 쓰입니다. 세마포어는 오래된 동기화 도구입니다. 세마포어는 어셈블리나 C, 모니터는 java와 같은 좀 더 high language에서 쓰입니다.

• 세마포어는 아래와 같은 번거로움이 있습니다.

1. 세마포어는 임계구역을 감싸야합니다.
2. 세마포어는 인자로 들어온 값을 기억하고 있어야 합니다.

• 모니터는 위의 세마포어의 번거로움을 해소시켜줍니다.

1. java에서 메소드 앞에 synchronized를 붙여줌으로써 메소드간 공유자원에 대한 상호베타를 보장할 수 있습니다.

• 모니터의 원리

1. 기본적으로 모니터는 공유자원에는 한 개의 메소드 및 함수만 접근할 수 있고, 두 개의 queue(베타동기, 조건동기)가 존재합니다.
2. 공유자원을 점유하고 있던 쓰레드가 특정 조건에 의해 wait이 호출되어 조건동기 queue에 block 됩니다.
3. 새로운 쓰레드가 공유자원을 점유합니다.
4. 새로운 쓰레드가 notify를 호출하면 조건동기 queue에 있던 쓰레드의 block이 해제되고, 공유자원을 점유하고 있던 쓰레드가 공유자원 점유를 해제하면 조건동기 queue에 있던 쓰레드가 공유자원을 점유하게 됩니다.

• 모니터의 역할

1. notify와 wait의 호출을 적절히 사용하면 쓰레드의 ordering이 가능합니다.
2. 여러 쓰레드가 교대로 실행되게 하려면? 전역변수를 사용합니다.
   : 하나의 쓰레드는 전역변수가 설정되어 있지 않으면 조건동기 queue에 block되게 하고, 전역번수가 설정되면 쓰레드가 동작 후 notify를 호출하여 다른 쓰레드의 block을 해제시켜줍니다. 그 후, 전역변수 설정을 해제시켜준 후에 해당 쓰레드는 wait을 호출하여 조건동기 queue에 block합니다. notify로 block이 해제된 쓰레드는 동작하게 되고, 동작이 끝난 후 해당 쓰레드도 notify를 호출하여 조건동기 queue에 block된 쓰레드를 해제시켜줍니다. 그 후, 전역변수를 설정해주고 wait을 호출하여 조건동기 queue에 block 합니다.

C. 프로그램 작성 과정

3. 참고

• JSEO의 Philosophers
  https://bigpel66.oopy.io/library/42/inner-circle/9
• 프로세스와 스레드의 차이
  https://gmlwjd9405.github.io/2018/09/14/process-vs-thread.html
• PCB (Process Control Block)
  https://jwprogramming.tistory.com/16
• Context Switching 원리
  https://nesoy.github.io/articles/2018-11/Context-Switching
• 멀티스레드를 사용하는 이유
  https://junshock5.tistory.com/146
• System Call
  https://fjvbn2003.tistory.com/306
• Kernel
  https://genesis8.tistory.com/241
• Mutex 원리
  http://egloos.zum.com/rousalome/v/10003464
• 프로세스 메모리 구조, 시스템 호출
  https://bnzn2426.tistory.com/59
• pthread reference
  http://www.digipine.com/index.php?mid=clan&document_srl=584
• 교착상태
  https://jhnyang.tistory.com/2?category=815411
• 식사하는 철학자 문제
  https://twinw.tistory.com/97
• 뮤텍스와 세마포어의 차이
  https://junghyun100.github.io/Semaphore&Mutex/