[운영체제] 8. Lock

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

 

Lock

Lock은 thread 간 데이터 무결성을 보장하기 위해 작업을 원자적으로(끊기지 않게) 수행하게끔 하는 아이디어다.

프로세스가 진행되는 도중 각종 interrupt가 발생할 수 있기 때문에 이를 방지하는 역할이다.

Lock을 사용하려면 Lock이 필요한 코드의 시작점과 끝점에 lock(&mutex)와 unlock(&mutex)를 해주면 된다.

 

Lock을 사용하기 위해선 하드웨어의 지원과  OS의 지원이 필요하다.

 

Evaluating Locks

 

효율적인 lock을 위해 세가지를 고려해야 한다.

- mutual exclusion : 상호 배제를 제공하는지

- fairness : 여러 스레드가 lock을 획득하려 할 때 공평하게 lock을 얻을 수 있는지 (=no starvation)

- performance : lock을 생성하고 사용하는 것에 따른 time overhead가 너무 크지 않는지

 

Controlling Interrupts

 

명령어가 원자성을 갖지 못하는 이유는 interrupt 때문이다. 스레드가 임계 영역에 접근중일 때, interrupt를 받지 않게끔 lock을 구현한다면 concurrency 문제가 없을 것이다.

하지만 위 방법은 많은 문제를 가지고 있다.

먼저 스레드가 interrupt를 키고 끌 권한이 있어야 한다. 하지만 이렇게되면 프로그램의 신뢰성을 보장하지 못한다.

또한 멀티 프로세서에서는 작동하지 않으며,  인터럽트를 무시한다는 것이 많은 문제를 초래할 수 있다. 마지막으로 인터럽트를 활성화하고 비활성화하는 것은 느리기때문에 이를 lock마다 사용하는건 비효율적이다.

 

A Failed attempt: just using loads/stores

 

책에서 flag 하나로 lock을 구현한 사례를 보여주지만, 이는 실패한 사례이다.

flag가 0이면 lock이 없고 1이면 lock을 가진 상태라 정의하자.

lock을 생성할 때 while(mutex->flag == 1) 일 때 무한루프를 돌다 while 문을 벗어나면 mutex->flag = 1;을 한다.

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex) {
	mutex->flag = 0;
}

void lock(lock_t *mutex) {
	while(mutex->flag==1)
    ; //spin-wait 발생
    mutex->flag = 1;
}

void unlock(lock_t *mutex) {
	mutex->flag = 0;
}

이는 두가지 문제점이 있다. 첫번째로 어떤 스레드가 lock을 획득한 시점부터 다른 스레드들이 모두 lock을 얻지 못하고 무한루프를 돈다(spin-wait). 또한, 어떤 스레드1에서 flag를 1로 바꾸기 직전에 interrupt가 발생하여 context switch가 되고 다른 스레드2에서 lock을 획득한다면, 다시 스레드 1로 context switch가 됐을 때 mutex->flag = 1;부터 실행되어 2개의 스레드가 lock을 가지게 된다.

 

이러한 문제들로 인해 원자적 연산을 지원하는 하드웨어를 이용하여 lock을 구현하는 방법을 고안하게 된다.

 

Test and set

 

/* implemented in CPU as hardware */

int TestAndSet(int *ptr, int new) {
    int old = *ptr;
    *ptr = new;
    return old;
}

해당 코드는 intel 등의 CPU에서 setting되어진 hardware instruction이므로, 원자적으로(=끊기지 않고) 작동한다.

이 명령어는 이전 ptr이 가리키던 값을 반환하고 현재 ptr을 새로운 값으로 설정한다.

이를 활용해 아래와 같이 spin-wait을 구현할 수 있다.

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *lock) {
	// 0 indicates that lock is available, 1 that is held
    lock->flag = 0;
}

void lock(lock_t *lock) {
    // TestAndSet의 반환값이 1일 경우에만 while 탈출.
    while(TestAndSet(&lock->flag, 1) == 1)
    	; // spin-wait
    // while문을 벗어나면 lock flag를 1로 수정하여 lock을 얻음.
    lock->flag = 1;
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

이전과 같은 flow를 같지만 lock은 TestAndSet으로 인해 원자적으로 동작할 수 있다.

이렇게 spin-wait을 사용하는 lock을 spin lock이라 한다..

 

Compare And Swap

 

CAS도 마찬가지로 원자적인 Hardware instruction이다. CAS는 쉽게 설명하면 변수의 예상 값과 실제 값을 비교하여 값이 일치하면 실제 값을 새로운 값으로 교체한다. 그 뒤 실제 값을 return한다.

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

CAS를 통한 spin lock은 아래 부분만 바꾸면 된다.

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

CAS는 TestAndSet에서 예상값과 비교하는 단계가 추가되어 Lock-Free Synchronization(멀티스레딩 시 각 스레드를 block하지 않고 데이터의 동기화를 보장)을 구현할 때 사용하며, Test and Set보다 더 확장성이 있고 강력한 instruction이다.

 

위에서 언급한 3가지 평가 기준으로 위 두 lock을 확인해보자.

1. mutual exclusion - hardware instruction이므로 가능

2. fairness - 공정성에 관한 rule은 없기에 보장하지 않음.

3. performance - spin-wait가 CPU를 낭비하기 때문에 좋지 않음. 특히 single CPU에서, lock이 선점된 동안 다른 스레드는 계속 spin wait하고 있으므로 비효율적.

 

위에서 mutual exclusion 문제는 해결됐다하더라도, 단일 프로세서에서 스케줄러가 없다면 spin-wait으로 인한 cpu 독점이 발생할 수 있다. 이를 해결하기 위한 스케줄링이 필요하다.

 

Fetch-And-Add

 

이는 비유하자면 여러 Thread에게 순서대로 티켓을 뽑게 하는 방법으로, 티켓을 뽑았을 때 그 변수를 저장하고 실행이 끝난 뒤 +1 시켜준 뒤 원래 값을 반환한다. 마찬가지로 원자적인 hardware instruction이다.

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

 

Fetch and add를 활용한 lock을 Ticket Lock이라 하는데, 여러 스레드가 공유자원에 대한 액세스를 순서대로 얻을 수 있도록 한다. 티켓 번호를 통해 스레드들이 순서대로 임계 영역에 access하도록 한다. 그 과정은 아래와 같다.

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)
        ; // lock의 turn과 자신의 티켓이 같을 때까지 spin
}

