본 내용은 OSTEP 의 내용을 정리 및 요약한 내용입니다. 전문은 이 곳을 방문하시면 보실 수 있습니다.

28 락

이 장에서는 앞서 다룬 락(lock) 을 이용하여 이 문제를 직접적으로 다루고자 한다. 프로그래머들은 소스 코드의 임계 영역을 락으로 둘러서 그 임계 영역이 마치 하나의 원자 단위 명령어인 것처럼 실행되도록 한다.

28.1 락: 기본 개념

  • 락은 일종의 변수다. 락의 변수는 락의 상태를 나타낸다.
    • 사용가능 상태(available) : unlocked 나 free 상태
    • 사용중(acquired) : 점유 중 상태
  • 락의 자료구조에 락을 보유한 쓰레드에 대한 정보나, 락을 대기하는 쓰레드들에 대한 정보 저장도 가능하다.
  • lock() 과 unlock() :
    • lock 루틴을 호출함으로써 락 획득을 시도한다. 락을 획득하면, 임계영역으로 진입이 된다.
    • 이렇게 락을 획득한 쓰레드를 락 소유자(owner)라고 부른다.
    • lock의 소유자가 임계영역에 존재하는 상태에서는 다른 쓰레드들은 임계영역을 진입할 수가 없다.
    • unlock() 을 락 소유자가 호출하게 되면, 락 변수는 다시 사용 가능 상태로 바뀌게 된다.
    • 어떤 쓰레드도 이 락을 대기하지 않느다면, 락의 상태는 사용 가능으로 유지되며, 대기중인 쓰레드가 존재하면 락 상태는 변경되며, 획득한 소유자가 임계영역으로 진입이 가능하게 된다.
  • 락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다.
  • 일반적으로 쓰레드는 프로그래머가 생성하고 운영체제가 제어한다.
  • 락은 쓰레드에 대한 제어권을 일부 이양 받는 역할을 하는 것이며, 락을 통해 프로세스 내의 쓰레드를의 혼란스러운 실행에 순서성을 부여할 수 있다.

28.2 Pthread 락

  • 쓰레드 간에 상호 배제(mutual exclusion) 기능을 제공하기 때문에 POSIX 라이브러리는 락을 mutex 라고 부른다.
  • 기본적으로 상호배제는 위에서 배운 락의 개념이 그대로 적용된다고 볼 수 있다.
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
Pthread_mutex_lock(&lock); // wrapper 함수 실행, 실패시 exit
balance = balance + 1;
Pthread_mutex_unlock(&lock);
  • Posix에서는 락과 언락 함수에 락의 변수명을 인자로 전달한다. 다른 변수를 보호하기 위해 다른 락을 사용할 수도 있기 때문이다.
  • 이 말은 하나의 락으로 모든 임계영역들을 보호하는 것(coarse-grained 락 사용 전략)이 아니라 각 데이터와 자료 구조를 보호하는데 있어 여러 락을 사용한다. 즉, 다수의 쓰레드가 서로 다른 락으로 임계지점들에 대해 보호된 코드를 실행할 수 있다. (미세 락(fine-grained) 사용 전략)

28.3 락의 구현

  • 그렇다면 락은 어떻게 구현할 수 있을까? 어떻게 락을 만들며, 어떤 하드웨어 지원이 필요하고, OS는 무슨 일을 여기서 맡아서 해야할까? 이런 문제들을 이번 장에 다루고자 한다.

🚩 핵심 질문: 락은 어떻게 만들까

효율적인 락은 어떻게 만들어야 하는가?
효율적인 락은 낮은 비용으로 상호 배제 기법을 제공하고 다음에 다룰 몇가지 속성들을 추가로 가져야 한다. 어떤 하드웨어 지원이 필요한가?
어떤 OS 지원이 필요한가?
  • 사용 가능한 락을 만들기 위해선, HW와 OS의 도움을 받아야 한다. 락과 같은 상호 배제를 위한 기법을 만드는 데 어떻게 활용하는지 학습할 것이다. 락과 같은 상호 배제를 위한 기법을 만드는데 어떻게 활용하는지 학습할 것이다.

