개요
LOCK이란 Atomicity를 부여하기 위해서 하나의 변수에 대한 접근을 제한하는 것이다. Lock은 다중 코어 환경에서 시스템에 일관성을 부여한다. Blocking Lock (spin lock, RW lock..)이나 Non-Blocking Lock(Mutex, Semaphores..)로 분류할 수 있다. 점점 증가하는 다중 코어환경에 적응 하기 위해서 Lock mechanism은 점점 진화하고 있다.
고려 사항
- Cache line movement: Lock의 read와 write가 cache line을 intensive하게 변경하는가?
- Varing thread contention: Lock이 contention이 심할때도 적을때도 빠르게 작동하는가? 특히 Fine-grained lock환경에서는 lock들의 contention이 심해지는 것은 일부분인데 두 경우 모두 빠른 응답속도를 제공할 수 있는가?
- Core subscription: Application은 Lock을 core을 subscripbe한뒤 idle상태에 두기 위해서 사용할 수도 있다. 이러한 경우에 spin lock그리고 sleeping lock의 적절한 선택이 요구된다. 즉 Lock이 빠른 응답속도를 위해서 Spin 할지 아니면 Utilization을 위해서 Sleep할지를 결정하는 문제가 있다.
- Memory footprint: Memory footprint는 Lock이 차지하는 공간이외에도 Scalablity때문에 중요하다. Lock의 사이즈가 크면 Scalability에 도 좋지 않을뿐더러 큰 Memory allocation을 일으켜서 Application성능을 감소시키기도 하고 struct page와 같이 크기에 민감한 곳에는 사용할 수 없기도 하다.
구현 방법
- Interrupt: 인터럽트를 해제하면 스레드 부분이 스케쥴링 되지 않음으로 변수의 Atomic을 보장할 수 있다.
- Busy-implementation: Lock변수가 사용되는 동안, 다음 사용을 요구하는 스레드를 무한 루프에 빠지게 함으로써 Lock을 획득 할 수 있다.
- Schedule thread: Lock변수가 사용되는 동안, 다음 스레드(프로세스)로 context를 넘김으로서 Lock을 획득 할 수 있다.
- 대부분의 사용 OS처럼 Linux는 nested critical sections즉 lock안에 lock을 허용하지 않는다. (심각한 Lock contention이 발생할 수 있다.)
Spin Lock
여기서 Busy lock 은 Spin lock이라고도 불리는데, 보통 스레드가 짧은 시간동안 선점되는 경우에 주로 사용한다. 즉 scheduling overhead가 spin lock하는 시간보다 길경우 사용하면 좋을 결과를 얻을 수 있다. 그러나 스핀락은 CPU사이클을 낭비하며, Starving문제가 생길수가 있다. 이는 어떠한 스레드가 SpinLock을 획득하는 지에 대한 순서를 정할 수가 없기 때문이다.
이문제를 해결하기 위해서 Ticket lock이라는 기법이 있다. 이는 하나의 쓰레드가 락 획득을 원하면, int형 Atomic 자료구조인 티켓 변수가 원자적으로 값을 증가(++)시킨다. 결과 값은 해당 쓰레드의 "차례(turn)"를 나타낸다. 만약 한 쓰레드가 (turn == myturn)이라는 조건에 부합하면 그 쓰레드가 임계 영역에 진입할 차례인 것이다. 언락 동작은 차례 변수의 값을 증가시켜서 대기 중인 다음 쓰레드에게 임계 영역 진입 차례를 넘겨준다.
Spin Lock은 여러 구현 방식이 있다. 이는 다중 코어 환경 혹은 가상머신에서 Lock holder preemption을 해결하기 위해서 등장하는 것과도 일치한다. 예를 들어서...
- TAS Lock: Test and set Lock으로 가장 간단한 Lock구현방법이며, CPU에서 제공하는 Test and set 명령어를 사용하여 Lock을 구현한다.
- qspinlock: MCS lock의 변종으로 virtualized environment에서 사용하기 위한 방법중에 하나이다.
Hierarchical Locking
계층적 locking이란 NUMA와 같이 disaggregated 시스템에서, 각 lock들의 remote access cost을 줄이고 scalability을 올리기 위하여 lock을 여러 계층 즉 global lock과 per-node lock으로 구분하여 각각에 적당한 locking mechanism을 제공하는 방식을 말한다. 그러나 multicore 시스템에서 효과적인과는 별개로, 적은수의 core에서는 degraded performance와 memory overhead가 큰 문제점이 있다.
Mutex
이제 두 처리 단위가 임계 구역에 동시에 접근하지 못하도록 막는 기법이 필요해진다. 이를 '상호 배제(Mutual Exclusion)'이라고 하며 보통 '뮤텍스'로 줄여서 이야기한다. 즉 Lock과 UnLock만을 지원하는 Locking 방식이라고 할 수 있다.
Semaphore
세마포어 참조. 세마포는 일반화된 뮤텍스라고 생각할 수 있다. (뮤텍스와 세마포어는 서로 튜링 동치이다. 즉 세마포어로 뮤텍스를 뮤텍스로 세마포어를 구현할 수 있다.)
세마포어 S는 정수값을 가지는 변수이며, 다음과 같이 P와 V라는 원자적 명령에 의해서만 접근할 수 있다. (P와 V는 각각 try와 increment를 뜻하는 네덜란드어 Proberen과 Verhogen의 머릿글자를 딴 것이다.)
P는 임계 구역에 들어가기 전에 수행되고, V는 임계 구역에서 나올 때 수행된다. 이때 변수 값을 수정하는 연산은 모두 원자성을 만족해야 한다. 다시 말해, 한 프로세스(또는 스레드)에서 세마포어 값을 변경하는 동안 다른 프로세스가 동시에 이 값을 변경해서는 안 된다.
P연산은 S를 1감소시키고, S가 0과 같으면 Wait를 한다. V는 S를 1증가시키며, 만약 세마포S가 0에서 1로 바뀌면 기다리고 있는 P를 깨우게 된다.
세마포어는 두가지 중요한 방법으로 사용될 수 있다. Mutal Exclusion과 Signaling의 두가지 방법론이 있다. Mutual Exclusion은 Lock과 동이라하게 세마포를 1로 초기화 시켜서 사용하는 방법이며, Signaling은 초기화를 0으로 해준다음 다른 스레드가 up시키는 방법으로 사용한다.