ReadWrite Lock

필요성

어떤 공유 데이터를 참조하는 여러 쓰레드가 있다고 가정하자.

이 쓰레드들은 평상시에는 이 공유 데이터를 읽기만 한다. 

그런데 아주 드문 경우에, 예를 들면 대략 1주일에 한 번 정도 이 공유 데이터를 수정하는 일이 벌어진다고 해보자.

 

사실 모든 쓰레드가 읽기만 한다면 Lock을 해줄 필요가 없다. Lock이 필요한 이유는 데이터 수정이 일어났을 때 쓰레드가 잘못 된 데이터를 읽게 될 가능성이 있기 때문이다. 그런데 위의 경우에서 1주일에 한 번 있는 데이터 수정 때문에 모든 읽기 작업에도 mutex를 사용해 Lock을 걸자니 매우 비효율적이라는 생각이 든다.

 

이런 경우 ReadWriteLock을 사용한다.

---

사용방식

ReadWriteLock은 ReadLock과 WriteLock으로 나누어진다. ReadLock은 공유 데이터를 읽을 때, WriteLock은 공유 데이터를 쓸 때 사용한다.  사용 코드를 먼저 보자. 대충 Lock과 LockGuard 처럼 사용하면 된다.

#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]);
#define READ_LOCK				READ_LOCK_IDX(0)
#define WRITE_LOCK_IDX(idx)		WriteLockGuard writeLockGuard_##idx(_locks[idx]);
#define WRITE_LOCK				WRITE_LOCK_IDX(0)

class TestLock
{
	USE_LOCK;
public :
	int32 TestRead()
	{
		READ_LOCK;
		if (_que.empty() == false)
		{
			return _que.front();
		}
		else
		{
			return -1;
		}
	}
	void TestPush()
	{
		WRITE_LOCK;
		_que.push(1);
	}
	void TestPop()
	{
		WRITE_LOCK;
		if (_que.empty() == false)
		{
			_que.pop();
		}
	}
private:
	queue<int32> _que;
};

TestLock testLock;
void ThreadWrite()
{
	while (true)
	{
		testLock.TestPush();
		this_thread::sleep_for(1ms);
	}
}
void ThreadRead()
{
	while (true)
	{
		int32 value = testLock.TestRead();
		cout << value<< 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);
	}
	GThreadManager->Join();
}

---

작동방식

평소에 읽기 작업만 할 때에는 바로 통과시켜주고, 가끔 쓰기작업이 생기면 다른 스레드의 읽기, 쓰기를 막아야한다.

그러려면 기본적으로 다음과 같은 원칙을 생각해볼 수 있다.

• Read Lock : read lock 중일 때에는 write lock 요청은 대기시킨다. read lock은 허용한다.
• Write Lock : write lock 중일 때에는 write lock도, read lock도 허용하지 않는다. 

그런데 위와 같은 조건에서 다음과 같은 사건이 발생했다고 생각해보자.

1. 쓰레드1이 Write Lock을 획득했다.
2. 쓰레드1이 다시 Write Lock(Read Lock) 요청을 했다. (재귀 락)
3. 이미 자기 자신에 의해 write lock이 걸려있었기 때문에 스레드 1은 대기상태에 빠졌다.
4. 그런데 자기 자신이 걸었던 write lock이 풀리려면 대기상태가 해제되어야 한다.

이러한 상황을 재귀 락이라고 한다. 이러면 데드 락이 발생된다. 따라서 원칙을 다음과 같이 수정한다.

• Read Lock : read lock 중일 때에는 write lock 요청은 대기시킨다. read lock은 허용한다.
• Write Lock : write lock 중일 때에는 자기 자신을 제외한 쓰레드의 write lock과 read lock을 허용하지 않는다. 

그러면 write lock 중에 read를 할 수 있다는 말인데, 뭔가 이상하다고 생각될 수 있다. 그러나 사실 자기 자신이 wirte lock중일 때 자기 자신이 read lock하는건 사실상 싱글 스레드와 똑같은 상황이다. 그러므로 문제되지 않는다.

그렇다면 read lock 중에 자기 자신이 write lock 하는 것도 싱글 스레드와 똑같으니 괜찮을까? 라는 생각도 들 수 있다. 하지만 이것은 문제가 될 수 있다. 아니 사실 문제가 될 수 있다기 보다는 상황이 이상하다. 다음 사건을 보자.

1. 쓰레드 1, 2, 3이 어떤 공유 자원에 대해 Read Lock을 걸어놓았다.
2. 쓰레드 1이 이 공유 자원에 대해 Write Lock을 걸려고 한다. 

