Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

1. Compare-And-Swap (CAS)

몇몇 시스템들은 compare-and-swap, 또는 compare-and-exchange라 불리는 하드웨어 명령어를 제공한다.

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

compare-and-swap의 기본적인 아이디어는 ptr로 명시된 주소에 있는 값이 expected와 같은지를 테스트해보는 것이다. 만약 같다면 ptr가 가리키는 메모리의 위치를 새로운 값으로 업데이트하고, 그렇지 않으면 아무 것도 하지 않는다. 모든 경우에 메모리 위치에 있던 원래의 값을 리턴함으로써 compare-and-swap을 호출한 코드에 이 작업이 성공했는지의 여부를 알려준다.

test-and-set(TAS)과 비슷하게 compare-and-swap으로도 락을 만들 수 있다. 예를 들어 앞서의 lock() 루틴을 다음과 같이 바꾸면 된다.

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

동작 자체는 test-and-set과 비슷하다. 플래그가 0인지를 확인하고, 만약 0이라면 원자적으로 해당 값을 1로 바꿔 락을 획득한다. 락이 다른 스레드에 의해 소유되고 있는 상태에서 락을 얻으려고 하는 스레드들은 해당 락이 풀릴 때까지 스핀한다.

보통 TAS는 락이 걸렸는지/안 걸렸는지만 확인하는 데만 쓸 수 있지만, CAS의 경우에는 임의의 값을 비교/교체할 수 있다. 예를 들어 PID나 TID를 쓸 수도 있다.

2. Load-Linked and Store-Conditional

어떤 플랫폼은 임계 영역을 만드는데에 도움을 되는 명령어 쌍을 제공하기도 한다. 예를 들어 MIPS 아크텍처의 load-linked와 store-conditional 명령어 쌍이 그렇다.

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

int StoreConditional(int *ptr, int value){
	if (no update to *ptr since LL to this addr){
		*ptr = value;
		return 1;
	}
	return 0;
}

load-linked는 전형적인 load 명령어와 비슷하게 메모리로부터 값을 가져와 레지스터에 넣는다. 핵심적인 차이는 store-conditional에 있는데, 이 명령어는 load-linked 이후 어떤 저장도 일어나지 않은 경우에만 성공한다.

성공하는 경우 store-conditional은 ptr에 있는 값을 value로 업데이트하고 1을 리턴하고, 실패하는 경우에는 업데이트가 되지 않고 0이 반환된다.

void lock(lock_t *lock) {
	while (1) {
		while (LoadLinked(&lock->flag) == 1)
			; // spin until it’s zero
		if (StoreConditional(&lock->flag, 1) == 1)
			return; // if set-to-1 was success: done
					// otherwise: try again
	}
}

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

lock() 코드를 보자. 스레드는 플래그가 0이 될 때까지 대기하며 스핀한다. 만약 플래그가 0이 되면, 스레드는 store-conditional을 통해 락을 얻으려 한다. 만약 성공하면 스레드는 원자적으로 플래그의 값을 1로 바꿔 임계 영역으로 진입할 수 있게 있게 된다.

store-conditional에서의 실패가 어떻게 일어날 수 있는지를 살펴보자.

1. 한 스레드가 lock()을 호출하고 load-linked를 실행하는데, 현재 락이 사용 가능한 상태이므로 0을 반환한다.
2. 이후 store-conditional을 실행하려 하기 전에 인터럽트가 발생해, 다른 스레드가 lock() 코드에 진입해 load-linked 명령어를 실행하고 0을 얻고 계속 진행했다고 해보자.
3. 이때 두 스레드는 모두 각각 load-linked를 실행하고 store-conditional을 실행하려 하지만, 이 스레드들 중 단 하나만이 플래그를 1로 업데이트하는 데 성공하고 락을 얻을 수 있다. store-conditional을 실행하려하는 두 번째 스레드는 실패할 것이고, 다시 락을 얻으려 시도한다.

3. Fetch-And-Add

마지막 하드웨어 기초 연산은 fetch-and-add 명령어다. 이 명령어는 원자적으로 특정 주소의 값을 증가시키고 원래의 값을 반환한다. fetch-and-add 명령어의 C 의사 코드는 다음과 같다.

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

이 예제에서는 fetch-and-add를 이용해 티켓 락(ticket lock)을 만들 것이다. 코드는 다음과 같다.

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) {
	lock->turn = lock->turn + 1;
}

이 방법은 락을 만들기 위해 하나의 값만이 아니라, 티켓과 턴 변수의 조합을 사용한다.

1. 스레드는 락을 얻기 전, 먼저 티켓 값에 원자적인 fetch-and-add를 수행한다. 이 값은 이 스레드의 turn(myturn)으로 생각된다.
2. 이후 전역적으로 공유되는 lock->turn은 어떤 스레드의 턴인지를 결정하기 위해 사용된다.
3. 만약 lock->turn이 특정 스레드가 가지고 있는 턴(myturn)과 같다면, 이는 그 스레드가 임계 영역에 들어갈 턴이라는 말이다.
4. 언락은 간단하게 턴을 증가시키고, 대기 중인 다음 스레드가 임계 영역에 들어갈 수 있게 됨으로써 이루어진다.

이 방법의 가장 큰 특징은 모든 스레드가 임계 영역에 진입할 수 있음을 보장한다는 점이다. 즉 한 스레드는 일단 티켓 값을 할당 받고나면, 미래에 언젠가는 실행될 것으로 스케줄링된다. 이전 방법에서는들에서는 그런 보장이 없어, 스핀 대기 중인 스레드는 영원히 스핀할 수도 있었다.