프로세스 동기화 | Operating System

배경

공유 메모리 시스템 에서 언급했던 것처럼 버퍼에 여러 프로세스가 동시에 값을 넣는다면 어떻게 되는지 알아본다. 간단하게 변수에 1을 더하고 값을 가져와보자. 단 2개의 프로세스가 동시에 작업을 수행한다.

같은 명령을 수행했는데 동시에 실행했다는 이유만으로 결과가 달라진다. 이런 상황을 경쟁 상황(race condition)이라 한다. 이런 문제는 다중스레드 시스템에서 빈번히 발생하기 때문에 협력하는 프로세스들 간의 프로세스 동기화와 조정은 중요하다.

치명적인 구역 문제

치명적인 구역(critical section) 혹은 임계 구역은 반드시 한 번에 하나의 프로세스만 접근해야 하는 구역을 말한다. 치명적인 구역 문제는 한 번에 하나의 프로세스만 접근할 수 있도록 접근을 관리하고 요청을 처리하는 문제이다. 코드에서 진입을 요청하는 부분을 집입 구역(entry), 나오는 부분을 퇴장 구역(exit), 그 외의 코드를 나머지 구역이라 한다. 치명적인 구역 문제를 해결하기 위해서는 최소한 아래 조건을 충족해야 한다.

상호 배제(mutual exclustion) : 무조건 한 번에 하나의 프로세스만 치명적인 구역에 접근해야 한다.
진행(progress) : 치명적인 구역에 있는 프로세스는 없지만 진입 구역에는 여러 개의 프로세스가 있다면, 진입 구역의 프로세스들 중에서만 다음 번에 치명적인 구역에 접근할 수 있다. 접근 프로세스를 선택하는 과정은 무기한 연기될 수 없다.
한정된 대기(bounded waiting) : 프로세스가 치명적인 구역 접근을 요청한 후 다른 프로세스가 치명적인 구역에 접근하는 횟수에는 제한이 있어야 한다. 무기한 기다리면 안된다는 뜻이다.

선점형 커널과 비선점형 커널

선점형(preemption)은 하나의 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 빼앗는 기법을 말한다. 비선점형 커널은 프로세스가 커널을 빠져나가거나 blocking되거나 제어를 양도할 때까지 기다리는 방식이다. 비선점형 커널은 한 순간에 커널에서 실행중인 프로세스가 하나임을 보장하기 때문에 경쟁 상황이 발생하지 않는다. 하지만 그렇기 때문에 응답이 민첩하지 못하다. 선점형 커널은 경쟁 상황을 처리하는 것이 특히 어렵지만 응답이 민첩하고 실시간 프로그래밍에 더 적합하다. 대부분 선점형 커널을 더 선호한다.

피터슨 해결안

치명적인 구역을 해결하는 가장 고전적인 방법이다. 현대 컴퓨터 구조가 save, load를 구현하는 방식 때문에 지금은 조금 안맞지만 치명적인 구역의 세 가지 요구 조건을 만족하는 데는 충분하다.

do {
  flag[i] = true; // 곧 들어갑니다.
  turn = j;       // 당신부터 하십시오.
  while (flag[j] && turn==j); // 내 차례가 아닐 경우 대기
  // 치명적인 구역 코드는 여기에
  flag[i] = false; // 이제 나갑니다.
} while (true);

flag는 치명적인 구역으로 진입할 준비가 되었다는 것을, turn은 실제 내가 사용한다는 것을 뜻한다. 또 지금은 i 프로세스와 j 프로세스만 있다고 가정한다.

먼저 flag로 내가 곧 치명적인 영역으로 들어간다는 것을 알리고, turn을 상대 프로세스에게 넘긴다. 조금 의아할 수 있는데 이렇게 상대에게 turn을 넘기면 어떤 프로세스도 무기한 기다리지 않아도 된다. 또한 turn은 동시에 두 값이 될 수는 없기 때문에 둘 중 하나만 대기하던 while문을 빠져나갈 수 있다.

동기화 하드웨어

현대 컴퓨터 구조에서는 하드웨어부터 소프트웨어까지 모두 합심해 치명적인 구역을 보호하는 방법을 제공한다. 모든 방식은 치명적인 구역에 자물쇠를 걸어 잠그는 방식(locking)이다.

