운영체제 (공룡책) - 6

‍주민하·2021년 10월 19일
동기화동기화 도구운영체제
1

운영체제

목록 보기
6/10

3. 프로세스 동기화

시스템은 보통 동시에, 혹은 병렬적으로 도는 여러(수백, 수천) 개의 스레드로 구성됨. 스레드는 주로 사용자 데이터를 공유함. 그러면서 운영체제는 다중 스레드를 지원하기 위해 지속적으로 여러 자료 구조를 갱신해야 함. 공유 데이터에 대한 접근을 제어하지 않으면 경합 조건이 발생해 손상된 데이터 값을 얻을 수도 있음.

프로세스 동기화란 공유 데이터에 대한 경합 조건을 방지하기 위해 접근을 제어하는 도구에 대한 내용임. 이러한 도구는 잘못 사용할 시 시스템 성능이 낮아지거나 교착상태가 발생하기에 조심히 다루어야 함.

6. 동기화 도구

협업 프로세스 cooperating process란 시스템에서 실행 중인 프로세스 중 다른 프로세스에 영향을 주거나 영향을 받을 수 있는 프로세스를 의미함. 협업 프로세스는 직접적으로 논리 주소 공간(즉, 코드랑 자료)을 공유할 수도 있고 공유 메모리나 메시지 전달만으로 자료를 공유할 수도 있음. 동시에 공유 데이터에 접근하면 데이터 비일관성이 발생할 수 있음. 이 단원에서는 논리 주소 공간을 공유하는 협업 프로세스가 순서대로 실행을 하도록 보장하여 데이터 일관성을 유지해주는 여러 메커니즘을 다룸.

단원 목표

  • 임계구역 문제와 경합 조건 이해
  • 임계구역 문제를 메모리 배리어, 비교 후 스왑 연산, 원자적 변수를 통한 하드웨어 해법 이해
  • 상호배제 락, 세마포어, 모니터, 조건 변수를 통해 임계구역 문제 해결
  • 임계구역 문제를 저/중/고 경쟁 시나리오에 따라 해결하는 도구 평가

6.1. 배경

프로세스는 동시 혹은 병렬로 실행 가능. 3.2.2 절에서 프로세스 스케줄링의 역할과 CPU 스케줄러가 빠르게 프로세스 간 교체를 해서 동시 실행을 제공하는 법을 알아봤음. 즉, 한 프로세스는 다른 프로세스가 스케줄링되기 전까지 잠깐만 실행이 된다는 뜻임. 사실상 언제나 인터럽트 당할 수도 있음. 추가적으로 4.2 절에서 병렬 실행을 통해 두 명령어 스트림(즉, 서로 다른 프로세스)이 서로 다른 프로세싱 코어에서 동시에 실행되도록 함. 이 단원에서는 동시 혹은 병렬 실행이 여러 프로세스가 공유하는 자료의 무결성 어떤 영향을 주는지에 대해 다룸.

실제 예시로. 3 단원에서 순차적 협업 프로세스 혹은 스레드로 구성된 시스템 모델을 개발했었음. 이때 전부 비동기로 돌면서 자료를 공유할 수도 있었음. 이 모델을 많은 운영체제 기능을 대표하는 패러다임인 생산자-소비자 문제에서 소개했었음. 특히 3.5 절에서는 유한 버퍼를 사용하여 프로세스가 메모리를 공유할 수 있는 법을 소개했었음.

이제 유한 버퍼로 다시 돌아와서... 언급했었듯이 원래 해법은 같은 시간에 최대 BUFFER_SIZE - 1 개의 원소를 허용했음. 이 알고리듬에서 이 결핍을 해결하기 위해 알고리듬을 수정한다고 가정. 한 가지 방법으로는 초기값이 0인 count라는 정수 변수를 추가해주는 것임. count는 버퍼에 새 원소를 추가할 때마다 증가되며, 버퍼에서 원소가 하나 씩 줄어들 때마다 감소됨. 생산자의 코드는 다음과 같음:

while (true) {
    /* next_produced에 원소를 생산 */
    
    while (count == BUFFER_SIZE) {
    	; /* 아무 것도 안 함 */
    }
    
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    count++;
}

소비자의 코드는 다음과 같이 수정:

while (true) {
    while (count == 0) {
    	; /* 아무 것도 안 함 */
    }
   
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    count--;
    
    /* next_consumed에 있는 원소를 소비 */
}

위에서의 생산자 소비자 함수가 각각 옳다고 하더라도, 동시에 실행될 시 제대로 작동 안 될 수도 있음. 예를 들어 count 변수의 값이 현재 5고, 생산자와 소비자 프로세스가 동시에 count++와 count--를 실행한다고 가정. 이 두 구문이 실행된 후 count의 값은 4가 될 수도, 5가 될 수도, 심지어 6이 될 수도 있음. 당연히 올바른 결과는 생산자와 소비자가 따로 실행됐다면 count == 5임.

count가 잘못되는 이유는 다음과 같이 볼 수 있음. count++ 문은 다음과 같이 기계어에서 구현되어있을 수 있음(일반적인 기계에서):

register_1 = count
register_1 = register_1 + 1
count = register_1

이때 register_1은 지역 CPU 레지스터 중 하나임. 마찬가지로 count--는 다음과 같이 구현되어있을 것임:

register_2 = count
register_2 = register_2 - 1
count = register_2

register_2도 마찬가지로 지역 CPU 레지스터. 당연히 register_1이랑 register_2가 서로 같은 물리적 레지스터일 수도 있지만, 이 레지스터의 내용물은 인터럽트 처리자에 의해 저장되고 복구될 것임(2.1.3 절).

"count++"와 "count--"를 동시에 실행한다면 위에서 보인 저수준 구문이 임의의 순서(당연히 고수준 구문의 순서는 보존이 됨)로 교차되어 실행이 된다는 뜻임. 예를 들어 다음과 같이 교차될 수 있음:

  1. T0: 생산자가 register_1 = count를 실행함 {register_1 = 5}
  2. T1: 생산자가 register_1 = register_1 + 1를 실행함 {register_1 = 6}
  3. T2: 소비자가 register_2 = count를 실행함 {register_2 = 5}
  4. T3: 소비자가 register_2 = register_2 - 1를 실행함 {register_2 = 4}
  5. T4: 생산자가 count = register_1를 실행함 {count = 6}
  6. T5: 생산자가 count = register_2를 실행함 {count = 4}

결과를 보면 알듯이 "count == 4"라는 잘못된 상태에 도달하게 되어 네 개의 버퍼가 차있다고 나옴. 실제로는 다섯 개가 차있는데. T4와 T5의 순서를 바꾸면 "count == 6"이 됨.

결과가 잘못 나온 이유는 프로세스가 변수 count를 동시에 접근하여 조작할 때, 이 실행의 결과가 접근이 발생하는 특정한 순서에 따라 달라지기 때문임. 이런 상황을 경합 조건 race condition이라 부름. 경합 조건을 막으려면 오로지 한 프로세스가 한 순간에 count를 조작할 수 있도록 보장해야함. 이걸 보장하려면 프로세스를 어떤 방법으로든 동기화를 해줘야 함.

방금 언급한 문제는 운영체제에서 시스템에 여러 다른 부분들이 자원을 조작하려 할 때 흔하게 발생함. 더 나아가 이전 단원에서 강조했듯 다중 코어 시스템이 중요해지면서 멀티스레드 어플리케이션 개발의 중요성이 더욱 커짐. 이런 어플리케이션에서는 데이터를 공유하고 있을 수도 있는 여러 스레드가 여러 프로세싱 코어에서 병렬로 돌고 있음. 당연히 이 스레드가 하는 활동에 의해 결과가 변해서 서로에게 영향을 주면 안 됨. 이게 정말 중요한 문제라서 이 단원의 대부분을 협업 프로세스 간의 프로세스 동기화 process synchronization와 협응 coordination에 대해 다룸.

6.2. 임계구역 문제

프로세스 동기화에 대한 내용은 우선 임계구역 문제에 대한 논의로 시작. n 개의 프로세스 {P0, …, Pn-1}으로 이루어진 시스템이 있다고 할 때, 각 프로세스는 임계구역 critical section이라 불리는 최소한 한 개의 프로세스와 공유 중인 자료에 접근하거나 갱신하는 코드의 한 부분을 갖고 있음. 이 시스템의 중요한 기능으로는 한 프로세스가 임계구역에서 실행 중이면, 다른 프로세스는 자신의 임계구역을 실행할 수 없음. 임계구역 문제 critical-section problem는 프로세스가 협업적으로 자료를 공유할 수 있도록 자신의 활동을 동기화하기 위한 프로토콜을 설계하기 위함임. 각 프로세스는 반드시 자신의 임계구역에 들어갈 때 허락을 맡아야 함. 이 요청을 구현한 코드 부분을 입장 구역 entry section이라 부름. 이후에 퇴장 구역 exit section이 나올 수도 있음. 나머지 부분을 나머지 구역 remainder section이라 부름. 일반적으로 프로세스는 아래 그림과 같은 일반적인 구조를 가짐. 입장 구역과 퇴장 구역은 박스로 둘러싸여 코드의 중요한 부분을 강조함.

