운영체제 강의노트 정리 - 프로세스 동기화

Operating System

프로세스 동기화

배경

생산자 소비자 문제에서 각 프로세스는 공유 메모리에 접근하므로 공통 변수와 버퍼를 공유한다. 이 때 공유 변수의 값이 결과에 영향을 주므로 각 프로세스에서의 수행이 병행적으로 이루어지면 실행되는 순서에 따라 올바르게 동작하지 않을 수 있다.

이처럼 병행으로 수행되는 여러 프로세스가 공통된 데이터를 조작할 때 결과가 접근 순서에 의해 결정되면, 경합 상태race condition가 존재한다고 말한다.

어떠한 코드 문장이 원자적으로 수행되어도 원하지 않는 결과가 발생할 수 있다.

// P1 : a = a + 1; b = b + 1;
// P2 : b = b * 2; a = a * 2;
a = a + 1;  // P1
b = b * 2;  // P2
b = b + 1;  // P1
a = a * 2;  // P2

위의 코드에서 변수 a와 b의 값이 같을 것을 예상하였으나 기대한 결과가 나오지 않는다.

프로세스 동기화를 통해 이러한 문제를 해결한다.

임계 구역 문제

Critical Section

프로세스 코드의 일부분. 다른 프로세스와 공동으로 사용하는 변수, 테이블, 파일 등을 변경하는 부분을 말한다.

임계 구역의 실행은 상호 배타적으로 일어나야 한다. 즉 한 프로세스가 임계 구역을 실행하고 있다면 다른 프로세스는 임계 구역에 진입할 수 없어야 한다.

이를 위해 각 프로세스는 임계 구역에 진입하기 전 허가를 받아야 하며, 이를 진입 구역entry section이라고 한다.

허가를 받아 임계 구역을 실행한 후 다른 프로세스들이 진입할 수 있도록 해야 하며, 이러한 처리를 하기 위한 구역을 출구 구역exit section이라고 한다.

진입 구역, 임계 구역, 출구 구역이 아닌 코드 부분을 잔류 구역remainder section이라고 한다.

remainder -> entry -> critical -> exit -> remainder

임계 구역 문제를 해결하는 메커니즘은 다음의 요건을 충족해야 한다.

  • 상호 배제mutual exclusive
    • 한 프로세스가 임계 구역에서 실행하고 있으면 다른 어떠한 프로세스도 임계 구역에 진입해서는 안된다.
  • 진행progress
    • 여러 개의 프로세스가 임계 구역에 진입하고자 하면 이들의 진입 순서는 이들에 의해 결정되어야 하며, 이 선택은 무한정 연기되어서는 안 된다.
  • 한계 대기bounded waiting
    • 한 프로세스가 임계 구역에 진입하고자 요청한 이후 해당 요청에 허용될 때까지, 다른 프로세스가 임계 구역에 진입할 수 있는 횟수가 제한되어야 한다.

소프트웨어 접근 방법

두 개의 프로세스를 위한 해결책

첫 번째

  • 공유 변수 int turn
  • 초기 값 turn = 1 or 0
  • turn이 i이면 Pi가 임계 지역에 진입할 수 있다.
do {
  // entry section
  while(turn != i);

  // critical section

  // exit section
  turn = j;

  // remainder section
} while(1);

이 경우 상호 배제는 만족하지만 진행 요구 조건은 충족하지 않는다. 다른 프로세스가 진입하고자 하더라도 해당 프로세스의 차례가 아니면 무조건 기다려야 하기 때문이다.

특히 한 프로세스가 예기치 임계 구역을 실행하던 도중 예기치 않게 종료되면 다른 프로세스는 임계 구역에 영원히 진입할 수 없게 된다.

두 번째

  • 공유 변수 boolean flag[2]
  • 초기 값 flag[0] = flag[1] = false
  • flag[i]가 true이면 Pi가 임계 구역에 진입할 준비가 되었음을 나타낸다.
do {
  // entry section
  flag[i] = true; // (1)
  while(flag[j]); // (2)

  // critical section

  // exit section
  flag[i] = false;

  // remainder section
} while(1);

이 경우 상호 배제는 만족하지만 진행 요구 조건은 충족하지 않는다. 다른 프로세스가 진입하고자 하더라도 해당 프로세스의 차례가 아니면 무조건 기다려야 하기 때문이다.

특히 flag 모두 true가 된 경우 두 프로세스는 영원히 기다리게 된다.

또한 프로세스가 자신의 flag 값을 true로 설정한 후 예기치 않게 종료되면 다른 프로세스는 영원히 진입할 수 없게 된다.

코드에서 (1)과 (2)의 순서를 바꾸면 상호 배제를 만족시키지 않게 된다.

세 번째

  • 공유 변수 boolean flag[2], int turn
  • 초기 값 flag[0] = flag[1] = false, turn = 0 or 1
do {
  // entry section
  flag[i] = true;
  while(flag[j]) {
    if(turn == j) {
      flag[i] = false;
      while(turn == j);
      flag[i] = true;
    }
  }

  // critical section

  // exit section
  turn = j;
  flag[i] = false;

  // remainder section
} whlie(1);

