12. Concurrency - Locks

The Classic Example

• 대표적인 예시는 은행 계좌 출금 문제다.
• 어떤 계좌에 1,000,000원이 있다고 하자.
• 두 사람이 동시에 ATM에서 각각 100,000원을 출금하면, 최종 잔액은 800,000원이 되어야 한다.
• 하지만 아래 코드가 동시에 실행되면 문제가 생길 수 있다.

int withdraw(account, amount)
{
    balance = get_balance(account);
    balance = balance - amount;
    put_balance(account, balance);
    return balance;
}

The Real Example

• 실제 machine instruction 수준에서도 같은 문제가 생긴다.
• 예를 들어 전역 변수 g를 증가시키는 코드를 생각해보자.

extern int g;

void inc()
{
    g++;
}

Sharing Resources

• local variable은 보통 thread 간 공유되지 않는다.
  • local variable은 stack에 저장된다.
  • 각 thread는 자기 stack을 가진다.
  • 따라서 다른 thread의 stack에 있는 local variable pointer를 넘기거나 저장하면 위험하다.
• global variable은 thread 간 공유된다.
  • static data segment에 저장된다.
  • 같은 process 안의 모든 thread가 접근할 수 있다.
• dynamic object도 thread 간 공유될 수 있다.
  • heap에 저장된다.
  • pointer를 통해 여러 thread가 접근할 수 있다.
• process 사이에서도 shared memory를 사용하면 memory를 공유할 수 있다.
• 즉 concurrency 문제는 주로 다음에서 발생한다.
  • global variable
  • heap object
  • shared memory
  • kernel 내부 shared data structure

Synchronization Problem

• concurrency는 non-deterministic result를 만들 수 있다. thread scheduling이 programmer의 직접 통제 아래 있지 않기 때문이다. 두 개 이상의 thread가 shared resource에 접근하고, 그중 하나 이상이 write를 하면 race condition이 생길 수 있다.
• race condition(경쟁 상태)
• 이런 bug는 debugging하기 어렵다.
  • 실행할 때마다 재현되지 않을 수 있다.
  • print문을 넣으면 timing이 바뀌어서 bug가 사라질 수도 있다.
• 따라서 shared resource 접근을 제어하기 위한 synchronization mechanism이 필요하다.
• synchronization은 concurrency를 제한해서 correctness를 지키는 방식이다.

Concurrency in the Kernel

• concurrency는 user-level program에서만 생기는 것이 아니다.
• kernel 안에서도 concurrency가 생긴다.
• kernel에서 동시에 실행될 수 있는 흐름은 다음과 같다.
  • system call handlers
  • interrupt handlers
  • background kernel threads
• 예를 들어 어떤 system call handler가 kernel data structure를 수정하는 중에 interrupt handler가 같은 data structure에 접근할 수 있다.
• 또는 multi-core 환경에서는 여러 CPU가 동시에 kernel code를 실행할 수 있다.
• 따라서 kernel 내부에서도 shared resource를 보호해야 한다.
• OS kernel에서 lock이 중요한 이유가 여기에 있다.

Critical Section

• critical section: shared resource에 접근하는 코드 영역
• 보통 shared variable이나 shared data structure를 읽거나 수정하는 코드가 critical section이 된다.
• critical section에는 mutual exclusion이 필요하다.
• mutual exclusion은 다음을 의미한다.
  • 한 번에 하나의 thread만 critical section에 들어갈 수 있다.
  • 다른 thread들은 critical section 입구에서 기다려야 한다.
  • 한 thread가 critical section을 빠져나오면 다른 thread가 들어갈 수 있다.
• critical section은 atomic하게 실행되어야 한다.
  • all-or-nothing처럼 보이도록 해야 한다.
  • 중간 상태를 다른 thread가 관찰하면 안 된다.

Locks

• lock은 mutual exclusion을 제공하는 memory object다.
• lock은 보통 두 가지 operation을 가진다.
  • acquire()
    • lock이 free가 될 때까지 기다린다.
    • lock이 free이면 lock을 잡는다.
  • release()
    • lock을 해제한다.
    • 기다리고 있던 thread가 있으면 진행할 수 있게 한다.
• lock 사용 방식은 다음과 같다.

acquire(lock);

/* critical section */

release(lock);

• lock은 처음에는 free 상태다.
• acquire()는 caller가 lock을 얻을 때까지 return하지 않는다.
• lock을 얻은 thread만 critical section에 들어간다.
• lock을 얻지 못한 thread는 기다린다.
• lock을 기다리는 방식은 크게 두 가지다.
  • spin
    • 계속 반복하면서 lock이 풀렸는지 확인한다.
    • spinlock
  • block
    • CPU를 포기하고 잠든다.
    • mutex
