ReaderWriterLock 구현
저번 시간에 배운 ReaderWriterLockSlim을 Interlocked을 이용하여 구현해보는 연습을 해보자.
재귀적 락(Lock을 건 상태에서 Lock을 거는 것)은 Writer->Reader, Writer->Writer만 허용된다.
먼저 WriterLock에 대해 알아보자
class Lock
{
const int EMPTY_FLAG = 0x00000000;
const int WRITE_MASK = 0x7FFF0000;
const int READ_MASK = 0x0000FFFF;
const int MAX_SPIN_COUNT = 5000;
// [Unused(1bit)] [WriteThreadId(15bits)] [ReadCount(16bits)]
int _flag = EMPTY_FLAG;
int _writeCount = 0;
public void WriteLock()
{
// 동일 쓰레드가 WriteLock을 이미 획득하고 있는지 확인
int lockThreadId = (_flag & WRITE_MASK) >> 16;
if(Thread.CurrentThread.ManagedThreadId == lockThreadId)
{
_writeCount++;
return;
}
// 아무도 WriteLock or ReadLock을 획득하고 있지 않을 때
// 경쟁해서 소유권을 얻는다.
while (true)
{
int desired = (Thread.CurrentThread.ManagedThreadId << 16) & WRITE_MASK;
for (int i =0; i < MAX_SPIN_COUNT; i++)
{
if(Interlocked.CompareExchange(ref _flag, desired, EMPTY_FLAG) == EMPTY_FLAG)
{
_writeCount = 1;
return;
}
}
Thread.Yield();
}
}
public void WriteUnlock()
{
_writeCount--;
if(_writeCount == 0)
Interlocked.Exchange(ref _flag, EMPTY_FLAG); // 원자성 보장
}
-
while 문 안을 먼저 살펴보자.
[Unused(1bit)][WriteThreadId(15bits)] [ReadCount(16bits)] 에 입각하여
desired 변수는 Thread.CurrentThread.ManagerThreadId를 16비트 옮겨서 WriteThreadId(15bits) 영역으로 이동시킨 것이다.
이때 _flag가 어떤 값도 할당받지 않은 초기상태(EMPTY_FLAG)이면 _flag에 desired를 원자성을 보장한 상태에서 대입한다.
만약에 _flag가 EMPTY_FLAG와 동일하여 _flag에 desired 값이 대입되면, 다른 쓰레드들은 if문을 통과하여 WriterLock을 return 할 수 없게 된다.
즉, MAX_SPIN_COUNT(5000) 만큼 기다렸다가 양보를 받아야한다.
상호배제를 위와 같은 방식으로 구현하였다.
-
재귀적 락 구현
lockThreadId는 _flag에서 ThreadId를 추출한 것이다.
그 ThreadId가 Thread.CurrentThread.ManagerThreadId와 동일하다면 _writeCount를 1 증가시키고 return으로 WriterLock을 종료한다.
이런 식으로 동일 쓰레드에서는 WriterLock 안에서 WriterLock을 걸어주는 것을 허용한다.
-
Unlock
_증가시켰던 _writeCount를 다시 1 감소시킨다. 걸어주었던 Lock 만큼 Unlock을 하기 위함이다.
그리고 _flag에 EMPTY_FLAG를 대입하여 다른 쓰레드가 WriterLock을 할 수 있도록 허용해준다.
public void ReadLock() // 상호 베타적인 Lock이 아니다.
{
int lockThreadId = (_flag & WRITE_MASK) >> 16;
if(Thread.CurrentThread.ManagedThreadId == lockThreadId)
{
Interlocked.Increment(ref _flag);
return;
}
while (true)
{
for (int i = 0; i < MAX_SPIN_COUNT; i++)
{
int expected = _flag & READ_MASK;
// 실패조건 1. WriteLock이 걸려 있을 때
// 실패조건 2. 경쟁 시 (경합 시) 다른 쓰레드가 선수 쳤을 때
if (Interlocked.CompareExchange(ref _flag, expected + 1, expected) == expected)
{
return;
}
}
Thread.Yield();
}
}
public void ReadUnlock()
{
Interlocked.Decrement(ref _flag);
}
}- ReadLock도 while 문을 먼저 보자.
마찬가지로, [Unused(1bit)][WriteThreadId(15bits)] [ReadCount(16bits)] 에 입각하여
expected에 _flag에 READ_MASK로 & 연산을 한 값을 대입하여, 만약에 _flag가 WriterLock을 걸린 지를 확인한다.
만약에 WriterLock이 안 걸렸다면 _flag과 expected가 동일할 것이다.
하지만 WriterLock이 걸려 있다면 _flag에가 [WriteThreadId(15bits)] 영역에 있기 때문에 expected와 flag가 동일한 값이 될 수 없다. 따라서 WriterLock이 걸려 있을 시 if문을 통과하지 못한다.
또 두 쓰레드끼리 경합했을 때 더 빠른 쓰레드가 _flag에 expected+1을 대입하게 되면 뒤 따라 오는 쓰레드는 _flag(==expected + 1)과 expected가 같지 않아 if문을 통과하지 못할 것이다.
허나 어느정도 시간 차를 둔 쓰레드는 if문을 통과할 수 있어 상호 베제의 특성을 가지지 않는다.
- 재귀적 락
재귀적 락을 보면 WriterLock가 유사하게 구현되었는데 ReaderLock의 경우 그냥 _flag에 원자성을 보장한 상태에서 1을 증가시킨다.
- Unlock
_flag를 원자성이 보장된 상태에서 1 감소 시킨다.
각 쓰레드들이 ReadLock과 ReadUnlock을 짝을 맞춰서 실행하기 때문에 _flag는 작업 후에 0이 된다.
class Program
{
static volatile int count = 0;
static Lock _lock = new Lock();
static void Main(string[] args)
{
Task t1 = new Task(delegate ()
{
for (int i = 0; i < 100000; i++)
{
_lock.ReadLock();
count++;
_lock.ReadUnlock();
}
Console.WriteLine(_lock._flag);
});
Task t2 = new Task(delegate ()
{
for (int i = 0; i < 100000; i++)
{
_lock.ReadLock();
count--;
_lock.ReadUnlock();
}
Console.WriteLine(_lock._flag);
});
t1.Start();
t2.Start();
Task.WaitAll(t1, t2);
Console.WriteLine(count);
}
}
ReadLock은 상호배제가 안되기에 count 값이 0이 아니라 5535 처럼 예측할 수 없는 값이 나온다.
_flag의 경우 Task t1과 t2에서 모두 0이 된 것을 확인할 수 있다.
class Program
{
static volatile int count = 0;
static Lock _lock = new Lock();
static void Main(string[] args)
{
Task t1 = new Task(delegate ()
{
for (int i = 0; i < 100000; i++)
{
_lock.WriteLock();
_lock.WriteLock();
count++;
_lock.WriteUnlock();
_lock.WriteUnlock();
}
});
Task t2 = new Task(delegate ()
{
for (int i = 0; i < 100000; i++)
{
_lock.WriteLock();
count--;
_lock.WriteUnlock();
}
});
t1.Start();
t2.Start();
Task.WaitAll(t1, t2);
Console.WriteLine(count);
}
}
WriteLock의 경우, Task t1에서 재귀적 락을 호출했음에도 데드락에 걸리지 않았고
상호배제가 이루어져서 count에 0이 할당된 것을 확인할 수 있다.
