문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 스레드]] == 개요 == 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의 구현체는 다음과 같은 구조체를 가진다. <syntaxhighlight lang=c> struct mcs_spinlock { struct mcs_spinlock *next; int locked; /* 1 if lock acquired */ }; </syntaxhighlight> * 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에는 사용할 수 없다.) == 같이 보기 == # [[qspinlock]] == 참고 == # https://lwn.net/Articles/590243/ # https://dl.acm.org/doi/10.1145/103727.103729 MCS lock 문서로 돌아갑니다.