[Operating System Concepts 10th] 6. Synchronization Tools 리뷰

2022-08-24 9 분 소요

본 글은 Operating System Concepts 10th (운영체제) 책을 보며 내용을 개인 공부에 목적으로 정리했습니다.
이전에 운영체제 관련 강의들을 들으면서 정리한 시리즈 글들이 있는데,
지식을 습득하는 데 있어 가장 느리지만 가장 빠른 방법이 원본책을 자세히 보는 것이라 생각됩니다.
책 내용들을 최대한 이해하기 위해 거의 모든 내용을 담고 있습니다.

책 pdf 링크 : Operating System Concepts 10th Edition by Abraham Silberschatz Peter B Galvin Greg Gagne pdf free download
연습 문제 정답지 : Solutions of Practice Exercises, Tenth Edition of Operating System Concepts, AVI SILBERSCHATZ

6. Synchronization Tools

협력적 프로세스(cooperating process)는 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나 영향을 받는 프로세스이다.
협력적 프로세스는 논리 주소 공간(즉, code 및 data)을 직접 공유하거나 공유 메모리(shared memory) 또는 메시지 전달(message passing)을 통해서만 데이터를 공유할 수 있다.
그러나 공유 데이터를 동시에 접근하면 데이터의 일관성(consistency)를 망칠 수 있기 때문에, 이런 일관성을 유지하는 다양한 메커니즘을 논의한다.

목표
- 임계구역(critical-section)을 설명하고 경쟁 조건(race condition)을 설명한다.
- 메모리 장벽, compare-and-swap 연산 및 원자적(atomic) 변수를 사용하여 임계구역(critical-section) 문제를 해결하는 방법을 보인다.
- low-, moderate- 및 high- 경쟁(contention) 시나리오에서 임계구역 문제를 해결하는 도구를 평가한다.

6.1 Background

프로세스는 명령어가 실행될 때 어느 지점에서나 인터럽트 되고, 처리 코어는 다른 프로세스의 명령어를 실행하도록 할당될 수 있다.
동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라 한다.
- 경쟁 상황으로부터 보호하기 위해, 한순간에 하나의 프로세스만이 변수 count를 조작하도록 보장해야 한다.
- 이러한 보장을 위해, 우리는 어떤 형태로든 프로세스들이 동기화되도록 할 필요가 있다.

멀티 스레드 응용에서는 자원을 공유할 가능성이 매우 높은 여러 스레드가 서로 다른 처리 코어에서 병렬로 실행된다.
이러한 행동에서 발생한 수정이 서로 간에 영향을 주지 않기를 원하기 때문에 6단원의 많은 부분은 협력하는 프로세스 간의 프로세스 동기화(process synchronization)와 조정(coordination)에 할애된다.

6.2 The Critical-Section Problem

임계 구역(critical-section) : 병렬컴퓨팅에서 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부를 말한다. ¹
임계구역 문제는 프로세스들이 데이터를 협력적으로 공유하기 위하여 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜을 설계하는 것이다.

/* Figure 6.1 */
while (true) {
  /* entry section */
    critical section
  
  /* exit section */
    remainder section
}

각 프로세스는 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 한다.
이러한 요청을 구현하는 코드 부분을 진입 구역(entry section)이라 한다.
임계구역 뒤에는 퇴출 구역(exit section)이 올 수 있다.
코드의 나머지 부분들을 나머지 구역(remaineder section)이라 한다.

임계구역 문제에 대한 해결로 다음 3가지 요구 조건을 충족해야 한다.

상호 배제(mutual exclusion) : 프로세스 $P_i$가 자기의 임계구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 없다.
진행(progress) : 자기의 임계구역에서 실행되는 프로세스가 없고 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는 데 참여할 수 있으며, 이 선택은 무한정 연기될 수 없다.
한정된 대기(bounded waiting) : 프로세스가 자신의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.

임의의 한순간에 많은 커널 모드 프로세스들이 운영체제 안에서 활성화될 수 있기 때문에 커널 코드는 경쟁 조건이 발생하기 쉽다.

