xenium 다운로드 - xenium 소스 코드 다운로드

xenium

C/C++

v0.0.2: Merge pull request #19 from rbalint

다운로드

제늄

xenium은 동시 데이터 구조 및 메모리 회수 알고리즘 모음을 제공하는 헤더 전용 라이브러리입니다. 데이터 구조는 다양한 회수 체계와 함께 사용할 수 있도록 매개변수화됩니다(STL이 할당자의 사용자 정의를 허용하는 방법과 유사).

헤더만
고도로 맞춤화 가능
초기화 코드가 필요하지 않습니다
동적 스레드 수 지원(고정된 컴파일 시간 사양 없음)

설명서에 자세한 내용이 나와 있습니다.

이 프로젝트는 https://github.com/mpoeter/emr의 이전 작업을 기반으로 합니다.

사용예

# include < xenium/ramalhete_queue.hpp >
# include < xenium/reclamation/epoch_based.hpp >

struct msg { ... };

xenium::ramalhete_queue<
  std::unique_ptr<msg>,
  xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
  xenium::policy::entries_per_node< 2048 >
> queue;

queue.push(std::make_unique<msg>());

std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
    // do something with data
}

데이터 구조

지금까지는 재생 계획에 중점을 두었기 때문에 현재 제공되는 데이터 구조의 수는 다소 적습니다. 그러나 가까운 시일 내에 여러 가지 데이터 구조를 더 추가할 계획입니다.

michael_scott_queue - Michael과 Scott [MS96]이 제안한 무제한 잠금 없는 다중 생산자/다중 소비자 큐입니다.
ramalhete_queue - Ramalhete [Ram16]가 제안한 빠른 무제한 잠금 없는 다중 생산자/다중 소비자 큐입니다.
vyukov_bounded_queue - Vyukov [Vyu10 ]가 제안한 버전을 기반으로 하는 제한된 다중 생산자/다중 소비자 FIFO 대기열입니다.
kirsch_kfifo_queue - Kirsch 등이 제안한 무제한 다중 생산자/다중 소비자 k-FIFO 대기열입니다. [KLP13].
kirsch_bounded_kfifo_queue - Kirsch 등이 제안한 제한된 다중 생산자/다중 소비자 k-FIFO 대기열입니다. [KLP13].
nikolaev_queue - Nikolaev [Nik19]가 제안한 무제한 다중 생산자/다중 소비자 대기열.
nikolaev_bounded_queue - Nikolaev [Nik19]가 제안한 제한된 다중 생산자/다중 소비자 큐입니다.
harris_michael_list_based_set - 정렬된 고유 개체 집합을 포함하는 잠금 없는 컨테이너입니다. 이 데이터 구조는 Harris [Har01]의 원래 제안을 기반으로 구축된 Michael [Mic02]이 제안한 솔루션을 기반으로 합니다.
harris_michael_hash_map - Harris [Har01]의 원래 제안을 기반으로 구축된 Michael [Mic02]가 제안한 솔루션을 기반으로 하는 잠금 없는 해시 맵입니다.
chase_work_stealing_deque - Chase와 Lev[CL05]의 제안을 기반으로 한 작업 훔치기 데크입니다.
vyukov_hash_map - 업데이트 작업에 세분화된 잠금을 사용하는 동시 해시 맵입니다. 이 구현은 Vyukov [Vyu08]가 제안한 버전에서 많은 영감을 받았습니다.
left_right - Ramalhete 및 Correia [RC15]가 제안한 LeftRight 알고리즘의 일반적인 구현입니다.
seqlock - 시퀀스 잠금(종종 "순차 잠금"이라고도 함)의 구현입니다.

매립 계획

재확보 방식의 구현은 Robison [Rob13]이 제안한 인터페이스의 수정된 버전을 기반으로 합니다.

다음과 같은 회수 계획이 구현됩니다.

lock_free_ref_count [Val95, MS95]
hazard_pointer [Mic04]
hazard_eras [RC17]
quiescent_state_based
generic_epoch_based - 여러 가지 방법으로 구성할 수 있는 일반화된 에포크 기반 회수자입니다. 단순화를 위해 해당 구성에 대해 다음 별칭이 미리 정의되어 있습니다.
- epoch_based [Fra04]
- new_epoch_based [HMBW07]
- debra [Bro15]
stamp_it [PT18a, PT18b]

건물

xenium은 헤더 전용 라이브러리이므로 이를 사용하려면 포함 디렉터리 목록에 xenium 폴더를 포함하는 것으로 충분합니다. 다른 타사 라이브러리는 필요하지 않습니다. 그러나 구현에서는 C++17 기능을 사용하므로 C++17을 충분히 지원하는 컴파일러가 필요합니다. 다음 컴파일러는 CI 빌드에 사용되므로 지원되는 것으로 알려져 있습니다.

gcc9
땡땡이10
비주얼 스튜디오 2019

단위 테스트에는 googletest 필요하고 벤치마크에는 taocpp/json 및 taocpp/config 필요합니다. 이러한 종속성은 하위 모듈로 포함되므로 단위 테스트 및/또는 벤치마크는 다음과 같이 구축될 수 있습니다.

 git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark

