[운영체제] Synchronization Examples

들어가며

동기화가 필요한 상황에 동기화를 어떻게 적용했는지 알아봅시다.

---

The Bounded-Buffer Problem (Producer-Consumer Problem)

구성 요소

• N size buffer : 크기가 유한한 버퍼
• Producer thread : 버퍼에 데이터를 추가하는 쓰레드
• Consumer thread : 버퍼의 데이터를 소모하는 쓰레드

 

문제 상황

버퍼가 비었을 때 Consumer thread가 데이터를 소모하려고 하거나, 버퍼가 가득 차있을 때 Producer thread가 데이터를 추가하는 것을 막아야 한다.

 

해결책

당연한 이야기지만, 버퍼가 가득 차 있을 때는 Producer thread가 데이터를 추가하지 못하도록 막고, 버퍼가 비어있을 때는 Consumer thread가 데이터를 사용하지 못하도록 막는다.

 

Semaphore을 추가로 둬서 이를 구현할 수 있다. wait과 signal의 동작은 이전과 같다.

• Semaphore full = 0 : 공유 변수이며 버퍼 내 아이템의 개수
• Semaphore empty = N : 공유 변수이며 버퍼 내 empty slot의 개수

do {
    // Entry Section
    wait (empty);
    wait (mutex);
    
    // Critical Section
    ...
    
    // Exit Section
    signal (mutex);
    signal (full);
    
} while (True);

 

---

Readers-Writers Problem

구성 요소

• Readers : 데이터를 읽기만 하는 프로세스
• Writers : 데이터를 읽고 쓰는 프로세스

 

문제 상황

Reader 간의 동시 접근은 Race Condition을 발생시키지 않음에도 불구하고, 동시적 접근이 불허됩니다.

 

해결책

Reader 간의 동시 접근은 Race Condition을 발생시키지 않습니다. 하지만, 두 개 이상의 Writer가 동시에 실행되거나 Reader와 Writier가 동시에 실행되는 경우 Race Condition이 발생할 수 있습니다. 따라서, 하나의 Reader가 데이터를 읽는 동안에 다른 Reader 또한 데이터를 읽을 수 있게 하면서, Writer의 접근은 막아야 합니다.

 

이번에도 Semaphore가 이용됩니다.

Semahpore wrt = 1 : writers 간의 mutual exclusion을 보장합니다.

Semaphore mutex = 1 : readcount를 critical section으로 만들기 위해 사용됩니다.

Integer readcount = 0 : readers의 개수

 

Writer process

do {
    wait(wrt);
    
    // writing
    
    signal(wrt);
    
} while(true);

 

Reader process

do {
    wait(mutex);
    readcount++;
    if(readcount == 1) wait(wrt);
    signal(mutex);
    
    // reading
    
    wait(mutex);
    readcount--;
    if (readcount == 0) signal(wrt);
    signal(mutex);
    
} while(true);

 readcount를 통해 최초의 reader가 writer가 동작하지 못하도록 막고, 마지막 reader가 writer가 실행될 수 있도록 만듭니다. readcount를 조작하는 부분을 제외하고는 wait() signal()로 둘러싸여져 있지 않으므로 critical section이 아니기 때문에, reader들은 동시에 데이터를 읽을 수 있습니다.

 

하지만, 한 범주의 프로세스가 우선권을 얻게 된다는 것은 starvation이 발생할 수도 있다는 것을 의미합니다. 실제로, 위 코드를 이용하여 reader가 우선권을 갖도록 구현하면 모든 reader가 데이터를 읽을 때 까지 writer는 실행될 수 없습니다. 또한, writer에게 우선권을 주어도 이 문제는 똑같이 발생합니다.

 

starvation을 해소해야 할지, 해소해야 한다면 어떻게 할 수 있을지 한번 생각해봅시다.

 

Dining Philosophers Problem

전제

• N명의 철학자와 N개의 젓가락이 있으며 원형 테이블 앉아 있습니다.
• 철학자는 왼쪽 또는 오른쪽 젓가락을 이용하여 음식을 먹을 수 있으며 왼쪽 젓가락부터 사용합니다.
• 한 젓가락은 한 사람만 사용할 수 있습니다.

문제 상황

모든 철학자가 동시에 왼쪽 젓가락을 사용하는 중에 모두 오른쪽 젓가락을 사용하고자 할 때, 누구도 젓가락을 내려놓을 수 없는 Deadlock이 발생합니다. 

Semaphore chopstick[5] = {1, 1, 1, 1, 1};

do {
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
    
    // eat
    
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    
    // think
    
} while(true);

 

해결책

• N-1명의 철학자만 테이블에 앉을 수 있게 합니다.
• 왼쪽 젓가락과 오른쪽 젓가락을 모두 사용할 수 있을 때만 젓가락을 사용할 수 있도록 합니다.
• 홀수 번째 철학자는 왼쪽 젓가락부터, 짝수 번째 철학자는 오른쪽 젓가락부터 사용하도록 합니다.

이 부분은 Deadlock 파트에서 추가로 다뤄보겠습니다.