[공룡책] Ch.6 동기화 도구

---

이 글은 공룡책을 읽고 정리한 글입니다.

---

 

 

 

0. 소개

---

3장에서 우리는 협력적 프로세스에 대해 배웠다. 협력적 프로세스는 논리 주소 공간을 직접 공유하거나, 공유 메모리 / 메시지 전달을 통해서만 데이터를 공유할 수 있다. 이때 공유 데이터를 동시에 접근하면 일관성을 망칠 수 있는데, 이 장에서는 논리 주소 공간을 공유하는 협력적 프로세스의 질서 있는 실행을 보장하는 것에 대해 논의한다.

---

 

 

 

1. 배경

---

우리는 3장에서 프로세스가 병행 또는 병렬로 실행할 수 있다는 것을 배웠고, 4장에서 CPU 스케줄러가 프로세스 사이를 오가며 모든 프로세스를 병행 실행시킨다는 것을 배웠다. 이것은 한 프로세스가 다른 프로세스가 스케줄 되기 전에 일부분만 진행한다는 것을 의미한다. 이때 한 변수에 서로 의존하는 경우 값이 변경되면 무결성을 해치는 상황이 된다. 병렬일 경우에도 마찬가지이다.

 

생산자 - 소비자 문제에서 count = 5라는 변수가 있을 때, 생산자는 레지스터 A에서 count++를 하고, 소비자는 레지스터 B에서  count--를 한다고 생각해보자. 이런 경우 count의 값은 4 또는 5 또는 6이 될 수 있는 것과 같이 부정확한 상태에 도달하게 된다.

이처럼 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황이라고 한다. 우리는 경쟁 상황이 생기지 않도록 하나의 프로세스만이 자료를 조작하도록 보장해야한다. 이런 보장을 위해 프로세스들을 동기화할 필요가 있다.

---

 

 

 

2. 임계구역 문제

---

프로세스 동기화에 관한 논의는 임계구역 문제로부터 시작한다.

임계구역이란 n개의 프로세스가 있을 때, 각 프로세스는 임계구역이라는 코드 부분이 존재하고, 임계구역 코드 안에서는 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다. 이 시스템의 특징은 한 프로세스가 자신의 임계구역에서 수행하면, 다른 프로세스들은 임계구역에 접근할 수 없다는 것이다. 

임계구역 문제는 프로세스들이 데이터를 협력적으로 공유하기 위해 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜을 설계하는 것이다.

각 프로세스는 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 하는데, 이런 요청을 구현하는 코드 부분이 진입 구역(entry section)이다. 그리고 임계구역 뒤에는 퇴출 구역(exit section)이 있다. 이후 밑의 코드는 나머지 구역(remainder section)이라고 부른다.

---

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

1. 상호 배제 (mutual exclusion)

→ 프로세스 P[i]가 자기의 임계구역에서 실행했다면, 다른 프로세스는 임계구역에 접근할 수 없다.

2. 진행 (progress)

→ 임계구역으로 진입하려는 프로세스들이 있다면, 나머지 프로세스들이 어떤 프로세스가 임계구역으로 진입할 수 있는지 결정하는데 참여하고, 이 결정은 무한정 연기될 수 없다.

3. 한정된 대기 (bounded waiting)

→ 어떤 프로세스가 임계구역으로 진입한다는 요청을 하면, 해당 요청이 허용될 때까지 다른 프로세스들이 임계구역에 진입하도록 허용하는 횟수에 한계가 있어야 한다.

---

운영체제 내에서 임계구역을 다루기 위해서는 선점형 커널과 비선점형 커널의 두 가지 일반적인 접근법이 사용된다.

선점형 커널은 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다.

비선점형 커널은 프로세스가 커널 모드에서 수행되는 동안 프로세스의 선점을 허용하지 않고, 커널 모드 프로세스는 커널을 빠져나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 수행한다.

 

