Read-Write Lock

인프런에 있는 루키스님의 게임 서버 강의를 듣고 정리한 내용입니다.

Read-Write Lock

만약 멀티쓰레드 환경에서 공유 자원의 값을 읽는 작업이 95%이고 쓰는 작업이 5%라 해보자. 단순히 데이터를 읽는 작업을 상호배재적으로 할 필요는 없지만, 지금까지 배운 lock 방식으로는 어쩔 수 없이 읽기 작업에도 mutex lock을 걸어야 했다. Read-Write Lock은 이러한 상황에서 유용하게 쓰이는 락 방법으로, 쓰기 작업은 하나의 쓰레드만 가능하지만, 읽기 작업은 동시에 여러 쓰레드에서 가능하게 하게 한다.

Lock Flag

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

먼저 구현 방식을 간단히 살펴보면, 위와 같이 32bit의 lock flag를 이용한다. 상위 16bit는 write lock에 대한 정보인데, 만약 어떤 쓰레드가 읽기 작업을 하고 있다면 해당 쓰레드의 Thread ID가 들어간다. 하위 16bit는 읽기 작업을 하고 있는 쓰레드의 개수를 의미한다. Read Lock의 count를 추적하는 이유는 count가 0이 되어야 write lock을 걸 수 있기 때문이다.

enum : uint32
{
    ACQUIRE_TIMEOUT_TICK = 10000,
    MAX_SPIN_COUNT = 5000,
    WRITE_THREAD_MASK = 0xFFFF'0000,
    READ_COUNT_MASK = 0x0000'FFFF,
    EMPTY_FLAG = 0x0000'0000
};

또한 게임에서는 lock을 잠시 동안만 잡고 푸는 경우가 대부분이기 때문에 SpinLock 방식이 주로 사용된다. SpinLock 매커니즘은 Tick Count를 이용해 구현하고, Lock Flag는 미리 정의해놓은 Mask Flag와의 비트 연산을 통해 다루면 편하다.

정리하자면 새로 정의한 Lock 클래스의 구조는 다음과 같다. 이때 재귀적인 lock 사용을 대비하기 위해 writeCount 또한 추적한다. 이후에 예상하지 못한 컨텐츠들이 추가되면 이런 재귀적인 상황이 발생한다고 카더라.

class Lock
{
    enum : uint32
    {
        ACQUIRE_TIMEOUT_TICK = 10000,
        MAX_SPIN_COUNT = 5000,
        WRITE_THREAD_MASK = 0xFFFF'0000,
        READ_COUNT_MASK = 0x0000'FFFF,
        EMPTY_FLAG = 0x0000'0000
    };

public:
    void WriteLock(const char* name);
    void WriteUnlock(const char* name);
    void ReadLock(const char* name);
    void ReadUnlock(const char* name);

private:
    Atomic<uint32> _lockFlag = EMPTY_FLAG;
    uint16 _writeCount = 0;
};

Write Lcok

void Lock::WriteLock()
{
	const uint32 lockThreadId = (_lockFlag.load() & WRITE_THREAD_MASK) >> 16;
	if (LThreadId == lockThreadId)
	{
		_writeCount++;
		return;
	}

	const int64 beginTick = ::GetTickCount64();
	const uint32 desired = ((LThreadId << 16) & WRITE_THREAD_MASK);
	while (true)
	{
		for (uint32 spinCount = 0; spinCount < MAX_SPIN_COUNT; spinCount++)
		{
			uint32 expected = EMPTY_FLAG;
			if (_lockFlag.compare_exchange_strong(OUT expected, desired))
			{
				_writeCount++;
				return;
			}
		}

		if (::GetTickCount64() - beginTick >= ACQUIRE_TIMEOUT_TICK)
			CRASH("LOCK_TIMEOUT");

		this_thread::yield();
	}
}

동일한 쓰레드가 소유하고 있으면 무조건 통과

const uint32 lockThreadId = (_lockFlag.load() & WRITE_THREAD_MASK) >> 16;
if (LThreadId == lockThreadId)
{
    _writeCount++;
    return;
}

