16. 철학자들은 왜 굶어 죽었을까?: Chapter 7. Synchronization Examples (Part 2 ~ Part 3)

식사하는 철학자들 문제

• 식사하는 철학자 문제 가정
  • 5명의 철학자가 5개의 의자에 각각 앉아 있음
  • 테이블 중앙에는 밥이 있음
  • 테이블에는 다섯개의 젓가락이 놓여 있음
  • 철학자들은 배가 고파지면 자신에게 가장 가까이 있는 두 개의 젓가락(왼쪽 젓가락과 오른쪽 젓가락)을 집으려고 시도함
  • 철학자들은 한번에  한 젓가락만 집을 수 있음
  • 철학자들은 이미 옆 사람의 손에 들어간 젓가락을 집을 수 없음
  • 동시에 두 개의 젓가락을 집으면 젓가락을 놓지 않고 식사를 함
  • 식사를 마치면 두 개의 젓가락을 모두 놓고 다시 생각을 시작함
• 식사하는 철학자 문제는 교착 상태Deadlock과 기아Starvation을 발생시키지 않고 여러 스레드에게 여러 자원을 할당해야 할 필요를 단순하게 표현한 것

 

 

세마포 해결안Semaphore Solution

• 각 젓가락을 하나의 이진 세마포로 표현함

• 철학자는 그 세마포에 wait() 연산을 실행하여 젓가락을 집으려고 시도함
• 또한 해당 세마포에 signal() 연산을 실행하여 자신의 젓가락을 놓음
• 이 해결안은 인접한 두 철학자가 동시에 식사하지 않는다는 mutual exclusion 조건을 보장하지만, deadlock을 야기할 가능성이 있음
  • 5명의 철학자가 동시에 배가 고프게 되어 각각 자신의 왼쪽 젓가락을 잡는다고 가정
  • chopstick의 모든 원소들은 0이 됨
  • 각 철학자는 그들의 오른쪽 젓가락을 집으려고 하면 영원히 기다려야 함. 즉 데드락 발생
• 데드락 문제의 여러 가지 해결책
  • 최대 4명의 철학자들만이 테이블에 동시에 앉을 수 있도록 함
  • 한 철학자가 젓가락 두개를 모두 집을 수 있을 때만 젓가락을 집도록 허용함
  • 비대칭 해결안 사용
    • 홀수 번호의 철학자는 왼쪽 젓가락을 집은 다음 오른쪽 젓가락을 집도록 함
    • 짝수 번호의 철학자는 오른쪽 젓가락을 집은 다음 왼쪽 젓가락을 집도록 함
• 그러나 이러한 데드락 문제의 해결책이 반드시 기아의 가능성도 제거 하는 것은 아님

 

 

모니터 해결안Monitor Solution

• 철학자들은 양쪽 젓가락 모두 얻을 수 있을 때만 젓가락을 집을 수 있다는 제한을 강제함
• enum 자료구조 State 통해 철학자가 처할 수 있는 세가지 상태를 구분함
• condition 변수 Self를 사용하여 철학자 i가 배고프지만 자신이 원하는 젓가락을 집을 수 없을 때 젓가락 집기를 미룰 수 있도록 함
• 젓가락은 분배는 모니터 DiningPhilosophers에 의해 제어됨
• 각 철학자는 식사하기 전에 pickup() 연산을 반드시 호출하고, 이 연산이 성공적으로 끝나면 철학자는 식사할 수 있음
• 각 철학자는 식사를 마친 후에 putdown() 연산을 반드시 호출해야 함
• 이 해결안은 이웃한 두 철학자가 동시에 식사하지 않는다는 것과 데드락이 발생하지 않는다는 것을 보장함
• 그러나 철학자가 굶어죽는 것, 즉 기아 상태가 발생 가능하다는 것에 유의해야 함
• 실습 코드(C)

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

#define true 1
#define NUM_PHILS 500

enum {THINKING, HUNGRY, EATING} state[NUM_PHILS];