참고자료

[브로15]	트레버 알렉산더 브라운. 잠금 없는 데이터 구조를 위한 메모리 회수: 더 나은 방법이 있어야 합니다. 분산 컴퓨팅 원리(PODC)에 관한 2015 ACM 심포지엄 진행 과정 , 261~270페이지. ACM, 2015.
[CL05]	데이비드 체이스와 요시 레프. 동적 순환 작업 도용 데크. 알고리즘 및 아키텍처의 병렬성에 관한 제17회 연례 ACM 심포지엄(SPAA) 진행 중 , 21~28페이지. ACM, 2005.
[프라04]	키어 프레이저. 실용적인 잠금 자유 . 2004년 케임브리지 대학교 컴퓨터 연구실 박사 학위 논문.
[Har01]	티모시 L. 해리스. 비차단 연결 목록의 실용적인 구현입니다. 제15차 분산 컴퓨팅 국제 컨퍼런스(DISC) 진행 , 300~314페이지. 스프링거-발라그, 2001.
[HMBW07]	토마스 E. 하트, 폴 E. 맥케니, 안젤라 뎀케 브라운, 조나단 월폴. 무잠금 동기화를 위한 메모리 회수 성능. 병렬 및 분산 컴퓨팅 저널, 67(12):1270–1285, 2007.
[KLP13]	크리스토프 커쉬(Christoph Kirsch), 마이클 리포츠(Michael Lippautz), 하네스 페이어(Hannes Payer). 빠르고 확장 가능하며 잠금이 없는 k-FIFO 대기열입니다. 병렬 컴퓨팅 기술(PaCT)에 관한 국제 컨퍼런스 진행 , 208~223페이지, Springer-Verlag, 2013년.
[마이크02]	매지드 M. 마이클. 고성능 동적 잠금 없는 해시 테이블 및 목록 기반 세트. 병렬 알고리즘 및 아키텍처에 관한 제14회 연례 ACM 심포지엄(SPAA) 진행 과정 , 73~82페이지. ACM, 2002.
[마이크04]	매지드 M. 마이클. 위험 포인터: 잠금이 없는 객체에 대한 안전한 메모리 회수. 병렬 및 분산 시스템의 IEEE 트랜잭션, 15(6):491–504, 2004.
[MS95]	Maged M. Michael과 Michael L. Scott. 잠금 없는 데이터 구조에 대한 메모리 관리 방법을 수정했습니다. 기술 보고서, 로체스터 대학교, 1995.
[MS96]	Maged M. Michael과 Michael L. Scott. 간단하고 빠르며 실용적인 비차단 및 차단 동시 대기열 알고리즘입니다. 분산 컴퓨팅 원리(PODC)에 관한 제15차 연례 ACM 심포지엄 진행 과정 , 267~275페이지. ACM, 1996.
[닉19]	Ruslan Nikolaev 확장 가능하고 휴대 가능하며 메모리 효율성이 뛰어난 잠금 없는 FIFO 대기열입니다. 제33회 분산 컴퓨팅 국제 심포지엄(DISC) 진행 중 , 2019.
[PT18a]	마누엘 포터(Manuel Pöter)와 예스퍼 라르손 트레프(Jesper Larsson Träff). 간략한 발표: C++ 메모리 모델의 스레드 효율적인 동시 메모리 회수 방식인 Stamp-it입니다. 알고리즘 및 아키텍처의 병렬성에 관한 제30회 연례 ACM 심포지엄(SPAA) 진행 , 355~358페이지. ACM, 2018.
[PT18b]	마누엘 포터(Manuel Pöter)와 예스퍼 라르손 트레프(Jesper Larsson Träff). Stamp-it은 C++ 메모리 모델의 스레드 효율적인 동시 메모리 회수 방식입니다. 기술 보고서, 2018.
[램16]	페드로 라말헤테. FAAArrayQueue - MPMC 잠금 해제 대기열(4/4부). 블로그, 2016년 11월.
[RC15]	페드로 라말헤테와 안드레아 코레이아. 왼쪽-오른쪽 - 대기 없는 인구 인식 읽기를 통한 동시성 제어 기술. 2015년 10월
[RC17]	페드로 라말헤테와 안드레아 코레이아. 간략한 발표: 위험 시대 - 비차단 메모리 회수. 알고리즘 및 아키텍처의 병렬성에 관한 제29차 연례 ACM 심포지엄(SPAA) 진행 , 367~369페이지. ACM, 2017.
[롭13]	아치 D. 로비슨. 동시 컨테이너의 안전한 파기를 위한 정책 기반 설계. C++ 표준 위원회 문서, 2013.
[발95]	존 D. 발루아. 잠금이 없는 데이터 구조 . 1995년 Rensselaer Polytechnic Institute 박사학위 논문.
[뷰08]	드미트리 뷰코프. 확장 가능한 해시 맵. Google 그룹스 게시, 2008년.
[뷰10]	드미트리 뷰코프. 간단하고 효율적인 제한된 MPMC 큐. Google 그룹스 게시, 2010년.