futex

Yield 하는 것 까지는 좋지만, 단순히 양보를 할 경우에는 CPU를 점유할 쓰레드에 대한 선택을 스케줄러에게만 맡기게 된다.

스케줄러는 어떤 쓰레드가 락을 풀어야하고 어떤 쓰레드가 대기 중인지에 대한 추적을 하지 않기 때문에, 경우에 따라 특정 쓰레드는 계속 양보만 하게 되는 starvation 현상이 발생할 수 있다.

여러 쓰레드가 락에 대기하고 있을 경우, 그 다음으로 스케줄링 되고 락을 획득할 쓰레드를 운영체제가 컨트롤 할 수 있어야 하는데, 이를 위해 큐를 사용한다.

큐를 사용하기에 앞서, 우선 락 구조체 역시 아래처럼 변경된다.

typedef struct __lock_t {
    int flag;
    int guard;
    queue_t* q;
}

락의 현재 상태를 표시하는 기존의 플래그값에, 추가적으로 어떤 쓰레드가 락을 잠그고 있는지(풀고 있는지)를 표시하기 위한 guard라는 또다른 작은 락이 추가된다.

락을 요청했지만 얻지 못한 쓰레드들은 q 에 추가되며, 락을 가지고 있던 쓰레드가 unlock을 할 경우에는 운영체제가 이 큐에서 쓰레드를 하나 뽑을 수 있게 된다.

쓰레드가 큐에 들어가기 위해서는 락의 현재 상태 flag 를 확인하고 조건에 따라 분기되는데, 이러한 로직을 위해 Test 부분과 Set 부분이 다시 아토믹하지 않게 나뉘게 된다.

이 때 인터럽트가 걸리면서 발생할 수 있는 경쟁조건을 해결하기 위해 추가적인 작은 guard 를 둘 뿐이며, 자세한 코드 설명은 생략한다.

guard를 위한 크리티컬섹션은 락 구현에서 몇 줄 안되는 코드밖에 되지 않기 때문에, 유저 프로그램을 잠그는 전체 락보다 작다.

즉 멀티프로세서 환경에서도, 다른 프로세서에서 실행되는 쓰레드가 guard가 풀리기를 대기하는 스핀 시간이 충분히 예측 가능하고 기다릴만 하다는 뜻이다.

결국 운영체제가 큐를 관리함으로써 starvation 현상을 제거할 수 있게 된다.

리눅스에서는 이런 waiting queue 방식으로 구현되어있는 futex를 지원한다.

futex는 정수 값 하나를 사용하는데, 최상위 비트의 값을 통해 락의 사용중 여부(flag)를 표시하고, 나머지 비트들로는 락을 요청한 대기중인 쓰레드의 수를 표현한다.

최상위 비트가 1인 경우 락을 사용한다는 표시이기 때문에, 값이 음수일 경우 락이 사용중이라는 뜻이 된다.

void mutex_lock(int* mutex)
{
    // 쓰레드별로 스택에 관리하는 지역변수, 락의 상태 캐싱
    int v;
    // 락 요청해보기
    if(atomic_bit_test_set(mutex, 31) == 0)
    {
        return;
    }
    // 락에 대기하겠다고 표시
    atmoic_increment(mutex);
    while(1)
    {
        // 이 사이에 인터럽트가 걸려서 unlock 될 수 있음
        // 혹시 모르니 락을 한번 더 요청
        if(atomic_bit_test_set(mutex, 31) == 0)
        {
            // 락을 얻을 경우 대기자수 -1
            atomic_decrement(mutex);
            return;
        }
        // 이 사이에 인터럽트가 걸려서 unlock 된 경우
        // 락이 풀려있기 때문에 다시 반복문으로 복귀하여 락 요청
        v = *mutex;
        if(v >= 0)
        {
            continue;
        }
        // 이 사이에 인터럽트가 걸려서 unlock 된 경우
        // 스택에 캐싱해놓았던 v와 락 상태가 달라지면 락이 풀렸다는 뜻
        if(v == *mutex)
        {
            futex_wait(mutex, v);
        }
    }
}

void mutex_unlock(int* mutex)
{
    // 락에 대기하고 있는 쓰레드가 없을 경우에는 락 해제후 바로 종료
    if(atomic_add_zero(mutex, 0x80000000))
    {
        return;
    }
    // 락에 대기하고 있는 쓰레드가 있으면, 해당 쓰레드를 깨워줌
    // 깨워진 쓰레드는 앞서 futex_wait 이후부터 다시 실행
    futex_wake(mutex);
}