1️⃣ 락: 기본 개념

balance = balance + 1;

위와 같은 임계 영역을 다음과 같이 락으로 감싼 상황을 가정해보자.

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

위의 코드에서 나타나는 특징들을 하나씩 살펴보자.

락은 하나의 변수이다.

락을 사용하기 위해서는 락 변수를 먼저 선언해야 한다.

락 변수는 락의 상태를 나타낸다.
✅ 사용 가능(available) 상태(해제(unlocked) 또는 free): 어느 쓰레드도 락을 갖고 있지 않은 상태
🚫 사용 중(acquired): 임계 영역에서 정확히 하나의 쓰레드가 락을 획득한 상태

락 자료 구조에 락을 보유한 쓰레드에 대한 정보나 락을 대기하는 쓰레드들에 대한 정보를 저장할 수도 있음.
➡️ 단, 락 사용자는 이러한 정보를 알 수 없음.

lock( )과 unlock( ) 루틴

🔒 lock() 루틴 호출을 통해 락 획득을 시도
➡️ 만약 어떤 쓰레드도 락을 갖고 있지 않다면, 락을 획득하여 임계 영역 내로 진입
➡️ 임계 영역 내로 진입한 쓰레드를 락 소유자(owner)라고 부름.
➡️ 락이 이미 사용 중이라면, lock() 함수가 리턴하지 않음.

🔓 락 소유자가 unlock()을 호출
➡️ 락은 다시 사용 가능한 상태가 됨.
➡️ lock() 호출 후 대기 중이던 쓰레드가 있다면, 락을 획득하여 임계 영역 내로 진입

락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공

일반적으로 쓰레드는 프로그래머가 생성하고 운영체제가 제어
➡️ 락은 쓰레드에 대한 제어권을 일부 이양 받을 수 있도록 해줌.

💡 락으로 코드를 감싸서 프로그래머는 그 코드 내에서는 하나의 쓰레드만 동작하도록 보장

2️⃣ Pthread 락

Mutex

쓰레드 간에 상호 배제(mutual exclusion) 기능을 제공하므로 POSIX 라이브러리는 락을 mutex라고 부름.

POSIX의 락 사용 방식

POSIX 방식에서는 변수 명을 지정하여 락과 언락 함수에 전달
➡️ 다른 변수를 보호하기 위해서 다른 락을 사용할 수도 있기 때문
➡️ 💡 세밀한 락 사용 전략

[거친(coarse-grained) 락 사용 전략]
하나의 락이 임의의 임계 영역에 진입할 때마다 사용

[세밀한(fine-grained) 락 사용 전략]
서로 다른 데이터와 자료 구조를 보호하기 위해 여러 락을 사용
➡️ 한 번에 여러 쓰레드가 서로 다른 락으로 보호된 코드 내에 각자가 진입 가능

3️⃣ 락 구현

효율적인 락 = 낮은 비용 + 상호 배제 기법 제공 & 몇 가지 속성들

사용 가능한 락을 만들기 위해서 하드웨어와 운영체제의 도움을 받아야 함.

정교한 락 라이브러리를 제작하는 데 있어 운영체제가 관여하는 것은 무엇인지 알아보자.

4️⃣ 락의 평가

락이 (잘) 동작하는지 평가하기 위한 기준을 정해야 한다.

상호 배제를 제대로 지원하는가

락의 가장 기본적인 역할이다.

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

공정성(fairness)

쓰레드들이 락 획득에 있어 공정한 기회가 주어지는지 확인해야 한다.

이 문제의 다른 관점: 좀 더 극단적인 상황을 평가
➡️ 락을 전혀 얻지 못해 굶주리는(starve) 경우가 발생하는가?

성능(performance)

특히, 락 사용 시간적 오버헤드를 평가해야 한다.

⛏️ 경쟁이 전혀 없는 경우

• 하나의 쓰레드가 실행 중에 락을 획득하고 해제하는 과정에서 발생하는 부하는 얼마나 되는가?

⚔️ 여러 쓰레드가 단일 CPU 상에서 락을 획득하려고 경쟁하는 상황

♟️ 멀티 CPU 상황에서 락 경쟁 시의 성능

