OSTEP 28 - Locks

JiYun·2025년 3월 15일
CSOSOSTEP

OSTEP

목록 보기
17/21

프로그래머들은 소스코드의 임계 영역을 락으로 둘러서 그 임계 영역이 하나의 원자 단위 명령어인 것처럼 실행되도록 한다.

1. 락: 기본 개념

balance = balance + 1;

다음과 같은 임계 영역이 있고, 락을 사용하기 위해 임계 영역을 감쌌다.

lock_t mutex; // 전역 변수로 선언된 락
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

락은 하나의 변수이기 때문에, 락을 사용하기 위해서는 락 변수를 먼저 선언해야한다. 이 락은 사용 가능 상태(어느 스레드도 락을 가지고 있지 않음)거나, 사용 중(임계 영역에서 정확히 하나의 쓰레드가 락을 획득한 상태)이다.

lock() 호출을 통해 락 획득을 시도한다. 사용 가능 상태라면 쓰레드는 락을 획득하여 임계영역 내로 진입한다. 이 쓰레드를 소유자(owner)라고 한다. 만약 다른 쓰레드가 lock()을 호출한다면, 락이 사용중인 동안에는 lock()함수가 리턴하지 않는다.

락 소유자가 unlock()을 호출한다면 락은 이제 다시 사용 가능한 상태가 된다. 다른 스레드가 lock()을 호출한 상태가 아니라면 사용가능 상태를 유지하고, 대기 중이던 쓰레드가 있다면 그 쓰레드가 락을 획득한다.

락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다. 락은 쓰레드에 대한 제어권을 일부 이양받을 수 있게 해준다. 락을 통해 프로그래머는 임계 영역 코드 내에서 하나의 쓰레드만 동작하도록 보장할 수 있다. 프로세스들의 혼란스러운 실행 순서에 약간의 질서를 부여할 수 있다.

2. Pthread 락

쓰레드 간에 상호 배제(mutual exclusion) 기능을 제공하기 때문에 POSIX 라이브러리는 락을 mutex라고 부른다. 상호 배제는 한 쓰레드가 임계 영역 내에 있다면 이 쓰레드의 동작이 끝날 때까지 다른 쓰레드가 임계 영역에 들어 올 수 도록 제한한다고 해서 얻은 이름이다.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

// 래퍼를 사용하여 락과 언락 시 에러를 확인하도록 하였다.
Pthread_mutex_lock(&lock); // pthread_mutex_lock()을 위한 래퍼.
balance = balance + 1;
Pthread_mutex_unlock(&lock);

POSIX 방식에서는 변수 명을 지정하여 락과 언락 함수에 전달하고 있다. 다른 변수를 보호하기 위해서 다른 락을 사용할 수도 있기 때문이다.

거친 락 (Coarse-Grained Locking)

  • 하나의 락이 큰 임계 영역을 제어함.
  • 쉽게 구현할 수 있지만, 병렬성이 제한됨.

세밀한 락 (Fine-Grained Locking)

  • 여러 락이 서로 다른 데이터나 자료구조를 보호함.
  • 한 번에 여러 쓰레드가 서로 다른 락으로 보호된 코드 내에 진입 가능.
  • 병렬성은 향상되지만, 데드락 등의 복잡한 이슈에 대처해야 함.

3. 락 구현

어떻게 락을 만들어야 할까? 어떤 종류의 하드웨어 지원이 필요할까? 운영체제는 무엇을 지원해야 할까?

사용 가능한 락을 위해서는 하드웨어와 운영체제의 도움이 필요하다.

4. 락의 평가

  1. 상호 배제
    • 임계 영역 내로 다수의 쓰레드가 집입하는 것을 막을 수 있는가
  2. 공정성
    • 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가
    • starvation이 발생하는가?
  3. 성능
    • 락 사용 시간적 오버헤드 평가
    • 하나의 쓰레드가 락을 획득하고 해제하는 과정에서의 부하는 얼마나 되는가?
    • 락 경쟁시

