[Distributed System] TestAndSet Lock

※ Herlihy , shavit 책을 그냥 혼자보기 쉽게 요약한 내용이라서 잘못된 내용이 담겨 있을 수 있다.

분산시스템에서 초점을 맞추고 있는 형태는 MIMD(Multiple Instruction Multiple Data)의 구조다.

[1]

MIMD의 형태로는 위와 같이 Bus를 sharing하는 형태를 보일 수도 있고, 혹은 오른쪽처럼 Mesh 형태로 core와 memory가 분산되어 있는 형태를 취할 수도 있다. 이중에서 Shared Bus 형태는 당연하겠지만 contention이 발생한다. thread가 memory로부터 데이터를 읽어올때는 항상 한개의 thread만이 bus를 점유하기 때문에 이에 따른 memory쪽이나 thread간의 communication 에 대한 contention이 발생할 수 있다. 물론 이를 해결하기 위해서 Lock을 쓰게 된다. Lock의 초점이 과거에는 thread가 과연 정해진 term에 Lock을 얻고 free 할 수 있느냐에 대한 correctness가 중요시 되었지만, multiprocessor가 나오면서 performance도 중요한 요소로 등장하게 되었다. 이를 위한 다양한 Lock Algorithm도 개발되었다. 

 자 그럼 Lock을 적용하면서 performance를 올리고 싶다. 어떻게 Lock을 써야 효율적인 성능을 나타낼까? 조금 막연하게 들릴 수 있겠지만, 가장 간단한 방법은 "그냥 중간에 쉴틈없이" Lock을 거는게 가장 효율적일 것이다.다르게 이야기 하면 Lock을 얻길 원하는 thread는 계속 상주해있다가, 필요할 때 Lock을 얻어가면 될 것이고, Lock을 얻지 못한 thread는 그냥 제자리에서 계속 맴돌면서 Lock-free가 되길 기다리는 것이다. 보통 이런 개념을 Spinning 혹은 spin lock이라고 하고, 또는 기다리는 thread 입장에서 본 busy-waiting이라고 언급하기도 한다. herlihy 책에서는 앞 장에서 언급된 Filter Lock이나 Bakery Algorithm 같은게 spin lock의 종류라면 보면 될 것 같다. 당연한 이야기이겠지만 이런 Lock에 걸리는 시간이 짧으면 짧을 수록 많은 thread들이 돌아가면서 일을 원활하게 처리할 수 있을 것이다.

 그런데 이런 spinlock의 문제는 lock을 얻지 못한 thread가 쭉 나열되면서 일종의 bottleneck을 보이게 된다는 것이다.

[2]

 

당연히 LockFree가 되면서 thread끼리는 누가 먼저 Lock을 얻을 것인가에 대한 경쟁을 할 것이고, 결국 contention이 발생하게 된다. 결국 이렇게 되면 thread를 여러개 사용하면서 얻을 수 있는 이점인 parallelism의 혜택은 누릴 수 없게 되는 것이다. 이를 위해서 도입하는 개념이 TestAndSet 이라는 것이다. 사실 이건 Lock을 위해서 나타났다기 보다는 Atomic operation을 하기 위해서 하드웨어 상에서 지원해주는 instruction 중 하나이다. 물론 단순히 하드웨어 차원이 아니라 소프트웨어 상으로도 구현이 되어 있고, C로는 다음과 같이 표현된다.

[3]

간단하게 설명하면 swap Mechanism을 사용해서 이전 값과 비교하는 것이다. 그래서 lockPtr에 들어있는 값을 oldValue에 넣어주고 반환해주는 구조를 가지고 있다. int로 구현되어 있긴 하지만 실제로 동작은 boolean으로 하며,넣어준 값이 true냐 false냐에 따라서 동작이 달라지게 된다. 이걸 Lock에 응용한게 TAS Lock이 된다. 크게 구조는 다음과 같이 된다,

[4]

위의 TAS코드를 그대로 가져와서 본다면 전역변수로 지정되어 있는 lock = 0 값이 TAS를 수행하면서 1로 변하게 될 것이다. 그런데 이 변수는 전역변수이기 때문에 한 Thread가 이미 값을 바꿔놓았다면 다른 thread가 이 값을 읽어올때는 다른 값을 읽게 될 것이다. 즉, 먼저 lock을 일고 TAS를 수행한 thread가 Lock을 가져가게 되는 것이다.

[5]

결국 그림처럼 먼저 TAS를 수행한 결과가 false가 나온 thread는 현재 lock을 hold하는 상태가 될 것이고, TAS가 true를 return 했다면 어떤 thread가 lock을 점유하고 있다는 말이 된다. 그런데 이게 언제까지 한 thread가 lock을 계속 가지고 있을 수는 없으므로 critical section이 끝난 이후에는 반드시 lock 변수를 다시 원래대로 false로 정의하게 해준다.

 하지만 단순히 TAS Lock만을 통해서는 효율적인 Lock을 구현할 수 없다. 결국은 thread가 Lock을 얻기 위해서는 매번 Lock() 함수를 불러야 하는데 이 부분이 어떻게 보면 비효율적이다, 그래서 Lock을 얻고자 할때 다른 thread가 LockFree를 할때까지 대기 하는 과정을 포함시킨게 TTAS(Test and Test And Set) Lock이다. 이 부분은 다음글에서 계속 이어보겠다.

Reference

[1][2] The Art Of Multiprocessor Programming : Chapter 7. Spin Locks And Contention ( Herlihy, shavit)

[3][4] TestAndSet (http://en.wikipedia.org/wiki/Test-and-set)

[5] Multicore Programming (http://www.cl.cam.ac.uk/teaching/1011/R204/2010-11nov-08-2-locks.pdf)