[OS] 프로세스 동기화(Process Synchronization)

 

서론

---

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

공유 자원 접근의 예

먼저 위와 같은 예를 살펴봅시다. 공유 자원인 전역 변수 예금 10만 원이 있다고 가정합시다. 프로세스 P1은 예금 10만 원을 확인한 상황에서 프로세스 P2가 예금 5만 원을 입금하여 총 15만 원의 예금을 저장합니다. 하지만 프로세스 P1입장에서는 아직 예금이 10만 원 이기에 10만 원을 추가하더라도 15 + 10 = 25라는 결과가 아닌 10 + 10 = 20이라는 총예금이 저장되게 됩니다.

 이러한 부정확한 상태에 도달하는 것은 두 개의 프로세스가 동시에 예금이라는 변수를 조작하도록 허용했기 때문입니다. 이처럼 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 합니다. 위와 같은 경쟁 상황으로부터 보호하기 위해, 우리는 한순간에 하나의 프로세스만이 변수 count를 조작하도록 보장해야 합니다. 이러한 보장을 위해, 우리는 어떤 형태로든 프로세스들이 동기화되도록 할 필요가 있습니다.

공유 자원	여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말함 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있음
경쟁 조건	2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황 경쟁 조건이 발생하면 공유 자원 접근 순서에 따라 실행 결과가 달라질 수 있음

 

문제(_The Critical-Section Problem)

---

프로세스 동기화에 관한 논의는 소위 임계 구역 문제라고 불리는 문제로부터 시작합니다. n개의 프로세스가 있는 시스템을 고려해 봅시다. 각 프로세스는 임계 구역(critical section)이라고 부르는 코드 부분을 포함하고 있고, 그 안에서는 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있습니다. 이 시스템의 중요한 특징은 한 프로세스가 자신의 임계 구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계 구역에 들어갈 수 없다는 사실입니다. 즉 동시에 두 프로세스는 그들의 임계 구역 안에서 실행할 수 없습니다. 임계 구역 문제는 프로세스들이 데이터를 협력적으로 공유하기 위하여 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜을 설계하는 것입니다. 각 프로세스는 자신의 임계 구역으로 진입하려면 진입 허가를 요청해야 합니다. 이러한 요청을 구현하는 코드 부분을 진입 구역(entry section)이라고 부릅니다. 임계 구역 뒤에는 퇴출 구역(exit section)이 따라올 수 있으며, 코드의 나머지 부분들은 총칭하여 나머지 구역(remainder section)이라고 부릅니다. 전형적인 프로세스의 일반적인 구조가 아래 이미지에 나타나 있습니다. 진입 구역과 퇴출 구역은 중요한 코드 부분임을 강조하기 위하여 상자로 둘러싸여 있습니다.

 

전형적인 프로세스의 일반적인 구조

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

1. 상호 배제(mutual exclusion): 한 프로세스가 임계 구역에 들어가면 다른 프로세스는 임계 구역에 들어갈 수 없다.
2. 진행의 융통성(progress flexibility): 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다.
3. 한정된 대기(bounded waiting): 어떤 프로세스도 무한정으로 대기하지 않아야 한다.

그렇다면 이제 우리는 이번 글에서 이러한 임계 구역 문제를 해결하는 방안을 크게 아래의 경우로 나누어 살펴보겠습니다.

1. 소프트웨어 기반 해결법(Peterson의 해결안)
2. 하드웨어 기반 해결법(Memory Barriers, test_and_set & compare_and_swap)
3. 상위 수준 소프트웨어 도구(Mutex Locks, Semaphores)

 