28.4 락의 평가

락 설계 시 락의 정상 동작 여부 판단 기준을 정해야 한다. 평가기준으로는 다음과 같다.

  • 상호 배제의 제대로된 지원여부
    가장 기본적인 역할이자, 핵심.
  • 공정성
    쓰레드들이 락 획득에 대한 공정한 기회가 제공 되는가?, 락을 전혀 얻지 못해 굶주리는(starve) 경우가 발생하는가?
  • 성능
    락 사용 시간적 오버헤드를 평가해야 한다. 경쟁이 전혀 없는 경우의 성능, 하나의 쓰레드가 실행중에 락을 획득하고 해제하는 과정에서 발생하는 부하는 얼마나 되는가를 파악해야 하며, 단일 CPU 상의 락을 획득하려고 경쟁할 때의 성능이 중요하다. 더불어 멀티 CPU 상황에서 락 경쟁 시의 성능도 중요하다.

28.5 인터럽트 제어

초기 단일 프로세스 시스템에서는 상호배제 지원을 위해 다음과 같은 방식을 사용한다.

void lock() {
	DisableInterrupts();
}

void unlock() {
	EnableInterrupts();
}
  • 단일 프로세서 시스템을 가정하고, 거기서 임계 영역 진입 전에 특별한 하드웨어 명령어를 사용하여 인터럽트를 비활성화 시킨다면, 임계 영역 내의 코드에서는 인터럽트가 발생할 수 없게 바뀐다.
  • 장점
    • 단순성 : 이 방식은 인터럽트 자체를 발생하지 않도록 하므로써, 코드가 실행중 다른 쓰레드의 끼어들기 보장한다.
  • 단점
    • 이 요청을 하는 쓰레드가 인터럽트를 활성/ 비활성화하는 특권 연산을 실행할수 있어야 하는데, 이는 신뢰할만한 프로그램이라면 문제가 없다 . 하지만 다른 목적으로 사용된다면 심각한 보안 문제, 자원의 과소비를 일으킬 수 있다.
    • 본 방식은 멀티프로세서에서는 적용할 수 없다. 여러 CPU에서 여러 쓰레드가 실행중이라면 각 쓰레드가 동일하게 임계영역을 진입하려고 할 수 있다. 이때 특정 프로세서에서의 인터럽트 비활성화는 다른 프로세서에서 실행중인 프로그램에서는 전혀 영향을 주지 못한다.(서로의 작업을 인지하고 하는 것이 아니니까) 결과적으로 멀티 프로세서가 흔해진 지금은 이렇게 해서는 해결되지 못한다.
    • 장시간의 인터럽트 중지는 중요한 인터럽트의 시점을 놓치게 만들 수 있다. 이는 시스템의 심각한 문제를 무시하는 결과로 이어질 수 있다.
    • 결론적으로 해당 방식의 락 구현은 비효율적이며 최신 CPU를 느리게 만드는 경향이 발생한다.
  • 위의 이유로 상호 배제를 위하여 인터럽트를 비활성화 방식의 락은 제한된 범위에서 사용되어야 한다.

28.6 실패한 시도: 오직 load/store 명령어만 사용하기

인터럽트 활성화/ 비활성화 방법을 사용하지 않고 락을 구현하려면 CPU 하드웨어와 락 구현을 위한 명령어를 사용해야한다. 그러나 이번 부분에서는 기본 아이디어들을 위하여 일반적인 load와 store 명령으로만 락을 구현해보고, 왜 안되는지를 보자.

typedef struct __lock_t {
	int flag;
} lock_t;

void init(lock_t *mutex) {
	// 0 -> 락이 사용 가능함. 1 -> 락 사용중 
	mytex->flag = 0;
}

