Operating System - Ch07. Synchronization example

본 글은 Operating System Concepts 10판을 기준으로 작성되었습니다...!

 

 

크앙~

챕터 6에서는 동기화 문제에 대한 이야기를 여럿 했었다.

이번 챕터에서는 프로세스 동기화 예시에 대해서 알아보자.

---

Typical Sychronization Problems...

보통 Semaphore로 해결할 수 있고, Mutex lock과  Condition variables로 해결할 수도 있다.

 

1. Bounded-Buffer Problem (한정 버퍼 문제, Producer-Consumer problem)

 

공유 자원을 두 프로세스가 동시에 이용하기 때문에 꼬이는 문제. Race condition이라고 함.

// 생산자 코드
void Producer(data) 
{
    while(count == N) {};
    buffer[in] = data;
    in = (in + 1) % N;
    count++;
}

// 소비자 코드
void Consumer(data)
{
    while(count == 0) {};
    data = buffer[out];
    out = (out + 1) % N;
    count--;
}

다음 코드에서는 두 가지 문제가 있다.

1. count가 Critical section 내부에 있고 두 프로세스가 동시에 접근/수정함, 즉 Critical section 보호가 안됨

2. Busy waiting이 있어 CPU Utilization이 떨어짐

 

이 문제들은 Semaphore를 사용해서 해결할 수 있음.

 

1.1 Semaphore를 이용한 해결 방법

 

세마포어를 사용하면 busy waiting을 하지 않고, critical section보호가 가능해진다. 동기화 문제 해 ★ 결

semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

empty, mutex, full 세마포어를 세 개 구현하고 사용한다. mutex는 critical section보호를 위한 것, empty는 busy waiting을 해결하기 위한 것임. wait은 챕터 6에서 본 것처럼 티켓을 발급받고 기다리다가 내 차례가 오면 티켓을 건네고 입장한다고 보면 편하다.

// 생산자 코드
void Producer(data)
{
    wait(empty); // empty > 0일 때까지 기다림, empty > 0이 되면 empty를 감소시킴
    wait(mutex); // 잠금
    /*
    버퍼에 데이터 추가.
    */
    signal(mutex); // 잠금 해제
    signal(full); // full 증가
}

// 소비자 코드
void Consumer(data)
{
    wait(full); // full > 0까지 기다림, full > 0이 되면 full을 감소시킴.
    wait(mutex); // 잠금
    /*
    버퍼에서 데이터 빼냄
    */
    signal(mutex); // 잠금 해제
    signal(empty); // empty 증가시킴
}

또한 동기화 문제를 Mutex lock과 condition variable을 이용해서도 해결이 가능하다.

 

1.2 Mutex lock과 condition variable을 이용한 해결 방법

MutexLock mutex;
CondVar not_full, not_empty; // Conditional variable

// 생산자 코드
void Producer(data) 
{
    lock(mutex); // 잠금
    while(count == N) // count가 꽉 찼을 때
    {
        wait(not_full); // 기다림.
    }
    /*
     버퍼에 데이터 저장
    */
    count++; 
    signal(not_empty); // 신호를 준다.
    unlock(mutex); // 잠금 해제
}

// 소비자 코드
void Consumer(data)
{
    lock(mutex) // 잠금
    while(count == 0) 
    {
        wait(not_empty); // 기다림.
    }
    /*
    버퍼에서 데이터 빼냄
    */
    count--;
    signal(not_full); // 신호를 준다.
    unlock(mutex); // 잠금 해제
}

세마포어와 거의 동일한 개념으로 동작함. 

 

2. Readers and Writers Problem (독자 - 작가 문제)

 

작가들은 공유자원을 수정하기 때문에 단 한명만 접근해야 하지만, 독자는 여럿이서 공유자원에 접근하는 것이 가능하다. 단, 독자들이 읽고 있을 때에는 작가가 수정해서는 안될 것.

semaphore wrt = 1; // 읽기/쓰기를 분리하는 역할
semaphore mutex = 1; // 잠금용
int readcount = 0; // 현재 독자의 수

세 가지 세마포어를 구현, readcount, mutex, wrt를 구현한다.

