Synchronization: The Critical Section Problem(3)

Hardware Solutions

How would you implement the Critical Section Problem in hardware?

Single CPU machine에서, 모든 CPU instruction에 접근하는 모든 프로세스는 일시적으로 interrupt를 비활성화할 수 있습니다.

disable_interrupts
// Critical section code
enable_interrupts

만약 인터럽트가 disable되면 현재 스레드는 인터럽트를 받을 수 없습니다. 예를 들어 CS안에 CPU instruction들은 완료될 것입니다.

그러나 오늘날 대부분의 시스템에서  하나 이상의 CPU core가 존재하고, interrupt를 disable하는 것은 privileged instruction입니다. 그러므로 위에서 제시된 기술은 거의 적용되지 않습니다.

대신, CPU가 특별한 atomic instruction인 __exch를 제공한다고 생각해봅시다. __exch는 두 메모리에 존재하는 값들을 바꿔줍니다. 이 때 다음 pseudo code와 같이 mutex lock을 구현해서 Critical Section을 제공합니다.

my_mutex_init(int* m)  { *m= 0; }

my_mutex_lock(int* m) {
  for(int q = 1; q ; ) {  __exch(&m , &q); }
} // when this returns it is safe to enter your critical section

// After you critical section is finished,call unlock...
my_mutex_unlock(int* m)  { *m= 0; }

교환하는 instruction은 하나의 인터럽트가 걸리지 않는 개별적인 인스트럭션이므로 atomic하게 동작합니다.예를 들어 두 스레드가 동시에 my_mutex_lock(그리고 나서 __exch)를 호출한다면, 한 스레드는 0을 받고, 다른 스레드는 0을 잃고 새로운 값 1을 받게 됩니다.

How do we really implement the Critical Section Problem on real hardware?(Advanced topic)

C11 atomic을 사용하는 완벽한 해결책은

https://locklessinc.com/articles/mutex_cv_futex/

이곳에 있습니다.(이것은 futex라 불리는 spinlock mutex입니다.)

typedef struct mutex_{
    atomic_int_least8_t lock;
    pthread_t owner;
} mutex;

#define UNLOCKED 0
#define LOCKED 1
#define UNASSIGNED_OWNER 0

int mutex_init(mutex* mtx){
    if(!mtx){
        return 0;
    }
    atomic_init(&mtx->lock, UNLOCKED); // Not thread safe the user has to take care of this
    mtx->owner = UNASSIGNED_OWNER;
    return 1;
}

위의 초기화 코드는 전혀 특별해 보이지 않습니다. 단지 mutex의 상태를 unlock하고 owner가 lock할수 있도록 세팅했습니다.

int mutex_lock(mutex* mtx){
    int_least8_t zero = UNLOCKED;
    while(!atomic_compare_exchange_weak_explicit
            (&mtx->lock, 
             &zero, 
             LOCKED,
             memory_order_acq_rel,
             memory_order_relaxed)){
        zero = UNLOCKED;
        sched_yield(); //Use system calls for scheduling speed
    }
    //We have the lock now!!!!
    mtx->owner = pthread_self();
    return 1;
}

헉...위 코드는 대체 뭘 하는 걸까요? 일단 시작할 때 변수를 초기화하여 unlock된 상태로 가지고 있습니다. Atomic Compare and Exchange는 대부분의 modern architecture 지원하는 instruction입니다. 이 operation의 pseudo code는 아래와 같습니다.

int atomic_compare_exchange_pseudo(int* addr1, int* addr2, int val){
    if(*addr1 == *addr2){
        *addr1 = val;
        return 1;
    }else{
        *addr2 = *addr1;
        return 0;
    }
}

위 작업은 모두 atomic하게 이루어집니다. 즉 인터럽트를 받지 않는 operation입니다. 그렇다면 weak part는 뭘 뜻할까요? atomic instruction들은 spurious failure(가짜 실패??)을 하기 쉽습니다. atomic function에는 strong part와 weak part 의 두 버전이 존재하는데, weak가 실패하는 일에 strong은 성공할 수도, 실패할 수도 있습니다. weak를 사용하는 이유는 더 빠르고 loop안에 있기 때문입니다. 즉 계속 spinning하고 있기 때문에 약간 더 자주 실패해도 문제가 없다는 것입니다.

메모리 순서에 대한 문제는 어떨까요? 이전에 이야기 했던 memory fence가 여기에 사용됩니다. 더 이상은 이 course의 범위를 벗어나므로 자세히 알아보진 않겠지만, 더 알고 싶다면 

https://gcc.gnu.org/wiki/Atomic/GCCMM/AtomicSync

이 링크를 살펴보세요.

while loop안에서 lock을 얻는데 실패했습니다. 그러고 0으로 reset하여 unlock하고 잠시동안 sleep했습니다. sleep이 끝나면 다시 lock을 얻기 위해 시도합니다. 일단 성공적으로 swap이 일어나면, critical section에 진입한 것입니다. unlock method를 위한 현재 스레드를 mutex의 주인으로 설정하고 성공적으로 반환합니다.

Atomic으로 작업하는 것을 완전히 신용하지 못할 때 어떻게 mutual exclusion을 보장할 수 있을까요? 스레드가 성공적으로 lock을 UNLOCKED(0)으로 예측해서 LOCKED(1) 상태로 바꿔준다면 승자로 간주됩니다. 이것을 어떻게 수행할까요?

int mutex_unlock(mutex* mtx){
    if(unlikely(pthread_self() != mtx->owner)){
        return 0; //You can't unlock a mutex if you aren't the owner
    }
    int_least8_t one = 1;
    mtx->owner = UNASSIGNED_OWNER;
    //Critical section ends after this atomic
    //Also this may fail, but that is fine
    if(!atomic_compare_exchange_strong_explicit(
                &mtx->lock, 
                &one, 
                UNLOCKED,
                memory_order_acq_rel,
                memory_order_relaxed)){
        //The mutex was never locked in the first place
        return 0;
    }
    return 1;
}

api를 만족시키기 위해서 mutex에 진입하기 전까지 mutex를 unlock할 수 없습니다. 그러고 나면 critical section은 atomic 이후에 존재하므로 mutex owner를 할당해제해야합니다. block되지 않길 원하므로 (pthread_mutex_unlock은 block되지 않습니다)strong exchange를 사용해야합니다. mutex가 locked되어 있다고 예측하고 있으므로, 이 mutex를 swap해 unlock해주어야 합니다. 만약 swap이 성공적으로 이뤄진다면 mutex가 unlock됩니다. 만약 swap이 일어나지 않으면 mutex는 UNLOCKED이므로, UNLOCKED에서 UNLOCKED로 스위칭이 되기 때문에 unlock을 차단하지 않도록 유지합니다.