[OS] 28장: Locks

28장: Locks

27장 복습: Lock API 함수

전역변수로 선언

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t init = PTHREAD_COND_INITIALIZER;

임계 영역에 상호 배제 기능 제공

• pthread_mutex_lock = 임계영역 lock 요청, lock을 할 수 없다면 대기
• pthread_mutex_trylock = lock 요청, lock 못 얻으면 대기X 리턴
• pthread_mutex_unlock = lock 해제, 대기중인 스레드는 lock 얻음

Lock 사용 법

1. Lock 변수 선언 및 초기화

   pthread_mutex_init(뮤텍스 객체, 속성) - 성공하면 0 반환

2. 임계영역 시작에서 Lock, 끝나면 Unlock

3. lock 사용 다 끝나면, 삭제

27장: Condition Variables (조건 변수)

쓰레드 간 특정 신호를 주고 받을 때 사용

• pthread_cond_init

  프로듀서-컨슈머 문제에서 임계영역 안에서 Queue가 비어있다고,

  단순 wait()를 박으면, 다른 프로세스가 진입할 수도 있음

  이 때, phtread_cond_wait를 사용함

• pthread_cond_signal = 대기하는 스레드를 깨워줌

• pthread_cond_broadcast = 대기하는 모든 스레드를 깨움

사용 방법

// A 스레드
pthread_mutex_lock(&lock);
while(ready == 0) // 레디 큐
        pthread_cond_wait(&init, &lock);
pthread_mutex_unlock(&lock);

임계 영역에 들어왔는데 레디 큐가 비어있는 경우 사용

스레드를 Sleep 상태로 보내고 lock을 해제함

// B 스레드
pthread_mutex_lock(&lock);
ready = 1;
pthread_cond_signal(&init); // init을 기다리는 스레드 하나 깨움
pthread_mutex_unlock(&lock);

만약 조건변수를 쓰지 않으면, spin lock이 걸려서 CPU 시간 낭비됨

단일 프로세스의 경우 다른 스레드가 작업 X

while(ready == 0) ;

Lock 개요

Lock 변수

• Lock의 상태를 저장함
• 사용 가능: 락 소유자 없는 상태
• 사용 중: 정확히 하나의 스레드가 락을 획득하여 임계영역에 진입한 상태

Granularity (사용범위)

• Coarse-grained

  적은 수의 락으로 넓은 범위 처리

• Fine-grained

  많은 수의 락으로 작은 임계영역 처리

Lock/Unlock 함수는 어떻게 만들까 ?

• 어떤 하드웨어 지원이 필요한가 ?
• 어떤 운영체제 지원이 필요한가 ?
• 만들어진 락은 무엇을 기준으로 평가할까 ?

락의 평가 기준

1. Mutual Exclusion (상호배제)
   • 한 번에 하나의 스레드만 임계 영역에 진입할 것이 보장되는지
2. Fairness (공정성)
   • 각 스레드가 락 획득을 위한 공정한 기회를 얻는지,
   • 기아 상태 스레드가 없는지
3. Performance (성능)
   • 락을 사용하는데 드는 시간적 오버헤드를 최소화할 수 있는가

CISC 아키텍처

• Lock 구현 (1): 인터럽트 제어

  lock을 얻으면 인터럽트 기능 꺼버림

  문제점

  • 락 획득을 원하는 스레드에 특권 명령 허용
    악의적으로 무한점거 해버릴 수 있음
  • 멀티 프로세서에 적용 불가

• Lock 구현 (2): SW 제어

### 장점

- SW만으로 가능

### 단점

- 이해하기 어려움
- 비효율적

Lock 구현 (3): TestAndSet (하드웨어 도입)

SW의 문제점

→ No Mutual Exclusion, Test와 Set이 분리되었기 때문

flag = 1로 설정 못 했는데 인터럽트 당하면 답이 없음

= Test와 Set이 분리되었기 때문

SW만으로 하지 않고, 하드웨어 활용

HW Atomic Operation을 추가하여 lock 구현

Test와 Set을 분리하지 않고 실행

!

int TestAndSet(int* old_ptr, int new) {
        int old = *old_ptr;
        *old_ptr = new; // set
        return old; // test
}

이러면 중간에 인터럽트 당하지 않고, 테스트와 셋 동시 설정 가능

= 원자적으로 수행

typedef struct __lock_t {
        int flag;
} lock_t;

void init(lock_t* lock) {
        lock->flag = 0; // 0은 사용가능, 1은 사용중
}

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

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

TestAndSet 함수에서 flag는 1로 세팅되고, 0을 리턴함

다른 프로세스가 들어오면 0으로 세팅, 1이 리턴 == true = busy waiting

TestAndSet 평가

1. Mutual Exclusion = Yes
   flag 0 값을 가지고 1로 변경하는 것은 하나의 스레드만 가능
2. Fairness = No
   누가 먼저 진입할지, 차례대로 기회 받을 수 있는지 모름
