atomic_queue
1.0.0
C ++ 14 원형 버퍼 및 std::atomic 기반으로 한 다중 프로듀서 다중 소비자 잠금 큐.
한 스레드 사이의 대기 시간을 최소화하여 요소를 큐에 밀고 다른 스레드가 큐에서 튀어 나오는 목표로 설계되었습니다.
Linux에서 개발, 테스트 및 벤치마킹되었지만 std::atomic 구현하는 C ++ 14 플랫폼을 지원해야합니다. Windows와 호환되는 것으로보고되었지만 GitHub에서 호스팅하는 지속적인 통합은 현재 Ubuntu-20.04 및 Ubuntu-22.04의 X86_64 플랫폼에 대해서만 설정됩니다. 다른 아키텍처 및/또는 플랫폼에서 실행되도록 지속적인 통합을 확장하라는 요청을 당기는 것이 환영합니다.
대기 시간을 최소화 할 때 좋은 디자인은 추가 할 것이 없을 때가 아니라 제거해야 할 것이 없을 때이 줄이 예시되어 있습니다.
대기 시간을 최소화하면 자연스럽게 처리량이 최대화됩니다. 낮은 대기 시간 상호 작용은 이상적인 수학적 및 실용적인 엔지니어링 의미에서 높은 욕설입니다. 낮은 대기 시간은 지연 및/또는 배치와 호환되지 않으므로 원본 (하드웨어) 전역 시간 순서 이벤트의 이벤트는 다른 스레드에 의해 하나의 대기열로 밀려납니다. 반면에 처리량 최대화는 여러 업데이트를 지연시키고 배치하여 대기 시간을 희생하면서 수행 할 수 있습니다.
이러한 대기열이 따르는 주요 디자인 원칙은 미니멀리즘 이며, 이와 같은 디자인 선택을 초래합니다.
push / pop 에 복사/움직임을 만듭니다. 큐의 요소에 대한 참조/포인터는 얻을 수 없습니다.이러한 작은 디자인 선택의 각각의 영향은 그 자체로 거의 측정 할 수 있지만, 총 영향은 단순한 구성 요소의 영향, 즉 슈퍼 스칼라 복합 또는 시너지 효과보다 훨씬 큽니다. 이러한 작은 디자인 선택의 여러 가지를 결합하여 나오는 시너지 효과는 CPU가 최소한으로 방해받는 피크 용량에서 수행 할 수있게합니다.
이러한 설계 선택은 또한 한계입니다.
초고대적 인 응용 프로그램에는 그와 더 이상 아무것도 필요하지 않습니다. 미니멀리즘은 돈을 지불하고 처리량 및 대기 시간 벤치 마크를 참조하십시오.
벤치 마크에서 참조하는 데 잘 알려져 있고 인기있는 스레드-안전 컨테이너가 사용됩니다.
std::mutex std::mutex 가있는 고정 크기 링 버퍼.pthread_spinlock pthread_spinlock_t 가있는 고정 크기 링 버퍼.boost::lockfree::spsc_queue 부스트 라이브러리의 대기없는 단일 프로듀서-싱글 소비자 큐.boost::lockfree::queue -부스트 라이브러리의 잠금 장치 다중 프로듀서 다기관 소비자 큐.moodycamel::ConcurrentQueue 비 블로킹 모드에서 사용되는 잠금 장치 다중 프로듀서 다기관 소비자 큐. 이 대기열은 대기 시간을 희생시키면서 처리량을 최대화하고 다른 스레드에 의해 하나의 큐로 밀려난 전 세계 시간 순서를 피하도록 설계되었습니다. 이 점에서 벤치마킹 된 다른 대기열과 동일하지 않습니다.moodycamel::ReaderWriterQueue 비 블로킹 모드에서 사용되는 잠금이없는 단일 프로듀서-단일 소비자 큐.xenium::michael_scott_queue Michael과 Scott이 제안한 잠금 장치가없는 다중 프로듀서 다중 소비자 큐 (이 대기열은 boost::lockfree::queue 과 유사하며 동일한 제안을 기반으로합니다).xenium::ramalhete_queue Ramalhete와 Correia가 제안한 잠금이없는 다중 프로듀서 다중 소비자 큐.xenium::vyukov_bounded_queue Vyukov가 제안한 버전을 기반으로 한 경계 다중 프로듀서 다중 소비자 큐.tbb::spin_mutex 인텔 스레딩 빌딩 블록에서 tbb::spin_mutex 있는 잠긴 고정 크기 링 버퍼.tbb::concurrent_bounded_queue 인텔 스레딩 빌딩 블록에서 비 차단 모드에서 사용되는 시조 큐.제공된 컨테이너는 헤더 전용 클래스 템플릿이며 빌딩/설치가 필요하지 않습니다.
git clone https://github.com/max0x7ba/atomic_queue.git
atomic_queue/include 디렉토리 (전체 경로 사용)를 추가하십시오.#include <atomic_queue/atomic_queue.h> c ++ 소스에서. vcpkg install atomic-queue
Conan 패키지를 소비하는 방법에 대한 공식 자습서를 따르십시오. 이 라이브러리와 관련된 세부 사항은 Conanncenter에서 제공됩니다.
제공된 컨테이너는 #include <atomic_queue/atomic_queue.h> 만 필요한 헤더 전용 클래스 템플릿입니다.
테스트 및 벤치 마크를 실행하려면 건물이 필요합니다.
git clone https://github.com/cameron314/concurrentqueue.git
git clone https://github.com/cameron314/readerwriterqueue.git
git clone https://github.com/mpoeter/xenium.git
git clone https://github.com/max0x7ba/atomic_queue.git
cd atomic_queue
make -r -j4 run_benchmarks
벤치 마크는 또한 인텔 TBB 라이브러리를 사용할 수 있어야합니다. /usr/local/include 및 /usr/local/lib 에 설치되어 있다고 가정합니다. 다른 곳에서 설치되면 cppflags.tbb 및 ldlibs.tbb Makefile 에서 수정할 수 있습니다.
AtomicQueue 원자 요소에 대한 고정 크기 링 버퍼.OptimistAtomicQueue 비어 있거나 가득 차면 바쁜 원자 요소를위한 더 빠른 고정 크기 링 버퍼. try_push / try_pop 대신 push / pop 과 함께 사용되는 AtomicQueue 입니다.AtomicQueue2 비 원소 요소에 대한 고정 크기 링 버퍼.OptimistAtomicQueue2 비 원소 요소에 대한 더 빠른 고정 크기 링 버퍼. try_push / try_pop 대신 push / pop 과 함께 사용되는 AtomicQueue2 입니다. 이 컨테이너는 해당 AtomicQueueB , OptimistAtomicQueueB , AtomicQueueB2 , OptimistAtomicQueueB2 버전을 갖는 버퍼 크기가 생성자에 대한 인수로 지정됩니다.
완전히 주문한 모드가 지원됩니다. 이 모드에서 소비자는 동일한 FIFO 주문에서 메시지를받습니다. 메시지가 게시되었습니다. 이 모드는 push 및 pop 함수를 위해 지원되지만 try_ 버전은 아닙니다. 인텔 X86에서 완전히 주문한 모드는 2019 년 현재 0 비용이 있습니다.
단일 생산자-단일 소비자 모드가 지원됩니다. 이 모드에서는 고가의 원자 읽기 모듈식이 쓰기 CPU 지침이 필요하지 않으며 가장 저렴한 원자 부하 및 저장소 만 필요합니다. 이는 대기열 처리량을 크게 향상시킵니다.
이동 전용 큐 요소 유형이 완전히 지원됩니다. 예를 들어, std::unique_ptr<T> 큐의 대기열은 요소가 AtomicQueue2B<std::unique_ptr<T>> 또는 AtomicQueue2<std::unique_ptr<T>, CAPACITY> 입니다.
큐 클래스 템플릿은 다음 멤버 기능을 제공합니다.
try_push 큐 끝에 요소가 추가됩니다. 대기열이 가득 차면 false 반환합니다.try_pop 큐 앞쪽에서 요소를 제거합니다. 대기열이 비어있을 때 false 반환합니다.push (Optimist) - 큐 끝에 요소를 추가합니다. 바쁜 대기열이 가득 차면 기다립니다. 대기열이 가득 차 있지 않을 때 try_push 보다 빠릅니다. FIFO 생산자 큐어 큐잉 및 총 주문.pop (OPTIMIST) - 큐 앞면에서 요소를 제거합니다. 대기열이 비어있을 때 바쁜 기다립니다. 대기열이 비어 있지 않을 때 try_pop 보다 빠릅니다. FIFO 소비자 대기열 및 총 주문 선택.was_size 통화 중에 소비되지 않은 요소의 수를 반환합니다. 반환 값이 검사 될 때까지 국가가 변경되었을 수 있습니다.was_empty 통화 중에 컨테이너가 비어 있으면 true 반환합니다. 반환 값이 검사 될 때까지 국가가 변경되었을 수 있습니다.was_full 통화 중에 컨테이너가 가득 차면 true 반환합니다. 반환 값이 검사 될 때까지 국가가 변경되었을 수 있습니다.capacity - 큐가 잡을 수있는 최대 요소 수를 반환합니다. 원자 요소 는 std::atomic<T>{T{}}.is_lock_free() 가 true 반환하고 C ++ 17 기능을 사용할 수 있으면 std::atomic<T>::is_always_lock_free 컴파일 시간에 true 로 평가하는 요소입니다. 다시 말해, CPU는 그러한 요소를 원자 적으로 기본적으로로드, 저장 및 비교 및 교환 할 수 있습니다. x86-64에서 이러한 요소는 모든 C ++ 표준 산술 및 포인터 유형입니다.
원자 요소의 대기열은 빈 요소 NIL 를 사용하기 위해 하나의 값을 예약하고 기본값은 0 입니다. NIL 값을 큐에 밀어 넣어서는 안되며 push 함수에는 디버그 모드 빌드에서이를 보호하기 위해 assert 진술이 있습니다. 릴리스 모드에서 NIL 요소를 대기열로 밀면 교착 상태 및/또는 손실 큐 요소와 같은 정의되지 않은 동작이 발생합니다.
낙관론 은 큐 유형이 아닌 대기열 수정 작업 제어 흐름을 선택하는 것입니다. 대기열이 대부분 가득 차 있지 않을 때 낙관주의 push 가장 빠릅니다. 대기열이 대부분 비어 있지 않을 때 낙관적 인 pop 입니다. 낙관적이고 그렇지 않은 작업은 제한없이 혼합 될 수 있습니다. 벤치 마크의 OptimistAtomicQueue 는 낙관주의 push 와 pop 만 사용합니다.
사용 예제는 exames.cc를 참조하십시오.
push and try_push 작업 동일한 큐 오브젝트의 후속 pop 또는 try_pop 작업과 ( std::memory_order 에 정의 된대로) 동기화합니다 . 의미 :
push / try_push memory_order::release 하지 않습니다. std::mutex::unlock 와 동일한 메모리 순서.pop / try_pop 이전에 비 원자로드 / 스토어가 재정렬되지 않으며, 이는 memory_order::acquire 작업입니다. std::mutex::lock 의 메모리 순서와 동일한 메모리 순서.push / try_push 큐에 미치는 영향은 소비자의 스레드에서 해당 특정 요소를 pop try_pop 소비자 스레드에서 볼 수있게됩니다. 여기에 사용 가능한 대기열은 요소를 저장하는 데 링 버퍼 배열을 사용합니다. 대기열의 용량은 컴파일 시간 또는 시공 시간에 고정됩니다.
생산 다중 프로듀서 다중 소비자 시나리오에서 링 버퍼 용량은 최대 예상 대기열 크기로 설정해야합니다. 링 버퍼가 가득 차면 소비자가 요소를 충분히 빨리 소비 할 수 없음을 의미합니다. 그것에 대한 수정은 다음과 같습니다.
push 및 pop 콜은 항상 다른 스레드와 관련하여 원자/일관성/고립 된 방식으로 대기열 상태의 무결성을 유지하기 위해 항상 비싼 CPU주기를 겪고 있으며 이러한 비용은 대기열 경합이 증가함에 따라 초대적으로 증가합니다. 하나의 이벤트에서 하나의 대기열 메시지로 인한 여러 개의 작은 요소 또는 요소의 생산자 배치는 종종 합리적인 솔루션입니다.2 개의 링 버퍼 배열 크기를 사용하면 몇 가지 중요한 최적화가 가능합니다.
% SIZE 사용하여 링 버퍼 배열 인덱스에 매핑됩니다. 나머지 바이너리 연산자 % 일반적으로 저렴하지 않은 Division CPU 명령어를 생성하지만 나머지 작업자가 저렴한 바이너리 and CPU 명령어로 나머지 작업자를 사용하는 Divise CPU 명령어를 생성합니다.M 소비자와 함께 N 생산자 대신 한 소비자와 경쟁하는 한 명의 생산자 일뿐입니다 (CPU의 수가 한 캐시 라인에 맞는 요소 수보다 크지 않을 때). 이 최적화는 생산자와 소비자의 수와 요소 크기로 더 잘 확장됩니다. 이 최적화를 비활성화하는 생산자와 소비자 수 (이 벤치 마크에서 각각 최대 약 2 개)를 사용하면 더 나은 처리량을 얻을 수 있지만 런의 차이가 높을 수 있습니다. 컨테이너는 크기와 내부 인덱스에 unsigned 유형을 사용합니다. X86-64의 플랫폼은 unsigned 플랫폼의 폭이 32 비트이며 size_t 폭이 64 비트입니다. 64 비트 명령어는 추가 바이트 명령어 접두사를 사용하여 CPU 명령 캐시 및 프론트 엔드에 약간 더 많은 압력 을가합니다. 따라서 32 비트 unsigned 인덱스는 성능을 최대화하는 데 사용됩니다. 이는 큐 크기를 4,294,967,295 요소로 제한하며, 이는 많은 응용 프로그램에서 합리적인 하드 제한 인 것 같습니다.
원자 큐는 모든 이동성 요소 유형 ( std::unique_ptr 포함)과 함께 사용할 수 있지만 최상의 처리량 및 대기 시간 T* 위해 대기열 요소는 복사 및 잠금 unsigned 없어야하는 데 저렴해야하므로 push 및 pop 작업이 가장 빠르게 완료되도록해야합니다.
개념적으로 push 또는 pop 작업은 두 가지 원자 단계를 수행합니다.
head 지수를 증가시키고, 소비자는 tail 지수를 증가시킵니다. 각 슬롯은 한 명의 생산자와 하나의 소비자 스레드 만 액세스합니다.NIL 로 변경하고 슬롯에서 소비자 로딩은 상태를 NIL 로 변경합니다. 이 슬롯은 하나의 생산자와 하나의 소비자 스레드를위한 스핀 락입니다. 이 대기열은 push 또는 pop 수행하는 스레드가 1 단계를 완료 한 다음 2 단계를 완료하기 전에 선점 될 것으로 예상합니다.
시스템 전체의 진행 상황이 보장되면 알고리즘은 잠금됩니다 . 이 대기열은 다음 속성으로 시스템 전체의 진행을 보장합니다.
push 선행 push 와 무관합니다. 하나의 생산자 스레드에 의한 불완전한 (선점) push 다른 스레드의 push 영향을 미치지 않습니다.pop 선행 pop 과 무관합니다. 하나의 소비자 스레드가 불완전한 (선점) pop 다른 스레드의 pop 영향을 미치지 않습니다.push 이 특정 대기열 슬롯의 요소를 pop 하는 하나의 소비자 스레드에만 영향을 미칩니다. 다른 모든 스레드 pop 은 영향을받지 않습니다.pop 하나의 생산자 스레드 에만이 특정 대기열 슬롯에 요소를 push 하면서 오랫동안 소비 될 것으로 예상 하면서이 소비자가 pop 완성하지 못한 반면 생산자가 전체 링 버퍼를 감싸지 않았을 가능성이 거의없는 시나리오에 영향을 미칩니다. 다른 모든 스레드는 푸시를 push 하고 pop 은 영향을받지 않습니다. Linux 작업 스케줄러 스레드 선점은 사용자 공간 프로세스가 영향을 미치거나 탈출 할 수없는 것입니다. 그렇지 않으면 모든 악성 응용 프로그램이이를 악용 할 수 있습니다.
그럼에도 불구하고 미션 크리티컬 애플리케이션 스레드의 선점을 최소화하기 위해 할 수있는 몇 가지가 있습니다.
SCHED_FIFO 스케줄링 클래스를 사용하십시오 (예 : chrt --fifo 50 <app> . 우선 순위가 높은 SCHED_FIFO 스레드 또는 커널 인터럽트 핸들러는 여전히 SCHED_FIFO 스레드를 선점 할 수 있습니다.SCHED_OTHER 사용하면 이러한 대기열을 사용하는 목적이 있습니다.SCHED_FIFO 실시간 스레드가 조절되는 것을 방지하기 위해 실시간 스레드 조절을 비활성화하십시오.taskset 사용하여 분리 된 코어에 명시 적으로 배치해야합니다. 사람들은 종종 std::this_thread::yield() / sched_yield / pthread_yield 에 대한 후속 호출로 바쁜 기다리는 제한을 제안합니다. 그러나 sched_yield 스레드가 대기하는 내용을 OS 커널에 통신하지 않기 때문에 잠금에 대한 잘못된 도구입니다. 따라서 OS 스레드 스케줄러는 공유 상태가 변경 될 때 적시에 호출 스레드를 다시 시작할 수 없도록 (이 CPU 코어에서 실행할 수있는 다른 스레드가 없다면, 발신자가 즉시 이력서를 재개 할 수 없음). 자세한 내용은 man sched_yield 의 메모 섹션과 sched_yield 및 Spinlocks에 대한 Linux 커널 스레드를 참조하십시오.
Linux에는 MUTEX 유형 PTHREAD_MUTEX_ADAPTIVE_NP 가 있으며, 이는 여러 반복을 위해 잠긴 뮤트를 바쁘게 만든 다음 대기 스레드를 막기 위해 커널에 차단 된 SYSCALL을 만듭니다. 벤치 마크에서 그것은 최악의 연기자였으며 더 잘 수행 할 수있는 방법을 찾을 수 없었습니다. 이것이 벤치 마크에 포함되지 않은 이유입니다.
Intel CPUS에서 One은 4 개의 디버그 컨트롤 레지스터를 사용하여 스핀 락 메모리 영역을 모니터링하고 select (및 그 친구) 또는 sigwait ( perf_event_open 및 uapi/linux/hw_breakpoint.h 참조)를 사용하여 대기 할 수 있습니다. 스핀 록 웨이터는 스핀 록 상태가 업데이트 될 때까지 select 또는 sigwait 로 스스로를 일시 중단 할 수 있습니다. 그러나 이러한 레지스터 중 4 개만 있으므로 그러한 솔루션은 확장되지 않습니다.
처리량 및 대기 시간 벤치 마크 차트를 봅니다.
벤치마킹을 복잡하게하는 몇 가지 OS 동작이 있습니다.
SCHED_FIFO Priority 50을 피하기 위해 스케줄러 시간 양자 만료를 비활성화하고 우선 순위가 낮은 프로세스/스레드에 의해 스레드를 방해 할 수 없게 만드는 데 사용됩니다.benchmarks 의 효과를 최소화하기 위해 실행 파일은 33 번 이상 실행됩니다. 벤치 마크 차트에는 평균 값이 표시됩니다. 차트 툴팁에는 표준 편차, 최소 및 최대 값도 표시됩니다. 단일 프로듀서-싱글 소비자 큐의 벤치 마크 성능 boost::lockfree::spsc_queue , moodycamel::ReaderWriterQueue 및 단일 프로듀서-싱글 소비자 모드의 이러한 큐는 정확히 동일한 원자 부하 및 저장 지침을 사용하여 동일한 알고리즘을 구현하기 때문에 동일해야합니다. boost::lockfree::spsc_queue 구현 당시 벤치마킹 된 L1D 캐시 경합을 최소화하기위한 최적화가 없었습니다.
몇 개의 x86-64 기계에만 액세스 할 수 있습니다. 다른 하드웨어에 액세스 할 수있는 경우 scripts/run-benchmarks.sh 의 출력 파일을 제출하십시오. 결과를 벤치 마크 페이지에 포함시킬 것입니다.
거대한 페이지를 사용할 수 있으면 벤치 마크는 TLB Misses를 최소화하기 위해 대기열에 1x1GB 또는 16x2MB 거대한 페이지를 사용합니다. 거대한 페이지를 활성화하려면 다음 중 하나를 수행합니다.
sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16
또는 시스템에서 투명한 거대한 페이지를 활성화하고 TCMALLOC와 같은 거대한 인식 할당자를 사용하고 싶을 수도 있습니다.
기본적으로 Linux Scheduler는 실시간 스레드가 CPU의 100%를 소비하여 스레드를 조절하며 이는 벤치마킹에 해 롭습니다. 자세한 내용은 실시간 그룹 스케줄링에서 찾을 수 있습니다. 실시간 스레드 스로틀링을 비활성화하려면 다음과 같습니다.
echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null
n 생산자 스레드는 4 바이트 정수를 하나의 동일한 대기열로 밀고, n 소비자 스레드는 큐에서 정수를 팝업합니다. 모든 생산자는 총 1,000,000 개의 메시지를 게시합니다. 전송 및 수신하는 총 시간이 측정됩니다. 벤치 마크는 다른 대기열의 확장 성을 측정하기 위해 1 명의 생산 업체와 1 명의 소비자 (total-number-of-cpus / 2) 생산자 / 소비자로부터 실행됩니다.
한 스레드는 한 대기열을 통해 다른 스레드에 정수를 게시하고 다른 대기열에서 답장을 기다립니다 (총 2 개의 대기열). 벤치 마크는 총 시간이 10 만 핑 완구, 최고 10 점을 측정합니다. 가장 낮은 대기 시간을 달성하고 측정 할 수 있도록 여기에서 경합 (1- 프로듀서 -1 소비자, 대기열의 1 요소)이 최소화됩니다. 평균 왕복 시간을보고합니다.
기부금은 환영받는 것 이상입니다. .editorconfig 및 .clang-format 사용하여 코드 형식을 자동으로 일치시킬 수 있습니다.
다중 스레드 프로그래밍의 주제에 관한 일부 책은 내가 꽤 유익한 것으로 나타났습니다.
저작권 (C) 2019 Maxim Egorushkin. MIT 라이센스. 파일 라이센스의 전체 라이센스를 참조하십시오.
