[전공생이 설명하는 OS] 동기화 - (6) 식사하는 철학자 문제 (코드 포함)

Dining Philosopher Problem

식사하는 철학자 문제는 다익스트라 선생님께서 논문을 통해 제시하신 대표적인 데드락 상황이다. 위와 같이 원형의 탁자에 5개의 포크가 놓여있다. 스파게티를 먹기 위해서는 2개의 포크를 사용해야한다는 규칙이 있다. 이 상황에서 5명의 철학자가 포크를 한 개씩 잡고 데드락에 빠지면 모두가 굶어 죽는 starvation 이 발생한다..!

철학자가 다 굶어죽는 c++ 코드는 다음과 같다.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>
#define NUM 5
sem_t forks[NUM]; // forks

void *philosopher(void*);


int main(){

	pthread_t threads[NUM];
	for(int i=0; i<NUM; i++)
		sem_init(&forks[i], 0, 1);

    sem_init(&room, 0, 4);

    int start_time, end_time;
    start_time = clock();  // time start!

    for(unsigned long int i=0; i<NUM; i++)
        pthread_create(&threads[i], NULL, philosopher, (void*)i);

    for(int i=0; i<NUM; i++)
        pthread_join(threads[i], NULL);

    end_time = clock();  // time end!
	
    printf("NO DEADLOCK\n");
    printf("Duration: %.2f\n", (double)(end_time-start_time)/CLOCKS_PER_SEC);
	return 0;
}

void pickup(int philosopher_num){
	sem_wait(&forks[philosopher_num % NUM]);
}

void putdown(int philosopher_num){
	sem_post(&forks[philosopher_num % NUM]);
}

void thinking(int philosopher_num){
	printf("philosopher %d is thinking\n", philosopher_num);
	return;
}

void eating(int philosopher_num){
	printf("philosopher %d is eating\n", philosopher_num);
	return;
}