5. 인터럽트 제어

초창기 단일 프로세스 시스템에서는 상호 배제 지원을 위해 임계 영역 내에서는 인터럽트를 비활성화하는 방법을 사용했다.

void lock() {
	DisableInterrupts();
}
void unlock() {
	EnableInterrupts();
}

임계 영역에 집입하기 전에, 인터럽트를 막는다면 임계 영역 내 코드는 원자적으로 수행될 수 있다. 이 방법의 주요 장점은 단순하다는 것이다.

그러나 단점이 많다.

  1. 요청을 하는 쓰레드가 인터럽트를 활성/비활성화하는 특권 연산을 실행할 수 있도록 허용해야한다. 이를 다른 목적으로 사용하지 않음을 신뢰할 수 있어야 한다.
    • 프로그램이 시작과 동시에 lock()을 호출하여 프로세서를 독점할 수 있다.
  2. 멀티 프로세서에서 적용할 수 없다.
    • 프로세서 마다 각자의 인터럽트 활성화 여부는 서로 영향을 끼치지 않는다. A에서 비활성화했더라도 B에서 접근할 수도 있다.
  3. 장시간 인터럽트 중지는 중요한 인터럽트 시점을 놓치게될 수 있다.
  4. 비효율적이다. 최신 CPU들에서는 인터럽트 관련 명령이 일반적인 명령에 비해 느린 경향이 있다.

이런 이유로, 상호 배제를 위한 인터럽트의 비활성화는 제한된 범위에서만 사용되어야 한다. 예를 들어 운영체제가 내부 자료구조에 대한 원자적 연산을 위해 인터럽트를 비활성화할 수 있다.

Dekker와 Peterson의 알고리즘
하드웨어 지원 없이 원자성을 지원하기 위한 개념을 제시했다. 그러나 하드웨어의 지원이 있다면 더 쉽게 해결할 수 있다는 것을 알게된 후 필요가 없어졌다.

6. Test-And-Set (Atomic Exchange)

멀티프로세서에서는 인터럽트를 중지시키는 것이 의미가 없다. 이에 시스템 설계자들은 락 지원을 위한 하드웨어를 설계하기 시작했다. 오늘날에는 모든 시스템이 이런 기능을 가지고있다.

하드웨어 기법 중 가장 기본은 Test-And-Set 명령어 또는 원자적 교체라고 불리는 기법이다. 이를 이해하기 위해 간단한 플래그 변수로 락은 구현해보자.

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex) {
	// 0: 락 사용 가능
	// 1: 락 사용 중
	mutex−>flag = 0;
}

void lock(lock_t *mutex) {
	while (mutex−>flag == 1) // flag 변수를 검사 (test) 한다
	; // spin−wait (do nothing)
	mutex−>flag = 1; // 이제 설정 (set) 한다
}

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

쓰레드가 lock()을 호출하여 플래그 값이 1인지 검사(test)한다. 1일 경우 다른 스레드가 락을 사용 중이다. 이때 while문으로 spin-wait하며 다른 스레드가 unlock()을 호출하여 플래그를 0으로 바꿀때까지 기다린다. while문을 탈출한 후, 플래그를 1로 설정(set)하여 락을 보유하고 있다고 표시한다.

이 방식에는 두가지 단점이 있다.

  1. 정확성

    시작할 때 flag = 0이라 하자. 쓰레드 1이 flag = 1을 실행하기 직전에 인터럽트가 일어난다면? 두 쓰레드 모두 플래그를 1로 설정하도록 하는 타이밍이 존재한다. 결국 두 쓰레드 모두 임계 영역에 진입하게 될 것이다.

  1. 성능

    사용 중인 락을 대기하는 과정에서 spin-wait 방식은 다른 쓰레드가 락을 해제할 때까지 시간을 낭비한다. 단일 프로세서 환경에서는 락을 소유한 쓰레드도 실행되지 못하는 시점이 존재하게 된다.

7. 진짜 돌아가는 스핀 락의 구현

