[OSTEP-28] - 락s

개요

여러개의 명령어를 동시에 실행할때 단일 프로세스의 인터럽트 혹은 여러 프로세스에서의 병행성문제 때문에 원자적으로 실행할 수 없음, 오퍼레이팅 시스템에서는 lock 을 이용하여 해당 문제를 해결하려고함

락

balance 변수를 갱신하는 간단한 코드 예시

lock_t mutex;
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

위의 코드에서는 임계 영역에서 정확히 하나의 쓰레드가 락을 획득하고 반환할 수 있음

• lock() 루틴: 락 획득을 시도함 → 락을 획득하여 임계영역내로 진입하는 쓰레드를 락 소유자(owner)라고 부름
• unlock() 루틴: 락 소유자가 unlock() 을 호출하면 락은 다시 사용 가능한 상태가 됨

Pthread 락

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

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
Pthread_mutex_lock(&lock); // pthread_mutex_lock()
balance = balance + 1;
Pthread_mutex_unlock(&lock);

• POSIX 방식에서는 변수명을 지정하여 락과 언락 함수에 전달함. 다른 변수들을 보호하기 위해서 다른 락을 사용할 수 도 있기 때문에
  • coarse-grained: 하나의 락을 임의의 임계영역에 진입할때 마다 사용함
  • fine-grained: 서로다른 데이터와 자료구조를 보호하기 위해 여러 락을 사용하여 보호된 코드내에 각자가 진입할 수 있도록 함

락 구현

효율적인 락은 어떻게 만들어야하는가? 효율적인 락은 낮은 비용으로 상호 배제 기법을 제공하고 몇가지 속성들을 추가로 가져야한다. 어떤 소프트웨어의 지원이 필요할까, 어떤 하드웨어의 지원이 필요할까?

락의 평가

• 상호배제: 상호 배제를 제대로 지원하는가
• 공정성: 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가
• 성능: n개의 쓰레드가 K 자원을 놓고 경쟁할때 성능은 어떤가

초창기 알고리즘: 인터럽트 제어

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

void lock(){
  DisableInterrupt();
}
void unlock() {
  EnableInterrupt();
}

임계 영역에 진입하기 전 인터럽트를 막는다면 임계 영역 내의 코드에 대해서는 인터럽트가 발생할 수 있기 때문에 원자적으로 실행 될 수 있음

장점

• 단순함: 코드가 실행중에 다른 쓰레드가 중간에 끼어들지 않음

단점

• 인터럽트 활성/비활성화를 위한 특권권한을 가지고 있어야함
• 다른 목적으로 사용하지 않음을 신뢰할 수 있어야함
• 운영체제가 시스템의 제어권을 다시 얻을 수 없을 수도있음
• 멀티프로세서에 적용 못함
  • 특정 프로세서에서의 인터럽트 비활성화는 다른 프로세서에서 실행 중인 프로그램에는 전혀 영향을 주지 못함 → 결과적으로 임계 영역에 접근 가능함
• 인터럽트의 시점을 놓칠 수 있음 (ex. 저장 장치에서 읽기 요청을 마쳤을 경우)

여담: 데커와 피터슨의 알고리즘

1960대에 다익스트라가 병행성을 어떻게 잘 처리할지에 대한 고민을 친구에게 얘기 했고 데커가 해결방안을 제시함. Dekker 알고리즘은 운영체제와 하드웨어 명령어의 지원을 받아 사용하는 방법들과 달리 load와 store 명령어만을 사용함. (해당 명령어들이 원자적으로 동작하는것을 가정함) 이 알고리즘은 피터슨에 의해서 개선됨 임계 영역에 두개의 쓰레드가 절대로 동시에 들어가지 못하도록 보장함

아래는 피터슨 알고리즘을 C++ 로작성한 코드이다

int flag[2];
int turn;

void init() {
  flag[0] = flag[1] = 0; // 1 -> 쓰레드가 락을 획득하길 원함
  turn = 0; // 누구 차례인가? (쓰레드 0 혹은 1)
}
void lock() {
  flag[self] = 1; // self-> 호출한 쓰레드의 id
  turn = 1 - self; // 다른 쓰레드의 차례가 되도록 만듬
  while((flag[1-self] == 1) && (turn == 1 - self)) // 상대방이 락을 원하고 상대방차례인 동안 spin lock
  
}

