운영체제

28 락

프로그래머들은 critical section을 락으로 둘러, 영역이 원자 단위 명령어인 것처럼 실행한다

---

락이 필요한 이유

• 코드 실행은 인터럽트 및 스케줄링에 따라 서로 인터리브된다
• 공유된 자원의 결과는 not deterministic하다

=> 공유 자원 접근에서 인터럽트, 쓰레드의 자원 접근 실행 순서 꼬임 등으로 인해 결과가 다를 수 있따

락: 기본 개념

• 락은 일종의 변수다
  • 락의 상태를 나타낸다
    • 사용가능 상태(unlocked or free)
      • 어떤 스레드도 락을 소유하고 있지 않다
    • 사용 중 상태(locked or held)
      • 임계영역에서 하나의 쓰레드가 락을 획득한 상태
        • 그래서 임계영역에 접근을 위해 대기가 필요하다

락의 의미

lock()

• 호출을 통해 락 획득을 시도한다
• 어떤 스레드도 락을 갖고 있지 않으면 호출을 한 스레드는 락을 획득한다
  • 임계영역으로 진입한다
  • 락의 owner가 된다 -락을 소유한 스레드가 임계영역에 존재하면 다른 스레드는 진입 불가하다

unlock()

• 락 owner가 호출하면 락은 다시 사용 가능한 상태가 된다
• 이전에 lock()을 호출해 대기 중인 스레드가 있다면 락의 상태가 바뀌어 owner가 바뀌고 임계영역으로 진입한다

락은 스케줄링에 대한 제어권을 제공한다
락으로 코드를 감싸 그 코드 내에서는 하나의 쓰레드만 동작하도록 보장할 수 있다
어느 정도 질서를 부여한다

pthread lock - mutex

• POSIX에서는 lock을 mutex라고 부른다

  • 상호배제(mutual exclusion)을 제공하기 때문이다

• 다른 변수들을 보호하기 위해 다른 락들을 사용할 수 있다

  • fine grained 접근법이다, 병행성을 키운다
    • fine grained
      • 다수의 쓰레드가 서로다른 락으로 보호된 코드를 실행
    • coarse grained
      • 하나의 락으로 모든 임계 영역을 보호

락 구현

효율적인 락은 mutual exclusion을 낮은 비용으로 제공한다
락을 구현하기 위해선 하드웨어와 OS가 도와준다

락 평가

락의 정상 동작 여부 평가를 위해 평가기준을 둬야한다

mutual exclusion

• 락이 동작하여 다수의 스레드가 임계영역에 접근하는 것을 막을 수 있는가
• 대부분 하나의 프로세스가 임계영역에 한번에 들어간다

Fairness

• 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가?(starvation)

  • 모든 프로세스는 임계영역에 합리적인 시간에 들어가야한다
  • 임계영역에 대한 요청은 모두 제공된다
  • 어떠한 스레드도 starvation 상태가 되면 안된다

Performance

• 락을 사용할때 시간 오버헤드가 추가된다
  • 오직 하나의 스레드가 락을 획득하고 해제하는 과정
  • 다중 CPU 상황에서 락 경쟁 시의 성능
    • 다른 스레드가 대기할 때 일어나는 성능 저하를 최소화 해야함

인터럽트 제어

임계영역에서 인터럽트 비활성화

• 초창기 시스템에서 mutual exclusion을 위한 해결 방법이다
• 싱글 프로세서 시스템에서 발견했다
  • 락을 하면 인터럽트 못하게 함!
• 장점
  • 단순하다
• 단점
  1. 프로그램에 너무 많은 신뢰를 주어야한다
     • 인터럽트를 on/off하려면 권한이 있어야한다
     • Greedy(or 불법)프로그램이 프로세서를 독점할 수 있다
       • 프로그램 시작과 동시에 LOCK을 호출해 독점해버릴 경우
  2. 멀티프로세서에선 지원이 안된다
     • 스레드가 다른 프로세서에서 실행중이라면 영향이 없다
       • 그래서 임계영역에 진입이 가능하다
  3. 장시간 인터럽트를 중지시키면 CPU를 느리게 만든다
     • 예를 들어 cpu가 저장장치에서 읽기 요청을 마친 사실을 모르고 지나간다면?
       • OS가 읽기 결과를 기다리는 프로세스를 깨울 방법이 없다

스핀락: 하드웨어 지원이 필요한 이유

