Philosophers - Mandatory

(Dining) Philosophers

Philosophy (from Greek, philosophia, literally "love of wisdom") is the study of general and fundamental questions about existence, knowledge, values, reason, mind, and language. Such questions are often posed as problems to be studied or resolved. The term was probably coined by Pythagoras (c. 570 – 495 BCE). Philosophical methods include questioning, critical discussion, rational argument, and systematic presentation. Classic philosophical questions include: Is it possible to know anything and to prove it? What is most real? Philosophers also pose more practical and concrete questions such as: Is there a best way to live? Is it better to be just or unjust (if one can get away with it)? Do humans have free will? Historically, "philosophy" encompassed any body of knowledge. From the time of Ancient Greek philosopher Aristotle to the 19th century, "natural philosophy" encompassed astronomy, medicine, and physics. For example, Newton’s 1687 Mathematical Principles of Natural Philosophy later became classified as a book of physics. In the 19th century, the growth of modern research universities led academic philosophy and other disciplines to professionalize and specialize. In the modern era, some investigations that were traditionally part of philosophy became separate academic disciplines, including psychology, sociology, linguistics, and economics. Other investigations closely related to art, science, politics, or other pursuits remained part of philosophy. For example, is beauty objective or subjective? Are there many scientific methods or just one? Is political utopia a hopeful dream or hopeless fantasy? Major sub-fields of academic philosophy include metaphysics ("concerned with the fundamental nature of reality and being"), epistemology (about the "nature and grounds of knowledge [and]... its limits and validity"), ethics, aesthetics, political philosophy, logic and philosophy of science.

 

언제나 그랬 듯, 과제의 Introdution은 구현 내용, 방향과 아무런 관련이 없습니다.

개요

Minishell과 3서클을 이루는 과제인 Philosophers과제 리뷰를 시작하겠습니다. 많은 Cadet이 철학자 과제를 사건의 지평선에서 다룹니다. 이전 2서클의 그래픽, 프로세스 통신, 알고리즘 이 3개의 과제가 난이도가 있기 때문에 많은 블랙홀 데드라인을 빼았기고 맙니다.

 

그래서 기수 동료들을 여기에서 잃기도 합니다. Minishell이 그렇듯, 이 과제도 난이도가 있거든요. 여기를 넘기면 c++을 만날 수 있습니다. 대신 miniRT만 하구요.

 

해당 과제는 멀티 프로세스와 스레딩을 학습하는 과제입니다. 쓰레드의 개념과 다중 쓰레드를 활용한 프로그램이 어떻게 안정성과 정확성을 가져갈 수 있는지 알아갑시다.

 

Dining philosophers problems는 알고리즘 문제에서 아주 유명하다고 합니다.

운영체제의 교착(데드락)상태를 설명하기 위한 문제. 1965년에 에츠허르 다익스트라가 만든 문제이다.

식사하는 철학자 문제는 컴퓨터과학에서 동시성과 교착 상태를 설명하는 예시로, 여러 프로세스(또는 스레드)가 동시에 돌아갈 때 교착 상태가 나타나는 원인을 직관적으로 알 수 있다.

 

과제에서는 어떻게 소개할까요?

 

• One or more philosophers sit at a round table. There is a large bowl of spaghetti in the middle of the table.

한 명 이상의 철학자가 원형 식탁에 앉습니다. 테이블의 가운데에 큰 스파게티 그릇이 있습니다.

• The philosophers alternatively eat, think, or sleep. While they are eating, they are not thinking nor sleeping; while thinking, they are not eating nor sleeping; and, of course, while sleeping, they are not eating nor thinking.

철학자는 먹거나, 생각하거나, 잠을 잡니다. 한 번에 오직 한 가지 행동만 수행합니다.

• There are also forks on the table. There are as many forks as philosophers. • Because serving and eating spaghetti with only one fork is very inconvenient, a philosopher takes their right and their left forks to eat, one in each hand.

탁자에는 철학자 수만큼 이나 포크가 놓여 있습니다. 철학자는 양손에 포크를 들어야만 식사를 할 수 있습니다.

