C ++ 11의 std :: atomic :: compare_exchange_weak () 이해

C ++ 11의 std :: atomic :: compare_exchange_weak () 이해

---

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak()C ++ 11에서 제공되는 비교-교환 프리미티브 중 하나입니다. 객체의 값이 같더라도 false를 반환한다는 점 에서 약 합니다 expected. 이는 일련의 명령어 (x86의 명령어 대신)가이를 구현하는 데 사용되는 일부 플랫폼에서 가짜 오류 때문입니다. 이러한 플랫폼에서 컨텍스트 전환, 다른 스레드에 의한 동일한 주소 (또는 캐시 라인) 다시로드 등은 기본 요소에 실패 할 수 있습니다. 그건 spurious는 (동일하지 않은 객체의 값이 아니다로서 expected동작 실패). 대신 일종의 타이밍 문제입니다.

그러나 나를 당혹스럽게하는 것은 C ++ 11 표준 (ISO / IEC 14882)에서 말한 것입니다.

29.6.5 .. 스퓨리어스 실패의 결과는 약한 비교 및 ​​교환의 거의 모든 사용이 루프에있게된다는 것입니다.

거의 모든 용도 에서 루프에 있어야하는 이유는 무엇 입니까? 이것은 가짜 실패로 인해 실패 할 때 반복된다는 의미입니까? 그렇다면 compare_exchange_weak()루프를 직접 사용 하고 작성 해야하는 이유는 무엇입니까? 우리는 compare_exchange_strong()가짜 실패를 제거해야한다고 생각하는 것을 사용할 수 있습니다 . 의 일반적인 사용 사례는 compare_exchange_weak()무엇입니까?

또 다른 질문이 있습니다. 그의 저서 "C ++ Concurrency In Action"에서 Anthony는 다음과 같이 말합니다.

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

!expected루프 상태에있는 이유는 무엇 입니까? 모든 스레드가 굶어 죽고 얼마 동안 진행되지 않도록 방지하기 위해 있습니까?

편집 : (마지막 질문 하나)

단일 하드웨어 CAS 명령어가없는 플랫폼에서는 약한 버전과 강력한 버전이 모두 LL / SC (예 : ARM, PowerPC 등)를 사용하여 구현됩니다. 그렇다면 다음 두 루프 사이에 차이점이 있습니까? 그 이유가 있다면? (나에게 비슷한 성능을 가져야합니다.)

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

여러분 모두가 루프 내부에 성능 차이가있을 수 있다고 언급하는 마지막 질문을 드리겠습니다. C ++ 11 표준 (ISO / IEC 14882)에서도 언급됩니다.

비교 및 교환이 루프에있을 때 약한 버전은 일부 플랫폼에서 더 나은 성능을 제공합니다.

그러나 위에서 분석 한 것처럼 루프의 두 버전은 동일하거나 유사한 성능을 제공해야합니다. 내가 그리워하는 것은 무엇입니까?

---

루프에서 교환하는 이유는 무엇입니까?

일반적으로 작업을 진행하기 전에 작업이 완료되기를 원하므로 compare_exchange_weak성공할 때까지 교환을 시도하도록 루프에 넣 습니다 (즉, 반환 true).

또한 compare_exchange_strong루프에서 자주 사용됩니다. 가짜 실패로 인해 실패하지는 않지만 동시 쓰기로 인해 실패합니다.

weak대신 사용 하는 이유 는 strong무엇입니까?

매우 쉬움 : 스퓨리어스 실패는 자주 발생하지 않으므로 성능에 큰 타격을주지 않습니다. 반대로 이러한 실패를 허용하면 일부 플랫폼 weak에서 버전을 훨씬 더 효율적으로 구현할 수 있습니다 (와 비교하여 strong). strong항상 가짜 실패를 확인하고이를 숨겨야합니다. 이것은 비싸다.

따라서 일부 플랫폼 weak보다 훨씬 빠르기 때문에 사용 strong됩니다.

언제 사용해야 weak언제 strong?

참조 할 때 사용하는 힌트를 언급 weak할 때 사용하는 방법과 strong:

비교 및 교환이 루프에있을 때 약한 버전은 일부 플랫폼에서 더 나은 성능을 제공합니다. 약한 비교 및 ​​교환에는 루프가 필요하고 강한 것은 필요하지 않을 때 강한 것이 바람직합니다.