readcount : 지금 독자의 수, 0일 때 작가가 접근 가능

mutex: 잠금 역할, critical section인 readcount를 보호하는 역할.

wrt: 쓰기/읽기 작업을 완전히 분리하기 위한 것, 최초의 독자와 마지막 독자가 wrt를 제어할 것.

void Writer()
{
    wait(wrt);
    /*
      쓰기 시작
    */
    signal(wrt);
}

void Reader()
{
    wait(mutex); // 잠금
    ++readcount; // 독자의 수 증가
    if(readcount == 1) // 누군가가 읽고 있다면,
        wait(wrt); // 쓰지 마.
    signal(mutex) // 잠금 해제
    /*
    읽기 시작
    */
    wait(mutex); // 잠금
    --readcount; // 독자의수 감소, 읽기 끝.
    if(readcount == 0) // 아무도 읽고있지 않다면,
        signal(wrt); // 이제 써도 돼.
    signal(mutex); // 잠금 해제
}

 

3. Dining-Philosophers Problem (식사하는 철학자 문제)

 

식사하는 철학자와 데드락 상태

  철학자는 테러리스트와 협상하지 않는다.

  Diijkstra가 정의한 문제, 원탁에 다섯 명의 철학자들이 앉아있다. 철학자들은 사색에 잠겨있고, 이 때 다른 철학자들과 대화하지 않고 생각만 한다. 그러다 배가 고파지면, 젓가락 하나를 집고, 다른 하나를 집은 후, 밥을 먹을 수 있다. 그리고 다 먹으면 양손의 젓가락을 내려놓고 다시 사색에 잠긴다.

 

뭔소리야?

 

  즉 내가 배고픈데 자신 옆에 철학자가 밥을 먹고 있으면 젓가락을 내려놓기 전까지는 나는 못먹는다는 소리. 젓가락은 공유 자원이고, 다섯의 프로세스 or 스레드가 눈치게임을 하는 것임. 이를 통해 기아상태에 빠지는 것을 방지할 수 있는데,  "기아"라는 말이 여기서 나왔다고 함.

semaphore chopstick[5] // 젓가락 다섯개

먼저 젓가락 다섯개를 세마포어로 정의한다.

void Philosopher (int i)
{
    while(true)
    {
        // 사색
        wait(chopstick[i]); // 하나 들고
        wait(chopstick[(i+1) % 5]; // 또 하나 들음
        // 먹음
        signal(chopstick[i]); // 하나 놓고
        signal(chopstick[(i+1) % 5)]; // 또 하나 놓음
    }
}

이렇게 구현하면, 데드락이 발생할 수 있음. 

동시에 모두 배고파져서 젓가락 하나씩 집었으면 모두 다 굶어죽는다는 것

데드락을 해결하기 위해 생각을 조금 바꿀 필요가 있음.

#define N 5
#define L(i) ((i+N-1)%N)
#define R(i) ((i+1)%N)

int state[5]; // 5명의 상태 정의
semaphore mutex = 1;
semaphore s[N]; // 현재 밥을 먹을 수 있는가

void test(int i) // 밥을 먹을 수 있는지 체크하는 함수
{
    if(state[i] == HUNGRY && state[L(i)] != EATING && state[R(i)] != EATING) // 배고픈데 양 옆이
    {                                                                        // 안먹고 있으면
        state[i] = EATING; // 먹는다.
        signal(s[i]); // 나가서 wait할 거라 signal 보냄.
    }
}

void pickup(int i)
{
    wait(mutex);
    state[i] = HUNGRY;
    test(i);
    signal(mutex);
    wait(s[i]);
}

void putdown(int i)
{
    wait(mutex);
    state[i] = THINKING;
    test(L(i));
    test(R(i)); // 양 옆의 누군가가 배고프면 test에서 signal을 보내줌.
    signal(mutex);
}

void philosopher(int i)
{
    while(true)
    {
        //사색
        pickup(i);
        //식사
        putdown(i);
    }
}

자바에 있는 monitor 기능을 통해서도 해결이 가능하다고 되있는데

자바 안쓴다잉!!!!