운영체제 공룡책 : Ch6. Synchronization Tools | 동기화 도구들

📌 들어가며

협력적 프로세스 cooperating process는 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나 영향을 받는 프로세스이다. 협력적 프로세스는 논리 주소 공간(즉, 코드 및 데이터)을 직접 공유하거나 공유 메모리 또는 메시지 전달을 통해서만 데이터를 공유할 수 있는데, 공유 데이터를 동시에 접근하면 데이터의 일관성을 망칠 수 있다. 이번 단원에서는 논리 주소 공간을 공유하는 협력적 프로세스가 질서있는 실행을 통해 데이터의 일관성을 유지하는 다양한 메커니즘에 대해 다루어보자.

 

---

📚 6.1 배경 Background

 프로세스는 concurrent하고 parallel하게 실행될 수 있다. 즉, CPU 스케줄러가 프로세스 사이에서 빠르게 오가며 각 프로세스를 실행하며 각 프로세스를 실행하여 모든 프로세스를 병행 실행시킨다. 

이것이 의미하는 바는, 한 프로세스는 다른 프로세스가 스케줄 되기 전에 일부분만 진행할 수 있다는 것이다. 사실 프로세스는 명령어가 실행될 때 어느 지점에서나 인터럽트 될 수 있고, 처리 코어는 다른 프로세스의 명령어를 실행하도록 할당될 수 있다. 또한 다른 프로세스에 속한 두 개의 명령어 흐름이 동시에 다른 처리 코어에서 실행될 수도 있다. 이 과정에서의 동시 혹은 병렬 실행이 여러 프로세스가 공유하는 데이터의 무결성에 어떤 영향을 주게 될까?

 

동시에 여러 개의 프로세스가 동일한 데이터를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황 race condition이라고 한다. 경쟁 상황으로부터 보호하기 위해, 한순간에 하나의 프로세스만이 데이터를 조작하도록 보장해야 한다. 이러한 보장을 위해, 어떤 형태로든 프로세스들이 동기화되어야 한다.

 

---

📚 6.2 임계구역 문제 The Critical-Section Problem

n개의 프로세스로 이루어진 시스템이 있다고 할 때, 각 프로세스는 임계구역 critical section이라고 부르는 코드 부분을 포함하고 있고, 그 안에서는 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다. 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다는 점이 중요하다. 쉽게 말해 두 프로세스는 동시에 그들의 임계구역을 실행할 수 없다. 

 

임계구역 문제는 프로세스들이 데이터를 협력적으로 공유하기 위해 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜을 설계하는 것이다. 각 프로세스는 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 하는데, 이러한 요청을 구현하는 코드 부분을 진입 구역 entry section이라고 부른다. 임계구역 뒤에는 퇴출 구역 exit section이 따라올 수 있다. 코드의 나머지 부분들은 총칭하여 나머지 구역 remainder section이라고 부른다. 

임계구역 문제에 대한 해결안은 다음의 세가지 요구 조건을 충족해야 한다.

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

 

운영체제 내에서 임계구역을 다루기 위해 선점형 커널 preemptive kernel과 비선점형 커널 nonpreemptive kernel의 두 가지 일반적인 접근법이 사용된다. 선점형 커널은 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다. 비선점형 커널은 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져나갈 때까지 또는 block 될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 수행된다.

 

비선점형 커널은 커널 안에서 실행 중인 프로세스는 하나 밖에 없으므로 커널 자료구조에 대한 경쟁 조건을 염려할 필요가 없다. 그에 비해 선점형 커널은 경쟁 조건이 발생하지 않도록 신중하게 설계해야 한다. 그런데도 왜 선점적 커널을 더 사용하는 것일까? 선점형 커널의 경우, 커널 모드 프로세스가 대기 프로세스로 되기까지 상당히 긴 기간 동안 실행될 위험이 적기에 응답이 민첩해질 수 있다. 그리고 선점형 커널은 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 더 적합하다.

 

