Q1. WriteLock은 상호 배타적, ReadLock은 상호 배타적이 아니게 한 원리를 설명하세요.
Q2. ReadLock은 해도 이상한 값이 나오는 이유를 설명하세요.
Q3. 재귀적으로 Lock을 할 때 허용되는 경우와 허용되지 않는 경우는? 이유는?
Q4. ReadLock에서 A,B가 동시에 진입할 때 flag가 잘 카운트 되도록 한 방법은?
Lock free 프로그래밍이라는 기법이랑 유사한데 처음하면 헷갈리고 어렵긴 해.
어렵다면 한번 구경만 하고 넘어가도 된다.
ServerCore에서 새 항목을 추가해서 Lock이라는 별도의 파일로 빼서 만들어 보자.
namespace ServerCore
{
internal class Lock
{
// [Unused(1)] [WriteThreadId(15)] [ReadCount(16)]
int _flag;
일단 _flag 변수를 선언해 사용할거야. int형이니 32비트가 될거야.
// [Unused(1)] [WriteThreadId(15)] [ReadCount(16)]
첫번째 비트는 사용 안할거야. WriteThreadId라고 15비트를 넣어 줄거야. ReadCount라는 애를 16비트를 이용해서 차지를 할거야.
ReadCount는 ReadLock을 획득했을 때 스레드들이 동시에 Read를 잡을 수 있다고 했어. Counting 하는 거,
WriteLock은 한번에 한 쓰레드만 획득할 수 있다 했어. 그 아이가 누구인지 여기에 기록하게 될 것이다.
락을 만들 때 정책을 몇 개 정해야 하는데
재귀적 락을 허용할 것인지 정해야 한다. WriteLock을 Acquire한 상태에서 같은 스레드에서 또 재귀적으로 다시 한번 Acquire를 할 때 허용할지 안할지에 관한 문제. 일단 쉽게 하기 위해 허용 안 한 상태에서 구현 해보도록 한다.
스핀락도 정책 있어야 한다. 5000번 스핀한 다음에 -> Yield 하는 방식으로 구현을 해본다.
flag를 사용하기 위해서 자주 사용할 애들은 const int 변수로 만들어 준다.
using System;
using System.Collections.Generic;
using System.Text;
namespace ServerCore
{
// 재귀적 락을 허용할지(No)
// 스핀락 정책 ( 5000번 -> Yield)
class Lock
{
const int EMPTY_FLAG = 0x00000000;
const int WRITE_MASK = 0x7FFF0000; // 15비트 사용
const int READ_MASK = 0x0000FFFF; // 16비트만 사용
const int MAX_SPIN_COUNT = 5000;
// [Unused(1)] [WriteThreadId(15)] [ReadCount(16)]
int _flag;
}
}
맨 위의 비트는 음수가 될 수 있어서 비워 두고 나머지 15랑 16을 각각 ThreadId랑 ReadCount로 쓰기로 했어.
아래의 16개를 ReadCount로 사용할거야. ReadCount만 빼내고 싶으면 윗줄은 0으로 하면 된다. 추출하려면 아랫줄은 다 1로 켜줘야 한다. 그래서 READ_MASK가 0x0000FFFF다. WRITE_MASK는 윗줄을 추출하는 거라 그 반대가 된다.
lock이랑 unlock을 하는 Acqire, Release 하는 인터페이스를 만들어 준다.
public void WriteLock()
{
}
public void WriteUnlock()
{
}
public void ReadLock()
{
}
public void ReadUnlock()
{
}
이제 가장 처음걸 만들어 보자
일단 int flag 시작 값을 0으로 맞춰준다.
int _flag = EMPTY_FLAG;
아무도 WriteLock or ReadLock을 획득하고 있지 않을 때, 경합해서 소유권을 얻는다. 가 해야 할 행동이다.
public void WriteLock()
{
// 아무도 WriteLock or ReadLock을 획득하고 있지 않을 때, 경합해서 소유권을 얻는다.
int desired = (**Thread.CurrentThread.ManagedThreadId** << 16) & WRITE_MASK;
while(true)
{
for(int i =0; i<MAX_SPIN_COUNT; i++)
{
// 시도를 해서 성공하면 return
**if (_flag == EMPTY_FLAG) // 아무도 WriteLock이나 Readlock을 획득 안한 상황
_flag = desired; // 원하는 값을 넣어주면 된다. WriteThreadId를 채워주고 싶**
}
// 5000번 했는데도 실패하면
Thread.Yield(); // 현재 실행 중인 스레드를 일시적으로 일시 중지하고 다른 스레드가 실행되도록 허용합니다
}
}
_flag가 비어 있다면 원하는 값(desired)을 넣어주면 된다. WriteThreadId를 채워주고 싶은데Thread.CurrentThread.ManagedThreadId를 그대로 사용했다. 16비트만큼 밀어주고, WRITE_MASK를 적용해서 나머지 부분은 0으로 밀어 준다.
ThreadId만 WriteThreadID의 비트에 들어가게 한 것. desired를 _flag에 넣어주면 생각하는 방법이 된다.
이렇게 하면 될까? 사실은 안된다.
멀티스레드에서 계속 이런 문제가 나왔었어.
if (_flag == EMPTY_FLAG) // 이렇게 비교를 하고
_flag = desired; // 이렇게 _flag에 집어 넣는 행위
이렇게 두 단계로 분리되어 있어.
멀티스레드에서 여러개가 동시에 WriteLock을 시도한다고 가정 하면 동시에 자기가 원하는 값을 flag에 넣을 테니 count++과 마찬가지로 **이상한 값이 넣어질 것이다. 동시 다발 적으로 여러명이 자기가 성공했다고 착각하게 될 거야.
이렇게 나눠서 하면 안되고 Interlocked 계열 함수로 바꿔치기를 해야 한다.
if (Interlocked.CompareExchange(ref _flag, desired, EMPTY_FLAG) == EMPTY_FLAG)
return;
이렇게 하면 두줄의 코드가 한방에 처리가 되고, 동시 다발적으로 두 마리가 들어 올 수 없게 된다.
뱉어주는 값은 이전 값을 뱉어 준다고 했으니까 성공했는지 알고 싶으면 ==EMPTY_FLAG인지를 확인하면 _flag EMPTY_FLAG였다는 걸 알 수 있어. 이렇게 두줄로 나눠진 것을 한줄로 처리할 수 있다.
만약에 동시 다발적으로 두명이 들어오면 두 스레드 마다 ThreadId가 다를 테니까 desired 값이 다르게 될 거다. 아무리 거의 동시 다발적으로 들어왔다고 해도 승자는 존재하기 마련일텐데 그 승자가 _flag값을 자기 desired 값으로 넣어줄테니까 결국 두번째로 시도하는 애는 애당초 EMPTY_FLAG와 같다는 조건에서 실패를 하기 때문에 동시 다발적으로 두마리가 들어 올 수 없게 된다.
public void WriteLock()
{
// 아무도 WriteLock or ReadLock을 획득하고 있지 않을 때, 경합해서 소유권을 얻는다.
int desired = (Thread.CurrentThread.ManagedThreadId << 16) & WRITE_MASK;
while(true)
{
for(int i =0; i<MAX_SPIN_COUNT; i++)
{
if (Interlocked.CompareExchange(ref _flag, desired, EMPTY_FLAG) == EMPTY_FLAG)
return;
}
Thread.Yield();
}
}
이렇게 하면 WriteLock을 구현할 수 있다.
WriteUnlock의 경우는 경합 할 필요 없이 Lock 한 애만 Unlock을 하면 된다.
WriteThreadId에 있는 // [Unused(1)] [WriteThreadId(15)] [ReadCount(16)] 이 값을 그냥 밀어주면 된다. 즉 _flag를 EMPT_FLAG로 밀어주면 되는 거니까
public void WriteUnlock()
{
Interlocked.Exchange(ref _flag, EMPTY_FLAG);
}
초기 상태로 바꿔주는 게 된다.
ReadLock의 의사 코드를 작성해 보면
public void ReadLock()
{
// 아무도 WriteLock을 획득하고 있지 않으면, ReadCount를 1늘린다.
while(true)
{
for(int i=0; i<MAX_SPIN_COUNT; i++)
{
**if((_flag & WRITE_MASK) == 0)
{
_flag = _flag + 1;**
return;
}
}
Thread.Yield();
}
}
아무도 WriteLock을 획득하고 있지 않으면,
// [Unused(1)] [WriteThreadId(15)] [ReadCount(16)]
WriteThreadId가 아무도 없다. 즉 _flag에 WRITE_MASK를 씌었더니 0이라고 하면, ReadCount를 1늘리면 된다. ReadLock은 여러 스레드가 동시에 잡을 수 있었기 때문에 ReadCount를 쿨하게 1씩 늘리면 된다.
SPIN_COUNT 5000번을 도는데 돌다가 정 안되면 Yield를 해주면된다.
아까와 마찬가지로 문제가 있다. 체크를 하고 1을 늘리는게 문제가 있어. 통과를 해서 늘리려는 상황에서 어떤 애가 WriteLock을 잡아 버리면 결국 WriteLock이 잡혔으니까 어떤 TheadId가 들어가고 _flag+1을 해줬으니까 ReadCount에 값이 동시에 들어가게 된다. WriteLock, ReadLock이 동시에 잡혔다는 얘기가 되니까 말이 안되는 상황이 된다. 결국 얘도 한번에 처리할 수 있는 방법으로 묶어야 한다.
public void ReadLock()
{
// 아무도 WriteLock을 획득하고 있지 않으면, ReadCount를 1늘린다.
while(true)
{
for(int i=0; i<MAX_SPIN_COUNT; i++)
{
int expected = (_flag & READ_MASK); // A(0) B(0) 스레드 동시에 들어왔다 가정
if (Interlocked.CompareExchange(ref _flag, expected + 1, expected) == expected)
// A(0->1) B(0->1) , A가 성공하면 _flag 값 1로 됨. B는 flag값 바뀐 상태라 (0->1) 실패한다.
// B는 다음 턴에 경합을 한다. 이렇게 계속 뺑뺑이 도는게 Lock free 프로그램의 기본
return;
}
Thread.Yield();
}
}
마찬가지로 Interlocked.CompareExchange를 쓰면 된다. 여기 부분이 까다로워. lock free 프로그래밍의 기초.
expected 예상하던 값은 _flag & READ_MASK 이 뜻은 // [Unused(1)] [WriteThreadId(15)] [ReadCount(16)] 에서 [Unused(1)] [WriteThreadId(15)] 는 날리고 [ReadCount(16)] 부분만 뽑아 와서 사용하는 부분이 expected라는 거. 예상한 값은 Write가 없는 값이니까 WriteFlag에 해당하는 값을 다 밀어 준 값을 넣어준 것이다.
예상 값은 expected고 원하는 값은 1을 늘린 값이 되는데 이게 성공했다는 얘기는 _flag & WRITE_MASK) == 0 이 의미가 된다.
얘가 한방에 통과 할 수도 안할 수도 있어. 만약 WriteLock을 누가 잡고 있었다고 하면 애당초 [WriteThreadId(15)] 이 부분이 0이 아니라 원하는 값이 맞지 않기에 실패하게 된다.
또는 두 마리가 동시에 ReadLock을 한다고 가정하면 int expected = (_flag & READ_MASK); 여기서 expected값 뽑을 때 까진 똑같겠지만 경합을 하는거. 1을 늘리고 싶어 하는데 맨 먼저 들어온 애는 1을 늘릴 수 있을거야. 다음에 들어온 애는 예상하던 값이 틀어지게 될거야. expected값을 1 늘려 _flag에 대입했기 때문에 expected 값이 _flag와 같지 않게 되니까 실패를 하고 다음 턴에 테스트를 해야 한다는 얘기가 된다.
요약하면 A, B 쓰레드가 거의 동시에 ReadLock 해가지고, int expected = (_flag & READ_MASK); 에 동시에 들어왔다 가정을 하면 expected값이 A(0), B(0), flag값이 0이면 0+1인 1로 바꿔주세요를 동시에 실행할거야. 승자가 나오면 만약 A가 먼저 실행됐다고 하면 expected+1이 flag에 들어가니까 flag가 1로 바뀐다. B가 요청한 건 _flag가 0이면 1로 바꿔주세요 였는데 이미 A에 의해 _flag값이 1로 바뀐 상태니까 B의 요청은 실패를 하게 된다. B는 다음 턴에 똑같이 경주를 해서 경합을 해서 다시 한번 실행을 하게 될 거다.
이렇게 계속 뻉뻉이를 돌면서 될 떄 까지 try 하는게 LockFree 프로그래밍의 기본이라고 할 수 있다.
이렇게 ReadLock을 하나 늘렸다고 하면 ReadUnLock을 하는 거 같은 경우는 간단하다.
ReadUnlock은 간단하다.
public void ReadUnlock()
{
Interlocked.Decrement(ref _flag);
}
그냥 1을 줄여주면 된다.
의문점이 왜 // [Unused(1)] [WriteThreadId(15)] [ReadCount(16)] 여기에 WriteThreadId를 넣어주는 걸까? 그냥 boolean 처럼 0이나 1 값을 넣어줘도 될텐데. 그렇게 하면 재귀적 락이 혹시라도 필요하게 되면 누가 얘를 잡고 있는지를 알아야 하기 때문에 이렇게 굳이 작업을 해 것이다.
이어서 만약 재귀적 락을 활용한다고 가정해 보자.
// 재귀적 락을 활용할지(Yes)
WriteLock->WriteLock OK,
WriteLock->ReadLock OK,
ReadLock->WriteLock NO(ReadLock은 애초 독점이 아니기에)
두 경우만 된다고 가정 해보자.
어떻게 하냐
int _writeCount = 0;
_writeCount를 추가하면 된다. 재귀적으로 몇 개가 write를 할지를 관리를 하는 거고, 굳이 왜 flag에 넣을 필요 없냐면 애당초 write라는게 상호 배타적인 관계였어. 누군가가 write Lock을 잡았다는 건 걔만 writeCount에 접근할 수 있다는 의미니까 multi thread에 문제가 없어서 별도의 변수로 빼줘도 된다.
public void WriteLock()
{
**// 동일 쓰레드가 WriteLock을 이미 획득하고 있는지 확인
int lockThreadId = (_flag & WRITE_MASK) >> 16;
if(Thread.CurrentThread.ManagedThreadId == lockThreadId)
{
_writeCount++;
return;
}**
// 아무도 WriteLock or ReadLock을 획득하고 있지 않을 때, 경합해서 소유권을 얻는다.
int desired = (Thread.CurrentThread.ManagedThreadId << 16) & WRITE_MASK;
while(true)
{
for(int i =0; i<MAX_SPIN_COUNT; i++)
{
if (Interlocked.CompareExchange(ref _flag, desired, EMPTY_FLAG) == EMPTY_FLAG)
{
**_writeCount = 1;**
return;
}
}
Thread.Yield();
}
}
내가 WriteLock을 잡고 있었다고 하면 성공한 거니까 _writeCount를 1 늘리고 return을 때려주면 된다. 만약 WriteLock을 잡는데 처음 성공을 했으면 바로 return 하는게 아니라 _writeCount를 1로 바꿔준 다음에 return 을 해준다.
writeUnlock 같은 경우에는 무조건 풀어주는게 아니라 lockCount라는 변수를 두는데 writeCount를
--해서 늘린 만큼을 다 회수 해서 0이 되면 풀어 준다는 얘기가 된다.
public void WriteUnlock()
{
**int lockCount = --_writeCount;
if(lockCount == 0)**
Interlocked.Exchange(ref _flag, EMPTY_FLAG);
}
ReadLock도 윗 부분에서 테스트를 해야 하는데
readCount를 늘려야 하는거. Interlocked.Increment(ref _flag); 이렇게 해주면 [Unused(1)] [WriteThreadId(15)] [ReadCount(16)] 에서 [ReadCount(16)] 얘만 1 늘리게 되는 거니까 정상적으로 처리가 된다.
public void ReadLock()
{
**// 동일 쓰레드가 WriteLock을 이미 획득하고 있는지 확인
int lockThreadId = (_flag & WRITE_MASK) >> 16;
if (Thread.CurrentThread.ManagedThreadId == lockThreadId)
{
Interlocked.Increment(ref _flag);
return;
}**
// 아무도 WriteLock을 획득하고 있지 않으면, ReadCount를 1늘린다.
while (true)
{
for(int i=0; i<MAX_SPIN_COUNT; i++)
{
**int expected = (_flag & READ_MASK); // A(0) B(0) 스레드 동시에 들어왔다 가정
if (Interlocked.CompareExchange(ref _flag, expected + 1, expected) == expected) // A(0->1) B(0->1) , A가 성공하면 _flag 값 1로 됨. B는 flag값 바뀐 상태라 (0->1) 실패한다. B는 다음 턴에 경합을 한다. 이렇게 계속 뺑뺑이 도는게 Lock free 프로그램의 기본
return;**
}
Thread.Yield();
}
}
여기서 할 때 조심해야 할 것은 WriteLock을 한 다음에 ReadLock을 했으면 반드시 풀어주는 순서도ReadUnlock을 해주고 풀어 준 다음에 WrtieUnlock을 해줘야 한다. 그렇지 않으면 순서가 꼬이게 된다.
이렇게 하면 재귀적으로 Lock을 잡는 것도 부분적으로 구현이 된 거고, Write와 Read에 대한 기능도 추가가 된 것이다.
가장 중요한 부분은
ReadLock에서
for(int i=0; i<MAX_SPIN_COUNT; i++)
{
**int expected = (_flag & READ_MASK); // A(0) B(0) 스레드 동시에 들어왔다 가정
if (Interlocked.CompareExchange(ref _flag, expected + 1, expected) == expected) // A(0->1) B(0->1) , A가 성공하면 _flag 값 1로 됨. B는 flag값 바뀐 상태라 (0->1) 실패한다. B는 다음 턴에 경합을 한다. 이렇게 계속 뺑뺑이 도는게 Lock free 프로그램의 기본
return;**
}
이부분 중요하니 이해가 갈 때 까지 분석해보자.
WriteLock만 간단하게 테스트 해보자.
Program.cs에 가서
using System;
using System.Threading;
using System.Threading.Tasks;
namespace ServerCore
{
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();
count++;
_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);
}
}
}
실행을 해보면
이렇게 0이 잘 나오는 것을 볼 수 있다.
Task t1 = new Task(delegate ()
{
for (int i = 0; i < 100000; i++)
{
_lock.WriteLock();
_lock.WriteLock();
count++;
_lock.WriteUnlock();
_lock.WriteUnlock();
}
});
이렇게 중첩으로 WriteLock을 넣어 줘도 0이 나오는 것을 알 수 있다.
Task t1 = new Task(delegate ()
{
for (int i = 0; i < 100000; i++)
{
_lock.WriteLock();
_lock.WriteLock();
count++;
_lock.WriteUnlock();
}
});
이렇게 까먹고 짝을 맞춰주지 않으면 영영 리턴을 하지 않는다.
왜냐하면 t1에서 Lock을 안 푼 상태에서 Task t2에서 계속 획득하려고 시도를 하니까 문제가 일어난 거
Task t1 = new Task(delegate ()
{
for (int i = 0; i < 100000; i++)
{
_lock.ReadLock();
count++;
_lock.ReadUnlock();
}
});
Task t2 = new Task(delegate ()
{
for (int i = 0; i < 100000; i++)
{
_lock.ReadLock();
count--;
_lock.ReadUnlock();
}
});
ReadLock을 하면 어떻게 될까? 애초에 상호 배타적이 아니라 락을 하나마나 이상한 값이 나올거다.
이렇게 간단한 ReadLock , WriteLock을 구현해봤다.
지금 이해가 안되도 상관 없다. 자주 일어나는 프로그래밍은 아님.
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
namespace ServerCore
{
// 재귀적 락을 허용할지(Yes) WriteLock->WriteLock OK, WriteLock->ReadLock OK, ReadLock->WriteLock NO(ReadLock은 애초 독점이 아니기에)
// 스핀락 정책 ( 5000번 -> Yield)
class Lock
{
const int EMPTY_FLAG = 0x00000000;
const int WRITE_MASK = 0x7FFF0000; // 15비트 사용
const int READ_MASK = 0x0000FFFF; // 16비트만 사용
const int MAX_SPIN_COUNT = 5000;
// [Unused(1)] [WriteThreadId(15)] [ReadCount(16)]
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을 획득하고 있지 않을 때, 경합해서 소유권을 얻는다.
int desired = (Thread.CurrentThread.ManagedThreadId << 16) & WRITE_MASK;
while(true)
{
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()
{
int lockCount = --_writeCount;
if(lockCount == 0)
Interlocked.Exchange(ref _flag, EMPTY_FLAG);
}
public void ReadLock()
{
// 동일 쓰레드가 WriteLock을 이미 획득하고 있는지 확인
int lockThreadId = (_flag & WRITE_MASK) >> 16;
if (Thread.CurrentThread.ManagedThreadId == lockThreadId)
{
Interlocked.Increment(ref _flag);
return;
}
// 아무도 WriteLock을 획득하고 있지 않으면, ReadCount를 1늘린다.
while (true)
{
for(int i=0; i<MAX_SPIN_COUNT; i++)
{
int expected = (_flag & READ_MASK); // A(0) B(0) 스레드 동시에 들어왔다 가정
if (Interlocked.CompareExchange(ref _flag, expected + 1, expected) == expected) // A(0->1) B(0->1) , A가 성공하면 _flag 값 1로 됨. B는 flag값 바뀐 상태라 (0->1) 실패한다. B는 다음 턴에 경합을 한다. 이렇게 계속 뺑뺑이 도는게 Lock free 프로그램의 기본
return;
}
Thread.Yield();
}
}
public void ReadUnlock()
{
Interlocked.Decrement(ref _flag);
}
}
}
'Server programming' 카테고리의 다른 글
| 02_01_네트워크 프로그래밍_네트워크 기초 이론 (0) | 2023.03.31 |
|---|---|
| 01_15_멀티쓰레드_ThreadLocalStorage (0) | 2023.03.31 |
| 01_13_멀티쓰레드_ReaderWriteLock (0) | 2023.03.21 |
| 01_12_멀티쓰레드_AutoResetEvent (0) | 2023.03.16 |
| 01_11_멀티쓰레드_ContextSwitching (0) | 2023.03.15 |
댓글