위 예제는 아이디어는 좋았지만, 하드웨어의 지원 없이는 동작이 불가능하다. 다행이 어떤 시스템에서는 이 개념에 근간한 락 구현을 위한 어셈블리 명령어를 제공한다. SPARC에서는 ldstub, x86에서는 xchg이다.

일반적으로 Test-And-Set 이라고 불리며, C코드의 일부를 사용해 동작을 정의해보자.

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

ptr이 가리키고 있던 예전의 값을 반환하고 동시에 new값을 ptr에 저장한다. 여기서 핵심은 이 동작들이 원자적으로 수행된다는 것이다.

“test and set”이라는 부르는 이유는, 검사하는 동시에 메모리에 새로운 값으로 설정하기 때문이다. 이 강력해진 명령어 만으로 더 간단한 spin-lock을 만들 수 있다.

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)**
	; // spin
}

void unlock(lock_t *lock) {
	lock−>flag = 0;
}
  • 락이 사용가능 상태일 경우 TestAndSet(flag, 1)을 호출하게 되면, 이전 값인 0을 리턴하고 flag를 1로 만든다. flag 값을 검사한 쓰레드는 while문을 회전하지 않고도 락을 획득하게 된다. 동작 이후에는 unlock()을 통해 다시 flag를 0으로 만든다.
  • 락이 사용 중인 상태 TestAndSet(flag, 1)을 호출하게 되면, 이전 값인 1을 리턴하고 flag를 1로 만든다. 다른 쓰레드에서 락이 해제될 때까지 while문을 반복하다가, flag가 0이 되었을 때, TestAndSet()은 0을 리턴하는 동시에 flag를 1로 만든다. 원자적이다.

락의 값을 검사(Test)하고 설정(Set)하는 동작을 원자적 연산으로 만들어 하나의 쓰레드만 락을 획득할 수 있도록 했다. 이제 제대로 동작하는 상호 배제 함수를 만드는 방법을 배웠다.

지금 설명한 방식이 스핀 락(spin lock)이라고 불린다. 이것이 가장 기초적인 형태의 락으로서, 락을 획득할 때까지, CPU 사이클을 소모하면서 회전한다. 이 방식을 제대로 사용하려면 선점형 스케줄러여야한다.

8. 스핀 락 평가

  • 정확성 상호 배제가 가능하다면, 스핀락은 임의의 시간에 단 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 한다. 제대로 동작하는 락이다.
  • 공정성 스핀락은 어떠한 공정성도 보장해줄 수 없다. 실제로 while문을 회전 중인 쓰레드는 경쟁에서 밀려 계속 그 상태에 머물러 있을 수도 있다. 쓰레드가 굶주리게 될 수 있다.
  • 성능 단일 CPU의 경우 스핀락의 성능 오버헤드가 매우 클 수 있다. 한 스레드가 락을 가지고 있고, N - 1개의 다른 스레드가 있다고 가정하자. 락을 획득하려는 나머지 스레드들을 하나씩 깨울 수 있다. N -1 가 CPU에 할당되있는 동안 사이클이 낭비된다. 멀티 CPU의 경우 (쓰레드 개수가 CPU 개수와 대충 같다면) 꽤 합리적으로 동작한다. CPU 1에서 실행중인 A가 락을 획득한 후 B가 락을 획득하려고 할때, B는 CPU 2에서 기다리기 때문에 CPU 1에서 CPU 사이클이 낭비되지 않는다.

9. Compare-And-Swap

또 다른 하드웨어 기법은 SPARC의 Compare-And-Swap, x86에서는 Compare-And-Exchange가 있다.

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

Compare-And-Swap 기법의 기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사하는가 것이다. 만약 일치한다면 ptr이 가리키는 주소의 값을 새로운 값으로 변경한다. 불일치한다면 아무 것도 하지 않는다. 원래의 메모리 값을 반환하여 CompareAndSwap를 호출한 코드가 락 획득의 성공 여부를 알 수 있도록 한다.