---

📚 6.3 피터슨의 해결안 Peterson's Solution

임계구역에 대한 고전적인 소프트웨어 기반 해결책인 피터슨의 해결안에 대해 알아보자.

 

피터슨의 해결안은 임계구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정된다. 프로세스는 P_0과 P_1로 구분하자. 편의상 P_i라고 표현할 때, P_j는 다른 프로세스를 가리키고 j는 1-i와 같다.

 

피터슨의 해결안은 두 프로세스가 두 개의 데이터 항목을 공유해야 한다.

int turn;
boolean flag[2];

변수 turn은 임계구역으로 진입할 순번을 나타낸다. 만약 turn == i이면, 프로세스 P_i가 임계구역에서 실행될 수 있다. 

flag 배열은 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다. flag[i]가 참이라면 P_i가 임계구역으로 진입할 준비가 되었다는 것이다.

 

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로 지정한다. 즉, P_j가 임계구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다. 만약 두 프로세스가 동시에 진입하기를 원한다면 turn은 거의 동시에 i와 j로 지정되지만, 둘 중 오직 한 배정만이 지속된다. 결국 turn의 궁극적인 값이 둘 중 누가 먼저 임계구역으로 진입할 것인가를 결정한다.

 

피터슨의 해결안이 올바르게 작동한다는 것을 증명하려면 다음과 같은 사실을 보여야 한다.

1. 상호 배제가 제대로 지켜진다.
2. 진행에 대한 요구 조건을 만족한다.
3. 대기 시간이 한없이 길어지지 않는다.

1번을 증명하려면, 각 P_i가 임계구역에 들어가기 위해서는 반드시 flag[j] == false 이든지 turn == i 여야 한다. 두 프로세스 모두 자신의 임계구역에 진입하려고 한다면 flag[i] == flag[j] == true가 되지만, turn 변수의 값이 0이면서 1일 수는 없기에 P_i과 P_j는 동시에 while문을 통과할 수 없을 것이다. 

 

2번과 3번을 증명하려면, P_i가 오로지 flag[j] == true와 turn == j에 의해 while 루프 안에서 공회전 할 때만 임계구역에 들어가지 못한다는 점을 들 수 있다.

P_j가 임계구역에 들어갈 준비가 안 되었을 때는 flag[j] == false 이고, P_i는 임계구역에 진입할 수 있다. P_j가 flag[j]를 true로 지정하고 역시 자신의 while문을 수행하게 되면 이때 turn은 i이거나 j일 것이다. turn == i 이면 P_i가 임계구역에 진입하게 되고, turn == j 이면 P_j가 임계구역에 진입하게 된다. 그러나 추후에 P_j가 임계구역을 빠져나올 때 P_j가 flag[j]를 false로 재지정하고 turn 값을 i로 지정하여 P_i가 진입할 수 있게 해준다. P_i가 while문 실행 중엔 turn 값을 바꿀 수 없기 때문에 P_j가 지난번에 임계구역에 진입했다면 P_i가 임계구역에 들어갈 수 있게 된다.

 

하지만 피터슨의 해결안은 최신 컴퓨터 아키텍처에서 작동한다고 보장되진 않는다. 주된 이유는 시스템 성능을 향상하기 위해 프로세서 및 컴파일러가 종속성이 없는 읽기 및 쓰기 작업을 재정렬 할 수 있기 때문이다.

 

예를 들어, 두 스레드 간에 공유되는 다음 데이터를 고려하자.

boolean flag = fasle;
int x = 0;

 

여기서 스레드1은 다음 명령문을 수행한다.

while(!flag)
	;
print x;

그리고 스레드2는 다음 명령문을 수행한다.

x = 100;
flag = true;

 

예상되는 동작은 스레드1이 변수 x에 대해 값 100을 출력하는 것이다. 하지만 변수 flag와 x 사이에 데이터 종속성이 없으므로 프로세서가 스레드2의 명령어를 재정렬하여 x=100을 배정하기 전에 flag가 true로 지정될 수 있고, 이 상황에서 스레드1은 변수 x에 대해 0을 출력할 수 있다.

 