이런 상황에서 쓰레드 1 입장에선 싱글 스레드와 같으니 상관 없다고 치지만, 쓰레드 2, 3 입장에선 읽기 중에 다른 쓰레드가 write lock을 걸려고 하는 상황이니 난감하다. 그러면 쓰레드1만 읽고있는 상황에서만 허용하면 되지 않을까? 라고 생각하고 보니, 쓰레드 1만 읽고있는지 아닌지 알려면 읽고있는 모든 쓰레드의 id를 기억해야만 한다. 하지만 이는 꽤나 비효율적이라고 생각되므로 그렇게 하지 않겠다.

 

---

구현

현재 공유 변수에 쓰기 작업을 하고있는 스레드의 ID와 읽기 작업을 하고있는 스레드의 수를 하나의 _lockFlag변수로 관리한다. _lockFlag 변수는 32비트 정수형으로 상위 16비트는 쓰기 중인 스레드의 ID를, 하위 16비트는 읽기 중인 스레드의 개수를 저장한다.

그리고 원래는 하나의 쓰레드만 write할 수 있지만, 재귀 락의 경우를 생각해 _writeCount 변수를 두어 중첩 횟수를 관리한다.

헤더파일을 보자.

class Lock
{
	enum : uint32
	{
		EMPTY_FLAG = 0x00000000,
		WRITE_THREAD_MASK = 0xFFFF0000,
		READ_COUNT_MASK = 0x0000FFFF,
		ACQUIRE_TIMEOUT_TICK = 10000,
		MAX_SPIN_COUNT = 5000
	};
public:
	void WriteLock();
	void WriteUnlock();
	void ReadLock();
	void ReadUnlock();
private:
	atomic<uint32> _lockFlag = EMPTY_FLAG;
	uint16 _writeCount = 0; //중첩 writeLock 추적용
};

enum 선언의 요소들의 의미를 알아보자.

• EMPTY_FLAG : 쓰고있는 스레드도, 읽고있는 스레드도 없는 상태를 나타낸다.
• WRITE_THREAD_MASK : _lockFlag와 & 연산 시 쓰고 있는 스레드의 ID를 추출할 수 있다,
• READ_COUNT_MASK : _lockFlag와 & 연산 시 읽고 있는 스레드의 수를 추출할 수 있다,
• ACQUIRE_TIMEOUT_TICK : lock 대기 시 최대 대기시간을 의미한다. 이 시간이 넘어가면 Crash한다.
• MAX_SPIN_COUNT : spin lock 시 최대 spin 횟수를 의미한다. 최대 spin횟수를 모두 채우면 yield를 통해 다른 스레드에게 점유를 넘긴다.

각 함수 구현을 살펴보자.

//다른 스레드의 writelcok은 막고, 같은 스레드의 writelock은 허용
void Lock::WriteLock()
{
	//같은 스레드일 경우 wirtecount 증가
	const uint32 threadId = _lockFlag.load() & WRITE_THREAD_MASK >> 16;
	if (LThreadId == threadId)
	{
		++_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;
			//lockFlag가 EMPTY_FLAG일 때까지 대기 -> write중인 스레드도 없고 read중인 스레드도 없는 상태.
			//아무도 없으면 자신의 ID를 넣음.
			if (_lockFlag.compare_exchange_strong(OUT expected, desired))
			{
				++_writeCount;
				return;
			}
		}
		if (GetTickCount64() - beginTick >= ACQUIRE_TIMEOUT_TICK)
		{
			CRASH("LOCK_TIMEOUT");
		}

		this_thread::yield();
	}
}

void Lock::WriteUnlock()
{
	//readLock이 다 풀려야 writeunlock 가능.
	if ((_lockFlag.load() & READ_COUNT_MASK) != 0)
	{
		CRASH("INVALID_UNLOCK_ORDER");
	}
	const int32 lockCount = --_writeCount;
	if (lockCount == 0)
	{
		_lockFlag.store(EMPTY_FLAG);
	}
}
//읽을 떄 자신 말고는 아무도 wrieteLock 중이지 않아야 함. 
void Lock::ReadLock()
{
	//같은 스레드가 쓰기 중일 경우 readcount 증가
	const uint32 threadId = _lockFlag.load() & WRITE_THREAD_MASK >> 16;
	if (LThreadId == threadId)
	{
		_lockFlag.fetch_add(1);
		return;
	}

	const int64 beginTick = GetTickCount64();
	while (true)
	{
		for (uint32 spinCount = 0; spinCount < MAX_SPIN_COUNT; spinCount++)
		{
			//쓰고있는 스레드가 없을 때 
			uint32 expected = _lockFlag & 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();
	}
}

void Lock::ReadUnlock()
{
	if ((_lockFlag.fetch_sub(1) & READ_COUNT_MASK) == 0)//fetch_sub는 계산 이전 값을 반환하기 때문에 0이면 이상함
	{
		CRASH("MULTIPLE_UNLOCK");
	}
}