앞서 작성한 Test-And-Set 방법을 사용했을 때와 같은 방식으로 락을 만들 수 있다.

typedef struct __lock_t {
	int flag;
} lock_t;

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

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

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

락이 사용가능할 경우, actual, expected 모두 0이다. 이제 flag는 1로 변경되고 이를 리턴한다.
락이 사용 중인 경우, actua(1)과 expected(0)는 서로 다르다. while문을 회전하며 대기하다가, 다른 쓰레드에서 락을 해제하면 두 값이 0으로 같아져 flag를 다시 1로 설정하고, 락을 획득할 수 있다.

CompareAndSwap 명령어는 TestAndSet 보다 더 강력하다. 대기 없는 동기화(wait-free synchronization)를 다룰 때 알게될 것이다.

10. Load-Linked 그리고 Store-Conditional

어떤 플랫폼은 임계 영역 진입 제어 함수를 제작하기 위한 명령어 쌍을 제공한다. MIPS 구조에서는 load-linked와 store-conditional 명령어를 앞뒤로 사용하여 락 이나 기타 병행 연산을 위한 자료 구조를 만들 수 있다.

Alpha, PowerPC, 그리고 ARM에서도 유사한 명령어를 지원한다.

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

int StoreConditional(int *ptr, int value) {
	if (no one has updated *ptr since the LoadLinked to this address) {
		*ptr = value;
		return 1; // 갱신 성공
	} else {
		return 0; // 갱신 실패
	}
}

LoadLinked는 일반 로드 명령어와 같이 메모리 값을 레지스터에 저장한다. StoreConditional 명령어는 동일한 주소에 다른 store가 없었던 경우에만 저장을 성공한다. 성공한 경우 LoadLinked가 탑재했던 값을 갱신하고 1을 반환한다. 실패하면 갱신하지 않고 0을 반환한다.

void lock(lock_t *lock) {
while (1) {
	while (LoadLinked(&lock−>flag) == 1)
	; // 0이 될 때까지 spin
	if (StoreConditional(&lock−>flag, 1) == 1)
		return; // 1로 변경하는 것을 성공한 경우 완료
		// 아니라면 처음부터 다시 시도
	}
}

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

lock()부분의 코드를 보자. 쓰레드가 while 문을 돌며 flag가 0이 되기를 기다린다(락이 해제된 상태). 락이 획득 가능한 상태가 되면 쓰레드는 store-conditional 명령어로 락 획득을 시도하고 만약 성공한다면 쓰레드는 flag 값을 1로 변경한다. 그리고 임계 영역 내로 진입한다.

좀더 짧게 작성할 수도 있다.

void lock(lock_t *lock) {
	while (LoadLinked(&lock−>flag)||!StoreConditional(&lock−>flag, 1))
	; // spin
}

11. Fetch-And-Add

마지막 하드웨어 기반의 기법은 Fetch-And-Add 명령어로 원자적으로 특정 주소의 예전 값을 반환하면서 값을 증가시킨다.

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

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) {
	**// lock 획득을 원할 때, FetchAndAdd()를 통해 자신의 차례 획득**
	int myturn = FetchAndAdd(&lock−>ticket);
	**// 다른 쓰레드에서 락을 해제해 내 턴이 올때까지 spin-lock**
	while (lock−>turn != myturn)
	; // spin
}

void unlock(lock_t *lock) {
	FetchAndAdd(&lock−>turn);
}

하나의 변수만을 사용하는 대신 이 해법에서는 티켓(ticket) 과 차례(turn) 조합을 사용하여 락을 만든다. fetch-and-add를 통해 자신의 턴(myturn)을 확인하고, 자신의 차례(myturn == turn)일 때 임계영역에 진입한다. 언락 동작 시에는 turn을 증가 시켜 다음 차례를 알려준다.