임계구역 문제에 대한 해법은 반드시 다음 세 가지 요구를 만족해야 함:

  1. 상호 배제 mutual exclusion. 만약 프로세스 Pi가 자신의 임계구역을 실행 중이라면 다른 프로세스가 자기 임계구역을 실행해서는 안 됨.
  2. 진행 progress. 만약 아무 프로세스도 자신의 임계구역을 실행하고 있지 않을 때, 어떤 프로세스가 자신의 임계구역에 들어가려고 한다면, 오로지 자신의 나머지 구역을 실행하고 있지 않은 프로세스들끼리만 해서 누가 다음에 임계구역에 들어갈지를 결정하며, 이 선택은 무한정 미뤄질 수 없음.
  3. 한정 대기 bounded waiting. 어떤 한 프로세스가 임계구역에 들어가려는 요청을 하고, 그 요청이 수락이 되기 전까지 다른 프로세스가 자기 임계구역에 들어갈 수 있게 허락해주는 수에는 한계가 있음.

각 프로세스가 0이 아닌 속도로 실행 중이라고 가정. 허나 n 개의 프로세스 간의 상대적인 속도에 대해서는 어떠한 가정도 할 수 없음.

어떤 주어진 시간에서 많은 커널 모드 프로세스가 운영체제 내에서 활성화 상태일 수 있음. 결과적으로 운영체제를 구현한 코드(커널 코드 kernel code)는 여러 경합 조건의 대상이 됨. 예를 들어 현재 열려있는 파일의 목록을 관리하는 커널 자료 구조가 있음. 새 파일이 열리거나 닫히면 이 목록은 수정되어야 함. 두 프로세스가 동시에 파일을 열었다고 가정하면 이 목록에 두 번의 갱신이 일어날 수도 있어 경합 조건이 발생함.

다음 그림이 다른 예시. 두 프로세스 P0와 P1이 fork() 시스템 호출로 새 자식 프로세스 생성 중임. 3.3.1 절에서 언급했듯 fork() 함수는 새롭게 생성된 프로세스의 프로세스 식별자를 부모 프로세스에게 반환해줌. 이 예제에서는 다음에 사용 가능한 프로세스 식별자의 값을 의미하는 커널 변수 next_available_pid에 대해 경합 조건이 발생함. 상호 배제를 제공하지 않는 이상 같은 프로세스 식별자 숫자가 서로 다른 프로세스에게 할당될 수도 있음.

경합 조건에 취약한 다른 커널 자료구조로는 메모리 할당 관리, 프로세스 목록 관리, 인터럽트 처리할 때 사용하는 구조들이 있음. 운영체제가 이런 경합 조건 문제에서 자유롭게 만드는 것은 커널 개발자의 책임임.

단일 코어 환경에서는 임계구역 문제를 공유 변수를 처리하는 도중 인터럽트만 막으면 손쉽게 해결 가능. 그러면 현재 명령어 처리 도중에 선점될 일이 없을 것임. 그러므로 다른 명령어가 갑작스레 실행되어 공유 변수에 대해 예측하지 못한 수정사항이 일어나지 않을 것임.

운영체제에서 일반적으로 임계구역은 다음 두 가지 방법으로 처리: 선점적 커널 preemptive kernel과 비선점적 커널 nonpreemptive kernel. 선점적 커널은 커널 모드에서 프로세스가 실행 중에 선점이 될 수 있도록 허용하는 것. 비선점적은 그 반대. 커널 모드 프로세스는 커널 모드를 벗어나거나, 막히거나, 자의적으로 제어권을 CPU에 양보할 때까지 실행됨.

당연히 비선점적 커널에서의 커널 자료 구조는 경합 조건에서 자유로움. 한 번에 한 프로세스만이 활성화되어있으니. 그러므로 선점적 커널은 공유 커널 데이터가 경합 조건에 안 걸리게 신중하게 설계해야함. 특히 SMP 구조에서 설계하기 어려움. 이 환경에서는 두 커널 모드 프로세스가 동시에 서로 다른 CPU 코어에서 돌 수 있으니까.

그럼 왜 선점적 커널을 더 사용하는 것임? 선점적 커널에서는 커널 모드 프로세스가 다시 프로세서를 반환하고 대기 프로세스로 되기 전까지 상당히 긴 기간 동안 실행된다는 위험이 덜하기에 더 반응적임. (물론 이건 커널 코드가 이렇게 안 돌도록 애초에 설계를 하는 방법으로 줄일 수도 있음.) 게다가 선점적 커널은 실시간 프로세스가 현재 커널에서 실행 중인 프로세스를 선점할 수 있어 실시간 프로그래밍에 더욱 적합함.

6.3. 피터슨의 해법

다음으로는 피터슨의 해법 Peterson's solution이라 부르는 고전적인 소프트웨어 기반 임계구역 해법을 보도록 함. 현대적인 컴퓨터 구조에서 load와 store와 같은 기본적인 기계어 명령어를 수행하는 방법 때문에 피터슨의 해법이 제대로 작동하리란 보장은 없음. 여튼 그래도 알고리듬적으로 임계구역 문제를 해결하려고 하고, 상호 배제, 진행, 한정 대기에 대한 요구 사항을 다루는 소프트웨어를 설계하려는 좋은 시도였기 때문에 공부하는 것.

피터슨의 해법은 임계구역과 나머지 구역 간을 왔다 갔다하는 두 프로세스 간에만 대한 것임. 프로세스는 P0와 P1 둘로 구분. 편의상 Pi이라 할 때, 얘의 짝을 Pj라 표현할 것. j는 1 - i임.

피터슨의 해법을 하려면 두 프로세스 간 두 개의 데이터를 공유해야 함:

int turn;
boolean flag[2];

turn 변수는 누가 임계구역 들어갈 차례인가를 의미. 즉, turn == i면 Pi가 임계구역 들어갈 차례라는 것임. 이제 알고리듬 설명:

while (true) {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j) {
    	;
    }
    
    /* 임계구역 */
    
    flag[i] = false;
    
    /* 나머지 구역 */
}

우선 프로세스 Pi가 flag[i]를 true로 설정하고 turn의 값을 j로 두어 임계구역에 들어감. 즉, 다른 프로세스가 임계구역 들어가고 싶으면 그래도 된다는 것임. 둘 다 동시에 임계구역 들어가려고 하면 turn이 거의 같은 시간에 i와 j로 설정될 것임. 어차피 둘 중 하나만 유효하게 되고, 다른 하나는 다른 갚으로 덮어 쓰여질 것임. 결국 최종적으로 turn의 값에 의해 둘 중 누가 임계구역에 먼저 들어갈지 결정될 것.

이 해법이 옳음을 증명하려면 다음을 보여야 함:

  1. 상호 배제가 보존됨
  2. 진행 소요를 만족함
  3. 유한 대기 소요를 만족함

첫번째 속성 증명하려면 우선 각 Pi는 오로지 flag[j] == false이거나 turn == i일 때만 임계구역에 들어갈 수 있다는 점을 들면 됨. 또한 두 프로세스 둘 다 임계구역에 동시에 들어가려고 하면 flag[0] == flag[1] == true임. 즉, turn의 값이 0이면서 1일 수는 없고 둘 중 하나만 가능하므로 P0와 P1는 거의 동시에 while문을 성공적으로 실행하지 못했을 것임. 즉 둘 중 하나, 뭐 예를 들면 Pj가 성공적으로 while문을 실행시켰을 반면 Pi 최소한 한 번 추가적인 구문(turn == j)을 실행했어야 했을 것임. 반면에 그 순간 flag[j] == true이고 turn == j이므로 이 조건은 Pj가 임계구역에 있는 동안은 유지될 것이므로 상호 배제가 보존됨.

두번째와 세번째 속성 증명하려면 프로세스 Pi가 오로지 조건 flag[j] == true와 turn == j에 의해 while 루프 안에 꼈을 때만 임계구역에 못 들어간다는 점을 들면 됨. Pj가 아직 임계구역에 들어갈 준비가 안됐으면 flag[j] == false이므로 Pi가 임계구역에 들어갈 수 있음. Pj가 flag[j]를 true로 설정한 상태고 지금 while문에서 실행 중이면 turn == i이거나 turn == j라는 뜻임. 만약 전자면 Pi가 임계구역 들어갈 것이고, 후자면 Pj가 임계구역 들어갈 것임. 나중에 Pj가 임계구역 벗어나면 flag[j]를 다시 false로 초기화할 것이므로 Pi가 임계구역에 들어갈 수 있게 될 것임. Pj가 flag[j]를 true로 설정해주면 반드시 turn을 i로 설정해줘야함. 그러므로 Pi가 while문 실행 중엔 turn의 값을 바꿀 수 없으니 Pj가 최대 한 번 들어가면(유한 대기)Pi가 임계구역에 들어가게 됨(진행).

