9. Advanced lock; Locks and Condition variables

기존 lock은 OS 스케쥴러가 lock으로 인해 무슨 일이 발생하는 지 몰랐다. 이제는 OS 스케쥴러가 이 lock 활동을 직접 관리하여 ready 상태의 thread를 run한다. 구현은 간단하게도 ready queue에서 lock으로 인해 동작 못하는 thread는 제거하는 방식이다. (park(), unpark())

 

Lock: Block when waiting

Lock에 lock과 guard, 그리고 queue가 있다. Guard는 queue를 위한 lock이라고 보면 된다. Acquire lock 과정은 다음과 같다.

1. guard 사용중: spin wait
2. guard 작업 없음: guard 얻음
   1. lock 잡혀있음
      1. queue에 thread 넣고 guard 내리기
      2. park()
   2. lock 없음
      1. lock 잡기
      2. guard 내리기

 

Release lock 과정은 다음과 같다.

1. guard 사용중: spin wait
2. guard 작업 없음: guard 얻음
   1. queue 비어있음
      1. lock 버리기
   2. queue에 뭐 있음
      1. unpark()
   3. guard 내리기

 

Queue에 guard를 사용할 때, spin wait을 해도 상관 없는 것은 작업 자체가 매우 빠른 시간 내에 끝나기 때문이다. release()할 때, unpark()하면서 lock=false를 하지 않는 이유는 thread를 깨우는 데에만 목적이 있기 때문이다.

 

Queue를 구현함으로 thread의 상태까지 관리할 수 있게 되었지만, race condition이 발생하게 된다.

wakeup/waiting race

Thread 1이 park()하기 전에 guard가 false가 되다보니까, thread 2가 lock을 release하는 과정에서 unpark()를 먼저 하게 된다. 이렇게 되면 thread 1은 queue에 park()되어 있는데, unpark()을 해줄 thread가 없어 thread가 죽어버린다. 그렇다고 park()한 후에 guard를 내리는 것은 불가능함으로 새로운 방법이 필요해진다. 그래서 나온게 setpark()다. "나 park()할 꺼니까 unpark()하지 마셈"이라고 알리는 것이다.

 

Block when waiting: Final correct lock

setpark()

setpark()의 효과는 굉장했따!

• setpark() 이후에 park() 전에 unpark()가 불리게 되면, park()는 thread를 queue에 넣지 않고 바로 return 한다.

 

Spin-waiting vs Blocking

Spin-waiting이 마냥 구리지는 않다. 가령 block되는 기간이 매우 짧다면, context switch 급의 비용을 지불하지 않고 계속해서 CPU를 잡고 있는 것이 더 효과적일 수 있다. 또한 프로세서가 uni-인지 multi-인지에 따라서도 장단점이 있다.

 

Uni-processor

Lock으로 인해 spin을 하고 있는 프로세스가 있다면, lock을 잡고 있는 친구를 먼저 돌리는게 효율적이다.

• Block이 더 좋아

 

Multi-processor

Waiting중인 친구가 스케쥴링되었다는 것은, 아마 곧 lock을 가질 것으로 예상된다는 의미이다. 그래서 lock이 release되기 전에, spin이나 block 중에 하나를 하고 있어야 한다.

• Lock이 빠르게 release됨: spin-wait (cost: CPU time)
• Lock이 느리게 release됨: block (cose: context switch)

이러나 저러나 결국 context switch 비용과 CPU time을 비교해 결정하게 된다. 최악의 경우에는 context switch를 겁나 빠르게 2번하는 경우이겠다.(시험에 나올지도?) 계산은 다음 내용을 참고하자.

 

When to Spin-wait vs Block?

Lock을 release하기 까지 thread의 실행 시간을 알고 있으면 spin을 할지, block을 할지 결정할 수 있게 된다. 우선 각 동작의 waste time이나 cost를 알아보자.

• Spin: CPU time, T
• Block: context switch cost, C

 

T<C면 spin을 하고 T>C면 block을 하면 될 것 같다. 다만 이를 결정하기 위해서는 job의 runtime을 알 수 있어야 하고 이는 상당한 overhead를 가져옴으로 사용이 사실상 불가능하다.

 

이를 해결하고자 등장한 것이 Two-phase Waiting이라고 보면 된다.

 

Two-phase waiting

Worst-case performance를 bound하려는 알고리즘이다. Performance는 actual/optimal로 선정한다.

 