이전까지 접근 방법과의 가장 중요한 차이점은 모든 쓰레드들이 각자의 순서에 따라 진행한다는 것이다. 쓰레드가 티켓 값을 할당받았다면, 미래의 어느 시점에 실행되기 위해 스케줄되어 있다는 것이다. 이전까지는 이러한 보장이 없었다. 예를 들어 Test-And-Set의 경우 다른 쓰레드들은 락을 획득/해제하더라도 어떤 쓰레드는 계속 회전만 하고 있을 수 있다. 즉 이번 해법은 *공정성에* 있다.

12. 요약: 과도한 스핀

이제까지 소개한 하드웨어 기반의 락은 간단하고, 그리고 제대로 동작한다. 하지만 때로는 이러한 해법이 효율적이지 않은 경우도 있다.

락을 소유중인 쓰레드 0이 실행 중 인터럽트가 발생하면, 락을 기다리는 또 다른 쓰레드는 계속해서 기다려야한다. N개의 쓰레드가 하나의 락을 획득하기 위해 경쟁하게 되면 상황이 더 심각해진다. N-1개의 쓰레드에 할당된 CPU 시간동안 spin하며 사이클이 낭비된다.

13. 간단한 접근법: 무조건 양보

하드웨어의 지원을 받아 많은 것을 해결하였다. 동작이 검증된 락과 락 획득의 공정성 (티켓 락을 사용한 경우)까지도 해결할 수 있었다. 그러면 쓰레드가 락을 해제하기를 기다리며 스핀만 무한히 하는 경우에는 어떻게 해야 할까?

가장 단순하고 친근한 방법은 락 해제를 기다리며 spin 해야하는 경우 cpu를 양보하는 것이다.

void init() {
	flag = 0;
}

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

void unlock() {
	flag = 0;
}

단일 CPU 시스템에서 이런 방식은 잘 작동한다. 락 획득을 시도했지만 다른 쓰레드가 사용 중이라면 CPU를 양보한다.

100개 정도의 쓰레드가 락을 획득하기 위해 경쟁하는 경우는 어떨까? 락을 기다리는 99개의 쓰레드들이 run-and-yield하게 될 것이다. spin-lock 보다는 나을 수도 있지만, 여전히 문맥 교환 비용을 생각하면 비효율적이다.

또한 굶주림 문제는 아직 손대지도 못했다. 어떤 쓰레드는 무한히 양보만 하고 있을 수도 있다.

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

이전 방법들은 너무 많은 부분을 운에 맡겼다. 스케줄러가 좋지 않은 선택을 한다면 기다리거나 CPU를 양보해야 한다. 둘 다 낭비의 여지가 있고 쓰레드가 굶주릴 수 있다.

어떤 쓰레드가 다음으로 락을 획득할지를 명시적으로 제어할 수 있어야 한다. 이를 위해 운영체제로부터 적절한 지원을 받고, 큐를 이용한 대기 쓰레드들을 관리할 것이다.

간단히 Solaris의 방식으로 해보자.

park(): 호출하는 쓰레드를 잠재우는 함수 unpark(threadID): threadID로 명시된 특정 쓰레드를 깨우는 함수

이 두 루틴은 이미 사용 중인 락을 요청하는 프로세스를 재우고 해당 락이 해제되면 깨우도록 하는 락을 제작하는 데 앞뒤로 사용할 수 있다.

TestAndSet 개념을 락 대기자 전용 큐와 함께 사용하여 효율적인 락을 만들 것이고, 큐를 사용하여 굶주림 현상을 방지할 것이다.

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 (TestAndSet(&m−>guard, 1) == 1)
	; // 회전하면서 guard 락을 획득
	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;
}

guard 변수를 사용하여 flag와 큐의 삽입과 삭제 동작을 스핀 락으로 보호한다. 이 방법은 스핀을 완전히 배제하지는 못했다. 하지만 스핀 대기 시간은 꽤 짧다. 사용자가 지정한 임계 영역에 진입하는 것이 아니라 락과 언락 코드 내의 몇 개의 명령어만 수행하면 되기 때문이다.