이 절 초반부에서 언급했듯이 요즘 컴퓨터 구조에서는 시스템 성능 개선 때문에 프로세서랑 컴파일러가 의존성이 없은 읽기 쓰기 연산을 재배치할 수도 있다는 점 때문에 피터슨의 해법이 제대로 작동할거란 보장이 없음. 단일 스레드 어플리케이션에서의 경우 프로그램의 올바른 실행을 문제 삼을 거 아니면 재배치한다고 문제될 것은 없음. 어차피 최종 결과는 예상 결과와 동일할 테니. (이는 마치 수표책 결산이랑 같음. 입출금의 실제 순서는 딱히 중요하지는 않으니까. 어차피 최종 금액은 같을 것임.) 하지만 공유 데이터를 갖는 멀티스레드 어플리케이션에서는 명령어 재배치에 의해 비일관적이거나 예측하지 못한 결과가 날 수도 있음.

예를 들어 다음 데이터가 두 스레드 간에 공유되고 있다고 가정:

boolean flag = false;
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을 출력할 수도 있음. 불확실하지만 프로세서가 스레드 1의 구문을 재배치하여 flag 값을 불러오기 전에 변수 x를 불러올 수도 있음. 이게 발생할 경우 스레드 2의 명령어의 재배치 여부와 무관하게 x 변수에 대해 0을 출력할 것임.

그래서 이게 어떻게 피터슨의 해법에 영향을 줌? 예를 들어 피터슨 해법에서 사용했던 예시의 입장 구역에 등장했던 두 할당문이 재배치되었다고 가정. 그러면 아래 그림에서처럼 두 스레드가 동시에 임계구역에 공존할 수도 있음.

다음 절에서 보겠지만, 상호 배제를 보존할 수 있는 유일한 방법은 제대로된 동기화 도구를 사용하는 것임. 이러한 도구를 논하는 것은 하드웨어에서 애초에 원시적으로 지원하는 것으로 시작해서 나중엔 커널 개발자와 어플리케이션 프로그래머가 사용 가능한 추상적인, 고수준의 소프트웨어 기반 API로 나아가야 함.

6.4. 동기화 하드웨어 지원

위에서는 임계구역 문제에 대한 소프트웨어 기반 해법을 제안했었음. (알고리듬이 운영체제로부터 특수한 지원을 받거나 특정 하드웨어 명령어가 상호 배제를 보장해주지 않기에 소프트웨어 기반 software-based 해법이라고 칭함.) 허나 위에서 보았듯 소프트웨어 기반은 요즘 컴퓨터에서는 제대로 안 돌 수도 있으므로 임계구역 문제를 해결하는데 도움을 줄 세 가지 하드웨어 명령어를 소개함. 이 원시적인 연산자들은 동기화 도구로 직접 사용할 수도 있고, 좀 더 추상적인 동기화 메커니즘의 기반으로 사용될 수도 있음.

6.4.1. 메모리 배리어

6.3 절에서 언급했듯 시스템이 명령어를 재배치하는 정책을 사용하여 자료의 상태의 신뢰성이 떨어지게 됨. 컴퓨터 구조에서 어플리케이션 프로그램에게 제공할 메모리 보장을 결정하는 방법을 메모리 모델 memory model이라 부름. 일반적으로 메모리 모델은 두 가지로 분류됨:

  1. 강정렬적 strongly ordered. 한 프로세서에서의 메모리 수정은 즉시 다른 프로세서에게 반영됨. 즉, 가시적임.
  2. 약정렬적 weakly ordered. 한 프로세서에서의 메모리 수정이 즉시 다른 프로세서에게 반영 안 될 수도 있음. 즉 가시적이지 않음.

메모리 모델은 프로세서 유형마다 다르므로 커널 개발자들 입장에서는 공유 메모리 다중 프로세서에서 메모리 수정 시 즉시 가시적이느냐를 확실하게 알 수 없음. 그렇기에 컴퓨터 구조는 메모리에 가해진 그 어떠한 수정 사항도 다른 프로세서에게 전달되도록 강제할 수 있는 명령어를 제공함. 이런 명령어를 메모리 배리어 memory barrier 혹은 메모리 울타리 memory fences라 부름. 메모리 배리어 명령어가 실행되면 시스템이 모든 불러오기와 저장하기가 다음 불러오기 혹은 저장하기 연산 수행 되기 전에 완료되었음을 보장함. 이렇게 되면 명령어를 재배치하더라도 메모리 배리어에 의해 저장 연산이 메모리에 적용이 되어 나중에 불러오기나 저장을 하더라도 수정 사항이 다른 프로세서에게도 즉시 반영이 되도록 할 수 있음.

마지막에 언급했던 명령어 재배치에 의해 문제 생겼던 예시로 다시. 여기에 메모리 배리어 사용해서 예상된 결과 얻기.

스레드 1에 메모리 배리어 연산 추가:

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

이러면 flag의 값이 x 값 이전에 반드시 불러와진다는 것을 보장할 수 있음.

마찬가지로 스레드 2에도 할당 사이에 메모리 배리어 추가해줄 수 있음.

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

이러면 x의 할당이 flag 할당보다 먼저 수행됨이 보장됨.

피터슨의 해법의 경우 입장 구역의 처음 두 할당 사이에 메모리 배리어 추가해주면 위에 그림에서 봤던 재배치 문제를 해결할 수 있음. 참고로 메모리 배리어는 상당히 저수준 연산 축에 끼므로 사실상 거의 커널 개발자들이 상호 배제를 보장하는 특수 코드를 작성할 때만 사용함.

6.4.2. 하드웨어 명령어

대부분의 요즘 컴퓨터 시스템에서는 원자적으로 atomically 워드의 내용물을 테스트하고 수정해줄 수 있게 하거나 두 워드 간의 내용물을 스왑해줄 수 있게 하는 특수한 하드웨어 명령어를 제공함. 이 특수한 명령어로 상대적으로 간단하게 임계구역 문제 해결 가능. 특정 기계에서의 특정 명령어 하나 하나 언급하지 말고, 이런 명령어들을 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() 명령어를 지원하면 불리언 변수 lock를 선언하여 false로 초기화해주어 상호 배제 구현 가능함. 프로세스 Pi의 구조는 다음과 같을 것임:

do {
    while (test_and_set(&lock)) {
    	; /* 아무것도 하지 않음 */
    }
    
    /* 임계 구역 */
    
    lock = false;
    
    /* 나머지 구역 */
} while (true);

compare_and_swap() 명령어(CAS)는 test_and_set() 명령어처럼 두 워드 간에 원자적으로 처리되지만 두 워드의 내용물을 스왑한다는 다른 메커니즘을 사용함.

CAS 명령어는 다음과 같이 정의된 세 가지 연산자를 기반으로 처리됨:

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

오로지 표현식 (*value == expected)이 true일 때만 피연산자 value를 new_value로 설정해줌. 여튼 CAS는 언제나 value의 원본 값을 반환함. 중요한 건 원자적으로 실행되므로 두 CAS가 동시에 (서로 다른 코어에서) 실행되더라도 임의의 순서로 순차적으로 실행된다는 것임.

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

while (true) {
    while (compare_and_swap(&lock. 0, 1) != 0) {
    	; /* 아무 것도 하지 않음 */
    }
    
    /* 임계구역 */
    
    lock = 0;
    
    /* 나머지 구역 */
}

전역 변수(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;
    
    /* 임계구역 */
    
    j = (i + 1) % n;
    while ((j != i) && !waiting[j]) {
    	 j = (j + 1) % n;
    }
    
    if (j == i) {
    	lock = 0;
    } else {
    	waiting[j] = false;
    }
    
    /* 나머지 구역 */
}

공통 자료 구조는 다음과 같음:

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가 되어 상호 배제 조건을 만족함.

진행 조건이 만족함을 보이려면 상호 배제에서 봤던 거랑 똑같음. 임계구역을 탈출하는 프로세스가 lock을 0으로 설정해주거나 waiting[j]를 false로 설정해줄 것임. 둘 다 대기 중이던 한 프로세스를 임계구역에 입장할 수 있게 해줌.

한정 대기 조건 만족하는지 보려면 프로세스가 임계구역 탈출할 때 waiting 배열을 순환 순서(i + 1, i + 2, …, n - 1, 0, …, i - 1)로 쭉 훑음. 이 순서에서 가장 처음으로 입장 구역에 있는 프로세스(waiting[j] = true)를 다음으로 임계구역에 들어갈 프로세스로 지정해줌. 임계구역 들어가려고 대기하는 모든 프로세스는 n - 1 번 내로 될 것임.

test_and_set()과 compare_and_swap() 원자적 명령어를 구현하는 세부사항은 컴퓨터 구조 책에서 좀 더 세부적으로 다룸.

6.4.3. 원자적 변수

