[Operating System] Locks

Lock이란?

Lock은 critical section의 operation들을 single atomic instruction처럼 실행되도록 보장해준다.

• lock variable은 lock의 상태에 대한 정보를 hold 한다.
  • available: unlocked, free
  • acquired: locked, held
• lock(): lock을 획득하고자 시도한다. lock을 잡은 다른 쓰레드가 없으면 lock을 획득하고 critical section에 들어간다.
• mutex: POSIX lib에서 사용하는 lock의 이름
• 다른 공유 변수에 대해선 다른 lock을 사용하는 것이 바람직하다.
• lock의 구현을 위해선 HW와 OS 모두의 support가 필요하다.

 

HW의 도움이 필요한 이유?

flag를 이용해서 lock을 잡았는지 못잡았는지 파악하는 경우, flag를 set하기 위한 operation은 반드시 atomic해야함.
완벽한 atomic instruction을 구현하려면 반드시 회로 레벨에서 로직이 구현되고 ISA로 정의 되어야 한다. (TAS, CAS)

 

Lock의 구현

Lock의 성능을 평가하기 위한 기준

1. mutex (상호배제): critical section에 하나의 쓰레드만 들어가는 것이 보장되는가.
2. fairness: wait 중인 쓰레드들이 공평하게 lock을 얻을 수 있는가?
3. performance: lock으로 인해 생기는 time 오버헤드를 최소화

 

Non-Blocking Lock

Non-blocking lock에서는 busy waiting을 하기 때문에 쓰레드 간의 context-switch로 인한 overhead는 없지만, 하나의 CPU에서 control을 계속 점유하기 때문에 자원의 낭비가 심하다. 따라서 lock과 unlock 사이의 critical section에 있는 workload가 크지 않을 때 이 방식을 사용하는 것이 효율적이다.

 

1. Interrupt Masking

• 단일 프로세서 시스템의 경우엔 disabling interrupt로 상호배제 가능
• 하지만 application 레벨에서 이를 악용하여 interrupt를 막아서 control을 독점할 수 있음
• 멀티 프로세서에서는 동작하지 않음

 

2. HW Support: TAS

• Atomic Exchange
• 옛날 값을 가리키는 포인터 새로운 값을 넘겨받고, 옛날 값을 가리키는 포인터를 old에 저장한뒤 ptr은 새로운 값으로 업데이트하고, old를 리턴한다. (이 과정이 HW 단에서 atomic하게 구현됨)

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

 

 

3. HW Support: CAS

• Compare and Swap
• ptr이 가리키는 값이 expected 값과 동일한지 테스트한다. 만약 동일하다면 ptr이 새로운 값을 가리키도록 업데이트 한다.
• 항상 actual 값을 리턴한다.
• N번 째 루프에서 ptr이 0이 되었고(다른 쓰레드에서 release) 현재 쓰레드에서 1로 업데이트 하였다면, N+1번 째 루프에서는 1을 리턴하여 busy wait하던 while loop을 빠져나와 진행할 수 있다.

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

// CAS를 사용한 lock
void lock(lock_t *lock) {
	while(CAS(&lock->flag, 0, 1) == 1)
    	;
}

 

4. Load-Linked and Store-Conditional

int LoadLinked(int *ptr) {
    return *ptr;
}

int StoreConditional(int *ptr, int value) {
    if (어떤 쓰레드도 LoadLinked 이후로 *ptr을 업데이트 하지 않았다면) {
    	*ptr = value;
       	return 1;	// success!
    }
    else {
    	return 0;	// update failed!
    }
}

// LoadLinked, StoreConditional을 사용한 Lock의 구현
void lock(lock_t *lock) {
    while(1) {
    	while (LoadLinked(&lock->flag) == 1)
            ;		// flag가 0이 될 때까지 spin
        if (StoreConditional(&lock->flag, 1) == 1)
            // LL 이후에 다른 쓰레드에 의한 업데이트가 일어나지 않았는지 확인하고 1로 업데이트
            return;		
}

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

• LoadLinked에서 ptr의 값을 읽고, StoreConditional에서 ptr이 가리키는 값을 업데이트 하는 중간에 다른 쓰레드에서 값을 업데이트 하지 않도록 보장해준다.

 

5. Fetch-And-Add

Read $\to$ Modify $\to$ Write 방식을 통해서 atomic하게 값을 증가시킨다. TAS와 마찬가지로 업데이트 이전의 옛날 값을 리턴한다.

 

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

 

6. Ticket Lock

Ticket lock은 이름에서부터 유추할 수 있듯이 모든 쓰레드들이 공평하게 lock을 잡을 수 있도록 하기 위해서 고안되었다.

• 위에서 살펴 본 Fetch-And-Add를 통해서 구현한다.

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)
    	;		// spin
        
