[OS] CH28_Locks: Critical section / Lock 방법 비교

28.1 Locks: The Basic Idea

 

critical section: 공유 변수를 업데이트하는 부분

1 lock_t mutex; // some globally-allocated lock ’mutex’
2 ...
3 lock(&mutex);
4 balance = balance + 1;  // critical section
5 unlock(&mutex);

critical section thread만 hold할 수 있다.

lock()을 호출하면 lock을 얻도록 노력하고 만얀 lock을 hold하고 있는 다른 thread가 없다면 이 thread는 lock을 얻고 critical section에 진입할 수 있다. (이 thread를 the owner of the lock이라고도 부름)

lock owner가 unlock() 호출하면, lock은 다시 available(free)됨. lock을 기다리는 thread가 없다면 그냥 free상태됨.

만약 기다리던 thread가 있다면 lock 상태가 변한 것을 알아채고 lock 얻고 critical section 진입

 

lock은 프로그래머에게 스케쥴링에 대한 최소한의 컨트롤을 제공.

Lock 분야의 컨트롤의 일부는 프로그래머에게 있다 (lock code 넣기)

 

28.2 Pthread Locks

mutex: POSIX 라이브러리가 lock을 위해 사용하는 것의 이름

ㄴ thread들 사이에서 상호 배제(mutual exclusion)를 제공

i.e. 한 thread가 critical section에 있다면 이것이 이 구간을 완료할 때까지 이 구간은 다른 thread들로부터 배제된다.

 

1 pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
2
3 Pthread_mutex_lock(&lock); // wrapper; exits on failure
4 balance = balance + 1;
5 Pthread_mutex_unlock(&lock);

28.3 Building A Lock 

Lock을 만드려면 하드웨어의 지원이 필요하다

 

28.4 Evaluating Locks

- Mutual exclusion: lock이 잘 작동하는가 (critical section에서 atomicity를 보장하는가)

- Fairness: starvation 없이 각각의 thread가 공평하게 lock을 얻을 수 있는가

- Performance: lock을 사용할 때 생기는 cost

 

28.5 Controlling Interrupts

Disable inturrupts for critical sections

1 void lock() {
2 	DisableInterrupts();
3 }
4 void unlock() {
5	 EnableInterrupts();
6 }

간단한 방법이지만 문제점이 많다.

단일 프로세서 시스템에서만 정상적으로 작동됨. -> multiprocessor 환경에서는 작동 안됨

어떤 thread가 enable 안하고 계속 쓰면 계속 기다릴 수밖에 없음

 

28.6 A Failed Attempt: Just Using Loads/Stores

 typedef struct __lock_t { int flag; } lock_t;

 void init(lock_t *mutex) {
 	// 0 -> lock is available, 1 -> held
	 mutex->flag = 0;
 }

 void lock(lock_t *mutex) {
 	while (mutex->flag == 1) // TEST the flag
 		; // spin-wait (do nothing)
	 mutex->flag = 1; // now SET it!
 }

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

문제1. No mutual exclusion

만약 thread1이 lock을 얻고 flag를 1로 바꾸려는 찰라 context switch가 일어난다면 thread2는 lock에 접근 했을 때, 아직 flag가 0이므로 lock을 얻는다

 

문제2. Spin-waiting wastes time waiting for another thread.

 

-> 그래서 하드웨어 지원이 필요함 (test-and-set instruction, also known as atomic exchange)

 

28.7 Building Working Spin Locks with Test-And-Set

하드웨어 지원을 통한 lock 구현

 

typedef struct __lock_t {
 	int flag;
 } lock_t;

 void init(lock_t *lock) {
	 // 0: lock is available, 1: lock is held
	 lock->flag = 0;
 }

 void lock(lock_t *lock) {
	 while (TestAndSet(&lock->flag, 1) == 1)
	 ; // spin-wait (do nothing)
 }

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

while (TestAndSet(&lock->flag, 1) == 1)  <- test랑 set 동시에 함

 

* 단일 프로세서에서 정확하게 작동되려면 preemptive scheduler가 필요하다

 

28.8 Evaluating Spin Locks

Correctness: yes

Fairness: no  (spin-wait 계속될 수 있음)

Performance: 단일 CPU에서는 no

                  thread 여러 개일 때(=CPU 여러 개일 때) yes

 

 

28.9 Compare-And-Swap

또다른 Hardware primitive는 compare-and-swap 명령 혹은 compare-and-exchange라고 부른다

기본 아이디어: ptr이 가리키는 주소에 있는 값이 expected랑 같은지 테스트한다.

만약 그렇다면, 아무것도 하지 않는다.