• When a philosopher has finished eating, they put their forks back on the table and start sleeping. Once awake, they start thinking again. The simulation stops when a philosopher dies of starvation.

철학자가 식사를 마치면, 테이블에 포크를 내려놓고 잠을 자기 시작합니다. 일단 잠에서 깨면, 그들은 다시 생각하기 시작합니다. 철학자가 굶어 죽었을 때, 프로그램을 종료합니다.

• Every philosopher needs to eat and should never starve.

모든 철학자는 굶주리지 않도록 먹어야합니다.

• Philosophers don’t speak with each other.

철학자는 서로 얘기하지 않습니다.

• Philosophers don’t know if another philosopher is about to die.

철학자는 다른 철학자가 곧 죽게 될지 알지 못합니다.

• No need to say that philosophers should avoid dying!

당연히 철학자들은 당연히 죽지 않아야 합니다!

목표 1

◦  Your(s) program(s) should take the following arguments: number_of_philosophers time_to_die time_to_eat time_to_sleep [number_of_times_each_philosopher_must_eat]

프로그램은 철학자 수, 죽는 시간, 먹는 시간, 자는 시간, [각 철학자가 먹어야 하는 횟수]을 인자로 받습니다.

◦ number_of_philosophers: The number of philosophers and also the number of forks.

철학자의 수 : 또한 포크의 개수와 같습니다.

◦ time_to_die (in milliseconds): If a philosopher didn’t start eating time_to_die milliseconds since the beginning of their last meal or the beginning of the simulation, they die.

죽는 시간 (1/1000초 단위) : 만약 시뮬레이터가 시작한 이후 혹은 마지막 식사 후 철학자가 먹지 않고 죽는 시간을 지난다면 사망합니다.

◦ time_to_eat (in milliseconds): The time it takes for a philosopher to eat. During that time, they will need to hold two forks.

식사 시간 (1/1000초 단위) : 식사하는데 걸리는 시간입니다. 두 개의 포크가 필요합니다.

◦ time_to_sleep (in milliseconds): The time a philosopher will spend sleeping.

자는 시간 (1/1000초 단위) : 수면에 소요되는 시간입니다.

◦ number_of_times_each_philosopher_must_eat (optional argument): If all philosophers have eaten at least number_of_times_each_philosopher_must_eat times, the simulation stops. If not specified, the simulation stops when a philosopher dies.

철학자가 먹어야 하는 횟수 (선택적 인자) : 만약 모든 철학자가 최소 식사 횟수를 충족하면 시뮬레이터를 종료합니다. 지정되지 않으면 철학자가 죽었을 때, 시뮬레이터가 종료됩니다.

◦ Each philosopher should be a thread.

각 철학자는 스레드이어야 합니다.

◦ There is one fork between each pair of philosophers. Therefore, if there are several philosophers, each philosopher has a fork on their left side and a fork on their right side. If there is only one philosopher, there should be only one fork on the table.

한 쌍의 철학자들 사이에는 포크 하나가 있습니다. 그래서 철학자가 오직 한명이라면 포크가 하나 밖에 없습니다. 식사를 할 수 없겠죠?

◦ To prevent philosophers from duplicating forks, you should protect the forks state with a mutex for each of them

철학자가 포크를 복제하는 것을 막기 위해, 포크의 상태를 뮤텍스로 보호해야 해야합니다.

 

목표 2

About the logs of your program

프로그램의 로그에 대해

Any state change of a philosopher must be formatted as follows

철학자의 상태 변화가 다음을 따라야 합니다.

 

◦ timestamp_in_ms X has taken a fork

[시간] N 철학자 포크를 집음.

◦ timestamp_in_ms X is eating

[시간] N 철학자 식사.

◦ timestamp_in_ms X is sleeping

[시간] N 철학자 취침.

◦ timestamp_in_ms X is thinking

[시간] N철학자 생각.

◦ timestamp_in_ms X diedReplace timestamp_in_ms with the current timestamp in milliseconds and X with the philosopher number.

timestamp_in_ms는 ms단위, X는 철학자 번호로 바꾸시오.

