비교 및 스왑 작동 방식

비교 및 스왑 작동 방식

비교 및 스왑이 원자성을 보장한다는 게시물을 꽤 읽어 보았지만 여전히 어떻게 하는지 알 수 없습니다.비교 및 스왑을 위한 일반 의사 코드는 다음과 같습니다.

int CAS(int *ptr,int oldvalue,int newvalue)
{
   int temp = *ptr;
   if(*ptr == oldvalue)
       *ptr = newvalue
   return temp;
}

이것이 어떻게 원자성을 보장합니까?예를 들어, 만약 내가 이것을 사용해서 뮤텍스를 구현한다면,

void lock(int *mutex)
{  
    while(!CAS(mutex, 0 , 1));
}

이것은 어떻게 두 개의 스레드가 동시에 뮤텍스를 획득하는 것을 막습니까?어떤 조언이라도 해주시면 정말 감사하겠습니다.

"일반 의사 코드"는 CAS(비교 및 스왑) 구현의 실제 코드가 아닙니다.특수 하드웨어 명령은 CPU의 특수 원자 하드웨어를 활성화하는 데 사용됩니다.예를 들어, x86에서LOCK CMPXCHG(http://en.wikipedia.org/wiki/Compare-and-swap) 를 사용할 수 있습니다.

예를 들어 gcc에는__sync_val_compare_and_swap()내장 - 하드웨어별 원자 CAS를 구현합니다.폴 E의 신선한 멋진 책에서 이 작전에 대한 설명이 있습니다.McKenny(Parallel Programming은 어려운가, 그리고 만약 그렇다면, 당신은 그것에 대해 무엇을 할 수 있는가?, 2014), 섹션 4.3 "원자 연산", 31-32페이지.

원자 작동 위에 더 높은 수준의 동기화를 구축하는 방법에 대해 더 자세히 알고 싶으며 활성 회전 시 스핀락 및 연소 CPU 사이클로부터 시스템을 보호하려면 다음 정보를 읽을 수 있습니다.futex리눅스의 매커니즘.Futexes에 대한 첫 번째 논문은 Futexes가 Ulrich Drepper 2011에 의해 까다롭다는 것입니다. 다른 하나는 LWN 기사 http://lwn.net/Articles/360699/ 입니다. (그리고 역사적인 것은 Fuques, Futexes and Furwocks입니다.) Linux에서의 빠른 사용자랜드 잠금, 2002)

Ulrich가 설명한 Mutex 잠금은 "빠른 경로"(mutex가 잠겨 있지 않고 스레드만 잠그려는 경우)에 대해 atomic 연산만 사용하지만, mutex가 잠겨 있으면 스레드가 futex(FUTEX_WAIT...)를 사용하여 sleep 상태로 전환됩니다(그리고 atom 연산을 사용하여 mutex 변수를 표시하여 잠금 해제 스레드에 "가 있음을 알립니다.누군가가 이 뮤텍스에서 기다리고 있다"고 말하고 있으므로 잠금 해제자는 futex(FUTEX_WAKE, ...)를 사용하여 그들을 깨워야 한다는 것을 알 수 있습니다.

두 개의 스레드가 잠금을 획득하는 것을 어떻게 방지합니까?뭐, 어느 하나의 스레드가 성공하면,*mutex될 것이다1, 따라서 다른 스레드의 CAS가 실패합니다(기대 값으로 호출되기 때문에)0보관함으로써 잠금이 해제됩니다.0인에*mutex.

기본적으로 ABA 위반이 필요하므로 CAS를 이상하게 사용하는 것입니다.일반적으로 단순한 원자 교환을 사용합니다.

while (exchange(mutex, 1) == 1) { /* spin */ }

// critical section

*mutex = 0;   // atomically

또는 약간 더 정교해지고 어떤 스레드에 잠금이 있는지에 대한 정보를 저장하려면 atomic-fetch-and-add로 트릭을 수행할 수 있습니다(예: Linux 커널 스핀락 코드 참조).

C에서는 CAS를 구현할 수 없습니다.조립 시 하드웨어 수준으로 이루어집니다.

언급URL : https://stackoverflow.com/questions/22339466/how-compare-and-swap-works