11_Read/Write lock

코드

lock.h

// lock.h
class Lock
{
 enum : u32 {
  ACQUIRE_TIMEOUT_TICK = 10000, // MAX waitable tick
  MAX_SPIN_COUNT = 5000,
  WRITE_THREAD_MASK = 0xFFFF'0000,
  READ_THREAD_MASK = 0x0000'FFFF,
  EMPTY_FLAG = 0x0000'0000,
 };
public:
 void write_lock();
 void write_unlock();
 void read_lock();
 void read_unlock();

private:
 Atomic<u32> _lock_flag = EMPTY_FLAG;
 u16 _write_count = 0;
};

변수

• _lock_flag: 현재 lock의 대한 상태이다.
• 앞의 16 비트는 몇 번 스레드가 write lock을 소유하고 있는지에 대한 정보이다.
• 뒤의 16 비트는 read lock의 호출 횟수를 의미한다.

• _write_count: write_lock의 호출 횟수를 의미한다.

enum

• ACQUIRE_TIMEOUT_TICK: 해당 lock의 소유권을 가지기 위한 시간 제한이다.

• MAX_SPIN_COUNT: 해당 lock의 소유권을 가지기 위한 횟수 제한이다.

• WRITE_THREAD_MASK: _lock_flag에서 write lock을 한 스레드의 번호를 추출하기위한 mask이다.

• READ_THREAD_MASK: _lock_flag에서 read 횟수를 추출하기위한 mask이다.

• EMPTY_FLAG: 초기화 상태

lock.cpp

// lock.cpp
void Lock::write_lock()
{
 const u32 lock_thread_id = ( _lock_flag.load() & WRITE_THREAD_MASK ) >> 16;
 // same thread
 if (tls_thread_id == lock_thread_id) {
  _write_count++;
  return;
 }

 // any-threads not shared
 const i64 begin_tick = GetTickCount64();
 const u32 desired = ((tls_thread_id << 16) & WRITE_THREAD_MASK);
 while (true) {
  for (u32 spin_count = 0; spin_count < MAX_SPIN_COUNT; spin_count++) {
   u32 expected = EMPTY_FLAG;
   if (_lock_flag.compare_exchange_strong(expected, desired)) {
    _write_count++;
    return;
   }
  }

  if (::GetTickCount64() - begin_tick >= ACQUIRE_TIMEOUT_TICK)
   CRASH("LOCK TIMEOUT");

  this_thread::yield();
 }
}

write lock의 경우

1. 같은 스레드에서 write lock을 호출한 경우 write lock의 카운트를 늘려주고 바로 리턴을 해준다.

2. 같은 스레드가 아닐 경우, lock_flag가 EMPTY_FLAG가 될 때까지 반복문을 실행한다.

3. EMPTY_FLAG가 되었다면, Read와 Write가 모두 lock이 되지않은 상태이므로, lock을 소유하고 현재의 스레드 ID를 _lock_flag의 앞 16비트에 넣어준다.

4. 만약 시간이 너무 오래 걸린다면, dead_lock이나 하나의 쓰레드에서 lock을 너무 오래 잡아주고 있으므로 crash를 해준다.

void Lock::write_unlock()
{
 if ((_lock_flag.load() & READ_THREAD_MASK) != 0)
  CRASH("INVALID UNLOCK ORDER") // W->R (0), R -> W (x)

 const i32 lock_count = --_write_count;
 if (lock_count == 0) {
  _lock_flag.store(EMPTY_FLAG);
 }
}

1. 만약, write lock이 걸려있는 상태에서 read lock이 걸려있으면 순서 문제이므로 crash를 해준다.

2. write_lock을 감소시켜준다.

3. 더 이상 lock을 사용하지 않는다면 EMPTY_FLAG로 변경해준다.

void Lock::read_lock()
{
 // same thread
 const u32 lock_thread_id = (_lock_flag.load() & WRITE_THREAD_MASK) >> 16;
 if (tls_thread_id == lock_thread_id) {
  _lock_flag.fetch_add(1);
  return;
 }

 // any-threads not shared, add shared count
 const i64 begin_tick = GetTickCount64();
 while (true) {
  for (u32 spin_count = 0; spin_count < MAX_SPIN_COUNT; spin_count++) {
   u32 expected = (_lock_flag.load() & READ_THREAD_MASK);
   if (_lock_flag.compare_exchange_strong(expected, expected + 1)) return;
  }

  if (::GetTickCount64() - begin_tick >= ACQUIRE_TIMEOUT_TICK)
   CRASH("LOCK TIMEOUT");

  this_thread::yield();
 }
}

1. 같은 스레드에서 read lock을 호출한 경우 _lock_flag의 read lock의 카운트를 늘려주고 바로 리턴을 해준다.

2. _lock_flag에서 READ_THREAD_MASK를 and 연산을 해주면 0000'read의 값을 구할 수 있다.

3. 만약 _lock_flag가 0000'read 값과 같다면 write는 없고 read만 하고 있으므로 lock을 소유할 수 있다.

4. 만약 _lock_flag가 thId'read라면 어디선가 write를 하고 있다는 것이므로 lock을 가지지 못하도록한다.

void Lock::read_unlock()
{
 if ((_lock_flag.fetch_sub(1) & READ_THREAD_MASK) == 0) {
  CRASH("Multiple unlock");
 }
}