• A displayed state message should not be mixed up with another message.
• 상태 메시지는 다른 메시지와 섞이면 안됩니다.
• A message announcing a philosopher died should be displayed no more than 10 ms after the actual death of the philosopher.
• 철학자의 사망 선고 메시지는 실제 사망 시간 기록과 10ms를 초과하면 안됩니다.
• Again, philosophers should avoid dying
• 다시한번 말하지만, 철학자는 죽음을 피해야 합니다.
• Your program must not have any data races.
• 프로그램에서 data races가 발생하면 안됩니다.

---

구현 전 사전 지식

1. Thread

2. Data race

---

1. Thread - Pipex와 이어지는 설명이 되겠습니다

프로그램에서 다수의 작업을 요구하면 그만큼의 프로세스가 필요한데, 프로세스는 특성 상, 동시 작업을 수월하게 할 수가 없습니다. 프로세스 생성시에 필요한 자원을 복사하여 생성(느린 속도)해야하고 프로세스 간의 정보 교환도 별도의 과정이 필요하므로 이러한 이유들이 쓰레드의 탄생 배경이 됩니다.

 

스레드는 프로세스 내에서 실행되는 작은 실행 단위로, 프로세스 내부의 공유된 자원(메모리, 파일 등)을 공유합니다. 한 프로세스 내에서 여러 스레드가 동시에 실행될 수 있으며, 스레드 간의 통신은 해당 프로세스의 공유된 자원을 통해 이루어집니다. 또한, 생성과 속도가 빠르고, 적은 메모리를 점유하며, 정보 교환이 쉽고 Context Switching 부하가 적지만 그 대가로 자원 선점과 동기화 문제가 발생하는데 이것이 과제에서 고려할 data race입니다.

 

그리고 과제에서 허용된 pthread 함수는, 함수 포인터와 데이터 포인터를 받아 하나의 함수를 실행하는 단위가 됩니다. 하나의 함수가 철학자가 수행할 루틴이라는 의미가 되겠습니다.

 

쓰레드 사용에 있어 반드시 고려해야할 안정성과 정확성의 문제와, 겪게될 교착 상태(dead lock)을 알아야 합니다.

 

교착 상태

교착상태(Deadlock)는 멀티스레딩 환경에서 발생할 수 있는 문제 중 하나로, 두 개 이상의 스레드가 서로의 작업이 끝나기를 기다리며 무한히 대기하는 상태를 말합니다. 교착상태는 다음의 네 가지 조건이 동시에 충족될 때 발생합니다. 이 조건을 "교착상태의 필요조건"이라고 부릅니다.

1. 상호 배제: 최소 하나의 자원은 배타적으로(하나의 스레드만 사용 가능하도록) 사용될 수 있어야 합니다.
2. 보유 대기: 최소 하나의 자원을 가진 상태에서 다른 자원을 기다리고 있어야 합니다.
3. 비선점: 다른 스레드에 의해 현재 사용 중인 자원을 강제로 뺏을 수 없어야 합니다.
4. 순환 대기: 스레드 간의 자원 대기 관계가 순환 형태로 형성되어야 합니다.

이 조건들이 모두 충족되면, 두 개 이상의 스레드가 서로에게 필요한 자원을 요청하고 대기하며, 결과적으로 시스템이 더 이상 진행하지 못하는 상태에 빠집니다. 그렇다면 과제에서 이런 상황이 어떻게 발생하게 될까요?

 

과제에서 철학자는 쓰레드이어야 한다고 했습니다. 따라서, 교착 상태를 일으키는 자원은 '포크'가 되겠습니다. 철학자는 좌, 우의 포크를 점해야 식사를 할 수 있습니다. 그런데 1번 철학자의 오른쪽 포크는, 1번 철학자의 오른쪽 철학자(예를들어 2번)의 왼쪽 포크로써, 이 포크를 두고 서로가 경쟁하게 됩니다. 이런식으로 모든 철학자가 한 손에만 포크를 쥐고 있다면 아무도 식사를 하지 못하고 전부 죽게될 것입니다.

 