따라서 대답은 기억하기 매우 간단 해 보입니다. 가짜 실패 때문에 루프를 도입해야한다면 그렇게하지 마십시오. 를 사용하십시오 strong. 어쨌든 루프가 있으면 weak.

!expected예에있는 이유

상황과 원하는 의미에 따라 다르지만 일반적으로 정확성을 위해 필요하지 않습니다. 생략하면 매우 유사한 의미가 생성됩니다. 다른 스레드가 값을로 재설정 할 수있는 경우에만 false의미 체계가 약간 다를 수 있습니다 (하지만 원하는 경우 의미있는 예제를 찾을 수 없습니다). 자세한 설명은 Tony D.의 설명을 참조하십시오.

다른 쓰레드가 쓸 때의 빠른 트랙 일 뿐이다 true. 그러면 우리는 true다시 쓰려고하는 대신 중단한다 .

마지막 질문에 대해

그러나 위에서 분석 한 것처럼 루프의 두 버전은 동일하거나 유사한 성능을 제공해야합니다. 내가 그리워하는 것은 무엇입니까?

에서 위키 백과 :

문제의 메모리 위치에 대한 동시 업데이트가없는 경우 LL / SC의 실제 구현이 항상 성공하는 것은 아닙니다. 컨텍스트 전환, 다른로드 링크 또는 (많은 플랫폼에서) 다른로드 또는 저장 작업과 같은 두 작업 간의 예외적 인 이벤트로 인해 저장 조건이 허위로 실패합니다. 메모리 버스를 통해 브로드 캐스트되는 업데이트가 있으면 이전 구현이 실패합니다.

따라서 LL / SC는 예를 들어 컨텍스트 전환에서 가짜로 실패합니다. 이제 강력한 버전은 "자신의 작은 루프"를 가져 와서 가짜 오류를 감지하고 다시 시도하여이를 숨 깁니다. 이 자체 루프는 스퓨리어스 실패 (및이를 마스킹)와 동시 액세스로 인한 실패 (값이 반환 됨)를 구별해야하기 때문에 일반적인 CAS 루프보다 더 복잡합니다 false. 약한 버전에는 이러한 자체 루프가 없습니다.

두 예제 모두에서 명시적인 루프를 제공하기 때문에 강력한 버전에 대해 작은 루프가 필요하지 않습니다. 결과적으로 strong버전이 있는 예 에서는 실패 확인이 두 번 수행됩니다. 한 번 compare_exchange_strong(스퓨리어스 실패와 동시 액세스를 구분해야하기 때문에 더 복잡함) 및 루프별로 한 번. 이 값 비싼 수표는 불필요하며 weak여기에서 더 빠른 이유 가 있습니다.

또한 귀하의 주장 (LL / SC) 은이를 구현할 수 있는 하나의 가능성 일뿐 입니다. 명령어 세트가 다른 플랫폼이 더 많이 있습니다. 또한 (더 중요한 것은) 가능한 모든 데이터 유형에std::atomic 대한 모든 작업을 지원해야 하므로 천만 바이트 구조체를 선언하더라도 여기에서 사용할 수 있습니다 . CAS가있는 CPU에서도 천만 바이트를 CAS 할 수 없으므로 컴파일러는 다른 명령어를 생성합니다 (잠금 획득, 비 원자 비교 및 ​​스왑, 잠금 해제). 이제 천만 바이트를 교환하는 동안 얼마나 많은 일이 발생할 수 있는지 생각해보십시오. 따라서 8 바이트 교환에서는 스퓨리어스 오류가 매우 드물지만이 경우에는 더 일반적 일 수 있습니다.compare_exchange

간단히 말해서, C ++는 "최선의 노력"하나 ( weak)와 "그 사이에 얼마나 많은 나쁜 일이 일어날 지에 관계없이 확실히 할 것입니다" ( ) 라는 두 가지 의미를 제공합니다 strong. 다양한 데이터 유형과 플랫폼에서 이것이 어떻게 구현되는지는 완전히 다른 주제입니다. 특정 플랫폼의 구현에 멘탈 모델을 묶지 마십시오. 표준 라이브러리는 사용자가 알고있는 것보다 더 많은 아키텍처에서 작동하도록 설계되었습니다. 우리가 도출 할 수있는 유일한 일반적인 결론은 성공을 보장하는 것이 실패 가능성에 대한 여지를 남기고 시도하는 것보다 일반적으로 더 어렵습니다 (따라서 추가 작업이 필요할 수 있음).