만일 두 프로세스가 동시에 파일을 열려고 한다면, 리스트에 대한 개별적인 갱신은 경쟁 조건을 일으킬 수 있다.
Figure 6.2에서, $P_0$ 및 $P_1$의 두 프로세스는 fork() 시스템 콜을 사용하여 자식 프로세스를 생성한다.
- fork()는 새로 생성된 프로세스의 프로세스 식별자를 부모 프로세스로 반환한다.
이 예에서, 커널 변수 next_available_pid에 경쟁 조건이 있으며, 이 변수는 다음 사용 가능한 프로세스 식별자의 값을 나타낸다.
상호 배제가 제공되지 않으면 동일한 프로세스 식별자 번호가 2개의 다른 프로세스에 배정될 수 있다.

운영체제 내에서 임계구역을 다루기 위해서 선점형 커널과 비선점형 커널의 2가지 일반적인 접근법이 사용된다.
- 선점형(preemptive) 커널은 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다.
- 비선점형(nonpreemptive) 커널은 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져나갈 때까지 또는 블록될 때까지 또는 자발적으로 CPU 제어를 양보할 때까지 계속 수행된다.
커널 모드 프로세스가 대기 중인 프로세스에 프로세서를 양도하기 전에 오랫동안 실행할 위험이 적기 때문에 선점형 커널은 더 응답이 민첩할 수 있고 따라서 사람들은 비선점형 커널보다 선점형 커널을 더 선호한다.

6.3 Peterson’s Solution

Peterson의 solution은 임계구역 문제를 해결하기 위한 좋은 알고리즘적인 설명을 제공하고 상호 배체, 진행, 한정된 대기의 요구 조건에 대한 해결책을 잘 제시하는 예이다.
Peterson’s solution은 임계구역과 나머지 구역을 번갈아 가며 실행하는 2개의 프로세스로 한정된다. ($P_i, P_j$)
Peterson’s solution은 두 프로세스가 2개의 데이터 항목을 공유하도록 하여 해결한다.

/* Figure 6.3 : The structure of process Pi in Peterson's solution */

while (true) {
  flag[i] = true;
  turn = j;
  while (flag[j] && turn == j)
    ;

    /* critical section */
  
  flag[i] = false;

    /* remainder section */
}

임계구역으로 진입하기 위해서 $P_i$는 먼저 flag[i]를 참으로 만들고, turn을 j로 지정한다.
- 변수 turn은 임계구역으로 진입할 순번을 나타낸다.
- turn의 궁극적인 값이 둘 중 누가 먼저 임계구역으로 진입할 것인가를 결정한다.
이렇게 함으로써 프로세스 j가 임계구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.

6.4 Hardware Support for Synchronization

상호 배제를 유지하는 유일한 방법은 적절한 동기화 도구를 사용하는 것이다.
이 절에서는 임계구역 문제를 해결하기 위한 지원을 제공하는 3가지 하드웨어 명령어를 제시한다.
이러한 primitive 연산은 동기화 도구로 직접 사용될 수 있거나 더 추상적인 동기화 기법의 기초 형태로 사용될 수 있다.

6.4.1 Memory Barriers

컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정하는 방식을 메모리 모델(memory model)이라 한다.
일반적으로 메모리 모델은 2가지 범주 중 하나에 속한다.
1. 강한 순서(Strongly ordered) : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보인다.
2. 약한 순서(Weakly ordered) : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않는다.

메모리 모델은 프로세서 유형에 따라 다르므로 커널 개발자는 공유 메모리 멀티 프로세서에서 메모리 변경의 가시성(visibility)에 대한 어떠한 가정도 할 수 없다.
이 문제를 해결하기 위해 컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장하는데, 이러한 명령어를 메모리 장벽(memory barriers) 또는 메모리 펜스(memory fences)라 한다.
메모리 장벽 명령어가 실행될 때, 시스템은 후속 적재 또는 저장 연산이 수행되기 전에 모든 적재 및 저장이 완료되도록 한다.
따라서 명령이 재정렬되더라도 메모리 장벽은 향후 적재 또는 저장 작업이 수행되기 전에 저장 작업이 메모리에서 완료되어 다른 프로세서에 보이도록 한다.
메모리 장벽은 매우 낮은 수준의 연산으로 간주하며 일반적으로 상호 배제를 보장하는 특수 코드를 작성할 때 커널 개발자만 사용한다.

6.4.2 Hardware Instructions