두 프로세스 모두 진입하고자 하는 경우(flag[0] = flag[1] = true) turn 값이 진입하는 프로세스를 결정하게 해주므로 세 가지 요구 조건을 모두 충족하게 된다.

네 번째

  • 공유 변수 boolean flag[2], int turn
  • 초기 값 flag[0] = flag[1] = false, turn = 0 or 1
do {
  // entry section
  flag[i] = true; // (1)
  turn = j;       // (2)
  while(flag[j] && turn == j);

  // critical section

  // exit section
  flag[i] = false;

  // remainder section
} while(1);

(1)에 따라 두 프로세스가 모두 진입하고자 하더라도 turn 변수값에 의해 하나의 프로세스만 while문을 통과할 수 있게 된다. 따라서 상호 배제를 만족하게 된다.

while문의 조건에 따라 한 프로세스에 오류가 있더라도 다른 프로세스는 임계 구역에 진입할 수 있다. 따라서 진행 및 한계 대기를 만족하게 된다.

다중 프로세스를 위한 해결책

  • 공유 변수 boolean choosing[n], int num[n]
  • 초기 값 choosing[n] = false, num[n] = 0
do {
  // entry section
  choosing[i] = true;
  num[i] = max(num[0] + ... + num[n - 1]) + 1;
  choosing[i] = false;
  for(j = 0; j < n; ++j) {
    while(choosing[j]);
    while((num[j] != 0) && ((num[j], j) < (num[i], i)));
  }

  // critical section

  // exit section
  num[i] = 0;

  // remainder section
} whlie(1);

동기화 하드웨어

단일 프로세서 시스템의 경우 공유된 변수를 변경하는 동안 인터럽트를 발생시킬 수 없도록 하여 위와 같은 문제를 쉽게 해결할 수 있다.

do {
  // disable interrupt

  // critical section

  // enable interrupt

  // remainder section
} while(1);

다중 프로세서 시스템에서는 인터럽트를 발생시키지 못하게 하더라도 여전히 두 프로세서에서 두 프로세스를 동시에 실행할 수 있으므로 임계 구역 문제를 해결할 수 없다.

대부분의 시스템은 특수한 하드웨어 명령어를 사용하여 이와 같은 문제를 해결한다.

TestAndSet 명령어

boolean TestAndSet(boolean &target) {
  boolean rv = target;
  target = true;
  return rv;
}
do {
  // entry section
  while(TestAndSet(lock));
  
  // critical section

  // exit section
  lock = false;

  // remainder section
} while(1);

Swap 명령어

void Swap(boolean &a, boolean &b) {
  boolean temp = a;
  a = b;
  b = temp;
}
do {
  // entry section
  key = true;
  while(key == true) Swap(lock, key);

  // critical section

  // exit section
  lock = false;

  // remainder section
} while(1);

TestAndSet과 Swap 알고리즘은 모두 상호 배제만을 충족할 뿐 한계 대기는 충족시키지 못한다.

do {
  // entry section
  waiting[i] = true;
  key = true;
  while(waiting[i] && key)
    key = TestAndSet(lock);
  waiting[i] = false;

  // critical section

  // exit section
  j = (i + 1) % n;
  while((j != i) && !waiting[j])
    j = (j + 1) % n;
  if(j == i) lock = false;
  else waiting[j] = false;

  // remainder section
} while(1);

위의 알고리즘을 사용하여 임계 구역 문제의 모든 요구 사항을 충족시킬 수 있다.

동기화 하드웨어나 소프트웨어 접근 방식으로 임계 구역 문제를 해결하려는 경우, 어느 한 프로세스가 임계 구역에 있으면 진입하고자 하는 다른 프로세스는 busy waiting을 해야 한다. 이는 아무 일도 하지 않지만 자원을 계속해서 사용하고 있음을 나타낸다.

세마포어

Semaphore. 정수 변수이며, 두 가지 연산 wait와 signal을 통해서만 접근할 수 있다. 이 두 연산은 원자적이다.

wait(S) {
  while (S <= 0);
  S--;
}
singal(S) {
  S++;
}

사용법

do {
  // entry section
  wait(mutex);
  
  // critical section

  // exit section
  signal(mutex);

  // remainder section
} while(1);

모든 프로세스는 mutex라는 세마포어를 공유하며, 1로 초기화된다.

한계 대기는 충족하지 못한다.

구현

busy waiting을 하는 세마포어를 spinlock이라고 한다. 이는 문맥 전환을 필요로 하지 않아 오랜 시간 동안 busy waiting을 하지 않는다면 효과적인 방법이다.

busy waiting을 제거하기 위해서는 wait 연산을 수행하였을 때 세마포어 값이 양수가 아니면 스스로를 블록하도록 해야 한다.

아래는 busy waiting이 없는 semaphore, wait, signal의 구조다.

typedef struct {
  int value;
  struct process *L;
} semaphore;
void wait(semaphore S) {
  S.value--;
  if(S.value < 0) {
    // S.L에 해당 프로세스 추가
    block();
  }
}
void signal(semaphore S) {
  S.value++;
  if(S.value <= 0) {
    // S.L에서 해당 프로세스 제거
    wakeup(S.L);
  }
}

