윈도우즈 원자 조작 메시지 대기열 구현

원자 조작은 스레드 동기화에서 매우 중요한 위치를 차지하는데, 스레드가 특정한 자원에 접근할 때 다른 스레드가 같은 시간에 이 자원에 접근할 수 없도록 보장한다.다음 코드를 예로 들면 다음과 같습니다.

// Define a global variable long g_x = 0; DWORD WINAPI ThreadFunc1(PVOID pvParam) { g_x ++; return 0; } DWORD WINAPI ThreadFunc2(PVOID pvParam) { g_x ++; return 0; }

g_x는 전역 변수로 선언되고 0으로 초기화되었습니다. 현재 만약 내가 두 개의 라인을 만들었다면, 하나는 ThreadFunc1을 실행하고, 다른 하나는 ThreadFunc2를 실행합니다.ThreadFunc1과 ThreadFunc2의 기능은 모두 gx 더하기 1.너는 ThreadFunc1과 ThreadFunc2가 돌아오면 gx의 값은 2이어야 하지만, 이것은 모든 가능한 결과 중의 하나일 뿐, 당신은 g 를 예측할 수 없습니다.x의 최종값.컴파일러는 gx++는 다음과 같은 어셈블리 코드를 생성합니다: MOV EAX, [g x];move the value in g_x into a register  INC EAX ; increase the value in the register  MOV [g_x], EAX ; store the new value back into g_x
두 스레드가 동시에 실행될 경우 MOV EAX, [g x],thread 1: move 0 into a register  INC EAX ; thread 1: increase the register to 1  MOV EAX, [g_x] ; thread 2: move 0 into the register again  MOV [g_x], EAX ; thread 1: move 0 into g_x  INC EAX ; thread 2: increase the register to 1  MOV [g_x], EAX ; thread 2: move 1 into g_x
위 코드 실행 후 gx의 최종치는 1이다!개발자들이 시스템 스케줄러에 관여할 수 없다는 사실이 놀랍다.사실, 100개의 라인이 동시에 g 를 실행해도x++,g_x의 최종치는 여전히 1일 수 있다!이것은 우리의 기대와는 거리가 멀다. 우리는 0이 두 번 증가한 결과가 컴파일러에 의한 코드의 영향을 받지 않고, CPU 스케줄링 라인의 행위에 영향을 받지 않으며, 컴퓨터 시스템에 설치된 CPU의 수량에 영향을 받지 않기를 바란다.다행히도, Windows는 일부 함수를 제공하여 우리의 코드가 예상하고 정확한 결과를 낼 수 있도록 보장한다.이 문제를 해결하기 위해서, 우리는 자증 조작이 원자라는 것을 보증해야 한다. 즉, 다른 라인에 의해 중단되지 않는다는 것이다.Windows에서 제공하는interlocked 함수족은 이를 위해 해결 방안을 제공합니다.Interlocked 함수족은 상당히 간단하고 이해하기 쉬우며 모든interlocked 함수는 매개 변수에 대한 조작이 원자적이다.예를 들어 다음과 같은 InterlockedExchangeAdd 및 InterlockedExchangeAdd64 함수가 있습니다.

LONG InterlockedExchangeAdd( PLONG volatile plAddend, LONG lIncrement); LONGLONG InterlockedExchangeAdd64( PLONGLONG volatile pllAddend, LONGLONG lIncrement);

우리는 위의 함수로 g 를 다시 쓸 수 있다x++ 작업:

long g_x = 0; DWORD WINAPI ThreadFunc1(PVOID pvParam){ InterlockedExchangeAdd(&g_x, 1); return 0; } DWORD WINAPI ThreadFunc2(PVOID pvParam){ InterlockedExchangeAdd(&g_x, 1); return 0; }

지금, gx의 자증은 원자이며, 그 최종치는 2이다.참고로 값을 1만 추가하면 InterlockedIncrement 함수를 사용할 수 있습니다.공유 변수를 수정하려는 모든 스레드는 간단한 C++ 산술 연산 대신 Interlocked 함수족을 호출해야 합니다.

// the long variable shared by many threads LONG g_x; // Incorrect way to increase the variable g_x ++; // Correct way to increase the variable InterlockedIncrement(&g_x);