치명적인 구역 문제는 공유 변수가 변경되는 동안 인터럽트를 발생시키지 않으면 해결할 수 있다. 인터럽트가 곧 선점이기 때문이다. 하지만 이렇게 하면 멀티 프로세서 환경에서 메시지를 교환하는데 시간이 오래 걸리게 되고 성능이 떨어지게 된다. 그래서 현대 하드웨어들은 인터럽트가 되지 않고 원자적으로(atomically) 수행되는 명령을 제공한다. 원자적이라는 말은 명령어 묶음을 한 번에 실행하는 것을 말한다. 이 명령들을 실행하는 동안에는 다른 명령은 실행될 수 없다.

test_and_set

boolean test_and_set(boolean *target) {
  boolean rv = *target;
  *target = true;
  return rv;
}

do {
  while (test_and_set(&lock)); // 대기
  // 치명적인 구역 코드는 여기에
  lock = false;
} while (true)

compare_and_swap

int compare_and_swap(int *value, int expected, int new_value) {
  int temp = *value;
  if (*value == expected)
    *value = new_value
  return temp;
}

do {
  while (compare_and_swap(&lock, 0, 1) != 0);
  // 치명적인 구역 코드는 여기에
  lock = false;
} while (true)

두 명령어(함수)은 하드웨어 차원에서 지원하는 명령어이다. 하드웨어는 이 두 명령어를 원자적으로 실행하는 것을 보장한다. 따라서 여러 프로세서가 해당 함수를 동시에 호출한다 하더라도 순서대로 실행될 것이다.

하지만 두 방식은 상호 배제 조건은 만족하지만 한정된 대기 조건을 만족하지 못한다. 다른 프로세스가 무한정 기다릴 수 있는 위험이 있다.

Mutex Locks

하드웨어적인 지원은 구현이 복잡하고 어플리케이션 개발자가 사용할 수 없다. 그래서 운영체제에서 API를 제공하는데 그 첫 번째가 mutex 락(lock)이다. mutex는 상호 배제의 약자로 치명적인 구역에 진입할 때는 락을 획득하고(acquire), 끝나면 락을 풀어준다(release).

프로세스는 락을 얻기까지 계속 while 문을 돌면서 기다린다. 이 방식을 바쁜 대기(busy waiting)라 하고 이 방식을 쓰는 락을 스핀락이라 한다. 이 방식은 불필요하게 CPU를 낭비하지만 문맥 교환을 할 필요 없기 때문에, 짧은 시간 쓸 때 추천한다.

acuqire() {
  while (!available) ; // busy wait
  available = false;
}
release() {
  available = true;
}

세마포어

세마포어(semaphore)는 mutex를 발전시킨 형태로 wait와 signal 함수로 접근할 수 있다. 세마포어의 값을 변경할 때에는 어떤 스레드도 동시에 작업해서는 안된다. 약자로 wait은 P, signal은 V로 불린다. 네덜란드어다.

코드 (간단한 버전)

wait(S) {
  while (S <= 0) ; // busy wait
  S--;
}
release(S) {
  S++;
}

사용법

세마포어는 정수로 락을 제어하기 때문에 한 번에 하나의 프로세스만 접근을 가능하도록 하는 이진 세마포어도 만들 수 있고, 아니면 최대 몇 개까지 동시에 접근 가능하도록 제어하는 카운팅 세마포어도 만들 수 있다. 세마포어는 처음 선언할 때 변수 S에 값을 할당하고, wait 함수가 호출되면 1을 감소한다. 그러다 S가 0이 되면 치명적인 구역이 꽉 찼다는 뜻이 되어 더 이상 접근하지 못 하고 대기한다. 누군가 signal 함수를 호출해 S를 증가시키면 이제 기다리던 프로세스나 스레드가 접근할 수 있다.

구현

세마포어는 mutex처럼 바쁜 대기를 하지 않고, 기다려야 되는 프로세스를 block한다. 그러면 해당 프로세스는 세마포어의 대기 큐에 들어간다. 누군가 치명적인 영역에서 나와 signal 함수를 호출하면 프로세스는 wake 연산을 실행하고 준비 큐에 들어간다. 이 과정을 반복한다.

typedef struct {
  int value;
  struct process *list; // 대기 큐
}

void wait(semaphore *S) {
  S->value--;
  if (S->value < 0) {
    push(S->list, current_process);
    sleep(); // 프로세스를 block한다.
  }
}

void signal(semaphore *S) {
  S->value++;
  if (S->value <= 0) {
    pop(S->list);
    wakeup();
  }
}