이처럼 서로 다른 상황의 성능을 평가하여야 다양한 락 기법들이 성능에 미치는 영향을 이해할 수 있음.

5️⃣ 인터럽트 제어

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

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

이 경우 임계 영역 내의 코드에서는 인터럽트가 발생할 수 없기 때문에 원자적으로 실행될 수 있음.

✅ 주요 장점: 단순하다.
인터럽트가 발생하지 않으면, 코드가 실행 중에 다른 쓰레드가 중간에 끼어들지 않는다는 것을 보장

⚠️ 단점1: 이를 요청하는 쓰레드에게 인터럽트 활성/비활성 특권(privileged) 연산 허가
쓰레드가 이를 다른 목적으로 사용하지 않음을 신뢰해야 함.
➡️ 탐욕적(Greedy) 기법을 사용한 프로그램이 시작과 동시에 lock()을 호출하여 프로세서를 독점하는 경우..

⚠️ 단점2: 멀티프로세서에서는 적용 불가
여러 쓰레드가 여러 CPU에서 실행 중인 경우 각 쓰레드가 동일한 임계 영역에 진입하려고 시도할 수 있음.
➡️ 특정 프로세서의 인터럽트 비활성화는 다른 프로세서에서 실행 중인 프로그램에는 전혀 영향을 주지 않음.

⚠️ 단점3: 인터럽트의 장시간 중지는 중요한 인터럽트의 시점을 놓칠 수 있음.
때로는 시스템에 심각한 문제를 가져 올 수 있음.
➡️ CPU가 저장 장치에서 읽기 요청을 마친 사실을 모르고 지나간다면 이를 기다리고 있는 프로세스는 언제 깨울 수 있을까..

⚠️ 단점4: 비효율적이다.
일반적인 명령어의 실행에 비해 인터럽트를 비활성화시키는 코드들은 최신의 CPU들에서는 느리게 실행되는 경향이 있음.

💡 따라서 상호 배제를 위한 인터럽트 비활성화는 제한된 범위에서만 사용되어야 한다.
➡️ 운영체제가 내부 자료 구조에 대한 원자적 연산을 위해 인터럽트를 비활성화하는 등
➡️ 운영체제 내부에서는 신뢰라는 문제가 사라지므로 용인 가능

6️⃣ Test-And-Set (Atomic Exchange)

멀티프로세서에서는 인터럽트를 중지시키는 것이 의미가 없음.
➡️ 시스템 설계자들은 락 지원을 위한 하드웨어를 설계하기 시작함.

💡 Test-And-Set 명령어 또는 원자적 교체(atomic exchange)
➡️ 하드웨어 기법 중 기장 기본적인 기법

이해를 위해 먼저 아래의 코드를 살펴보자.

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

💡 간단한 변수(flag)를 사용하여 쓰레드가 락을 획득하였는지를 나타낸다.

그러나 위의 코드에는 두 가지 문제가 있다.

⚠️ 문제1: 정확성
위의 예시에서 적시에 인터럽트가 발생하면 두 쓰레드 모두 플래그를 1로 설정하는 경우가 생길 수 있음.
➡️ 임계 영역에 두 쓰레드가 다 진입할 수 있음.
➡️ 🚫 상호 배제 제공 실패

⚠️ 문제2: 성능
사용 중인 락을 대기할 때 spin-wait라는 방법을 사용
➡️ 플래그의 값을 무한히 검사하므로, 다른 쓰레드가 락을 해제할 때까지 시간을 낭비
➡️ 특히, 단일 프로세서에서 매우 손해가 큼.(적어도 문맥 교환이 있기 전까지는 락을 소유한 쓰레드조차 실행X)

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

앞선 아이디어는 하드웨어 지원 없이는 동작이 불가능
➡️ 일부 시스템은 이 개념에 근간한 락 구현을 위한 (어셈블리) 명령어를 제공

아래와 같이 시스템마다 명령어의 이름은 다르지만,

• SPARC: ldstub(load/store unsigned byte 동작)

• x86: xchg(원자적 교체 명령어)

기본적으로 동일한 일을 수행하며 일반적으로 Test-And-Set라고 불린다.

