7. 운영체제 Lock

Lock이란?

• 여러 코드 명령어를 lock으로 둘러서 그 영역을 하나의 atomic instruction으로 만드는 것
• lock variable은 lock의 상태를 나타냄 → avaiable or acquired

 

Mutex Lock

• lock()을 호출했을 때, 다른 쓰레드가 해당 lock을 사용하고 있지 않다면, 그 쓰레드는 lock을 획득하면서 critical section에 진입함
• 다른 쓰레드가 같은 lock variable로 lock()을 호출하면 소유중인 쓰레드가 그 lock을 놓기전에는 실행되지 않음

 

Mutex Unlock

• 쓰레드가 unlock()을 호출하면 해당 lock variable은 available 상태가 됨
• 이 때 대기중인 쓰레드가 있다면 그 중에 하나가 실행됨

 

Lock Implementation

1. Mutual Exclusion : Critical Section이 잘 보호되었는가? Mutual Exclusion 잘 되는가?
2. Fairness : Starvation이 발생하지 않는가?
3. Performance : 락을 얻고 해제하는데 오버헤드가 어떠한가?

 

1) Disabled Interrupt 

• critical section안에서는 interrupt를 비활성화하여 그들을 atomic하게 하는 것
• 문제점 : 쓰레드가 특권을 갖게 되고 멀티 코어 프로세서에서는 적용이 안됨

 

2) Test-And-Set

• 단순히 "flag 변수"를 추가해서 "lock의 소유 여부"를 알려줌
• critical section에 진입하는 쓰레드는 변수를 Test하고 사용 가능하다면 Set함
• Spin lock :  다른 쓰레드들은 while loop 안에서 lock이 available 할 때까지 대기

 

Race condition

• lock variable을 Test하는 과정에서 interrupt가 발생하면 race condition이 발생할 수 있다.
• Thread0이 Test해서 critical section에 진입하고 Set을 하기전에 interrupt가 발생하여 Thread1도 critical section에 진입하면 atomic이 깨진다.
  

  

Atomic Test-And-Set

• 이 함수는 어셈블리 딴에서 xchg 명령어로 atomic하게 실행됨
• 이 함수를 통해 interrupt와 race condition을 막을 수 있음
  

  

• 맨 처음 lock()을 호출하면 flag를 1로 만들고 0을 리턴한다.
• 그 상태에서 다른 쓰레드가 lock()을 호출하면 1을 리턴하므로 계속해서 while loop를 도는 spin lock이 발생한다.

 

3) Other Methods

1. Compare-And-Swap
2. Load-Linked, Store-Conditional
3. Fetch-And-Add

 

---

Spin Lock의 문제점

• Mutual Exclusion : Good
• Fairness : Bad, 모든 쓰레드가 공평하게 실행될 기회를 보장할 수 없음
• Performance : Bad, lock을 test하면서 CPU를 낭비하지만 아무것도 안함. 싱글코어일 때 더욱 문제

 

Yield Instead of Spin

• Spinning 대신에 yield() 라는 system call을 호출
  

  

• yield() call은 CPU 낭비를 줄여주지만, 반복되고 중복되는 yield() call이 발생한다.

 

Sleep Instead of Spin : Park and Unpark 

• sleep 상태를 유지하다가 lock이 available할 때 wake up
• park() : 재움
• unpark() : 깨움

 

mutex 초기화

mutex_lock

• lock()에서는 guard라는 변수를 사용하여 flag변수와 큐의 동작을 spin lock으로 보호한다.
• 만약 flag가 0이 아니라면, lock을 획득하지 못하고 wait queue에 들어가서 sleep(park)

 

Race Condition

• 쓰레드가 park() 하기 직전에 interrupt가 발생하여 lock을 소유중이 쓰레드가 unpark()를 호출하는 경우
  → 이러면 sleeping 쓰레드가 영원히 깨어나지 못함
• OS는 setpark() 함수를 통해 park() 직전에 쓰레가 있음을 알림
  

  

 

mutex_unlock

• 똑같이 guard가 사용됨
• wait queue에 쓰레드가 없으면 lock을 해제, 있으면 unpark()해서 깨움
• guard로 인해 lock이 획득-해제를 반복하는 것이 아니라 다음 쓰레드에서 lock을 전달하는 방식으로 이어짐

 

Futex

• Fast user-space mutex
• futex_wait() 과 futex_wake()
• 하나의 쓰레드가 lock과 unlock을 할 때 최적화된 알고리즘

---

Sleep and Spin

spinning은 lock이 해제되기 직전에는 유용한 것으로 알려져 있다.

대기 중인 lock이 짧은 시간 안에 풀린다는 보장만 있다면(ex. 커널 프로그래밍) spin lock이 더 효율적이다.

 

Multi-Threading Isn't Always Faster

• 멀티 쓰레드 프로그래밍에서 correctness와 performance는 조심스럽게 다뤄져야 한다.
• 아래 코드는 thread-safe하지만, 쓰레드 수가 늘어날수록 성능이 저하된다.
• 쓰레드들이 lock으로 보호되면 쓰레드가 순차적으로 실행되어 싱글 쓰레드보다 느려진다.
  

  

• 위 코드를 아래와 같이 바꾸면 성능이 개선된다.
  

  

 

Tips! 

• Tip 1: Minimize the number of critical sections.
• Tip 2: Reduce the length of critical sections.
• Tip 3: Separate a critical section into multiple, disjoint parts by using independent locks, instead of using a single lock to protect the entire function or data structure.