[병행성 #2] 락(Lock)

락(Lock)이란 무엇인가?

락은 하나의 변수다. 사용 가능(available) 또는 사용 중(acquired)을 나타냄.

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

• 사용 가능: 어느 스레드도 락을 보유하지 않은 상태
• 사용 중: 단 하나의 스레드가 임계 영역에 들어가기 위해 락을 보유한 상태
• lock()/unlock()의 동작
  1. lock() 호출
     • 락이 비어 있으면 즉시 획득 → 해당 스레드는 임계 영역 진입 (진입 한 쓰레드를 락 owner라고 부름)
     • 이미 사용 중이면 임계 영역 안으로 진입하지 않고 대기(블록 혹은 스핀)
  2. unlock() 호출
     • 락을 해제 → 대기 중인 쓰레드가 있으면 그 중 하나가 락 획득
• 프로그래머에 대한 이점
  • 쓰레드 스케줄링의 최소한 제어권을 프로그래머에게 일부 위임
  • 코드 블록 단위로 단일 쓰레드 실행을 보장
  • 멀티스레드 간 혼란스러운 실행 순서에 질서를 부여

---

POSIX 뮤텍스(mutex)

쓰레드 간에 mutual exclusion 기능을 제공하기 위해 POSIX 라이브러리는 락을 뮤텍스(mutex) 라고 부른다.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);
balance = balance + 1;
pthread_mutex_unlock(&lock);

• 거친 락 전략(coarse-grained locking)
  • 하나의 뮤텍스로 전체 영역을 보호 → 단순하지만 성능 저하 가능
• 세밀한 락 전략(fine-grained locking)
  • 여러 데이터 구조별로 뮤텍스를 분리하여 병렬성을 높임

---

락 구현

락을 실제로 구현하려면 하드웨어와 운영체제 도움이 필요

평가 방법

1. 상호 베제
2. 임계 영역 내로 다수의 쓰레드가 진입을 막을 수 있는가?
3. 공정성
4. 쓰레드 들이 락 획득에 공정한 기회가 주어지는가?
5. 성능
6. 락을 획득하고 헤제하는 과정에서 발생하는 부하는?

인터럽트 비활성화 방식 (단일 CPU)

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

• 임계 영역 내에서는 인터럽트를 비활성화하는 방법을 사용하여 원자성 보장
• 장점:
  1. 단순함 ㅋㅋ
• 단점:
  1. 특권 연산 허가 필요 → 잘 알지 못하는 다른 프로그램에게도 줘서 악의적인 프로그램 발생 가능
  2. 멀티프로세서에 무의미 → 쓰레드가 여러 CPU에서 실행 중이라면 각 쓰레드가 동일한 임계 영역을 진입하려는 경우 특정 프로세서의 인터럽트 비활성화는 다른 프로세서에서 실행중인 프로그램에 영향을 주지 않음.
  3. 중요한 인터럽트를 놓칠 위험
  4. 장시간 동안 인터럽트를 중지시키는 것은 시스템에 심각한 문제를 가져올 수 있다.
  5. 현대 CPU에서 비효율적
  6. 비효율 적이다.

---

플래그 변수로 스핀 락 구현하기

가장 기초적인 형태의 락으로서 락을 획득할 때까지 CPU 사이클을 소모하면서 회전 한다

typedef struct { int flag; } lock_t;

void init(lock_t *m) {
  m->flag = 0;  // 0: free, 1: locked
}
void lock(lock_t *m) {
  while (m->flag == 1)  /* spin */ ;
  m->flag = 1;
}
void unlock(lock_t *m) {
  m->flag = 0;
}

• 간단한 변수인 플래그의 값을 가지고 플래그의 값을 무한히 검사한다.
• flag = 1 이면 락 보유중인 것
• 문제점
  • 두 스레드가 거의 동시에 flag=1 설정 → 상호 배제 실패(두개의 쓰레드가 다 진입)
  • 단일 CPU에서 spin 비용이 큼 → 문맥 교환 전까지는 spin함

TestAndSet 기반 스핀락

int TestAndSet(int *ptr, int new) {
  int old = *ptr;
  *ptr = new;
  return old;
}

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

• 락 보유 검사 하고 획득 하는 TestAndSet 동작을 원자적 연산으로 만듦
• 문제점
  • 공정성 : 스핀 락은 대기 중인 쓰레드가 계속 굶주릴 수 있음.
  • 성능 : 단일 CPU의 경우 CPU 사이클을 낭비하면서 락을 획득하기 위해 대기한다. 멀티 CPU 인 경우 ( 쓰레드 개수와 CPU의 개수가 대충 같다면) 스핀 락은 꽤 합리적으로 동작.

Compare-And-Swap (CAS)

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

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