n명의 철학자가 원형 테이블에 앉아있는 상황에서 n번 철학자는 n -1 번 철학자와 n + 1번 철학자가 식사를 하지 않아야(포크 놓기) 식사할(포크 집기) 수 있습니다. 다만, 철학자들은 서로 대화할 수 없고, 누가 죽을지를 알지 못합니다. 도덕성을 발휘할 수 없다는 것이죠. 이들은 양보하지 않습니다!

 

여기서 허용 함수를 설명하겠습니다.

• int usleep(useconds_t microseconds) - unistd.h
  • useconds_t : 부호 없는 정수형, 마이크로초 단위 대기시간을 의미
  • microseconds : 1,000,000 마이크로초 = 1초
  • milliseconds : 1,000 밀리초 = 1초 200 * 1000
• int gettimeofday(struct timeval tv, struct timezone tz)
  • tv : struct timeval 타입의 포인터, 함수가 현재 시간을 저장할 구조체
  • tz : 사용하지 않는 매개변수로 일반적으로 널(시스템 시간) 전달 (특정 지역 도는 시간 관련 정보를 나타내는데 사용)
  • struct timeval
  • { time_t tv_sec; // 초 단위의 시간(UTC협정시, GMT그리니치 평균시로 부터 경과한 시간을 의미) suseconds_t tv_usec; // 마이크로초 단위의 시간 (useconds_t과는 역할, 사용 시기만 다름) };
  • tv_sec과 tv_usec를 다룰 때, 자료형 선택에 주의하시기 바랍니다. 단위가 크므로, 데이터 손실이 일어날 수 있습니다.
• int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void ), void arg)
  • thread: 생성된 스레드의 정보를 저장할 pthread_t 타입의 변수에 대한 포인터입니다.
  • attr: 스레드의 속성을 지정하는 pthread_attr_t 타입의 포인터입니다. 보통 NULL을 전달하여 기본 속성을 사용합니다.
  • start_routine: 스레드가 실행할 함수의 포인터입니다. 이 함수는 스레드가 시작되면 실행됩니다.
  • arg: start_routine 함수에 전달할 인자입니다.
• int pthread_detach(pthread_t thread)
  • thread: 분리할 스레드의 식별자(pthread_t)입니다.
  • 분리된 스레드는 자동으로 리소스를 해제하므로, 해당 스레드가 종료되면 관련된 메모리 등의 리소스가 자동으로 해제됩니다. 하지만 주의할 점은 분리된 스레드의 상태에 접근하려 할 때 예측할 수 없는 결과가 발생할 수 있다는 것입니다. 스레드가 종료되었더라도 해당 스레드가 사용한 자원에 접근하려면 안전한 방법을 사용해야 합니다.
  pthread_detach 함수는 다음과 같은 상황에서 유용합니다:
  • 생성한 스레드가 메인 스레드나 다른 스레드와 독립적으로 실행되고, 해당 스레드의 종료 후 자원 해제를 자동으로 처리하고자 할 때.
  • 생성한 스레드의 종료 상태를 기다리지 않고 계속해서 다른 작업을 수행하고자 할 때.
  분리된 스레드는 리소스 해제 등을 자동으로 처리하므로, 필요에 따라 사용하면 편리합니다.
• int pthread_join(pthread_t thread, void retval)
  • thread: 종료될 때까지 대기할 스레드의 식별자입니다. 이는 pthread_create 함수에서 반환한 스레드 식별자를 사용합니다.
  • retval: 생성한 스레드의 종료 값을 저장할 포인터입니다. 만약 스레드 함수가 pthread_exit를 호출하여 반환 값을 지정한 경우, 이 값을 retval 포인터로 받아올 수 있습니다. 일반적으로는 NULL을 사용하여 반환 값을 받지 않을 수도 있습니다.
• int pthread_mutex_init(pthread_mutex_t mutex, const pthread_mutexattr_t attr)
  • mutex: 초기화할 뮤텍스 변수의 포인터입니다. 초기화된 뮤텍스는 이 변수에 저장됩니다.
  • attr: 뮤텍스의 특성을 지정하는 속성 변수의 포인터입니다. 일반적으로 NULL을 사용하여 기본 특성을 사용합니다.
  pthread_mutex_init 함수의 주요 목적은 뮤텍스를 초기화하는 것으로, 이 함수를 호출하여 뮤텍스를 설정하고나서 이후에 pthread_mutex_lock, pthread_mutex_unlock 등의 함수를 사용하여 뮤텍스를 활용할 수 있게 됩니다.