보통 compare_and_swap() 명령어는 직접 상호 배제를 제공할 때 사용하지는 않고, 대신 임계구역 문제를 해결하는데 사용되는 다른 도구들을 위한 기본 재료로 사용되는 편임. 그런 도구 중 하나가 바로 원자적 변수 atomic variable로, 정수, 불리언과 같은 기본 자료형에 원자적 연산을 제공함. 6.1 절에서 보았듯 정수값 증감하면 경합 조건이 발생할 수도 있었음. 이런 것처럼 한 변수가 카운팅되는 것처럼 그 값이 갱신 중일 때 자료 간 경합이 발생할 수 있는 상황에서 상호 배제를 보장해줄 때 원자적 변수를 사용해주면 됨.

원자적 변수를 지원하는 대부분의 시스템은 특수한 원자적 자료형과 원자적 변수에 접근하고 조작하는 함수도 제공함. 이런 함수들은 보통 compare_and_swap() 연산으로 구현함. 예를 들어 다음 함수는 원자적 정수열을 증가시킴:

increment(&sequence);

여기서 increment() 함수는 CAS 명령어로 구현함:

void increment(atomic_int* v)
{
    int temp;
    
    do {
    	temp = *v;
    } while (temp != compare_and_swap(v, temp, temp + 1));
}

원자적 변수가 원자적 갱신을 제공하기는 하는데, 이게 모든 상황에서 경합 조건을 해결해주지는 않음. 예를 들어 6.1 절에서의 유한 버퍼 문제에서 count에 원자적 정수를 사용할 수는 있음. 그러면 count의 갱신이 원자적임을 보장할 수는 있음. 하지만 생산자와 소비자에는 count의 값에 의존하는 조건을 갖는 while 루프를 가짐. 만약 버퍼가 현재 비어있고, 두 소비자가 count > 0 조건을 대기하며 반복문을 돌리고 있다고 가정. 이때 생산자가 버퍼에 한 원소를 넣으면 count의 값이 겨우 1이 되었을 뿐인데 두 소비자 동시에 while문을 벗어나(count가 이제 0과 같지 않으니) 소비를 시작할 수도 있음.

원자적 변수는 운영체제 뿐만 아니라 동시적 어플리케이션에서 흔히들 사용하기는 하는데, 사실상 카운터나 시퀀스 생성기와 같은 공유 데이터의 단일 갱신에서만 사용함. 다음 절에서는 좀 더 일반적인 상황에서 경합 조건을 다루는 더 강력한 도구를 다룸.

비교 후 스왑 원자적으로 만들기

인텔 x86 구조에서 어셈블리어문 cmpxchg로 compare_and_swap() 명령어 구현함. 원자적 실행을 강제하려면 lock 접두사를 사용하여 수신지 피연산자가 갱신 중일 때 버스를 고정할 수 있음. 일반적으로 이 연산은 다음과 같이 생김:
lock cmpxchg <수신지 피연산자>, <송신지 피연산자>

6.5. 상호배제 락

위에서 언급한 하드웨어 기반의 임계구역 문제 해결방법은 복잡할 뿐만 아니라 일반적으로 어플리케이션 프로그래머들은 접근할 수 없음. 대신 운영체제 설계자가 임계구역 문제를 해결해줄 수 있는 고수준 소프트웨어 도구를 만듦. 가장 간단한 도구가 바로 상호배제 락 mutex lock임. (사실 상호배제 mutex라는 말은 상호 배제 mutual exclusion이라는 말임.) 상호배제 락으로 임계구역을 보호하여 경합 조건을 방지함. 즉, 프로세스는 임계구역에 들어가기 전에 반드시 락을 얻어야 임계구역에 들어갈 수 있고, 나갈 땐 락을 반납하고 나가야 함. 아래 그림에서처럼 acquire() 함수로 락을 얻고, release() 함수로 반납한.

상호배제 락에는 available이라는 불리언 변수가 있어 락이 사용 가능한지 여부를 알 수 있음. 지금 사용할 수 있으면 acquire() 호출이 성공하여 이제 락은 사용할 수 없게 됨(역자: 내가 쓰고 있으니까 ㅎㅎ). 사용자가 반납할 때까지 다른 프로세스가 락 받으려는 시도가 막힘.

acquire()는 다음과 같이 정의함:

acquire()
{
    while (!available) {
    	; /* 바쁜 대기 중 */
    }
    available = false;
}

release()는 다음과 같이 정의함:

release()
{
    available = true;
}

둘 다 원자적으로 호출됨. 그러므로 상호배제 락은 위 절에서 언급한 CAS 연산으로 구현 가능함. 이건 직접 해보셈.

이렇게 구현했을 때의 최대 단점은 바로 바쁜 대기 busy waiting이 존재한다는 점임. 어떤 프로세스가 임계구역에 이미 들어가있으면 다른 프로세스는 반드시 acquire()을 얻기 위해 계속해서 루프를 돌려야 함. 이렇게 계속 루프 돌리는 거 당연히 프로세스 간 하나의 CPU 코어를 공유하는 다중 프로그래밍 시스템에서 문제가 됨. 게다가 다른 프로세스가 좀 더 생산적인 일에 사용할 수도 있는 CPU 사이클을 바쁜 대기하는데 낭비하는 꼴이 됨. (6.6 절에서 임시로 대기 중인 프로세스를 재우고, 락이 사용 가능해지면 깨우는 전략을 살펴볼 것.)

여기서 다룬 상호배제 락은 락이 사용 가능할 때까지 "돌린다 spin"는 점에서 스핀락 spinlock이라 부름. (위에서 compare_and_swap() 명령어 예시 보여줬던 곳에서도 똑같은 문제 발생함.) 스핀락도 당연히 장점은 있음. 프로세스가 락을 대기할 때 문맥 교환이 일어날 필요가 없음(문맥 교환 시간 오래 걸리니까). 다중 코어 시스템에서 특정 상황에서는 락을 걸 때 스핀락이 제일 선호하는 방법일 때도 있음. 락이 짧은 기간 동안만 걸려야할 때는 한 스레드가 한 프로세싱 코어에서 "도는" 동안 다른 스레드가 다른 코어에서 임계구역에서 실행 중일 것임. 요즘 다중 코어 컴퓨팅 시스템에서 대부분의 운영체제는 스핀락 널리 사용 중임.

7 단원에서는 상호배제 락을 통해 고전적인 동기화 문제를 해결하는 법을 볼 것임. 또한 여러 운영체제와 Pthread에서 상호배제 락과 스핀락이 어떻게 사용되는지 볼 것.

락 경합

락은 경합을 해줄 수도, 안 해줄 수도 있음. 스레드가 락을 가지려고 할 때 막힌다면 락은 경합 중 contended이라 할 수 있고, 얻는다면 비경합 중 uncontended이라 함. 경합 중인 락은 고수준 경합 high contention(상대적으로 많은 수의 스레드가 락을 얻으려고 시도 중)이나 저수준 경합 low contention(상대적으로 적은 수의 스레드가 락을 얻으려고 시도 중) 둘로 구분 가능함. 당연하겠지만 고수준 경합 중인 락들이 동시적 어플리케이션의 전체적인 성능을 낮춤.

"짧은 기간"이란 무슨 의미?

스핀락은 보통 다중 프로세스 시스템에서 락이 짧은 기간 동안만 사용될 때 사용하는 라킹 메커니즘으로 여겨짐. 아니 그래서 얼만큼 짧아야 짧은 기간임? 락을 대기할 때 두 문맥 교환(스레드를 대기 상태로 옮기는 문맥 교환과 락이 사용 가능해졌을 때 대기 스레드를 복구하는 문맥 교환)가 필요하다는 점에서 일반적으로 스핀락이 최소 두 문맥 교환 내만큼 사용할 락에서 스핀락을 사용.

6.6. 세마포어

상호배제 락은 위에서 언급했듯이 일반적으로 가장 간단하다고 불리는 동기화 도구임. 이 절에서는 상호배제 락과 비슷하게 작동하면서도 프로세스를 좀 더 복잡하게 동기화할 수 있도록 해주는 방법도 제공하는 강력한 도구 공부.

세마포어 semophore S는 정수 변수로, 초기화할 때 말고는 오로지 두 가지 표준 원자적 연산 wait()과 signal()로만 접근 가능. 세마포어는 네덜란드 컴퓨터 과학자 에츠허르 다익스트라가 처음 소개한 개념으로, wait() 연산도 원래 네덜란드어로 "테스트하다"를 의미하는 proberen에 따서 P로 불렀었고, signal()은 "증가하다"라는 의미의 verhogen에서 따서 V로 불렀음. wait()은 다음과 같이 정의:

wait(S)
{
    while (S <= 0) {
    	; /* 바쁜 대기 */
    }
    S--;
}

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

signal(S)
{
    S++;
}

세마포어라는 정수 값을 수정하려면 wait()이나 signal() 연산을 원자적으로 실행해야 함. 즉, 만약 한 프로세스가 세마포어 값을 수정하면, 그 어떠한 다른 프로세스도 동시에 같은 세마포어 값을 수정할 수 없음. 추가적으로 wait(S)의 경우 정수값 S(S ≤ 0) 테스트하는 것과 마찬가지로 가능한 모든 수정사항들(S--)도 반드시 인터럽트 없이 실행이 되어야 함. 이런 연산을 어떻게 구현하는지 6.6.2 절에서 볼 것임. 우선 세마포어가 어떻게 사용될 수 있는지 볼 것.