void lock(lock_t *mytex) {
	while (mutex->flag == 1) //flag 변수를 검사
		; // spin-wait, busy-wait
	mutex->flag = 1; // set 
}

void unlock(lock_t *mutex) {
	mutex->flag = 0;
}
  • 해당 방식은 임계 영역에 진입하는 첫 쓰레드가 lock()을 호출하여 플래그 값이 1인지 검사(test)를 진행한다.
  • 그러나 1이 아니라면 계속 spin-wait을진행하며, 해당 조건을 통과하게 되면(flag = 0) 다시 플래그 값을 1로 설정하고, 해당 쓰레드가 이 락을 보유(hold)하고 있다고 표시한다.
  • 임계 영역에서 나오게 되면, 이때 쓰레드는 unlock()을 호출하고 플래그 값을 초기화하여 락을 보유하지 않게 된다.
  • 본 코드는 두 가지 문제점이 있다.
    • 제대로 작동하는가?(correctness)
      • 적시에 인터럽트가 발생하면 두 쓰레드 모두 플래그를 1로 설정하는 경우가 생길수 있다. 이러면 쓰레드가 둘다 임계영역에 접근할 수 있고, 상호 배제 제공이라는 기본 요구 조건을 보장 할 수 없게 된다.
    • 성능
      • spin-wait은 일종의 busy wait으로 무한하게 CPU가 플래그 값을 검사하게 되고, 이런 경우 CPU에 불필요한 수준의 자원을 소모하게 만들며, 단일 프로세서의 경우 매우 손해가 크다. 락을 소유한 쓰레드 조차 컨텍스트 스위칭이 발생하기 전까지 계속 멈춰있는 것이나 마찬가지이기 때문이다.

28.7 Test-And-Set을 사용하여 작동하는 스핀 락 구현하기

시스템 설계자들은 락 지원을 위한 하드웨어 설계를 1960년대부터 고민해왔다. 1960년대 버로우 B5000과 같은 초기 멀티프로세서 시스템에서도 하드웨어 지원 기능을 갖고 있다.

하드웨어 기법 중 가장 기본은 test-and-set 명령어, 또는 원자적 교체(atomic exchange)로 알려진 명령어 방식이다.

int TestAndSet(int *old_ptr, int new) {
	int old = *old_ptr;  // old_ptr의 이전 값을 가져온다.
	*old_ptr = new;      // old_ptr에 new 값을 저장한다. 
	return old;          // old 값을 반환한다.
}

// 이미 임계 영역에 접근한 쓰레드를 제외하면, 결코 값을 수정할 수 없는 구조를 확실하게 보장한다. 
// 28.3 TestAndSet을 이용한 간단한 스핀 락
typedef struct __lock_t {
	int flag;
} lock_t;

void init(lock_t *lock) {
	// 0 은 획득 가능 상태, 1은 락을 획득 했음 
	lock->flag = 0;
}

void lock(lock_t *lock) {
	while(TestAndSet(&lock->flag, 1) == 1)
		; // 스핀(아무 일도 하지 않음.
}