pthread_mutex_t mutex_lock;
// condition variable
// 이 변수에 접근할 때는 항상 동기화가 됨
pthread_cond_t cond_vars[NUM_PHILS];

void init(){
    int i;
    for (i=0; i<NUM_PHILS; i++){
        state[i] = THINKING;
        pthread_cond_init(&cond_vars[i], NULL);
    }
    pthread_mutex_init(&mutex_lock, NULL);
    srand(time(0));
}

int leftOf(int i){
    return (i+NUM_PHILS-1) % NUM_PHILS;
}

int rightOf(int i){
    return (i+1) % NUM_PHILS;
}

void think(int id){
    printf("%d: Now, I'm thingking...\n", id);
    usleep((1+rand() % 50)*10000);
}

void eat(int id){
    printf("%d: Now, I'm eating...\n", id);
    usleep((1+rand()%50)*10000);
}

void test(int i){
    if(state[i] == HUNGRY && state[leftOf(i)]!=EATING && state[rightOf(i)] != EATING)
    {
        state[i] = EATING;
        pthread_cond_signal(&cond_vars[i]);
    }
}

void pickup(int i){
    // mutex lock 획득
    // pthread_mutex_lock(&mutex_lock);
    // critical section
    state[i] = HUNGRY;
    test(i);
    while(state[i] != EATING){
        pthread_cond_wait(&cond_vars[i], &mutex_lock);
    }
    // exit section
    // pthread_mutex_unlock(&mutex_lock);
}

void putdown(int i){
    // mutex lock 획득
    // pthread_mutex_lock(&mutex_lock);
    // critical section
    state[i] = THINKING;
    test(leftOf(i));
    test(rightOf(i));
    // exit section
    // pthread_mutex_unlock(&mutex_lock);
}

void *philosopher(void *param){
    // 받아온 idx 주소의 값을 id에 넣어줌
    int id = *((int *)param);
    while (true){
        think(id);
        pickup(id);
        eat(id);
        putdown(id);
    }
}

int main(int argc, char const *argv[])
{
    int i;
    pthread_t tid;
    // mutex lock, conditin variables, 철학자 상태 초기화
    init(); 

    for (i=0; i<NUM_PHILS; i++){
        // philisopher 스레드 5개 생성  
        // pid를 (void *)로 타입캐스팅 한 idx의 주소를 넘겨줌
        pthread_create(&tid, NULL, philosopher, (void *)&i); 
    }

    for (i=0; i<NUM_PHILS; i++)
        pthread_join(tid, NULL);
    return 0;
}

왼쪽: NUM_PHILS를 5로 한 경우의 실행 결과 이미지 / 오른쪽: NUM_PHILS를 50으로 했을 때의 실행 결과 이미지

• 실습 코드(JAVA)

package com.os_study;

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
// 재진입 가능 (cpu에서 context switch가 발생했을 때 재진입을 가능하게 해주는 패키지)
import java.util.concurrent.locks.ReentrantLock;

enum State{
    THINKING, HUNGRY, EATING
}

public class DiningPhilosophers {
    public static void main(String[] args) {
        int numOfPhils = 5;
        Philosopher[] philosophers = new Philosopher[numOfPhils];
        DiningPhilosopherMonitor monitor = new DiningPhilosopherMonitor(numOfPhils);
        for (int i=0; i<philosophers.length; i++){
            new Thread(new Philosopher(i, monitor)).start();
        }
    }

    private static class Philosopher implements Runnable{
        private int id;
        private DiningPhilosopherMonitor monitor;
        
        public Philosopher(int id, DiningPhilosopherMonitor monitor){
            this.id = id;
            this.monitor = monitor;
        }
        
        @Override
        public void run() {
            while (true){
                think();
                monitor.pickup(id);
                eat();
                monitor.putdown(id);
            }
        }

        private void think() {
            try {
                System.out.println(id + ": Now I'm thinking...");
                Thread.sleep((long)(Math.random()*500));
            } catch (InterruptedException e) {}
        }

        private void eat() {
            try {
                System.out.println(id + ": Now I'm eating...");
                Thread.sleep((long)(Math.random()*50));
            } catch (InterruptedException e) {}
        }
    }