앞에서 이야기했듯이 동일한 쓰레드가 재귀적으로 writelock을 호출하면 writeCount를 증가시키고 통과시키면 된다. 이때 다른 쓰레드의 개입은 고려할 필요가 없으므로 굳이 atomic한 연산을 할 필요가 없다. 간단하게 ++로 구현이 가능하다.

const int64 beginTick = ::GetTickCount64();
const uint32 desired = ((LThreadId << 16) & WRITE_THREAD_MASK);
while (true)
{
    for (uint32 spinCount = 0; spinCount < MAX_SPIN_COUNT; spinCount++)
    {
        uint32 expected = EMPTY_FLAG;
        if (_lockFlag.compare_exchange_strong(OUT expected, desired))
        {
            _writeCount++;
            return;
        }
    }

    if (::GetTickCount64() - beginTick >= ACQUIRE_TIMEOUT_TICK)
        CRASH("LOCK_TIMEOUT");

    this_thread::yield();
}

SpinLcok의 작동 방식만 따로 빼서 살펴보자. 먼저 MAX_SPIN_COUNT 만큼만 while문을 돌며 경합을 한다. 만약 경합 결과 lock을 얻지 못했다면 yield를 호출해 다음 쓰레드에게 양보한다. 또한 같은 쓰레드가 경합에서 여러 번 지게되어 ACQUIRE_TIMEOUT_TICK을 초과한다면, Lock Timeout 크래쉬를 내도록 한다.
다음으로 현재 lockFlag와 Empty Flag를 비교하여 CAS 연산을 진행한다. 이때 desied flag가 empty flag이므로 다른 어떤 쓰레드가 읽기 작업을 수행 중이라면 조건문을 통과할 수 없다. 만약 조건문을 통과했다면 wirte flag 부분에 thread id를 넣어주고 리턴하면 된다.

Write Unlcok

void Lock::WriteUnlock()
{
if ((_lockFlag.load() & READ_COUNT_MASK) != 0)
    CRASH("INVALID_UNLOCK_ORDER");

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

참고로 위 Lock 클래스는 Write Lock을 잡고 있는 쓰레드가 Read Lock을 잡는 것이 가능한 정책을 사용한다(반대의 경우는 당연히 안됨). 따라서 read lock이 전부 풀리기 전까지 write lock이 풀리면 안되는데, 보험 차원에서 crash 매크로를 통해 이를 확인 할 수 있다..

Read Lock

void Lock::ReadLock()
{
	const uint32 lockThreadId = (_lockFlag.load() & WRITE_THREAD_MASK) >> 16;
	if (LThreadId == lockThreadId)
	{
		_lockFlag.fetch_add(1);
		return;
	}

	const int64 beginTick = ::GetTickCount64();
	while (true)
	{
		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() - beginTick >= ACQUIRE_TIMEOUT_TICK)
			CRASH("LOCK_TIMEOUT");

		this_thread::yield();
	}
}

const uint32 lockThreadId = (_lockFlag.load() & WRITE_THREAD_MASK) >> 16;
if (LThreadId == lockThreadId)
{
    _lockFlag.fetch_add(1);
    return;
}

먼저 위 코드는 Write Lock을 잡고 있는 쓰레드라면 CAS없이 단순하게 fetch_add로 무조건 통과시킨다는 것이다. 만약 어떤 쓰레드가 Write Lock을 잡고 있다면 lock 경합이 없는 것이 확실하므로, 가능한 이야기다.

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;
}

SpinLock 작동 방식은 Write Lock과 동일하므로 경합 부분만 살펴보자. 먼저 expected_flag가 뜻하는 것은 아무도 소유하고 있지 않아야 한다는 것이다(wirte_flag = 0). 따라서 _lockFlag의 CAS 조건문은 어떤 쓰레드가 Write Lock을 소유했거나, 다른 Read Lock에게 새치기를 당한 경우 실패하게 된다.

Read Unlock

void Lock::ReadUnlock()
{
    if ((_lockFlag.fetch_sub(1) & READ_COUNT_MASK) == 0)
        CRASH("MULTIPLE_UNLOCK");
}

Read Unlock같은 경우 그냥 Read Count만 1 감소시키면 되기 때문에 굉장히 간단하다. 혹시 모르니 1 빼기 전에 Read Count가 0 이었다면 crash 발생!

맨 위로 이동하기

Server 카테고리 내 다른 글 보러가기