• lock의 핵심 보장은 다음이다.
  • at most one thread can hold a lock at a time

Pthread Mutex

• Pthread에서는 mutex를 통해 lock을 사용할 수 있다.
• mutex는 mutual exclusion을 제공하는 대표적인 synchronization primitive다.

int pthread_mutex_init(
    pthread_mutex_t *mutex,
    const pthread_mutexattr_t *mattr
);

void pthread_mutex_destroy(
    pthread_mutex_t *mutex
);

void pthread_mutex_lock(
    pthread_mutex_t *mutex
);

void pthread_mutex_unlock(
    pthread_mutex_t *mutex
);

• pthread_mutex_lock()은 lock을 얻을 때까지 기다린다.
• pthread_mutex_unlock()은 lock을 해제한다.
• Pthread mutex는 사용자 프로그램에서 critical section을 보호할 때 사용한다.

Using Locks

• 은행 계좌 예제에 lock을 적용하면 다음처럼 된다.

int withdraw(account, amount)
{
    acquire(lock);

    balance = get_balance(account);
    balance = balance - amount;
    put_balance(account, balance);

    release(lock);

    return balance;
}

Shared Linked List

typedef struct __node_t {
    int key;
    struct __node_t *next;
} node_t;

typedef struct __list_t {
    node_t *head;
} list_t;

void List_Init(list_t *L) {
    L->head = NULL;
}

void List_Insert(list_t *L, int key)
{
    node_t *new =
        malloc(sizeof(node_t));
    assert(new);

    new->key = key;
    new->next = L->head;
    L->head = new;
}

int List_Lookup(list_t *L, int key)
{
    node_t *tmp = L->head;

    while (tmp) {
        if (tmp->key == key)
            return 1;

        tmp = tmp->next;
    }

    return 0;
}

new->next = L->head;  // L->head 읽기
L->head = new;        // L->head 쓰기

Linked-List Race

• linked list race의 핵심은 다음이다.
  • 두 thread가 같은 old head를 본다.
  • 두 node 모두 old head를 next로 가진다.
  • 하지만 L->head에는 둘 중 하나만 남는다.
• 결과적으로 하나의 insert가 사라진다.
• data structure의 invariant가 깨진다.
• linked list의 invariant는 보통 다음과 같다.
  • head는 list의 첫 node를 가리킨다.
  • 각 node의 next는 다음 node를 가리킨다.
• insert 중간에는 이 invariant가 잠깐 깨질 수 있다.
• 이 중간 상태를 다른 thread가 보면 문제가 생긴다.
• lock은 이런 중간 상태를 다른 thread가 보지 못하게 막는다.

Locking Linked Lists

• linked list를 보호하는 가장 단순한 방법은 list 전체에 lock 하나를 두는 것이다.
• 여기서 잡는 lock은 L->lock이고, 보호 대상은 L->head와 list 구조 전체다.
• lock variable 자체와 protected data를 구분해야 한다. pthread_mutex_lock(&L->lock)은 L->lock을 잡아서 L->head update를 atomic하게 보이게 만드는 것이다.

typedef struct __list_t {
    node_t *head;
    pthread_mutex_t lock;
} list_t;

• insert는 다음처럼 감쌀 수 있다.

void List_Insert(list_t *L, int key)
{
    node_t *new = malloc(sizeof(node_t));
    assert(new);

    new->key = key;

    pthread_mutex_lock(&L->lock);
    new->next = L->head;
    L->head = new;
    pthread_mutex_unlock(&L->lock);
}

• 중요한 것은 lock을 어디부터 어디까지 잡을지 결정하는 것이다.
• 너무 크게 잡으면 안전하지만 parallelism이 줄어든다.
• 너무 작게 잡으면 race condition이 남을 수 있다.

Locking Approach 1: Everything as Critical Section

• 첫 번째 방식은 함수 전체를 critical section으로 보는 것이다.
• 예를 들어 List_Insert() 전체를 lock으로 감싼다.
  • 장점은 단순하고 안전하다.
  • 단점은 필요 이상으로 concurrency를 제한한다.
  • 예를 들어 malloc()이나 assert()까지 lock 안에 넣으면, 실제 shared list를 건드리지 않는 부분까지 serialized된다.
  • 따라서 performance가 나빠질 수 있다.

Locking Approach 2: Critical Section as Small as Possible