6.6.1. 세마포어 용법

운영체제는 보통 카운팅과 이진 세마포어를 구분해서 봄. 카운팅 세마포어 counting semaphore의 값에는 한계가 없음. 이진 세마포어 binary semphore의 값은 오로지 0이거나 1임. 이진 세마포어는 상호배제 락과 비슷함. 사실 상호배제 락을 제공하지 않는 체제에서는 이진 세마포어로 상호배제를 제공함.

카운팅 세마포어로 한정된 개수의 개체로 구성된 자원에 접근을 제어할 수 있음. 세마포어는 몇 개의 자원으로 초기화가 됨. 자원을 쓰려는 각 프로세스는 세마포어에 대해 wait() 연산을 해주어야 함(즉, 카운트를 감소함). 프로세스가 자원을 반납하면 signal() 연산을 수행함(카운트를 증가함). 세마포어의 카운트가 0이 되면 모든 자원이 사용된 것임. 이후에 프로세스가 자원을 사용하려고 하면 카운트가 0보다 커질 때까지 막힐 것임.

세마포어로 여러 동기화 문제 해결할 수 있음. 예를 들어 동시에 실행 중인 프로세스가 있다고 할 때, P1는 구문 S1를 갖고, P2는 구문 S2를 갖는다고 가정. 또한 S2가 반드시 S1가 완료되야만 실행이 가능하다고 가정. 이땐 P1과 P2가 공통된 공유 세마포어 synch를 공유하고, 0으로 초기화되었다고 가정. 프로세스 P1에 다음 구문을 추가:

S_1;
signal(synch);

프로세스 P2에는 다음 구문 추가:

wait(synch);
S_2;

synch가 0으로 초기화되었기 때문에 P2 입장에서는 P1이 signal(synch)를 호출해야만 S2를 실행할 수 있으므로, S1은 완료가 된 상태일 것임.

6.6.2. 세마포어 구현

6.5 절에서 상호배제 락을 구현했을 때 바쁜 대기라는 문제가 있었었음. 위에서 정의했던 wait()과 signal() 세마포어 연산은 똑같은 문제 그대로 있음. 이걸 해결하려면 정의를 수정해야함: 프로세스가 wait() 연산을 실행할 때, 세마포어 값이 양수가 아니면, 대기해야함. 이때 바쁜 대기를 하는게 아니라, 프로세스가 스스로를 중지시킴. 이때 중지 연산은 프로세스를 세마포어에 대한 대기 큐로 보내어 프로세스의 상태를 대기 상태로 바꾼다는 뜻임. 그럼 제어권이 CPU 스케줄러로 넘어가서 실행할 다른 프로세스를 선택하게 될 것임.

중단된 프로세스는 세마포어 S를 대기하므로 다른 프로세스가 signal() 연산을 실행할 때 재시작되어야함. 프로세스는 wakeup() 연산에 의해 재시작되어 프로세스를 대기 상태에서 준비 상태로 바꿔줌. 그럼 프로세스가 준비 큐로 올라가게 됨. (CPU가 실행 중인 프로세스에서 준비 상태로 된 프로세스로 교환해줄 수도, 아닐 수도 있음. 이건 CPU 스케줄링 알고리듬에 따라 다름.)

이 정의에 따라 세마포어를 재정의:

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

각 세마포어는 정수 값과 프로세스의 목록 list를 갖고 있음. 프로세스가 어떤 한 세마포어에 대해서 대기해야한다면 해당 프로세스를 목록에 추가해줌. signal() 연산이 대기 중인 프로세스에서 한 프로세스를 제거하여 깨워줌.

wait() 연산은 다음과 같이 정의:

wait(semaphore* S)
{
    S->value--;
    if (S->value < 0) {
    	이 프로세스를 S->list에 추가;
        sleep();
    }
}

signal() 세마포어 연산은 다음과 같이 정의:

signal(semphore* S)
{
    S->value++;
    if (S->value <= 0) {
    	프로세스 P를 S->list에서 제거;
        wakeup(P);
    }
}

sleep() 연산은 자기를 호출한 프로세스를 중단시킴. wakeup(P) 연산은 중단된 프로세스 P의 실행을 재개해줌. 이 두 연산은 운영체제에서 기본 시스템 호출로 제공됨.

이 구현법에서는 세마포어 값이 음수일 수도 있음. 바쁜 대기가 있던 세마포어의 고전적인 정의에서는 세마포어 값이 절대 음수가 될 수 없었음. 세마포어 값이 음수면 그 절대값이 해당 세마포어에 대기 중인 프로세스의 개수임. 이건 감소의 순서와 wait() 연산 구현 내의 테스트의 순서를 바꾸면 알 수 있음.

대기 중인 프로세스 목록은 프로세스 제어 블록(PCB)으로 이루어진 연결장(역자: link field)으로 쉽게 구현할 수 있음. 각 세마포어는 정수값과 PCB의 목록을 가리키는 포인터로 구성되어있음. 한정 대기를 보장하는 목록에서 프로세스 추가/삭제하는 방법 중 하나로는 선입선출 큐를 사용하여 세마포어가 큐에 대한 머리 포인터와 꼬리 포인터를 둘 다 가지면 됨. 일반적으로 목록은 아무 큐 전략을 사용해도 되긴 함. 세마포어의 올바른 용법은 세마포어 목록이 어떤 큐 전략을 사용하든 영향을 받지 않음.

위에서 언급했듯 세마포어 연산은 원자적으로 실행이 되어야 함. 그 어떠한 두 프로세스도 같은 세마포어에 대해 wait()과 signal() 연산을 동시에 실행해서는 안 됨. 이건 임계구역 문제임. 단일 프로세서 환경에선 이걸 단순히 wait()이나 signal() 연산을 실행 중일 때 인터럽트를 막아주면 해결이 가능함. 단일 프로세서 환경에서는 인터럽트만 없으면 다른 프로세스의 명령어가 교차되어 실행될리가 없으니까. 현재 실행 중인 프로세스만 다시 인터럽트가 활성화되어 스케줄러가 다시 제어권을 얻기 전까지 실행될 것임.

다중 코어 환경에서는 인터럽트를 모든 프로세싱 코어에서 비활성화해줘야함. 안 그러면 다른 프로세스(다른 코어에서 동작하는)의 명령어가 임의의 순서로 교차되어 실행될 수도 있음. 모든 코어에서 인터럽트를 비활성화하는 건 어려울 뿐만 아니라 성능을 엄청 깎아 먹음. 그러므로 SMP 체제에서는 반드시 compare_and_swap()이나 스핀락 같은 다른 기법을 통해 wait()과 signal()이 원자적으로 실행되도록 보장해야 함.

이렇게 정의하더라도 wait()과 signal()에서 바쁜 대기가 아예 사라진 것은 아님. 사실상 바쁜 대기를 어플리케이션의 입장 구역에서 임계구역으로 옮겼을 뿐임. 게다가 wait()과 signal() 연산의 임계구역에서 바쁜 대기를 하도록 범위가 한정되었을 뿐이며, 이 구역은 보통 짧음(제대로 짰다면, 최소 10 개의 명령어를 넘어서는 안 됨). 그러므로 임계구역은 사실성 거의 차지될 일이 없으며, 바쁜 대기도 거의 안 일어나며, 일어나도 짧은 기간 동안만 일어남. 임계구역이 길거나 (몇 분, 혹은 심지어 몇 시간) 언제나 차지되어야 하는 어플리케이션의 경우 완전히 다른 상황임. 이 경우 바쁜 대기는 상당히 비효율적임.

6.7. 모니터

세마포어가 간편하고 효과적인 프로세스 동기화 메커니즘을 제공하긴 했지만, 제대로 사용하지 않으면 검출하기 어려운 타이밍 오류가 발생함. 이런 오류는 오로지 특정 실행 순서에만 발생하며, 이게 언제나 발생하지 않기 때문에 어려움.

이러한 오류를 생산자-소비자 문제(6.1 절)에서 카운트를 사용했을 때 확인할 수 있었음. 이 예시에서는 타이밍 문제가 상당히 희귀한 확률로 발생하며, 심지어 발생하더라도 count 값이 1 만큼 적기에 충분히 합리적인 값처럼 보임. 그렇더라도 여튼 답은 아니니까. 그렇기에 상호배제 락과 세마포어를 애초에 제안한 것임.

