6.4 Hardware Support for Synchronization

 소프트웨어 기반 솔루션은 현대 컴퓨터 아키텍처에서 작동이 보장되지 않는다. 이 섹션에서는 critical section을 해결하기 위한 세 가지 하드웨어 명령을 제시한다. 이러한 원시 작업은 직접 동기화 도구로도 사용될 수도 있고, 더 추상적인 동기화 메커니즘의 기반이 될 수도 있다.

 

6.4.1 Memory Barriers

 코드 재배열 때문에 피터슨 해결책은 잘 작동하지 않기 때문에 다른 방안을 모색해야하는데, 컴퓨터 아키텍처가 응용 프로그램에 어떤 메모리 보장을 제공할 것인지 결정하는 것을 메모리 모델이라고 한다. 일반적으로 메모리 모델은 두 가지 범주 중 하나에 속한다.

1. Strongly Ordered: 하나의 프로세서에서 메모리 수정이 즉시 다른 모든 프로세서에게 보이는 경우
2. Weakly Ordered: 하나의 프로세서에서 메모리 수정이 다른 프로세서에게 즉시 보이지 않을 수 있는 경우

 메모리 모델은 프로세서 유형에 따라 다르므로 shared memory 의 multi-processor 에서 메모리 수정의 가시성에 대해 어떠한 가정도 할 수 없다. 이 문제를 해결하기 위해 컴퓨터 아키텍처는 메모리 변경 사항을 모든 다른 프로세서로 전파할 수 있는 명령을 제공하여, 메모리 수정이 다른 프로세서에서 실행 중인 스레드에게 보이도록 한다. 이러한 명령을 memory barrier 또는 memory fences 라고 한다. memory barrier 명령이 수행되면 시스템은 모든 로드와 스토어가 다음 로드 또는 스토어 작업을 수행하기 전에 완료되도록 보장한다. 따라서 명령이 재배열되더라도 memory barrier는 스토어 작업이 메모리에서 완료되고 다른 프로세서에게 보이도록 보장하게 된다.

/* thread1 */
while (!flag)
  memory_barrier();
print(x);

위는 flag의 값이 x의 값보다 먼저 로드되도록 보장한다.

/* thread2 */
x = 100;
memory_barrier();
flag = true;

 마찬가지로 스레드 2에 의해 수행된 할당 사이에 메모리 장벽을 배치하면 x에 대한 할당이 플래그에 대한 할당보다 먼저 발생하도록 보장한다.

 Peterson의 해결책과 관련하여, 우리는 entry 섹션의 첫 두 할당문 사이에 memory barrier 를 배치하여 Figure 6.4에 표시된 작업 재배열을 피할 수 있다. memory barrier는 매우 저수준의 작업으로 되어 있고, 일반적으로 커널 개발자가 상호 배제를 보장하는 특수화된 코드를 작성할 때에만 사용된다.

 

6.4.2 Hardware Instructions

 지금에 와서는 많은 아키텍처에서 한 단어의 내용을 테스트하고 수정하고 두 단어의 내용을 atomically 교환하는 특별한 하드웨어 명령을 제공한다. 그 예로 test_and_set(), compare_and_swap()이 있다.

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


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

 test_and_set() 명령의 특징은 원자적(atomic)이게 실행된다는 것이다. 그래서 두 개의 test_and_set() 두 코어에서 동시에 실행될 경우, 임의의 순서로 한쪽의 test_and_set()가 다 끝나면 다른 쪽의 test_and_set이 실행되게 된다. 이를 통해 boolean 변수 lock을 false로 초기화 시키게 되면 Mutual Exclusion을 구현하게 된다. compare_and_set() (CAS) 명령도 이와 동일하게 atomically하게 동작하지만, 두 단어의 내용을 교환하는 동작을 하게 된다.

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

/* code */

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

CAS는 세 개의 인자를 통해 작동하며 *value == expected 가 true일 때만 새 값으로 설정하게 된다. 하지만 CAS는 항상 변수 value를 원래 값으로 반환하는데, 이러한 특징은 원자적으로 실행되기 때문에 두 개의 CAS 명령이 동시에 실행될 경우 test_and_swap과 마찬가지로 순차적으로 실행된다.

 전역변수 lock이 선언되고 0으로 초기화된다. 처음에 while을 만나서 compare_and_swap을 호출하는 첫 번째 프로세스는 lock을 1로 설정한다. 그런 다음 lock의 원래 값이 기대 값 0과 같기 때문에 critical section에 들어가게 되고, compare_and_sawp()은 더이상 호출 되지 않을 것이다. 왜냐면 lock이 기대값이 0과 같지 않기 때문이다. 그리고 프로세스가 임계영역을 빠져나갈 때, lock을 다시 0으로 설정해서 다른 프로세스가 임계영역에 들어갈 수 있도록 한다. 프로세스 P_i 구조에서 상호배제의 요구를 만족하지만, bounded waiting은 만족하지 못한다.

 이제 bounded waiting을 만족하는 CAS를 보자.

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

 전역 변수로는 boolean waiting[n], int lock 이고, 모든 배열의 요소는 false로 초기화된다. lock은 0으로 초기화된다.