---

📚 6.4 동기화를 위한 하드웨어 지원 Hardware Support for Synchronization

소프트웨어 기반 해결책은 최신 컴퓨터 아키텍처에서 작동하지 않을 수 있다. 그렇기에 임계구역 문제를 해결하기 위한 지원을 제공하는 세 가지 하드웨어 명령어에 대해 알아보자.

 

6.4.1 메모리 장벽 Memory Barriers

6.3절에서 봤듯이, 시스템은 명령어의 순서를 재정렬 할 수 있기에 데이터의 신뢰성이 떨어질 수 있다. 컴퓨터 아키텍처가 응용 프로그램에게 제공할 메모리 보장을 결정하는 방식을 메모리 모델 memory model이라고 하는데, 일반적으로 메모리 모델은 두 가지로 분류된다.

1. 강한 순서 strongly ordered :  한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임.
2. 약한 순서 weakly ordered : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음.

메모리 모델은 프로세서 유형에 따라 다르므로 커널 개발자는 공유 메모리 다중 처리기에서 메모리 변경의 가시성에 대한 가정을 할 수 없다. 이 문제를 해결하기 위해 컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 것을 보장하는데, 이러한 명령어를 메모리 장벽 memory barriers 또는 메모리 펜스 memory fences라고 부른다.

메모리 장벽 명령어가 실행될 때, 시스템은 모든 적재/저장 연산이 다음 적재/저장 연산이 수행되기 전에 완료되도록 하기에, 명령이 재정렬되더라도 향후 적재/저장 작업이 수행되기 전에 저장 작업이 메모리에서 완료되어 다른 프로세서에게도 즉시 반영이 되도록 한다.

 

명령어를 재정렬하여 잘못된 결과를 만들 수 있었던 문제로 돌아가보자.

그리고 여기에 예상되는 결과가 나오도록 메모리 장벽을 사용해보자.

 

스레드1에 메모리 장벽 연산을 추가하면

while(!flag)
	memory_barrier();
print x;

flag 값이 x 값보다 먼저 적재되도록 보장한다.

 

마찬가지로 스레드2에도 메모리 장벽 연산을 추가하면

x = 100;
memory_barrier();
flag = true;

flag에 배정하기 전에 x에 대한 배정이 먼저 실행되도록 할 수 있다.

 

메모리 장벽은 매우 낮은 수준의 연산으로 간주하며 일반적으로 상호 배제를 보장하는 특수 코드를 작성할 때 커널 개발자만 사용한다.

 

 

6.4.2 하드웨어 명령어 Hardware Instructions

대부분의 현대 컴퓨터 시스템에서는 원자적으로 atomically 워드의 내용물을 테스트하고 변경하거나 두 워드의 내용을 교환 swap할 수 있게 하는 특수한 하드웨어 명령어를 제공한다. 이 특수한 명령어를 사용하여 임계구역 문제를 해결할 수 있다. test_and_set()과 compare_and_swap() 명령어를 중심으로 살펴보자.

 

test_and_set() 명령어는 다음과 같이 정의할 수 있다.

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

중요한 특징은 이 명령어가 원자적으로 실행되기에 만약 두 test_and_set() 명령어가 (서로 다른 코어에서) 동시에 실행되더라도 임의의 순서로 순차적으로 실행될 것이다. 만약 기계가 test_and_set() 명령을 지원한다면, false로 초기화되는 lock이라는 boolean 변수를 선언하여 상호 배제를 구현할 수 있다. 프로세스 P_i의 구조는 다음과 같을 것이다.

do {
    while (test_and_set(&lock))
    	; /* do nothing */
        
    /* critical section */
        
    lock = false;
        
    /* remainder section */
} while (true);

 

