오버플로하지 않는 원자 참조 카운터를 구현하는 방법은 무엇입니까?

Question

오버플로로부터 안전 할 원자 정수를 기반으로하는 참조 계산에 대해 생각했습니다. 그것을하는 방법?

오버플로가 현실적인 문제인지 여부에 초점을 두지 마십시오. 그 일 자체는 실질적으로 중요하지 않더라도 내 관심사를 가지고 있습니다. 레퍼런스 카운트

---

예

예시적인 구현은 Boost.Atomic에서 예로서 도시되어있다. 만 형성 될 수있는 객체에 대한 새로운 참조 : 또한 다음의 설명에서는

struct T 
{ 
    boost::atomic<boost::uintmax_t> counter; 
}; 

void add_reference(T* ptr) 
{ 
    ptr->counter.fetch_add(1, boost::memory_order_relaxed); 
} 

void release_reference(T* ptr) 
{ 
    if (ptr->counter.fetch_sub(1, boost::memory_order_release) == 1) { 
     boost::atomic_thread_fence(boost::memory_order_acquire); 
     delete ptr; 
    } 
} 

항상 memory_order_relaxed 수행 할 수 있습니다 참조 카운터를 증가

주어진다

: 그 예를 바탕으로 우리는 샘플 코드 다음 추출 할 수 있습니다 기존 참조를 한 스레드에서 다른 스레드로 전달하면 이미 필요한 동기화가 이루어져야합니다.

에 대한 하나의 스레드에서 기존의 참조를 통해 가능한 모든 액세스를 수행하여 다른 스레드에서 개체를 삭제하는 것이 중요합니다. 이는 참조를 삭제 한 후 (이 참조를 통해 객체에 대한 모든 액세스가 분명히 발생해야 함) "객체 삭제"작업과 객체를 삭제하기 전에 "획득"작업에 의해 수행됩니다.

fetch_sub 작업에는 memory_order_acq_rel을 사용할 수 있지만 참조 카운터가 아직 0에 도달하지 않아 불필요한 "획득"작업이 발생하고 성능이 저하 될 수 있습니다.

편집 >>>

이 Boost.Atomic 문서가 잘못 여기있을 것으로 보인다. 결국 acq_rel이 필요할 수 있습니다.

적어도 std::atomic을 사용하면 boost::shared_ptr이 구현됩니다 (다른 구현도 있습니다). 파일 boost/smart_ptr/detail/sp_counted_base_std_atomic.hpp을 참조하십시오.

또한 Herb Sutter는 그의 강의에서 C++ and Beyond 2012: Herb Sutter - atomic<> Weapons, 2 of 2 (참조 계산 시작 부분은 1:19:51에서 시작 함)에서 언급합니다. 또한 그는이 이야기에서 담장을 사용하는 것을 꺼리는 것 같습니다.

덕분에 아래의 의견을 지적 해 주신 user 2501에게 감사드립니다.

< < < 최종 편집

---

초기 시도

이제 문제는 add_reference 수 (어떤 점에서) 오버 플로우를 작성한다. 그리고 그것은 그렇게 조용히 할 것입니다.어떤 것은 분명히 객체를 조기에 파괴 할 수있는 release_reference과 일치하는 호출을 할 때 문제가 될 수 있습니다. (add_reference가 다시 한번 호출 할 것이다 1에 도달하는 것을 제공.)

내가 add_reference가 오버 플로우를 감지하고 아무 위험없이 정상적으로 실패하는 방법을 생각했다. 우리는 둘 사이에 다른 스레드가 다시 (1에 도달) add_reference 다음 release_reference를 호출 할 수 있기 때문에 fetch_add는 (잘못 적용되는 오브젝트를 파괴)하지 않을 것이다 떠나면 0에 비교

.

첫 번째 검사 (load)는 도움이되지 않습니다. 이 방법으로 다른 스레드는 load과 fetch_add 호출 사이에 자체 참조를 추가 할 수 있습니다.

---

이 해결책입니까?

그런 다음 우리는 load으로 시작할 수 있다고 생각했지만 그 다음에야 만 compare_exchange을 작성했습니다.

먼저 load을 입력하고 로컬 값을 가져옵니다. std::numeric_limits<boost::uintmax_t>::max()이면 실패합니다. add_reference은 가능한 모든 것이 이미 취해 졌으므로 다른 참조를 추가 할 수 없습니다.

그렇지 않으면 우리는 이전의 로컬 참조 카운트에 1을 더한 다른 로컬 값을 만듭니다.

이제 우리는 원래의 로컬 참조 카운트 (이것은 다른 스레드가 평균 시간에 참조 카운트를 수정하지 않음을 보장)와 원하는 값으로 증가 된 로컬 참조 카운트를 예상 값으로 제공합니다.

compare_exchange이 실패 할 수 있으므로 루프 (load 포함)를 수행해야합니다. 성공하거나 최대 값이 검출 될 때까지

---

몇 가지 질문

1. 이러한 솔루션은 정확합니까?
2. 유효하게하려면 어떤 메모리 순서가 필요합니까?
3. 어느 compare_exchange을 사용해야합니까? _weak 또는 _strong?
4. release_reference 기능에 영향을 줍니까?
5. 실제로 사용됩니까?

Answer 1

해결책은 정확합니다. 한 가지로 개선 될 수도 있습니다. 현재 값이 로컬 CPU에서 최대 값에 도달하면 다른 CPU에 의해 값이 감소 할 수 있지만 현재 CPU는 여전히 이전 값을 캐시합니다. 더미 compare_exchange을 expected 및 newValue과 함께 사용하면 최대 값이 그대로 있는지 확인한 다음 예외 (또는 원하는 값)를 던질만한 가치가 있습니다.어쨌든 루프에서 실행되고, 따라서 다음 load이 매우 안정적으로 최신 값을 얻을 것이다 당신이 _weak 또는 _strong 사용 여부

그것은 중요하지 않습니다 나머지 부분

.

add_reference 및 release_reference의 경우 누가 실제로 추가되었는지 여부를 확인합니다. 예외가 발생합니까? 그렇다면 아마도 작동 할 것입니다. 그러나 일반적으로 참조 수준 카운터에 uintptr_t를 사용하면 실패하지 않는 낮은 수준의 항목을 허용하는 것이 좋습니다. 따라서 주소 공간을 포함 할만큼 충분히 커질 수 없으므로 동시에 존재하는 개체 수에 제한이 없습니다.

아니요, 위와 같은 이유로 실제로 사용되지 않습니다.

Answer 2

빠른 계산 : uint는 32 비트이므로 최대 uint는 4G (40 억 가지)입니다. 각 참조/포인터는 적어도 4 바이트 (64 비트 시스템 인 경우 8 개)이므로 오버플로하려면 동일한 객체를 가리키는 참조를 저장하는 데 필요한 16GB의 메모리가 필요합니다. 이는 심각한 결함을 지적해야합니다.

나는 그것이 오늘이나 가까운 장래에 문제가 아니라고 말할 것이다.

Answer 3

이 질문은 만족스럽지 않습니다. 원자 단위 증가가 1 CPU 사이클을 차지한다고 가정하더라도 (4GHz CPU에서는 64 비트 정수를 감싸는 데 반 년이 걸릴 것입니다), CPU는 아무것도하지 않고 계속 증가합니다.

실제 프로그램의 현실을 고려할 때, 이것이 당신을 괴롭힐 수있는 진짜 문제라고 생각하는 것이 어렵습니다.