복잡한 버전으로 세마포어를 구현하면 세마포어는 음수를 가질 수 있다. 음수값이 뜻하는 것은 대기하고 있는 프로세스의 수가 된다. 대기 중인 프로세스 목록은 PCB의 주소값(포인터)을 저장하여 찾을 수 있다. 또 선입선출(FIFO) 방식을 써서 한정된 대기를 보장한다.

교착상태와 기아

위 그림처럼 $P_0$은 $P_1$을 기다리고, $P_1$는 $P_0$을 기다리고 있다. 이렇게 풀리지 않는 상태를 교착상태(deadlock)이라 한다. 교착 상태는 뒤에서 더 자세히 이야기한다.

무한 봉쇄 또는 기아(starvation)는 어떤 프로세스가 무한정 block되어 있는 상태를 말한다. 세마포어 대기 큐에서 후입선출(LIFO) 방식을 사용할 경우 발생할 수 있다.

우선순위 역전 문제

낮은 순위의 프로세스가 락을 얻었다고 가정해보자. 프로세스가 연산을 끝내야 다른 프로세스들도 해당 락을 얻어 연산을 할 수 있다. 하지만 CPU는 높은 순위의 프로세스가 더 활발히 사용한다. 또한 선점형 방식을 쓰는 시스템에서는 CPU 자원이 끊임없이 선점될 수 있기 때문에 낮은 순위의 프로세스가 락을 반환할 때까지 시간이 오래 걸리게 된다.

이 문제는 셋 이상의 우선 순위를 가진 시스템에서만 발생한다. 우선순위를 두 개만 만드는 방법도 있지만 비효율적이기 때문에 시스템은 우선순위 상속 프로토콜을 구현해 문제를 해결한다. 이 프로토콜은 더 높은 우선순위 프로세스가 필요로 하는 자원을 가지고 있는 프로세스에 일시적으로 높은 우선순위를 할당하는 것이다. 자원 사용이 끝나면 다시 원래의 우선순위로 돌아간다.

고전적인 동기화 문제들

유한 버퍼 문제

배경의 예시와 비슷하게, 버퍼를 생산하고 소비하는 작업을 동시에 하면 문제가 발생한다. 이 것을 해결하는 방법은 다음과 같다.

mutex 세마포어는 1로 초기화해 상호 배제를 구현한다. empty와 full 세마포어는 각각 비어 있는 버퍼 수와 꽉 찬 버퍼 수를 뜻한다. empty 세마포어는 n으로 초기화되고, full 세마포어는 0으로 초기화된다. 코드를 보면 생산자는 꽉 찬 버퍼를 생산하고, 소비자는 비어 있는 버퍼를 생산한다고 해석할 수 있다.

// 생산자 프로세스
do {
  wait(empty);

  wait(mutex);
  // 버퍼에 값 추가하기
  signal(mutex);

  signal(full);
} while (true);

// 소비자 프로세스
do {
  wait(full);

  wait(mutex);
  // 버퍼의 값 사용하기
  signal(mutex);

  signal(empty);
} while (true);

Readers-Writes 문제

하나의 파일에 여러 프로세스들은 읽거나 쓸 수 있다. 읽기는 여러 명이 동시에 해도 상관없다. 하지만 쓰기는 무조건 한 프로세스만이 해야 하며 쓸 동안에 다른 프로세스들은 읽을 수 없다. 이 문제는 두 가지 변형이 있다.

writer는 진입 구역에 들어가서 reader들의 작업이 끝날 때까지 기다린다.
writer가 기다리는 동안에 새로운 reader들은 읽기를 시작할 수 있다.
reader는 최대한 기다리지 않고 작업해야 한다.
writer는 진입 구역에 들어가서 reader들의 작업이 끝날 때까지 기다린다.
writer가 기다리는 동안에 새로운 reader들은 읽기를 시작할 수 없다.
writer는 최대한 빨리 실행되어야 한다.

주의해야 할 것이 이 문제들의 해결책이 기아를 유발할 수도 있다. 첫 번째 경우는 writer가, 두 번째 경우는 reader가 기아 상태에 빠질 수 있다. 기아를 해결한 방법은 이 링크를 참조하면 된다. 어떤 시스템에는 이 문제를 통합해 read-writer 락을 제공하는 경우도 있다.

첫 번째 방법 해결

mutex 세마포어는 코드의 원자성을 보장하기 위해서 사용한다. read_count는 현재 읽기 중인 프로세스의 수를 말한다. rw_mutex는 두 가지 의미가 있는데,