물론, 상호배제 락이나 세마포어를 사용해도 타이밍 오류는 발생할 수 있음. 어떻게 일어나는지 보려면 임계구역 문제에서 사용했던 세마포어 해법을 다시 봐야 함. 모든 프로세스가 1로 초기화된 이진 세마포어 변수 mutex를 공유함. 각 프로세스는 임계구역에 들어가기 전 반드시 wait(mutex)를 실행하고, 그 후에는 signal(mutex)를 호출해야 함. 이 순서가 지켜지지 않으면 두 프로세스가 동시에 임계구역에 존재할 수도 있음. 여기서 발생하는 몇 가지 문제를 보도록 하자. 이 문제들은 단 하나의 프로세스가 제대로 작동하지 않더라도 발생함. 이러한 상황은 너무나도 정직한 프로그래밍 오류나 협력하지 않는 프로그래머에 의해 발생할 수도 있음.

  • 프로그램이 세마포어 mutex에 대한 wait()과 signal() 연산이 실행되는 순서를 바꿔주어 다음과 같이 순서가 바뀌었다고 가정:
    signal(mutex);
    
...
    
임계 구역
    
...
    
wait(mutex);

    이 상황에서는 여러 프로세스가 동시에 임계구역에서 실행 중일 수도 있어 상호 배제 조건을 위배함. 이 오류는 오로지 여러 프로세스가 동시에 임계구역에 있어야만 찾을 수 있음. 이 상황이 언제나 재현 가능한 것도 아님.
  • 프로그램이 signal(mutex)를 wait(mutex)로 바꿔줬다고 가정:
    wait(mutex);
    
...
    
임계 구역
    
...
    
wait(mutex);

    이 경우 프로세스는 wait()에 대한 두 번째 호출을 영구히 막아버려 세마포어를 더 이상 사용할 수 없게됨.
  • 프로세스가 wait(mutex)나 signal(mutex), 혹은 둘 다 생략해버렸다면 상호 배제 조건을 만족하지 못하거나, 프로세스가 영구히 막히게 됨.

이러한 여러 가지 오류들은 프로그래머가 세마포어나 상호배제 락을 올바르지 않게 사용했을 때 손쉽게 겪을 수 있는 오류들. 이런 오류를 처리하는 전략 중 한 가지는 간단한 동기화 도구를 고수준 언어에 포함시키는 것. 그 중 하나가 이 절에서 다룰 모니터 monitor라는 근본적인 고수준 동기화 기능임.

6.7.1. 모니터 용법

추상 자료형 abstract data type 혹은 ADT는 캡슐화된 자료와, 이에 대해 ADT의 구체적인 구현에 독립적인 자료에 대한 함수 집합을 제공함. 모니터형 monitor type이란 모니터 내에서 상호배제를 지원하는 프로그래머가 정의한 연산을 갖는 ADT. 모니터형은 해당 형의 개체의 상태를 의미하는 값을 정의하는 변수와, 이 변수에 대한 함수를 갖고 있음. 모니터형 문법은 다음 그림과 같음. 모니터형은 여러 프로세스에 의해 직접 사용될 수 없음. 그러므로 모니터 내에서 정의된 함수는 모니터와 그 매개변수들이 속한 지역에서 선언된 변수들만 접근할 수 있음. 마찬가지로 모니터의 지역 변수는 오로지 지역 함수에 의해서만 접근이 가능함.

monitor 모니터 이름
{
    /* 공유 변수 선언 */
    function P_1(...)
    {
    	...
    }
    
    function P_2(...)
    {
    	...
    }
    
    .
    .
    .
    
    
    function P_n(...)
    {
    	...
    }
    
    initialization_code(...)
    {
    	...
    }
}

모니터 생성은 한 순간에 모니터 내에서 단 하나의 프로세스만 활성화 되어있음을 보장함. 결과적으로 프로그래머는 명시적으로 동기화 문제를 처리해줄 필요가 없게 됨. 그러나 모니터 생성은 지금까지 공부한 걸로 봤을 땐 몇가지 동시성 스킴에 적용하기엔 충분히 강력하지는 않음. 그렇기에 추가적인 동기화 메커니즘이 필요함. 이 메커니즘은 condition 생성이 제공함. 수제 동기화 스킴을 작성해야 하는 프로그래머의 경우 조건 condition 형 변수 하나 이상을 정의해야 함:

condition x, y;

조건 변수가 호출할 수 있는 유일한 연산은 wait()과 signal()임.

연산

x.wait();

은 이 연산을 호출하는 프로세스는 다른 프로세스가

x.signal();

을 호출하기 전까지 중단된다는 의미.

x.signal() 연산은 정확히 하나의 중단된 프로세스를 재개해줌. 중단된 프로세스가 없으면 signal() 연산은 아무런 영향도 주지 않으므로 x의 상태는 연산이 아예 일어나지 않았던 것과 동일하게 바뀌지 않음(아래 그림 참고). 이에 반해 세마포어에 대한 signal() 연산은 언제나 세마포어의 상태에 영향을 주었었음.

x.signal() 연산이 프로세스 Pi에 의해 호출이 되었다고 하면 조건 x에 대해 중단 되었던 프로세스 Q가 존재할 것임. 당연히 이 중단된 프로세스 Q는 실행을 재개할 수 있으며, 신호를 보내는 프로세스 P는 반드시 대기해야함. 이게 안 되면 P랑 Q 둘 다 동시에 모니터에서 활성화되버릴 것임. 그러나 개념적으로 두 프로세스 다 실행을 지속할 수 있음. 두 가지 가능성 존재:

  1. 신호 후 대기 signal and wait. P가 Q가 모니터를 벗어나거나 다른 조건을 대기할 때까지 대기.
  2. 신후 후 지속 signal and continue. Q는 P가 모니터를 벗어나거나 다른 조건을 기다릴 때까지 대기.

둘 중 어떤 방법을 택하느냐는 논쟁거리임. 한쪽에서는 P가 이미 모니터에서 실행 중이므로 신호 후 지속 signal-and-contintue가 좀 더 합리적이라고 하고, 다른 쪽에서는 스레드 P가 지속할 수 있게 해주면 Q가 재개될 때 즈음에 Q가 대기하던 논리 조건이 더 이상 참이 아니게 되버릴 수 있다고 함. 이 두 선택지의 절충안도 있긴 있음: 스레드 P가 신호 연산을 수행하고, 즉시 모니터를 벗어나여 Q가 즉시 재개되도록 해줌.

자바, C#과 같은 수많은 언어는 이 절에서 언급한 모니터의 개념을 제공함. Erlang과 같은 다른 언어에서는 비슷한 메커니즘으로 동시성 제공.

6.7.2. 세마포어로 모니터 구현하기

이제 모니터를 세마포어를 통해 구현. 각 모니터마다 이진 세마포어 mutex(1로 초기화)를 두어 상호 배제 보장. 프로세스는 모니터에 들어가기 전에 반드시 wait(mutex)를 실행해야 하고, 모니터 나갈 때 반드시 signal(mutex)를 호출해야 함.

신호 후 대기 스킴을 사용할 것임. 송신 프로세스가 반드시 재개된 프로세스가 떠나거나 대기할 때까지 대기해야하기 때문에 추가적인 이진 세마포어 next(0으로 초기화)가 필요함. 송신 프로세스는 next를 사용하여 자기 스스로를 중단시킬 수 있음. 정수형 변수 next_count로 next에서 중단된 프로세스의 개수를 얻을 수 있음. 즉, 각 외부 함수 F는 다음으로 교체:

wait(mutex);
...
F의 본문
...
if (next_count > 0) {
    signal(next);
} else {
    signal(mutex);
}

이러면 모니터 내의 상호 배제가 보장됨.

이제 드디어 조건 변수를 어떻게 구현하는지. 각 조건 x마다 이진 세마포어 x_sem과 정수형 변수 x_count를 두고 둘 다 0으로 초기화. x.wait() 연산을 다음과 같이 정의:

++x_count;
if (next_count > 0) {
   signal(next);
} else {
   signal(mutex);
}
wait(x_sem);
--x_count;

x.signal() 연산은 다음과 같이 구현:

if (x_count > 0) {
    ++next_count;
    signal(x_sem);
    wait(next);
    --next_count;
}

이 구현은 Hoare와 Brinch-Hansen의 모니터의 정의에 적합함. 물론 몇몇 경우에서는 이 구현의 일반성이 불필요하여 효율성을 좀 더 개선할 수 있긴 함. 직접 해보셈.

6.7.3. 모니터 내에서 프로세스 재개하기

이제 모니터 내에서 프로세스 재개 순서 다룰 것. 여러 프로세스가 조건 x에 대해 중단되어 있고, 어떤 한 프로세스가 x.signal()을 호출한다면, 그래서 어떤 중단된 프로세스를 실행할지를 어떻게 셜정? 한가지 간단한 해결방법은 그냥 선도착 선처리(FCFS) 순서로 처리하여 가장 오랫동안 대기한 프로세스를 우선적으로 재개해주면 됨. 대부분의 경우 이런 단순한 스케줄링 스킴은 충분하지 않기 때문에 조건적 대기 conditional wait 생성을 사용해줘야 함. 이 생성은 다음과 같이 생김:

x.wait(c);

여기서 c는 wait() 연산이 실행될 때 평가되는 정수형 표현식임. c의 값은 우선순위 숫자 priority number라고도 부르는데, 중단된 프로세스에 이름에 저장해줌. x.signal()을 실행할 때 가장 작은 우선순위 숫자를 갖는 프로세스를 다음으로 재개해줌.

