[운영체제] 병행성 2 (Concurrency)

 모든 코드를 병렬로 동작시킬 수는 없다. 싱글턴, 연결 리스트, 경쟁 자원 등을 사용하는 코드라면 예상치 못 한 결과가 발생할 수 있다. 이 경우엔 atomic 을 보장해야 한다. 그 중에서 mutex(mutual exclution) 를 위한 lock 을 구현하는 방법에 대해 살펴본다.

 lock 과 unlock 사이에는 atomic 을 보장해야 한다. critical section 에 들어간 스레드를 이 lock 의 owner 라고 부른다. lock 의 owner 가 존재할 때 다른 스레드는 들어갈 수 없다.

 가장 간단한 접근 방법으로 lock 이라는 자료구조에 flag 라는 필드가 있다고 가정해 보자. flag 가 0이면 lock 의 소유자가 없는 것이고, flag 가 1이면 누군가가 lock 을 갖고 있는 것이다. 만약 flag 가 1이라면 0이 될 때까지 무한 루프를 돈다. 이 방법은 불가능하다. flag 값을 초기화하는 과정에서 context switching 이 발생할 수 있기 때문이다. flag 값을 atomic 하게 초기화할 수 있는 방법이 소프트웨어만으로는 없기 때문에 하드웨어의 지원이 필요하다. 참고로 flag = 1; 과 같은 연산을 하기 위해서는 mov eax [flag]; mov eax 1; mov [flag] eax 와 같이 세 번의 연산이 필요하다. 사실 어셈블리 잘 모른다. 아님 말고.
 하드웨어는 atomic instruction 들을 지원한다. 이것을 이용해 lock 을 구현할 수 있다.
 그리고 위 방법에 또 하나의 문제가 있다. lcok 을 갖지 못 한 스레드는 아무 일도 하지 않는데 무한 루프를 돌면서 CPU 자원을 낭비한다.

 lock 을 구현하려면 세 가지 조건을 만족해야 한다.

• mutual exclution : critical section 에는 반드시 하나의 스레드만 존재해야 한다.
• progress : 아무도 lock 을 잡고 있지 않다면 누군가는 잡아야 한다.
• bounded wating : 누군가 unlock 을 했고, unlock 을 기다리고 있는 스레드가 있다면 이 스레드가 들어갈 수 있어야 한다.

atomic instruction 을 이용하는 방법은 무엇일까?

x86 에서는 Test And Set 을 지원하고 가장 많이 사용된다. 아까 변수 초기화를 하기 위해선 값을 가져오고, 그 값을 변경하고, 값을 대입하는 세 가지 단계로 이루어진다고 했는데, Test And Set 이 이 과정을 atomic 하게 해 준다. Test And Set 의 코드는 다음과 같다.

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

 코드 하이라이팅이 C++ 기준으로 되어 있는데, C 라고 생각하면 되고 new 는 키워드가 아닌 변수 이름으로 사용한 것이다. 변수와 초기화할 값을 받아서 변수의 값을 바꿔주고, 원래 값을 반환해 준다. 후위 연산자와 비슷하다. 기존에 flag 를 이용한 lock 을 다음과 같이 구현할 수 있다.

typedef struct {
    int flag;
} lock_t;

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

 기존에 flag 에 있던 값이 1이라면 while 조건이 참이고 flag 에 있던 값이 0이라면 while 문을 탈출하게 된다. 무한 루프를 도는 이런 형태의 lock 을 spin lock 이라고 한다.

 위에서 구현한 spin lock 평가

