아토믹으로 Lock-Free 자료구조 만들기

2022.07.03 - [언어/C++] - 아토믹 (Atomic, cpp17)

아토믹 (Atomic, cpp17)

 

Thread-Safe한 자료구조가 필요하다고 하자. mutex등을 이용해서 자료구조로의 접근을 제한하는 방식은 느리다. 이전 글에서 다룬 atomic을 이용하여 스핀 락을 만든다면 mutex보다 더 빠른 락을 만들 수 있다.

 

그러나 데이터의 읽기가 빈번하게 일어나는 자료구조라면 어떨까? 데이터를 읽을 때는 딱히 스레드의 동시 접근을 제한할 필요가 없으니 자료구조에 접근할때마다 스레드가 락을 취득하는 것은 비효율적이다. 

 

물론 이를 위한 Read-Write 사용할 수도 있지만 자료구조 자체에서 이러한 락을 지원해준다면 사용하는 입장에서 더 간편하게 쓸 수 있을 것이다.

 

이렇게 Thread-Safe하면서 Lock-Free인 자료구조가 물론 어디에선가 제공되겠지만 대충 이런 자료구조가 어떤식으로 동작하는지에 대한 이해를 위해 간단한 자료구조를 만들어 볼까 한다.

 

 

 

Non Thread Safe Stack

---

const int MAX_SIZE = 100000;

class NonSafeStack
{
public:
	int at(int idx)
	{
		return mNums[idx];
	}

	void push_back(int num)
	{
		++mIdx;
		mNums[mIdx] = num;
	}

	int size()
	{
		return mIdx+1;
	}
	
private :
	int mIdx = -1;
	array<int, MAX_SIZE> mNums;
};

간단하게 위와 같은 스택이 있다. push를 지원하며 at()을 통해 데이터의 랜덤 엑세스도 가능하다.

 

void push_half(NonSafeStack & stack)
{
	for (int i = 1; i <= MAX_SIZE/2; ++i)
		stack.push_back(i);
}

int main()
{
	NonSafeStack stack;
	thread thread1(push_half, ref(stack));
	thread thread2(push_half, ref(stack));

	thread1.join();
	thread2.join();

	cout << "stack size : " << stack.size() << endl;
}

이제 위 코드와 같이 스레드 두개를 만들어서 각각 스택에 5만개의 데이터를 넣었다. 

 

당연하게도 두 스레드가 동시에 stack의 mIdx에 접근할 것이기 때문에 stack의 사이즈는 10만이 되지 않을 것이다. 

 

 

 

Lock-Free Stack

---

Lock-Free 스택에서는 그냥 mIdx를 atomic으로 선언해주면 된다.

 

그 뒤 push_back() 메서드를 다음과 같이 수정했다.

 

void push_back(int num)
{
	//mIdx의 값이 1증가하면서, 증가하기 전의 값의 idx에 저장된다. (atomic)
	int idx = mIdx.fetch_add(1);	
	++idx;
	mNums[idx] = num;
}

 

결과는 당연히 10만으로 잘 나온다

 

 

다만 여기서도 문제가 한 가지 존재하는데,

 

int at(int idx)
{
	return mNums[idx];
}

 

위 메서드에서 스레드가 쓰레기 값을 읽을 수 있다는 점이다. 따라서 값이 valid한지를 검증하기 위한 또 다른 변수가 필요하다. 혹은, 각각의 data마다 atomic<bool> 변수를 추가해서 valid한지를 체크할 수도 있다.