[Thread] 스핀락(SpinLock)

 여러개의 스레드가 공유자원을 쓰고있을 때, 해당 공유자원이 있는 임계 영역(Critical Section)에 동시에 접근하게 되면, 공유 자원에 대한 접근이 어떤 순서로 이루어졌는지에 따라 실행 결과가 같지 않고 실행할때 마다 달라지는 경쟁 상태(Race Condition)이 발생하게 된다.

 따라서 해당 문제를 해결하기 위해 한 스레드가 임계 영역에 접근하면 다른 스레드들은 이 스레드가 이용하는 동안 해당 임계영역에 접근 할 수 없도록, 즉 두 개 이상의 프로세스가 동시에 임계영역에 접근하는 것을 막하야하는데, 이를 상호 배제(Mutual Exclusion)라고 한다. 상호배제는 Lock을 통해 달성할 수 있는데, 이 글에서는 Lock을 구현하는 여러가지 방법중 스핀락(SpinLock)에 대해서 알아보고자한다.

 스핀락을 통틀어 Lock에 대해서는 면접에서 자주 물어보는 것 중 하나이므로 제대로 이해하고 넘어가는게 좋겠다.

 

🔻스핀락(SpinLock)

 스핀락(SpinLock)은 이름 그대로, 다른 스레드가 Lock을 소유하고 있다면, 그 Lock이 반환될 떄까지 계속 확인하며 기다리는 방법이다. 즉, Lock을 획득할때 까지 해당 스레드가 빙빙 돌고있는(spin) 것이다.

  스핀락은 문맥교환(Context Switching)이 발생하지 않아 문맥교환의 들어가는 CPU의 부하를 줄일 수 있다는 장점이 있지만, Lock이 반환될 때까지 계속 확인하면서 루프를 돌고있는 Busy Waiting자체가 CPU를 쓸데없이 낭비한다는 단점이 있다. 만일 한 스레드가 Lock을 오랫동안 소유하고 있다면 기다리는 스레드들은 계속해서 무한루프만 돌고있는 상태이므로 굉장히 비효율적일 수 있다. 따라서 스핀락은 임계 영역이 짧거나, 빨리 처리가 가능한 경우에 사용하면 문맥교환비용을 아낄 수 있어서 효율적이다.

 다만 하나의 CPU나 하나의 코어만을 사용하는 경우에는 매우 비효율적이다. 만약 다른 스레드가 Lock을 가지고 있고 그 스레드가 Lock을 풀어 주려면 싱글 CPU 사용률 100%를 만드는 상황이 발생하므로 주의해야한다.

 

🔻스핀락(SpinLock)의 구현

 스핀락을 구현하기 위한 동작과정을 생각해보면,

1. 만약 Lock을 다른 스레드가 소유하고 있으면, 해당 Lock이 풀릴때 까지, 무한루프를 돈다.

2. 만약 Lock을 소유하고 있는 스레드가 없다면, 해당 Lock을 얻고, 이제는 소유중이라고 Lock의 상태를 변경한다.

 이 두가지 경우만 구현하면 되어서 매우 간단해보인다. 그래서 해당 알고리즘을 c++코드 그대로 옮겨보도록 하겠다.

//잘못된 코드

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

		_locked = true;
	}

	void unlock()
	{
		_locked = false;
	}

private:
	volatile bool _locked = false;
};

