[OS] Chapter 7. 프로세스 동기화

Table of Contents

프로세스 동기화 문제 #

데이터 접근 방식
- 한 저장 공간(메모리, 주소 공간)에 있는 데이터를 연산 실행 주체(CPU, 프로세스)가 읽어와서 연산을 한 후, 다시 저장 공간에 연산 결과를 저장한다.

연산 주체	저장 공간
컴퓨터	하드디스크
CPU	메모리
프로세스	프로세스의 주소 공간

따라서 하나의 저장 공간을 여러 주체가 접근하려고 할 때 경쟁 상태(Race Condition) 가 생길 가능성이 있다.
운영체제에서 Race Condition이 발생하는 경우
- (1) 커널 모드 수행 중에 인터럽트가 발생해서 인터럽트 처리 루틴을 수행할 때
  - 양쪽 모두 커널 코드를 수행하므로 커널 주소 공간을 공유하고 있다.
  - 해결책: 커널 모드 수행 중일 때는 인터럽트를 비활성화한다.
- (2) 커널 모드 수행 중에 다른 프로세스가 시스템 콜을 해서 문맥교환이 일어나고, 다른 프로세스가 커널 모드를 수행할 때
  - 두 프로세스는 데이터를 공유하지 않지만, 시스템 콜을 하는 동안에는 커널 주소 공간에 접근할 수 있다.
  - 해결책: 커널 모드 수행 중일 때는 CPU를 선점하지 않는다.
- (3) 멀티 프로세서에서 공유 메모리 내의 커널 데이터
  - 해결책: 커널 내부의 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 한다.

프로세스 동기화(procee synchronization) 문제 = 병행 제어(concurrency control) 문제
- 공유 데이터에 여러 프로세서가 동시에 접근하는 상황(race condition)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다.
- 일관성 유지를 위해서는 동시에 접근하는 프로세스 간에 실행 순서를 정하는 메커니즘이 필요하다. 즉, 동기화가 필요하다.

크리티컬 섹션 #

critical section
각 프로세스의 코드 영역에 있는 공유 데이터를 접근하는 코드이다.

크릴티컬 섹션 문제의 해결법 충족 조건

조건	설명
상호 배제 (Mutual Exclusion)	어떤 프로세스 하나가 크리티컬 섹션을 수행 중이면 다른 모든 프로세스가 크리티컬 섹션에 들어갈 수 없어야 한다.
진행 (Progress)	아무도 크리티컬 섹션에 없을 때, 어떤 프로세스가 크리티컬 섹션에 들어가고자 한다면, 들어갈 수 있어야 한다.
유한 대기 (Bounded Waiting)	어떤 프로세스가 크리티컬 섹션에 들어가려고 요청하고 기다릴 때, 다른 모든 프로세스가 크리티컬 섹션에 들어갈 수 있는 횟수가 제한되어야 한다.

알고리즘 1

do 
{
  while(turn != 0); // 내차례(turn == 0)일 때까지 대기한다. 
  
  critical section
  
  turn = 1;         // 다른 프로세스 차례(turn == 1)로 만든다. 
  
  // ...
} while(1);

turn이 내 차례이면 크리티컬 섹션에 들어간다.
문제점
- 교대로만 들어갈 수 있다. 그래서 어떤 프로세스가 한 번만 크리티컬 섹션에 들어갈 때에는 다른 프로세스가 여러번 들어가길 원한다고 해도 들어갈 수가 없게 된다. (Progress 조건에 부합하지 않게 된다.)

알고리즘 2

do 
{
  flag[me] = true;
  while(flag[other] == true); // 상대방의 플래그가 false일 때까지 대기한다. 
  
  critical section
  
  flag[me] = false;           // 내 작업이 끝났음을 알린다.  
  
  // ...
} while(1);

flag를 만들어서 상대방 값을 확인하고 크리티컬 섹션에 들어간다.
문제점
- 두 프로세스 모두가 flag[me] = true 인 상태로 무한정 대기할 수 있다.

알고리즘 3 (Peterson’s Algorithm)

do 
{
  flag[me] = true;            // 크리티컬 섹션에 들어가겠다는 의사표명을 한다. 
  turn = other;               // 상대방의 턴으로 바꾼다. 
  
  // 상대방이 의사를 표명했고, 상대방 턴일 때 대기한다.  
  while(flag[other] == true && turn = other);
  
  critical section
  
  flag[me] = false;           // 내 작업이 끝났음을 알린다.  
  
  // ...
} while(1);