• 두 번째 방식은 critical section을 최대한 작게 잡는 것이다.
  • insert에서 실제 shared structure를 건드리는 부분은 다음이다.
    • new->next = L->head
    • L->head = new
• 따라서 이 부분만 lock으로 감쌀 수 있다.
  • 장점은 lock hold time이 짧다.
  • 단점은 어디까지가 shared invariant를 깨뜨리는 부분인지 정확히 알아야 한다.
  • 잘못 줄이면 bug가 생긴다.
  • 즉 critical section을 줄이는 것은 performance에는 좋지만 correctness 판단이 더 어려워진다.

Locking Approach 3: Lookup은?

• insert뿐 아니라 lookup도 생각해야 한다.
• lookup은 list를 읽기만 한다.

int List_Lookup(list_t *L, int key)
{
    node_t *tmp = L->head;

    while (tmp) {
        if (tmp->key == key)
            return 1;
        tmp = tmp->next;
    }

    return 0;
}

• 만약 list에 insert만 있고 delete가 없다면 lookup에는 lock이 없어도 안전할 수 있다.
• 이유는 node가 사라지지 않기 때문이다.
• 하지만 delete가 있다면 lookup 중인 node가 다른 thread에 의해 free될 수 있다.
• 그러면 lookup도 lock이 필요하다.
• 즉 lock이 필요한지는 단순히 read냐 write냐만으로 결정되지 않는다.
• data structure가 어떤 operation을 지원하는지 함께 봐야 한다.

Requirements for Locks

• 좋은 lock은 세 가지 측면에서 평가할 수 있다.

1. correctness
   • mutual exclusion
     • 한 번에 하나의 thread만 critical section에 들어가야 한다.
   • progress 또는 deadlock-free
     • 여러 thread가 critical section에 들어가고 싶어 하면, 그중 하나는 진행할 수 있어야 한다.
   • bounded waiting 또는 starvation-free
     • 기다리는 thread가 언젠가는 lock을 얻을 수 있어야 한다.
2. fairness
   • 각 thread가 lock을 얻을 공정한 기회를 가져야 한다.
3. performance
   • contention이 없을 때 lock overhead가 작아야 한다.
   • contention이 있을 때도 너무 많은 CPU cycle을 낭비하면 안 된다.
   • multi-core 환경에서도 성능이 잘 나와야 한다.

Implementing Locks

• lock 구현 방식은 환경에 따라 달라진다.
• 크게 두 경우를 생각할 수 있다.
  • single-core
  • multi-core
• single-core에서는 interrupt를 막는 것만으로도 critical section을 보호할 수 있다.
• 하지만 multi-core에서는 한 CPU의 interrupt를 꺼도 다른 CPU가 동시에 접근할 수 있다.
• 따라서 multi-core에서는 atomic instruction이 필요하다.
• lock 구현 방식은 크게 다음과 같다.
  • controlling interrupts
  • software-only algorithm
  • hardware atomic instruction

Controlling Interrupts

• single-core 시스템에서는 critical section 동안 interrupt를 disable할 수 있다.

void acquire(struct lock *l)
{
    cli();
}

void release(struct lock *l)
{
    sti();
}

• cli()는 interrupt를 비활성화한다.
• sti()는 interrupt를 활성화한다.
  • interrupt를 끄면 timer interrupt 같은 외부 event에 의해 context switch가 발생하지 않는다.
  • 따라서 single-core에서는 critical section이 중간에 끊기지 않는다.
  • 장점은 단순하다는 것이다.
  • single-processor kernel에서는 유용할 수 있다.
  • 하지만 단점이 크다.
    • user program에게 제공할 수 없다.
    • multi-processor 시스템에서는 충분하지 않다.
    • critical section이 길면 중요한 interrupt가 지연되거나 손실될 수 있다.
    • 현대 CPU에서는 atomic instruction보다 느릴 수 있다.
  • 특히 multi-core에서는 한 core의 interrupt를 꺼도 다른 core는 계속 실행된다.
  • 그래서 multi-core에서는 atomic instruction 기반 lock이 필요하다.

Multicore: Initial Attempt

• multi-core에서 단순히 flag 하나로 spinlock을 만들면 다음처럼 생각할 수 있다.

struct lock {
    int held = 0;
};

void acquire(struct lock *l)
{
    while (l->held);
    l->held = 1;
}

void release(struct lock *l)
{
    l->held = 0;
}

