3-3장. 락(Lock) - 2

위에서 살펴봤듯 멀티 프로세서에서는 인터럽트를 중지시키는 것이 의미가 없기 때문에 시스템 설계자들은 락 지원을 위한 하드웨어 설계를 하기 시작했다. 오늘날 모든 시스템들은 하드웨어 지원 기능을 가지고 있으며, 단일 CPU 시스템 또한 이런 기능이 존재한다.

Test-And-Set (Atomic Exchange)

하드웨어 기법 중 가장 기본은 Test-And-Set 명령어 또는 원자적 교체(atomic exchange) 라고 불리는 기법이다. Test-And-Set 명령어를 사용하면 락을 간단하게 구현할 수 있다.

 

ptr이 가리키는 이전 값을 old로 받아 리턴(TEST)한다. 동시에 그 값을 new로 바꾼다(SET). 이 동작은 원자적으로 수행되어야 하며 중간에 인터럽트 될 수 없다. 때문에, 소프트웨어 만으로는 구현이 불가능하다. 하드웨어 선에서 메모리를 통과하는 버스를 잠가 다른 CPU나 코어의 메모리 관련 명령어 실행을 원천 봉쇄한다.

 

스핀 락(Spin lock)

Test-And-Set 명령어를 이용하면 스핀 락을 구현할 수 있다. 스핀 락이란, 임계 영역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된 락이다. 쓰레드가 락을 획득할 때까지 빙빙 돌고(spinning) 있다는 것을 의미한다. Test-And-Set을 이용하여 스핀 락을 구현하면 다음과 같다.

 

평가

• 정확성 : 락에서 가장 중요한 측면은 바로 정확성이다. 스핀 락은 오직 한 쓰레드 만이 임계 영역에 진입할 수 있기 때문에 정확하다. 
  
  

• 공정성 : 대기 중인 많은 쓰레드들에게 공정하게 진입할 기회가 주어지는가? 스핀 락에 대한 것이라면 아니다. 스핀 락은 어떠한 공정성도 제공하지 않는다. 최악의 경우에는 영원히 진입하지 못하고 스핀 하는 쓰레드가 생길 수 있다. 이는 쓰레드를 굶주리는 기아(Starvation) 상태로 만들 수 있다.
  
  

• 성능 : 마지막 항목은 성능이다. 스핀 락을 사용할 때 지불해야 하는 비용은 무엇인가? 단일 CPU에서의 성능은 끔찍할 수 있다. n개의 쓰레드 중 락을 갖고 있던 쓰레드가 선점된 경우에, 스케줄러가 락을 획득하기 위해 시도하는 나머지 쓰레드들(n - 1개)을 하나씩 깨울 수도 있다. 쓰레드는 할당받은 기간 동안 CPU 사이클을 낭비하면서 락을 획득하기 위해 대기한다. 하지만 CPU가 여러 개인 경우 스핀 락의 성능은 적절하다. CPU가 여러 개이기 때문에 나머지 쓰레드들을 다른 프로세서에서 실행시키면 된다. 이렇게 되면 while문을 회전하면서 대기하는 것은 그렇게 많은 사이클을 낭비하지 않기 때문에 효율적일 수 있다. 

Compare-And-Swap

또 다른 하드웨어 기법으로는 Compare-And-Swap이 있다. 코드는 다음과 같다.

 

Compare-And-Swap 기법의 기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사하는 것이다. 만약 일치한다면 ptr이 가리키는 주소의 값을 새로운 값으로 변경한다. 불일치한다면 아무것도 하지 않는다. 원래의 메모리 값을 반환하여 CompareAndSwap를 호출한 코드가 락 획득에 성공 여부를 알 수 있다.

Compare-And-Swap을 사용하면 Test-And-Set 방법을 사용했을 때와 같은 방식으로 락을 만들 수 있다. 다음 처럼 말이다.

 