turn과 flag를 둘 다 사용한다.
- 세 가지 조건을 모두 충족한다.
문제점: Busy Waiting(= Spin Lock)
- while(flag[other] == true && turn = other)에서 계속 CPU와 메모리를 쓰면서 기다리게 된다.

이런 과정을 하드웨어적으로 수행할 수 있도록 지원한다면 간단하게 해결 가능하다.
- (1) lock의 값을 읽고 (2) lock의 값을 true로 설정하는 것을 한 번에 수행한다.

do 
{
  while(Test_and_set(lock)); // lock이 false이면 true로 설정하고 들어간다. 
  
  critical section
  
  lock = false;
  
  // ...
} while(1);

세마포어 #

Semephores
추상 자료형으로써, integer 값을 가지며 자원의 개수를 나타낸다.
두 가지 연산으로만 접근이 가능하다.
- 세마포어 S가 있을 때
- (1) P(S) 연산: 자원을 가져간다.
```
while(S <= 0); // 자원이 없으면 기다린다. 
S--;
```
- (2) V(S) 연산: 자원을 내놓는다.
```
S++;
```

Busy Waiting(= Spin Lock) 방식 #

크리티컬 섹션 문제를 세마포어로 해결하면…

semaphore mutex;

do 
{
  P(mutex);
  critical section
  V(mutex);
  
  //...
} while(1);

Block & Wakeup(= Sleep Lock) 방식 #

세마포어를 다음과 같이 정의한다.
- value, L → PCB → PCB → PCB …

typedef struct
{
  int value;         // 세마포어
  struct proces * L  // 프로세스 대기(wait) 큐
} semaphore;

Block()
- 그 프로세스를 suspend 시키고 PCB를 세마포어의 대기(wait) 큐에 넣는다.
Wakeup(P)
- 프로세스 P를 wakeup 시키고 PCB를 준비(ready) 큐로 옮긴다.

(1) P(S) 연산

S.value--;       // 자원을 가져가기로 한다. 
if (S.value < 0) // 근데 자원이 없다.  
{
  add process to S.L  // 대기 큐에 넣고
  block();            // 대기한다. 
}

(2) V(S) 연산

S.value++;        // 자원을 내놓기로 한다. 
if (S.value <= 0) // 내놓아도 자원이 없다. 즉 자원이 없어서 잠들어 있는 프로세스가 있다. 
{
  remove process P from S.L  // 대기 큐에서 빼서
  Wakeup(P);                 // 깨운다. 
}

두 방식의 비교 #

일반적으로 Block & Wakeup이 좋다.
크리티컬 섹션의 길이가 긴 경우, 그동안 기다리지 않는 Block & Wakeup이 더 좋다.
하지만 크리티컬 섹션의 길이가 짧은 경우에는, block과 wakeup 상태를 바꾸는 데 오버헤드가 들기 때문에 Busy Wait가 더 좋을 수 있다.

세마포어의 종류 #

Counting Semaphore
- 도메인이 0이상인 임의의 정수값이다.
- 자원을 카운팅하는 데 쓰인다.
Binary Semaphore(=mutex)
- 0과 1값만 가질 수 있는 세마포어이다.
- 주로 상호 배제 (lock/unlock)에 쓰인다.

교착상태와 기아 #

교착상태(Deadlock)
- 둘 이상의 프로세스가 서로 상대방이 가진 자원을 얻기 위해 무한히 기다리는 현상이다.
- 예: Dining-Philosophers problem
- 해결책: 자원을 얻을 수 있는 순서를 설정한다.
기아(Starvation)
- 프로세스가 suspend 당하고 세마포어 큐에서 영원히 나갈 수 없는 현상을 말한다.

고전적인 동기화 문제들 #

Bounded-Buffer problem (Producer-Consumer problem) #

공유되는 메모리의 버퍼 크기가 유한한 환경에서, 자원을 생산하는 Producer와 사용하는 Consumer가 여럿일 때 발생하는 문제이다.

공유 데이터
- 버퍼 및 버퍼 조작 변수(empty/full 버퍼의 시작 위치)
동기화 변수
- mutex: 상호 배제 필요
  - 동일 버퍼에 작업하지 않기 위해 Binary Semaphore가 필요하다.