• mutual exclution : O
• fairness : X, 여러 개의 스레드가 unlock 을 기다리고 있을 때 모든 스레드가 lock 을 받을 수 있다는 보장이 없다.
• performance : X, while 문을 돌며 cpu 를 차지하고 있기 때문에 오버헤드가 크다.

 spin 을 하지 않고도 lock 을 구현하는 방법이 있지만, 만약 빠른 시간 내에 lock 을 얻을 수 있다면 spin lock 이 더 효율적이다.

 현대 CPU 에서는 파이프라인(컴퓨터 구조)을 이용하기 때문에 CPU 에 대한 접근이 순서대로 이루어지지 않는다. 그래서 어떤 instruction 을 atomic 으로 만들고 싶으면 명령어 앞에 lock 을 붙여준다. (lock inc eax) x86 에서 TestAndSet 은 xchg (xchg eax, [addr])를 사용하면 된다. 이 instruction 은 두 값을 교환한다. 이 연산을 이용해서 스핀락을 구현할 수 있다.

 atomic instruction 을 사용하면 오버헤드가 크다. 특히 멀티 코어 CPU 에서는 더 크다. 캐시가 성능의 큰 부분을 차지하는데, 하나의 코어가 lock 을 갖고 메모리에 있는 값을 바꾸면 다른 코어의 캐시에서 갖고 있는 값은 잘못된 값이 되기 때문에 다시 읽어와야 한다. 따라서 멀티 코어 시스템에서 성능을 높이기 위해서는 락을 사용하는 부분을 줄여야 한다.

 다른 CPU 에서는 CompareAndSwap, FetchAndAdd 라는 명령어를 지원하는 경우도 있다. FetchAndAdd 를 이용하면 ticket lock(fairness 보장) 을 구현할 수 있다. load linked and store conditional, (이중 루프)소프트웨어적으로 락을 구현하는 경우도 있다.

 기존의 spin lock 의 경우 무한루프를 돌기 때문에 성능 이슈가 있다. 성능을 높이기 위해서는 운영체제의 지원이 필요하다. 간단한 접근 방법으로는 루프가 시작되면 yield 하는 방법이 있지만 이 방법은 context switching 이 너무 많이 일어나고 starvation 문제가 있다. 결국 이 접근 방법으로는 해결한 것이 없다.

 그래서 Queue 를 이용하여 해결할 수 있다. 락을 얻지 못 한 경우 대기열(queue)에 넣고 ready queue 에서는 뺀다. 다시 말하면 lock 을 관리하는 별도의 queue 에 넣고, ready queue 에서는 뺀다는 얘기이다. 대기열에 들어간 스레드는 unlock 을 기다린다.

park() : 스스로를 wait queue 로 보낸다.
unpark(threadID) : wait queue 에서 ready queue 로 보낸다.

typedef struct lock_t {
    int flag;
    int quard;
    queue_t *q;
} lock_t;

void lock(lock_t *m) {
    while(TestAndSet(*m->quard, 1) == 1) ;
    if (m->flag == 0) {
        m->flag = 1;
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park();
    }
}

 먼저 guard 값을 spin 을 통해 얻어 flag 에 대한 접근을 보장받는다. flag 를 얻지 못 하는 경우 스스로를 queue 에 넣고 sleep 상태에 들어간다. guard 를 얻지 않고 바로 flag 에 접근하면 비효율적이다. 빠른 시간 안에 lock 을 얻을 수 있는 경우에도 wait queue 에 들어가기 때문이다.

void unlock(lock_t *m) {
    while(TestAndSet(&m->quard, 1) == 1) ;
    if(queue_empty(m->q))
        m->flag = 0;
    else 
        unpark(queue_remove(m->q)) ;
    m->quard = 0;
}

 unlock 을 하는 경우에도 gaurd 를 통해 flag 접근에 대한 보장을 받는다. queue 가 비어 있다면 flag 를 0으로 만들어 주고, 만약 대기 중인 스레드가 있다면 그 스레드를 깨워(unpark) 준다. queue 에 무언가 있는데 unpark 해 주지 않는다면 그 스레드는 영원히 실행되지 않을 수도 있다.

 m->flag = 0 직전에 누군가 park 하면 이 스레드를 깨워줄 스레드가 존재하지 않는 문제가 발생할 수 있다는데, guard 값으로 해결된 거 아닌가? 하는 의문이 든다. 솔라리스에서는 setpark() 를 추가하여 setpark 와 park 사이에 누군가 unlock 을 했다면 sleep 상태로 들어가지 않는다.

 park 와 unpark 는 리눅스에서는 futex_wait(address, expected) (값이 다르면 그대로 리턴) 과 futex_wake(address) 로 구현되어 있다.

 spin lock 은 루프를 돌기 때문에 오버헤드가 크고 wait 를 이용한 lock 의 구현은 wait 에서 lock 이 깨어나는 데까지 너무 오래 걸린다. 따라서 처음에는 spin 을 돌다가 일정 시간이 지난 후에도 lock 을 잡지 못 하면 두 번째 phase 로 넘어가 sleep 한다.