[C++/Game Server] Reader-Writer Lock

Reader-Writer Lock

• 32비트 int형을 사용하여 상위 16비트를 Write 소유 스레드 ID로, 하위 16비트를 Read 카운트로 사용하는 RW SpinLock
• Mutex를 사용하지 않고 RW Lock을 직접 구현하는 이유
  • 재귀적으로 lock을 사용하기 어려움
    • Recursive Lock을 따로 사용해야 함
  • 상호배타적인 특성이 필요한 상황에서 사용하고자 함
    • 보통 고정되어 있는 보상이나 고정된 데이터를 변경해야 하는 상황에서 일반 lock을 사용하기에 아까움
    • ex) 99.9999% 일정한 보상 아이템을 변경해야 하는 0.0001%의 상황
• Write Count와 Read Count를 사용하여 Readers-Writers Problem 완화

[OS] Synchronization II

 

Lock.h (Lock 클래스 정의)

/*-----------------
	RW SpinLock
------------------*/

/*
[WWWWWWWW][WWWWWWWW][RRRRRRRR][RRRRRRRR]
W: WriteFlag (Excusive Lock Owner ThreadId)
R: ReadFlag (Shared Lock Count)
*/

class Lock
{
	enum :uint32
	{
		ACQUIRE_TIMEOUT_TIC = 10'000, 		// 최대로 기다려줄 틱 (10초)
		MAX_SPIN_COUNT = 5'000, 			// 스핀 카운트를 최대 몇번 돌 것인지
		WRITE_THREAD_MASK = 0XFFFF'0000, 	// 상위 16비트를 뽑아오기 위한 마스크
		READ_COUNT_MASK = 0X0000'FFFF, 		// 하위 16비트를 뽑아오기 위한 마스크
		EMPTY_FLAG = 0X0000'0000			// 비어있는 32비트를 나타냄
	};
public:
	void WriteLock();
	void WriteUnlock();
	void ReadLock();
	void ReadUnlock();

private:
	Atomic<uint32> _lockFlag = EMPTY_FLAG;

	uint16 _writeCount = 0;
};

 

Lock.cpp (Lock 클래스 구현)

#include "pch.h"
#include "Lock.h"
#include "CoreTls.h"

void Lock::WriteLock()
{
	// 재귀적으로 동일한 스레드가 이 락을 소유하고 있다면 무조건 성공하게끔
	const uint32 lockThreadId = (_lockFlag.load() & WRITE_THREAD_MASK >> 16);
	if (lockThreadId == LThreadId)
	{
		_writeCount++;
		return;
	}

	// 아무도 소유(Write) 및 공유(Read)하고 있지 않을 때, 경합해서 소유권을 얻음
	const int64 beingTick = ::GetTickCount64(); // 시작 tick
	const uint32 desired = ((LThreadId << 16) & WRITE_THREAD_MASK);
	while (true)
	{
		for (uint32 spinCount = 0; spinCount < MAX_SPIN_COUNT; spinCount++)
		{
			uint32 expected = EMPTY_FLAG; // Write, Read 모두 비어있어야 lock 획득
			if (_lockFlag.compare_exchange_strong(OUT expected, desired)) {
				_writeCount++;
				return;
			}
		}
        // 시간을 너무 많이 소비하면 CRASH 유도
		if (::GetTickCount64() - beingTick >= ACQUIRE_TIMEOUT_TIC)
			CRASH("WRITE_LOCK_TIMEOUT");
		
		this_thread::yield();
	}
}

void Lock::WriteUnlock()
{
	// Read Count 다 풀기 전에는 WriteUnlock 불가능
	if ((_lockFlag.load() & READ_COUNT_MASK) != 0)
		CRASH("INVALID_UNLOCK_ORDER");

	const int32 lockCount = --_writeCount;
	if (lockCount == 0)
		_lockFlag.store(EMPTY_FLAG);
}

void Lock::ReadLock()
{
	// 동일한 스레드가 소유하고 있다면 무조건 성공 (W->R 허용이므로)
	const uint32 lockThreadId = (_lockFlag.load() & WRITE_THREAD_MASK >> 16);
	if (lockThreadId == LThreadId)
	{
		_lockFlag.fetch_add(1);
		return;
	}

	// 아무도 소유하고 있지 않을 때 경합해서 공유 카운트(R_L)을 올림
	const int64 beingTick = ::GetTickCount64();

	while (1)
	{
		for (uint32 spinCount = 0; spinCount < MAX_SPIN_COUNT; spinCount++)
		{
			uint32 expected = (_lockFlag.load() & READ_COUNT_MASK);
			if (_lockFlag.compare_exchange_strong(OUT expected, expected + 1))
				return;
		}
		if (::GetTickCount64() - beingTick >= ACQUIRE_TIMEOUT_TIC)
			CRASH("READ_LOCK_TIMEOUT");

		this_thread::yield();
	}
}