- full/empty: 가용 자원을 세는 것이 필요
  - 한정적인 버퍼가 모두 사용되었을 때를 대비해서 Counting Semaphore가 필요하다.

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

Producer 코드

do 
{
  produce an item in x  // 자원 x를 만든다. 
  
  P(empty);         // 자원을 만들만한 빈 버퍼가 있는지 확인하고 획득한다. 
  P(mutex);         // 해당 버퍼에 lock을 건다. 
  
  add x to buffer
  
  V(mutex);         // 버퍼에 lock을 푼다. 
  V(full);          // 생산된 자원의 개수를 늘린다. 
} while(1);

Consumer 코드

do 
{
  P(full);          // 자원이 만들어진 버퍼가 있는지 확인하고 획득한다. 
  P(mutex);         // 해당 버퍼에 lock을 건다. 
  
  remove an item from buffer to y
    
  V(mutex);        // 버퍼에 lock을 푼다. 
  V(empty);        // 사용한 자원의 개수를 늘린다.  
  
  consume the item in y
  
} while(1);

Readers and Writers problem #

한 프로세스가 공유 데이터 DB를 Write 중일 떄는 다른 모든 프로세스가 접근할 수 없다. 하지만 Read는 여럿이서 동시에 해도 되는 경우에 발생하는 문제이다.

공유 데이터
- DB 자체
- readCount: 현재 DB에 접근 중인 Reader의 수
동기화 변수
- mutex: 공유 데이터 readCount에 접근 제어를 위해
- db: Reader와 Writer가 DB에 올바르게 접근하도록 하기 위해

int readCount = 0;
DB 자체;

semaphore mutes = 1, db = 1;

Writer 코드

P(db); // 공유 데이터를 사용하기 위해 lock을 건다. 

writing DB

V(db); // lock을 푼다.

Reader 코드

P(mutex); // readCount를 사용하기 위해 lock을 건다. 
readCount++; // 읽기로 한다. 
if (readCount == 1) P(db); // 최초의 Reader라면 Write를 금하기 위해 공유 데이터에 lock을 건다. 
V(mutex); // readCount lock을 푼다. 

reading DB

P(mutex);
readCount--;
if (readCount == 0) V(db); // 모든 Reader가 다 읽었으면 Writer가 쓸 수 있게 공유 데이터의 lock을 푼다. 
V(mutex);

기아(Starvation) 문제가 발생할 수 있다.
- Reader가 계속해서 들어오면 Writer는 영영 DB에 접근할 수 없다.
- Reader의 수를 제한해서 해결할 수 있겠다.

Dining-Philosophers problem #

생각하다가 배고프면 밥을 먹는 5명의 철학자들이 원탁에 둘러 앉았다. 젓가락을 양쪽 사람과 하나씩 공유하고 있을 때 발생하는 문제이다.

동기화 변수

// 1로 초기화되어 있다. 즉, 한 번에 한 명만 쓸 수 있다. 
semaphore chopstick[5];

Philosopher 코드

do
{
  P(chopstick[i]);  // 왼쪽 젓가락을 잡는다. 
  P(chopstick[(i + 1) % 5]); // 오른쪽 젓가락을 잡는다. 
  
  eat();
  
  V(chopstick[i]);
  V(chopstick[(i + 1) % 5]);
  
  think();
}while(1);

교착상태(Deadlock) 문제가 발생할 수 있다.
- 모든 Philosopher가 동시에 배가 고파서 왼쪽 젓가락을 집은 경우. 아무도 식사를 할 수 없다.
해결 방법
- (1) 5명 중에 배고픈 4명만 동시에 식탁에 앉을 수 있게 한다.
- (2) 젓가락 2개를 모두 집을 수 있을 때만 젓가락을 집을 수 있게 한다.
- (3) 짝수 Philosopher는 왼쪽, 홀수 Philosopher는 오른쪽 젓가락부터 집을 수 있게 한다.

동기화 변수

enum {thinking, hungry, eating} state[5];
semaphore self[5] = 0; // 젓가락 2개를 모두 집을 수 있는가 (처음은 권한 없음)
semaphore mutex = 1; // Philosopher의 상태를 바꿀 수 있는 권한

Philosopher 코드

do 
{
  pickup(i);
  eat();
  putdown(i);
  think();
} while(1);