Worst possible의 performance는 T이다. Spin-wait을 무한대로 할 수 있기 때문이다. 이 때, optimal은 block 한번임으로 C이다. 따라서 performance는 T/C이다. Bound되지 않는다.

 

이를 보장하기 위해서는 C만큼 spin하다가 block하면 된다. 이 때의 actual cost = T(=C) + C = 2C가 된다. Optimal은 C임으로 performance는 2가 되어 bound된 performance를 보장할 수 있게 된다.

 

 Concurrency objectives

Mutual exclusion은 lock을 통해 해결할 수 있었다. Ordering은 어떻게 결정할까? 해답은 conditional variables과 semaphore이다. Ordering이 필요한 상황은 parent에서 thread의 종료를 기다리는 경우이다.

 

Conditional variables

Waiting thread의 queue라고 생각하면 된다. wait(CV)과 signal(CV)가 있다.

• wait(CV, lock)
  • acquire lock
  • thread sleep + release lock (atomic)
  • Awaken될 때, lock을 얻고 일어남
• signal(CV)
  • waiting thread 중 하나를 wake
  • waiting thread가 없으면 그냥 return

 

그래서 join은 다음처럼 구현될 수 있다.

Parent에서 thread_join()을 부르고, child에서 thread_exit()하기를 기다리는 상황이다. Parent는 conditional variable을 통해 wait한다. Child는 job이 완료되면 signal(CV)을 통해 parent의 wait을 깨운다. 

 

당연히도 atomic한 operation이 아니기 때문에, signal before wait 같은 경우가 발생한다. 해결방법은 다음과 같다.

done = 1을 추가하여 thread_exit()이 먼저 실행되면, parent에서 wait()하지 않도록 구현한다.

 

Producer/consumer problem

Conditional variable이 주로 사용되는 경우는 producer/consumer 구조의 상황이다. 대표적인 경우는, UNIX pipes이다. Buffer에 data를 read/write하는 경우로, write하면 buffer에 data가 저장, read하면 buffer에 data가 지워진다. Buffer가 가득 차면, writer는 기다리고 반대로 비어 있으면 reader가 wait해야 한다.

 

Easy case

다음의 상황을 가정하고 conditional variable을 사용해 본다.

• 1 producer
• 1 consumer
• 1 shared buffer to fill/consume (max = 1)
• numfill = buffer에 저장된 수

 

Producer와 consumer의 동작은 다음과 같다.

1. Consumer는 numfill == 0이기 때문에 sleep하게 된다. Producer는 numfill == max가 아니기 때문에 하나를 채우고 signal()을 통해 consumer를 깨우게 된다.
   1. Producer가 실행될 경우, wait(CV)에 의해 sleep되고
   2. Consumer가 실행될 경우, numfill != 0이기 때문에 buffer에서 1개를 가져오고 signal()을 통해 producer를 깨우게 된다.

 

이런 식으로 비교적 간단하게 ordering을 구현할 수 있게 된다. 그러나 consumer나 producer의 수가 늘어나면, 모두 sleep되는 문제가 발생할 수 있다. 가령 2 consumers라고 생각해 본다.

1. Consumer 1이 sleep
2. Producer가 1개 만들고 깨우고, sleep
3. Consumer 1이 data를 get하려고 헀지만, Consumer 2가 먼저 실행되서 read가 안됨

 

위 문제는 if문을 while문으로 바꾸면, 다시 sleep이 되기 때문에 producer에게 차례가 넘어가 data를 buffer에 넣을 수 있게 된다. 다만, 이때는 다른 문제가 발생한다.

1. Consumer 1 sleep
2. Consumer 2 sleep
3. Producer 1개 만들고 signal 1개, sleep
4. Consumer 1이 한개 가져가고 sleep
5. 전부다 sleep(buffer에 아무것도 없음)

 

해결책 1

이게 다 적합한 친구를 깨워주지 못해서 발생하는 문제이다. 근데 적합한 친구를 찾는 것은 어려운 일이니, 해결이 어렵다. 그래서 그냥 전부다 깨워버린다. 이를 broadcase(CV)로 사용한다. Waiting인 친구들도 깨워버리긴 하지만, 어차피 또 wait될 친구들이기 때문에 상관 없다.

 

해결책 2

상황에 맞춰서 2개의 conditional variable을 사용하는 방법이다. 위의 예제에서는 producer가 &empty CV를, consumer가 &fill CV를 사용한다. 다음처럼 문제 없이 동작이 가능해진다.

 

 

Consumer는 do_fill() 다음에 동작하고, producer는 do_get() 이후에 동작하게 된다.