void unlock(lock_t *lock) {
	lock->flag = 0;
}
  • 이 락이 동작이 제대로 되는 이유를 보면, 처음 쓰레드가 lock()을 호출하고 다른 어떤 쓰레드도 현재 락을 보유하고 있지 않다고 생각해보자.
    • flag 값은 0이며, TestAndSet 함수를 호출하면, 루틴은 flag의 이전 값인 0을 반환한다.
    • while 문을 돌지 않으며, 임계영역에 정상적으로 진입하며, unlock 호출과 함께 락을 반환한다.
  • 반대의 경우 락을 획득하지 못하면,
    • TestAndSet(flag, 1)루틴을 실행한다. 이번에는 이미 락은 보유된 상태이며, 값을 계속 집어넣지만, 1로 설정이 되어가기 때문에 0이 들어갈 경우가 없어지고, while 문을 반복하게 된다.
    • 결국 락을 보유한 쓰레드가 이 값을 0으로 바꿀 때까지 원자적 연산이 보장된다.
  • 본 방식은 락의 값을 검사(test)하고 새로운 값으로 (set)하는 동작을 원자적 연산으로 만들어서, 오직 하나의 쓰레드 만 락을 획득할 수 있도록 만들었다.
  • 이러한 방식을 보면서 스핀락이란 무엇인가를 이해할 수 있으며, 가장 기초적인 형태의 락이 어떤 형태인지를 알 수 있다.
  • 단일 프로세서에서 이 방식을 제대로 사용하려면 선점형 스케줄러 를 사용한다. 이러한 방식은 필요에 따라 다른 쓰레드가 실행되도록 인터럽트를 발생 시킬 수 있다. 선점형이 아닌 경우 단일 CPU에서 while 문을 회전하며 대기하는 쓰레드가 CPU를 영원히 독점해 버리기 때문이다.

28.8 스핀 락 평가

스핀 락의 효율에 대해 평가해보자.

  • 락에서 가장 중요한 측면은 상호 배제의 정확성 이다. 스핀 락은 임의의 시간에 단 하나의 쓰레드 만이 임계영역에 진입할 수 있도록 한다.
  • 다음 중요 항목 공정성을 보자. 대기 중인 쓰레드들에 있어서 스핀 락은 얼마나 공정하게 기회를 제공하여, 경쟁 속에서 공정성이 제거되어, 쓰레드가 굶주린 상태가 되는 측정할 수 있다. 그러나 애석하게도 스핀 락의 구조는 공정성을 보장해줄 수 없다. while 문의 회전 중인 쓰레드는 경쟁에 밀려서 계속 그 상태를 유지할 수도 있다.
  • 마지막으로 성능 면에서 보면, busy wait 형태로 단일 CPU의 경우에 스핀락이 가지는 성능 오버헤드가 상당히 클 수 있다. 왜냐면 쓰레드가 할당 받은 기간 동안 CPU 사이클을 낭비하는 구조이기 때문이다.
    • 그에 비해 멀티 프로세스 형태, CPU 개수나, 쓰레드 개수를 여러개를 지원하는 경우, 스핀 락은 합리적일 수 있다. 임계 영역의 구간이 매우 짧고, 한쪽에서 진행하는 동안 대기하고 있던 다른 쓰레드가 락이 풀리는 순간 락을 획득하게 된다.

28.9 Compare-And-Swap

// 28.4 Compare-And-Swap

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

하드웨어적 기법으로 SPARC의 Compare-And-Swap 의 방법이 존재한다. x86에서는 Comapre-And-Exchange 라고 불리는데, 의사코드는 위와 같다.

이 방식은 ptr이 가리키고 있는 주소 값이 expected한 변수와 일찌하는 지를 검사하는 방식이다. 만약 일지 하면 주소 값을 새로운 값으로 변경하며, 불일치하면 아무 작업도 하지 않는다. 이 코드는 Test-And-Set에서 사용한 예제와 유사하게 동작하는 것을 볼 수 있다.

그럼에도, CompareAndSwap 명령어는 TestAndSet 명령어보단 강력하다. 대기 없는 동기화(wait-free synchronization) 와 같은 주제를 다룰 때 이 루틴의 특성과 능력을 알게 될 것이다. 단순히 스핀 락과 같은 식으로 만들어 사용시에는 이 명령어는 스핀락과 다를바 없는 동작을 한다.

28.10 Load-Linked 그리고 Store-Conditional

어떤 플랫폼에서는 임계 영역 진입 제어 함수를 제작하기 위해 명령어 쌍을 제공한다. MIPS 구조에서는 load-linked 와 store-conditional 명령를 앞 뒤로 사용하여 락이나 기타 병행 연산을 위한 자료구조를 만들 수 있다. 이를 C 의사 코드를 나타낸 것은 다음과 같으며, Alpha, PowerPC, ARM에서도 유사한 명령어를 지원한다.