인터럽트 활성/비활성화를 사용하지 않고 락을 구현하기 위해선 하드웨어의 도움이 필요하다
소프트웨어만 사용하면 구현할 수 없다
아래로 살펴보자

1. 첫번째 시도: 단일 플래그를 사용해 락이 되었는지 안되었는지 확인

작동 방식

flag 변수를 이용해 쓰레드가 락을 획득했는지 검사

임계영역에 진입하는 스레드가 lock을 호출해 플래그가 1인지 검사하고
1이 아니면 플래그를 1로 설정 후 해당 스레드가 락을 보유한다고 표시

임계영역에서 나오면 쓰레드가 unlock을 호출해 플래그 값을 초기화해 락을 보유하지 않는다 알림

만약 누가 임계영역을 사용 중 이라면 쓰레드는 spin wait을 하며 기다림

문제점

1. Correctness 제대로 작동해?

   • mutual exclusion을 주지 않는다
     • 여러 쓰레드가 임계영역에 접근할 수 있다

2. Performance

   • spin wait을 할때 플래그의 값을 무한히 검사한다
     • 시간을 낭비한다
     • busy waiting, busy looping, spinning

atomic한 인스트럭션을 위해 하드웨어의 지원이 필요하다

Test and set 원자적 변경

• 인스트럭션은 간단한 lock을 지원하도록 만들어 진다
  • 몇몇 시스템은 락 지원을 위한 하드웨어를 설계 시작

하드웨어 기법 중 기본은 test and set, atomic exchange로 알려진 명령어이다

Test-and-Set operation

int TestAndSet(int* ptr, int new){
    int old = *ptr; // 이전의 포인터 값을 가져옴
    *ptr = new;     // 새로운 값 저장
    return old;     // old 값 반환
}

ptr이 가리키던 예전 값을 반환하고 동시에 new에 새 값을 저장한다
원자적으로 실행이 된다

• Test(load)와 Set(store)를 하나의 원자적 operation으로 만든다

  • test: 이전 값을 확인
  • set: 새 값을 lock

• old 값을 반환한다

• 즉시 new 값을 갱신한다

• 순서는 원자적으로 실행된다

이를 활용해 spin lock을 만들 수 있다

한 쓰레드가 락 오너로써 임계영역을 사용하고 있을 때
다른 쓰레드가 락을 획득하려고 하면
flag가 1이므로 계속 spin을 돌 것이다
만약 원래의 owner가 lock을 반환을 한다면 flag가 0으로 설정됨과 동시에
test and set 함수에서 flag값을 1로 바꾼디 해당 쓰레드가 락 owner가 된다

• 스핀락은 락을 획득할때 까지 CPU를 소모하며 회전한다
  • 그렇기 때문에 단일프로세서에서 이 방법을 쓰려면 프로세스가 독점되면 되지 않는다
    • Preemptive scheduler를 사용해야한다
      • while을 도는 쓰레드가 CPU를 독점해 컴퓨터가 죽는다

스핀락 평가

Correctness

• mutual exclusion을 보장한다
• 하나의 쓰레드만 임계영역에 접근할 수 있다

Fairness

• 공정성을 보장해줄 수 없다
• spin을 하는 스레드는 락을 보장받을 수 없다
  • 계속 스핀할 수도 있다

Performance

• 단일 CPU에서 성능 열하는 매우 심각
  • spin 쓰레드는 CPU를 할당받은 시간에 spin만 하며 낭비
• CPU가 여러개(cpu개수와 쓰레드 개수가 대충 같을)일 경우 spin lock은 합리적으로 동작
  • 한 프로세서에서 동작중이고 다른 프로세서에서 spin을 하며 대기하니 많은 사이클을 낭비하지 않는다

Compare And Swap (Exchange)

int CompareAndSwap(int* ptr, int expected, int new){
    int actual = *ptr;  // ptr에 예전 값을 업데이트
    if(actual == expected)
        *ptr = new;     // 메모리 위치 업데이트
    return actual;      // 반환
}

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

• 주소의 값이 expected 변수와 일치하는지 검사한다

  • 일치한다면 ptr이 가리키는 주소의 값을 새 값으로 업데이트 한다
  • 다르다면 원래의 메모리 값을 반환한다

• spin에서 flag가 0인지 검사하고 그렇다면 자동으로 1로바꾼다

Load-linked 그리고 Store-Conditional

• store-conditional는 동일한 주소에 다른 store가 없었을 경우에만 저장을 성공한다
  • succuess: 1을 반환하고 ptr의 값을 갱신
  • fail: ptr이 가리키는 value가 갱신되지 않고 0을 반환

