CS & C++ Notes

6.4 Hardware Support for Synchronization

9 min read

  • 공룡책
  • cs

Info

해당 섹션은 HW에서 critical-section problem을 해결하기 위해서 사용되는 3가지 방법에 대해서 알아본다.

  • Memory Barriers
  • Hardware Instructions
  • Atomic Variables

Memory Barriers

메모리 모델

컴퓨터 아키텍처가 어떻게 응용 프로그램의 메모리를 보증(guarantees)할지는 메모리 모델이 달려있다.

메모리 모델의 2가지 분류
  1. Strongly ordered : 메모리의 수정이 다른 모든 프로세스에 즉시 반영된다.
  2. Weakly ordered : 메모리의 수정이 다른 모든 프로세스에 즉시 반영되지 않을 수 있다.

1번은 주로 RTOS에서 2번은 GPOS에서 사용된다.

메모리 동기화 명령어

컴퓨터 아키텍처는 모든 프로세서에게 메모리 변경 사항을 전파하고, 이를 다른 프로세서에서 실행 중인 스레드에 즉시 반영하도록 강제하는 명령어를 제공한다.

즉시 반영한다는 건, 순서를 강제한다는 의미와 같다. 따라서 강제하는 명령어는 ATomic Operation이 가능하도록하는 명령어를 의미한다.

메모리 배리어(펜스)의 역할
  1. 가시성(visible) 보장 : 메모리 배리어는 메모리의 수정 사항이 다른 프로세서에서 실행 중인 스레드에 즉시 가시적이 되도록 보장한다.
  2. 실행 순서 보장 : 메모리 배리어 명령어 실행 시, 시스템은 이후의 모든 로드(load) 및 스토어(store) 작업이 수행되기 전에, 모든 이전 로드와 스토어 작업이 완료되었음을 보장한다.

메모리 배리어는 동기화를 위한 명령어 중 하나로 사용된다. 가시적이란 표현은 메인 메모리에 저장된 값과 CPU 캐시에 저장된 값이 다른 경우를 의미한다.


따라서, 명령어의 재배치가 발생하더라도, 메모리 배리어를 통해 모든 스토어 작업이 메모리에서 완료되고, 다른 프로세서에 가시적이 되며, 모든 후속 로드나 스토어 작업이 수행되기 전에 이러한 상태가 보장된다.

Memery Barrier는 load, store 작업을 visible할 수 있도록 해주기 때문에, 명령어 재배치 발생으로 부터 자유롭다. (최적화시 발생)

스레드 1에 메모리 배리어 추가
arduinoCopy code
while (!flag)
		memory_barrier();
print x;

이를 통해 **flag**의 값이 **x**의 값보다 먼저 로드되는 것을 보장한다.

스레드 2에서 할당 사이에 메모리 배리어 배치
csharpCopy code
x = 100;
memory_barrier();
flag = true;

이를 통해 **x**에 대한 할당이 **flag**에 대한 할당보다 먼저 발생하는 것을 보장한다.


배리어 명령은 위, 아래 명령의 순차성을 보장한다.

피터슨의 해결책과 메모리 배리어

진입 섹션에서 처음 두 개의 할당 문 사이에 메모리 배리어를 배치함으로써, 아래에 보여진 연산의 재배치를 피할 수 있다.

메모리 배리어는 매우 저수준의 연산으로 간주되며, 일반적으로 상호 배제를 보장하는 특수 코드를 작성할 때 커널 개발자들에 의해서만 사용된다.

Hardware Instructions

현대 컴퓨터 시스템에서 임계 영역 해결을 위해 사용되는 2가지 명령어

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

이 명령어의 중요한 특성은 원자적으로 실행된다는 것이다.

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

**lock**을 false로 초기화함으로써 상호 배제를 구현할 수 있다.

위에 예시는 이해를 돕기 위함이지, 실제 구현은 아니다. 사용할 때는 test_and_set을 이용하여 사용하면 된다.

std::atomic_flag::test_and_set - cppreference.com

compare_and_swap() (CAS) 명령어

  • 정의 : test and set() 명령어와 마찬가지로 두 단어에 대해 원자적으로 작동하지만, 두 단어의 내용을 교환하는 다른 메커니즘을 사용한다.

  • 사용 : 세 개의 피연산자에 작동하며, 오직 *value == expected 표현식이 참일 때만 피연산자 값을 새 값으로 설정합니다. 어떠한 경우에도, CAS는 변수 **value**의 원래 값을 항상 반환한다


  • 특징 : 명령어의 중요한 특징은 원자적으로 실행된다는 것입니다. 따라서, 두 CAS 명령어가 동시에 실행되더라도(각각 다른 코어에서), 어떤 임의의 순서로 순차적으로 실행될 것이다.

  • 상호 배제 : 전역 변수(lock)를 선언하고 0으로 초기화합니다. **compare and swap()**을 호출하는 첫 번째 프로세스는 **lock**을 1로 설정합니다. 이는 원래 **lock**의 값이 예상 값 0과 같았기 때문에, 이후에 임계 영역에 진입합니다. **compare and swap()**에 대한 이후 호출은 **lock**이 더 이상 예상 값 0과 같지 않기 때문에 성공하지 않습니다. 프로세스가 임계 영역을 나갈 때, 그것은 **lock**을 0으로 다시 설정하여 다른 프로세스가 임계 영역에 진입할 수 있게 합니다.

Atomic Variables

  • 목적과 기본 개념:
    • 목적: 원자 변수(atomic variable)는 기본 데이터 타입(예: 정수, 불린)에 대해 원자적 연산을 제공하여, 데이터 경쟁(data race) 상황에서 상호 배제(mutual exclusion)를 보장합니다.
    • 기본 개념: 원자 변수는 한 번에 하나의 스레드만 변수를 업데이트할 수 있도록 하여, 경쟁 상황에서도 데이터의 일관성을 유지합니다.
  • 배경: 경쟁 상황과 원자 변수의 필요성:
    • 경쟁 상황: 여러 스레드가 동일한 변수를 동시에 업데이트하려 할 때 발생합니다. 예를 들어, 정수 값을 증가시키거나 감소시키는 간단한 작업조차도 경쟁 상황을 일으킬 수 있습니다.
    • 원자 변수의 역할: 이러한 경쟁 상황에서 변수 업데이트를 위한 상호 배제를 제공함으로써 데이터 레이스를 방지합니다.
  • 변수의 한계와 주의 사항:

    • 한계점: 원자 변수는 단일 변수 업데이트에 대한 상호 배제를 제공하지만, 모든 종류의 경쟁 상황을 해결하는 완벽한 솔루션은 아닙니다.

    load, store에 대한 원자적 행동을 보장하지만 다른 보장은 없기때문에 한계가 명확한듯 하다.

atomic 변수 std::atomic - cppreference.com

그래프 뷰

백링크