flag 변수가 false인지 검사하고 만약 그렇다면 자동적으로 true로 바꾸어 락을 획득한다. 다른 쓰레드가 락을 보유하고 있는 중에 락을 획득하려고 시도하는 쓰레드는 락이 획득 가능한 상태가 될 때까지 while 문에서 회전하게 된다. 

 

x86 기반에서 CompareAndSet 함수를 기계어 구현하면 다음과 같다.

 

C++11에서는 CompareAndSet 메서드를 다음과 같이 구현하면 된다.

 

atomic_bool은 bool 형식인데 원자적인 특성을 가진 것이다. 이 형식을 가진 변수는 읽고 쓰는 것을 원자적으로 수행한다. atomic_compare_exchange_strong은 성공하면 true, 실패하면 false를 리턴하며, expected에 addr에 있던 원래 값을 넣어서 리턴한다.

 

다음은 위 CompareAndSwap을 사용한 상호 배제 코드이다. 5000만 번 2를 더하는 작업을 4개의 쓰레드가 나누어 작업한다.

#include <atomic>
#include <thread>
#include <iostream>
using namespace std;

static const int NUM_THREADS = 4;
volatile int sum;
atomic_bool lock = false;

bool CompareAndSet(atomic_bool *addr, bool expected, bool new_val)
{
    atomic_compare_exchange_strong(addr, &expected, new_val);
    return expected;
}

void my_lock()
{
    while(true == CompareAndSet(&lock, false, true));
}

void my_unlock()
{
    lock = false;
}

void worker(int count)
{
    for(int i = 0; i < count; ++i)
    {
        my_lock();
        sum = sum + 2;
        my_unlock();
    }
}

int main()
{
    thread workers[NUM_THREADS];
    sum = 0;
    for(auto &th : workers) th = thread{worker, 50000000 / NUM_THREADS};
    for(auto &th : workers) th.join();
    cout << "Sum = " << sum << endl;
    system("pause");
}

 

Load-Linked와 Store-Conditional

어떤 플렛폼은 임계 영역 진입 제어 함수를 제작하기 위한 명령어 쌍을 제공한다. 그것이 바로 Load-Linked와 Store-Conditional 명령어이다. 코드는 다음과 같다.

 

LoadLinked는 메모리 값을 레지스터에 저장한다. store-conditional 명령어는 동일한 주소에 다른 스토어가 없었던 경우에만 저장을 성공한다. 저장이 성공하면, LoadLinked가 탑재했던 값을 갱신한다. 성공한 경우 1을 반환하고 ptr이 가리키는 value값을 갱신한다. 실패한 경우에는 ptr이 가리키는 value의 값이 갱신되지 않고 0을 반환한다.

 

위 두 함수를 이용하여 락을 구현하면 다음과 같다.

 

쓰레드는 while문을 돌며 flag가 0이 되기를 기다린다.(락이 해제된 상태) 락이 획득 가능한 상태가 되면 쓰레드는 StoreConditional 명령어로 락 획득을 시도하고 만약 성공한다면 쓰레드는 flag 값을 1로 변경한다. 그리고 임계 영역으로 진입한다.

 

StoreConditional 명령어는 실패할 수도 있다. 이 점이 중요하다. 쓰레드가 lock을 호출하여 LoadLinked를 실행하고 락이 사용 가능한 상태이므로 0을 반환한다. StoreConditional 명령어를 시도하기 전에 이 쓰레드는 인터럽트에 걸렸고 다른 쓰레드가 락 코드를 호출하고 LoadLinked 명령어를 실행하여 0을 반환받은 후 계속 진행한다고 해 보자. 이 시점에서 두 쓰레드는 모두 LoadLinked 명령어를 실행하였고 각자가 StoreConditional을 부르려는 상황이다. 이 명령어의 주요 기능은 오직 하나의 쓰레드만 flag 값을 1로 설정한 후에 락을 획득할 수 있도록 하는 것이다. 두 번째로 StoreConditional을 실행하려는 쓰레드는 락 획득에 실패하고 다음 기회를 기다려야 한다. 

 

lock 명령어를 다음과 같이 좀 더 짧게 구현할 수도 있다.