SpinLock

면접에서 Spin lock을 구현하라는 요청을 많이 하는데, spin lock 구현을 보고 멀티쓰레드 이해도를 확인할 수 있기 때문이다.

 

보통 구현하라고 하면 다음과 같은 코드를 짠다.

class SpinLock
{
public:
	void lock()
	{
		while (_locked)
		{

		}
		_locked = true;
	}

	void unlock()
	{
		_locked = false;
	}

private:
	bool _locked = false;
};

int32 sum = 0;
mutex m;
SpinLock spinLock;

void Add()
{
	for (int32 i = 0; i < 10'000; i++)
	{
		lock_guard<SpinLock> guard(spinLock);
		sum++;
	}
}

void Sub()
{
	for (int32 i = 0; i < 10'000; i++)
	{
		lock_guard<SpinLock> guard(spinLock);
		sum--;
	}
}

int main()
{
	std::thread t1(Add);
	std::thread t2(Sub);

	t1.join();
	t2.join();

	cout << sum << endl;
}

하지만 결과는 0이 아닌 값이 나온다. 틀린 구현이다.

 

먼저 volatile 키워드를 알아보자. volatile은 기타 언어와 다르게 c++에서는 컴파일러 최적화를 하지 말아달라는 키워드이다.

디스어셈블리 창을 보면 volatile키워드가 있을 때, 컴파일러 최적화가 이뤄지지 않는 것을 볼 수 있다.

 

00007FF7B5EB1030  xchg        ax,ax  
	bool flag = true;
	while (flag)
00007FF7B5EB1032  jmp         main+2h (07FF7B5EB1032h)

 

	volatile bool flag = true;
00007FF6F4BE1048  mov         byte ptr [rsp+30h],1  
00007FF6F4BE104D  nop         dword ptr [rax]  
	while (flag)
00007FF6F4BE1050  movzx       eax,byte ptr [flag]  
00007FF6F4BE1055  jmp         main+20h (07FF6F4BE1050h)

 

하지만 spin lock이 제대로 작동하지 않은 이유가 이 때문만은 아니다. 멤버변수 _locked에 volatile키워드를 추가해도 최종 값 0이 나오지 않는다.

 

이유는 _locked값을 읽는 부분과 _locked값을 쓰는 부분이 분리되어 있어 아래 그림 처럼 lock을 함께 얻는 상황이 발생하기 때문이다.

 

 

 

제대로 동작하게 하기 위해 CAS(Compare-And-Swap)을 이용한다. c++에선 atomic의 compare_exchange_strong함수가 이를 지원한다. _locked를 atomic<bool> 타입으로 바꾼다.

// CAS (Compare - And - Swap)
bool expected = false;
bool desired = true;

_locked.compare_exchange_strong(expected, desired);

// CAS 의사코드
if (_locked == expected)
{
	expected = _locked;
	_locked = desired;
	return true;
}
else
{
	expected = _locked;
	return false;
}

_locked가 expected인지 확인하고 그렇다면 _locked를 desired로 세팅하고 true를 리턴한다.

그렇지 않으면 false를 리턴한다. 해당 과정이 원자적으로 이뤄진다.

 

while (_locked.compare_exchange_strong(expected, desired) == false)
{
	expected = false;
}

 

 

따라서 위와 같이 무한 반복을 하면서 값을 체크하면 되는데 expected를 레퍼런스로 받기 때문에 lock획득에 실패하면 expected값을 원래대로 돌려놔야한다.

 

spin lock의 장점은 커널모드로 컨텍스트 스위칭 하지 않기 때문에 금방 획득할 것으로 예상되는 lock을 얻기에 효과적이다. 하지만 lock획득을 무한히 요청하기 때문에 cpu 점유율이 올라 갈 수 있다.