다음의 C 코드의 일부를 사용하여 TestAndSet의 동작을 정의해 보자.

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

위의 코드를 통해 "test and set"이라고 불리는 이유를 알 수 있다.
➡️ "test"하는(반환되는 값) 동시에 메모리에 새로운 값을 "set"하기 때문

✅ 핵심은 이 동작들이 원자적으로 수행된다는 것

이제 6️⃣의 예시 코드에서 lock() 함수를 다음과 같이 재작성하여 간단한 스핀 락(spin lock)을 만들 수 있다.

void lock(lock_t *lock) {
  while (TestAndSet(&lock−>flag, 1) == 1);
  // 스핀(아무 일도 하지 않음)
}

💡 위의 락이 동작하는 이유를 다시 짚어보자.

1. 한 쓰레드가 lock() 요청 시 아직 다른 어떤 쓰레드도 락을 보유하고 있지 않고 있음.

   1. flag 값은 0

2. 해당 쓰레드가 TestAndSet(flag, 1)을 호출

   1. TestAndSet()은 flag의 이전 값인 0을 반환

3. flag 값을 검사한 쓰레드는 while 문에서 회전하지 않고 락 획득

4. 해당 쓰레드는 flag 값을 1로 설정하여 락을 보유하고 있음을 표시

5. 임계 영역 내의 동작을 끝마치면 unlock()을 호출하여 flag를 다시 0으로 변경

락이 사용 중이어서 flag 값이 1인 경우의 동작도 생각해보자.

1. 쓰레드가 lock()을 호출하여 TestAndSet(flag, 1) 루틴을 실행한다.

2. 이미 락을 다른 쓰레드가 보유하고 있으므로 예전 값으로 1을 반환하는 동시에 flag의 값을 다시 1로 설정한다.

   1. 락을 보유하고 있는 쓰레드가 있는 한 TestAndSet는 계속 1을 반환

   2. 대기 중인 쓰레드는 락이 해제될 때까지 계속 while 문을 반복

3. 락을 보유하고 있던 쓰레드가 flag 값을 0으로 변경

4. 대기 중이던 쓰레드가 TestAndSet()를 호출하여 0을 받는 동시에 원자적으로 값을 1로 변경

5. 임계 영역으로 진입

✅ 락의 값을 검사(test)하고 새로운 값으로 설정(set)하는 동작을 원자적 연산으로 만듦으로써 오직 하나의 쓰레드만 락을 획득할 수 있도록 만듦.

💡 스핀 락

• 가장 기초적인 형태의 락

• 락을 획득할 때까지, CPU 사이클을 소모하면서 회전

• 단일 프로세서에서 이 방식을 제대로 사용하려면 선점형 스케줄러(preemptive scheduler)를 사용하여야 함.

  • 선점형 스케줄러는 필요에 따라 다른 쓰레드가 실행될 수 있도록 타이머를 통해 쓰레드에 인터럽트를 발생시킬 수 있음.

  • 선점형 스케줄러가 아니라면 while 문을 회전하여 대기하는 쓰레드가 CPU를 영원히 독점

8️⃣ 스핀 락 평가

락에서 가장 중요한 측면은 상호 배제의 정확성
➡️ 스핀 락은 임의의 시간에 단 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 함.

하지만 스핀 락은 어떠한 공정성도 보장해줄 수 없음.
➡️ while 문을 회전 중인 쓰레드는 경쟁에서 밀려 계속 그 상태에 남아 있을 수 있음.

성능을 평가하기 위해서는 몇 가지 경우를 생각해보아야 함.

1. 단일 프로세서를 사용할 때 락을 획득하기 위해 경쟁하는 경우

   1. 스핀 락이 갖는 성능 오버헤드는 상당히 클 수 있음.

   2. 스케줄러가 락을 대기 중인 쓰레드들을 하나씩 깨우는 경우 할당받은 기간 동안 CPU 사이클을 낭비하면서 락을 획득하기 위해 대기