compare_and_swap() 명령어(CAS)는 test_and_set() 명령어와 마찬가지로 두 개의 워드에 대해 원자적인 연산을 하지만 두 워드의 내용 교환 swap에 기반을 둔 다른 기법을 사용한다. CAS 명령어는 다음과 같이 정의된 세 가지 연산자를 기반으로 처리된다.

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

피연산자 value는 오직 (*value == expected) 수식이 참일 때만 new_value로 지정된다. 중요한 것은 명령이 원자적으로 실행되므로 두 CAS가 서로 다른 코어에서 동시에 실행되면 임의의 순서로 순차적으로 실행된다는 것이다.

 

프로세스 P_i에 대해 CAS를 통한 상호 배제는 다음과 같이 처리될 수 있다.

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

전역변수 lock이 선언되고 0으로 초기화된다. compare_and_swap()을 처음 호출한 프로세스가 lock을 1로 설정한다. 원래 lock의 값이 예상값 0과 같으므로 프로세스는 임계구역에 들어간다. 이후의 compare_and_swap() 호출은 현재 lock의 값이 예상값 0과 같지 않기 때문에 성공하지 못한다.  프로세스가 임계구역을 벗어날 때는 lock을 0으로 변경하고, 다른 프로세스가 임계구역에 들어갈 수 있게 허용한다.

 

위 알고리즘은 상호 배제 조건은 만족하지만, 한정된 대기 조건을 만족시키지는 못한다. 다음 코드는 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

일반적으로 compare_and_swap() 명령어는 상호 배제를 제공하기 위해 직접 사용되지 않고, 오히려 임계구역 문제를 해결하는 다른 도구를 구축하기 위한 기본 구성요소로 사용된다. 그러한 도구 중 하나는 원자적 변수 atomic variable로, 정수 및 부울과 같은 기본 데이터 유형에 대한 원자적 연산을 제공한다.

 

---

📚 6.5 Mutex Locks

임계구역 문제에 대한 하드웨어 기반 해결책은 복잡할 뿐만 아니라 응용 프로그래머는 사용할 수가 없다. 대신 운영체제 설계자들은 임계구역 문제를 해결하기 위한 상위 수준 소프트웨어 도구들을 개발하였고, 가장 간단한 도구가 바로 mutex lock이다. mutex lock으로 임계구역을 보호하고, 따라서 경쟁 조건을 방지하기 위해 mutex lock을 사용한다. 즉, 프로세스는 임계구역에 들어가기 전에 반드시 락을 획득해야 하고, 임계구역에서 빠져나올 때 락을 반환해야 한다.

위의 그림에서처럼 acquire() 함수가 락을 획득하고, release() 함수가 락을 반환한다.

 

mutex lock은 available이라는 boolean 변수를 가지는데, 이 변수 값이 락의 가용 여부를 표시한다.

 

acquire()은 다음과 같이 정의한다.

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

release()는 다음과 같이 정의한다.

release() {
    available = true;
}

 

acquire()과 release() 함수 호출은 원자적으로 수행되어야 한다. 따라서 mutex lock은 CAS를 통해 구현될 수 있다.

이렇게 구현했을 때의 최대 단점은 바로 바쁜 대기 busy waiting을 해야 한다는 것이다. 프로세스가 임계구역에 있는 동안 임계구역에 들어가기를 원하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 계속 실행해야 하고, 이러한 루프의 실행은 하나의 CPU 코어가 여러 프로세스에 공유되는 멀티프로그래밍 시스템에서 분명히 문제가 된다. 

 

---

📚 6.6 Semaphore

mutex와 유사하게 동작하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화할 수 있는 방법을 제공하는 도구에 대해 살펴보자.

 

세마포 S는 정수 변수로서, 초기화를 제외하고는 단지 두 가지의 표준 원자적 연산 wait()와 signal()로만 접근할 수 있다. 

 

wait()의 정의는 다음과 같다.

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

signal()의 정의는 다음과 같다.

signal(S) {
    S++;
}

 

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

 

---