스케일러블 세마포

매니코어OS
이동: 둘러보기, 검색

응용의 스케일러빌러티를 위해서 많은 코어로 구성된 NUMA 시스템을 효율적으로 사용하였는데, 작업 및 데이타 배치( task placement, data sharding )등 다양한 기술이 실제로 적용되었다. 그러나 운영 체제 경우, OS의 여러 하위 시스템이 서로 상호 작용하고 데이터 구조를 공유하여 이러한 기술(data sharding 등)을 항상 적용하지 않았고, 결국 운영체제의 스케일러빌러티 문제를 야기하였다. 현재의 OS는 스핀 록(spinlock) 및 세마포(semaphore), 뮤텍스 (mutex)와 같은 다양한 동기화 프리미티브 도입을 통해 이 문제를 해결하려고 시도하지만, 스케일러빌러티 이슈는 해결하지 못하였다. 따라서 NUMA 시스템을 고려한 동기화 기법인 CST-lock를 연구하였다.

cstlock1.png

CST-lock의 특징으로 첫째 NUMA 구조를 인식하는 세마포, 뮤텍스 동기화 기법이다. 기존의 잠금 기법은 높은 경쟁를 위해 queue 기반 spinlock을 사용하여 캐시 라인 경합을 잘 처리하지만 캐시 라인 바운스(constantly transferred from one cache to the other)를 지원하지 못한다. 즉 NUMA 시스템에서 원격 소켓에서 원격 메모리 접근은 소캣 내에서 로켈 접근보다 최소 1.6배 느려 성능을 심각하게 저하 시킬 수 있다. 따라서 계층적인 잠금 구조로, 아래 그림과 같이 CPU 소켓마다 락 대기 자료구조를 두는 것이 특징이다. 소켓 내에서 잠금을 처리하여, 소켓 간 접근를 완화하였다.

두번째 특징은 memory-efficient 자료구조이다. 대부분의 계층적 잠금 기법은 큰 자료구조로 메모리를 많이 사용하게 된다. 이 메모리 팽창(memory bloat)는 시스템의 메모리 부족을 야기시켜 심각한 문제가 된다. 이것은 동기화 프리미티브가 메모리를 정적으로 할당할 때 더욱더 문제이다. 예를 들어, rwsem 구조에 16 바이트를 추가 한 후 XFS inode의 구조가 4 % 증가하면, 시스템에 캐시 된 수백만 개의 inode가 있을 수 있기 때문에 공간과 성능에 엄청난 영향을 미친다. 따라서 계층적 점금 자료구조를 NUMA 단위 구조로 동적으로 할당하여 메모리 팽창 문제를 피한다.

세번째 특징은 효과적인 경쟁 관리다. 세마포 등은 스핀락과 달리, lock 소유자가 lock를 해제하기 까지 sleep를 한다. 하지만 unlock 과정에서 쓰레드를 wakeup하는 오버헤드가 존재하다. 이를 개선하기 위해서 리눅스의 세마포 등 기법은 spin-then-park 방식을 사용하고 있다. 즉 sleep이전에 잠시 spin를 하면서 lock 해제를 기다리는 것이다. 그러나 시스템의 경쟁 상황을 파악하지 않고 이 방식이 적용되고 있다. 따라서, scheduling-aware하게 spin 또는 park를 결정하도록 한다.

마지막 특징은 wake-up 방식이다. 보통 lock 소유자는 대기자 리스트의 맨 처음 대기자에게 lock를 릴리스한다. 이 과정에서 대기자는 wake-up를 해야 하기 때문에 비효율적이다(보통 2,000-8,000 사이클). 따라서 CST-lock에서는 sleep한 대기자보다 spin하고 있는 대기자가 있다면, 아래 그림과 같이 먼저 lock를 spin하고 있는 대기자에게 릴리스하고 다른 대기자를 wake-up한다.

cstlock2.png

MOS_BENCH 결과, 아래 그림과 같이 기존 리눅스보다 많은 코어/많은 쓰레드에서 더욱 스케일러블한 성능을 보인다. 그리고 계층적 잠금 구조인 cohort lock과는 유사한 성능이지만 메모리를 더욱 효율적으로 사용함을 알 수 있다.

cstlock3.png

논문 :