일반적으로 선점형 커널을 더 선호하는 편인데, 커널 모드 프로세스가 오랫동안 실행할 위험이 적어서 선점형 커널이 더 응답이 빠르다. 그리고 실시간 프로세스가 현재 커널에서 실행중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 더 적당하다.

---

 

 

 

3. Peterson의 해결안

---

임계구역 문제에 대한 해결하는 소프트웨어적 방법중 하나가 있는데 이것을 Peterson's Solution이라고 부른다.

Peterson의 해결안은 임계구역과 나머지 구역을 번갈아가며 실행하는 두 개의 프로세스로 한정하고, 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.

int turn; // 임계구역으로 진입할 프로세스
boolean flag[2]; // 프로세스가 입계구역으로 진입할 준비가 됐으면 1

 

이때 turn == i이면 프로세스 P[i]가 임계구역에서 실행될 수 있고, flag[i][가 참이라면 P[i]가 임계구역으로 진입할 준비가 된다.

임계구역에 진입하기 위해서 P[i]는 먼저 flag[i]를 참으로 만들고, turn을 j로 지정한다. 이렇게 하여 프로세스 j가 임계구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.

만약 두 프로세스가 동시에 진입하기 원해도 한 프로세스만 배정이 지속되기 때문에 turn의 값이 누가 먼저 임계구역으로 진입할 것인지 결정하게 된다.

---

while(True) {
	flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
    	;
        /* critical section */
    flag[i] = false;
    	/* remainder section */
}

이제 이 해결책이 올바르게 동작하는지 증명만 하면 되므로 아래와 같은 사실을 보이면 된다.

1. 상호 배제가 제대로 지켜진다는 사실

2. 진행에 대한 요구 조건을 만족한다는 사실

3. 대기 시간이 한없이 길어지지 않는다는 사실

 

1) mutual exclusion 증명

각 P[i]가 임계구역에 들어가려면 flag[j] == false이거나, turn == i여야 한다. 이때 turn 값은 1개로만 설정되기 때문에 두 값이 동시에 임계구역에 들어갈 수는 없다. 그리고 임계구역에 들어간 순간에는 turn과 flag의 값을 변경하지 않기 때문에 상호 배제가 지켜진다.

 

2) progress, bounded waiting 증명

프로세스 P[j]가 임계구역으로 들어갈 준비가 되지 않았으면 flag[j] == false로 P[i]가 임계구역에 진입할 수 있다.

flag[j] == true, turn = j인 경우 P[j]가 임계구역에 진입하게 되는데, 나중에 P[j]가 임계구역을 빠져나온다면 flag[j] == false로 변경하여 P[i]가 임계구역에 진입할 수 있게끔 해준다. P[j]가 flag[j] == true로 재지정한다면 반드시 turn 값도 i로 지정해주어야 한다. 그리고 P[i]는 while문을 수행하는 동안 turn 값을 바꾸지 않기 때문에 P[i]는 P[j]가 이전에 임계구역에 진입했으면 이번에는 자신도 한 번은 들어갈 수 있게 된다.

 

아쉽게도 Peterson의 해결책은 최신 컴퓨터 아키텍처에서는 작동하지 않는다고 보면 된다. 이유는 시스템 성능을 향상시키기 위해 종속성이 없는 읽기/쓰기 작업을 재정렬할 수 있기 때문이다.

그래서 상호 배제를 유지하는 유일한 방법은 적절한 동기화 도구를 사용하는 것이다.

---

 

 

 

4. 동기화를 위한 하드웨어 지원

---

3절에서는 소프트웨어 기반의 해결책을 제시하였지만, 이것은 최신 컴퓨터 아키텍쳐에서는 적용되지 않는다. 다른 소프트웨어 기반의 해결책도 언젠가는 적용되지 않을 수 있기 때문에 하드웨어쪽에서 해결책을 찾아야 한다.

이 절에서는 임계구역 문제를 해결하기 위한 지원을 제공하는 세 가지 하드웨어 명령어를 제시한다.

---

1) 메모리 장벽

컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식을 메모리 모델이라고 한다. 메모리 모델은 아래 두 가지중 하나에 속한다.

 