많은 현대 머신들은 한 워드의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로(atomically) 교환(swap)할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공한다.
- 우리는 이들 특별한 명령어들을 사용하여 임계구역 문제를 상대적으로 간단한 방식으로 해결할 수 있다.

test_and_set() 명령어를 Figure 6.5처럼 정의할 수 있다.
- 이 명령어는 원자적으로 실행된다.
- 그러므로 만일 2개의 test_and_set() 명령어가 동시에 실행된다면, 이들은 어떤 임의의 순서로 순차적으로 실행될 것이다.

/* Figure 6.5 : The definition of the atomic test_and_set() instruction */
boolean test_and_set(boolean *target) {
  boolean rv = *target;
  *target = true;

  return rv;
}

만일 머신이 test_and_set() 명령을 지원한다면, false로 초기화되는 lock이라는 boolean 변수를 선언하여 상호 배제를 구현할 수 있다. (Figure 6.6)

/* Figure 6.6 : Mutual-exclusion implementation with test_and_set() */
do {
  while (test_and_set(&lock))
    ; /* do nothing */

    /* critical section */
  
  lock = false;

    /* remainder section */
} while (true);

compare_and_swap() (CAS)는 3개의 피연산자를 대상으로 연산을 하며, 아래 Figure 6.7에 정의되어 있다.
- 이 명령의 중요한 특징은 명령이 원자적으로 실행된다는 것이다. 따라서 2개의 CAS 명령이 동시에 실행되면 임의의 순서로 순차적으로 실행된다.
피연산자 value는 오직 (*value == expected) 수식이 참일 때에만 new_value로 지정된다.
어떠한 경우에든 CAS 명령어는 언제나 value의 원래 값을 반환한다.

/* Figure 6.7 : The definition of the atomic compare_and_swap() instruction */
int compare_and_swap(int *value, int expected, int new_value) {
  int temp = *value;

  if (*value == expected)
    *value = new_value;

  return temp;
}

CAS를 사용하는 상호 배제는 다음과 같이 지켜질 수 있다.
전역 변수 (lock) 이 선언되고 0으로 초기화된다.
compare_and_swap()을 호출한 첫 번째 프로세스는 lock을 1로 지정할 것이다.
lock이 원래 값이 expected 값과 같으므로 프로세스는 임계구역으로 들어간다.
이후의 compare_and_swap() 호출은 현재 lcok의 값이 기댓값 0과 같지 않기 때문에 성공하지 못한다.
프로세스가 임계구역을 빠져나올 때 lock을 0으로 변경하고, 다른 프로세스가 임계구역을 들어갈 수 있게 허용한다.

while (true) {
  while (compare_and_swap(&lock 0, 1) != 0)
    ; /* do nothing */
    
    /* critical section */

  lock = 0;

    /* remainder section */
}

하지만, 위 알고리즘은 상호 배제 조건은 만족시키지만 한정된 대기 조건을 만족시키지 못한다.
Figure 6.9는 임계구역 요구 조건을 모두 만족시키는 compare_and_swap() 명령어 알고리즘이다.
공통 데이터는 다음과 같다.

boolean waiting[n];
int lock;

waiting 배열의 원소는 false로 초기화되고 lock은 0으로 초기화된다.
- 이 알고리즘이 상호 배제 조건을 만족시킨다는 것을 증명하기 위해서는 $P_i$가 임계구역에 진입하는 경우가 오직 waiting[i] = false 이든지 key ==0 이여야 한다.
처음으로 compare_and_swap()을 실행시키는 프로세스는 key == 0을 발견할 것이다.
- 다른 프로세스들은 모두 기다려야 한다.
- 변수 waiting[i]가 false가 되는 것은 다른 프로세스가 임계구역을 떠날 때뿐이다.
- 이때 오직 한 개의 waiting[i]만이 false로 지정되고 따라서 상호 배제가 보장된다.

Progress 조건이 만족함을 보이기 위해서는 임계구역을 떠나는 프로세스는 lock을 0으로 하든지 waiting[j]를 false로 한다.
- 어느 쪽이든 둘 다 임계구역으로 들어가고자 하는 프로세스를 진입하게 만들어준다.
Bounded waiting 조건이 만족함을 보이기 위해서는 한 프로세스가 임계구역을 떠날 때에는 waiting 배열을 순환하면서 (i+1, i+2, …, n-1, 0, …, i-1) 훑어본다는 사실에 착안하면 된다.
- 순환하면서 조사하여 (waiting[j]== true)이면서 위 순환 순서 중 첫 번째 프로세스가 임계구역에 들어가게 된다.
- 따라서 임계구역에 들어가고자 하는 프로세스는 최대한 n-1회만 양보하면 들어갈 수 있다.