//28.5 Load-Linked, Sotre-Conditional
int LoadLinked(int *ptr) {
	return *ptr;
}

int StoreConditional(int *ptr, int value) {
	if(no update to *ptr since the LoadLinked to this address) {
			*ptr = value;
			return 1;   // 성공
	} else {
		return 0;       // 갱신 실패
	}
}
  • load-linked 는 일반 로드 명령어와 같이 메모리 값을 레지스터에 저장한다. 실제 차이는 store-conditional 명령어에서 나타난다. store-conditional 명령어는 동일한 주소에 다른 스토어가 없었던 경우에만 저장을 성공한다.
  • 저장이 성공 시 load-linked 가 탑재 했던 값을 갱신하고, 성공시 store-conditional 은 1을 반환하고 ptr이 가리키는 value 의 값을 갱신한다. 실패한 경우엔 ptr 이 가리키는 value 값이 갱신되지 않고, 0을 반환한다.
// 28.6 Load-Linked 와 Store-COndtional 을 사용하여 락 만들기 
void lock(lock_t *lock) {
	while (true){
		while (LoadLinked(&lock->flag) == 1) {
			; // 0이 될 때까지 스핀 
		}
		if (StoreCondtional(&lock->flag, 1) == 1) {
				return ; // 1로 변경하는 것이 성공하였다면 : 완료 
				         // 아니라면 : 처음부터 다시 시도 
		}
	}
}
  • lock() 부분의 코드를 보자. 쓰레드가 while 문을 돌면서 flag = 0이 되기를 기다린다. 락 획득이 가능해 졌을 때, 락 획득을 시도하고, 성공하면 쓰레드는 flag 값을 1로 변경한다. 그리곤 임계 영역에 진입한다.
  • 하지만 실패할 수도 있다. 쓰레드가 lock() 을 호출하여 load-linked 를 실행하고, 락이 가능한 상태이므로 0을 반환한다. store-conditional 명령어를 시도하기 전에, 이쓰레드는 인터럽트에 걸렸고, 다른 쓰레드가 락 코드를 호출하고, load-linked 명령어는 실행하여 0을 반환, 이에 이번 쓰레드가 진행했다고 하자.
  • 이 시점에 두 쓰레드는 모두 load-linked 명령어를 실행해 각자 store-conditional 을 부르려는 상황이다.
  • 이 상황에서 오직 하나의 쓰레드만 flag 값을 1로 설정한 후, 락을 획득할 수 있고, 다시 복귀한 쓰레드는 store-conditional 에서 락 획득을 실패하고, flag그 값이 갱신된것을 파악, return 0을 하고 만다.
// 좀더 짧게 축소한 코드 
void lock(lock_t *lock) {
	while (LoadLinked(&lock->flag) || !StoreConditional(&lock->flag, 1))
		; // 회전 
}

28.11 Fetch-And-Add

마지막 하드웨어 기반의 기법은 Fetch-And-Add 명령어 형태가 있다. C언어로 된 의사 코드는 다음과 같다.

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

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) 
		; // 회전
}

void unlock(lock_t *lock) {
	FetchAndAdd(&lock->turn);
}
  • 본 방식은 티켓 락 이라는 재미있는 것을 만들었다. 하나의 쓰레드가 락 획득을 원하면, 티켓 변수에 원자적 동작인 fetch-and-add 명령어를 실행한다. 그리고 이는 자신의 턴(myturn)을 나타낸다.
  • 전역 공유 변수인 lock->turn 을 사용하여 어느 쓰레드 차례인지를 판단한다. 만약 한 쓰레드가 myurn == turn 상황이라는 조건에 부합한다면, 이는 그 쓰레드가 임계 영역에 진입할 차례라는 것을 보여준다. 언락 동작은 차례 변수의 값을 증가시켜, 대기중인 다음 쓰레드에게 임계 영역 진입 차례를 넘겨준다.
  • 이러한 방식은 이전까지와는 다른 점이 순서에 따라 진행되도록 되어 있다는 점이다. 기존의 해법은 기아와 관련하여 해결을 제대로 해주지 못하고, 기아 상태가 발생할 수 있다.