- 강한 순서: 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임

- 약한 순서: 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음

메모리 모델은 프로세서 유형에 따라 달라서 커널 개발자는 어떠한 가정도 할 수가 없다는 문제가 있다.

 

이것에 대한 해결책은 컴퓨터 아키텍처가 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장한다. 이런 명령어를 메모리 장벽, 메모리 펜스라고 부른다.

 

메모리 장벽은 상호 배제를 보장하는 특수 코드를 작성할 때 사용된다.

---

2) 하드웨어 명령어

현대 기계들은 인터럽트 되지 않는 하나의 단위로 특별한 하드웨어를 제공한다.

한 워드(word)의 내용을 검사하고 변경하는 것을 test_and_set()

두 워드의 내용을 원시적으로 교환하는 것을 compare_and_swap() (CAS)

 

- test_and_set()

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

이 명령어의 특징은 원자적(atomically)으로 실행된다는 점이다. 그러므로 두 개의 test_and_set()이 동시에 실행된다면, 임의의 순서로 순차적으로 실행될 것이다.

만일 기계가 test_and_set() 명령어를 지원하면 false로 초기화된 lock이라는 boolean 변수를 사용하여 상호 배제를 구현할 수도 있다.

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

 

- compare_and_swap() (CAS)

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

CAS는 3개의 피연산자를 대상으로 연산을 하며, 피연산자 value는 오직 (*value ==  expected) 수식이 참일 때만 반환한다.

CAS는 언제나 value의 원래 값을 반환하고, 이 명령도 원자적으로 실행된다. 따라서 이 명령이 동시에 두 개가 들어오면 임의의 순서로 실행된다.

test_and_set()과 마찬가지로 CAS도 0으로 초기화된 전역 변수 lock을 사용하여 상호 배제를 구현할 수 있다.

/* 상호 배제 */
while(True) {
	while(compare_and_swap(&lock, 0, 1) != 0)
    	; /* do nothing */
    
    	/* critical section */
    
    lock = 0;
    
    	/* remainder section */
}

위 코드는 상호 배제를 만족하지만, 진행 문제(progress) 와 한정된 대기 조건(bounded waiting)을 만족시키지 못한다.

그래서 0으로 초기화되는 lock 변수와 false로 초기화되는 waiting 배열의 원소를 추가하여 코드를 구현한다.

/* 상호 배제, 진행 문제, 한정된 대기 조건 해결 */
while(True) {
	waiting[i] = true;
    key = 1;
    while (waiting[i] && key == 1)
    	key = compare_and_key(&lock, 0, 1);
    waiting[i] = false;
    
    	/* critical sections */
    
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
    	j = (j + 1) % n;
    
    if (j == i) lock = 0;
    else waiting[j] = false;
    
    	/* remainder section */
}

---

3) 원자적 변수

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

원자적 변수는 상호 배제를 보장하는데 사용되며, 원자적 갱신을 제공하지만 모든 상황에서 경쟁 조건을 완벽히 해결하지는 못한다는 단점이 있다.

---

 

 

 

5. Mutex Locks

---

4절에서 언급한 하드웨어 기반 해결책은 복잡하고, 응용 프로그래머가 사용할 수 없다. 그래서 운영체제 설계자들은 임계구역 문제를 해결하기 위해 상위 수준의 소프트웨어 도구를 개발하는데, 이중에서 가장 간단한 도구가 Mutex Locks이다.

 

Mutex Locks는 임계구역을 보호하고, 경쟁 조건을 방지하기 위해 사용한다. 즉 프로세스는 임계 구역에 들어가기 전에 반드시 lock을 획득해야 하고, 임계구역을 빠져나올 때 lock을 반환해야 한다. 여기서 lock을 획득하는 함수는 acquire()이고, lock을 반환하는 함수는 release()이다. 이 두 함수는 원자적으로 수행되어야 하기 때문에 CAS를 사용하여 구현된다.

 