void lock(lock* lock){
    while(LoadLinked(&lock->flag || !StoreConditional(&lock->flag,1)));
}

• 쓰레드는 while을 돌며 flag가 0이 되기를 기다림(락이 해제)

 락을 획득할 수 있는 상태가 되면 쓰레드는 store-conditional로 락 획득을 시도, 성공한다면 스레드는 flag를 1로 변경 후 임계 영역으로 진입

• 실패할 수도 있음

 락이 사용가능하니 0을 반환했을 것
 storeconditional로 flag를 1로 변경하려는 순간 인터럽트에 걸려
 다른 쓰레드가 락을 차지
 그럼 인터럽트 걸린 쓰레드는 락 획득을 못함!
 왜? store 조건문에서 주소 값이 업데이트 안되었을 때만 flag를 1로 변경하니
 이미 변경되었기 때문에 락을 못 얻는다

Fetch-And-Add

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

• 원자적으로 특정주소의 이전 값을 반환하며 값을 증가시킨다
• fetch and add를 사용해 티켓 락을 만들어 보자
  • fairness 문제를 해결할 수 있다

Ticket Lock

• 스레드들에게 순서를 보장해 공정성을 보장한다
• 티켓과 turn 조합을 사용해 락을 만든다

방법

락을 하면 티켓값을 늘린다
언락을 하면 턴 값을 늘린다

티켓과 턴 값이 같아야 lock을 사용할 수 있다
같지 않으면 spin한다

쓰레드가 티켓 값을 할당 받으면 미래에 무조건 락을 사용할 수 있게 스케줄이 된다

• 이전 방법은 어떠한 쓰레드가 계속 spin할 수 있지만 ticket lock은 순서를 보장한다

Ticket lock 시나리오

티켓 0 turn 0

1. 스레드가 티켓 뽑음 티켓 0 발급 (다음 티켓 값 1로 증가)
2. 스레드의 티켓과 턴 값 비교
   • 같을 경우
     • 락 소유
   • 다를 경우
     • 같을 때 까지 spin
     • 같아지면 락 소유

• 스레드에게 순서를 보장한다
  • lock->turn은 어떤 스레드의 턴인지 결정한다
  • 쓰레드가 티켓 값을 할당 받으면 미래에 무조건 락을 사용할 수 있게 스케줄이 된다

Ticket lock 평가

multual exclusion (corecteness)

• 좋음
• 한번에 하나의 스레드만 사용가능하다

Fairness

• 좋음
• 대기하는 스레드들에게 나중에 사용할 수 있게 보장해줌

Performance

• SPNNING을 하며 cpu 사이클 낭비

과도한 스핀

하드웨어 기반 스핀 락은 간단하고 제대로 동작한다
그러나 효율적이지 않을 경우도 있다

• 스레드가 스핀할때 값을 확인하느라 전체 타임 슬라이스를 잡아먹는다

어떻게 spinnnig을 피할까?

OS의 도움이 필요

간단한 접근: 조건없는 양보 just yield

락이 해제되기를 기다리며 스핀을 할 때 자신에게 할당된 CPU를 다른 쓰레드에 양보한다

• yield() 시스템 콜은 스레드 상태를 running에서 ready로 전환한다

• context switch를 할 때 비용이 상당하다

• starvation 문제가 일어날 수도 있다

큐의 사용: 스핀 대신 sleeping

어떤 쓰레드가 락에 들어가려고 하는지 추적하는 큐

• park() 시스템 콜은 쓰레드를 잠재운다
• unpark(threadID)는 명시된 쓰레드를 깨운다
  => 사용하는 락을 요청하는 쓰레드를 재우고 락이 해제되면 깨울 수 있다

Wakeup/Wating Race

• 쓰레드가 park()를 호출하기 직전 락을 소유한 쓰레드가 락을 해제하는 경우
  • 쓰레드를 깨워줄 쓰레드가 없다
    • Wakeup/Waiting Race

2단계 락

두 단계의 락은 락이 곧 해제될 것 같으면 회전 대기가 더 유용하다는 것을 인식

• 1단계
  • 락은 회전하며 대기, 락이 빠른 시간내에 해제될 것을 가정
  • 만약 첫단계에서 락을 얻지 못한다면, 2단계로 진입
• 2단계
  • 락을 호출한 스레드는 sleep한다
  • 락 해제시 블럭된 쓰레드 중 하나를 잠에서 깨운다