28.12 요약: 과도한 스핀

지금까지 소개한 하드웨어 기반의 락은 간단하면서도, 제대로 동작했다. 하지만 이러한 해법은 효율적이라고 말할 수는 없다. 예를 들어 두개의 쓰레드가 존재하고, 쓰레드 0, 1은 경쟁관계이며, 쓰레드 0이 임계 영역 내에 있다고 보자. 그 순간 인터럽트가 발생해, 컨텍스트 스위칭이 발생하고 쓰레드 1은 락을 획득하려고 하나 이미 다른 쓰레드가 획득하고 있다. 그렇다면 인터럽트가 다음 발생하기 전까지 쓰레드 1은 계속 대기만을 하게 되고, 쓰레드 0도 작업은 그 다음 스위칭이 된 이후에야 된다. 즉 스핀락의 형태는 시간낭비가 태생적으로 발생할 수 밖에 없으며, 경쟁할 쓰레드가 늘어나면 늘어날 수록 낭비가 발생한다. 그렇기에 구현을 위해 우리는 다음 질문에 대한 고민이 필요해질 것이다.

🚩 핵심 질문: 회전을 피하는 방법

어떻게 하면 스핀에 CPU 시간을 낭비하지 않는 락을 만들 수 있을까?

28.13 간단한 접근법 : 조건 없는 양보!

지금까지 하드웨어 지원으로 간단하게 구현된 내용은 동작은 검증되고, 락 획득의 공정성 까지도 어떻게든 해결 했다. 하지만 밝혀진 것처럼 컨텍스트 스위칭에서는 무력한 모습이 발생했고, 스핀만 무한하게 발생하는 경우가 발견되었다. 이를 개선하기 위해 가장 먼저 해볼 시도는 락이 해제 되기를 기다리며 스핀해야 하는 경우 자신에게 할당된 CPU를 다른 쓰레드에게 양보하는 것이다.

// 28.8 Test-And-Set 와 양보를 이용한 락 
void init() {
	flag = 0;
}

void lock() {
	while(TestAndSet(&flag, 1) == 1) {
		yield(); // CPU 를 양보해버림
	}
}

void unlock() {
	flag = 0;
}

이는 가정이지만, 어쨌든 시스템 내부에 yield() 기법이 있다고 가정한다. 하나의 쓰레드는 실행중, 준비, 막힘의 프로세스 상태에서 양보(yield)라는 시스템콜은 호출 쓰레드 상태를 실행중(running)에서 준비(ready) 상태로 변환하고, 이를 통해 다른 쓰레드가 실행되도록 유도한다. 즉, 양보 동작은 OS의 CPU 작업 스케쥴링에서 자신을 빼는 것(deschedule)하는 것이다.

이러한 방식은 단일 CPU 에서는 양보기법을 통해 락을 보유한 쓰레드가 임계영역을 넘어가기 좋도록 아주 적절하게 대응 되는 것을 볼 수 있다.

하지만 멀티 쓰레드의 개수가 많아진다면 어떨까? 라운드 로빈스케줄러인 경우를 고려해보자. 만약 이런 경우 100개의 쓰레드가 있다면, 1개의 락을 보유한 쓰레드를 위해 99개가 양보를 하는 패턴으로 동작할 가능성이 발생하고 만다. 즉, 컨텍스트 스위칭(문맥교환)의 비용이 여전히 상당한 경우가 발생하는 것이다.

이러한 점에서 굶주림 문제는 더더욱 개선이 되지 않았기에 어떤 쓰레드가 무한히 양보만 하는 경우가 발생할 수 있다.