void *philosopher(void *arg){

	int philosopher_num;
	philosopher_num = (unsigned long int) arg;
	
	int eating_count = 10000;
	while(eating_count > 0){

		pickup(philosopher_num);
		printf("philosopher %d picks up the fork %d.\n", philosopher_num, philosopher_num);
		
		pickup(philosopher_num + 1);
		printf("philosopher %d picks up the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);
		
		eating(philosopher_num);
		eating_count -= 1;

		putdown(philosopher_num + 1);
		printf("philosopher %d puts down the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);
		
		putdown(philosopher_num);
		printf("philosopher %d puts down the fork %d.\n", philosopher_num, philosopher_num);
		thinking(philosopher_num);
	}

	return NULL;
}

1. Prevention

이전 포스팅에서 언급했듯이, 데드락을 방지하는 기법에는 Prevention과 Avoidence 기법이 있다. prevention 기법은 교착상태가 발생할 수 있는 4가지 조건(Hold&Wait / Mutual exclusion / Non preemption / Circular wait) 이 모두 만족하지 않도록 적어도 1가지를 방지하는 기법이다. concurrency 가 낮아지고, 자원의 utilization 이 나빠질 수 있다는 단점이 존재한다.

1) 첫번째 방법

교착상태의 4가지 필수 조건 중 하나만 prevention 하면 된다. 그 중에서 순환대기가 만들어지지 않도록 한번에 4명만 식사하게 강제하는 방법이 있다. 세마포를 이용해서 4명만 방에 들어가도록 하고, 4명이 방에 들어있는 동안은 나머지 1명은 밖에서 대기해야한다. 스파게티를 한입 먹으면 포크를 내려놓고 밖으로 나와야한다.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>
#define NUM 5
sem_t forks[NUM]; // forks
sem_t room;

void *philosopher(void*);


int main(){

	pthread_t threads[NUM];
	for(int i=0; i<NUM; i++)
		sem_init(&forks[i], 0, 1);

    sem_init(&room, 0, 4);

    int start_time, end_time;
    start_time = clock();  // time start!

    for(unsigned long int i=0; i<NUM; i++)
        pthread_create(&threads[i], NULL, philosopher, (void*)i);

    for(int i=0; i<NUM; i++)
        pthread_join(threads[i], NULL);

    end_time = clock();  // time end!

    printf("NO DEADLOCK\n");
    printf("Duration: %.2f\n", (double)(end_time-start_time)/CLOCKS_PER_SEC);
	return 0;
}

void pickup(int philosopher_num){
	sem_wait(&forks[philosopher_num % NUM]);
}

void putdown(int philosopher_num){
	sem_post(&forks[philosopher_num % NUM]);
}

void thinking(int philosopher_num){
	printf("philosopher %d is thinking\n", philosopher_num);
	return;
}

void eating(int philosopher_num){
	printf("philosopher %d is eating\n", philosopher_num);
	return;
}

void *philosopher(void *arg){

	int philosopher_num;
	philosopher_num = (unsigned long int) arg;
	
  int eating_count = 10000;
  while(eating_count > 0){

    	sem_wait(&room);  // 4명만 입장 가능
		pickup(philosopher_num);
		printf("philosopher %d picks up the fork %d.\n", philosopher_num, philosopher_num);
		
		pickup(philosopher_num + 1);
		printf("philosopher %d picks up the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);
		
		eating(philosopher_num);
		eating_count -= 1;

		putdown(philosopher_num + 1);
		printf("philosopher %d puts down the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);
		
		putdown(philosopher_num);
		printf("philosopher %d puts down the fork %d.\n", philosopher_num, philosopher_num);
		sem_post(&room);  // 퇴장
		thinking(philosopher_num);
	}

	return NULL;
}

2) 두번째 방법

Hold & wait 하지 않도록 강제하는 방법이다. 즉 한번에 포크를 2개를 얻도록 강제하는 방식이다.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>
#define NUM 5
sem_t forks[NUM]; // forks
sem_t once;

void *philosopher(void*);


int main(){

    pthread_t threads[NUM];
    for(int i=0; i<NUM; i++)
        sem_init(&forks[i], 0, 1);

    sem_init(&once, 0, 1);

    int start_time, end_time;
    start_time = clock();  // time start!

    for(unsigned long int i=0; i<NUM; i++)
        pthread_create(&threads[i], NULL, philosopher, (void*)i);

    for(int i=0; i<NUM; i++)
        pthread_join(threads[i], NULL);

    end_time = clock();  // time end!

    printf("NO DEADLOCK\n");
    printf("Duration: %.2f\n", (double)(end_time-start_time)/CLOCKS_PER_SEC);

    return 0;
}

void pickup(int philosopher_num){
	sem_wait(&forks[philosopher_num % NUM]);
}

void putdown(int philosopher_num){
	sem_post(&forks[philosopher_num % NUM]);
}

void thinking(int philosopher_num){
	printf("philosopher %d is thinking\n", philosopher_num);
	return;
}

void eating(int philosopher_num){
	printf("philosopher %d is eating\n", philosopher_num);
	return;
}

void *philosopher(void *arg){

    int philosopher_num;
    philosopher_num = (unsigned long int) arg;

    int eating_count = 10000;
    while(eating_count > 0){

        sem_wait(&once);  // 한번에 한명만 다 잡을 수 있다.
        pickup(philosopher_num);
        printf("philosopher %d picks up the fork %d.\n", philosopher_num, philosopher_num);

        pickup(philosopher_num + 1);
        printf("philosopher %d picks up the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);
        sem_post(&once);   // 한번에 한명만 다 잡을 수 있다.

        eating(philosopher_num);
        eating_count -= 1;

        putdown(philosopher_num + 1);
        printf("philosopher %d puts down the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);

        putdown(philosopher_num);
        printf("philosopher %d puts down the fork %d.\n", philosopher_num, philosopher_num);

        thinking(philosopher_num);
    }

    return NULL;
}

3) 세번째 방법

자원의 순서를 바꿔서, 순환대기를 끊어내는 방법이다(resource reordering). 포크를 잡을 때 번호가 낮은 것부터 잡도록 하는 것이다. 0번~4번까지 존재한다고 가정하면, 기존에는 4번 철학자는 4번 포크를 잡은 뒤에 0번 포크를 잡으려고 시도했었다. 이 순서를 뒤집어서 4번 철학자가 0번포크를 먼저 잡도록 하면 전체적인 순환이 발생하지 않는다.

이 방법에 경우, 다른 방법과 다르게 추가적인 lock 을 설정하지 않았다는 장점이 있다. 식사하는 철학자 문제에서는 꽤 괜찮은 접근법이지만, resource 의존관계의 복잡성에 따라 구현 난이도가 달라진다는 점, os 의 입장에서는 resource ordering 을 하는 것이 매우 어렵다는 점 등의 단점이 있다. application level 에서 특수한 상황에서는 적용해볼만한 방법이 되겠다.

#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <semaphore.h>
#define NUM 5
sem_t forks[NUM]; // forks

void *philosopher(void*);


int main(){

    pthread_t threads[NUM];
    for(int i=0; i<NUM; i++)
        sem_init(&forks[i], 0, 1);

    sem_init(&room, 0, 4);

    int start_time, end_time;
    start_time = clock();  // time start!

    for(unsigned long int i=0; i<NUM; i++)
        pthread_create(&threads[i], NULL, philosopher, (void*)i);

    for(int i=0; i<NUM; i++)
        pthread_join(threads[i], NULL);

    end_time = clock();  // time end!
	
    printf("NO DEADLOCK\n");
    printf("Duration: %.2f\n", (double)(end_time-start_time)/CLOCKS_PER_SEC);
	return 0;
}

void pickup(int philosopher_num){
	sem_wait(&forks[philosopher_num % NUM]);
}

void putdown(int philosopher_num){
	sem_post(&forks[philosopher_num % NUM]);
}

void thinking(int philosopher_num){
	printf("philosopher %d is thinking\n", philosopher_num);
	return;
}

void eating(int philosopher_num){
	printf("philosopher %d is eating\n", philosopher_num);
	return;
}

void *philosopher(void *arg){

    int philosopher_num;
    philosopher_num = (unsigned long int) arg;

    int eating_count = 10000;
    while(eating_count > 0){

        if (philosopher_num < 4) {

            pickup(philosopher_num);
            printf("philosopher %d picks up the fork %d.\n", philosopher_num, philosopher_num);

            pickup(philosopher_num + 1);
            printf("philosopher %d picks up the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);

        } else { // 4번 철학자

            pickup(philosopher_num + 1); // 0번 포크
            printf("philosopher %d picks up the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);

            pickup(philosopher_num); // 4번 포크
            printf("philosopher %d picks up the fork %d.\n", philosopher_num, philosopher_num);
        } 

        eating(philosopher_num);
        eating_count -= 1;

        putdown(philosopher_num + 1);
        printf("philosopher %d puts down the fork %d.\n", philosopher_num, (philosopher_num + 1) % NUM);

        putdown(philosopher_num);
        printf("philosopher %d puts down the fork %d.\n", philosopher_num, philosopher_num);
        thinking(philosopher_num);
    }

    return NULL;
}

2. Avoidence

위에서 설명했던 방법들은 concurrency 에 제약을 가하는 방식으로 교착상태를 방지한다. 자원 활용도가 떨어지고, concurrency 가 저하된다는 단점이 있다. 이와 반대로 회피하는 기법은, 자원에 대한 요청이 있을 때 deadlock 이 발생하지 않는 안전한 요청인지를 확인하고 허가하는 방식이다. 상대적으로 더 높은 자원 활용률과 concurrency를 보일 수 있다. 대표적인 알고리즘으로는 Banker's Algorithm 이 있다.

Banker's Algorithm

은행원 알고리즘에 대한 좋은 포스팅이 있어서, 소개! 내가 더 잘 설명할 자신이 없다 ㅎ

[운영체제]교착상태 회피-은행원 알고리즘(Banker's Algorithm) 쉬운 예시, 안전상태, 불안전상태

[한 번에 끝내는 운영체제 목차!] Deadlock Avoidance 교착상태 회피 저번 시간에 교착상태 해결 방안 4종류를 알아봤어요 교착상태 예방, 교착상태 회피, 교착상태 탐지, 교착상태 복구! 이렇게 4가지

jhnyang.tistory.com

'CS > Operating System' 카테고리의 다른 글

[전공생이 설명하는 OS] 메모리 관리 - (2) Virtual Memory (0)	2022.06.02
[전공생이 설명하는 OS] 메모리 관리 - (1) Partition/Page/Segment (0)	2022.06.02
[전공생이 설명하는 OS] 동기화 - (5) Deadlock (0)	2022.05.31
[전공생이 설명하는 OS] 동기화 - (4) 생산자 소비자 문제 (0)	2022.05.22
[전공생이 설명하는 OS] 동기화 - (3) 조건동기화 (pthread 예제 코드 포함) (0)	2022.05.22