2. 여러 프로세서에 쓰레드가 퍼져 있는 경우

   1. 스핀 락은 꽤 합리적으로 동작

   2. 락을 대기 중인 쓰레드가 락을 사용 중인 쓰레드와 다른 CPU에서 실행 중인 경우 while 문을 회전하면서 대기하는 것은 그렇게 많은 사이클을 낭비하지 않음.

9️⃣ Compare-And-Swap

또 다른 하드웨어 기법으로 Compare-And-Swap(SPARC)/Compare-And-Exchange(x86)가 있다.

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

💡 기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사
➡️ ✅ 만약 일치한다면 ptr이 가리키는 주소의 값을 새로운 값으로 변경
➡️ 🚫 불일치한다면 아무 것도 하지 않음.

위 방법은 Test-And-Set 방법과 동일한 방식으로 락을 만들 수 있음.

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

동작 또한 Test-And-Set과 유사하다.

• flag 변수가 0인지 검사하고 만약 그렇다면 자동적으로 1로 바꾸어 락을 획득

• 다른 쓰레드가 락을 보유하고 있다면, 획득할 때까지 while 문에서 회전

CompareAndSwap 명령어는 TestAndSet 명령어보다 더 강력
➡️ 대기없는 동기화(wait-free synchronization)를 다룰 때 진가가 나타남.

🔟 Load-Linked 그리고 Store-Conditional

어떤 플랫폼은 임계 영역 진입 제어 함수를 제작하기 위한 명령어 쌍을 제공

MIPS 구조에서는 load-linked와 store-conditional 명령어를 앞뒤로 사용하여 락이나 기타 병행 연산을 위한 자료 구조를 만들 수 있음.

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; // 갱신을 실패함
  }
}

load-linked: 일반 로드 명령어와 같이 메모리 값을 레지스터에 저장

store-conditional: 동일한 주소에 다른 스토어가 없었던 경우에만 저장을 성공
➡️ 저장이 성공하면, load-linked가 탑재했던 값을 갱신
➡️ ✅ 성공한 경우에는 ptr이 가리키는 value의 값을 갱신하고 1을 반환
➡️ 🚫 실패한 경우에는 갱신없이 0을 반환

다음은 load-linked와 store-conditional을 사용하여 락을 만드는 방법이다.

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

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

lock() 부분의 동작 순서는 다음과 같다.

1. 쓰레드가 while 문을 돌며 flag가 0(락의 해제)이 되기를 기다린다.

2. 락이 획득 가능한 상태가 되면 쓰레드는 store-conditional 명령어로 락 획득을 시도한다.

   1. ✅ 성공 하는 경우

      1. 쓰레드는 flag 값을 1로 변경하고 임계 영역 내로 진입한다.

   2. 🚫 실패 하는 경우

      1. 다시 락을 획득할 수 있을 때까지 기다린다.

⭐ 그럼 이렇게 store-conditional 명령어가 실패하는 경우를 살펴보자.

쓰레드가 lock()을 호출하여 load-linked를 통해 0을 반환 받은 후 store-conditional 명령어를 시도하기 전에 인터럽트에 걸린다고 생각해보자.

이때 다른 쓰레드가 store-conditional을 통해 락 획득에 성공한다면?
➡️store-conditional은 오직 하나의 쓰레드만 flag 값을 1로 설정 후 락을 획득할 수 있도록 하므로 인터럽트에 걸린 쓰레드는 다음 기회를 기다릴 수 밖에 없다.(즉, 실패) 😓

아래와 같이 lock()을 조금 더 간결하게 작성할 수 있다.

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

1️⃣1️⃣ Fetch-And-Add

Fetch-And-Add 명령어는 원자적으로 특정 주소의 예전 값을 반환하면서 값을 증가시킨다.

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

🎟️ 티켓 락
Mellor-Crummey와 Scott이 제안한 것으로, 하나의 변수 만을 사용하는 대신 티켓(ticket)과 차례(turn) 조합을 사용하여 락을 만든다.

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) {
  FetchAndAdd(&lock−>turn);
}

하나의 쓰레드가 락 획득을 원할 때, fetch-and-add(원자적으로 동작)를 실행한다.
➡️ 결과 값은 해당 쓰레드의 "차례"(myturn)을 나타낸다.
➡️ myturn == lock->turn(전역 공유 변수) 조건에 부합하면 임계 영역에 진입