// unlock을 하게 되면 turn+1을 하여 특정 스레드에게 lock 획득 권한을 준다.
void unlock(lock_t *lock) {
    lock->turn = lock->turn + 1;
}

설명하자면 lock을 가진 스레드가 unlock하면 turn값이 1씩 증가하여 해당 turn값을 가진 스레드가 lock을 얻게 된다.

따라서 이는 모든 스레드가 언젠가는 lock을 얻을 수 있으므로 fairness하다.

하지만 performance 측면에서 여전히 spin wait이 존재하므로 비효율적이다.

spinning을 피하기 위해 OS의 지원을 받는 방법이 있다.

 

Just Yield

 

그냥 양보하는 방법이다. spin 중인 스레드가 CPU를 포기하고 다른 스레드가 실행할 수 있도록 OS에서 제공하는 yield() syscall을 사용한다. yield()는 running state를 ready state로 변경하는 syscall이다.

스레드가 두개만 있을 때 이 방법은 적합하지만, 스레드가 아주 많다면 context switch 비용 소모도 크고, 또한 fairness를 보장할 수 없어 starvation이 여전히 발생할 수 있다. (ex. 100번까지 스레드 중 1번만 반복해서 lock을 가질 수 있음)

이를 해결하기 위해 Queue를 사용한다.

 

Using Queue: Sleeping Instead of spinning

 

현재 lock을 가진 스레드가 unlock한 후 lock을 얻을 스레드를 정해주는 방식이다. 이때 lock을 얻을 스레드를 추적하기 위한 Queue와 OS 지원이 필요하다.

이를 구현하기 위해 Solaris에서 사용하는, 스레드를 절전모드로 전환하는 park()와 깨우는 unpark()를 사용할 것이다.

스레드가 lock을 획득하지 못하면 park()하고 lock을 가진 스레드가 unlock을 호출하면 unpark()로 특정 스레드를 깨운다.

typedef struct __lock_t {
    int flag;
    int guard;
    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) {
    // guard가 0이 될 때까지 spin
    while(TestAndSet(&m->guard, 1) == 1)
        ;
    
    // guard가 0이고 flag가 0이면 lock을 얻어도 되는 시점
    if (m->flag == 0) {
        m->flag = 1;
        m->guard = 0;
    // guard는 0이지만 flag가 1이면 queue에 자신을 추가후 대기상태로
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park()
    }
}

void unlock(lock_t *m) {
    // guard가 0이 될 때까지 spin
    while(TestAndSet(&m->guard, 1) == 1)
        ;
    // 만약 queue가 비었다면 flag = 0
    if (queue_empty(m->q))
        m->flag = 0;
    // queue가 빈 것이 아니라면 queue에서 하나를 run상태로 수정
    else
        unpark(queue_remove(m->q));
    m->guard = 0;
}

 

위 방법의 한계는 1. testandset을 사용하기에 spin wait을 완전히 해결하지 않았다는 점과 2. wakeup / waiting race가 발생한다는 점이다.

 

위 코드의 lock에서 queue에 먼저 자신을 넣은 뒤 park()를 호출하는데, queue에 넣자마자 unpark()를 한 뒤 park()가 실행된다면 queue에 자신이 없기 때문에 영원히 대기 상태에 머무는 문제가 발생한다. 이를 wakeup / waiting race라 한다. 

이를 해결하기 위해 setpark()이라는 syscall이 있다. setpark()은 park() 직전임을 알리는 syscall로, 위의 코드에서 queue_add() 바로 밑에 들어갈 것이다. 이를 호출한 뒤 unpark()이 먼저 호출되면 바로 스레드를 return하여 lock을 획득하게 한다. 

 

이렇게 Queue와 park(), unpark(), setpark()를 사용한 lock을 평가해보자면

mutual exclusion(correctness) - 한번에 하나의 스레드만 임계 영역에 진입하고 다른 스레드는 대기 상태이기에 보장된다.

Fairness - 스레드들이 큐에 대기하고, 큐 순서대로 lock을 얻어 임계 영역에 진입하므로 보장된다.

performance - context switch overhead가 있으나 spin-wait와 비교하면 훨씬 효율적이므로 보장된다.