void unlock() {
  flag[self] = 0; // 원래의 의도를 취소함
}

Test-And-Set (Atmoic Exchange)

멀티프로세서에서는 인터럽트를 중지시키는것이 의미가 없기 대문에 락 지원을 위한 하드웨어를 설계하기 시작함 하드웨어 기법 중 가장 기본은 Test-And-Set 명령어 또는 원자적 교체라고 불리는 기법

typedef struct __lock_t {int flag;} lock_t;
void init(lock_t *mutex) {
  mutex->flag = 0;
}

void lock(lock_t *mutex) {
  while (mutex->flag ==1);
  mutex-flag = 1;
}

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

단점

• 적시에 인터럽트가 발생하면 두 쓰레드 모두 플래그를 1로 설정하는 경우가 생길 수 있고, 임계영역에 두 쓰레드 모두가 진입할수도 있음.
• 사용중인 락을 대기하는 방법에 spin-wait 방식을 사용하여 플래그의 값을 무한히 검사하는데. 이 방법은 다른 쓰레드가 락을 해제할때까지 시간을 낭비함, 단일 프로세스에서 손해가 겁나큼

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

int TestAndSet(int *old_ptr, int new) {
  int old = *old_ptr; // 이전 값 검사
  *old_ptr = new; // 이전값을 현재 값으로 변경
  return old;
}

typedef struct __lock_t {
  int flag;
  
} lock_t;

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

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

• 단일 프로세서에서 위 방식을 제대로 사용하려면 선점형 스케줄러를 사용해야함, 선점형 스케줄러는 필요에 따라 다른 쓰레드가 실행될 수 있도록 타이머를 통해 쓰레드에 인터럽트를 발생시킬 수 있음. 선점형이 아니면, 단일 CPU 에서 스핀 락의 사용은 불가능함

Compare-And-Swap

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

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

과도한 스핀

두 개의 쓰레드를 프로세서가 하나인 시스템에서 실행한다고 해 보자. 쓰레드 0이 임계영역 내에 있어서 락을 보유한 상태에서 인터럽트에 걸렷다고 해보자. t2 가 락을 획득하려고하는데 이미 락을 갖고 있어서 진입하지 못한다, 이때 타이머 인터럽트로 인해 t1으로 넘어간다. 락을 반환하고, t2 가 사용할 수 있게된다

위와 같은 상황에서 N 개의 쓰레드가 하나의 락을 획득하기 위해 경쟁하게 되면 상황은 더욱 심각해진다. N-1개의 쓰레드에 할당된 CPU 시간 동안, 비슷한 이유로 낭비하게 된다.

어떻게 하면 스핀에 CPU 시간을 낭비하지 않는 락을 만들 수 있나?

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

간단한 접근법: 무조건 양보!

하드웨어의 지원을 받아 동작이 검증된 락과, 락 획득의 공정성까지도 해결할 수 있었다. 하지만 문맥교환으로 인해 쓰레드가 락을 해제하기를 기다리며 스핀만 무한히 하는 경우에는 어떻게 해야하나..?

스핀해야하는 경우 자신에게 할당한 cpu 를 무조건 양보!

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

이 방법은 CPU 시간을 포기하고 다른 쓰레드가 실행될 수 있도록 하는 yield() 기법이 존재한다고 가정한다. 하지만 이 방법은 쓰레드가 100개 있을때 무한히 양보만 하고 있는 쓰레드가 존재할 수도 있어서 좋지않은 방법이다.

큐의 사용: 스핀 대신 sleep zzz…

이전 방법은 너무 운에 의존했다. 이를 해결하기 위해서는 어떤 쓰레드가 다음 락을 제어할지 명시적으로 제어할 수 있어야한다.

이를 위해서는 운영체제가 큐를 이용한 대기 쓰레드들의 관리를 해야한다.

• park(): 호출하는 쓰레드를 잠재움
• unpark(threadID) : threadID 깨워버림 → 락 점유 가능하도록

typedef struct __lock_t {
  int flag; // 실제 자원
  int guard; // 큐의 삽입과 삭제 flag 동작을 스핀락으로 보호 
  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) {
  while (TestAndSet(&m->guard, 1) == 1);
  if(queue_empty(m->q)) m->flag =0;
  else unpark(queue_remove(m->q)); // (다음 쓰레드 깨워버림)
  m->guard=0;
}