1. 락: 기본 개념
락은 일종의 변수다.
락을 사용하기 위해서는 락 변수를 먼저 선언해야 한다.
이 락 변수는(또는 짧게 락은) 락의 상태를 나타낸다.
락은 둘 중 하나의 상태를 갖는다.
첫 번째는 사용 가능(available) 상태이다.
즉, 어떤 스레드도 락을 소유하고 있지 않다.
두 번째는 사용 중(acquired) 상태이다.
즉, 임계 영역에서 정확히 하나의 스레드가 락을 획득한 상태이다.
lock()과 unlock() 루틴의 의미는 간단하다.
lock() 루틴 호출을 통해 락 획득을 시도한다.
만약 어떤 스레드도 락을 갖고 있지 않으면 그 스레드는 락을 획득하여 임계 영역 내로 진입한다.
이렇게 락을 획득한 스레드를 락 소유자(owner)라고 부른다.
만약 다른 스레드가 lock()을 호출할 경우, 락이 사용중인 동안에는 lock() 함수는 리턴하지 않는다.
락을 소유한 스레드가 임계 영역에서 존재하는 상태에서는 다른 스레드들이 임계 영역으로 진입할 수가 없다.
락 소유자가 unlock()을 호출한다면 락은 이제 다시 사용 가능한 상태가 된다.
어떤 스레드도 이 락을 대기하고 있지 않다면 락의 상태는 사용 가능으로 유지된다.
만약에 대기 중이던 스레드가 있었다면, 락의 상태가 변경되었다는 것을 인지하고 락을 획득하여 임계 영역 내로 진입하게 된다.
2. 락의 평가
락 설계시, 락의 정상동작 여부 판단을 위한 평가기준을 정해야 한다.
첫째는 상호 배제를 제대로 지원하는가이다.
기본적으로 락이 동작하여 임계 영역 내로 다수의 스레드가 진입하는 것을 막을 수 있는지 검사해야 한다.
둘째는 공정성(fairness)이다.
쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가?
이것을 보는 다른 관점은 좀 더 극단적인 상황을 평가해 보는 것이다.
락을 전혀 얻지 못해 굶주리는(starve) 경우가 발생하는가?
마지막 기준은 성능(performance)이다.
특히, 락 사용 시간적 오버헤드를 평가해야 한다.
이 주제에 대해서 고려해야 할 몇 가지 사항이 있다.
하나는 경쟁이 전혀 없는 경우의 성능이다.
하나의 스레드가 실쟁 중에 락을 획득하고 해제하는 과정에서 발생하는 부하는 얼마나 되는가?
다음은 여러 스레드가 단일 CPU 상에서 락을 획득하려고 경쟁할 때의 성능이다.
마지막은 멀티 CPU 상황에서 락 경쟁 시의 성능이다.
이런 서로 다른 상황의 성능을 평가하여야 앞으로 다룰 다양한 락 기법들이 성능에 미치는 영향을 이해할 수가 잇다.
3. 인터럽트 제어
초창기 단일 프로세스 시스템에서는 상호 배제 지원을 위해 임계 영역 내에서는 인터럽트를 비활성화하는 방법을 사용했었다.
이 방법은 응용 프로그램을 너무 많이 신뢰해야 하며, 멀티프로세서에서는 적용할 수가 없고, 중요한 인터럽트의 시점을 놓칠 수 있으며, 최신의 CPU 들에서는 느리게 실행되는 경향이 있다.
4. load/store 명령어만 사용하기
인터럽트 활성화/비활성화 방법을 사용하지 않고 락을 구현하려면 CPU 하드웨어와 락 구현을 위한 명령어를 사용해야만 한다.
간단한 변수(flag)를 사용하여 스레드가 락을 획득하였는지를 나타낸다.
임계 영역에 진입하는 첫 스레드가 lock()을 호출하여 플래그 값이 1인지 검사(test)하고 플래그의 값을 1로 설정(set)하여 이 스레드가 락을 보유(hold)하고 있다고 표시한다.
임계 영역에서 나오면 스레드가 unlock()을 호출하여 플래그 값을 초기화하여 락을 더 이상 보유하고 있지 않다고 표시한다.
만약 첫 번째 스레드가 임계 영역 내에 있을 때 다른 스레드가 lock()을 호출하면, 그 스레드는 while 문으로 spin-wait 하며 처음 스레드가 unlock()을 호출하여 플래그를 초기화하기를 기다린다.
처음 스레드가 플래그를 초기화하면 대기하던 스레드는 while문에서 빠져나와 플래그를 1로 설정하고 임계 영역 내로 진입한다.
이 방식에는 두 가지 문제가 있다.
하나는 제대로 작동하는가 여부(correctness)이고 다른 하나는 성능이다.
5. test-and-set
TestAndSet 명령어가 하는 동작은 다음과 같다.
ptr이 가리키고 있던 예전의 값을 반환하고 동시에 new에 새로운 값을 저장한다.
여기서의 핵심은 이 동작들이 원자적으로 수행된다는 것이다.
"testandset"라고 부르는 이유가 이전 값을 검사(test)하는 동시에 메모리에 새로운 값을 설정(set)하기 때문이다.
지금 설명한 방법이 스핀 락으로 불리는 이유를 이제 이해할 수 있을 것이다.
이것이 가장 기초적인 형태의 락으로서, 락을 획득할 때까지, CPU 사이클을 소모하면서 회전한다.
단일 프로세스에서 이 방식을 제대로 사용하려면 선점형 스케줄러(preemptive scheduler)를 사용한다.
이 방식은 상호 배제를 제대로 지원하지만 어떠한 공정성도 보장해 줄 수 없으며 단일 CPU의 경우 스핀 락이 갖는 성능 오버헤드는 상당히 클 수 있다.
스레드는 할당받은 기간 동안 CPU 사이클을 낭비하면서 락을 획득하기 위해 대기하기 때문이다.
반면에 CPU가 여러 개인 경우 스핀 락은 꽤 합리적으로 동작한다.
다른 프로세서에서 락을 획득하기 위해 while문을 회전하면서 대기하는 것은 그렇게 많은 사이클을 낭비하지 않기 때문에 효율적일 수 있다.
6. Compare-And-Swap
이 기법의 기본 개념은 ptr이 가리키고 있는 주소의 값의 expected 변수와 일치하는지 검사하는 것이다.
그 이후의 코드는 앞서 사용한 Test-And-Set와 동일하다.
7. Fetch-And-Add
이 기법은 특정 주소의 예전 값을 반환하면서 값을 증가시킨다.
티켓 락이라는 재미있는 것을 만들어보자.
하나의 변수만을 사용하는 대신 이 해법에서는 티켓(ticket)과 차례(turn) 조합을 사용하여 락을 만든다.
기본 연산은 간단하다.
하나의 스레드가 락 획득을 원하면, 티켓 변수에 원자적 동작인 fetch-and-add 명령어를 실행한다.
결과 값은 해당 스레드의 차례를 나타낸다.
전역 공유 변수인 lock->turn을 사용하여 어느 스레드의 차례인지 판단한다.
만약 한 스레드가 (myturn == turn) 이라는 조건에 부합하면 그 스레드가 임계 영역에 진입할 차례인 것이다.
unlock 동작은 차례 변수의 값을 증가시켜서 대기 중인 다음 스레드에게 임계 영역 진입 차례를 넘겨준다.
8. 과도한 스핀
한 스레드가 락을 획득한 상태라서 그 스레드가 락을 해제하기만을 기다리며 스핀만 무한히 하는 경우에 어떻게 해야할 것인가?
양보(yield)라는 시스템 콜을 호출하여 스레드 상태를 준비(ready) 상태로 변환하여 다른 스레드가 실행 중 상태로 전이하도록 할 수 있다.
하지만 이 방법은 문맥 교환 비용이 상당하며 낭비가 많다.
또한 어떤 스레드는 무한히 양보만 하고 있는 경우가 있을 수 있다.
9. 큐의 사용: 스핀 대신 잠자기
이전 방법들의 근본 문제는 너무 많은 부분을 운에 맡긴다는 것이다.
다수의 스레드가 락을 대기하고 있을 경우, 다음으로 락을 획득할 스레드를 명시적으로 선택할 수 있어야 한다.
이를 위해서는 운영체제의 적절한 지원과 큐를 이용한 대기 스레드들의 관리가 필요하다.
Solaris의 방식을 사용하겠다.
두 개의 호출 문이 있는데, park()는 호출하는 스레드를 잠재우는 함수이고 unpark(threadId)는 threadId로 명시된 특정 스레드를 깨우는 함수이다.
이 두 루틴은 이미 사용 중인 락을 요청하는 프로세스를 재우고 해당 락이 해제되면 깨우도록 하는 락을 제작하는 데 앞뒤로 사용할 수 있다
10. 다른 운영체제, 다른 지원
Linux의 경우 futex라는 것을 지원한다.
이것은 Solaris의 인터페이스와 유사하지만 커널 내부와 좀 더 밀착되어 있다.
futex는 특정 물리 메모리 주소 그리고 커널에 정의된 큐를 가지고 있다.
호출자는 futex 관련 함수를 호출하여 잠을 자거나 잠에서 깨어난다.
futex는 두 개의 명령어가 있다.
futex-wait(address, expected) 명령어는 address의 값과 expected의 값이 동일한 경우 스레드를 블럭시킨다.
같지 않다면 리턴한다.
futex-wake(address) 명령어를 호출하면 큐에서 대기하고 있는 스레드 하나를 깨운다.