3. Performance = ?
   Single CPU: CPU 시간 낭비
   Multiple CPUs: 꽤 좋음

Lock 구현 (4): CompareAndSwap

ptr이 가리키고 있는 주소값이 expected 변수와 일치하는가 ?

• 일치하면 ptr이 가리키는 주소 값을 새 값으로 변경
• 불일치하면 아무것도 안함

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

        return actual;
}

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

만약 현재 lock→flag가 1이라면,

두 번째 인자 0과 비교해서 다르면 flag를 바꾸지 않음

RISC 아키텍처

Lock 구현 (5): Load-Linked And Store-Conditional

• Load-Linked = 메모리 적재

  현재 lock→flag 불러옴

• Store-Conditinal

  Load-Linked 해서 flag가 0인걸 확인했어도, 그 사이에 flag가 바꼈을 수도 있음

  if 문으로 한 번 더 검사하고, flag 값 바꿔줌

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

int StoreConditional(int* ptr, int value) {
        if (LoadLinked 명령 후, *ptr이 변경되지 않은 경우) {
                *ptr = value;
                return 1;
        } else {
                return 0;
        }
}

void lock(lock_t* lock) {
        while(1) {
                while(LoadLinked(&lock->flag) == 1) ;

                if (StoreConditional(&lock->flag, 1) == 1)
                        return;
        }
}

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

==

while(LoadLinked(&lock->flag) || !StoreConditional(&lock->flag, 1))

Lock 구현 (6): 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) {
        int myturn = FetchAndAdd(&lock->ticket);
        while(lock->turn != myturn) ;
}

void unlock(lock_t* lock) {
        FetchAndAdd(&lock->turn);
}

공정성 만족

Too Much Spining

Spin lock = Busy Waiting

⇒ 변하지 않을 값을 기다리며 CPU 소모

임계 영역이 길 때 문제 발생

해결 방법

1. 무조건 양보
2. 큐의 사용: Sleep Lock
3. OS마다의 해결책
4. 2단계 락

1. 무조건 양보

void init() {
        flag = 0;
}

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

void unlock() {
        flag = 0;
}

Spin 해야할 때 무조건 양보

yield = 레디큐 맨 끝

• 문맥 교환 비용이 과도해질 수 있음
  스레드가 100개 이상이면, 계속 Context Switch
• 특정 스레드의 기아를 막을 수 없음
  → 공정성이 무너짐

2. 큐사용: Sleep Lock

Sleep에 들어가면 대기 큐로 가게 함
락 사용이 가능할 때, 대기중인 스레드를 깨움

필요한 시스템 API

• park()
  • 스스로 대기 상태로 전이
• unpark(threadID)
  • threadID로 지정된 스레드를 깨움

TestAndSet으로 Sleep Lock 구현

• lock 자료구조 초기화

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

• lock & unlcok 사용

1. 처음에 flag와 guard가 0으로 세팅되어 있음
2. A 스레드가 lock 진입
   TestAndSet에서 Guard 검사로 1로 바뀜 + 스핀락 안 걸림
   if (m→flag == 0)에 의해 flag를 1로 설정하고 guard를 0으로 세팅함
3. 이제 B 스레드가 Lock에 진입
   while문에 안 걸림 = 스핀락 발생 X,
   만약 A가 guard=0 안 했으면 스핀락 ㅇㅇ

A가 flag를 1로 해둬서 else문으로 들어가서 본인을 queue에 넣음
guard=0으로 세팅함
이제 park()을 해야 하는데, 이때 A가 unlock 과정에서 Unpark() 해버림
4. A가 unlock 과정에서 Queue가 비어있지 않으니까
else 문으로 들어가서 unpark()을 수행해버림
5. B 스레드가 park()을 하면 더이상 unpark() 해줄 수 있는 애가 없게 됨

void lock(lock_t* m) {
        while(TestAndSet(&m->guard, 1) == 1) ;

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

        if (queue_empty(m->q))
                m->flag = 0; // Lock 대기자 없을 때만 flag 해제
        else
                unpark(queue_remove(m->q));
                // flag 해제 X, 다음 스레드를 깨움
        m->guard = 0;
}

Wake Up/Waiting Race 문제점

1. A 스레드: park() 직전에 인터럽트 당함
2. B 스레드: 락 사용 종료 → 큐에 대기자가 없으므로 락을 해제함
3. A 스레드: 남은 park() 마저 수행 → 영원히 못 깨어남

해결

setpark() 사용
: 다른 스레드가 미리 unpark() 하면 park()은 수행 X

queue_add(m->q, gettid());
setpark(); // park()을 호출할 예정이라고 표시함
m->guard = 0; // 선취점 발생
park();

setpark()을 했는데, 다른 스레드가 인터럽트 했음

그러고 그 스레드가 lock 작업 마치고 Unpark()을 했다면,

다시 돌아온 기존 스레드는 park()을 수행하지 않음