unlock() 동작은 차례 변수의 값을 증가시켜서 대기 중인 다음 쓰레드가 존재한다면 임계 영역의 진입 차례를 넘겨준다.

💡 이전까지의 접근 방법과 다른 점은 모든 쓰레드들이 각자의 순서에 따라 진행한다는 것
➡️ 쓰레드가 티켓 값을 할당받았다면 미래의 어느 때에 실행되기 위해 스케줄되어 있다는 것

이전의 Test-And-Set의 경우 다른 쓰레드들은 락을 획득/해제하더라도 어떤 쓰레드는 계속 회전만하고 있을 수 있음.

1️⃣2️⃣ 요약: 과도한 스핀

지금까지의 하드웨어 기반 락 ➡️ 간단하고 제대로 동작하지만, 효율적이지 않은 경우도 있음.

N개의 쓰레드가 프로세서가 하나인 시스템에서 실행하는 경우

1. 한 쓰레드가 락을 보유한 상태에서 인터럽트에 걸림.

2. 다음 차례의 쓰레드는 락 획득을 시도 시 스핀 시작

3. 다른 N-1 개의 쓰레드들 또한 할당된 CPU 시간 동안 비슷한 이유로 낭비

4. 다시 락을 보유한 쓰레드 차례가 되면 락을 해제

하드웨어의 지원으로만은 이 문제를 해결할 수 없다.
➡️ 운영체제로부터의 지원이 추가로 필요

1️⃣3️⃣ 간단한 접근법: 무조건 양보!

첫 번째 시도 ➡️ 락이 해제되기를 기다리며 스핀해야 하는 경우 자신에게 할당된 CPU를 다른 쓰레드에게 양보

다음은 Test-And-Set에 양보를 이용한 락을 적용한 코드이다.
➡️ 운영체제에 자신이 할당받은 CPU 시간을 포기하고 다른 쓰레드가 실행될 수 있도록 하는 yield() 기법이 있다고 가정

void init() {
  flag = 0;
}

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

void unlock() {
  flag = 0;
}

하나의 쓰레드는 다음과 같은 상태를 가질 수 있다.

• 실행 중(running)

• 준비(ready)

• 막힘(blocked)

양보(yield) 시스템 콜은 호출 쓰레드 상태를 실행 중(running) 상태에서 준비(ready) 상태로 변환하여 다른 쓰레드가 실행 중 상태로 전이하도록 한다.
➡️ 양보 동작은 스케줄 대상에서 자신을 빼는 것(deschedule)이나 마찬가지

⚠️ 단일 CPU에서 100개 정도의 쓰레드들이 락 획득을 위해 경쟁하는 경우
나머지 99개의 쓰레드가 각자 lock()을 호출하고 CPU를 양보
➡️ round-robin 스케줄러 사용 시 99개의 쓰레드가 run-and-yield 패턴으로 동작
➡️ ✅ 99개의 시간 간격을 낭비하게 되는 회전 방식보다는 좀 더 좋음
➡️ 🚫 여전히 문맥 교환 비용이 상당하며 낭비가 많음.
➡️ 🚫 굶주림 문제(이 경우 무한한 양보)는 아직 고려하고 있지도 않음.

1️⃣4️⃣ 큐의 사용: 스핀 대신 잠자기

어떤 쓰레드가 다음으로 락을 획득할지를 명시적으로 제어할 수 있어야 함.
➡️ 운영체제제로부터 적절한 지원과 큐를 이용한 대기 쓰레드들의 관리가 필요

Solaris의 방식을 통해 이를 알아보자.

아래와 같은 두 개의 호출문이 있다.

• park(): 호출하는 쓰레드를 잠재우는 함수

• unpark(threadID): threadID로 명시된 특정 쓰레드를 깨우는 함수

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

다음 예시에서 두 가지를 시도해보자.

1. Test-And-Set 개념을 락 대기자 전용 큐와 함께 사용하여 좀 더 효율적인 락을 제작

2. 큐를 통해 다음 락 획득 대상을 제어하여 기아 현상을 피할 수 있도록 함.

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으로 설정되어 있지 않음.]