lock() 에 추가된 동작이 있다. lock()을 호출했는데 다른 쓰레드가 이미 락을 보유중이라면, gettid()를 호출하여 현재 실행 중인 쓰레드 ID를 얻고, 락 소유자의 큐에 자기 자신을 추가하고 guard 변수를 0으로 변경한 후 CPU를 양보한다.

다른 쓰레드가 깨어났을 때 flag 변수가 0으로 설정되지 않는다. 깨어날 때는 guard 락을 획득한 상태가 아니기 때문에 flag를 1로 변경할 수 없다. 따라서 그냥 1인 채로 두고 락을 획득하려는 다음 쓰레드로 직접 전달한다. flag는 0이 되었다 다시 1이 되는게 아니라 그냥 계속 1이다.

마지막으로, park() 직전에 경쟁 조건이 발생한다. 한 쓰레드는 락이 사용중이라 park()를 실행하려고 한다. 그 직전에 락 소유자한테 CPU가 할당되면 문제가 생길 수 있다.

경쟁 조건이 어떻게 발생하는가?

  1. B가 park()를 호출하기 바로 직전에 CPU 스케줄링이 발생하여 A가 실행된다.
  2. A가 락을 해제하고 B를 깨우기 위해 unpark()를 호출한다.
  3. 하지만 B는 아직 park()를 호출하지 않았으므로, 실제로는 깨워질 수 없다. 따라서 B는 락이 해제되었음에도 불구하고 계속 대기 상태에 머물게 된다.

이러한 문제를 해결하기 위해 Solaris 운영체제는 setpark() 시스템 콜을 도입했다.

guard 변수의 역할을 커널에서 담당하는 것도 하나의 방법이다. 커널은 락 해제와 실행 중인 쓰레드를 큐에서 제거하는 동작을 atomic하게 처리하기 위해 주의를 기울여야 한다.

15. 다른 운영체제, 다른 지원

좀 더 효율적인 락을 만들기 위한 운영체제 지원 내용을 살펴보았다. 다른 운영체제들도 유사한 기능을 지원하지만 세부적인 내용은 다르다.

Linux의 경우 futex라는 것을 지원한다. 각 futex는 특정 물리 메모리 주소와 연결되어 있으며 futex마다 커널 내부의 큐를 밖고 있다. 호출자는 futex를 호출하여 필요에 따라 잠을 자거나 깨어날 수 있다.

  • futex_wait(address, expected) address 값이 expected와 같으면 쓰레드를 잠재운다. 같지 않다면 즉시 리턴한다.
  • futex_wake(address) 큐에서 대기하는 쓰레드 하나를 깨운다.
void mutex_lock (int *mutex) {
	int v;
	
	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;
	}

	v = *mutex;
	if (v >= 0)
		continue;
	futex_wait (mutex, v);
	}
}

void mutex_unlock (int *mutex) {

	if (atomic_add_zero (mutex났 0x80000000))
		return;
	
	futex_wake (mutex);

16. 2단계 락

2단계 락 기법은 락이 곧 해제될 것 같은 경우라면 회전 대기가 유용할 수 있다는 것에서 착안하였다.

첫 번째 단계에서는 곧 락을 획득할 수 있을 것이라는 기대로 회전하며 기다린다. 만약 첫 회전 단계에서 락을 획득하지 못했다면 두 번째 단계로 진입하여 호출자는 잠에 빠지고 락이 해제된 후에 깨어나도록 한다.

앞서 본 Linux의 락은 이러한 형태를 갖는 락이지만 한 번만 회전한다. 일반화된 방법은 futex가 잠재우기 전에 일정 시간 동안 반복문 내에서 회전하도록 하는 것이다.

17. 요약

방금 보인 기법은 락이 실제 어떻게 구현되는지를 보여준다. 일부 하드웨어 지원 (강력한 명령어의 형태)과 일부 운영체제의 지원(예, park()와 unpark()와 같은 형태)을 받아 락을 구현하였다.

profile
JiYun
고수가 되고싶다
이전 포스트

OSTEP 27 - Thread API

다음 포스트

OSTEP 29 - Locked Data Structures

0개의 댓글