monitor ResourceAllocator
{
    boolean busy;
    condition x;
    
    void acquire(int time)
    {
        if (busy) {
            x.wait(time);
        }
        busy = true;
        x.signal();
    }
    
    void release(int time)
    {
        busy = false;
        x.signal();
    }
    
    initialization_code()
    {
    	busy = false;
    }
}

이 새로운 메커니즘을 이해하려면 위의 코드에서의 ResourceAllocator 모니터를 이해해야 함. ResourceAllocator는 하나의 자원에 대해 경쟁 중인 프로세스 간에 자원 할당을 제어함. 각 프로세스는 자원 할당을 요청할 때 해당 자원을 사용할 최대 시간을 명시해줌. 모니터는 자원을 가장 기간이 짧은 할당 요청을 보낸 프로세스에 할당해줌. 여기서 자원에 접근해야하는 프로세스는 다음 순서를 지켜야 함:

R.acquire(t);
...
access the resource;
...
R.release();

여기서 R은 ResourceAllocator형 개체임.

아쉽게도 모니터 개념은 직전 접근 순서가 지켜질거란 보장은 없음. 특히 다음 문제가 발생함:

  • 프로세스가 자원에 대한 권한 없이도 자원에 접근할 수도 있음
  • 프로세스가 자원에 접근 권한 얻은 후 다시 그 자원을 반환 안 해줄 수도 있음
  • 프로세스가 요청하지도 않은 자원을 반환할 수도 있음.
  • 프로세스가 같은 자원을 두 번 요청(처음 걸 반환하지도 않고)할 수도 있음.

세마포어를 사용해도 같은 문제 발생하고, 이 문제는 애초에 모니터 생성을 개발하게 된 이유와도 결국 같음. 이전엔 세마포어 제대로 사용했나를 고민했지만 이제는 고수준 프로그래머가 정의한 연산을 제대로 사용했냐까지 고민해야하므로 더 이상 컴파일러가 도와주지도 못 함.

프로세스가 적합한 순서를 지킴을 보장하려면 반드시 모든 프로그램이 ResourceAllocator 모니터와 이 모니터가 관리하는 자원을 사용하는 모든 프로그램을 검사해야함. 우선 사용자 프로세스는 언제나 모니터에서 올바른 순서로 호출을 해야 함. 두번째로 비협력적인 프로세스가 단순히 모니터가 제공한 상호배제의 관문을 무시하고 접근 프로토콜 사용하지 않고 직접 공유 자원에 접근하지 못하도록 보장해야 함. 이 두 가지 조건이 만족되어야만 시간 의존적 오류가 발생하지 않아 스케줄링 알고리듬이 패배하지 않는 다는 것을 보장할 수 있음.

이걸 검사하는게 작고 정적인 시스템에서는 가능할지라도 크거나 동적인 시스템에서는 합리적이지 않음. 이 접근 제어 문제는 17 단원에서 다룰 추가적인 메커니즘이 나와야만 해결 가능함.

6.8. 라이브니스

동기화 도구로 임계구역으로의 접근을 조정하게 되면 프로세스가 무한정 임계구역에 입장하기를 대기하게 되는 문제가 발생할 수도 있음. 6.2 절에서 임계구역 문제가 반드시 만족해야 하는 세 가지 기준을 논했음. 무한정 대기하는 문제의 경우 진행과 한정 대기 두 가지 기준을 위배하게 됨.

라이브니스 liveness란 프로세스가 실행 수명 주기에서 제대로 진행이 되도록 시스템이 보장하는 속성을 의미함. 위에서 언급한 프로세스가 무한정 대기하는 문제가 "라이브니스 실패 liveness failure"의 한 예시임.

라이브니스 실패에는 여러 형태가 있지만, 전부 공통적으로 일반적으로 나쁜 성능과 반응성이라는 특징을 가짐. 가장 간단한 라이브니스 실패 예시는 무한 루프임. 바쁜 대기가 바로 라이브니스 실패가 발생할 수도 있는 가능성을 갖고 있음. 특히 프로세스가 임의의 긴 기간 만큼 루프할 수도 있을 때 그럼. 상호배제 락이나 세마포어와 같은 도구로 상호배제를 제공하려고 시도하면 동시성 프로그래밍에서 위와 같은 실패가 발생하곤 함. 이 절에서는 라이브니스 실패가 발생할 수도 있는 두 가지 상황을 알아 볼 것.

6.8.1. 데드락

세마포어를 대기 큐로 구현하면 두 개 이상의 프로세스가 오로지 한 프로세스에서 발생한 이벤트를 무한정 대기하는 일이 발생할 수도 있음. 여기서 말하는 이벤트란 signal() 연산의 실행을 의미함. 이러한 상태에 들어오게 되면 프로세스가 데드락 deadlock 상태에 있다고 함.

두 프로세스 P0와 P1이 각각 1로 설정된 두 세마포어 S와 Q를 가진다고 가정:

P0이 wait(S)을 실행하고, P1이 wait(Q)를 실행한다고 사정. P0이 wait(Q)를 실행하면 반드시 P1이 signal(Q)를 실행할 때까지 대기해야함. 마찬가지로 P1이 wait(S)를 실행하면 P0가 signal(S)를 실행할 때까지 대기해야함. 어쨋든 이 signal() 연산은 절대 실행되지 않으므로 P0와 P1은 데드락 상태임.

집합의 모든 프로세스가 집합 내의 다른 프로세스의 의해 발생한 이벤트를 대기 중일 때 프로세스 집합이 데드락 상태에 있다고 함. 이 예제에서의 "이벤트"란 상호배제 락이나 세마포어와 같은 자원의 획득과 반납임. 다른 이벤트로도 데드락이 발생할 수 있음. 이건 8 단원에서 다룰 것. 8 단원에서는 데드락 문제를 처리할 여러 메커니즘과 여러 다른 라이브니스 실패를 다룸.

6.8.2. 우선순위 역전

고순위 프로세스가 현재 저순위 프로세스나 저순위 프로세스의 연속된 사슬이 현재 접근 중인 커널 자료를 읽거나 수정해야할 때 스케줄링 문제가 발생함. 커널 자료를 보통 락으로 보호하므로 고순위 프로세스는 저순위 프로세스가 자원을 다 쓸 때까지 대기해야함. 만약 저순위 프로세스가 고순위 프로세스에 의해 선점되면 문제가 조금 더 복잡해짐.

예를 들어 세 프로세스 L, M, H이 있고, L < M < H 순으로 우선순위를 갖는다고 가정. 프로세스 H가 세마포어 S를 필요로 하는데, 이게 지금 프로세스 L이 사용 중이라고 가정. 일반적인 경우 프로세스 H는 L이 자원 S 다 쓸 때까지 대기해야하지만, M이 이제 실행 가능해져서 프로세스 L을 선점했다고 가정. 이 경우 더 낮은 우선순위를 갖는 프로세스 M이 프로세스 H가 프로세스 L이 자원 S 반납할 때까지 기다리는 시간에 간접적으로 영향을 주었다고 할 수 있음.

이런 라이브니스 문제를 우선순위 역전 priority inversion이라 부르며, 당연히 두 개 이상의 우선순위를 갖는 시스템에서 발생함. 일반적으로 우선순위 역전은 우선순위 상속 프로토콜 priority-inheritance protocol을 구현하여 피할 수 있음. 이 프로토콜에 의하면 고순위 프로세스가 필요로 하는 자원을 접근하는 모든 프로세스는 해당 자원을 다 쓸 때까지 고순위 프로세스의 우선순위를 상속받음. 위의 예씨의 경우 우선순위 상속 프로토콜에 의해 프로세스 L이 임시로 프로세스 H의 우선순위를 상속받아 프로세스 M이 선점하지 못할 것임. 프로세스 L이 자원 S 다 사용하면 H로부터 상속 받은 우선순위 반납하여 원래 우선순위로 돌아올 것임. 자원 S가 이제 사용 가능하니 프로세스 M이 아니라 프로세스 H가 다음으로 실행 될 것임.

우선순위 역전과 마스 패스파인더

우선순위 역전은 단순히 스케줄링에 불편을 주는 것으로 끝나지 않을 수도 있음. 실시간 시스템과 같이 빽빽한 시간 제약을 갖는 시스템에서 우선순위 역전을 사용할 경우 프로세스가 원래 작업 처리하는데 걸리는 속도보다 더 시간이 오래 걸리게 될 수도 있음. 이게 발생하면 다른 문제들이 또 발생해 결국 시스템이 실패할 수도 있음.

1997년에 실험을 위해 화성에 발사한 NASA에서 탐사차량 소저너를 탑재한 탐사선 마스 패스파인더의 경우. 소저너가 임무를 시작하자마자 컴퓨터가 자주 리셋되기 시작. 리셋할 때마다 통신을 포함한 모든 하드웨어와 소프트웨어를 재초기화함. 이거 해결 못하면 소저너는 임무를 실패했을 것.