/* Figure 6.9 : Bounded-waiting mutual exclusion with compare_and_swap() */
while (true) {
  waiting[i] = true;
  key = 1;
  while (waiting[i] && key == 1)
    key = compare_and_swap(&lock, 0, 1);
  waiting[i] = false;

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

    /* remainder section */
}

6.4.3 Atomic Variables

원자적 변수(atomic variable)은 정수 및 부울과 같은 기본 데이터 유형에 대한 원자적 연산을 제공한다.
원자적 변수는 카운터가 증가할 때와 같이 갱신되는 동안 단일 변수에 대한 데이터 경쟁이 있을 수 있는 상황에서 상호 배제를 보장하는 데 사용될 수 있다.

6.5 Mutex Locks

운영체제 설계자들은 임계구역 문제를 해결하기 위한 상위 수준 소프트웨어 도구들을 개발하는데, 가장 간단한 도구가 mutex lock이다.
- mutex = mutual exclusion
- 임계구역을 보호하고, 경쟁 조건을 방지하기 위해 mutex 락을 사용한다.
프로세스는 임계구역에 들어가기 전에 반드시 락을 획득해야 하고 임계구역을 빠져나올 때 락을 반환해야 한다.

/* Figure 6.10 */
acquire() {
  while (!avaiable)
    ; /* busy wait */
  available = false;
}

releaes() {
  available = true;
}

while (true) {
  /* acquire lock */
    critical section
  
  /* release lock */
    remainder section
}

위 Figure 6.10을 보면 acquire() 함수가 락을 획득하고 release() 함수가 락을 반환한다.
Mutex 락은 available이라는 boolean 변수를 가지는데 이 변수 값이 락의 가용 여부를 표시한다.
- 락이 가용(available)하면 acquire()호출은 성공하고 락은 곧 사용 불가 상태가 된다.
- 사용 불가 상태의 락을 획득하려고 시도하는 프로세스는 락이 반환될 때까지 봉쇄된다.
- acquire() 또는 release() 함수 호출은 원자적으로 수행되어야 한다.

하지만 이런 구현 방식의 단점은 바쁜 대기(busy waiting)을 해야 한다는 것이다.
프로세스가 임계구역에 있는 동안 임계구역에 들어가기를 원하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 계속 실행해야 한다.
바쁜 대기는 다른 프로세스가 생산적으로 사용할 수 있는 CPU 주기를 낭비한다.

앞서 설명한 mutex 락 유형을 스핀락(spinlock)이라고 한다.
- 락을 사용할 수 있을 때까지 프로세스가 회전하기 때문이다.
스핀락은 프로세스가 락을 기다려야 하고 문맥 교환에 상당한 시간이 소요될 때 문맥 교환이 필요하지 않다는 장점이 있다.

6.6 Semaphores

세마포(semaphores)는 mutex와 유사하게 동작하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화할 수 있는 방법을 제공해준다.
- 세마포(semaphore) : 2개의 원자적 함수로 조작되는 정수 변수로서, 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법으로 사용된다. ²
세마포 $S$는 정수 변수로서, 초기화를 제외하고는 단지 2개의 표준 원자적 연산 wait()와 signal()로만 접근할 수 있다.
- wait() = P (검사하다)
- signal() = V (증가하다)

wait()와 signal()의 정의는 다음과 같다.
- wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 한다.
- 즉, 한 스레드가 세마포 값을 변경하면, 다른 어떤 스레드도 동시에 세마포 값을 변경할 수 없다.

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

signal(S) {
  S++;
}

6.6.1 Semaphore Usage

운영체제는 카운팅(count)과 이진(binary) 세마포를 구분한다.
- 카운팅 세마포의 값은 제한 없는 영역을 갖는다.
- 이진 세마포의 값은 0과 1사이의 값만 가능하다.
카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있다.
세마포는 가용한 자원의 개수로 초기화된다.
각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하며, 이때 세마포의 값은 감소한다.
프로세스가 자원을 방출 할 때는 signal() 연산을 수행하고 세마포는 증가하게 된다.
세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타낸다.
이후 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 봉쇄된다.