• int pthread_mutex_lock(pthread_mutex_t mutex)
  • mutex: 뮤텍스 변수의 포인터입니다. 획득하려는 뮤텍스를 가리키는 변수입니다.
  pthread_mutex_lock 함수는 뮤텍스를 획득하려고 시도하는 함수로, 다음과 같은 동작을 수행합니다:
  • 뮤텍스가 현재 다른 스레드에 의해 보유되고 있다면, 호출한 스레드는 뮤텍스가 해제될 때까지 대기합니다. 이를 블로킹(blocking) 상태라고 합니다.
  • 뮤텍스가 다른 스레드에 의해 보유되지 않고 있다면, 호출한 스레드는 뮤텍스를 획득하고 실행을 계속합니다.
• int pthread_mutex_unlock(pthread_mutex_t mutex)
  • mutex: 해제하려는 뮤텍스 변수의 포인터입니다.
  pthread_mutex_unlock 함수는 뮤텍스를 해제하는 함수로, 다음과 같은 동작을 수행합니다:
  • 호출한 스레드가 뮤텍스를 보유하고 있다면, 해당 뮤텍스를 해제하고 다른 스레드가 뮤텍스를 획득할 수 있도록 합니다.
  • 만약 호출한 스레드가 뮤텍스를 보유하고 있지 않다면, 이 함수 호출은 무시됩니다.
• int pthread_mutex_destroy(pthread_mutex_t mutex)
  • mutex: 제거할 뮤텍스 변수의 포인터입니다.
  pthread_mutex_destroy 함수를 호출하여 뮤텍스를 제거할 때는 몇 가지 주의해야 할 점이 있습니다:
  1. pthread_mutex_destroy 함수를 호출하기 전에 해당 뮤텍스가 획득되지 않은 상태로 있는지 확인해야 합니다. 즉, 다른 스레드에 의해 현재 보유되고 있지 않은 상태여야 합니다. 만약 뮤텍스를 보유한 상태에서 제거하면 예측하지 못한 동작이 발생할 수 있습니다.
  2. 제거한 뮤텍스를 다시 사용하려고 하면 정의되지 않은 동작이 발생할 수 있습니다. 따라서 뮤텍스가 더 이상 필요하지 않을 때에만 pthread_mutex_destroy 함수를 호출해야 합니다.

2. Data race

https://kr.mathworks.com/products/polyspace/static-analysis-notes/what-data-races-how-avoid-during-software-development.html

데이터 레이스(Data Race)는 멀티스레딩 환경에서 발생하는 문제로, 둘 이상의 스레드가 동시에 하나의 공유된 자원에 접근하고 쓰기를 시도할 때 발생합니다. 이러한 상황에서 어떤 스레드가 먼저 데이터를 변경하는지 알 수 없고, 그로 인해 예측 불가능한 결과가 발생할 수 있습니다.

 

데이터 레이스가 발생하는 주요 이유는 다음과 같습니다:

1. 경쟁 조건: 여러 스레드가 동시에 공유 데이터에 접근하고 수정하려고 할 때, 어떤 스레드가 먼저 실행될지 예측할 수 없게 됩니다. 이로 인해 스레드 간의 실행 순서에 따라 데이터의 최종 상태가 달라질 수 있습니다.
2. 비동기성: 멀티스레딩 환경에서는 각 스레드가 병렬로 실행되기 때문에, 스레드 간의 실행 시간이나 순서를 예측하기 어렵습니다. 따라서 동시에 공유된 자원에 접근하는 경우, 데이터 레이스가 발생할 수 있습니다.
3. 동기화 부재: 적절한 동기화 메커니즘이나 도구를 사용하지 않고 여러 스레드가 공유된 자원에 접근하면 데이터 레이스가 발생할 가능성이 높아집니다. 동기화를 통해 스레드 간의 안전한 자원 접근을 보장할 수 있습니다.
4. 원자성 부족: 공유 데이터에 대한 연산이 원자적이지 않을 때(즉, 한 번의 연산으로 완전히 수행되지 않을 때) 데이터 레이스가 발생할 수 있습니다. 이는 특히 복잡한 연산이나 여러 단계의 작업이 필요한 경우에 발생할 수 있습니다. *과제에서 고려할 필요는 없습니다.

