[운영체제] CAS 기반 SpinLock

 

개요

Spin Lock을 직접 구현하고 Mutex와 성능 차이를 체크해본다.

 

프로젝트 정보(Project Informaion)

CPU	Intel I7-6700 3.40Ghz 4코어 8스레드
OS	Windows 10
IDE	Visual Studio 2019 x86
Language	C++11
Sum	10000000

 

Spin Lock 이란

SpinLock이란 Busy-Waiting(바쁜 대기) 방식을 사용하는 Lock으로 Lock을 얻을 때까지 계속 루프를 돌면서 시도를 하는  Lock을 말한다. 

SpinLock은 문맥 교환(Context Switching)에 따른 오버헤드보다 대기(Busy-Waiting)에 따른 오버헤드가 더 적을 때 성능의 이점이 나타난다. 

 

CAS

SpinLock은 라이브러리를 제공하지 않기 때문에 CAS를 기반으로 해서 설계해야 한다. 여기서 CAS란 (Compare-And-Set)의 약자로 원자적으로 자료가 교환되는 하드웨어(기계어) 명령어이다. CAS를 구현하는 방법은 두 가지가 있는데 

Windows에서 제공하는 InterLockedCompareExchange()를 사용하던지 C++ 표준에서 제공하는 std::atomic_compare_exchange_strong()을 사용해야 한다.

 

C++ 표준 함수를 이용한 CAS

DWORD CSpinLock::CAS(volatile DWORD* target, int  new_value, int cmp) {
    DWORD originValue = *target;
    std::atomic_compare_exchange_strong(
        reinterpret_cast<volatile std::atomic_int* >(target), &cmp, new_value);
    return originValue;
}

 

Windows에서 제공하는 함수의 CAS

InterlockedCompareExchange(&state_, dwCurThrId, LOCK_AVAIL)

 

 

여기서는 C++ 표준의 함수가 아닌 Windows에서 제공하는 함수를 사용해서 진행한다.

 

Spin Lock - SpinWait

Spin Lock에 필요한 SpinWiat 구조체를 정의한다. 이 구조체는 SpinOnce()라는 멤버 함수를 가지는데 실제 이 함수가 

스핀을 통해서 스레드를 대기시키는 역할을 한다. 호출할 수 있는 한계치를 설정해 스핀 횟수가 그 값 이하일 동안은 

YieldProcessor()를 호출하고 그 이상일 경우에는 SwitchToThread() 나 Sleep()의 호출 빈도를 조절해 함수를 호출하도록 처리한다.

 

 

 int yieldSoFar = (count_ >= YIELD_THRESHOLD ? count_ - YIELD_THRESHOLD : count_);
 
            if ((yieldSoFar % SLEEP_1_TIMES) == SLEEP_0_TIMES - 1)
                Sleep(0);
            else if ((yieldSoFar % SLEEP_1_TIMES) == SLEEP_1_TIMES - 1)
                Sleep(1);
            else
                SwitchToThread();

YieldProcessor(), SwitchToThread(), Sleep()의 설명은 다음과 같다.

 

- YieldProcessor()

  YieldProcessor()는 함수가 아니라 매크로이며 C++ 내장 함수인 mm_pause를 호출하게 된다. mm_pause는 인텔 CPU

  명령어인 pause 어셈블리 코드로 대체된다. 이 명령어는 아무것도 하지 않는다는 의미인 NOP 명령과 비슷하며, 또한

  C++ 내장 함수 _nop()가 nop 어셈블리 코드를 지원한다. Pause를 실행하면 해당 스레드가 CPU에게 스핀 대기(Spin Wait)

 상태라는 것을 알려주어 CPU는 하이퍼 스레드에 존재하는 다른 논리적 프로세서가 자신의 작업을 수행할 수 있게 한다.

 

- SwitchToThread()

  이 함수는 자신을 호출한 스레드의 남은 타임 퀀텀(CPU 타임)을 포기시키고 다른 스레드에게 CPU를 넘겨준다. 

  즉 강제로 스레드의 문맥 전환을 유발하는 것이다. SwitchToThread는 자신을 호출한 스레드의 타임 슬라이스를

  다른 스레 드에게 양도해서 그 스레드를 실행 준비 상태로 들어가게 한다. 

 

- Sleep()

   SwitchToThread()는 무조건 문맥 전환을 시키지만 가능하면 그러지 않는 것이 더 좋다. 이를 위해 타임아웃 값을 0으로

    지정해 sleep 함수를 호출하면 자기와 같거나 자기보다 높은 우선순위를 가진 스레드가 없다면 문맥 전환을 하지 않는다.

 

 

 

Mutex Lock

Mutex란 C++ 11부터 포함된 표준 라이브러리에 있는 class이다. 

 

void CPerformanceComparison::SumByMutex()noexcept {
    for (unsigned int i = 0; i < MAX_LOOP; ++i) {
        std::lock_guard<mutex> lg(mutex_);
        sum_ += 1;
    }
}

 

std::lock_guard는 RALL 기반으로 스코프를 벗어나면 자동으로 unlock을 해주는 템플릿 기반 class이다.

 

성능 체크

 

테스트 방식은 동일한 조건으로 Sum을 계산하며 Sum을 시작하기 전과 후에 시간을 측정해서 얼마나 시간이 걸렸는지 확인한다.

 

 

Sum 10000000개의 해당하는 Core별 경과 시간은 다음과 같다.

단위는 초 단위이며 컴퓨터가 8 코어 이기 때문에 사실상 16부터는 의미가 크게 없는 수치이다. 그래도 짧은 시간 안에 연산을 하는 코드는 SpinLock의 성능이 더 높다는 것을 확인할 수 있다.

 

 

 

유의사항

* 해당 프로젝트는 예외 처리를 최소한으로 했기 때문에 버그가 있을 수 있습니다.

* 만약 이 블로그 글을 보고 잘못된 점이나 참고 가능한 것 등 공부가 가능한 게 있다면 댓글이나

   메일(SnowFleur0128@gmail.com)로 보내주시면 감사하겠습니다.

 

2020.12.07(수정)

기존 코드는 SPinLock을 100% 구현한 게 아니라서 다시 책을 참고하여 SpinWait을 넣었고 C++ 표준을 이용한 CAS가 아닌 Win에서 제공하는 함수를 이용해서 진행하였다.

 

 

출처 및 소스코드 링크

Git: github.com/SnowFleur/2020-Operator-System/tree/master/%EB%B3%91%ED%96%89%EC%84%B1(Parallelism)/Lock

 

RAII: [프로그래밍/Modern C++] - [C++] RAII(Resoucre Acquisition Is Initialization)

참고 책: 윈도우 시스템 프로그램을 구현하는 기술(한빛)

 

SRWLock:  [운영체제(Operator System)] - [운영체제] SRWLock