6.6.2 Semaphore Implementation

위에서 설명한 세마포 연산 wait()과 signal()의 정의 역시 mutex 락처럼 바쁜 대기를 해야하는 문제를 가지고 있다.
이걸 극복하기 위해 wait()과 signal() 세마포 연산의 정의를 다음과 같이 변경할 수 있다.
프로세스가 wait() 연산을 실행하고 세마포 값이 양수가 아닌 것을 발견하면, 프로세스는 반드시 대기해야 한다.
그러나 바쁜 대기 대신에 프로세스는 자신을 일시 중지시킬 수 있다.
일시 중지 연산은 프로세스를 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기 상태로 전환한다.
그 후에 제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행하기 위하여 선택한다.

세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야 한다.
프로세스는 wakeup() 연산에 의하여 재시작되는데, 이것은 프로세스의 상태를 대기상태에서 준비 완료 상태로 변경한다.
그리고 프로세스는 준비 완료 큐에 넣어진다.
세마포를 다음과 같이 정의할 수 있다.
- 각 세마포는 한 개의 정수 value와 프로세스 리스트 list를 가진다.
- 프로세스가 세마포를 기다려야 한다면, 이 프로세스를 세마포의 프로세스 리스트에 추가된다.

typedef struct {
  int value;
  struct process *list;
} semaphore; 

wait()와 signal() 연산은 다음과 같이 정의할 수 있다.
- signal() 연산은 프로세스 리스트에서 한 프로세스를 꺼내서 그 프로세스를 깨워준다.
- sleep() 연산은 자기를 호출한 프로세스를 일시 중지시킨다.
- wakeup(P) 연산은 일시 중지된 프로세스 P의 실행을 재개시킨다.

wait(semaphore *S) {
  S->value--;
  if (S->value < 0) {
    add this process to S->list;
    sleep();
  }
}

signal(semaphore *S) {
  S->value++;
  if (S->value <= 0) {
    remove a process P from S->list;
    wakeup(P);
  }
}

6.7 Monitors

세마포 또는 mutex 락을 이용하여 임계구역 문제를 해결할 때 프로그래머가 세마포를 잘못 사용하면 다양한 유형의 오류가 쉽게 발생할 수 있다.
이러한 오류를 처리하기 위한 한 가지 전략은 간단한 동기화 도구를 통합하여 고급 언어 구조물을 제공하는 것이다. 그 중 하나가 모니터(monitors) 형이다.

6.7.1 Usage

추상화된 데이터 형(abstract data type, ADT)은 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호한다.
- 모니터 형(monitor type)은 모니터 내부에서 상호 배제가 보장되는 프로그래머가 정의한 일련의 연산자 집합을 포함하는 ADT이다.
모니터 형은 또한 변수들의 선언을 포함하고 있는데 이 변수들의 값은 그 형에 해당하는 한 인스턴스의 상태를 정의한다.
그리고 모니터 형은 이 변수들을 조작할 수 있는 프로시저 또는 함수들의 본체도 같이 포함하고 있다.

/* Figure 6.11 Pseudocode syntax of a monitor */
monitor monitor name
{
  /* shared variable declarations */

  function P1 (...) {
    ...
  }
  function P2 (...) {
    ...
  }

  ...
  function Pn (...) {

  }
  initialization_code (...) {
    ...
  }

}

6.8 Liveness

라이브니스(liveness)는 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성을 말한다.

6.8.1 Deadlock

대기 큐를 가진 세마포를 구현은 2개 이상의 프로세스들이, 오로지 대기 중인 프로세스들 중 하나에 의해서만 야기될 수 있는 이벤트를 무한정 기다리는 상황이 발생할 수 있다.
이런 상태에 도달했을 때, 이들 프로세스들을 교착 상태(deadlock)라고 한다.
- 한 집합 내의 모든 프로세스가 그 집합 내의 다른 프로세스만이 유발할 수 있는 이벤트를 기다릴 때, 이 프로세스들의 집합이 교착 상태에 있다고 말한다.

References

KakaoTalk Twitter Facebook LinkedIn

poeun 🔅