void unlock(lock_t *lock) {
    FetchAndAdd(&lock->turn);
}

 

Blocking Lock

 

앞서 살펴본 non-blocking 방식과 달리 lock을 잡지 못하면 다른 쓰레드로 control을 넘겨서 다른 쓰레드의 job이 진행될 수 있도록 한다.

 

1. Yield

• Spin 시엔 CPU를 포기하고 다른 쓰레드에게 컨트롤을 넘겨줌
• yield를 하면 state가 run에서 ready로 바뀜
• 단점: context switch로 인한 오버헤드 / starvation의 가능성
  
  

void init() {
    flag = 0;
}

void lock() {
    while (TAS(&flag, 1) == 1)
    	yield();
}

void unlock() {
    flag = 0;
}

 

2. Wait Queue를 이용: Spin 대신 Sleep-Wake

• Wait queue를 통해서 lock을 잡으려고 기다리는 쓰레드들의 리스트를 저장한다.

Solaris에서는 park와 unpark라는 sleep-wake 매커니즘을 제공한다.

• park(): 호출한 쓰레드를 sleep 시킨다.
• unpart(tid): tid에 해당하는 쓰레드를 깨운다.

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) {
    while(TAS(&m->guard, 1) == 1)   // TAS는 함수에 들어온 old 값을 리턴함
        ;   // gaurd lock을 얻을 때까지 spin
    if(m->flag == 0) {
        m->flag = 1;    // lock을 얻음
        m->guard = 0;   // gaurd unlock
    } else {
        queue_add(m->q, gettid());      // wait queue에 삽입
        m->guard = 0;   // guard unlock
        setpark();      // @추가: 잠시 후에 park할 것음을 알림 
        park();     // sleep
    }
}

void unlock(lock_t *m) {
    while(TAS(&m->guard, 1) == 1)
        ;   // guard lock을 얻을 때까지 spin
    if(queue_empty(m->q))   // 만약 wait queue에 기다리는 쓰레드가 있다면
        m->flag = 0;    // unlock
    else
        unpark(queue_remove(m->q)); // wait queue 맨 앞의 쓰레드를 깨움
    m->guarg = 0;   // guard unlock
}

 

3. Futex

리눅스의 sleep-wake 매커니즘으로는 futex가 있다.

• futex_wait(address, expected): 호출한 쓰레드를 재움
• futex_wake(address): 큐에서 기다리고 있는 쓰레드 중 하나를 깨움

 

 

---

Non-Blocking vs Blocking

1. 싱글 프로세서

싱글 프로세서의 경우엔 한 개의 프로세서를 가지고 쓰레드 간에 time sharing을 하는데, 특정한 쓰레드가 한 개밖에 없는 프로세서 자원을 혼자서 잡고 있으면 deadlock과 같은 문제가 발생하기 때문에 기다리는 프로세스는 무조건 sleep을 하고 다른 쓰레드에 컨트롤을 넘겨줄 수밖에 없다. 즉, 싱글 프로세서에서는 반드시 blocking lock을 사용해야 한다.

 

2. 멀티 프로세서

Non-blocking 방식은 context switch 오버헤드가 없다는 점에서 이점이 있지만, 하나의 쓰레드가 CPU 자원을 쓸데 없이 낭비한다는 점에서 오버헤드가 있다. 따라서 lock이 빠르게 release 될 수 있는 경우엔 non-blocking 방식이 유리하지만, lock을 길게 잡고 있는 경우엔 blocking 방식이 효율적이다.

 

이와 같은 blocking 방식과 non-blocking 방식의 특징을 고려해서 섞은 것이 Two-Phase Lock이다.

 

 

Two-Phase Lock

처음엔 spinning을 하면서 일정 시간동안 기다리다가 그 동안에 lock을 잡지 못하면 spinning을 멈추고 sleep한다.