Interlocked 함수족의 구현 세부 사항은 현재 CPU 플랫폼에 따라 달라집니다.x86 구조의 CPU에서 Interlocked 함수는 버스에 하드웨어 신호를 설정하여 다른 스레드가 잠긴 메모리 영역에 접근하지 못하게 합니다.Interlocked 함수족의 실현 세부 사항은 중요하지 않다. 중요한 것은 매개 변수에 대한 조작이 원자적이고 컴파일러와 CPU 구조, 수량의 영향을 받지 않는다는 것이다.Interlocked 함수족에 전달되는 변수 주소는 32비트/64비트로 정렬해야 하며 C가 실행될 때 제공되는aligned_malloc 및 alignedrealloc 함수로 지정된 자릿수로 정렬된 메모리 블록을 생성/재할당: void *aligned_malloc(size t size,size t alignment),size는 할당할 바이트의 수를 나타냅니다.alignment는 이 메모리 블록을 정렬하는 바이트의 경계입니다.alignment는 반드시 2의 배수여야 합니다.또한 Interlocked 함수족의 실행 속도는 상당히 빨라서 보통 50개의 CPU 주기를 초과하지 않고 사용자 모드와 핵 모드 사이를 변환할 필요가 없다(이런 변환을 실행하는 데 필요한 CPU 주기 수는 보통 1000보다 크다).
다음은 지정된 값을 대체하는 데 사용되는 interlocked 함수 세 개입니다.

LONG InterlockedExchange( PLONG volatile plTarget, LONG lValue); LONGLONG InterlockedExchange64( PLONGLONG volatile plTarget, LONGLONG lValue); PVOID InterlockedExchangePointer( PVOID* volatile ppvTarget, PVOID pvValue);

함수InterlockedExchange와 InterlockedExchangePointer는 두 번째 인자의 값으로 첫 번째 인자 주소의 값을 대체하고, 대체 과정은 원자 조작이다.32비트 응용 프로그램에서 함수는 32비트 값으로 32비트 값을 대체하고 64비트 응용 프로그램에서 InterlockedExchange는 32비트 값을 사용하지만 InterlockedExchangePointer는 64비트 값을 사용합니다.함수는 첫 번째 매개 변수 주소의 옛 값을 되돌려줍니다.InterlockedExchange는 스핀들 잠금을 작성할 때 유용합니다.

// Global variable indicating whether a shared resource is in user or not BOOL g_fResourceInUser = FALSE; void Func1() { // wait to access the resource while(InterlockedExchange(&g_fResourceInUse, TRUE) == TRUE) Sleep(0); // access the resource ... // reset the flag InterlockedExchange(&g_fResourceInUse, FALSE); }

위의 코드는 의미가 비교적 명확하여 더 이상 설명하지 않는다.자전거 자물쇠는 CPU 시간을 낭비할 수 있으니 주의해야 한다.스핀다운 루프의 CPU는 두 값을 계속해서 비교하여 스핀다운 루프를 결정해야 합니다.위 코드는 자전거 자물쇠를 사용하는 모든 라인의 우선순위가 같아야 한다. 그렇지 않으면 자전거 자물쇠 안에 있는 라인이 비교적 높은 우선순위를 가지면 CPU는 자전거 자물쇠를 사용하는 순환에 빠질 것이다. 또한 자전거 자물쇠를 사용하는 라인에 대해 SetProcessPriorityBoost/SetThreadPriorityBoost를 호출해서 시스템이 우선순위를 올리는 것을 금지한다.
자전거 자물쇠를 사용할 때 보호된 자원에 접근하는 시간은 가능한 한 짧아야 한다.더욱 효과적인 방법은 우선 자전거 자물쇠 대기를 사용하고 일정 시간이 지난 후에도 보호된 자원에 접근할 수 없으면 내부 핵 모드로 들어가 대기(이 때 스레드는 CPU 시간을 소모하지 않고 끊긴다)하는 것이다. 이것이 바로 임계구역(Critical Section)의 실현 원리이다.
다음은 마지막 교환 Interlocked 값 대체 함수입니다.

LONG InterlockedCompareExchange( PLONG plDestination, LONG lExchange, LONG lCompared); PVOID InterlockedCompareExchangePointer( PVOID* ppvDestination, PVOID pvExchange, PVOID pvCompared);

함수는 현재 값(plDestination/ppvDestination)과 lCompared/pvCompared를 비교하고 양자가 같을 때 현재 값은 lExchange/pvExchange로 대체됩니다. 그렇지 않으면 현재 값은 변하지 않고 함수는 현재 값의 이전 값을 되돌려줍니다.
위에서 설명한 것 외에 Windows는 일부 Interlocked 함수를 제공했지만 이러한 함수는 모두 위의 함수로 이루어진 것이다. 예를 들어 다음과 같다.