• ptr이 가르키고 있는 주소의 값이 expected 변수와 일치하는 지 검사
• Test-And-Set 와 비슷하지만 강력함
• 대기없는 동기화(wait-free synchronization) 일때 엄청난 능력

Load-Linked / Store-Conditional (LL/SC)

int LoadLinked(int *ptr) {
  return *ptr;
}
int StoreConditional(int *ptr, int val) {
  if (ptr에 다른 store가 없었던 경우에만) {
    *ptr = val;
    return 1;
  } else {
    return 0;
  }
}

void lock(lock_t *m) {
  while (1) {
    while (LoadLinked(&m->flag) == 1) ;   // spin until free
    if (StoreConditional(&m->flag, 1))
      return;  // 성공
  }
}

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

• 장점: 충돌 감지 후 재시도 → 불필요한 spin 최소화

Fetch-And-Add (Ticket Lock)

typedef struct {
  int ticket;
  int turn;
} lock_t;

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

void init(lock_t *m) {
  m->ticket = m->turn = 0;
}

void lock(lock_t *m) {
  int myturn = FetchAndAdd(&m->ticket);
  while (m->turn != myturn) /* spin */ ;
}
void unlock(lock_t *m) {
  FetchAndAdd(&m->turn);
}

• 각 스레드는 ticket = FetchAndAdd(&ticket)로 순번 확보
• turn 값과 비교하여 자신의 차례일 때만 임계 영역 진입
• 언락 동작은 차례 변수의 값을 증가시켜서 대기 중인 다음 쓰레드에게 임계 영역 진입 차례를 넘겨준다
• 공정성(Fairness)과 순서가 보장

과도한 스핀

락은 간단하고 제대로 동작한 것이 큰 장점. 하지먄 효율적일까 ?

운이 좋지 않게도 임계영역 내에서 락을 보유한 상태에서 인터럽트에 걸려있다면 .. 타이머 인터럽트에 의해서 다시 락이 걸려있는 스레드로 돌아와야지만 해야하는 시간 낭비가 발생한다..

어떻게 해결할 수 있을까 ?

• 양보 방식
  • 운영체제에 자신이 할당받은 CPU 시간을 포기하고 다른 쓰레드가 실행될 수 있도록 하는 yield() 기법으로 해결가능
  • But 만약 대기중인 쓰레드가 많다면 ? 양보또한 99개의 낭비가 발생하게 됨.
  • 어떤 쓰레드는 무한히 양보만 하고있는 경우가 생길수도 있음.

  void init() {
  	flag = 0;
  }
  
  void lock() {
  	while (TestAndSet(&flag, 1) == 1)
  		yield();
  }
  
  void unlock() {
  	flag = 0;
  }
  

• 큐를 사용한 스핀 대신 잠자기
  • 스케줄러 선택에 ‘운’에 의존 → 기아(starvation) 발생 가능
  • 어느 쓰레드가 다음에 락을 얻을지 제어 불가
  명시적인 대기 쓰레드 관리 필요
  • 큐를 사용하여 다음으로 락을 획득할 대상을 제어
  Solaris의 park/unpark 기능 (운영체제의 지원)
  • 호출 쓰레드를 재우고, 깨우는 방법
  • 자신의 락을 획득할 수 없다면, gettid()를 호출하여 현재 실행 중인 쓰레드 ID를 얻고, 락 소유자의 큐에 자기 자신을 추가하고, CPU를 양보.

  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); // spin하면서 guard 락을 획득
    if (m >flag == 0) {
      m >flag = 1; // 락 획득함
      m >guard = 0;
  	} else { 
       queue_add(m >q, gettid());
       setpark(); //
       m >guard = 0;
       park();
  	}
  }
  
  void unlock(lock_t *m) {
  	while (TestAndSet(&m >guard, 1) == 1); // spin 하면서 guard 락을 획득
  	if (queue_empty(m >q))
  		m >flag = 0; // 락을 포기함
  	else
  		unpark(queue_remove(m >q)); // 락을 획득함
  	m >guard = 0;
  }
  

  깨우기/대기 경쟁(wakeup/waiting race) 발생 가능성 있음 → park() 문을 수행하기 전에 인터럽트가 발생하여 다른 쓰레드가 락을 해제할 가능성 존재.
  setpark(); 를 통해 park() 호출 직전이라는 것을 표시하여 park()가 실제로 호출 되기 전에 다른쓰레드가 unpark()를 먼저 호출하면 바로 리턴
• 2단계 락 (two-phase lock)
  • 스핀 락과 sleep 락의 장점을 결합해 ‘짧게 스핀 → 잠자기’ 흐름을 구현
  • one-phase 에서는 회전하며 기대
  • 만약 첫 회전 단계에서 락을 획득하지 못하면 two-phase
  • two-phase 에서는 호출자는 잠에 빠지고 락이 해제된 후에 깨어나도록

 

출처: 운영체제: 아주 쉬운 세 가지 이야기