28.14 큐의 사용 : 스핀 대신 잠자기

지금까지의 방법들에서 근본적인 문제는 너무나많은 부분을 운에 맡기고 있다는 점이다. 스케줄러가 유기적으로 실행될 쓰레드를 잘 고르면 좋지만, 그렇지 않은 경우 CPU를 다시 반납해야 할 수가 있고, 이런 경우 당연히 문제는 발생하기 마련이다.

따라서 다수의 쓰레드가 락으로 대기할 때, 다음으로 락을 획득할 쓰레드를 명시해주는 방식으로 관리하는 방법의 필요성이 대두 된다. 이러한 예로써 Solaris의 방식을 설명해보고자 한다.

쓰레드를 잠재우는 park() 함수와 쓰레드 ID 로 명시된 특정 쓰레드를 깨우는 unpack(threadID) 함수가 있다. 이 예제를 살펴 보자.

//28.9 큐, Test-And-Set 양보와 깨우기를 사용한 락 
typedef strcut __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(TestAndSet(&m->guard, 1) == 1) {
		;
	}
	if (m->flag == 0) {
		m->flag = 1; // 락을 획득
		m->guard = 0;
	} else {
		queue_add(m->q, gettid());
		m->guard = 0;
		park();
	}
}

void unlock(lock_t *m) {
	while (TestAndSet(&m->guard, 1) == 1)
		; // 회전하면서 guard 락을 획득 
	if (queue_empty(m->q))
		m->flag = 0; // 락을 포기 -> 누구도 락을 원치 않음이라고 적혀 있으나, 한마디로 큐에 아무도 없는 경우 
	else 
		unpark(queue_remove(m->q)); // 락을 다음 쓰레드를 위해 전달,
	m->guard = 0;
}
  • 이 예제에서 흥미로운 점은 두가지 정도다.
    • 앞 서 배운 Test-And-Set 의 개념을 락 대기자 전용 큐와 함께 사용하여 좀더 효율적인 락을 만든다.
    • 큐를 사용하여 다음으로 락을 획득할 대상을 제어하여 기아 현상을 피할 수 있도록 한다.
  • guard 변수를 이용한 스핀락으로 큐와 flag 변수를 보호한다. 이 방법이 스핀락을 활용하긴 하지만, 오버헤드 자체는 적다. 변수를 획득하거나 해제하는 과정에서 인터럽트도 될 수는 있다. lock()에서 쓰레드가 자신을 얻을 수 없을 때는 gettid() 함수를 통해 자신의 쓰레드 ID를 큐에 추가한다. 그리곤 양보하게 되는데, 이후 이 중간에 인터럽트가 발생한다면 park() 실행 후 guard 락이 해제되면 어떤일이 발생할까? -> 사실 이러면 쓰레드가 깨어났을 때, flag = 0 으로 리셋되지 않을 수 있다.
  • 그러나 이런 경우 쓰레드가 깨어나는 시점은 park()에서 리턴된 시점이다. 해당 시점에서 쓰레드는 guard 를 보유하지 않았고, 따라서 flag = 1로 설정 조차 할 수 없다. 락을 해제하는 쓰레드는 락을 다음 쓰레드에게 직접 넘겨주게 된다. 따라서 이 과정에서 flag = 0으로 리셋이 될 필요는 없는 것이다.
  • 이 코드는 그러나 경쟁조건이 발생할 수도 있다. 쓰레드가 park()를 호출하기 직전에 락을 소유한 쓰레드가 락을 해제하면, 락 소유 쓰레드는 락을 해제하면서 깨울 쓰레드 존재 여부를 검사한다. 하지만 이땐 대기중인, 큐에 등록된 쓰레드가 없으니, 쓰레드 락을 해제하고 계속 실행된다. park() 된 쓰레드는 block 된 상태 그대로이며 깨어나지 않는다. 왜냐면 unpark() 해줄 쓰레드가 없는 것이다.
  • 이러한 문제를 wakeup/ waiting race 라고 부른다.
  • 이에 대해 Solaris 는 setpark() 라는 함수를 추가하여 이를 해결하였다. park() 전에 미리 준비를 해둠으로써 park() 호출 시 다른 쓰레드가 unpark() 를 먼저 호출한다면 추후 park() 호출 시 이를 호출한 쓰레드를 블럭이 아닌 리턴으로 바꿔 멈추지 않도록 조치를 취하는 것이다.

