쓰레드 동기화
- 유저 모드 동기화
커널 모드로 전환하지 않고 동기화를 수행한다. 커널 모드보다 빠르지만 기능이 제한적이다.
- 크리티컬 섹션 Critical Section
- 스핀락 인터락 함수 기반 Interlocked Family of Function
- SRWLock Slim Reader/Writer Lock
- 커널 모드 동기화
커널 모드로 전환하여 커널이 제공하는 동기화 방법을 사용한다. 느리지만 더 다양한 기능을 사용할 수 있다.
- 뮤텍스 Mutex
- 세마포어 Semphore
- 이름있는 뮤텍스 Named Mutex
- 이벤트 Event
CriticalSection
뮤텍스처럼 락을 걸고 임계 영역을 진입하며 공유 자원을 사용한 이후 다시 반납한다.
생성과 소멸에 관한 함수
// 생성
void InitializeCriticalSecion(LPCRITICAL_SECTION lpCriticalSection);
// 소멸
void DeleteCriticalSection(LPCRITICAL_SECTION lpCriticalSection);임계영역 진입에 관한 함수
void EnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection);
void LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection);- EnterCriticalSection : 임계 영역 진입을 위한 함수로 다른 쓰레드가 이미 호출하였다면 block 상태에 놓이게 된다.
- LeaveCriticalSection : 임계 영역을 빠져나올 때 호출하는 함수로 block 상태에 있는 다른 쓰레드가 있다면 다른 쓰레드를 깨워 임계영역에 진입할 수 있도록 해준다.
클래스 예시
#pragma once
#include "ILockable.h"
#include <Windows.h>
class CriticalSection : public ILockable
{
public:
CRITICAL_SECTION m_Mutex;
public:
CriticalSection()
{
InitializeCriticalSection(&m_Mutex);
}
~CriticalSection()
{
DeleteCriticalSection(&m_Mutex);
}
FORCEINLINE virtual void Lock() override
{
EnterCriticalSection(&m_Mutex);
}
FORCEINLINE virtual void UnLock() override
{
LeaveCriticalSection(&m_Mutex);
}
};
스핀락 - Interlocked Family Of Function 기반의 동기화
락이 없는 스핀락을 사용하는 이유
스핀 락은 락을 얻지 못 했을 경우 쓰레드를 재우지 않고 CPU를 사용하며 락을 계속 얻으려고 시도한다. 주로 락이 걸리는 영역이 굉장히 작을 경우에 쓰레드를 재우고 깨우는 커널 함수에 의한 비용보다 폴링 방식이 더 빠르게 락을 얻을 확률이 높다.
InterlockedCompareExchange 함수
윈도우에서 제공하는 Interlock 함수 종류는 다양하다. 주로 변수 하나에 대한 접근 방식을 동기화하고자 할 때 사용하며 내부적으로 하나의 쓰레드에 의해서만 실행되도록 구현되어 있다.
LONG __cdecl _InterlockedCompareExchange(volatile LONG* Destination, LONG ExChange, LONG Comperand);스핀 락 구현을 위해 자주 사용되는 이 함수는 Destination 변수를 확인해서 Comperand 값과 같다면 ExChange값으로 바꾸고 빠져나온다. 그렇지 않다면 바꾸지 않고 빠져나온다.
이 함수는 이전의 값을 반환하는데, 주로 Destination 변수에 0을 설정하고 ExChange를 1로 설정하여 1로 변경되었을 경우 0을 반환하고 변경되지 않았다면 1을 반환한다.
따라서 위 함수를 통해 스핀 락을 구현할 수 있다.
volatile LONG gFlag = 0;
void AcquireLock()
{
LONG oldFlag;
while (oldFlag = _InterlockedCompareExchange(&gFlag, 1, 0)) {}
}void ReleaseLock()
{
_InterlockedDecrement(&gFlag);
}InterlockedDecrement()는 해당 32비트 변수를 1 감소 시켜 락을 반환한다.
클래스 예시
#pragma once
#include "ILockable.h"
#include <Windows.h>
#include <atomic>
class SpinLock : public ILockable
{
private:
volatile unsigned int m_Flag;
int m_MaxSleepIteration;
int m_YieldIteration;
public:
SpinLock(int MaxSleepIteration = 30, int YieldIteration = 20)
:
m_Flag(0),
m_MaxSleepIteration(MaxSleepIteration),
m_YieldIteration(YieldIteration)
{
}
FORCEINLINE virtual void Lock() noexcept override
{
int iterations = 0;
while (InterlockedCompareExchange(&m_Flag, 1, 0))
{
// 더 높은 우선순위의 ready 스레드가 있으면 Context Switching이 일어난다.
if (iterations + m_YieldIteration >= m_MaxSleepIteration)
{
Sleep(0);
}
if (iterations >= m_YieldIteration && iterations < m_MaxSleepIteration)
{
iterations = 0;
SwitchToThread();
}
++iterations;
//
// Yield processor on multi-processor but if on single processor then give other thread the CPU
YieldProcessor(/*no op*/);
}
}
FORCEINLINE virtual void UnLock() noexcept override
{
InterlockedDecrement(&m_Flag);
}
};
class AtmoicSpinLock : public ILockable
{
private:
std::atomic_flag m_Flag;
int m_MaxSleepIteration;
int m_YieldIteration;
public:
AtmoicSpinLock(int MaxSleepIteration = 30, int YieldIteration = 20)
:
m_Flag{},
m_MaxSleepIteration(MaxSleepIteration),
m_YieldIteration(YieldIteration)
{}
FORCEINLINE virtual void Lock() noexcept override
{
int iterations = 0;
while (m_Flag.test_and_set(std::memory_order_acquire))
{
if (iterations + m_YieldIteration >= m_MaxSleepIteration)
{
Sleep(0);
}
if (iterations >= m_YieldIteration && iterations < m_MaxSleepIteration)
{
iterations = 0;
SwitchToThread();
}
++iterations;
YieldProcessor(/*no op*/);
}
}
FORCEINLINE virtual void UnLock() noexcept override
{
m_Flag.clear(std::memory_order_release);
}
};
SRW Lock (번역)
https://docs.microsoft.com/en-us/windows/win32/sync/slim-reader-writer--srw--locks
Slim reader/writer (SRW) locks은 single 프로세스의 멀티 쓰레드가 최적화된 메모리 사용과 속도로 공유 자원을 접근하는 것을 가능하게 한다. SRW lock은 멀티 프로세스에서 공유될 수 없다.
Reader 행동은 공유 자원을 읽기만 하며 Writer는 공유 자원을 쓰기도 한다. Write가 거의 일어나지 않고 Read가 대부분이라면 멀티 쓰레드가 공유 자원을 읽고 쓴다면 exclusive lock을 사용하는 Critical Section이나 Mutex는 병목이 될 수 있다.
Shared mode : 다중 Reader 쓰레드가 read-only 접근을 허용하도록 하며 병행적으로 공유자원을 읽게 해준다. Read 행위가 Write 행위보다 선행되면 이 동작 방식은 다른 lock보다 더 좋은 성능을 보인다.
Exclusive mode : Writer가 쓰레드를 점유하면 Read/Write 모두 금지된다. 따라서 다른 모든 쓰레드가 락을 얻을 수 없다.
SRWLock은 두 모두 중 선택하여 락을 얻을 수 있고 Reader는 shared 모드로 Writer는 exclusive 모드로 락을 얻어야한다. 하지만 FIFO나 공평한 정책을 사용하지 않기 때문에 어떤 쓰레드가 소유권을 먼저 획득할 지 보장이 없다.
SRW lock은 포인터 크기(8바이트)를 가지며 이는 매우 빠르게 lock 상태를 변경하는 것을 가능하게 한다. 단점은 정보를 거의 가지고 있지 않기 때문에 shared 모드에서 올바르지 않은 재귀적 사용을 탐지할 수 없다. 게다가, 한 shared 모드로 락을 얻은 쓰레드는 그 중간에 exclusive 모드로 락을 승격시킬 수 없다.
관련 함수
// SRW lock 초기화 함수
void InitializeSRWLock(
PSRWLOCK SRWLock
);
// SRWLock Exclusive 모드
void AcquireSRWLockExclusive(
PSRWLOCK SRWLock
);
// SRWLock Shared 모드
void ReleaseSRWLockExclusive(
PSRWLOCK SRWLock
);클래스 예시
#pragma once
#include "ILockable.h"
#include <windows.h>
class SRWLock : public ILockable
{
private:
SRWLOCK m_Lock;
public:
SRWLock()
:
m_Lock(SRWLOCK_INIT)
{}
FORCEINLINE virtual void Lock() noexcept override
{
AcquireSRWLockExclusive(&m_Lock);
}
FORCEINLINE virtual void UnLock() noexcept override
{
ReleaseSRWLockExclusive(&m_Lock);
}
};
Semaphore
세마포어는 특정 작업을 하는 쓰레드 개수를 제한시킨다. 세마포어는 최대 허용할 자원 개수를 의미하는 파라미터가 있으며 이 자원을 획득하는 쓰레드는 자원 수를 하나 줄이고 작업을 진행한다. 작업을 마친 쓰레드는 ReleaseSemphore를 통해 자원 수를 다시 하나 증가 시켜야한다.
HANDLE CreateSemaphoreA(
LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,
LONG lInitialCount,
LONG lMaximumCount,
LPCSTR lpName
);- lpSamphoreAttributes : 보안 속성
- lIintialCount : 초기 세마포어 자원 수
- lMaximumCount : 최대 허용 자원 수
- LPSTR : 이름있는 세마포어 지정
획득 방법 : WaitForSingleObject를 이용하여 함수가 WAIT_OBJECT_0를 반환시 카운트를 감소시키고 작업을 진행할 수 있게 된 것을 의미한다. 그렇지 않다면 타임 아웃 WAIT_TIMEOUT을 반환한다.
WaitForSingleObject(hSemaphore, dwTimeOut);
커널 모드 동기화
뮤텍스 Mutex
HANDLE CreateMutex(LPSECURITY_ATTRIBUTES lpMutexAttributes, BOOL bInitialOwner, LPCTSTR lpName);- lpMutexAttributes: 보안 속성을 지정한다.
- bInitalOwner: 생성한 쓰레드가 바로 락을 얻을 수 있게 설정을 할 수 있다. (TRUE)
- lpName: 뮤텍스에 이름을 지정한다. 널 값이 아니라면 이름있는 뮤텍스가 생성된다.
반환값은 핸들값이며 뮤텍스가 커널 오브젝트임을 의미한다. CloseHandle 함수를 통해 뮤텍스 자원을 해제한다.
뮤텍스의 커널 오브젝트의 상태가 Signaled 상태일 때 획득 가능하며 따라서 WaitForSingleObject 함수를 통해 락을 얻는 것을 시도할 수 있다. 락을 얻게되면 Mutex 객체는 Non-Signaled 상태가 된다. 공유 자원을 사용한 이후에는 ReleaseMutex를 호출하여 락을 반납하고 Signaled 상태가 되도록 한다.
STL mutex
Portable한 코드를 작성하려면 STL에서 제공하는 mutex를 사용해야하며 std::lock_guard<T>를 이용한 RAII 방식으로 임계영역을 잠그는 것에 실수를 줄 일 수 있다. 커널 모드의 동기화 방법을 제공하며 CriticalSection과 마찬가지로 내부적으로 스핀락이 구현되어 있어 락을 얻지 못한 스레드가 바로 block되지 않는다. std::mutex는 획득 스레드가 또 다시 lock을 할 때 데드락이 발생하는데, std::recursive_mutex 객체는 재진입을 허용하며 여러 스레드에서 하나의 뮤텍스를 사용하고자할 때 std::shared_mutex와 같은 동기화 객체를 제공한다.
클래스 예시
일반적으로 std::lock_guard를 이용한다. (성능 비교를 위해 클래스를 만들었음)
#pragma once
#include "ILockable.h"
#include <mutex>
class StdMutex : public ILockable
{
private:
std::mutex m_Mutex;
public:
StdMutex()
:
m_Mutex{}
{}
__forceinline virtual void Lock() override { m_Mutex.lock(); }
__forceinline virtual void UnLock() override { m_Mutex.unlock(); }
};
이벤트 Event
HANDLE CreateEvent(
LPSECURITY_ATTRIBUTES lpEventAttributes,
BOOL bManualReset,
BOOL bInitialState,
LPCTSTR lpName);- lpEventAttributes: 보안 속성을 지정한다.
- bManualReset: 수동 리셋 혹은 자동 리셋 모드를 설정한다. 자동 리셋 모드인 경우 이벤트 객체가 Signaled 상태일 때 WaitForSingleObject 함수로 인해 (혹은 다른 상태 변경 함수) Non-Signaled 상태가 자동으로 되도록한다.
- 자동이 아니라면 ResetEvent 함수를 통해 Non-Signaled 상태가 되도록 만들어야 한다.
- bInitialState: 이벤트 초기 상태를 결정한다. (TRUE 일 시 Signaled 상태)
- lpName: 이름을 지정한다.
이벤트 객체는 실행 순서를 동기화할 때 사용한다. 주로 쓰레드를 함수 내부에서 이벤트 객체로 블락하고 (WaitForSingleObject) Signaled 상태가 되었을 때 실행을 시작할 수 있도록 한다.
쓰레드의 바탕 함수는 hEvent가 Signaled 상태가 되어야 실행을 시작할 수 있게 된다.
여러가지 동기화 기법 테스트
1. Critical Section : 유저 모드 동기화 기법
2. std::mutex : 커널 모드 동기화 기법
3. SpinLock : 스핀 동안 컨텍스트 스위칭을 유도하거나 YieldProcessor()를 호출하여 다른 프로세서의 명령어 인출을 유도한다.
4. Atomic SpinkLock : Interlock 함수를 이용하지 않고 atomic_flag 객체를 이용하여 test_and_set 기법을 이용한다.
5. SRWLock : Reader/Writer 행위에 따른 SRWLock
테스크
1. Simple Task
단순히 공유 자원 변수 SharedCount를 1 증가시킨다.
2. Complex Task
string을 보관하는 set 컨테이너에 키를 삽입한다.
임계 영역이 작고 증감과 같은 단순한 연산에서 락이 없는 SRWLock과 Spin Lock 방법은 괜찮은 성능을 보인다.
해쉬 컨테이너를 업데이트하는 작업을 Complex Task로 정의하였는데 유의미한 차이는 볼 수 없었다. 하지만 이보다 임계영역이 더 큰 작업의 경우 SpinLock 계열은 Complex Task에서 근소한 차이로 폴링 방식을 사용하기 때문에 복잡한 테스크에서 block 쓰레드를 깨울 수 있는 mutex나 critical section 보다 좋지 않을 수 있다.
사용한 코드
#include "Define.h"
#include "PerformanceCounter.h"
#include "CriticalSection.h"
#include "SpinLock.h"
#include "StdMutex.h"
#include "SRWLock.h"
using namespace std;
bool SelectSimple = true;
constexpr int NUM_TEST = 10;
constexpr int NUM_THREADS = 8;
constexpr int NUM_LOOP_EASY = 100000;
constexpr int NUM_LOOP_HARD = 10000;
HANDLE hWaitThread = {};
HANDLE hReadyThread[NUM_THREADS];
HANDLE hThread[NUM_THREADS];
vector<string> RandomStrings;
void GenerateString();
struct UserData
{
int id;
DWORD ThreadId;
ILockable* Method;
string Name;
int* SharedCount;
unordered_set<string>* SharedContainer;
double Result;
};
struct Statistics
{
string Name;
double mean;
double var;
double min;
double max;
};
DWORD WINAPI ExecuteSimpleTask(LPVOID lpParameter)
{
PerformanceCounter counter;
UserData* pData = (UserData*)lpParameter;
SetEvent(hReadyThread[pData->id]);
WaitForSingleObject(hWaitThread, INFINITE);
counter.Tick();
for (int i = 0; i < NUM_LOOP_EASY; ++i)
{
LockGuard<ILockable> lock(pData->Method);
++(*pData->SharedCount);
}
pData->Result = counter.Toc();
return 0;
}
DWORD WINAPI ExecuteComplexTask(LPVOID lpParameter)
{
PerformanceCounter counter;
UserData* pData = (UserData*)lpParameter;
constexpr int PerThread = NUM_LOOP_HARD / NUM_THREADS;
int LoopStart = pData->id * PerThread;
int LoopEnd = std::min(LoopStart + PerThread, (int)RandomStrings.size());
auto& Container = pData->SharedContainer;
SetEvent(hReadyThread[pData->id]);
WaitForSingleObject(hWaitThread, INFINITE);
counter.Tick();
for (int i = LoopStart; i < LoopEnd; ++i)
{
LockGuard<ILockable> lock(pData->Method);
const string& key = RandomStrings[i];
if (Container->find(key) == Container->end())
{
Container->insert(key);
}
}
pData->Result = counter.Toc();
return 0;
}
void GetMethod(int sel, ILockable** method, string& Name)
{
switch (sel)
{
case 0:
*method = new CriticalSection();
Name = "CriticalSection";
break;
case 1:
*method = new StdMutex();
Name = "Std Mutex";
break;
case 2:
*method = new SpinLock();
Name = "SpinLock";
break;
case 3:
*method = new AtmoicSpinLock();
Name = "Atomic SpinLock";
break;
case 4:
*method = new SRWLock();
Name = "SRWLock";
break;
}
}
int main()
{
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
printf("Number Of Hardware Threads : %d\n", std::thread::hardware_concurrency());
printf("Number Of Created Threads : %d\n", NUM_THREADS);
GenerateString();
hWaitThread = CreateEvent(NULL, TRUE, FALSE, NULL);
for (int i = 0; i < NUM_THREADS; ++i)
{
hReadyThread[i] = CreateEvent(NULL, TRUE, FALSE, NULL);
}
string SelectedTask = SelectSimple ? "Easy" : "Hard";
Statistics stats[5];
int printcount = 0;
for (int sel = 0; sel < 5; ++sel)
{
ILockable* method = nullptr;
string Name = "";
GetMethod(sel, &method, Name);
stats[sel].Name = Name;
vector<double> Results;
for (int t = 0; t < NUM_TEST; ++t)
{
UserData Data[NUM_THREADS] = {};
int* cnt = new int(0);
unordered_set<string>* Container = new unordered_set<string>();
for (int i = 0; i < NUM_THREADS; ++i)
{
Data[i].Method = method;
Data[i].Name = Name;
Data[i].id = i;
Data[i].SharedCount = cnt;
Data[i].SharedContainer = Container;
hThread[i] = CreateThread(NULL, NULL,
SelectSimple ? ExecuteSimpleTask : ExecuteComplexTask,
(LPVOID)&Data[i], 0, &Data[i].ThreadId);
}
WaitForMultipleObjects(NUM_THREADS, hReadyThread, TRUE, INFINITE);
SetEvent(hWaitThread);
WaitForMultipleObjects(NUM_THREADS, hThread, TRUE, INFINITE);
for (int i = 0; i < NUM_THREADS; ++i)
{
if (printcount < 10)
{
++printcount;
cout << *Data[i].SharedCount << ", " << Data[i].SharedContainer->size() << " ";
}
Results.push_back(1000. * Data[i].Result);
}
delete cnt;
delete Container;
for (int i = 0; i < NUM_THREADS; ++i)
{
CloseHandle(hThread[i]);
}
for (int i = 0; i < NUM_THREADS; ++i)
{
ResetEvent(hReadyThread[i]);
}
ResetEvent(hWaitThread);
}
delete method;
auto& record = stats[sel];
CalculateMeanAndVariance(Results, record.mean, record.var, record.max, record.min);
}
printf("\n[%s]===========================================================================\n", SelectedTask.c_str());
for (int i = 0; i < 5; ++i)
{
printf("[%d][%15s] Mean : %5.2lfms, Var : %5.2lfms, Min : %5.2lfms, Max : %5.2lfms\n",\
i+1, stats[i].Name.c_str(), stats[i].mean, stats[i].var, stats[i].min, stats[i].max);
}
return 0;
}
void GenerateString()
{
for (int i = 0; i < NUM_LOOP_HARD; ++i)
{
string key = "";
int n = 0;
while (n < 64)
{
key.push_back(rand() % 128);
++n;
}
RandomStrings.push_back(std::move(key));
}
}
'Computer Science 기본 지식 > 운영체제' 카테고리의 다른 글
| [C++ Thread] Lock Free Programming - (2) Lock Free Queue (0) | 2021.10.18 |
|---|---|
| [C++ Thread] Lock-Free Programming - (1) Lock Free ? / Lock Free Stack (1) | 2021.10.13 |
| [Windows] 완료 루틴 (Completion Routine)과 APC (Asynchronous Procedure Call) (0) | 2021.10.04 |
| [Windows] Overlapped I/O (0) | 2021.10.04 |
| [운영체제] OS관련 용어 (0) | 2021.10.04 |