데이터 레이스는 예측할 수 없는 결과를 초래하며, 이를 방지하기 위해서는 동기화 메커니즘(뮤텍스 락(mandatory), 세마포어(bonus) 등)을 사용하여 공유 자원에 대한 안전한 접근을 보장하거나, 원자적인 연산을 사용해야 합니다. 동기화 없이 멀티스레드 프로그래밍을 진행할 때는 주의가 필요하며, 데이터 레이스를 최소화하기 위해 적절한 설계와 동기화 기법을 사용해야 합니다.

 

Data race가 발생하는 예시 코드를 보겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define NUM_THREADS 2
#define NUM_INCREMENTS 1000000

int sharedData = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void *incrementCounter(void *threadID) {
    for (int i = 0; i < NUM_INCREMENTS; ++i) {
        // 뮤텍스 락
        //pthread_mutex_lock(&mutex);

        sharedData++; // 공유된 변수 증가 연산

        // 뮤텍스 언락
        //pthread_mutex_unlock(&mutex);
    }
    pthread_exit(NULL);
}

int main() {
    pthread_t threads[NUM_THREADS];

    // 두 개의 스레드 생성
    for (long t = 0; t < NUM_THREADS; ++t) {
        int result = pthread_create(&threads[t], NULL, incrementCounter, (void *)t);
        if (result) {
            fprintf(stderr, "Error: pthread_create() returned %d\n", result);
            exit(EXIT_FAILURE);
        }
    }

    // 모든 스레드의 실행이 종료될 때까지 대기
    for (long t = 0; t < NUM_THREADS; ++t) {
        int result = pthread_join(threads[t], NULL);
        if (result) {
            fprintf(stderr, "Error: pthread_join() returned %d\n", result);
            exit(EXIT_FAILURE);
        }
    }

    // 최종 결과 출력
    printf("Final value of sharedData: %d\n", sharedData);

    // 뮤텍스 소멸
    pthread_mutex_destroy(&mutex);

    return 0;
}

 

현실로 비유가 될 지 모르겠지만 한번 해보려고 합니다.

 

A, B  두 명의 사람이 sharedData라는 블럭을 2,000,000개까지 함께 쌓을 것입니다. 다만, 실제로 블럭을 쌓는 것이 아닌, 말로 소통하지도 않고 생각으로만 쌓기로 정했습니다. 각각 1,000,000개의 블럭을 쌓아 목표 개수에 도달할 것입니다. 그리고 벽에 종이 하나를 붙인 다음 '갯수 : 0'을 적고 다음과 같은 규칙을 정했습니다.

1. 블럭은 반드시 하나씩 쌓고, 쌓을 때마다 종이에 개수를 표시할 것.
2. 블럭을 쌓기 전에 종이에 표시된 개수를 확인하고 쌓을 것.
3. 블럭을 쌓기 전에 확인했던, 종이에 표시된 개수를 믿을 것. 적으려고 할때 쓰여있는 표기된 개수는 믿지 말것! (규칙이 이상하지만..)

코드의 mutex_lock, mutex_unlock이 어떤 의미를 갖는지 두 가지 상황을 제시하겠습니다.

 

1. lock, unlock이 없는 경우 (경쟁 조건과 동기화의 부재를 의도)

 

A, B는 열심히 서로가 쌓은 블럭 개수를 확인하며 둘 다 1,000,000개의 블럭 개수를 채웠습니다. 그런데, 아무리 여러 번 블럭 쌓기 놀이를 해도 결과가 2,000,000개가 되지 않았습니다. 둘은 거짓말을 하지 않았습니다. 왜 이런일이 발생할까요? 어떤 일이 있었는지 봅시다.

결과를 예측할 수 없음

