저번 글에서는 spinlock을 이용하여 lock을 구현하는 방법을 알아보았습니다. 특히 Hardware-based spin lock들은 간단하고 잘 작동하였습니다.
이러한 해결책은 thread가 spinning을 할 때 time slice동안 값을 확인하는 것외에 아무 작업도 하지 않기 때문에 매우 비효율적일 수 있습니다.
따라서 OS의 도움을 받아 spinning을 피할 수 있는 방법에 대해 공부해보겠습니다.
Spinning을 피하는 방법
=> OS의 Support
1. Just Yield
가장 간단한 방법으로 Just Yield가 있다. 말 그대로 현재 스레드가 spin을 하고 있으면, CPU를 다른 스레드에게 주는 방법이다
- OS 시스템 콜은 caller를 running 상태에서 ready 상태로 바꾼다.
- 이 방법은 context switch 비용이 크고, startvation 문제가 존재한다. (yield하고 다른 스레드가 계속 사용하여 starvation 문제 발생 가능)
2. Using Queues: Sleeping Instead of Spinning
두 번째 방법으로는 lock에 진입을 기다리는 스레드를 추적할 Queue를 두는 것이다.
- park(): 호출한 스레드를 sleep에 놓는다.
- unpark(threadID): threadId로 지정된 특정 스레드를 깨운다.
guard 변수를 사용하여 flag를 변경하기 전 즉, lock을 흭득하기 전에 guard로 한 번더 체크를 해주는 것을 확인할 수 있다.
하지만 spinning lock을 해결한 방법인데 lock함수 내부를 보면 여전히 spinning이 있는 것을 확인할 수 있다. gaurd에 대한 spinning으로 (flag값을 변경할 때 mutual exclusive를 보장하기 위해), 먼저 들어온 thread가 lock flag를 1로 선점하고 나면 다시 guard를 0으로 설정하기 때문에 오랫동안 spinning하지 않는다. 따라서 기존 spin lock에 비해 overhead가 현저히 작다고 한다.
unlock함수에서 큐가 비었으면 flag=0으로 만들어 lock을 해제하고, 큐에 lock을 기다리는 스레드가 있을 경우 lock을 그대로 유지하고 unpark을 호출한다.
Wakeup/waiting race
위 경우 Wakeup/waiting race가 발생할 수 있다.
- 스레드 B가 lock에서 park()을 호출하기 전에 context switch가 발생하고, 스레드 A가 lock을 해제하는 경우(unpark) 스레드 B는 sleep에서 깨어날 수가 없다. (깨워줄 스레드가 없음)
- Solaris는 세 번째 system call인 setpark()을 추가하여 이 문제를 해결한다.
- setpark을 호출함으로써, 스레드가 조만간 park을 할 것이라는 것을 알려준다.
- 만약 park이 실제로 호출되기전에 unpark이 호출되면, 이어지는 park은 sleeping하는 대신
즉시 리턴한다.
3. Futex
Linux에서는 Solaris의 park와 unpark과 비슷한 futex를 제공한다.
- futex_wait(address, expected): 호출한 스레드를 sleep에 넣는다. 만약 address가 expected와 다르면 즉시 리턴한다.
- futex_wake(address): 큐에서 wait중인 스레드를 하나 깨운다.
futext를 사용하여 구현한 lock을 살펴보자.
v의 최상위 비트는 lock을 사용중인지 아닌지 확인한다.
나머지 모든 비트는 기다리고 있는 스레드 수를 나타낸다.
위의 mutex_lock함수 내부에서는 4가지 경우로 lock을 얻을 수 있다.
먼저 mutex_lock함수를 리턴한다는 것은 mutex_lock을 호출한 코드에서 리턴을 기다리며 wait하고 있는 상태가 풀리는 것이므로 lock을 얻는다고 이해하면 된다.
-
atomic_bit_test_set를 이용하여 31번 비트(최상위 비트)를 atomic하게 test와 set한다. 만약 리턴값이 0이면 mutext_lock 함수를 return하고 즉시 lock을 얻게 된다. 그렇지 않다면 atomic_increment를 수행하여 기다리고 있는 스레드 수를 하나 증가시키고 while문 내부로 들어간다.
-
while문 내부에서 다시 최상위 비트에 대해 test_set을 수행하고 lock을 얻을 수 있으면 atomic_decrement를 호출하여 기다리고 있는 스레드 수를 감소시키고 lock을 얻는다. 그렇지 않으면 v에 mutex의 값을 저장한다.
-
만약 v가 음이 아닌 정수이면 즉, 최상위 비트가 0인지 1인지 판단하여 양수이면 lock을 가진 스레드가 unlock을 했다는 의미이므로, continue문에 의해 while 반복문의 처음으로 돌아가서 test_set을 수행한다. 그렇지 않으면 futex_wait을 호출한다.
-
futex_wait에서도 v값과 mutex의 값이 다르면(lock을 가진 스레드가 unlock시 최상위비트 1이 0으로 바뀜) 즉시 리턴하여 lock을 얻게 된다.
mutext_unlock에서는 atomic_add_zero를 호출하는데 최상위 비트에 1을 더해주고, 0인지 확인한다. 만약 0이면 lock을 기다리는 스레드가 없다는 뜻이므로 리턴한다. lock을 기다리는 스레드가 존재할 경우 futex_wake를 호출하여 sleep큐에서 스레드 하나를 깨운다.
4. Two-Phase Locks
지금까지 spinning을 피하기 위해 lock을 얻을 수 없을 경우 sleep하는 형태로 lock을 구현하는 방법을 알아보았다.
하지만 lock이 곧 풀릴 것인데, sleep을 호출하여 context switch를 하는 것은 손해일 것이다.
따라서 어느정도 spinning은 유용할 수 있다. 이 접근을 이용한 것이 Two-Phase Locks이다.
- First phase
잠시 동안 lock을 흭득하기를 기다리며 spin 하고 첫번째 spin phase동안 lock을 얻지 못하면, 두번째 phase에 진입한다. - Second phase
caller를 sleep한다. (context switch) caller는 lock이 free가 된 이후 깨어난다.
이렇게 OS의 도움을 받아 spin lock을 지양하여 구현하는 방법과 두 방법을 적절히 합친 방법까지 모두 알아보았습니다.
다음에는 Thread들간의 동작을 동기화 하기 위한 Condition Variable에 대해 알아보겠습니다.