읽는 프로세스가 있으니 프로세스는 읽을 수는 있지만 쓸 수는 없다.
쓰는 프로세스가 있으니 누구도 쓰거나 읽을 수 없다.

// writer
do {
  wait(rw_mutex);
  signal(rw_mutex);
} while(true)

// reader
do {
  wait(mutex);
  read_count++;
  if (read_count == 1)
    wait(rw_mutex);
  signal(mutex);

  // reading

  wait(mutex);
  read_count--;
  if (read_count == 0)
    signal(rw_mutex);
  signal(mutex);
}

식사하는 철학자들 문제

그림과 같이 서로 소통하지 않는 답답한 철학자들이 앉아 있다. 철학자가 음식을 먹기 위해서는 두 개의 포크가 필요하다. 음식을 먹고는 제자리에 포크를 놔둔다. 그런데 5명이 동시에 자기 왼쪽에 있는 포크를 집었다. 그리고 다들 자기 오른쪽 포크가 생길 때까지 무한정 기다린다. 이러면 모두가 음식을 먹지 못 하는 교착 상태(deadlock)이 발생한다. 아래에 해결 방법 몇 가지를 소개한다.

자리와 포크는 5개로 두되, 철학자들은 4명만 앉힌다.
홀수 번째 철학자는 왼쪽 포크부터 집고, 나머지 철학자는 오른쪽 포크부터 집는다.
포크 두 개를 모두 잡을 수 있을 때만 포크를 집어야 한다. (치명적인 영역 안에 들어와서 포크를 잡는다.)

위의 방법을 사용하면 모두가 음식을 먹지 못 하는 상황(교착상태)은 발생하지 않는다. 단 어느 한 명이 계속 포크를 기다리다 굶을 수 있기 때문에 주의해야 한다(기아).

모니터

세마포어는 앞서 배경에서 설명했던 오류를 해결해준다. 하지만 wait과 signal을 잘 못된 위치에 사용하거나 깜박하고 signal을 호출하지 않는 등 부주의로 인한 오류는 쉽게 발생할 수 있다. 이런 오류를 근본적으로 처리하기 위해 고급 언어 구조물 중 하나인 모니터를 쓴다.

// 하나의 자원을 할당하는 모니터 예시
monitor monitor name {
    /* 공유 변수 정의*/
    boolean busy;
    condition x; // 동기화 기법

    function acquire(int time) {
        if (busy) x.wait(time);
        busy = true;
    }

    function release() {
        busy = false;
        x.signal()
    }

    function initialization_code() {
      busy = false
    }
}

모니터 사용법

추상화된 데이터 타입(ADT)는 데이터와 함수들을 하나의 단위로 묶는다. 모니터 구조물은 모티너 안에 항상 하나의 프로세스만이 활성화되도록 보장해 준다. condition 구조물은 wait과 signal로 구성되어 있고, 모니터에 동기화 기법을 제공한다.

condition의 signal 연산은 만약 wait 중인 프로세스가 없으면 아무런 동작도 하지 않는다. 세마포어는 wait을 무한정 기다린다는 것에서 대조적이다. condition의 signal이 호출되었을 때 wait 중인 프로세스가 있다면, 프로세스는 두 가지 선택을 할 수 있다.

Signal and wait : signal을 보낸 프로세스는 wait 중인 프로세스가 모니터를 떠날 때까지 기다린다.
Signal and continue : wait 중인 프로세스는 signal 중인 프로세스가 모너터를 떠날 때까지 기다린다.

모니터 내에서 프로세스 수행 재개

Signal 연산으로 어떤 프로세스를 재개할 것인가? 첫 번째 방법은 FCFS 순이다. 먼저 wait 한 쪽을 재개한다. 다른 방법은 wait을 호출할 때 우선 순위를 할당하는 건데, x.wait(c) 꼴로 우선순위 정수(c)를 보낸다. 다음 번에는 가장 작은 우선순위 정수를 가진 프로세스를 재개한다.

대체 방안들

트랜잭션 메모리

여기서 트랜잭션이란 메모리를 읽고 쓰는 것을 말한다. 트랜잭션은 원자적으로 수행하며, 한 트랜잭션이 모두 끝나면 해당 트랜잭션은 확정(commit)된다. 만약 중간에 실패하면 해당 트랜잭션이 실행되기 전 상황으로 되돌아 간다(rollback). 이 방식은 프로그래밍 언어 차원에서 지원해야 한다. 예를 들어 아래와 같이 표현할 수 있다.

