다음 글을 참고하였습니다.
www.codeproject.com/Articles/184046/Spin-Lock-in-C
mutex나 critical section과 같은 원시 동기화 객체를 쓰는 경우, 다음의 일련의 사건들이 두 스레드 사이에서 일어난다.
1) Thead 1이 락 L을 획득하고 실행한다.
2) Thread 2가 락 L을 획득하려 하지만, 이미 소유자가 있기 때문에 차단당하고 문맥 교환을 일으킨다.
3) Thread 1이 락 L을 반납한다. 이 행동은 커널 모드에서 스레드 2에게 알림(Signal)을 주게 된다.
4) Thread 2가 깨어나고 락 L을 획득하고 문맥 교환을 일으킨다.
원시 동기화 객체를 사용하는 경우 최소 두 번의 문맥 교환이 포함된다. 스핀 락을 사용할 경우 이러한 값비싼 문맥 교환과 커널 모드 진입을 없앨 수 있다.
현대 하드웨어는 여러 원자적 연산을 제공하는데, 그중 하나가 Compare and Swap (CAS) 연산이다. CAS 연산은 어떤 메모리에 대해 주어진 비교값과 같으면 새로운 값으로 쓰는(Write) 원자적 연산이다. Win32 시스템에서는 interlocked 연산이라고도 한다. Interlocked 함수와 함께, 응용 프로그램은 비교와 저장을 가로챌 수 없는 연산으로 구현할 수 있다.
Interlocked 함수를 쓴다면, 문맥 교환과 커널 모드 진입이 없는 lock free 동기화를 구현할 수 있다. 멀티 프로세서 장치에서, 스핀 락(busy waiting의 한 종류)은 문맥 교환에 드는 수천 CPU 사이클을 피할 수 있다.
단점으로는, 만약 오랜 시간 동안 소유되고 있다면 다른 스레드가 락을 얻고 진입할 기회를 방해하므로 무용지물이 된다.
class Lock
{
public:
volatile int dest = 0;
int exchange = 100;
int compare = 0;
void acquire()
{
while (true)
{
if (_InterlockedCompareExchange(&dest, exchange, compare) == 0)
{
// locked acquire
break;
}
}
}
// release the lock
void release()
{
// lock released
dest = 0;
}
};스레드 T1이 먼저 acquire()에서 락을 얻었다면, dest 값은 100으로 바뀌게 된다. 스레드 T2가 진입하려고 하면 dest는 100이므로 _InterlockedCompareExchange는 실패하고 계속 while문으로 체크를 하게 된다. T1 스레드가 release()를 호출하고 dest를 0으로 설정해야 T2가 락을 획득할 수 있다. acquire를 호출한 스레드만 release를 호출할 수 있으므로 상호 배제가 보장된다.
위 스핀 락 구현은 실제로 쓰기 적절하지 않은데, CPU 사이클을 소모하는 바쁜 대기를 수행하기 때문이다. (스레드는 프로세서에 스케줄 되어있는 상태이다.) 또 다른 스피닝의 단점은 InterlockedCompareExchange가 계속 메모리를 접근하면서 값을 비교하기 때문에 시스템 버스 통신에 부하를 준다.
단일 코어 장치에서는 spin wait은 CPU의 낭비이며 다른 스레드 T2는 심지어 spinning 스레드가 커널에 의해 교환될 때 까지 스케줄 되지 않을 수 도 있다.
지금까지 이러한 구현은 좋지 않다. 범용 목적의 스핀락은 꽤 오랜 시간 동안 스핀 되는 최악의 시나리오까지 고려하여 구현해야 한다.
Yield Processor
Win32 함수 YieldProcessor()는 nop이라는 명령어를 프로세서에게 산출한다. 이것은 프로세서가 이 코드가 현재 스핀 wait 중이며, 프로세서를 다른 다른 논리 프로세서에게 양보함으로 다른 논리 프로세서가 계산을 진행하게끔 한다.
Switch to Another Thread
spinning 중인 스레드가 타임 퀀텀에 가까운 시간을 소비하였을 때, 때때로 문맥 교환을 강제할 필요가 있을 것이다. 함수 SwichToThread()는 호출 스레드의 타임 퀀텀을 포기하고 다른 준비 상태의 스레드가 동작할 수 있도록 한다. 문맥 교환이 일어나면 True를 아니라면 False를 반환한다.
Sleeping
SwichToThread()는 실행을 위해 시스템에 있는 모든 스레드를 고려하지 않을 수 있다. 따라서 Sleep()이나 SleepEx()으로 스레드를 재울 수도 있다. Sleep(0)는 현재 스레드보다 우선순위에 있는 스레드가 있을 시에만 문맥 교환이 일어나게 한다.
다른 고려사항
pure spin lock은 락이 매우 짧은 시간에만 획득될 때 효과적이다. 임계 구역이 10 명령어를 넘지 않고 실용적으로 단순한 메모리 할당이나 가상 호출 혹은 file I/O는 10 명령어를 넘어간다.
당연 단일 프로세서 환경에서 스핀 락을 쓰는 것은 낭비이다.
간단한 예제
참고 사이트에 있는 코드입니다.
namespace LockFree
{
const unsigned int YIELD_ITERATION = 30; // yeild after 30 iterations
const unsigned int MAX_SLEEP_ITERATION = 40;
const int SeedVal = 100;
// This class acts as a synchronization object similar to a mutex
struct tSpinLock
{
volatile LONG dest;
LONG exchange;
LONG compare;
tSpinLock(){
dest = 0;
exchange = SeedVal;
compare = 0;
}
};
//
// This class provides wait free locking functionalities
class tSpinWait
{
public:
tSpinWait(){ m_iterations = 0;}
inline bool HasThreasholdReached() { return (m_iterations >= YIELD_ITERATION); }
void Lock(tSpinLock &LockObj);
void Unlock(tSpinLock &LockObj);
private:
tSpinWait(const tSpinWait&);
tSpinWait& operator=(const tSpinWait&);
private:
unsigned int m_iterations;
};
};- tSpinLock 구조체는 기본 스핀 락을 위한 값을 저장할 수 있다. dest는 volatile, 메모리상 변수이다.
- tSpwinWait는 Lock과 Unlock 인터페이스만 정의한다. 실제 락 객체를 전달해야 한다.
-- Lock 연산
void tSpinWait::Lock(tSpinLock &LockObj)
{
m_iterations = 0;
while(true)
{
// A thread alreading owning the lock shouldn't be allowed to wait to acquire the lock - reentrant safe
if(LockObj.dest == GetCurrentThreadId())
break;
/*
Spinning in a loop of interlockedxxx calls can reduce the available memory bandwidth and slow
down the rest of the system. Interlocked calls are expensive in their use of the system memory
bus. It is better to see if the 'dest' value is what it is expected and then retry interlockedxx.
*/
if(InterlockedCompareExchange(&LockObj.dest, LockObj.exchange, LockObj.compare) == 0)
{
//assign CurrentThreadId to dest to make it re-entrant safe
LockObj.dest = GetCurrentThreadId();
// lock acquired
break;
}
// spin wait to acquire
while(LockObj.dest != LockObj.compare)
{
if(HasThreasholdReached())
{
if(m_iterations + YIELD_ITERATION >= MAX_SLEEP_ITERATION)
Sleep(0);
if(m_iterations >= YIELD_ITERATION && m_iterations < MAX_SLEEP_ITERATION)
{
m_iterations = 0;
SwitchToThread();
}
}
// Yield processor on multi-processor but if on single processor then give other thread the CPU
m_iterations++;
if(Helper::GetNumberOfProcessors() > 1) { YieldProcessor(/*no op*/); }
else { SwitchToThread(); }
}
}
}spin wait 상태에서 다음 파라미터들이 쓰이는데
- YIELD_ITERATION (30) : 문맥 교환을 강제하기 전에 30번 정도 Sleep(0)를 통해 우선순위 스레드가 있는지 확인하고 있다면 문맥 교환이 일어나게 해 준다.
- MAX_SLEEP_ITERATION (40): 40번을 넘어가면 문맥 교환을 강제한다.
또한 spin wait 상태에서 단일 프로세서 장치이면 바로 문맥 교환을 강제한다.
-- Unlock 연산
void tSpinWait::Unlock(tSpinLock &LockObj)
{
if(LockObj.dest != GetCurrentThreadId())
throw std::runtime_error("Unexpected thread-id in release");
// lock released
InterlockedCompareExchange(&LockObj.dest, LockObj.compare, GetCurrentThreadId());
}
//- dest를 compare 값으로 바꾸기 위해 원자적 연산 InterlockedCompareExchange를 이용해야 한다.
Mutex 대신 Spinlock을 사용하는 이유에 대하여
stackoverflow.com/questions/5869825/when-should-one-use-a-spinlock-instead-of-mutex
배경
한 스레드가 뮤 텍스를 잠그려고 다른 스레드가 이미 소유중이라 실패하게 된다. 그 스레드는 잠자게 되고 다른 스레드가 실행될 수 있도록 한다. 기존 뮤텍스를 소유하던 스레드가 다 사용하고 반납할 때까지, 해당 스레드는 계속 잠자는 상태일 것이다.
스핀 락의 경우 락을 시도하고 실패하면 성공할 때 까지 계속 시도하게 된다. 주어진 타임 퀀텀을 다 사용하지 않는 이상 다른 스레드로 문맥 교환이 일어나는 일은 발생하지 않는다.
문제
뮤 텍스에서 스레드를 잠자는 상태로 만들고 다시 깨우는 것은 굉장히 비싼 연산인데, 이 연산은 굉장히 많은 CPU 사이클을 소모하게 된다. 만약 뮤 텍스가 아주 잠깐 동안만 잠긴 상황이라면, 다른 모든 스레드들이 잠자고 다시 깨어나는 비용이 스핀 락에서 폴링 하는 비용보다 비쌀 수 있다. 한편, 폴링은 또한 락이 오랫동안 소유중 일 때 CPU 자원을 소모함으로 낭비를 발생시킬 수 있다. 이 때는 스레드를 차라리 재우는 것이 나을 수 있다.
해결책
싱글 코어 장치에서 스핀 락을 쓰는 것은 의미가 없다. 왜냐하면 CPU 코어 하나를 사용하여 락을 기다리는 것이 결국 다른 스레드가 락을 소유하고 있기 때문인데, 이는 어차피 문맥 교환을 요구하기 때문이다. 한편, 멀티 코어 장치에서 스핀락을 사용하는 것은 CPU 자원 낭비 말고는 아무것도 낭비하지 않는다. 만약 스레드 하나가 다 사용하고 락을 반납했다면, 잠자지 않고 체크 중이던 다른 스레드가 바로 락을 얻고 실행을 할 수 있다.
멀티 코어 시스템에서 많은 락에 의해 잠자고 다시 깨우는 일은 전체 실행시간을 저하시킬 만큼 비용이 들 수 있다. 스핀 락은 타임 퀀텀과 비슷한 시간 동안 락을 얻을 수 있는 기회를 주기 때문에 처리량이 더 늘어나게 된다.
실제 사용
실제로는 현대 운영체제는 하이브리드 뮤 텍스와 스핀 락을 사용한다. 멀티 코어 시스템에서 하이브리드 뮤 텍스는 락을 잠글 수 없을 때 바로 잠자지 않고 (곧 락을 얻을 수 있을지 모르기 때문에) 뮤텍스는 초기에 스핀 락처럼 행동한다. 일정 시간 동안 계속 잠글 수 없다면, 그제야 스레드를 재운다.
하이브리드 스핀 락은 초기에는 스핀 락처럼 작동하지만 CPU 소모 시간을 줄이기 위해 한발 물러선 행동을 취할 수 있다. 실제로 스레드를 재우는 것은 아니지만 양보 기법으로 다른 스레드가 CPU를 스케줄받아 명령어를 실행하도록 두는 것이며 결국 스핀 락이 열릴 수 있는 확률을 높인다. (여전히 스레드 스위칭 비용은 들지만 잠자고 깨우는 비용은 없다.)
요약
의심 없이 뮤 텍스를 쓰라는 의미, 현대 시스템에서는 뮤 텍스가 초기에는 스핀 락처럼 동작하게 만들기 때문이다. 스핀 락이 더 나은 선택일 수 도 있지만 직접 락 객체를 만들어서 스핀 락이던 뮤 텍스던 적용을 하여 직접 성능을 비교해보길 바란다.
간단한 비유를 통한 두 사용법
- 인기 있는 음식점이나 패밀리 레스토랑에서 대기하는 경우 (고전적인 동기화 원시 객체의 사용)
식당에 입장하여 식사를 하기 위해서는 기존 손님이 나와야 한다. 패밀리 레스토랑에 운이 없게도 붐비는 타이밍에 가게 되어 대기시간이 1시간이 넘게 걸리는 상황이라 하자. 이런 경우 보통 대기 장소에서 대기하게 되는데(Sleep) 웨이터(OS)가 건네준 진동 알람 디바이스를 받아 알람이 울릴 때까지 기다리는 것이다. 한편, 계속 웨이터에게 자리가 있는지 물어봤자 없을 확률이 더 크기 때문에 다른 일을 해야 하는 웨이터 기분만 상하게 할 뿐이다. 이럴 때는 웨이터를 믿고 알려줄 때까지 기다리는 것이 현명하다.
- 이벤트성으로 온라인으로 기차표를 구하거나 수강신청을 하는 경우 (스핀 락)
이러한 경우에 기차표를 사거나 수강신청을 하는 작업은 굉장히 빨리 일어난다. 하지만 전산 서버의 처리 한계로 동시에 접속할 수 있는 클라이언트 수가 제한되어 있다 하자. 또한 우리 예약 시스템은 애석하게도 누른 순서대로 들여보내는 것이 아니라 입장 시도의 가능 여부만 알려준다. 비난 받을 만한 시스템에도 클라이언트는 어쩔 수 없이 새로 고침 하며 입장 시도를 하고 (Polling) 운이 좋게 입장을 한다면 서비스를 제공받을 것이다. 만약 시스템이 현재 입장 가능하다고 알려준다면 괜찮을까?(Sleep-Wait) 아니, 이미 불만 가득한 입장 시스템이 지연 없이 알림을 제공한다 믿을 수 없다. 알려준 상황에서는 이미 이전 시점에 여유가 있었다는 얘기고 입장 시도 순간에는 다른 사람이 이미 입장해있을 수도 있다. 따라서 입장 시스템(OS)이 알려주는 신호를 받지 않고 그냥 계속 시도하는 것이 낫다.
'Computer Science 기본 지식 > 운영체제' 카테고리의 다른 글
| [운영체제] OS관련 용어 (0) | 2021.10.04 |
|---|---|
| [C++ Thread] Windows API에서 쓰레드 생성 (0) | 2021.06.01 |
| [C++ Thread] 쓰레드 풀 Thread Pool (0) | 2021.04.30 |
| [C++ Thread] 약속과 미래 객체, std::promise / std::future (0) | 2021.04.30 |
| [C++ Thread] memory order 와 atomic 객체 (0) | 2021.04.27 |