아니라면, 메모리에 있던 원래 값을 리턴해서 compare-and-swap을 호출하는 코드가 성공인지 실패인지 알게함.

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

28.10 Load-Linked and Store-Conditional

load-linked 연산은 일반적인 load 명령이랑 유사하게 작동하며, 메모리에서 값을 가져 와서 레지스터에 저장한다.

주요 차이점은 store-conditional에서 발생한다. store-conditional은 주소에 대한 중간 저장소가 없는 경우에만 성공하고 (load-linked로부터 값을 저장한다)

성공하는 경우, store-conditional은 1을 리턴하고 ptr의 값을 value로 업데이트한다.

만약 실패하면 ptr의 값은 업데이트되지 않고 0을 리턴한다.

 

1. thread는 flag가 0으로 set될 때까지 spin-waiting

2. thread는 store-conditional을 통해서 lock을 얻기를 기다림

3. 성공하면 thread는 자동적으로 flag 값을 1로 바꾸고 critical section에 들어올 수 있음

 

store-conditional이 실패하는 경우

하나의 thread가 lock()을 호출하고 load-linked를 실행하고 lock이 hold되지 않았으면 0을 리턴

store-conditional 시도하기 전에 이것은 interrupt되고 다른 thread는 lock code에 들어가서 load-linked instruction을 실행함 그리고 0을 얻고 계속 진행

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

int StoreConditional(int *ptr, int value) {
 	if (no update to *ptr since LoadLinked to this address) {
	 *ptr = value;
	return 1; // success!
 } else {
 	return 0; // failed to update
 }
}

2개의 thread는 각각 load-linked를 수행하고 store-conditional을 시도한다. 

이러한 명령의 주요 특징은 하나의 thread는 flag를 1로 업데이트하는데 성공하고 lock을 얻는다.

다른 thread는 store-conditional을 시도하지만 실패한다.

 

28.11 Fetch-and-add

마지막 hardware primitive는 fetch-and-add 명령이다. 이것은 특정 주소의 이전 값을 리턴하면서 값을 atomically하게 증가시킨다.

fetch and add로 ticket lock을 생성할 수 있음

 

thread가 잠금을 얻고자 할 때, 먼저 ticket value에 대한 atomic fetch-and add를 수행한다.

이 값은 이제 thread의 "turn"(myturn)

전역으로 공유하는 lock->turn으로 어떤 thread의 turn인지 알아냄 

mythread==turn인 thread가 critical section으로 진입

 

* 모든 thread 실행을 보장

 

28.12 Too much spinning: What now?

hardware-based spin lock은 단순하고 작동되지만, 자기 차례올 때까지 계속 spin 돌며 기다려야 하므로 비효율적이다.

-> spinning을 피하려면 os의 지원이 필요하다

 

28.13 A simple approach: Just yield, baby

lock 접근 했는데 누가 쓰고 있으면 CPU 포기함 -> 현재 job을 포기한 것, 다음 턴에 다시 접근 가능

문제점: context switch로 인한 cost / starvation

 

thread state: running/ready/blocked 중 하나

yield는 running 상태에서 ready 상태로 바꾸는 system call이다 -> CPU 포기

 

28.14 Using Queues: Sleeping instead of spinning

Queue가 어떤 thread들이 lock에 진입하길 대기 중인지 track을 저장함

park(): 호출한 thread를 sleep 시킴 -> scheduler에서 제외 시킴 (wake하면 다시 scheduler에 올려짐)

unpark(threadID): threadID로 지정된 thread를 깨움

 

만약 park() (thread2)에 대한 호출 전에 lock (thread1)을 해제하는 경우, thread2는 영원히 sleep

-> setpark() system call을 이용하여 문제 해결

 

setpark(): thread가 park를 나타낼 수 있다.

만약 park()가 호출되기 전에 interrupted되거나 다른 thread가 unpark()를 호출하면 park()는 즉시 리턴됨(sleep안하고)

 

28.15 Differnt OS, Different Support

Linux가 제공하는 Futex (Solaris의 park(), unpark()와 비슷)

- futex_wait(address, expected) :

  호출한 thread를 sleep 시킴

  만약 address의 값과 expected랑 다르면 바로 리턴됨

- futex_wake(address)

  queue에서 기다리고 있는 하나의 thread를 wake

 

28.16 Two-phase locks

- first phase

  lock 얻기를 희망하면서 잠시 lock spin

  first spin phase 동안 lock을 얻지 못하면 second phase에 진입

- second phase

  부른 thread를 sleep 시킴

  lock이 free되면 그 때 다시 wake