• 이 코드는 직관적으로는 맞아 보인다.
• held가 1이면 기다리고, 0이면 1로 바꿔 lock을 잡는 방식이다.
• 하지만 multi-core에서는 틀릴 수 있다.
• 이유는 다음 두 동작이 atomic하지 않기 때문이다.
  • l->held가 0인지 확인
  • l->held = 1로 설정
• 두 CPU가 동시에 held == 0을 보고 둘 다 held = 1을 실행할 수 있다.
• 그러면 두 thread가 동시에 lock을 잡았다고 생각한다.
• mutual exclusion이 깨진다.
• 따라서 lock 구현에는 read와 write를 하나의 atomic operation으로 묶는 기능이 필요하다.

Software-only Algorithms

• hardware atomic instruction 없이 lock을 구현하려는 algorithm들도 있다.
• 대표적으로 다음이 있다.
  • Dekker’s algorithm
  • Peterson’s algorithm
  • Lamport’s Bakery algorithm
• 이런 알고리즘들은 이론적으로 mutual exclusion을 제공할 수 있다.
• 하지만 실제 OS나 modern multicore 환경에서는 보통 hardware atomic instruction을 사용한다.
• 이유는 구현과 성능, memory ordering 문제가 복잡하기 때문이다.

Hardware Atomic Instructions

• 현대 CPU는 lock 구현을 위해 atomic instruction을 제공한다.
• atomic instruction은 read-modify-write를 indivisible하게 수행한다.
• 대표적인 atomic instruction은 다음과 같다.
  • Test-And-Set
  • Compare-And-Swap
  • Load-Linked / Store-Conditional
  • Fetch-And-Add
• 이런 instruction은 lock 구현의 핵심 building block이다.
• OS의 spinlock도 보통 이런 atomic instruction을 기반으로 구현된다.

Test-And-Set

• Test-And-Set은 memory location의 old value를 읽으면서 동시에 new value로 바꾸는 atomic instruction이다.
• x86에서는 xchg가 비슷한 역할을 한다.
• 개념적으로는 다음과 같다.

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

• 중요한 점은 이 전체 동작이 atomic하게 실행된다는 것이다.
• 즉 두 CPU가 동시에 실행해도 중간에 끼어들 수 없다.
• Test-And-Set을 사용하면 spinlock을 만들 수 있다.

struct lock {
    int held;
};

void acquire(struct lock *l)
{
    while (TestAndSet(&l->held, 1));
}

void release(struct lock *l)
{
    l->held = 0;
}

• lock이 free이면 held는 0이다.
• TestAndSet(&held, 1)은 old value 0을 반환하고, 동시에 held를 1로 만든다.
• old value가 0이면 lock 획득에 성공한 것이다.
• old value가 1이면 이미 누가 lock을 잡고 있으므로 계속 spin한다.

Compare-And-Swap

• Compare-And-Swap, CAS는 old value가 expected value와 같을 때만 new value로 바꾸는 atomic instruction이다.
• x86에서는 cmpxchg가 이에 해당한다.
• 개념적으로는 다음과 같다.

int CompareAndSwap(int *v, int expected, int new)
{
    int old = *v;

    if (old == expected)
        *v = new;

    return old;
}

• CAS를 사용한 lock은 다음처럼 만들 수 있다.

void acquire(struct lock *l)
{
    while (CompareAndSwap(&l->held, 0, 1));
}

• held가 0일 때만 1로 바꾸려고 시도한다.
• old value가 0이면 lock을 얻는다.
• old value가 1이면 누군가 lock을 가지고 있으므로 계속 기다린다.
• CAS는 lock뿐 아니라 lock-free data structure에서도 많이 쓰인다.

Load-Linked and Store-Conditional

• LL/SC는 MIPS, Alpha, PowerPC, ARM 등에서 지원되는 방식이다.
• Load-Linked는 memory에서 값을 읽는다.
• Store-Conditional은 그 사이에 다른 store가 없었을 때만 write에 성공한다.
• 만약 다른 thread나 CPU가 같은 address에 write했다면 Store-Conditional은 실패한다.
• 개념적으로 lock은 다음처럼 만들 수 있다.

void acquire(struct lock *l)
{
    while (1) {
        while (LL(&l->held));

        if (SC(&l->held, 1))
            return;
    }
}

void release(struct lock *l)
{
    l->held = 0;
}

• LL로 lock 상태를 읽고, 비어 있으면 SC로 1을 쓰려고 한다.
• SC가 성공하면 lock을 얻은 것이다.
• 실패하면 누군가 중간에 건드린 것이므로 다시 시도한다.

Basic Spinlocks Are Unfair

