16. Locks

앞서 mutex와 condition variableㅇ로 OS가 제공해주는 락함수를 알아보았다.

락의 효과

앞서 mutex와 condition variableㅇ로 OS가 제공해주는 락함수를 알아보았다. 이번엔 mutex를 어떻게 구현해야 하는지를 알아보도록 하자. 먼저 락을 통해 우리가 무엇을 제공해야 하는지 3가지가 있다.

• Mutual exclusion (상호배제) : 하나의 쓰레드만 임계구역에 접근하게 하는가
• Fairness (공정성) : 쓰레드들이 락 획득에 대해 공정한 기회가 주어지는가
• Performance (성능) : 락 사용이 시간적으로 오버헤드가 나진 않는가

✔️ 초기 Interrupts

초창기 단일 프로세스 시스템에서는 인터럽트를 비활성화하는 방식을 사용했다. 단순하지만 프로세스가 독점할 수 있고 멀티 프로세서에서는 사용이 불가능하다.

void lock(){
    DisalbeInterrupts();
}
void unlock(){
    EnalbeInterrupts();
}

✔️ Spin Lock with Loads/Stores

flag변수를로 확인하여 락의 사용 여부를 확인한다. 하지만 이방법은 spin wait으로 시간을 낭비하고, while문이 atomic하지 않다는 문제점이 있다.

typedef struct __lock_t { int flag; } lock_t;
void init(lock_t *mutex){
    mutex -> flag = 0; //0이면 사용가능, 1이면 사용 불가능
}
void lock(lock_t *mutex){
    while(mutex->flag == 1) //플레그를 검사 (Test)
    ;   //spin-wait
    mutex->flag = 1;    //플래그를 1로 설정 (Set)
}
void unlock(lock_t *mutex){
    mutex -> flag = 0;
}

✔️ Spin Lock with Test-and-Set

앞선 방법의 Test와 Set까지를 원자적으로 수행하는 TestAndSet 어셈블리 명령어를 제공한다.

int TestAndSet(int *old_ptr, int new){
    int old = *old_ptr; //old_ptr의 이전값을 가져옴
    *old_ptr = new; //새 값을 저장
    return old; //이전 값 반환
}

typedef struct __lock_t { int flag; } lock_t;
void init(lock_t *lock){
    lock -> flag = 0; //0이면 사용가능, 1이면 사용 불가능
}
void lock(lock_t *lock){
    while(TestAndSet(&lock -> flag, 1) == 1);
}
void unlock(lock_t *lock){
    lock -> flag = 0;
}

지금까지는 기초적인 락의 형태로, 락을 획득할때 까지 CPU사이클을 소모해야 했다. 하지만 이 방식은 단일 프로세서에서 선점형 스케쥴러가 아니라면 쓰레드가 CPU를 독점할 수 있기 때문에 사용이 불가능 하다.

✔️ Spin Lock with Compare-and-Swap

Compare-and-Swap도 Test-and-Set과 같은 instruction인데, 메모리 영역에 대해 기대값과 같으면 새값으로 바꾸는 명령어 이다.

int CompareAndSwap(int *ptr, int expected, int new){
    int actual = *ptr;  
    if(actual == expected)  //기대값과 같으면 
        *ptr = new; //새값으로 바꿈
    return actual;  //이전 값 반환
}

void lock(lock_t *lock){
    while(CompareAndSwap(&lock -> flag, 0, 1) == 1);
}

이구현은 Test-and-Set과 거의 동일하다. 상호배제는 제공하지만 공정성과 성능에서는 좋지 않다.

✔️ Ticket Locks

마지막 하드웨어 기반의 기법은 Fetch-and-Add이다. 이전 기법들과 다른점은 모든 쓰레드들이 각자 순서에 따라 진행된다는 것이다. 이 방법으로 공정성을 보장해 줄 수 있다.

int FetchAndAdd(int *ptr){
    int old = *ptr; //old_ptr의 이전값을 가져옴
    *ptr = old + 1; //새 값을 저장
    return old; //이전 값 반환
}

typedef struct __lock_t { int flag; int turn; } lock_t;
void lock_init(lock_t *lock){
    lock->ticket = 0;
    lock->turn = 0;
}
void lock(lock_t *lcck){
    int myturn = FetchAndAdd(&lock -> ticket);  //ticket을 1 증가
    while(lock -> turn != myturn)
    ;
}
void unlock(lock_t *mutex){
    FetchAndAdd(&lock -> turn); //turn을 1 증가
}

Ticket lock을 통해 상호배제와 공정성을 해결했다. 하지만 아직 spin을 사용하기 때문에 성능의 문제점이 있다.

✔️ Locks with Queues

성능을 개선하기 위해 어떤 쓰레드가 락을 획득할지를 제어할 수 있어야 한다. 이를 위해 운영체제는 큐를 이용해 대기 쓰레드들을 관리한다. 두개의 함수가 있는데 park()는 호출하는 쓰레드를 잠재우는 함수고, unpark(threadID)은 threadID라는 특정 쓰레드를 깨우는 함수다. 그리고 앞서 배운 Test-and-Set을 활용하여 이 기법을 사용해 보자.

typedef struct __lock_t { 
    int flag;   //락 변수
    int guard;  //flag와 큐의 동작을 스핀락으로 보호하는데 사용
    queue_t *q; 
} lock_t;
void lock_init(lock_t *m){
    m->flag = 0;
    m->guard = 0;
    queue_init(m->q);
}

void lock(lock_t *m){
    while(TestAndSet(&m -> quard, 1) == 1); //guard락 획득
    if(m -> flag == 0){ //guard는 1, flag는 0인 상태
        m->flag = 1;    //락 획득
        m->guard = 0; //guard를 풀어줌
     }else{ //guard는 1, flag도 1인 상태
        queue_add(m->q, gettid());
        m->guard = 0;   //다른 쓰레드들이 flag를 확인하게 하기 위해 guard를 풀어줌
        park(); //
     }
}
void unlock(lock_t *m){
    while(TestAndSet(&m -> quard, 1) == 1); //guard락 획득
    if(queue_empty(m->q){   //잠든 쓰레드가 없는 경우
        m->flag = 0;
     }else{ //guard는 1, flag도 1인 상태
        unpark(queue_remove(M->q);  
     }
     m->guard = 0;
}

하지만 위의 코드의 lock에는 문제점이 있다. lock에서 park을 하기 전에 다른 쓰레드로 CPU가 할당되어 다른 쓰레드가 그 락을 해제하면 아까 park을 하려한 쓰레드는 park을 마저 수행하여 잠들어버리며 깨어날 방법이 없어진다. 그래서 setpark이라는 시스템콜을 사용하여 lock함수를 개선시킬 수 있다. setpark()은 호출된 이후 park호출전 다른 쓰레드가 이 쓰레드에 대해 unpark을 했었다고 하면 setpark이 이를 인지하고 재우지 않게 한다. (unpark을 했는지는 커널 내 특정 변수에 저장되어 atomic하게 업데이트된다.)

void lock(lock_t *m){
    while(TestAndSet(&m -> quard, 1) == 1); //guard락 획득
    if(m -> flag == 0){ //guard는 1, flag는 0인 상태
        m->flag = 1;    //락 획득
        m->guard = 0; //guard를 풀어줌
     }else{ //guard는 1, flag도 1인 상태
        queue_add(m->q, gettid());
        setpark();
        m->guard = 0;   //다른 쓰레드들이 flag를 확인하게 하기 위해 guard를 풀어줌
        park();
     }
}

지금까지 락의 구현의 방법들에 대해 살펴보았다. 각각의 방법들을 평가하여 정리해 보았다.