[OSTEP] 병행성 - 락

1. 락

• 여러 개의 명령어들을 원자적으로 실행해보고 싶지만 단일 프로세서의 인터럽트로 인해서(또는 멀티 쓰레드를 여러 프로세서에 병행성하려고 해서) 그렇게 할 수가 없었다.
• 프로그래머들은 소스 코드의 임계 영역을 락(lock)으로 둘러서 그 임계 영역이 마치 하나의 원자 단위 명령어인 것처럼 실행되도록 한다.

1.1 락: 기본 개념

• 락은 일종의 변수다.
• 락을 사용하기 위해서는 락 변수를 먼저 선언해야 한다.
• 이 락 변수는 락의 상태를 나타낸다.
• 락은 둘중 하나의 상태를 갖는다.
  1. 사용 가능(available) 상태 (unlockedf 또는 free)
     • 즉 어떤 쓰레드도 락을 소유하고 있지 않다.
  2. 사용 중(acquired) 상태
     • 즉 임계 영역에서 정확히 하나의 쓰레드가 락을 획득한 상태이다.

• lock() 루틴 호출을 통해 락 획득을 시도한다.
  • 이렇게 락을 획득한 쓰레드를 소유자(owner)라고 부른다.
  • 락을 소유한 쓰레드가 임계 영역에 존재하는 상태에서는 다른 쓰레드들이 임계 영역으로 진입할 수 없다.
• 락 소유자가 unlock()을 호출한다면 락은 이제 다시 사용 가능한 상태가 된다.

• 일반적으로 쓰레드는 프로그래머가 생성하고 운영체제가 제어한다.
• 락으로 코드를 감싸서 프로그래머는 크 코드 내에서는 하나의 쓰레드만 동작하도록 보장할 수 있다.

1.2 Pthread 락

• 쓰레드 간에 상호 배제(mutual exclusion) 기능을 제공하기 때문에 POSIX 라이브러리는 락을 mutex라고 부른다.
• 상호 배제는 한 쓰레드가 임계 영역 내에 있다면 이 쓰레드의 동작이 끝날 때까지 다른 쓰레드가 임계 영역에 들어 올 수 없도록 제한한다고해서 얻은 이름이다.
• 각 데이터와 자료 구조를 보호하는 데 있어서, 여러 락을 사용한다.

1.3 락의 평가

• 락 설계시, 락의 정상동작 여부 판단을 위한 평가기준을 정해야 한다.
  1. 상호 배제를 제대로 지원하는가이다.
  2. 공정성(fairness)
     • 락을 전혀 얻지 못해 굶주리는(starve) 경우가 발생하는지를 판단해야한다.
  3. 성능(performance)이다.

이제부터 1.4절부터 락을 구현하는 여러가지 방법에 대해 알아볼 것이다. 스핀락부터 스핀을 사용하지 않는 락까지 알아본다.

1.4 인터럽트 제어

• 초창기 단일 프로세스 시스템에서는 상호 배제 지원을 위해 임계 영역 내에서는 인터럽트를 비활성화하는 방법을 사용했다.

    void lock(){
        DisableInterrupts();
    }
    void unlock(){
        EnableInterrupts();
    }

• 이 방법은 잔점이 많다.
• 첫 번째 단점은, 요청을 하는 쓰레드가 인터럽트를 활성/비활성화하는 특권(privileged) 연산을 실행할 수 있도록 허가해야 한다.
  • 이를 다른 목적으로 사용하지 않음을 신뢰할 수 있어야 한다.
• 두 번째 단점은, 멀티프로세서에서는 적용을 할 수가 없다.
• 세 번째 단점은, 장시간 동안 인터럽트를 중지시키는 것은 중요한 인터럽트의 시점을 놓칠 수 있다.
• 마지막은, 이 방법은 비효율적이다.

1.5 오직 load/store 명령어만 사용하기(실패한 시도)

• load와 store 명령어만으로 락을 구현한다.
  • 간단한 플래그 변수를 사용하여 쓰레드가 락을 획득하였는지를 나타낸다.

    void init(lock_t *mutex){
        mutex->flag = 0; // 0 -> 락 사용가능, 1 -> 락 사용중
    }
    void lock(lock_t *mutex){
        while (mutex->flag == 1) ; // flag 변수 검사 이후 spin-wait
        mutex->flag = 1; // 이제 설정
    }
    void unlock(lock_t *mutex){
        mutex->flag = 0;
    }

• 실패원인: 적시에 인터럽트가 발생하면 두 쓰레드 모두 플래그를 1로 설정하는 경우가 생길 수 있어서 임계 영역에 두 쓰레드 다 진입할 수 있게 된다.
• 성능저하: spin-wait라는 방법을 사용하여 플래그의 값을 무한히 검사하는데, 이는 시간을 낭비한다.

1.6 Test-And-Set을 사용하여 작동하는 스핀 락 구현하기

• 하드웨어 기법 중 가장 기본은 test-and-set 명령어 또는 원자적 교체(atomic exchange)로 알려진 명령어이다.

    int TestAndSet(int *old_ptr, int new){
        int old = *old_ptr;
        *old_ptr = new;
        return old;
    }
    
    void lock(lock_t *mutex){
        while (TestAndSet(flag, 1) == 1) ; // TestAndSet으로 원자적으로 플래그를 검사
    }

• 락의 값을 검사(test)</storng>하고 새로운 값으로 설정(set)하는 동작을 원자적 연산으로 만듦으로써 오직 하나의 쓰레드만 락을 획득할 수 있도록 만들었다.
• 지금 설명한 방법이 스핀 락으로 불리는 이유를 이제 이해할 수 있다.
• 락을 획득할 때까지, CPU 사이클을 소모하면서 회전한다.
• 이 방식을 제대로 사용하려면 선점형 스케줄러(preemptive scheduler)를 사용해야 한다.
  • 선점형이 아니면, 단일 CPU에서 스핀 락의 사용은 불가능하다. 왜냐하면 while 문을 회전하며 대기하는 쓰레드가 CPU를 영원히 독점하기 때문이다.

