Chapter 7. 동기화 예제

안녕하세요 파피몬입니다! 운영체제 7단원에 대해 공부해 보았습니다. 

Abraham Silberschatz의 Operating System Concepts 10th edition과 학부 수업을 듣고 정리한 내용입니다. 오개념이 있다면 알려주세요~~

 

이번에는 우리 앞서 배운 동기화 도구들을 통해 고전적인 동기화 문제를 해결해보도록 하자!

 

<유한 버퍼 문제>

papimon.tistory.com/51

앞선 동기화 도구들 1부 포스팅에서 차 있는 버퍼의 갯수를 세는 count 변수의 inconsistency에 대해 알아보고 해결 방법을 알아보았다. 

이제 이 문제를 Semaphore를 통해 해결해보자! 주석을 통해 동작 원리를 설명해 보았다. 

[소비자 & 생산자가 공유하는 자료구조]

int n;
semaphore mutex = 1; //버퍼에 접근하는 소비자&생산자 상호배재 보장하는 이진 세마포
semaphore empty = n; //비어있는 버퍼는 n개로 초기화
semaphore full = 0;  //꽉 찬 버퍼는 0개로 초기화

[생산자] - 소비자를 위해 꽉 찬 버퍼를 생성해주기

while(true){
    // 소비자가 사용할 아이템 생성하기
    wait(empty); //비어있는 버퍼가 0개면 (모든 버퍼가 꽉 차있으면) 대기하기
    wait(mutex); //소비자가 버퍼에 접근 중이면 대기
    // 이제 생성한 아이템을 버퍼에 넣기
    signal(mutex); //생산자의 버퍼 접근 종료
    signal(full); //꽉 찬 버퍼 하나 추가해주기
}

[소비자] - 생산자를 위해 비어있는 버퍼로 전환

while(true){
    wait(full); //꽉 찬 버퍼가 0개면 (채워진 버퍼가 없다면) 대기하기
    wait(mutex); //생산자가 버퍼에 접근 중이면 대기하기
    // 버퍼에서 빼서 사용함
    signal(mutex); //소비자의 버퍼 접근 종료
    signal(empty); //비어있는 버퍼 하나 추가해주기
}

 

<Readers-Writers 문제>

하나의 데이터베이스가 병행 프로세스 간에 공유한다고 생각해보자. 많은 프로세스가 동시에 파일을 읽는 것은 문제가 없다. 하지만 만약 많은 프로세스가 동시에 하나의 파일에 작성한다??? 오 그건 있어서는 안된다. 

 

책에서는 이 Readers-Writers 문제 해결하는 2가지 방식을 소개한다. 

Q1. Writer가 공유 객체에 대해 사용 허가를 안 받았다면, Reader가 대기하는 경우는 없어야 한다!

  - Writer가 Starve 할 수도...

Q2. Writer가 준비가 되었다면, 최대한 빨리 쓸 것!

  - Reader가 Starve 할 수도...

 

구현 예시로는 첫 번째의 방식인 Q1의 해결방식을 소개한다. 

[Reader & Writer가 공유하는 자료구조]

//Writer 하나만 접근 가능하게 상호 배제 보장
//임계구역에 첫 진입하는 Reader와 마지막 Reader도 사용한다 -- Reader들이 읽고 있으면 계속 읽게!
semaphore rw_mutex = 1; 
//Reader가 read_count 갱신할 때 상호 배제 보장
semaphore mutex = 1;
//현재 몇 개의 프로세스가 Read 중 인지 나타냄
int read_count = 0;

[Writer] 

while(true){
    wait(rw_mutex); //reader나 writer가 실행 중인가?
    writing to file
    signal(rw_mutex); //다 작성했다!
}

[Reader] 

while(true){
    wait(mutex);
    read_count++;  //저 Reader 이제 파일 읽겠습니다!
    if(read_count == 1)  //내가 처음 읽기 시작한 Reader 인가요?
        //Writer가 실행할 수 있으니 파악해야 한다
        //Writer가 실행 안하고 있다면, rw_mutex 0으로 바꾸고, Writer의 접근을 차단한다. 
        //Writer가 실행 중이라면, rw_mutex는 0이기에, 현재 Reader는 Block
        //Writer가 종료 된다면, rw_mutex는 1이 되고, 그제서야 Read가 가능하다!
        wait(rw_mutex);  
    signal(mutex);
    Reading done;
    wait(mutex);
    read_count--;  //저 이제 다 읽었어요
    if(read_count == 0)  //제가 마지막으로 읽고 나가는 Reader 인가요?
        signal(rw_mutex);  //Writer 그동안 쓰고 싶으셨을 텐데 이제 쓰세요!
    signal(mutex);
}

위에서 언급 했듯, Reader가 처음에 문 열고 들어와 뒤이어 Reader 프로세스가 계속 수행된다면, Writer는 starvation 상태에 빠지게 된다. 

 

<The Dining-Philosophers Problem>

생각하는 철학자 문제 설명

생각하는 철학자 문제를 살펴보자. 

다섯 명의 생각하는 철학자들이 의자에 앉아 생각하거나, 밥을 먹거나 한다. 여기서 철학자는 자신의 양 옆에 있는 젓가락을 집어 들어야 밥을 먹을 수 있는데 젓가락은 총 5개가 마련되어 있다. 

 

Semaphore로 이 상황을 구현한다면 다음과 같을 것이다. 

[Philosopher i의 상황]

while(true){
    wait(chopstick[i]); //내 왼쪽에 있는 젓가락 획득
    wait(chopstick[(i+1)%5]); //내 오른쪽에 있는 젓가락 획득
    Philosopher i is eating
    signal(chopstick[i]); //내 왼쪽에 있는 젓가락 내려놓기
    signal(chopstick[(i+1)%5]); //내 오른쪽에 있는 젓가락 내려놓기
    Philosopher i is thinking
}

이를 통해 두 명의 인접한 철학자가 동시에 밥을 먹는 경우는 없을 것이다. 하지만 문제가 발생하는 경우가 있으니, 바로 Deadlock이라는 현상이다. (이는 8단원에서 자세히 다룬다)

 

예를 들어 동시에 모든 철학자들이 자신의 왼쪽에 있는 젓가락을 든다면, 모든 철학자가 오른쪽에 있는 젓가락을 획득하기 위해 wait() 상태, 여기선 sleep() 상태에 빠져있을 것이다. 그리고... 그 누구도 sleep() 에서 빠져 나올 수 없을 것이다. 이런 특수한 상황을 Deadlock이라고 하는데, 이는 다음 단원 포스팅에서 알아보도록 하자. 

 

이를 해결하기 위한 솔루션으로 책에서는 다음과 같은 방식을 제안한다. 

  1. 최대 4명만 앉기

  2. 한 철학자가 젓가락 2개를 잡을 수 있는게 확인이 되어야 들 수 있게 해준다. 

  3. 홀수 번호 철학자는 젓가락을 왼쪽->오른쪽 순서로 든다. 

  4. 짝수 번호 철학자는 젓가락을 오른쪽->왼쪽 순서로 든다. 

 

생각하는 철학자 문제는 아주 유명해서 설명을 잘해주시는 유튜브 고수님들이 많다. 그 중 한분의 영상을 공유하며 포스팅을 마치도록 하겠다!