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

1. Compare-And-Swap

몇몇 시스템들이 제공하는 하드웨어 기초 연산은 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과 비슷하게, compare-and-swap으로도 락을 만들 수 있다. 예를 들어 앞서의 lock() 루틴을 다음과 같이 바꿀 수 있다.

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

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

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에 있다. 이 명령어는 해당 주소에 어떠한 저장도 끼어들지 않은 경우에만 성공한다. 성공하는 경우 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에서의 실패가 어떻게 일어날 수 있는지를 살펴보자. 한 스레드는 lock()을 호출하고 load-linked를 실행하는데, 현재 락이 사용 가능한 상태이므로 0을 반환한다. 그런데 이후 store-conditional을 실행하려 하기 전에, 인터럽트가 발생해 다른 스레드가 락 코드에 진입해 load-linked 명령어를 실행하고 0을 얻고 계속 진행했다고 해보자. 이때 두 스레드는 모두 각각 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;
}

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

이 해결법과 이전 해결법들 사이의 중요한 차이들에 대해 주의하자. 이 해결법은 모든 스레드가 진행될 것임을 보장한다. 즉 한 스레드는 일단 티켓 값을 할당 받으면, 이 스레드는 미래의 어떤 시점에 실행될 것으로 스케줄링된다. 이전의 시도들에서는 그런 보장이 없어, 예를 들어 test-and-set에서 스핀 대기 중인 스레드는 영원히 스핀하게 될 수도 있었다.