void update() {
    atomic {
      // 공유 데이터 변경
    }
}

이 방식의 이점은 개발자는 원자성에 대해 책임질 필요가 없다는 점이다. 또한 락이 없기 때문에 교착 상태가 발생하지 않는다. 읽기 같은 경우에는 여러 프로세스가 동시에 읽을 수도 있다.

트랜잭션 메모리는 하드웨어 또는 소프트웨어로 구현할 수 있다. 소프트웨어 트랜잭션 메모리(STM)는 소프트웨어 구현이다. 컴파일러는 STM을 트랜잭션 블록에 삽입하고, STM은 동시에 실행해야 하는 부분과 저수준 락킹이 필요한 지점을 검사한다. 하드웨어 트랜잭션 메모리(HTM)은 프로세서 캐시에 남아 있는 공유 데이터의 충돌을 관리하기 위해, 하드웨어 캐시 계층 구조와 캐시 일관성 프로토콜을 사용한다. HTM은 STM보다 오버헤드가 적으나 하드웨어적인 변경이 필요하다.

OpenMP

OpenMP 파트에서 설명한 OpenMP는 #pragma omp parallel로 병렬 처리를 지원하고, #pragma omp cirtical로 치명적인 구역에서 하나의 스레드만 실행할 수 있게 한다. 사용하기는 매우 쉽지만, OpenMP는 mutex처럼 동작하기 때문에 교착상태가 발생할 수 있다.

함수형 프로그래밍 언어

우리가 흔히 아는 언어는 절차형 프로그래밍 언어이다. 함수형 프로그래밍 언어는 명령으로 이루어져 있지 않고, 값을 변경하지 않는다. 값을 변경하지 않기 때문에 경쟁 조건이나 교착상태가 발생하지 않는다. Erlang과 Scala는 대표적인 함수형 언어이다. Erlang은 병행성과 병렬 시스템에서 실행되는 어플리케이션을 개발하기 쉬운 언어이다. 한편, Scala는 함수형 언어이면서 객체지향 언어이기 때문에 Java나 C#과 유사한 특징이 있다.

Deadlocks

교착상태와 기아에서 간단하고 소개한 바와 같이 block 된 프로세스들이 다시는 그 상태를 빠져나갈 수 없는 상황을 말한다.

시스템 모델

모든 자원은 획득하고 사용하고 방출한다. 자원은 물리적인 자원(CPU, 메모리 프린터 등)일 수 있고, 논리적 자원(mutex, 파일)일 수 있고, 다른 어떤 사건(IPC 등)일 수도 있다. 프로세스가 다른 프로세스에 의해서만 발생할 수 있는 사건을 기다린다면, 그 프로세스 집합은 교착상태에 있다. 예를 들어 DVD는 프린터에, CD는 컴퓨터에 꽂혀 있다. DVD는 컴퓨터에서 CD가 제거되기를 기다리고, CD는 프린터에서 DVD가 제거되기를 기다린다. 서로가 서로를 기다리기 때문에 어느 누구도 움직이질 않는다.

교착상태의 특징

4가지 조건은 모두 만족해야 교착상태가 발생할 수 있다.

상호 배제(Mutual exclusion) : 한 번에 하나의 프로세스만 그 자원을 이용할 수 있다. 다른 프로세스는 기다려야 한다.
점유 대기(Hold-and-wait) : 프로세스는 자원을 점유한 채 다른 자원을 요청할 수 있다.
비선점(No preemption) : 프로세스가 점유하고 있는 자원을 강제로 방출(release)할 수 없다.
순환 대기(Circular wait): 아래 그림처럼 서로가 서로를 기다린다.

자원 할당 그래프

P는 프로세스 집합, R은 자원의 집합을 나타낸다.

처리 방법

예방하거나 회피하는 프로토콜을 사용한다.
예방은 교착상태의 조건들 중 하나를 성립하지 않도록 하는 방법이고, 회피는 운영체제가 프로세스들의 요청을 지연시키면서 조정하는 방법이다.
교착상태를 허용한 다음에 회복시킨다.
교착 상태는 매우 드물게 발생하기 때문에 발생하면 수작업으로 복구할 수 있다.
교착상태가 발생하지 않은 척한다.
대부분의 운영체제는 세 번째 방법을 사용한다. 교착상태를 처리하는 것은 개발자의 몫이다.

Sunghun Son / Operating System / 프로세스 동기화

배경