void pickup(int i)
{
  P(mutex);  // 상태를 변경하기 위해 mutex에 lock을 건다. 
  state[i] = hungry;
  test(i);
  V(mutex);  // 상태 변경을 완료해서 mutex를 unlock 한다. 
  P(self[i]); // 젓가락 2개를 집을 수 없다면 기다린다. 가능하면 lock을 건다. 
}

void putdown(int i)
{
  P(mutex);
  state[i] = thinking;
  test((i + 4) % 5); // 왼쪽 철학자에 대해 test를 해서 젓가락을 준다. 
  test((i + 1) % 5); // 오른쪽 철학자에 대해 test를 해서 젓가락을 준다. 
  V(mutex);
}

// 젓가락 2개를 모두 집을 수 있는지 테스트한다. 
void test(int i)
{
  if (state[(i + 4) % 5] != eating && // 왼쪽 철학자가 밥을 먹지 않고
      state[i] == hungry &&           // 내가 지금 배고프고
      state[(i + 1) % 5] != eating)   // 오른쪽 철학자가 밥을 먹지 않을 때 
  {
    state[i] = eating;
    V(self[i]);  // 밥먹는 권한을 갖는다. unlock을 한다. 
  }
}

모니터 #

세마포어의 문제점
- 코딩하기 힘들다.
- 한번의 실수가 모든 시스템에 치명적인 영향을 준다.
- 정확성을 검증하는 것이 어렵다.
- 자발적 협력이 필요하다.

모니터(Monitor)
- 동시 수행중인 프로세스 사이에서 추상 데이터 형식의 안전한 공유를 보장하기 위해 만들어진, high-level synchronization construct이다.

monitor monitor_name
{
  // 공유 변수
  shared variable declaration
  
  // 공유 변수에 접근할 수 있는 함수를 구현한다. 
  procedure body P1 (...) { ... }
  procedure body P2 (...) { ... }
  procedure body P3 (...) { ... }
  
  // 초기화 함수 
  {
    initialization code
  }
}

모니터 내에서는 한 번에 하나의 프로세스만 활동 가능하다.
프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.
프로세스가 모니터 안에서 기다릴 수 있게 하기 위해서 condition variable을 사용한다.
- condition variable은 wait()과 signal() 연산으로만 접근 가능하다.
- wait()
  - signal()로 빠져나갈 수 있을 때까지 계속 suspend되게 한다.
- signal()
  - suspend된 프로세스 중에 하나의 프로세스가 빠져나갈 수 있게 한다.
  - suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

Bounded-Buffer problem #

monitor bounded_buffer
{
  int buffer[N];
  condition full, empty; // 자신의 큐에 프로세스를 매달아서 wait() 혹은 signal()을 한다. 
  
  void produce(int x)
  {
    if there is no empty buffer
      empty.wait(); // 비어 있는 버퍼를 줄서서 기다린다. 
    add x to an empty buffer
    full.signal(); // 혹시 생성된 버퍼가 없어서 기다리는 프로세스가 있는지 알아보고 깨워준다. 
  }
  
  void consume(int *x)
  {
    if there is no full buffer
      full.wait();
    remove an item from buffer and store it to *x
    empty.signal();
  }
}

Dining-Philosophers problem #

monitor dining_philosopher
{
  enum {thinking, hungry, eating} state[5];
  condition self[5];
  
  void pickup(int i)
  {
    state[i] = hungry;
    test(i);
    if (state[i] != eating)
      self[i].wait(); // 밥 먹을 수 없으면 대기.
  }
  
  void putdown(int i)
  {
    state[i] = thinking;
    test((i + 4) % 5); // 왼쪽 철학자에게 젓가락을 준다. 
    test((i + 1) % 5); // 오른쪽 철학자에게 젓가락을 준다. 
  }
  
  // 젓가락 2개를 모두 집을 수 있는지 테스트한다. 
  void test(int i)
  {
    if (state[(i + 4) % 5] != eating && // 왼쪽 철학자가 밥을 먹지 않고
      state[i] == hungry &&             // 내가 지금 배고프고
      state[(i + 1) % 5] != eating)     // 오른쪽 철학자가 밥을 먹지 않을 때 
    {
      state[i] = eating;
      self[i].signal();  // 밥을 먹을 수 있게 한다.
    }
  }
  
  void init()
  {
    for (int i = 0; i < 5; i++)
      state[i] = thinking;
  }
}

// Each Philosopher:
do 
{
  pickup(i);
  eat();
  putdown(i);
  think();
} while(1);