[OSTEP 운영체제 정리] - Lock

너무 덥지만 Lock을 알아보자...

락: 기본 개념

balance = balance + 1;

lock_t mutex; // 글로벌 변수로 선언된 락
 …
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

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

 

[ 락의 상태 ]

사용가능( available, (unlocked or free)): 어느 쓰레드도 락을 갖고 있지 않는 것

사용중(acquired) : 즉, 임계 영역에서 정확히 하나의 쓰레드가 락을 획득한 상태

lock()

• 호출을 통해 락 획득을 시도한다.
• 만약 어떤 쓰레드도 락을 갖고 있지 않으면, 그 쓰레드는 락을 획득하여 임계영역 내로 진입

⇒ 진입한 쓰레드 : 락의 소유자(owner)

다른 스레드는 잠금을 보유한 첫 번째 스레드가 임계 영역에 있는 동안 임계 영역에 들어가는 것이 방지된다.

Pthread 락

쓰레드 간에 상호 배제 기능을 제공하기 때문에 이 락을 mutex 라고 부른다.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
...
pthread_mutex_lock(&lock); // pthread_mutex_lock()을 위한 래퍼
counter = counter + 1; // critical section
pthread_mutex_unlock(&lock);

락 구현

락을 만들기 위해 어떤 하드웨어와 운영체제의 지원이 필요한가?

락의 평가

만들기 전에 평가를 이해해서 목표 파악한다.

Mutual exclusion(상호배제)

  : 상호배제를 제대로 지원하는가. 기본적으로 락이 동작하여 임계 영역 내로 다수의 쓰레드가 진입을 막을 수 있는지 검사해야한다.

Fairness(공정성)

  : 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가? : 잠금을 얻기 위해 경쟁하는 모든 스레드는 잠금이 해제되면 공평하게 획득할 기회를 갖게 된다.

Performance(성능)

  : 락 사용 시간적 오버헤드 평가, 쓰레드의 개수, CPU의 수

인터럽트 제어

void lock() {
	DisableInterrupts();
}

void unlock() {
	EnableInterrupts();
}

장점 : 단순하다.

단점 :

- 요청을 하는 쓰레드가 인터럽트를 활성/비활성화하는 특권 연산을 실행할 수 있도록 허가해야된다.

- 멀티프로세서에서 적용할 수 없다.

- 장시간 동안 인터럽트를 중지시키는 것은 중요한 시점을 놓칠 수 있다.

 

✅ 상호 배제를 위해 인터럽트를 비활성화하는 것은 제한된 범위에서만 사용되어야한다. (특정 복잡한 인터럽트 처리 상황을 방지하기 위해)

Spin Locks with Loads/Stores

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;
} 

 

⇒ No mutual exclusion

스핀 대기는 다른 스레드가 잠금을 해제하기를 기다리는 동안 시간을 낭비한다.

진짜 돌아가는 스핀 락의 구현, Spin Locks with Test-and-Set

TestAndSet : 검사하는 동시에 메모리에 새로운 값 설정
int TestAndSet(int *old_ptr, int new) {
	int old = *old_ptr; // old_ptr 의 이전 값을 가져옴
	*old_ptr = new; // old_ptr 에 ’new’ 의 값을 저장함
	return old; // old의 값을 반호나
} 

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 *mutex) {
	mutex->flag = 0;
} 

 

이것은 Not Fair

단일 CPU에서, 성능 오버헤드가 크다

[ Evaluating Spin Locks ]

1. 상호배제의 Correctness ✅
2. 스핀락은 임의의 시간에 단 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 한다.
3. Fairness ❌
4. 스핀락은 어떠한 공정성도 보장해줄 수 없다. 게다가 하나의 쓰레드는 계속해서 스핀 될 것이다.
5. Performance
6. 단일 CPU의 경우, 스핀락이 갖는 성능 오버헤드는 상당히 클 수 있다. ⇒ 굳이 while? CPU가 여러개인 경우 스핀락은 꽤 합리적으로 동작한다. ⇒ while 낭비까진 아니여서 효율

Spin Locks with Compare-and-Swap

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

void lock(lock_t *lock) {
	while (CompareAndSwap(&lock->flag, 0, 1) == 1); //회전
}

 

개념

: ptr이 가르키고 있는 주소의 값이 expected 변수와 일치하는지 검사하는 것 : 만약 일치한다면, ptr이 가리키는 주소의 값을 새로운 값으로 변경, 아니라면 원래값을 반환하여 CompareAndSwap을 호출한 코드가 락 획득의 성공 여부를 알 수 있도록 한다.

test-and-set 방법을 사용했을 때와 같은 방식으로 락 만들기 가능

Ticket Locks, Fetch-And-Add

원자적으로 특정 주소의 예전 값을 반환하면서 값을 증가시킨다.

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

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

하나의 변수만을 사용하는 대신, 이 해법에서는 티켓과 차례 조합을 사용하여 락을 만든다. 결과 값은 쓰레드의 차례를 나타낸다.

---

 

여태껏 하드웨어의 지원을 받아 해결… ⇒ 문제는 너무 많은 스핀을 돈다.

void lock(lock_t *lock) {
	while (TestAndSet(&lock->flag, 1) == 1)
	yield(); //CPU를 양보함
}

단순하고 친숙한 방법을 쓰자

락이 해제되기를 기다리며 스핀해야하는 경우, 자신에게 할당된 CPU를 다른 쓰레드에게 양보하자 !

실행 ⇒ 준비 상태로 변환

라운드로빈 스케줄러를 사용하는 경우라면 락을 갖고 있는 쓰레드가 다시 실행되기까지 99개의 쓰레드가 실행하고 양보하는 패턴, 비용과, 문맥교환 비용이 상당하다 ! 또한 starvation 현상을 막지 못한다.

큐의 사용, 스핀 대신 잠자기

typedef struct __lock_t {
	int flag; // lock
	int guard; // spin-lock around the flag and
	// queue manipulations
	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(); // wakeup/waiting race
	}
}

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;
}

Futex

Linux의 경우 Futex를 지원한다.

Futex는 특정 물리 메모리 주소와 연결이 되어 있으며 Futex마다 커널 내부의 큐를 갖고 있다. 호출자는 필요에 따라 잠을 자거나 깰 수 있다.

futex_wait(address, expected)

address값과 expected 값이 동일한 경우 쓰레드를 잠재우고, 같지 않다면 즉시 리턴

futex_wake(address)

큐에서 대기하고 있는 쓰레드를 하나 깨운다.

이 코드에서 하나의 정수를 이용하여 락의 사용중 여부와, 대기자 수를 표현한다.

만약 락이 음수라면, 락이 사용중인 것을 나타낸다.

이 코드가 흥미로운 이유는 경쟁이 없이 일반적인 경우라면 아주 약간만 일을 하도록 하였다.

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);
}

Two-Phase Locks

이중 단계 잠금은 잠금이 곧 해제될 경우 스핀 대기가 유용할 수 있음을 인식한다.

First phase

  잠금이 해제되기를 기대하며 잠시 동안 스핀 대기한다.

  이 첫 번째 스핀 단계 동안 잠금이 획득되지 않으면, 두 번째 단계로 넘어간다.

Second phase

  호출자는 대기 상태로 전환

  잠금이 나중에 해제되면 호출자는 깨워진다.

---

[출처]
https://github.com/remzi-arpacidusseau/ostep-translations/blob/master/korean/README.md

ostep-translations/korean/README.md at master · remzi-arpacidusseau/ostep-translations

해당 책을 기반으로 정리하였습니다.