Mutual Exclusion

 요구사항이 충족됨을 증명하기 위해, 프로세스 P_i가 임계영역에 들어갈 수 있는 경우는 waiting[i] == false이거나 key == 0일 때 뿐이라는 것을 알 수 있다. 그러한 process가 임계영역을 들어가고, 빠져나갈 때만 false가 될 수 있고, 하나의 waiting[i] 만 false로 설정되며, 이는 상호배제 요구사항이 충족됨을 알 수 있다.

Progress

 진행 요구 사항이 충족되었는지를 증명하기 위해, 임계 영역을 빠져나가는 프로세스는 lock을 0으로 설정하거나 waiting[j]를 false로 설정한다. 이 둘 다 임계 영역에 진입을 기다리고 있는 프로세스를 진행시킬 것이다.

Bounded Waiting

유한 대기 요구 사항이 충족되었는지를 증명하기 위해, 프로세스가 임계 영역을 빠져나갈 때, 배열 waiting을 순환 순서(i + 1, i + 2, ..., n − 1, 0, ..., i − 1)로 스캔한다. 이 순서에서 entry section에 있는 첫 번째 프로세스(waiting[j] == true)를 임계 영역에 다음으로 들어갈 것으로 지정한다. 임계 영역에 들어가기를 기다리는 모든 프로세스는 이러한 순서 안에서 n − 1번 안에 그렇게 할 것이다.

 

6.4.3 Atomic Variables

 일반적으로, CAS 명령어는 상호 배제를 제공하기 위해 직접 사용되지 않는다. 대신에 이는 임계 영역 문제를 해결하는 다른 도구들을 구성하는 기본 구성 요소로 사용된다. 그 중 하나가 Atomic Variables 인데, 이는 int나 boolean과 같은 기본 데이터 유형에 대한 원자적 작업을 제공한다. 정수 값을 증가시키거나 감소시키는 것은 race condition 을 발생시킬 수 있지만, 원자 변수는 카운터가 증가될 때 단일 변수에 대한 데이터 racing 이 발생할 수 있는 상황에서 Mutual Exclusion 를 보장하기 위해 사용 가능하게 구성된다.

 원자 변수를 지원하는 대부분은 특별한 원자 데이터 유형과 원자 변수를 액세스하고 조작하기 위한 함수를 제공한다. 이러한 함수들은 대부분 CAS 연산을 사용하여 구현되고, 정수에 대한 증가시키는 함수 increment(&sequence) 또한 CAS 명령어를 사용하여 구성된다.

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

 

 atomic variables가 원자적 업데이트를 제공하지만 모든 상황에서 race condition을 완전히 해결하지는 않는다는 점을 기억하자.

 예를 들어, 6.1절에서 설명한 bounded buffer 문제에서 카운트에 대한 원자적 정수를 사용할 수 있다. 근데 카운트의 업데이트가 원자적으로 이루어질 것이고 이는 문제가 해결되는 것으로 보일 것이다.

 하지만 프로듀서와 컨슈머 프로세스는 또한 카운트 값에 따라 while 루프가 실행되기 때문에 현재 버퍼가 비어 있고, 두 컨슈머가 count > 0을 기다리며 루프를 돌고 있는 상황을 고려해본다면, 프로듀서가 버퍼에 하나의 항목을 입력했을때, count가 0이 아니기 때문에 두 컨슈머가 모두 while 루프를 빠져나오고 소비하기 시작할 수 있다. 이렇게 하면 count 값이 1로 설정된 것뿐인데도 불구하고 모두가 소비를 시작할 수 있게 된다(두 개 이상의 프로세스가 동시에 critical section에 들어가게 된다는 것임).

 따라서 원자 변수는 주로 운영 체제 및 동시성 애플리케이션에서 사용되지만, 그 사용은 주로 카운터 및 시퀀스 생성기와 같은 공유 데이터의 "단일" 업데이트로 제한된다.