28.15 다른 운영체제, 다른 지원

효율적인 락을 만들기 위한 노력들을 살펴보았다. 세부적으로 차이는 있겠지만 다른 OS들도 유사한 기능을 제공한다.

  • Linux 의 경우 futex라는 것을 지원한다. 보다 커널에 밀착되어 있으며, 특정 물리 메모리 주소, 그리고 커널이 정의한 큐를 갖고 있다. 호출자는 futex 관련 함수를 호출하여 잠을 자거나 잠에서 깨어난다.

    • futex_wait(address, expected) 명령어는 주소와 expected 값이 동일한 경우 쓰레드를 블럭 시킨다. 같지 않으면 리턴한다.

    • futex_wake(address) 는 큐에서 대기하던 쓰레드 하를 깨우게 된다.

  • nptl 라이브러리의 lowlevellock.h에서 발췌한 예시로 Linux 사용법은 그림 28.10(351페이지)는 흥미로운 방식으로 락을 지원한다.

    • 락의 사용중 여부, 대기자 수를 동시에 사용하며, 따라서 락이 음수이면 락이 사용중인 것으로 표현한다.
    • 이 코드는 경쟁이 없는 경우에 대해 최적화되어 있다.

  • 결론적으로 실제 사용되는 락의 동작 메커니즘의 이해는 직접 찾아보길 바란다.

void mutex_lock(int* mutex){
	int v;
		// 31번째 비트가 이미 초기화 되어 있다. mutex를 이미 획득했다. 바로 리턴한다.(빠르게 실행하는 방법)
	if (atomic_bit_test_set(mutex, 31) == 0)
		return;
	atomic_increment(mutex);
	while(1) {
		if (atomic_bit_test_set(mutex, 31) == 0) {
			atomic_decrement (mutex);
			return ;
		}
		// 이제 대기해야 함. 관찰중인 futex 값이 실제 음수인지 확인한다.(잠김 된 것인지)
		v = *mutex;
		if (v >= 0)
			continue ;
		futex_wait(mutex, v);
	}
}

void mutex_unlock(int* mutex) {
	// 필요 충분 조건으로 관심 대상의 다른 쓰레드가 없는 경우 한해서 0x80000000를 카운터에 더하면 0을 얻는다.
	if(atomic_add_zero(mutex, 0x80000000))
		return ;
	// 이 mutex를 기다리는 다른 쓰레드가 있다면, 그 쓰레드를 깨운다.
	futex_wake(mutex);
}

28.16 2단계 락

고전적 락의 특성을 가진 락들은 19060년 대 초에 사용된 것이며, 요즘은 2단계 락(two-phase lock) 이라고 불린다. 이는 락이 곧 해제될 것 같으면, 회전 대기가 더 유용하다는 점에 착안하였다. 첫 스텝에선 회전 대기르 하며, 빠른 시간 내에 해제 될거라 생각한다. 하지만 락을 획득하지 못하면, 호출자는 차단 되고 락 해제 시 블럭된 쓰레드를 깨운다. 이러한 형태로 두개의 개념이 하이브리드 된 특성을 만드는 것이다.

하지만 이는 우수한 만큼 하드웨어 환경, 쓰레드의 개서, 그리고 세부 작업량 등과 같은 많은 것들에 의해 결정된다.

28.17 요약

실제 구현된 락의 코드는 하드웨어 환경에 적합하게 최적화 되어 있어서, 이 부분은 직접 더 찾아봐야 한다.