이 방식의 단점은 바쁜 대기(busy waiting)을 해야 한다는 점이다. 바쁜 대기란 어떤 프로세스가 임계 구역에 있는 동안 임계구역에 들어가기를 원하는 다른 프로세스는 acquire() 함수를 호출하는 반복문을 계속 실행해야 한다. 이것은 CPU 주기를 낭비하게 된다.

 

여기에 나온 Mutex Locks은 스핀락(spinlock)이라고도 하는데, 락을 사용할 수 있을 떄까지 프로세스가 회전한다.

이때 스핀락은 문맥 교환이 필요하지 않다는 장점이 있어서 많은 운영체제에서 널리 사용된다.

---

 

 

 

6. 세마포 (Semaphores)

---

5절 처음에 언급했듯이 Mutex Locks는 가장 간단한 도구이다. 그래서 여기서는 mutex와 유사하게 동작하지만, 프로세스들이 자신의 행동을 더 정교하게 동기화할 수 있는 방법을 제공하는 강력한 도구를 설명한다.

 

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

signal(S) {
	S++;
}

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

wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 한다. 

---

1) 세마포 사용법

운영체제는 세마포를 카운팅 세마포와 이진 세마포로 나눈다.

카운팅 세마포의 값은 제한 없는 영역을 갖고, 이진 세마포의 값은 0 또는 1만 가능하다. 그래서 이진 세마포는 mutex lock과 유사하다.

 

카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는데 사용할 수 있다. 각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하여 세마포의 값을 줄인다. 반대로 프로세스가 자원을 방출할 때에는 signal() 연산을 수행하고 세마포의 값을 증가시킨다.

여기서 세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타내고, 이후 자원을 사용하려는 프로세스는 세마포의 값이 0보다 클 때까지 봉쇄된다.

---

2) 세마포 구현

Mutex Locks 구현에서 바쁜 대기 문제가 있었는데, 세마포 연산 wait()과 signal() 역시 바쁜 대기 문제를 가지고 있다.

 

- wait()

해결방안은 프로세스가 wait() 연산을 실행한다면 세마포 값이 양수가 아닐 경우 프로세스는 반드시 대기하도록 하는 것 대신 프로세스를 일시중지 시켜서 세마포와 관련된 대기 큐에 넣는다. 이때 프로세스를 일시중시 시키는 명령어는 sleep()이다.

 

- signal()

세마포 S를 대기하면서 일시중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작하면 된다. 이때 프로세스를 재시작하는 명령어는 wakeup() 연산이다.

---

 

 

 

7. 모니터

---

세마포는 프로세스 간의 동기화를 위해 편리하고 효과적으로 쓸 수 있지만, 잘못 사용하면 특정 실행 순서에만 발생하는 오류라 발견하기 어려운 타이밍 오류를 야기할 수 있다. 그리고 두 프로세스가 동시에 임계구역 안에 있는 문제도 발생할 수 있다.

이번 절에서는 일어날 수 있는 문제점을 나열하려고 한다.

 

- wait(mutex)와 signal(mutex) 연산의 순서가 바뀌면 여러 프로세스가 임계구역에 진입하여 상호 배제 조건을 위반한다.

- signal(mutex) 대신 wait(mutex)를 사용한 경우, 프로세스는 원래 wait(mutex) 함수가 실행될 때 영구적으로 봉쇄된다.

- 프로세스가 wait(mutex)나 signal(mutex)중 최소 하나를 빠뜨리면 프로세스는 영원히 봉쇄된다.

 

이렇게 다양한 오류가 쉽게 생길 수 있기 때문에 이런 오류를 처리하기 위해 간단한 동기화 도구를 통합하여 고급 언어 구조물을 제공하는 것이다. 모니터가 이런 고급 언어 구조물 중 하나이다.

 

모니터의 경우에는 아래 링크를 참조하면 더 자세하게 알 수 있다.

https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-11.-%EB%AA%A8%EB%8B%88%ED%84%B0

[운영체제(OS)] 11. 모니터

---