스핀 락 평가

1. 정확성
   • 제대로 동작한다.
2. 공정성
   • 단순한 스핀 락은 공정하지 않으며 쓰레드가 굶주리게 만들 수 있다. (while문을 회전하기 때문에)
3. 성능
   • 단일 CPU의 경우 성능 오버헤드는 상당히 클 수 있다. 쓰레드는 할당받은 기간 동안 CPU 사이클을 낭비하면서 락을 획득하기 위해 대기한다.
   • 멀티 CPU의 경우 다른 프로세서에서 락을 획득하기 위해 while문을 회전하면서 대기하는 것은 그렇게 많은 사이클을 낭비하지 않기 때문에 효율적일 수 있다.

1.7 Compare-And-Swap

    int CompareAndSwap(int *ptr, int expected, int new){
        int original = *ptr;
        if (original == expected)
            *ptr = new;
        return original
    }

• Compare-And-Swap 기법은 기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사하는 것이다.
• CompareAndSwap 명령어는 TestAndSet 명령어보다 더 강력하다.
  • 대기없는 동기화(wait-free synchronization)와 같은 주제를 다룰 때 이 루틴이 갖느 능력을 알게 될 것이다.

1.8 Load-Linked 그리고 Store-Conditional

• load-linked와 store-conditional 명령어를 앞뒤로 사용하여 락이나 기타 병행 연산을 위한 자료 구조를 만들 수 있다.

1.9 Fetch-And-Add

• Fetch-And-Add 명령어로 원자적으로 특정 주소의 예전 값을 반환하면서 값을 증가시킨다.

    int FetchAndAdd(int *ptr){
        int old = *ptr;
        *ptr = old + 1;
        return old;
    }

    typedef struct __lock_t{
        int ticket;
        int turn;
    } lock_t;
    
    void lock_init(lock_t *lock){
        lock->ticket = 0;
        lock->turn = 0;
    }

    void lock(lock_t *lock){
        int myturn = FetchAndAdd(&lock->ticket);
        while (lock->turn != myturn) ;
    }

    void unlock(lock_t *lock){
        FetchAndAdd(&lock->turn)
    }

• 위의 방법은 티켓락
  • 이전까지의 접근 방법과 이번 해법의 중요한 차이 중 하나는 모든 쓰레드들이 각자의 순서에 따라 진행한다는 것이다.

1.10 요약: 과도한 스핀

• 두개의 쓰레드를 프로세서가 하나인 시스템에서 실행하면 레이턴시가 증가한다.
• N개의 쓰레드가 하나의 락을 획득하기 위해 경쟁하게 되면 상황은 더욱 심각해진다.
• N-1개의 쓰레드에 할당된 CPU 시간 동안, 비슷한 이유로 낭비하게된다.

1.11 간단한 접근법: 조건 없는 양보!

• 위의 방법들로 동작이 검증된 락과 락 획득의 공정성(티켓 락을 사용한 경우) 까지도 해결할 수 있었다.
• 이전 쓰레드가 인터럽트에 걸리기 전에 락을 이미 획득한 상태라서 그 쓰레드가 락을 해제하기를 기다리며 스핀만 무한히 하는 경우에 어떻게 해야 할것인가?
  • 첫 번째 방법은 락이 해제되기를 기다리며 스핀해야하는 경우 자신에게 할당된 CPU를 다른 쓰레드에게 양보하는 것이다.

    void init(){
        flag = 0;
    }

    void lock(){
        while(TestAndSet(&flag, 1) == 1)
            yield();
    }

    void unlock(){
        flag = 0;
    }

• 위의 방법은 Test-And-Set와 양보를 이용한 락이다.
  • 운영체제에 자신이 할당받은 CPU 시간을 포기하고 다른 쓰레드가 실행될 수 있도록 하는 yield90 기법을 사용한다.
  • 단점은 많은 쓰레드가 있을 때 하나를 제외한 나머지의 쓰레드가 실행과 양보를 반복하는 패턴으로 비용이 많이 든다. 또한 어떤 쓰레드는 무한히 양보만 하고 있는 경우가 있을 수 있다.

1.12 뮤의 사용: 스핀 대시 잠자기

• 이전 방법들의 근본 문제는 너무 많은 부분을 운에 맡긴다는 것이다.
• 다수의 쓰레드가 락을 대기하고 있을 경우, 다음으로 락을 획득할 쓰레드를 명시적으로 선택할 수 있어야 한다. 이를 위해서는 운영체제의 적절한 지원과 큐를 이요한 대기 쓰레드들의 관리가 필요하다.
  • park(), unpark() <- 쓰레드를 잠재우고 깨우는 함수이다.
• 장점
  1. 앞서 배운 Test-And-Set 개념을 락 대가지 전용 큐와 함께 사용하여 좀 더 효율적인 락을 만들 수 있다.
  2. 큐를 사용하여 다음으로 락을 획득할 대상을 제어하여 기아 현상을 피할 수 있도록 할 수 있다.

1.13 2단계 락

• 첫 번째 단계에서는 회전하며 대기한다. 락이 빠른 시간 내에 해제될 것을 가정한다.
• 만약 첫 단계에서 락을 획득하지 못했다면 두 번째 단계로 진입한다.
• 두 번째 단계에서 호출자는 차단된다.
• 락 해제시 블럭된 쓰레드중 하나를 잠에서 깨운다.