• 단순 spinlock은 fairness를 보장하지 않는다.
• lock이 풀렸을 때 어떤 thread가 lock을 얻을지는 scheduler와 timing에 달려 있다.
• 어떤 thread는 계속 lock을 얻고, 어떤 thread는 계속 밀릴 수 있다.
• 즉 starvation이 가능하다.
• 특히 scheduler는 lock의 내부 상태를 모른다.
• scheduler는 어떤 thread가 lock을 기다리는지, 누가 lock holder인지 모른 채 CPU를 배정할 수 있다.
• 그래서 lock을 기다리는 thread를 계속 실행시키고, 정작 lock을 들고 있는 thread는 실행하지 않는 비효율이 생길 수 있다.

Fetch-And-Add

• Fetch-And-Add는 memory 값을 atomic하게 증가시키면서 old value를 반환하는 instruction이다.
• x86에서는 xadd가 이에 해당한다.
• 개념적으로는 다음과 같다.

int FetchAndAdd(int *v, int a)
{
    int old = *v;
    *v = old + a;
    return old;
}

• Fetch-And-Add는 ticket lock 구현에 사용할 수 있다.
• ticket lock은 lock을 얻으려는 thread에게 번호표를 나눠주고, 자기 차례가 올 때까지 기다리게 한다.

Ticket Locks

• ticket lock은 fairness를 개선한 lock이다.
• 구조는 다음과 같다.

struct lock {
    int ticket;
    int turn;
};

• ticket은 다음으로 나눠줄 번호다.
• turn은 현재 lock을 얻을 차례인 번호다.
• acquire는 다음처럼 동작한다.

void acquire(struct lock *l)
{
    int myturn = FetchAndAdd(&l->ticket, 1);

    while (l->turn != myturn);
}

• 각 thread는 FetchAndAdd()로 자기 ticket number를 받는다.
• 그리고 turn이 자기 번호가 될 때까지 기다린다.
• release는 다음처럼 동작한다.

void release(struct lock *l)
{
    l->turn = l->turn + 1;
}

• lock을 놓을 때 turn을 증가시켜 다음 ticket을 가진 thread가 들어오게 한다.
• ticket lock의 장점은 bounded waiting을 제공한다는 것이다.
• 즉 먼저 온 thread가 먼저 lock을 얻는다.
• starvation을 줄일 수 있다.

CPU Scheduler is Ignorant

• lock과 scheduler는 독립적으로 동작한다.
• scheduler는 누가 lock을 들고 있는지, 누가 lock을 기다리는지 알지 못한다.
• 그래서 다음과 같은 비효율이 생길 수 있다.
  • A가 lock을 들고 있다.
  • B가 A가 가진 lock을 기다리고 있다.
  • 그런데 scheduler가 A 대신 B를 계속 실행한다.
• 이 경우 B는 계속 spin만 한다. A가 실행되어야 lock을 풀 수 있는데, A가 CPU를 못 받으면 system 전체가 비효율적으로 실행된다.
  • 즉 spinlock은 lock holder가 빨리 실행되어 critical section을 끝낸다는 가정에 의존한다.
  • 하지만 scheduler가 그 사실을 모르면 CPU cycle이 낭비된다.

Ticket Locks with yield

• ticket lock에서 계속 spin하는 대신 yield()를 호출하게 만들 수도 있다.

void acquire(struct lock *l)
{
    int myturn = FetchAndAdd(&l->ticket, 1);

    while (l->turn != myturn)
        yield();
}

void release(struct lock *l)
{
    l->turn = l->turn + 1;
}

• yield()는 CPU를 다른 thread에게 양보한다. 이렇게 하면 기다리는 thread가 CPU를 계속 낭비하지 않는다. 특히 critical section이 길거나 lock holder가 CPU를 받아야 하는 상황에서는 도움이 된다.
• 하지만 yield()에도 context switch 비용이 있다. 따라서 아주 짧은 critical section에서는 spin이 더 나을 수 있다. 반대로 critical section이 길면 yield나 blocking 방식이 더 낫다.

Yield Instead of Spin

• spin은 기다리는 동안 CPU를 계속 사용한다.
• yield는 기다리는 동안 CPU를 양보한다.
• 두 방식의 차이는 다음과 같다.

• lock 구현에서는 critical section의 길이와 contention 정도를 고려해야 한다.
• 짧고 자주 잡는 lock은 spinlock이 적합할 수 있다.
• 오래 기다릴 수 있는 lock은 mutex나 sleep lock이 더 적합할 수 있다.