[Concurrency] Lock: Mutex와 RWLock의 원리

보통 Mutex에는 2가지 구현체가 있다.

일반적인 최적화된 일반 Mutex와, read의 비율이 높은 상황에 최적화된 RWLock(Read Write Lock)이다.
후자는 RWMutex라고도 부른다.

read가 많을떄 RWLock이 더 빠르다는 것은 피상적으로 알지만, 그 구현 상세가 어떤 식인지는 대부분 잘 모를 것이다. 여기서는 Rust의 표준 구현을 예로 들어서 한번 간단히 풀어보겠다.

Futex의 구현 패턴에 대해서 안다면 이해가 더 빠를 것이다.
https://blog.naver.com/sssang97/224019441610

일반 Mutex의 구현

기본 Mutex는 futex라고 하는 매커니즘을 통해 구현된다.

경쟁이 적은 경우를 최적화하기 위해서 CAS 기반의 가벼운 User 레벨 Lock을 먼저 사용하고, 경쟁으로 인해 충돌이 발생하면 OS 수준에서 지원하는 Queue 기반의 스레드 스케줄링을 하는 것이다.

그래서 구현을 까보면

처음에 CAS 날려서 Lock 안걸려있으면 바로 lock을 점유한다.
CAS 수준 점유에 실패하면, 그때부터 본격적인 lock 경쟁 작업을 시작한다.

이렇게.

먼저 spin lock으로 User 기반의 가벼운 락을 잡고, spinlock으로도 점유가 불가능한 상황에서는 OS 기능인 futex를 호출해서 스레드를 대기열에 놓도록 구성을 한다.
futex_wait 함수를 호출하면, OS에서 Lock 점유가 가능할 때까지 스레드를 멈췄다가 실행해준다.
그러면 다시 동일하게 spinlock을 돌리는 것이다.

스핀락은 이런 식으로 구현되어있다.
100번까지 재시도한다.

스핀을 얼마나 돌지는 아마 언어 구현체들마다 다를 수 있을 것이다. Rust는 100번이다.

RWLock의 구현

이번에는 RWLock을 까보자.
RWLock의 기본적인 아이디어는 이렇다.

1. read는 다른 read를 차단하지 않는다.

2. read는 다른 write를 차단한다.

3. writer는 다른 write를 차단한다.

4. writer는 read보다 선점 우선순위가 높다.

다시 말해서 동시 read가 많이 들어오는 경우에 최적화된 구현이라고 할 수 있다. write는 비교적 무겁다.

이것도 futex의 구현 패턴을 따르는 것은 동일하나, 세부적인 구현은 보다 복잡한 편이다.

write부터 한번 보자.

CAS 한번 날려서 경쟁 없으면 즉시 lock을 얻는건 똑같다.

경쟁 구현부는 비교적 복잡한 편이다.

여기서 조금 특이한 것은, 단순 0/1 플래그를 쓰는게 아니라 비트단위 마킹으로 WRITE LOCK 상태와 READ LOCK 상태를 구분한다는 것이다.

이것도 마찬가지로 스핀락 먼저 시도하고, 금방 Lock을 얻는다면 futex syscall 없이 종료된다.
하지만 lock이 걸려있다면 futex syscall을 날려서 OS의 스케줄링을 얻는 형태다.

또 특이한 것이 WRITERS_WAITING 비트 플래그로 최초 write 진입자가 먼저 선점 체크를 한다는 것이다. 그래서 최초 writer는 os syscall 없이 계속해서 스핀락을 건다.
그 이후에 들어오는 후속 writer는 일단 futex_wait으로 os systecall을 날려서 장기간 대기를 고려한다.

spinlock은 비슷하게 최대 100번까지 돈다.

아무튼 이래서 RWLock의 write Lock이 Mutex의 일반 Lock보다는 리소스 비효율적인 것이다. writer가 빈번하게 진입한다면 스핀락으로 CPU를 계속 갈구는 놈이 항상 생기는 형태다.

이번에는 read lock을 봐보자.

read lock은 lock 점유 조건이 느슨하다.
state가 0일 필요도 없고, read lock 상태라면 언제든 진입 가능하게 해뒀다.
대신 read lock을 점유중인 reader 개수를 state로 계속해서 더한다.

경쟁 구현부도 대충 비슷하다.
write lock이 잡혀서 read lock을 잡을 수 없는 경우에 진입할텐데

이것도 마찬가지로 처음에는 spinlock으로 점유를 시도하다가, 안되면 futex_wait으로 OS 대기를 걸고, lock에 자리가 또 나면 spinlock으로 시도하는 그런 반복 로직이다.