void Lock::ReadUnlock()
{
	// Read Count 1 감소 & Read Count가 음수로 내려가면 CRASH 유도
	if ((_lockFlag.fetch_sub(1) & READ_COUNT_MASK) == 0)
		CRASH("MULTIPLE_UNLOCK");
}

• 메모리 구조
  • Write Flag(16-31 bits): 현재 write 독점권을 가진 스레드의 ID 저장
  • Read Flag(0-15 bits): 현재 read 공유권을 가진 스레드들의 개수 저장
• 재귀적 lock(W → W)과 lock 승계(W → R)가 가능하도록 설계
  • W → W (재귀 허용): _writeCount를 통해 동일 스레드가 여러 번 WriteLock을 호출해도 데드락에 빠지지 않음
  • W → R (허용): 쓰기 권한을 가진 스레드가 읽기 권한도 가질 수 있음
    
    • 단, 해당 스레드가 진행 중인 Read 작업이 모두 끝나기 전(ReadCount가 0이 되기 전)에는 WriteUnlock 불가능
  • R → W (불가): 읽기 권한만 가진 상태에서 쓰기 권한으로 승격하려 하면 데드락을 방지하기 위해 로직상 차단
• SpinLock
  • MAX_SPIN_COUNT만큼 루프를 돌며 CAS를 시도하며 유저 모드에서 최대한 해결하려 함
  • 실패 시 this_thread::yield()를 통해 커널 모드로의 전환(Context Switching)을 유도하여 CPU 자원 낭비를 줄임

 

LockGuard 구현 및 사용

• 사용하기 편하게 LockGuard 클래스 및 매크로를 생성하여 사용

 

Lock.h (LockGuard Class)

/*----------------
	LockGuards
----------------*/

class ReadLockGuard
{
public:
	ReadLockGuard(Lock& lock) :_lock(lock) { _lock.ReadLock(); }
	~ReadLockGuard() { _lock.ReadUnlock(); }

private:
	Lock& _lock;
};

class WriteLockGuard
{
public:
	WriteLockGuard(Lock& lock) :_lock(lock) { _lock.WriteLock(); }
	~WriteLockGuard() { _lock.WriteUnlock(); }

private:
	Lock& _lock;
};

 

CoreMacro.h (LockGuard 매크로 정의)

/*----------------
	Lock
----------------*/

#define USE_MANY_LOCKS(count)	Lock _locks[count];
#define USE_LOCK				USE_MANY_LOCKS(1)
#define READ_LOCK_IDX(idx)		ReadLockGuard readLockGuard_##idx(_locks[idx]); // ##idx가 idx로 치환됨 (readLockGuard_1, readLockGuard_2 ..)
#define READ_LOCK				READ_LOCK_IDX(0)
#define WRITE_LOCK_IDX(idx)		WriteLockGuard writeLockGuard_##idx(_locks[idx]); // ##idx가 idx로 치환됨 (writeLockGuard_1, writeLockGuard_2 ..)
#define WRITE_LOCK				WRITE_LOCK_IDX(0)

 

GameServer.cpp (Main)

#include "pch.h"
#include <iostream>
#include "CorePch.h"
#include <atomic>
#include <mutex>
#include <Windows.h>
#include <future>
#include "ThreadManager.h"
#include <chrono>

class TestLock
{
	USE_LOCK;

public:
	int32 TestRead()
	{
		READ_LOCK;

		if (_queue.empty())
			return -1;
		return _queue.front();
	}

	void TestPush()
	{
		WRITE_LOCK;

		_queue.push(rand() % 100);
	}

	void TestPop()
	{
		WRITE_LOCK;

		/*
		한 스레드가 너무 오래 lock을 잡고 있는 경우(현재 10초) CRASH
		while (1)
		{
		}*/

		if (_queue.empty() == false)
			_queue.pop();
	}

private:
	queue<int32> _queue;
};

TestLock testLock; 

void ThreadWrite()
{
	while (1)
	{
		cout << "WRITE" << endl;
		testLock.TestPush();
		this_thread::sleep_for(1ms);
		testLock.TestPop();
		cout << "Write" << endl;
	}
}

void ThreadRead()
{
	while (1)
	{
		int32 value = testLock.TestRead();
		cout << "Read" << endl;
		this_thread::sleep_for(1ms);
	}
}

int main()
{
	for (int32 i = 0; i < 2; i++)
	{
		GThreadManager->Launch(ThreadWrite);
	}

	for (int32 i = 0; i < 5; i++)
	{
		GThreadManager->Launch(ThreadRead);
	}
	
	return 0;
}

• 다음과 같이 main을 구성하면 Write 스레드 2개와 Read 스레드 5개가 적절하게 lock을 분배하며 제 역할을 하는 것을 볼 수 있음
• Lock을 잡고 무한 반복을 돌리면 한 스레드가 lock을 오래 잡는 상황을 발생시켜 CRASH를 유도하는 것을 확인 가능