• 쓰레드가 깨어날 때는 마치 쓰레드가 park()에서 리턴하는 것과 같이 보임.

• 하지만 그 시점에서 guard 락을 획득한 상태가 아님.

  • flag 변수의 값을 1로 변경하는 것을 시도조차 할 수 없음.

• 락을 획득하려는 다음 쓰레드로 직접 전달

  • 그 사이에 flag는 0으로 바뀌지 않음.

[⚔️ park() 직전에 경쟁 조건이 발생]

• 한 쓰레드가 락이 사용 중인 이유로 park() 문을 수행하려는 상황

  • 만약 그 직전에 락 소유자한테 CPU가 할당되는 경우 ➡️ ⚠️ 문제 발생

  • 락을 보유한 쓰레드가 해당 락을 해제함.

  • 처음의 쓰레드가 park()를 수행하면 (잠재적으로) 깨어날 방법이 없음.

    ➡️ 깨우기/대기 경쟁(wakeup/waiting race)

• Solaris는 이 문제를 setpark() 시스템 콜을 추가하여 해결

  • 이 루틴은 park()를 호출하기 직전이라는 것을 표시

  • 이때 인터럽트가 수행되고 park() 호출 전 다른 쓰레드가 unpark()를 먼저 호출

    ➡️ park() 문은 sleep 하는 대신 바로 리턴

lock() 내에 다음과 같이 setpark()를 추가하여 깨우기/대기 경쟁 문제를 해결한다.

queue_add(m−>q, gettid());
setpark(); // 새로운 코드
m−>guard = 0;

guard 변수의 역할을 커널에서 담당하는 것도 하나의 방법
➡️ 커널은 락 해제와 실행 중인 쓰레드를 큐에서 제거하는 동작을 원자적으로 처리하기 위해 주의해야 함.

1️⃣5️⃣ 다른 운영체제, 다른 지원

Linux

futex라는 것을 지원

futex는 특정 물리 메모리 주소와 연결되어 있으며 futex마다 커널 내부의 큐를 갖고 있음.

호출자는 futex를 호출하여 필요에 따라 잠을 자거나 깨어날 수 있음.

futex에는 두 개의 명령어가 제공됨.

• futex_wait(address, expected)

  • address 값과 expected 값이 동일한 경우 쓰레드를 잠재움.

  • 같지 않은 경우 즉시 리턴함.

• futex_wake(address)

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

nptl 라이브러리의 lowlevellock.h(gnu libc 라이브러리의 일부)를 살펴보자.

• 하나의 정수를 이용하여 락의 사용 중 여부(최상위 비트), 대기자 수(나머지 비트)를 표현

  • 만약 락이 음수라면 락이 사용 중인 것을 나타냄.

• 경쟁이 없는 일반적인 경우에 대한 최적화 방법을 제시

  • 단 하나의 쓰레드가 락을 획득하고 해제하는 경우

    ➡️ 원자적으로 비트 단위의 TestAndSet로 락을 획득하고 원자적 덧셈을 하여 락을 해제

1️⃣6️⃣ 2단계 락

Linux의 기법에는 1960년 초에 있었던 Dahm 락을 시작으로 지금까지 간혹 사용되던 오래된 기법이 녹아있음.
➡️ 요즘은 2단계 락(two-phase lock)이라고 불림.

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

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

첫 번째 단계 ➡️ 곧 락을 획득할 수 있을 것이라는 기대로 회전하며 기다린다.

두 번째 단계 ➡️ 첫 번째 단계에서 락을 획득하지 못했다면 sleep 했다가 락이 해제된 후에 깨어난다.

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

💡 2단계 락은 두 개의 좋은 개념을 사용하여 개선된 하나를 만들어 내는 하이브리드 방식의 일종
➡️ 하드웨어 환경, 쓰레드의 개수, 세부 작업량 등에 의존성이 있으므로 항상 좋다고 보기는 어려움.

📚 참고 문헌

Operating Systems: Three Easy Pieces ― 28: Locks

운영체제 아주 쉬운 세 가지 이야기 ― 31: 락