A와 B는 종이의 '0'을 확인하고 블럭을 쌓기 시작했습니다. A가 블럭을 쌓고 종이에 '1'을 표시했습니다. B역시도 블럭을 하나 쌓고 종이에 '1'을 표시했습니다. 시작부터 무언가 잘못되었다고 생각하지 않고 둘은 블럭을 쌓았습니다. A는 두 번째 블럭을 쌓기 전, 종이의 '1'을 확인하고는 "아직 B가 블럭을 하나도 쌓지 않았군!"이라며 블럭을 쌓으러 갔습니다. B도 두 번째 블럭을 쌓기 전, A와 똑같은 생각을 하며 블럭을 쌓으러 갔습니다.

 

A가 갑자기 힘을 내기 시작했습니다. 블럭을 빠르게 쌓으며 종이에 2, 3, 4, .... 9 숫자를 적어나가기 시작했습니다. A가 아홉 번째 블럭을 쌓고 종이에 '9'를 적자마자, 두 번째 블럭을 쌓고 돌아온 '규칙 3'대로 숫자 '2'를 적으며 세 번째 블럭을 쌓으러 갔습니다. A가 열 번째 블럭을 쌓기 전, 종이를 확인했더니 '2'를 보고는 열 번째 블럭을 쌓고 숫자 '3'을 표기했습니다.

 

비유가 우스꽝스럽지 않나요? A, B 스레드는 공유 자원(변수)을 변화시킬 때 메모리에서 값을 가져올 것입니다. 메모리에서 값을 가져온 시점이, 값이 변화되어 저장되는 시점순서와 순차적 보장이 되지 않기 때문에 이런 일이 발생하게 되는 것입니다.

 

 2. lock, unlock을 추가한 경우

 

A, B는 두 개의 종을 달아두고, 다음과 같은 규칙을 추가했습니다.

 

블럭을 쌓기 전 1번 종을 치고, 종이에 적은 다음 2번 종을 치자. 한 사람이 1번 종을 치고 2번 종을 치기 전까지 다른 사람은 1번 종 앞에서 기다리고 있는 거야!

안정성과 정확성을 확보

비로소 A, B는 목표치 2,000,000개를 채울 수 있게된 것입니다.

---

구현

static void	eating(t_philo *philo)
{
	pthread_mutex_lock(philo->r_fork);
	message("has taken a fork", philo);
	pthread_mutex_lock(philo->l_fork);
	message("has taken a fork", philo);
	message("is eating", philo);
	ft_usleep(philo->system->time_to_eat, philo);
    pthread_mutex_lock(philo->status);
	philo->lifespan = get_time();
	philo->num_of_meals++;
    pthread_mutex_unlock(philo->status);
	pthread_mutex_unlock(philo->l_fork);
	pthread_mutex_unlock(philo->r_fork);
}

fork는 다른 철학자(스레드)와의 공유 자원으로 뮤텍스 보호를 이루어야 하고, status는 사망 시간을 계산할 때 모니터링 스레드와의 공유 자원으로 뮤텍스 보호를 이루어야 합니다.

static int	simulate(t_sys *sys)
{
	t_uint	i;

	if (sys->num_of_philo == 1)
	{	
		printf("0 1 has taken a fork\n");
        	ft_usleep(sys->time_to_die, NULL);
		printf("%u 1 died\n", sys->time_to_die);
	}
	else
	{
		i = 1;
		if (!simulate_thread(sys, i))
			return (ft_error("ptread_create", sys));
		ft_usleep(sys->time_to_eat / 2, NULL);
		i = 2;
		if (!simulate_thread(sys, i))
			return (ft_error("ptread_create", sys));
		i = 0;
		while (i < sys->num_of_philo)
			pthread_join(sys->philos[i++].thread, NULL);
	}
	ft_exit(sys);
	return (0);
}

철학자 문제의 가장 전형적인 풀이는 홀수와 짝수를 나누는 것입니다. 모든 철학자가 포크를 하나씩 집는 교착 상태를 방지하기 위해 순서를 미리 정하는 방법입니다.

 