LONG InterlockedIncrement(PLONG plAddend); LONG InterlockedDecrement(PLONG plAddend);

이 두 함수는 분명히 InterlockedExchangeAdd에서 실현할 수 있다.이외에도 Interlocked Compare Exchange 64를 바탕으로 OR, XOR 및 AND 작업에 사용되는 Interlocked 함수, 예를 들어 Interlocked And64:

LONGLONG InterlockedAnd64(LONGLONG* Destination, LONGLONG value) { LONGLONG old = *Destination; do { old = *Destination; } while(InterlockedCompareExchange64(Destination, old&value, old) != old); return old; }                  ： LONGLONG InterlockedAnd64(LONGLONG* Destination, LONGLONG value) { return InterlockedCompareExchange64(Destination, (*Destination)&value, *Destination); }

Windows XP를 시작으로 정수와 부울 값에 대한 원자 조작을 제외하고 개발자는 새로운 함수를 사용하여'인터록 사이드 링크드 리스트'라고 불리는 스택을 조작할 수 있다.스택에 있는 각 작업(예: 스택 압축, 플라이아웃)은 원자 작업이며 다음 표에는 이러한 함수가 나열되어 있습니다.
함수명
묘사
InitializeSListHead
Creates an empty stack
InterlockedPushEntrySList
Adds an element on top of the stack
InterlockedPopEntrySList
Removes the top element of the stack and returns it
InterlockedFlushSList
Empties the stack
QueryDepthSList
Returns the number of elements stored in the stack
인터넷에는 다선정에서 원자가 자물쇠보다 효율이 훨씬 높다는 논문이 있다.테스트 결과는 속도와 붕괴의 운행 시간에서 볼 때 자물쇠를 잠그는 방식보다 훨씬 낫다.
1200개의 라인을 열었는데 테스트 결과의 운행 속도가 비교적 빠르고 유일하게 부족한 점은 cpu를 차지하는 것이 비교적 커서 100%에 이르렀기 때문에 견디기 어려워서 어떤 방법으로 해결해야 할지 모르겠다.각 분야의 소인들이 해결 방안을 제시하는 것을 환영합니다.감사합니다.

class UrlQueue
{
public:
	static UrlQueue *GetInstance()
	{
		static UrlQueue urlQueue;//        
		return &urlQueue; 
	} 
    UrlQueue(int maxsize=1000)
	{    // Initialize the list header to a MEMORY_ALLOCATION_ALIGNMENT boundary.
		pListHead = (PSLIST_HEADER)_aligned_malloc(sizeof(SLIST_HEADER),
		MEMORY_ALLOCATION_ALIGNMENT);
		if( NULL == pListHead )
		{
			printf("Memory allocation failed.
");
			return;
		}
		InitializeSListHead(pListHead);
	}

    ~UrlQueue()
	{
		_aligned_free(pListHead);
	}

    void Push(const char *val)//       
	{
		int num =  QueryDepthSList(pListHead);
		while(num>=1000)
		{
			num = QueryDepthSList(pListHead);
			if(num<1000) break;;
		}
		pProgramItem = (PPROGRAM_ITEM)_aligned_malloc(sizeof(PROGRAM_ITEM),MEMORY_ALLOCATION_ALIGNMENT);
        if( NULL == pProgramItem )
        {
            printf("Memory allocation failed.
");
            return ;
        }
        pProgramItem->url = val;
        pFirstEntry = InterlockedPushEntrySList(pListHead, 
                       &(pProgramItem->ItemEntry)); 
	}
   

void Pop(const char ** url)//       
{
	 pListEntry = InterlockedPopEntrySList(pListHead);

        if( NULL == pListEntry )
        {
            printf("List is empty.
");
            return ;
        }
  
        pProgramItem = (PPROGRAM_ITEM)pListEntry;
		 
		*url = pProgramItem->url;
		_aligned_free(pListEntry);
}


private:
	typedef struct _PROGRAM_ITEM 
	{
		SLIST_ENTRY ItemEntry;
		const char* url; 
	} PROGRAM_ITEM, *PPROGRAM_ITEM;
    PSLIST_ENTRY pFirstEntry, pListEntry;
    PSLIST_HEADER pListHead;
    PPROGRAM_ITEM pProgramItem;
};