    private static class DiningPhilosopherMonitor {
        private int numOfPhils;
        private State[] state;
        private Condition[] self;
        private Lock lock;

        public DiningPhilosopherMonitor(int num) {
            numOfPhils = num;
            state = new State[num];
            self = new Condition[num];
            lock = new ReentrantLock();
            for (int i=0; i<num; i++){
                state[i] = State.THINKING;
                self[i] = lock.newCondition();
            }
        }

        private int leftOf(int i){
            return (i + numOfPhils - 1) % numOfPhils;
        }

        private int rightOf(int i){
            return (i + 1) % numOfPhils;
        }

        private void test(int i){
            if (state[i] == State.HUNGRY &&
                    state[leftOf(i)] != State.EATING &&
                    state[rightOf(i)] != State.EATING)
            {
                state[i] = State.EATING;
                self[i].signal();
            }
        }

        public void pickup(int id) {
            lock.lock();
            try {
                state[id] = State.HUNGRY;
                test(id);
                if (state[id] != State.EATING)
                    self[id].await();
            } catch (InterruptedException e){

            }
            finally {
                lock.unlock();
            }
        }

        public void putdown(int id) {
            lock.lock();
            try {
                state[id] = State.THINKING;
                test(leftOf(id));
                test((rightOf(id)));
            } finally {
                lock.unlock();
            }
        }
    }
}

numOfPhils를 5로 한 경우의 실행 결과 이미지

 

 

7.5 대체 방안들Alternative Approaches

• 다중 코어 시스템의 등장과 함께 이러한 여러 처리 코어의 이점을 극대화할 수 있는 병행 어플리케이션 개발에 관한 압력이 증가하게 됨
• 그러나 병행 어플리케이션은 race condition, deadlock과 같은 라이브니스 위험을 증가시킴
• 전통적으로 mutex lock, 세마포, 모니터와 같은 기법이 이러한 쟁점을 해결하기 위해 사용되어 왔음
• 그러나 처리 코어의 개수가 증가할수록 race condition과 deadlock위험이 없는 다중 스레드 어플리케이션을 설계하는 작업은 점점 더 어려워지고 있음
• 스레드-세이프Thread-Safe 어플리케이션 설계에 도움을 줄 수 있는 프로그래밍 언어와 하드웨어의 다양한 기능
  • 트랜잭션 메모리
    • 데이터베이스 이론 분야에서 출발한 아이디어로 프로세스 동기화 전략을 제공함
    • 메모리 트랜잭션: 메모리 일기와 쓰기  연산의 원자적인 연속적 순서
    • 한 트랜잭션의 모든 연산이 완수되면 메모리 트랜잭션은 확정commit됨
    • 그렇지 않으면 그 시점까지 완수된 모든 연산은 취소되고 트랜잭션 시작 이전의 상태로 되돌려야roll-back함
    • 트랜잭션 메모리는 소프트웨어 또는 하드웨어로 구현될 수 있음
      
      • 소프트웨어 트랜잭션 메모리STM
        • 특별한 하드웨어 없이 소프트웨어 만으로 구현됨
      • 하드웨어 트랜잭션 메모리HTM
        • 하드웨어 캐시 계층 구조와 캐시 일관성 프로토콜 사용
  • OpenMP
    • 컴파일러 디렉티브와 API로 구성됨
    • ex) #pragma omp parallel
    • 스레드의 생성과 관리가 OpenMP 라이브러리에 의해서 처리되어 응용 개발자들은 신경 쓰지 않아도 됨
  • 함수형 프로그래밍
    • 함수형 프로그래밍은 명령형 언어가 제공하는 패러다임과 많이 다른 패러다임을 따름
    • 근본적인 차이는 함수형 언어는 상태를 유지하지 않는다는 것을 들 수 있음
    • 함수형 언어는 변경 가능 상태를 허용하지 않기 때문에 race condition이나 deadlock과 같은 쟁점에 대해 신경 쓸 필요가 없음