철학자가 1명인 경우에는 결과가 자명하기 때문에 예외 처리했습니다. 직접 스레드를 생성하여 처리해도 될 것 같습니다. 그러면 인원이 다수일 경우를 봅시다.

 

먼저 홀수 철학자가 먼저 루틴을 수행할 수 있도록 스레드를 실행한 후, time_to_eat의 절반 정도만큼 대기시간을 걸어두고 짝수 철학자를 실행하여, 모든 홀수가 식사를 마치고 바로 짝수가 식사할 수 있도록 했습니다.

 

물론, 이는 전체 인원이 짝수일 경우에 이상적인 결과를 나타냅니다. 전체 인원이 홀수인 경우에는 마지막 홀수 철학자가 1번 때문에 식사하지 못하므로 다른 방법으로 처리합니다.

 

왜 생각하는 시간은 주어지지 않았을까?

 

과제에서 생각하는 시간은 주어지지 않았습니다. 생각하는 시간은 다음과 같이 정의됩니다.

 

수면이 끝나고 다음 식사를 하기까지의 대기시간

 

문제는 전체 인원이 짝수가 아닌 홀수일 때 반드시 한 명이 식사 시간 x 2만큼 기다려야 한다는 것입니다. 그래서 어떤 철학자도 죽지 않는 time_to_die(죽는 시간)는 식사 시간 x 3이상은 되어야 합니다. (단, time_to_eat + time_to_sleep >= time_to_die가 아닌 경우)

 

세 명의 철학자가 코드대로 식사를 한다고 생각해 봅시다. 그러면 테이블에서 식사를 할 수 있는 사람은 반드시 한 명 뿐입니다. 남은 두 명은 포크를 두 개 가질 수 없기 때문이죠. 다음 식사도 한 명이기 때문에 남은 한 명은 두 명의 식사를 기다리게 되었습니다.

 

3 610 200 200으로 프로그램을 실행했다고 합시다. 만약 1번이 식사를 마친 후, 2번이 식사를 마쳤다면, 1번은 잠에서 깨어 식사를 할 준비가 됩니다. 그러면 이 프로그램을 실행할 때 마다 어떤 스레드가 먼저 실행될지 알 수 없기 때문에 3번의 생존은 확률 게임이 되어버렸습니다. 또한 1번이 먼저 식사를 하지 않았다면, 그리고 다음 순서 누군지도 확실하지 않다면, 생존 확률 게임의 주인공은 실행할 때 마다 달라질 것입니다.

 

그래서 홀수, 짝수를 나누어 실행함과 생각하는 시간을 부여함으로써 이를 해결할 수 있게 됩니다.

 

홀수, 짝수를 나누는 것은 반드시 식사 시간 x 2만큼 기다려야 하는 인원(이타적인 철학자)을 지정할 수 있는 것이고, 생각하는 시간은 이타적인 철학자가 반드시 죽지 않도록 할 수 있는 장치입니다.

 

생각하는 시간을 부여하지 않으면 수면을 마치자마자 식사를 할 수 있게 되어 이타적인 철학자와 포크 경쟁을 하게 됩니다. 이러면 식사를 못하게 될 수 있습니다. 따라서 저는 다음과 같이 의도하여 코드를 작성했습니다.

 

"잠에서 깨어났으면 양심적으로 생각하는 시간을 가져라!"

(니 옆자리 죽는다)

이와 관련하여 과제는 다음과 같이 요구합니다.

1. 철학자는 죽지 않도록 먹어야 합니다.

2. 철학자는 죽음을 피해야 합니다.

3. 철학자는 서로 대화하지 않습니다.

4. 철학자는 누군가 죽게 될 것인지를 알지 못합니다.

 

이타적인 철학자의 주변 철학자들이 의도적으로 한 차례를 쉬어주는 상황은 이 요구 조건 3, 4에 반하게 됩니다. 하지만 생각하는 시간을 부여하는 것은 철학자들이 자기 루틴을 수행하는 것이므로, 저는 개인적으로 생각하는 시간이 주어지지 않은 이유가 과제를 해결하는 입장에서 이를 고려하도록 하기 위함으로 보고 있습니다.

---

마치며

다음 글은 semaphore를 이용한 구현입니다.