busy waiting이 없는 경우 세마포어는 음수의 값을 가질 수 있으며, 이는 세마포어를 기다리는 프로세스의 수를 나타낸다.

이진 세마포어

이진 세마포어의 경우 가질 수 있는 값의 범위가 0 또는 1로 제한된다.

아래는 busy waiting이 없는 wait, signal의 구조다.

void wait(semaphore S) {
  if(S.value == 1)
    S.value = 0;
  else {
    // S.L에 해당 프로세스 추가
    block();
  }
}
void signal(semaphore S) {
  if(S.L is empty)
    S.value = 1;
  else {
    // 해당 프로세스를 S.L에서 제거
    // wakeup(S.L);
  }
}

고전 동기화 문제

한계 버퍼 생산자와 소비자 문제

생산자는 버퍼가 가득 차 있으면 대기해야 하고, 소비자는 버퍼가 비어 있으면 대기해야 한다.

버퍼에 대한 접근은 상호 배타적이어야 한다.

두 개의 계수 세마포어 empty 및 full과, 한 개의 이진 세마포어 mutex가 사용된다.

mutex 세마포어는 상호 배제를 위해, empty 및 full 세마포어는 프로세스 동기화를 위해 사용된다.

  • mutex 세마포어는 1로 초기화되며, 버퍼 접근에 대한 상호 배제를 제공한다.
  • empty 세마포어는 버퍼의 크기 n으로 초기화되며, 비어 있는 버퍼의 수를 나타낸다.
  • full 세마포어는 0으로 초기화되며, 채워져 있는 버퍼의 수를 나타낸다.
// 생산자
do {
  // nextp에 다음 item 생산

  wait(empty);
  wait(mutex);

  // nextp를 버퍼에 추가

  signal(mutex);
  signal(full);
} while(1);

// 소비자
do {
  wait(full);
  wait(mutex);

  // 버퍼에 있는 item을 nextc로 옮김

  signal(mutex):
  signal(empty);

  // nextc 소비
} while(1);

읽기 쓰기 문제

여러 프로세스가 데이터 객체를 공유하는데, 어떠한 프로세스는 이 객체의 내용을 읽고 싶고, 다른 어떠한 프로세스는 이 객체의 내용을 갱신하고 싶다.

하나의 쓰기 프로세스와 다른 프로세스가 병행으로 수행되는 경우 기대하지 않은 결과가 발생할 수 있다.

읽기 우선 읽기 쓰기 문제

읽기 프로세스는 쓰기 프로세스가 공유 객체에 접근하고 있지 않다면 대기하지 않는다.

쓰기 프로세스가 굶주릴 수 있다.

쓰기 우선 읽기 쓰기 문제

쓰기 프로세스가 준비되었다면 더이상 새로운 읽기 프로세스를 수행시킬 수 없다.

읽기 프로세스가 굶주릴 수 있다.

철학자들의 만찬 문제

다섯 명의 철학자 / 철학자는 생각하거나 식사함 / 다섯 개의 젓가락 / 두 개의 젓가락을 집어야 식사 가능

  1. 세마포어를 하나 사용
    • 상호 배제는 충족하나, 교착상태 발생 가능성
  2. 하나의 젓가락을 집은 다음, 다른 하나를 집을 수 없으면 집은 젓가락을 내려놓고 잠시 기다린 후 다시 시도
    • livelock 발생 가능성
    • 임의의 시간을 기다리는 것으로 해결
  3. 세마포어를 하나 더 사용하여 전체 과정을 임계 구역으로 설정
    • 한 번에 한 철학자만 식사 가능
  4. 세마포어를 하나 더 사용하여 젓가락을 집는 부분만 임계 구역으로 설정
    • 교착 상태 발생 가능성

임계 영역

세마포어를 사용하면 상호 배제를 쉽게 충족시킬 수 있으나, 프로그램을 잘못 작성하거나 악용될 위험이 있다.

이러한 문제를 해결하기 위해 세마포어의 상위 개념의 동기화 해결 도구를 사용한다.

임계 영역critical section과 모니터monitor가 있다.

  • 공유 변수 v: shared T
  • region v when (B) S; : B 조건이 참일 때 S 문장을 수행할 수 있음, 이미 한 프로세스가 S를 수행하고 있으면 다른 프로세스는 기다림

병행 수행되더라도 원자적으로 수행된다.

모니터

모니터 내에 선언된 변수는 모니터 내에 정의된 함수를 통해서만 접근 가능하며, 모니터 내에 정의된 함수는 모니터 내에 정의된 변수만 사용할 수 있다.

한번에 한 프로세스만이 모니터 내부 함수를 실행할 수 있다.

모니터 내에 정의된 함수를 사용할 수 없을 때 대기할 수 있도록 하기 위해 추가로 조건condition 타입의 변수를 제공한다.

조건 변수는 다음의 두 연산에 의해서만 조작될 수 있다.

  • wait : 이 연산을 수행하는 프로세스는 대기한다.
  • signal : 이 연산을 수행하면 대기 중인 하나의 프로세스가 재개한다.