문제가 발생한 이유는 한 고순위 작업 "bc_dist"가 원래 예상된 시간보다 더 오래 걸렸기 때문임. 저순위 "ASI/MET" 작업이 bc_dist도 필요로 하는 공유 자원을 사용하고 있어서 강제로 대기했어야 했는데, 이 "ASI/MET"도 계속 여러 중간순위 작업들에 의해 선점을 당하고 있었음. "bc_dist" 작업은 계속 공유 자원을 위해 대기하고 있으니 결국 "bc_sched" 작업이 문제를 발견하여 리셋이 됐던 것임. 소저너는 이런 일반적인 우선순위 역전의 경우 문제를 겪고 있었던 것.

소저너의 운영체제는 VxWorks 실시간 운영체제로 모든 세마포어에 대해 우선순위 상속을 가능케 해주던 전역 변수를 갖고 있었음. 몇 번 테스트 후 소저너에서 해당 변수를 설정해주었고(화성에서!), 문제가 해결이 됨.

이 문제, 검출, 해법을 보고 싶으면 해당 소프트웨어 팀 리드가 작성한 글을 읽어보도록.

6.9. 평가

임계구역 문제를 해결하는데 사용할 수 있는 여러 동기화 도구를 다루었음. 제대로 구현하고 사용만 한다면 이 도구들은 효과적으로 상호 배제를 보장할 뿐만 아니라 라이브니스 문제도 해결 가능함. 요즘 다중 코어 컴퓨터 시스템의 힘을 활용하는 동시 프로그램이 갈 수록 증가하면서 동기화 도구의 성능에도 많은 관심이 주어지고 있음. 이 도구를 언제 사용하는지가 근데 문제가 될 수 있음. 이 절에서는 어떤 동기화 도구를 언제 사용할지에 대한 간단한 전략을 다룰 것.

하드웨어적 해법은 6.4 절에서 논했으며, 보통 저수준이며, 일반적으로 상호배제와 같은 동기화 도구를 생성할 때 사용할 근본으로 보통 사용함. 허나 최근엔 CAS 명령어로 락 없는 lock-free 알고리듬을 만들어 락을 거는 데의 부담 없이 경합 조건으로부터 보호를 제공할 수 있음. 락 없는 해법이 부담도 적고 확장성이 좋아 최근에 유명세를 얻고는 있지만 알고리듬 자체가 개발하기도 어렵고 테스트도 어려움. (직접 해보셈.)

CAS 기반 접근법은 낙관적인 접근법이라 부름. 변수를 우선 아무 생각없이 갱신하고, 충돌 검출을 통해 다른 스레드가 해당 변수를 동시에 수정하고 있는지 확인함. 만약 다른 스레드가 동시에 수정 중이었다면 성공적으로 충돌 없이 변수의 값이 갱신이 될 때까지 재시도함. 상호배제 락은 반대로 비관적인 전략이라 부름. 다른 스레드가 동시에 변수를 갱신 중이라고 가정하므로, 갱신하기 전에 비관적으로 락부터 걸음.

여러 경합 상황에서 여러 CAS 기반 동기화와 전통적인 동기화(상호배제 락이나 세마포어) 간의 성능 차이에 대한 일반적인 규칙을 얻을 수 있는 가이드라인:

  • 무경합 uncontended. 둘 다 일반적으로 빠르지만, CAS 보호가 전통적인 동기화보다 빠름.
  • 일반적인 경합 moderate contention. CAS 보호가 좀 더 빠름. 전통적인 동기화보다 훨씬 빠를 수도 있음.
  • 고수준 경합 high contention. 경합이 심할 땐 전통적인 동기화가 CAS 기반 동기화보다 훨씬 빠름.

일반적인 경합 수준이 흥미로운게, CAS 연산은 거의 매 번 성공하고, 실패하더라도 아래 코드에서의 루프를 겨우 몇번만 돌다가 성공함. 반면에 상호배제 락을 할 경우 경합 중인 락을 얻으려는 모든 시도의 결과는 스레드를 중단시키고 대기 큐에 넣어 다른 스레드로 문맥 교환이 되는 코드 경로이므로 복잡하고 시간이 오래 걸리게 됨.

while (true) {
    while (compare_and_swap(&lock. 0, 1) != 0) {
    	; /* 아무 것도 하지 않음 */
    }
    
    /* 임계구역 */
    
    lock = 0;
    
    /* 나머지 구역 */
}

경합 조건을 처리하는 메커니즘에 따라서도 시스템 성능에 엄청난 영향이 감. 예를 들어 원자적 정수가 전통적인 락보다 더 가벼우면서 일반적으로 카운터와 같은 단일 변수를 갱신하는 경우에선 상호배제 락이나 세마포어보다 더 적합함. 다중 프로세서 시스템에서 락이 짧은 기간동안만 걸려 스핀록을 사용하는 운영체제의 설계에서도 이를 볼 수 있음. 일반적으로 상호배제 락이 세마포어보다 더 간단하고 부담도 덜 요구하며, 임계구역으로의 접근을 보호할 때 이진 세마포어보다 더 선호됨. 허나 유한한 개수의 자원과 같은 경우에선 카운팅 세마포어가 상호배제 락보다 일반적으로 좀 더 적합함. 마찬가지로 독자-작가 락이 더 높은 수준의 동시성을 제공하기에(즉, 여러 독자들) 상호배제 락보다 더 선호됨.

모니터와 조건 변수와 같은 고수준 도구의 장점은 단순함과 사용 간편성임. 하지만 이런 도구는 부담이 높으며 구현에 따라 경합이 자주 발생하는 상황에서는 덜 확장적일 수도 있음.

다행히도 동시성 프로그래밍에서 요구하는 부분들을 처리하는 확장적이면서 효율적인 도구를 개발하는 연구가 진행되고 있음. 예를 들면:

  • 더 효율적인 코드를 생성하는 컴파일러 설계
  • 동시 프로그래밍을 지원하는 언어 개발
  • 현존하는 라이브러리와 API의 성능 개선

다음 단원에서는 개발자들이 사용 가능한 여러 운영체제와 API에서 어떻게 이 단원에서 언급한 동기화 도구를 구현하는지를 알아볼 것.

6.10. 요약

  • 경합 조건이란 프로세스가 동시에 공유 데이터에 접근을 하여 최종 결과가 동시 접근이 발생한 순서에 따라 달라질 때 발생함. 경합 조건은 잘못된 공유 데이터 값을 야기할 수 있음.
  • 임계구역이란 공유 데이터가 수정될 수 있는 코드의 부분이므로 경합 조건이 발생할 수 있는 구역임. 임계구역 문제란 프로세스가 서로 협업하며 자료를 공유할 수 있도록 활동을 서로 동기화하는 프로토콜을 설계하는 것이 목적임.
  • 임계구역 문제의 해법은 반드시 다음 세 가지 조건을 만족해야 함: (1) 상호 배제, (2) 진행, (3) 한정 대기. 상호 배제란 오로지 한 프로세스가 한 순간에 임계구역에서 활성화되어있음을 보장하는 것임. 진행이란 프로그램에서 다음에 어떤 프로세스가 임계구역에 입장할지를 협업으로 정하는 것을 보장하는 것임. 한정 대기란 프로그램이 임계구역 이전에 들어갈 시간에 한계를 주는 것을 의미함.
  • 피터슨의 해법과 같은 임계구역 문제에 대한 소프트웨어 기반 해법은 요즘 컴퓨터 구조에서 제대로 돌지 않음.
  • 임계구역 문제를 위한 하드웨어 지원에는 메모리 배리어, 비교 후 스왑 명령어와 같은 하드웨어 명령어, 원자적 변수 등이 있음.
  • 상호배제 락이란 프로세스가 임계구역에 들어가려면 락을 걸고, 임계구역에서 나가려면 락을 풀도록 강제하는 것으로 상호 배제성을 제공함.
  • 세마포어는 상호배제 락처럼 상호 배제성을 제공할 수 있으나 상호배제 락은 락의 사용 가능성을 의미하는 이진 값을 갖는 반면, 세마포어는 정수값을 갖기에 여러 동시성 문제를 해결하는 데 사용할 수 있음.
  • 모니터란 고수준의 프로세스 동기화를 제공하는 추상 자료형. 모니터는 조건 변수를 통해 프로세스가 특정 조건이 참이될 때까지 대기하고, 조건이 참이 되면 서로에게 신호를 보냄.
  • 임계구역 문제에 대한 해법은 데드락과 같은 라이브니스 문제를 겪을 수도 있음.
  • 임계구역 문제를 해결하고 프로세스의 활동 간을 동기화하는 사용하는 여러 도구들 간에서는 여러 경합 수준에서 평가할 수 있음. 경합 수준마다 더 잘 나가는 도구들이 다름.
profile
‍주민하
개발자
이전 포스트

운영체제 (공룡책) - 5

다음 포스트

운영체제 (공룡책) - 7

0개의 댓글