---

거의 모든 용도 에서 루프에 있어야하는 이유는 무엇 입니까?

반복하지 않고 실패하면 프로그램이 유용한 작업을 수행하지 않았기 때문에 원자 객체를 업데이트하지 않았고 현재 값이 무엇인지 알지 못합니다 (수정 : Cameron의 아래 주석 참조). 통화가 유용한 일을하지 못한다면 그 일의 요점은 무엇입니까?

이것은 가짜 실패로 인해 실패 할 때 반복된다는 의미입니까?

예.

그렇다면 compare_exchange_weak()루프를 직접 사용 하고 작성 해야하는 이유는 무엇입니까? 우리는 가짜 실패를 제거해야한다고 생각하는 compare_exchange_strong ()을 사용할 수 있습니다. compare_exchange_weak ()의 ​​일반적인 사용 사례는 무엇입니까?

일부 아키텍처 compare_exchange_weak에서는 더 효율적이고 스퓨리어스 오류는 매우 드물기 때문에 약한 형식과 루프를 사용하여 더 효율적인 알고리즘을 작성하는 것이 가능할 수 있습니다.

일반적으로 알고리즘이 반복 될 필요가없는 경우 대신 강력한 버전을 사용하는 것이 좋습니다. 스퓨리어스 실패에 대해 걱정할 필요가 없기 때문입니다. 강력한 버전에서도 루프가 필요하다면 (많은 알고리즘은 어쨌든 루프가 필요합니다), 약한 형식을 사용하는 것이 일부 플랫폼에서 더 효율적일 수 있습니다.

!expected루프 상태에있는 이유는 무엇 입니까?

값이 true다른 스레드 에 의해 설정되었을 수 있으므로 설정하려고 계속 반복하는 것을 원하지 않습니다.

편집하다:

그러나 위에서 분석 한 것처럼 루프의 두 버전은 동일하거나 유사한 성능을 제공해야합니다. 내가 그리워하는 것은 무엇입니까?

스퓨리어스 실패가 가능한 플랫폼에서는 스퓨리어스 실패 compare_exchange_strong를 확인하고 재 시도하기 위해 구현 이 더 복잡 해야한다는 것은 분명합니다 .

약한 형식은 가짜 실패시 반환되며 재 시도하지 않습니다.

---

다양한 온라인 리소스 (예 : this one and this one ), C ++ 11 Standard 및 여기에 제공된 답변을 살펴본 후 직접 답변하려고합니다 .

관련 질문이 병합되고 (예 : " 왜! expected? "가 "왜 compare_exchange_weak ()를 루프에 넣었 습니까? ") 병합되고 그에 따라 답변이 제공됩니다.

---

compare_exchange_weak ()이 거의 모든 용도에서 루프에 있어야하는 이유는 무엇입니까?

전형적인 패턴 A

원자 변수의 값을 기반으로 원자 업데이트를 수행해야합니다. 실패는 변수가 원하는 값으로 업데이트되지 않았으며 다시 시도하려고 함을 나타냅니다. 참고 우리가 정말 동시 쓰기 또는 가짜 오류로 인해 실패 여부에 대해 걱정하지 않는다. 그러나 우리는 이러한 변화를 만드는 것이 우리 라는 사실에 관심 이 있습니다.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

실제 예는 여러 스레드가 단일 연결 목록에 요소를 동시에 추가하는 것입니다. 각 스레드는 먼저 헤드 포인터를로드하고 새 노드를 할당하고이 새 노드에 헤드를 추가합니다. 마지막으로 새 노드를 헤드와 교체하려고합니다.

또 다른 예는 std::atomic<bool>. 루프 current를 처음 설정 true하고 종료 하는 스레드에 따라 한 번에 최대 하나의 스레드가 임계 섹션에 들어갈 수 있습니다 .

전형적인 패턴 B