이렇게 나타내볼 수 있는데, 이를 실행해보면 당연히 제대로 동작하지 않는다!

 lock쪽 함수를 살펴보면 _locked가 false가 되기전까지 의미없는 반복문을 돌다가 false가 되면 반복문을 나오고 lock을 얻었으니 _locked를 다시 true로 해주는 모습이다.

 그런데 만약에 반복문을 나오고 _locked = true로 바꾸기 전에, 즉 loop은 끝났지만 _locked = false인 상황이 중간에 존재한다. 이 상황에서 다른 스레드가 "_locked = false이니까 나도 반복문 끝내야지"하고 반복문을 끝내는 상황이 발생할 수 있다.

 이렇게되면 동시에 두개의 스레드가 Lock을 얻게되므로 Mutual Exclusive를 달성하지 못하고 Lock으로서의 기능을 하지 못하게된다. 따라서 실행해보면 Lock의 기능이 제대로 수행되지 않을 것이다.

 이러한 문제가 발생한 이유는 _locked가 false인지 확인하고 false면 루프를 나와서 true로 바꾸는 이 일련의 과정이  "Atomic"하게 이루어지지 않았기때문에 발생한 일이다. 그러면 해당 코드를 어떻게 수정하면 Atomic하게 바꿀 수 있을까.

 

 우리는 여기서 CAS(Compare-And-Swap)연산을 사용할 수 있다. 이 연산은 특정 메모리위치의 값이 주어진 값과 동일하다면 해당 메모리 주소를 새로운 값으로 대체해주는 연산인데, 이 연산이 atomic하게 이루어진다.

CAS의 의사코드를 C++로 나타내어보면,

bool expected = false;
bool desired = true;
//cas (compare-and-swap)
if (_locked == expected)
{
	expected = _locked;
	_locked = desired;
	return true;
}
else
{
	expected = _locked;
	return false;
}

 여기서 expected는 비교하는 값, desired는 만약 동일하다면 새로 교체할 값을 의미한다. _locked와 expected값이 같다면 _locked값을 desired값으로 교체하고 교체가 성공했다는 결과를 반환한다. 다르면 교체가 실패했다는 결과를 반환한다.

 그런데 이과정이 Atomic하게 일어난다는 것이다. 따라서 위의 문제를 차단하는 효과를 얻을 수 있다.

 

그러면 이 CAS를 C++에서는 어떻게 사용할 수 있을까?

C++11부터 지원하는 <atomic>라이브러리를 이용하여 사용가능하다.

#include <atomic>
class SpinLock
{
public:
	void lock()
	{
		bool expected = false;
		bool desired = true;
		while (_locked.compare_exchange_strong(expected, desired) == false)
		{
			expected = false;
		}
	}

	void unlock()
	{
		_locked.store(false);
	}

private:
	atomic<bool> _locked = false;
};

 이렇게 _locked변수를 atomic<bool> 클래스 타입으로 설정해주고, compare_exchange_strong이라는 함수가 해당 클래스에 구현되어있는데 이것이 CAS연산을 해주는 함수이다. 이렇게 해주면 _locked가 false일때 루프를 벗어나고 _locked를 true로 바꿔주는 일련의 과정이 atomic하게 수행되므로 스레드간의 race condition을 해결할 수 있게되었다.

 

while문안에 expected=false로 설정해주는 이유는

해당 함수의 선언부를 살펴보면 expected가 레퍼런스타입으로 받아오기 때문에 true로 바뀔 수 있으니 false로 계속해서 설정해주는 것이다.

 

🔻결과확인

이렇게 SpinLock을 구현하였으므로 잘 동작하는 지 확인해보도록하자.

int32 sum = 0;
SpinLock s;

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

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

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

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

	cout << sum << endl;
}

Add함수는 sum값을 100000번 더하는 함수이고, Sub함수는 sum을 100000번 빼는 함수이다. 이를 쓰레드 두개를 만들어 각각 동시에 실행해보자. 만약 Lock이 잘 수행된다면 결과값은 0이 나올것이고 잘 구현되지 않았다면 실행할때마다 다른 값이 나올 것이다.

실행결과 0으로 올바른 값이 잘 나오는 것을 확인할 수 있었다.

 

🔻마치며

 SpinLock을 구현해보면서 여러가지 생각해볼 거리들이 많았던 것 같다. 작년에 운영체제에서 배운내용들이 나오면서 다시한번 운영체제의 중요성에 대해 생각해볼 수 있었고, SpinLock의 경우 면접에서도 단골질문이라고 하니 제대로 익혀두는게 좋을것 같다.