개요
MCS lock (Mellor-Crummey and Scott lock)은 기본적인 spinlock기반의 lock을 per-CPU 구조의 Lock으로 옮긴것이다. 기존의 spinlock은 각각의 acquire마다 cache-line을 일치시키기 위한 cache-line bouncing이 발생한다. 이는 많은 contention이 일어나는 환경에서 큰 overhead을 일으킬 수 있다. 특히 Scalability가 지켜져야 하는 상황에서는 cache-line coherence 문제 덕분에 scalablility가 저하된다. 즉 MCS lock은 이런 spin-lock구현에서 global variable에 access해야 하는 상황을 극복하여 이러한 문제를 해결하였다.
방식
우선 MCS lock의 구현체는 다음과 같은 구조체를 가진다.
struct mcs_spinlock {
struct mcs_spinlock *next;
int locked; /* 1 if lock acquired */
};
- OP: 기본적인 동작은 mcs_lock의 locked를 계속해서 local 에서 살피면서 만약 true일경우는 spin을 아닐경우 critical section에 접근하는 것으로 구현된다.
- INIT: MCS_lock을 만드는 것은 이러한 구조체를 Init하는 것에서 부터 시작한다. MCS_lock의 INIT과정에서는 *next 필드가 NULL로 초기화 된다. 그후 unconditional atomic exchange로 *next field가 스스로의 mcs_spinlock 구조체를 가르키도록 한다.
mcs_spinlock(main, *next = cpu_1, locked = false) -> mcs_spinlock(cpu_1, *next = NULL, locked=false)
- ACQUIRE: 만약 두번째 CPU가 lock을 획득하려고 하는 경우 먼저 이 CPU는 mcs_spinlock의 main의 *next가 NULL인지 확인한다. 만약 NULL일 경우 mcs_spinlock의 *next를 스스로를 가르키도록 1과 같은 방식으로 수정하면 될것이고 아닐 경우 *next필드가 가르키고 있는 값을 스스로의 구조체 값으로 변경하고 locked 를 true로 바꾼다.
mcs_spinlock(main, *next = cpu_2, locked = false) -> mcs_spinlock(cpu_2, *next = NULL, locked = true) mcs_spinlock(cpu_1, *next = cpu_2, locked = false) -> mcs_spinlock(cpu_2, *next = NULL, locked = true)
- UNLOCK: unlock에서는 일단 스스로의 locked state를 보고 만약 true일 경우 누군가 lock을 acquire할려고 했다는 것임으로 *next필드가 가르키고 있는 cpu의 locked을 true에서 false로 바꾸고 (즉 다음 waiter의 상태를 unlock)하고 스스로를 deallocated한다.
- 즉 mcs_lock의 main구조체는 항상 *next필드로 이루어지는 queue의 tail을 가르키고있으며, 만약 mcs_lock을 획득하는 과정에서 tail이 NULL이면 그냥 스스로를 넣고 실행시키면 되고 아니면 tail의 *next필드를 수정하여 스스로를 tail에다가 insert하고 locked값이 true로 바뀔때까지 waiting하는 구조이다.
장단점
장점
- spin이 local variable을 확인하며 돌기 때문에 scalability을 지킬 수 있다.
- spin이 local varaible을 확인하며 돌기 때문에 cache line coherence overhead가 적다.
단점
- msc_lock은 memory allocation이 크다. 왜냐하면 *next필드가 이미 주소값 하나를 저장해야 하기 때문인데 따라서 mcs_lock을 size에 민감한 곳에는 사용할 수 없다. (예를 들어서 linux의 struct page에는 사용할 수 없다.)