This is actually the pattern mentioned in Anthony's book. In contrary to pattern A, you want the atomic variable to be updated once, but you don't care who does it. As long as it's not updated, you try it again. This is typically used with boolean variables. E.g., you need implement a trigger for a state machine to move on. Which thread pulls the trigger is regardless.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Note that we generally cannot use this pattern to implement a mutex. Otherwise, multiple threads may be inside the critical section at the same time.

That said, it should be rare to use compare_exchange_weak() outside a loop. On the contrary, there are cases that the strong version is in use. E.g.,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak is not proper here because when it returns due to spurious failure, it's likely that no one occupies the critical section yet.

Starving Thread?

One point worth mentioning is that what happens if spurious failures continue to happen thus starving the thread? Theoretically it could happen on platforms when compare_exchange_XXX() is implement as a sequence of instructions (e.g., LL/SC). Frequent access of the same cache line between LL and SC will produce continuous spurious failures. A more realistic example is due to a dumb scheduling where all concurrent threads are interleaved in the following way.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Can it happen?

It won't happen forever, fortunately, thanks to what C++11 requires:

Implementations should ensure that weak compare-and-exchange operations do not consistently return false unless either the atomic object has value different from expected or there are concurrent modifications to the atomic object.

Why do we bother use compare_exchange_weak() and write the loop ourselves? We can just use compare_exchange_strong().

It depends.

Case 1: When both need to be used inside a loop. C++11 says:

When a compare-and-exchange is in a loop, the weak version will yield better performance on some platforms.

On x86 (at least currently. Maybe it'll resort to a similiar scheme as LL/SC one day for performance when more cores are introduced), the weak and strong version are essentially the same because they both boil down to the single instruction cmpxchg. On some other platforms where compare_exchange_XXX() isn't implemented atomically (here meaning no single hardware primitive exists), the weak version inside the loop may win the battle because the strong one will have to handle the spurious failures and retry accordingly.

But,

rarely, we may prefer compare_exchange_strong() over compare_exchange_weak() even in a loop. E.g., when there is a lot of things to do between atomic variable is loaded and a calculated new value is exchanged out (see function() above). If the atomic variable itself doesn't change frequently, we don't need repeat the costly calculation for every spurious failure. Instead, we may hope that compare_exchange_strong() "absorb" such failures and we only repeat calculation when it fails due to a real value change.

Case 2: When only compare_exchange_weak() need to be used inside a loop. C++11 also says:

When a weak compare-and-exchange would require a loop and a strong one would not, the strong one is preferable.

This is typically the case when you loop just to eliminate spurious failures from the weak version. You retry until exchange is either successful or failed because of concurrent write.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

At best, it's reinventing the wheels and perform the same as compare_exchange_strong(). Worse? This approach fails to take full advantage of machines that provide non-spurious compare-and-exchange in hardware.

Last, if you loop for other things (e.g., see "Typical Pattern A" above), then there is a good chance that compare_exchange_strong() shall also be put in a loop, which brings us back to the previous case.

---

Alright, so I need a function which performs atomic left-shifting. My processor doesn't have a native operation for this, and the standard library doesn't have a function for it, so it looks like I'm writing my own. Here goes:

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

Now, there's two reasons that loop might be executed more than once.

1. Someone else changed the variable while I was doing my left shift. The results of my computation should not be applied to the atomic variable, because it would effectively erase that someone else's write.
2. My CPU burped and the weak CAS spuriously failed.

I honestly don't care which one. Left shifting is fast enough that I may as well just do it again, even if the failure was spurious.

What's less fast, though, is the extra code that strong CAS needs to wrap around weak CAS in order to be strong. That code doesn't do much when the weak CAS succeeds... but when it fails, strong CAS needs to do some detective work to determine whether it was Case 1 or Case 2. That detective work takes the form of a second loop, effectively inside my own loop. Two nested loops. Imagine your algorithms teacher glaring at you right now.

And as I previously mentioned, I don't care about the result of that detective work! Either way I'm going to be redoing the CAS. So using strong CAS gains me precisely nothing, and loses me a small but measurable amount of efficiency.

In other words, weak CAS is used to implement atomic update operations. Strong CAS is used when you care about the result of CAS.

참고URL : https://stackoverflow.com/questions/25199838/understanding-stdatomiccompare-exchange-weak-in-c11