1. Peterson의 해결안(_Peterson's Solution) - 소프트웨어 기반 해결법

---

int turn;
boolean flag[2];​

변수 turn은 임계 구역으로 진입할 순번을 나타냅니다. 즉 만일 turn == i 이면 프로세스 Pi가 임계 구역에서 실행될 수 있습니다. flag 배열은 프로세스가 임계 구역으로 진입할 준비가 되었다는 것을 나타냅니다. 예를 들어, flag[i]가 true이라면 Pi가임계 구역으로 진입할 준비가 됩니다.

Peterson의 해결안에서 프로세스 Pi의 구조

 임계 구역으로 진입하기 위해서 Pi는 먼저 flag[i]를 true으로 만들고, turn을 j로 지정합니다. 이렇게 함으로써 프로세스 j가 임계 구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장합니다. 만일 두 프로세스가 동시에 진입하기를 원한다면 turn은 거의 동시에 i와 j로 지정될 것입니다. 그러나 둘 중 오직 한 배정만이 지속됩니다. 다른 배정은 발생하기는 하지만 곧바로 겹쳐 쓰이게 됩니다. turn의 궁극적인 값이 둘 중 누가 먼저 임계 구역으로 진입할 것인가를 결정합니다.

 이제 해결책이 올바르게 동작한다는 것을 증명해보겠습니다. 우리는 다음과 같은 사실을 보여야 합니다.

1. 상호 배제(mutual exclusion)가 제대로 지켜진다는 사실
2. 진행에 대한 요구 조건을 만족한다는 사실(progess flexibility)
3. 대기 시간이 한없이 길어지지 않는다는 사실(bounded waiting)

1번을 증명하려면 각 Pi가 임계 구역에 들어가기 위해서는 반드시 flag[j] == false이든지 아니면 turn == i 여야 함을 주목해야 합니다. 두 프로세스 모두 자기 임계 구역을 수행 중이라면 flag[0] == flag[1] == true로 지정하여야 합니다. 위 두 가지 분석을 살펴보면 P0와 P1이 모두 while 문을 동시에 성공적으로 지나가지는 못했을 것입니다. 왜냐하면 turn 변수의 값은 0이든지 1 둘 중 하나여야 하지 동시에 두 값을 가질 수는 없기 때문입니다. 따라서 둘 중 하나만이, 예를 들어 Pj만이 while을 성공적으로 지나갈 수 있었을 것이고, 나머지 Pi는 ("turn == j") 문을 한 번 이상 더 실행했어야 할 것입니다. 그렇지만 그 순간에 flag[j] == true이고 turn == j인 상태는 Pj가 임계 구역 안에 있을 때에는 변하지 않습니다. 따라서 상호 배제는 지켜집니다.

 2와 3을 증명하려면 우리는 프로세스 Pi가 임계 구역에 진입 못 하도록 막는 방법은 그것을 while 문에(flag[j] == true && turn == j) 조건으로 묶어두어 계속 공회전하도록 만드는 방법이라는 사실에 주목하여야 합니다. 이 while loop가 유일한 방법이기 때문입니다. Pj가 임계 구역에 들어갈 준비가 되지 않았을 경우에는 (flag[j] == false)이고 Pi는 임계 구역에 진입할 수 있습니다. Pj가 flag[j]를 true로 지정하고 역시 자신의 while 문을 수행하게 되면 이때 turn == i 이든지 turn == j일 것입니다. turn == i 라면 Pi가 임계 구역에 진입하게 되고 turn == j라면 Pj가 임계 구역에 진입하게 됩니다. 그러나 추후 Pj가 임계 구역을 빠져나올 때는 Pj가 flag[j]를 false로 재지정하여 Pi로 하여금 진입하게 만들어 줍니다. Pj가 flag[j]를 true로 재지정하고 나면 반드시 turn 값도 i로 지정해주어야 합니다. Pi는 while 문을 수행하는 동안 turn 값을 바꾸지 않기 때문에 Pi는 Pj가 지난번에 진입했다면 이번에는 자기도 한 번은(따라서 대기 시간이 한없이 길어지지 않음) 들어갈 수 있게(progess 보장) 됩니다.

하지만 Peterson의 해결안은 최신 컴퓨터 아키텍처에서 작동한다고 보장되지 않습니다. 주된 이유는 시스템 성능을 향상하기 위해 프로세서 및/또는 컴파일러가 종속성이 없는 읽기가 및 쓰기 작업을 재 정렬할 수 있기 때문입니다. 데이터를 공유하는 다중 스레드 응용 프로그램의 경우 명령 순서가 바뀌게 되면 데이터의 일관성이 깨지거나 예기치 못한 결과를 낳을 수 있습니다.

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

boolean flag = false;
int x = 0;

여기서 Thread 1은 다음 명령문을 수행합니다.

while (!flag)
	;
print x;

그리고 Thread 2는 다음 명령문을 수행합니다.

x = 100;
flag = true;

 물론 예상되는 동작은 스레드 1이 변수 x에 대해 값 100을 출력하는 것입니다. 그러나 변수 flag와 x 사이에 데이터 종속성이 없으므로 프로세서가 스레드 2의 명령어를 재 정렬하여 x = 100을 배정하기 전에 flag가 true로 지정될 수 있습니다. 이 상황에서 스레드 1은 변수 x에 대해 0을 출력할 수 있습니다. 프로세서가 스레드 1이 실행할 명령문을 재 정렬하여 flag 값을 적재하기 전에 변수 x를 적재할 수도 있지만 명백해 보이지는 않습니다. 이렇게 재 정렬되면 스레드 2가 실행할 명령어들이 재 정렬되지 않더라도 스레드 1은 변수 x에 대해 0을 출력할 것입니다.

Peterson의 해결안에서 명령 순서 변경의 영향

 

2. 하드웨어 기반 해결법(Memory Barriers, test_and_set & compare_and_swap)

---

(1) 메모리 장벽(Memory Barriers)

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

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

 메모리 모델은 프로세서 유형에 따라 다르므로 커널 개발자는 공유 메모리 다중 처리기에서 메모리 변경의 가시성에 대한 어떠한 가정도 할 수 없습니다. 이 문제를 해결하기 위해 컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장합니다. 이러한 명령어를 메모리 장벽(memory barries) 또는 메모리 펜스(memory fences)라고 합니다. 메모리 장벽 명령어가 실행될 때, 시스템은 후속 적재 또는 저장 연산이 수행되기 전에 모든 적재 및 저장이 완료되도록 합니다. 따라서 명령이 재 정렬되더라도 메모리 장벽은 향후 적재 또는 저장 작업이 수행되기 전에 저장 작업이 메모리에서 완료되어 다른 프로세서에 보이도록 합니다.

 명령어를 재 정렬하여 잘못된 결과를 초래할 수 있는 가장 최근의 예제로 돌아가서 예상되는 결과나 나오도록 메모리 장벽을 사용해봅시다.

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

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

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

 마찬가지로 스레드 2에서 수행한 배정 사이에 메모리 장벽을 넣으면

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

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

Peterson의 해결안과 관련하여 진입 구역의 처음 두 배정문 사이에 메모리 장벽을 배치하여 작업의 재정렬을 피할 수 있습니다. 메모리 장벽은 매우 낮은 수준의 연산으로 간주하며 일반적으로 상호 배제를 보장하는 특수 코드를 작성할 때 커널 개발자만 사용합니다.

(2) 하드웨어 명령어 test_and_set() & compare_and_swap()

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

원자적 test_and_set() 명령어의 정의

중요한 특징으로는 이 명령어가 원자적(atomically, 더 이상 나누어질 수 없는 하나의 동작, 인터럽트가 발생돼도 멈추지 않음)으로 실행된다는 점입니다. 

원자적 행위 - 위키백과, 우리 모두의 백과사전

그러므로 만일 두 개의 test_and_set() 명령어가 동시에 실행된다면(각각 다른 코어에서), 이들은 어떤 임의의 순서로 순차적으로 실행될 것입니다. 만일 기계가 test_and_set() 명령을 지원한다면, false로 초기화되는 lock이라는 boolean 변수를 선언하여 상호 배제를 구현할 수 있습니다. 이를 사용하는 프로세스 Pi의 구조는 아래와 같습니다.

test_and_set() 명령어를 사용한 상호 배제 구현

다음으로 compare_and_swap() 명령어(CAS)는 test_and_set() 명령어와 마찬가지로 두 개의 워드에 대해 원자적인 연산을 하지만 두 워드의 내용 교환에 기반을 둔 다른 기법을 사용합니다. CAS는 3개의 피연산자를 대상으로 연산을 하며, 아래 코드와 같이 정의되어 있습니다.

compare_and_swap() 명령어의 정의

피연산자 value는 오직 (*value == expected) 수식이 참일 때에만 new_value로 지정됩니다. 어떠한 경우에든 CAS 명령어는 언제나 value의 원래 값을 반환합니다. 이 명령의 중요한 특징은 명령이 원자적으로 실행된다는 것입니다. 따라서 두 개의 CAS 명령이 동시에 실행되면(각각 다른 코어에서) 임의의 순서로 순차적으로 실행됩니다.

 CAS를 사용하는 상호 배제는 다음과 같이 지켜질 수 있습니다.

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

프로세스 Pi의 구조가 아래에 나와 있습니다.

compare_and_swap() 명령어를 사용한 상호 배제 구현

위 알고리즘은 상호 배제 조건은 만족시키지만 한정된 대기 조건을 만족시키지는 못합니다. 임계 구역 요구 조건을 모두 만족시키는 compare_and_swap() 명령어를 이용한 또 다른 알고리즘이 아래에 나타나 있습니다. 

공통된 데이터는 아래와 같습니다.

boolean waiting[n];
int lock;

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

 Progress 조건이 만족함을 보이기 위해서는 위의 상호 배제 논리를 여기에도 비슷하게 사용할 수 있습니다. 임계 구역을 떠나는 프로세스는 lock을 0으로 하든지 waiting[j]를 false로 합니다. 어느 쪽이든 둘 다 임계 구역으로 들어가고자 하는 프로세스를 진입하게 만들어 줍니다.

 한정된 대기(bounded waiting) 조건을 만족시킴을 증명하기 위해서는 한 프로세스가 임계 구역을 떠날 때에는 waiting 배열을 순환하면서 훑어본다는 사실에 착안하면 됩니다. 이처럼 순환하면서 조사하여(waiting[j] == true) 이면서 위 순환 순서 중 첫 번째 프로세스가 임계 구역에 들어가게 됩니다. 따라서 임계 구역에 들어가고자 하는 프로세스는 최대한 n - 1회만 양보하면 들어갈 수 있습니다.

 

3. 상위 수준 소프트웨어 도구(Mutex Locks, Semaphores)

---

(1) Mutex Locks

바로 위에서 제시한 임계 구역 문제에 대한 하드웨어 기반 해결책은 복잡할 뿐 아니라 응용 프로그래머는 사용할 수가 없습니다. 대신 운영체제 설계자들은 임계 구역 문제를 해결하기 위한 상위 수준 소프트웨어 도구들을 개발했습니다. 가장 간단한 도구가 바로 Mutex Locks입니다. 사실 mutex라는 용어는 mutual exclusion의 축약 형태입니다. 우리는 임계 구역을 보호하고, 따라서 경쟁 조건을 방지하기 위해 mutex 락을 사용합니다. 즉, 프로세스는 임계 구역에 들어가기 전에 반드시 락을 획득해야 하고 임계 구역을 빠져나올 때 락을 반환해야 합니다. 아래 코드처럼 acquire() 함수가 락을 획득하고 release() 함수가 락을 반환합니다.

Mutex 락을 사용한 임계구역 문제 해결책

Mutex 락은 available이라는 boolean 변수를 가지는데 이 변수 값이 락의 가용 여부를 표시합니다. 락이 가용하면 acquire() 호출은 성공하고 락은 곧 사용 불가 상태가 됩니다. 사용 불가 상태의 락을 획득하려고 시도하는 프로세스는 락이 반환될 때까지 봉쇄됩니다.

acquire() 함수의 정의는 다음과 같습니다.

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

release() 함수의 정의는 다음과 같습니다.

release() {
    available = true;
}

 acquire() 또는 release() 함수 호출은 원자적으로 수행되어야 합니다. 따라서 mutex 락은 이전에 설명한 CAS를 사용하여 구현될 수 있습니다. 

 지금까지 설명한 구현 방식의 단점은 바쁜 대기(busy waiting)를 해야 한다는 것입니다. 프로세스가 임계 구역에 있는 동안 임계 구역에 들어가기를 원하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 계속 실행해야 합니다. 이러한 계속된 루프의 실행은 하나의 CPU 코어가 여러 프로세스에서 공유되는 실제 다중 프로그래밍 시스템에서 분명히 문제가 됩니다. 바쁜 대기는 다른 프로세스가 생상적으로 사용할 수 있는 CPU 주기를 낭비합니다. (이후 Semaphores에서는 대기 프로세스를 일시적으로 휴면 상태로 전환한 후 락을 사용할 수 있게 되면 깨워서 바쁜 대기를 피하는 전략을 검토합니다.)

 우리가 설명한 mutex 락 유형을 스핀 락(spinlock, 바쁜 대기의 한 종류)이라고도 합니다. 락을 사용할 수 있을 때까지 프로세스가 "회전"하기 때문입니다.

스핀락 - 위키백과, 우리 모두의 백과사전

그러나 스핀 락은 프로세스가 락을 기다려야 하고 문맥 교환에 상당한 시간이 소요될 때 문맥 교환이 필요하지 않다는 장점이 있습니다. 다중 코어 시스템의 특정 상황에서는 실제로 락이 필요할 때 스핀 락이 선호됩니다. 최신 다중 코어 컴퓨팅 시스템에서 스핀 락은 많은 운영체제에서 널리 사용됩니다. 

(2) 세마포(_Semaphores)

이번에는 Mutex와 유사하게 동작하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화할 수 있는 방법을 제공하는 강력한 도구를 설명해보겠습니다.

세마포 S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait()와 Signal()로만 접근할 수 있습니다. wait() 연산은 원래 "검사하다"를 의미하는 네덜란드어 proberen에서 P, 그리고 signal() 연산은 "증가하다"를 의미하는 verhogen에서 V라고 지어졌습니다.

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

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

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

signal(S) {
    S++;
}

 wait()와 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 합니다. 즉, 한 스레드가 세마포 값을 변경하면, 다른 어떤 스레드도 동시에 동일한 세마포 값을 변경할 수 없습니다. 추가로, wait(S)의 경우, S의 정수 값을 검사하는 작업(S <=0)과 그에 따라 실행될 수 있는 변경(S--)하는 작업 또한 인터럽트 되지 않고 실행되어야 합니다. 이제 이들 연산이 어떻게 구현되는지와 어떻게 사용될 수 있는지를 알아보겠습니다.

(2-1) 세마포 사용법(_Semaphore Usage)

운영체제는 아래의 두 가지 세마포를 구분합니다.

1. 카운팅 세마포(counting semaphore): 제한 없는 영역(domain)의 값을 가진다.
2. 이진 세마포(binary semaphore): 0과 1 사이의 값만 가진다.

이진 세마포는 mutex락과 유사하게 동작합니다. 사실 몇몇 시스템에서는 mutex락을 제공하지 않고 상호 배제를 보장하기 위해서 이진 세마포가 대신 사용됩니다.

 카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있습니다. 

1. 세마포는 가용한 자원의 개수로 초기화됩니다.
2. 각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하며, 이때 세마포의 값은 감소합니다.
3. 프로세스가 자원을 방출할 때는 signal() 연산을 수행하고 세마포는 증가하게 됩니다.
4. 세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타냅니다.
5. 이후 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 봉쇄됩니다.

 우리는 또한 다양한 동기화 문제를 해결하기 위하여 세마포를 사용할 수 있습니다. 예를 들어 P1은 S1 명령문을, P2는 S2 명령문을 병행하게(concurrently) 수행하려는 두 프로세스를 고려해 봅시다. 우리는 이 문제를 P1과 P2가 세마포 synch를 공유하도록 하고, synch는 0으로 초기화합니다. P1에 다음 명령문을 삽입합니다.

S1;
signal(synch);

또 P2에 다음 명령문을 삽입합니다.

wait(synch);
S2;

synch 값은 0으로 초기화되어 있으므로, P2가 S2를 수행하는 것은 P1이 signal(synch)를 호출한 후에만 가능할 것입니다. 따라서 이 호출은 S1을 실행한 이후에만 가능할 것입니다.

(2-2) 세마포 구현(_Semaphore Implementation)

이전에 논의된 mutex 락 구현은 바쁜 대기(busy waiting)를 해야 했다는 사실을 기억해야 합니다. 지금 설명한 세마포 연산 wait()과 signal()의 정의 역시 같은 문제를 가지고 있습니다. 이 문제를 극복하기 위하여, 우리는 wait()와 signal() 세마포 연산의 정의를 다음과 같이 변경할 수 있습니다. 

1. 프로세스가 wait() 연산을 실행하고 세마포 값이 양수가 아닌 것을 발견하면, 프로세스는 반드시 대기해야 한다.
2. 그러나 바쁜 대기 대신에 프로세스는 자신을 일시 중지시킬 수 있다.
3. 일시 중지 연산은 프로세스를 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기 상태로 전환한다.
4. 그 후에 제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행하기 위하여 선택한다.

 세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야 합니다. 프로세스는 wakeup() 연산에 의하여 재시작되는데 이것은 프로세스의 상태를 대기상태에서 준비 완료 상태로 변경합니다. 그리고 프로세스는 준비 완료 큐에 넣어집니다(CPU는 CPU 스케줄링 알고리즘에 따라 실행 중인 프로세스로부터 새로 준비 완료가 된 프로세스로 전환될 수도 있고 되지 않을 수도 있다).

 이러한 정의를 따르는 세마포를 구현하기 위해, 우리는 세마포를 다음과 같이 정의합니다.

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

각 세마포는 한 개의 정수 value와 프로세스 리스트 list를 가집니다. 프로세스가 세마포를 기다려야 한다면, 이 프로세스를 세마포의 프로세스 리스트에 추가합니다. signal() 연산은 프로세스 리스트에서 한 프로세스를 꺼내서 그 프로세스를 깨워줍니다.

 wait() 연산은 이제 다음과 같이 정의될 수 있습니다.

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

signal() 연산은 다음과 같이 정의될 수 있습니다.

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

sleep() 연산은 자기를 호출한 프로세스를 일시 중지시킵니다. wakeup(P) 연산은 일시 중지된 프로세스 P의 실행을 재개시킵니다. 이들 두 연산은 운영체제의 기본적인 시스템 콜로 제공됩니다.

 바쁜 대기를 하는 세마포의 고전적 정의에서는 세마포의 값은 음수를 가질 수 없으나, 이처럼 구현하면 음수 값을 가질 수 있습니다. 세마포 값이 음수일 때, 그 절댓값은 세마포를 대기하고 있는 프로세스들의 수입니다. 이 사실은 wait() 연산의 구현에서 세마포 값의 감소와 검사의 순서를 바꾼 결과입니다.

 대기하는 프로세스들의 리스트는 각 프로세스 제어 블록(PCB)에 있는 연결 필드에 의하여 쉽게 구현될 수 있습니다. 각 세마포는 정수 값과 프로세스 제어 블록의 리스트에 대한 포인터를 갖고 있습니다. 한정된 대기를 보장하도록 리스트에 프로세스를 추가하고 삭제하는 한 가지 방법은 선입 선출 방식 큐를 사용하는 것으로 세마포가 큐의 머리와 꼬리에 대한 포인터를 모두 가지게 됩니다. 그러나 일반적으로 리스트는 임의의 큐잉 전략을 사용할 수 있습니다. 세마포를 정확하게 사용하는 것은 세마포 리스트를 위해 특정한 큐잉 전략을 사용하는 것과는 무관합니다.

 이전에 언급했던 것처럼 세마포가 원자적으로 실행되어야 한다는 것은 매우 중요합니다. 우리는 같은 세마포에 대해 두 프로세스가 동시에 wait()와 signal() 연산들을 실행할 수 없도록 반드시 보장해야 합니다. 이런 상황은 임계구역 문제에 해당합니다. 단일 처리기 환경에서는, 단순히 wait() 와 signal() 연산들이 실행되는 동안 인터럽트를 금지함으로써 간단히 해결할 수 있습니다. 이 방법은 일단 인터럽트가 금지되면, 다른 프로세스들의 명령어들이 끼어들 수 없기 때문에 단일 처리기 환경에서는 올바르게 동작합니다. 인터럽트가 다시 가능해지고 스케줄러가 제어를 다시 얻을 수 있을 때까지 오로지 현재 수행되고 있는 프로세스만 실행됩니다.

 다중 코어 환경에서는 모든 처리 코어에서 인터럽트를 금지하여야만 합니다. 그렇지 않으면(다른 코어에서 실행되는) 상이한 프로세스들의 명령어들이 임의의 방법으로 서로 끼어들 수 있습니다. 모든 코어에서 인터럽트를 금지하는 매우 어려운 작업일 수 있으며 성능을 심각하게 감소시킵니다. 따라서 SMP 시스템은 wait() 와 signal() 연산이 원자적으로 실행되는 것을 보장하기 위하여 compare_and_set() 또는 스핀 락과 같은 다른 기법을 제공해야 합니다.

 우리는 wait()와 signal() 연산의 현재 정의에서 바쁜 대기를 완전하게 제거하지 못했다는 것을 인정하는 것이 중요합니다. 오히려, 우리는 바쁜 대기를 진입 코드에서 응용 프로그램의 임계 구역으로 이동하였습니다. 더구나, 우리는 바쁜 대기를 wait()와 signal() 연산의 임계 구역에만 국한하였으며, 이 구역은 매우 짧습니다(코드가 적절하게 작성되었다면, 약 10개의 명령어를 넘지 않는다). 그러므로 임계 구역은 거의 항상 비어 있으며, 바쁜 대기는 드물게 발생하며, 발생하더라도 그 시간이 아주 짧습니다. 임계 구역이 매우 길거나(수 분 또는 심지어 수 시간 정도) 또는, 거의 항상 점유된 응용 프로그램들을 갖는 전혀 다른 황경도 존재합니다 이 경우에 바쁜 대기는 극도로 비효율적입니다.

 

정리

---

1. 경쟁 조건은 프로세스가 공유 데이터에 병행하게(concurrently)하게 접근할 때 발생하며 최종 결과는 병행 접근이 발생한 특정 순서에 따라 다르다. 경쟁 조건으로 인해 공유 데이터 값이 손상될 수 있다.
2. 임계 구역은 공유 데이터가 조작될 수 있으며, 경쟁 조건이 발생할 수 있는 코드 영역이다. 임계구역 문제는 데이터를 협력적으로 공유하기 위하여 자신의 활동을 동기화하는 프로토콜을 설계하는 것이다.
3. 임계 구역 문제에 대한 해결책은 (1) 상호 배제, (2) 진행의 융통성, (3) 한정된 대기 의 세 가지 요구 사항을 충족해야 한다.
4. Peterson의 해결안과 같은 임계구역 문제에 대한 소프트웨어 해결책은 최신 컴퓨터 아키텍처에서 제대로 작동하지 않는다.
5. 임계구역 문제에 대한 하드웨어 지원에는 Memory Barriers, compare_and_swap 명령과 같은 하드웨어 명령 및 원자적 변수가 포함된다.
6. Mutex 락은 프로세스가 임계 구역에 들어가기 전에 락을 획득하고 임계 구역에서 나올 때 락을 해제할 것을 요구함으로써 상호 배제를 제공한다.
7. Mutex 락과 같이 세마포를 사용하여 상호 배제를 제공할 수도 있다. 그러나 mutex 락은 락의 사용 여부를 나타내는 이진 값을 가지지만, 세마포는 정수 값을 가지므로 다양한 동기화 문제를 해결하는 데 사용될 수 있다. 

 

세마포와 뮤텍스의 차이

---

[운영체제] Mutex 뮤텍스와 Semaphore 세마포어의 차이

세마포와 뮤텍스의 차이는 공유 자원에 접근할 수 있는 대상의 개수 차이 입니다.

• 뮤텍스는 한개의 스레드만이 공유 자원에 접근할 수 있습니다.(이진 세마포랑 같은 개념)
• 세마포는 카운트 변수를 사용해 공유자원에 여러 프로세스가 접근하는 것을 막습니다.