atomic_queue

Atomic_queue

C ++ 14 คิว การล็อค แบบหลายผู้ผลิตหลายผู้ผลิตตามบัฟเฟอร์แบบวงกลมและ std::atomic

ออกแบบโดยมีเป้าหมายเพื่อลดเวลาแฝงระหว่างเธรดหนึ่งที่ผลักองค์ประกอบลงในคิวและเธรดอื่นโผล่ออกมาจากคิว

มันได้รับการพัฒนาทดสอบและเปรียบเทียบกับ Linux แต่ควรรองรับแพลตฟอร์ม C ++ 14 ใด ๆ ที่ใช้ std::atomic รายงานว่าเข้ากันได้กับ Windows แต่การรวมอย่างต่อเนื่องที่โฮสต์โดย GitHub ถูกตั้งค่าเฉพาะสำหรับแพลตฟอร์ม x86_64 บน Ubuntu-20.04 และ Ubuntu-22.04 คำขอดึงเพื่อขยายการรวมการรวมอย่างต่อเนื่องเพื่อทำงานบนสถาปัตยกรรมอื่น ๆ และ/หรือแพลตฟอร์มยินดีต้อนรับ

หลักการออกแบบ

เมื่อลดเวลาแฝงการออกแบบที่ดีไม่ได้เมื่อไม่มีอะไรเหลือให้เพิ่ม แต่เมื่อไม่มีอะไรเหลือให้ลบเนื่องจากคิวเหล่านี้เป็นแบบอย่าง

ลดความหน่วงให้น้อยที่สุดตามธรรมชาติเพิ่มปริมาณงาน การตอบโต้เวลาแฝงต่ำนั้นมีความสูงสูงในความรู้สึกทางคณิตศาสตร์และวิศวกรรมที่ใช้งานได้ดี ความหน่วงแฝงต่ำนั้นเข้ากันไม่ได้กับความล่าช้าและ/หรือการแบตช์ซึ่งทำลายลำดับเวลาของเหตุการณ์ทั่วโลก (ฮาร์ดแวร์) ที่ผลักดันให้เข้าคิวหนึ่งคิวโดยเธรดที่แตกต่างกัน ในทางกลับกันการเพิ่มปริมาณงานสูงสุดสามารถทำได้โดยเสียค่าใช้จ่ายในการแฝงโดยการหน่วงเวลาและการแบตช์การอัปเดตหลายครั้ง

หลักการออกแบบหลักคิวเหล่านี้ตามมาคือ ความเรียบง่าย ซึ่งส่งผลให้ตัวเลือกการออกแบบเช่น:

• คำแนะนำอะตอมขั้นต่ำขั้นต่ำ ไม่สามารถใช้งานได้โดยค่าเริ่มต้นและฟังก์ชั่นป๊อปเริ่มต้นไม่สามารถถูกกว่าใด ๆ ในแง่ของหมายเลขคำสั่ง CPU / ความดันแคช L1I
• การโต้แย้งอย่างชัดเจน/การหลีกเลี่ยงการแบ่งปันเท็จสำหรับคิวและองค์ประกอบของมัน
• อาร์เรย์แหวนขนาดคงที่เชิงเส้น ไม่มีการจัดสรรหน่วยความจำฮีปหลังจากสร้างวัตถุคิว มันไม่ได้รับ CPU L1D หรือ TLB ที่เป็นมิตรมากกว่านั้น
• ความหมายที่มีค่า หมายความว่าคิวทำสำเนา/ย้ายตาม push / pop ไม่มีการอ้างอิง/ตัวชี้ไปยังองค์ประกอบในคิว

ผลกระทบของตัวเลือกการออกแบบขนาดเล็กเหล่านี้แต่ละตัวเองนั้นแทบจะไม่สามารถวัดได้ แต่ผลกระทบทั้งหมดของพวกเขานั้นยิ่งใหญ่กว่าผลรวมของผลกระทบอย่างง่าย ๆ ขององค์ประกอบดังกล่าว การทำงานร่วมกันที่เกิดขึ้นจากการรวมตัวเลือกการออกแบบขนาดเล็กเหล่านี้เข้าด้วยกันเป็นสิ่งที่ช่วยให้ซีพียูสามารถดำเนินการได้ที่ขีดความสามารถสูงสุดของพวกเขา

ตัวเลือกการออกแบบเหล่านี้ยังเป็นข้อ จำกัด :

• ขนาดคิวสูงสุดจะต้องตั้งค่าในเวลาคอมไพล์หรือเวลาการก่อสร้าง ขั้นตอนด้านบัฟเฟอร์แบบวงกลมปัญหาการเรียกคืนหน่วยความจำที่มีอยู่ในคิวตามรายการที่เชื่อมโยงกับราคาของขนาดบัฟเฟอร์คงที่ ดูการเรียกคืนหน่วยความจำที่มีประสิทธิภาพสำหรับโครงสร้างข้อมูลที่ปราศจากล็อคใน C ++ สำหรับรายละเอียดเพิ่มเติม ขนาดบัฟเฟอร์คงที่อาจไม่ได้มีข้อ จำกัด มากนักเนื่องจากเมื่อคิวมีขนาดใหญ่กว่าขนาดที่คาดหวังสูงสุดซึ่งบ่งบอกถึงปัญหาที่องค์ประกอบไม่ได้ใช้งานเร็วพอและหากคิวเพิ่มขึ้นเรื่อย ๆ ความไม่สะดวกที่เห็นได้ชัดเพียงอย่างเดียวคือต้องทำการคำนวณล่วงหน้าเกี่ยวกับสิ่งที่จะเป็นจำนวนองค์ประกอบที่ไม่ได้รับการรับรองที่ใหญ่ที่สุด/ที่ยอมรับได้ในคิว
• ไม่มีฟังก์ชั่นการกด/ป๊อปการปิดกั้นระบบปฏิบัติการ คิวนี้ได้รับการออกแบบมาสำหรับสถานการณ์ที่ต่ำเป็นพิเศษและการใช้ระบบปฏิบัติการที่ปิดกั้นแบบดั้งเดิมจะเป็นการเสียสละเวลาแฝงแบบ push-to-pop สำหรับเวลาแฝงที่เป็นไปได้ต่ำที่สุดเราไม่สามารถปิดกั้นในเคอร์เนล OS ได้เนื่องจากเวลาแฝงของการปลุกของด้ายที่ถูกบล็อกอยู่ที่ประมาณ 1-3 ไมโครวินาทีในขณะที่เวลาการเดินทางไปกลับของคิวนี้อาจต่ำถึง 150 นาโนวินาที

แอพพลิเคชั่นที่มีความล่าช้าต่ำเป็นพิเศษต้องการสิ่งนั้นและไม่มีอะไรเพิ่มเติม ความเรียบง่ายจ่ายออกไปดูปริมาณงานและการตรวจสอบความหน่วงแฝง

แบบอย่าง

คอนเทนเนอร์ที่ปลอดภัยและเป็นที่นิยมอื่น ๆ อีกหลายแห่งใช้สำหรับการอ้างอิงในมาตรฐาน:

• std::mutex - บัฟเฟอร์แหวนขนาดคงที่พร้อม std::mutex
• pthread_spinlock - บัฟเฟอร์แหวนขนาดคงที่พร้อม pthread_spinlock_t
• boost::lockfree::spsc_queue คิวผู้ผลิตเดี่ยวผู้ผลิตเดี่ยวรอฟรีจาก Boost Library
• boost::lockfree::queue คิวผู้ผลิตหลายผู้ผลิตหลายคนที่ไม่ได้ล็อคจาก Boost Library
• 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 จากการสร้างเกลียว Intel
• tbb::concurrent_bounded_queue - คิว eponymous ที่ใช้ในโหมดที่ไม่ปิดกั้นจากการสร้างเกลียว Intel

ใช้ห้องสมุด

คอนเทนเนอร์ที่ให้ไว้เป็นเทมเพลตคลาสเฉพาะส่วนหัวไม่จำเป็นต้องมีอาคาร/ติดตั้ง

ติดตั้งจาก GitHub

1. โคลนโครงการ:

 git clone https://github.com/max0x7ba/atomic_queue.git

2. เพิ่ม Directory atomic_queue/include (ใช้เส้นทางเต็ม) ไปยังเส้นทางรวมของระบบบิลด์ของคุณ
3. #include <atomic_queue/atomic_queue.h> ในแหล่ง C ++ ของคุณ

ติดตั้งโดยใช้ VCPKG

 vcpkg install atomic-queue

ติดตั้งโดยใช้โคนัน

ทำตามการสอนอย่างเป็นทางการเกี่ยวกับวิธีการใช้แพ็คเกจโคนัน รายละเอียดเฉพาะสำหรับห้องสมุดนี้มีอยู่ใน Conancenter

คำแนะนำในการสร้างและเรียกใช้มาตรฐาน

คอนเทนเนอร์ที่ให้ไว้เป็นเทมเพลตคลาสส่วนหัวเท่านั้นที่ต้องใช้ #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

เกณฑ์มาตรฐานยังต้องการให้ห้องสมุด Intel TBB พร้อมใช้งาน สันนิษฐานว่ามีการติดตั้งใน /usr/local/include และ /usr/local/lib หากติดตั้งที่อื่นคุณอาจต้องการแก้ไข cppflags.tbb และ ldlibs.tbb ใน Makefile

ห้องสมุดไตร่ตรอง

คิวที่มีอยู่

• AtomicQueue - ตัวบัฟเฟอร์ขนาดคงที่สำหรับองค์ประกอบอะตอม
• OptimistAtomicQueue บัฟเฟอร์ขนาดคงที่ที่เร็วกว่าสำหรับองค์ประกอบอะตอมซึ่งไม่ว่างเมื่อว่างหรือเต็ม มันเป็น AtomicQueue ที่ใช้กับ push / pop แทน try_push / try_pop
• AtomicQueue2 ตัวบัฟเฟอร์ขนาดคงที่สำหรับองค์ประกอบที่ไม่ใช่อะตอม
• OptimistAtomicQueue2 ตัวบัฟเฟอร์ขนาดคงที่ที่เร็วกว่าสำหรับองค์ประกอบที่ไม่ใช่อะตอมซึ่งไม่ว่างเมื่อว่างหรือเต็ม มันเป็น AtomicQueue2 ที่ใช้กับ push / pop แทน try_push / try_pop

ภาชนะเหล่านี้มี AtomicQueueB ที่สอดคล้องกัน, OptimistAtomicQueueB , AtomicQueueB2 , OptimistAtomicQueueB2 รุ่นที่มีการระบุขนาดบัฟเฟอร์เป็นอาร์กิวเมนต์ของตัวสร้าง

รองรับโหมดที่สั่งซื้อทั้งหมด ในโหมดนี้ผู้บริโภคจะได้รับข้อความในการสั่งซื้อ FIFO เดียวกันข้อความถูกโพสต์ โหมดนี้ได้รับการสนับสนุนสำหรับฟังก์ชั่น push และ pop แต่ไม่ใช่เวอร์ชัน try_ ใน Intel x86 โหมดที่สั่งซื้อทั้งหมดมีค่าใช้จ่าย 0 ณ ปี 2019

รองรับโหมดผู้ผลิตเดี่ยว-ผู้บริโภค ในโหมดนี้ไม่จำเป็นต้องมีคำแนะนำ CPU การอ่านแบบอะตอมที่มีราคาแพงซึ่งจำเป็นต้องมีเพียงโหลดอะตอมและร้านค้าที่ถูกที่สุดเท่านั้น ที่ปรับปรุงปริมาณงานคิวอย่างมีนัยสำคัญ

ประเภทองค์ประกอบคิวแบบย้ายอย่างเดียวได้รับการสนับสนุนอย่างเต็มที่ ตัวอย่างเช่นคิวของ std::unique_ptr<T> องค์ประกอบจะเป็น AtomicQueue2B<std::unique_ptr<T>> หรือ AtomicQueue2<std::unique_ptr<T>, CAPACITY>

คิว API

เทมเพลตคลาสคิวให้ฟังก์ชั่นสมาชิกต่อไปนี้:

• try_push - ผนวกองค์ประกอบเข้ากับคิว ส่งคืน false เมื่อคิวเต็ม
• try_pop - ลบองค์ประกอบออกจากด้านหน้าของคิว ส่งคืน false เมื่อคิวว่างเปล่า
• push (optimist) - ผนวกองค์ประกอบไปยังส่วนท้ายของคิว ไม่ว่างรอเมื่อคิวเต็ม เร็วกว่า try_push เมื่อคิวไม่เต็ม ผู้ผลิต FIFO เป็นทางเลือกในการจัดคิวและคำสั่งซื้อทั้งหมด
• pop (Optimists) - ลบองค์ประกอบออกจากด้านหน้าของคิว ไม่ว่างรอเมื่อคิวว่างเปล่า เร็วกว่า 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 จะต้องไม่ถูกผลักเข้าไปในคิวและมีคำสั่ง assert ในฟังก์ชั่น push เพื่อป้องกันในโหมดดีบั๊กสร้าง การผลักองค์ประกอบ NIL ลงในคิวในโหมดการเปิดตัวสร้างผลลัพธ์ในพฤติกรรมที่ไม่ได้กำหนดเช่นการหยุดชะงักและ/หรือองค์ประกอบคิวที่หายไป

โปรดทราบว่า การมองโลกในแง่ดี เป็นทางเลือกของกระแสการควบคุมการดำเนินการปรับคิวแทนที่จะเป็นประเภทคิว push ในแง่ดีนั้น เร็วที่สุดเมื่อคิวไม่เต็มเวลาส่วนใหญ่ pop ในแง่ดี - เมื่อคิวไม่ว่างเปล่าตลอดเวลา มองโลกในแง่ดีและไม่สามารถผสมได้โดยไม่มีข้อ จำกัด OptimistAtomicQueue s ในเกณฑ์มาตรฐานใช้เฉพาะ push และ pop ในแง่ดี เท่านั้น

ดูตัวอย่าง CCC สำหรับตัวอย่างการใช้งาน

บันทึกการใช้งาน

ลำดับหน่วยความจำของการโหลดที่ไม่ใช่อะตอมและร้านค้า

push และ try_push การดำเนินการ ซิงโครไนซ์กับ (ตามที่กำหนดไว้ใน std::memory_order ) ด้วยการดำเนินการ pop หรือ try_pop ที่ตามมาของวัตถุคิวเดียวกัน หมายความว่า:

• ไม่มีการโหลด / ร้านค้าที่ไม่ได้รับการจัดลำดับใหม่ในอดีต 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 ผู้ประกอบการไบนารีที่เหลือ % โดยปกติจะสร้างคำสั่ง CPU ที่ไม่ถูก แต่ใช้การเปลี่ยนขนาดกำลัง 2 ที่ผู้ประกอบการที่เหลือเป็นคำสั่งไบนารีราคาถูก and CPU หนึ่งคำสั่งและนั่นเร็วเท่าที่จะได้รับ
• ดัชนีองค์ประกอบภายในสายแคช จะถูกสลับกับ ดัชนีสายแคช ดังนั้นองค์ประกอบคิวต่อเนื่องจึงอยู่ในสายแคชที่แตกต่างกัน สิ่งนี้จะช่วยลดการโต้แย้งสายแคชระหว่างผู้ผลิตหลายรายและผู้บริโภคหลายราย แทนที่จะเป็นผู้ผลิต N ร่วมกับผู้บริโภค M ที่แข่งขันกับองค์ประกอบที่ตามมาในสายแคชแหวนตัวบัฟเฟอร์เดียวกันในกรณีที่เลวร้ายที่สุดมันเป็นเพียงผู้ผลิตเพียงรายเดียวที่แข่งขันกับผู้บริโภครายหนึ่ง (pedantically เมื่อจำนวนซีพียูไม่สูงกว่าจำนวนองค์ประกอบที่สามารถพอดีกับสายแคชเดียว) การเพิ่มประสิทธิภาพนี้จะปรับขนาดได้ดีขึ้นด้วยจำนวนผู้ผลิตและผู้บริโภคและขนาดองค์ประกอบ ด้วยจำนวนผู้ผลิตและผู้บริโภคจำนวนน้อย (สูงถึง 2 ของแต่ละคนในเกณฑ์มาตรฐานเหล่านี้) การปิดการใช้งานการเพิ่มประสิทธิภาพนี้อาจให้ปริมาณงานที่ดีขึ้น (แต่ความแปรปรวนที่สูงกว่าในการวิ่ง)

คอนเทนเนอร์ใช้ประเภท unsigned สำหรับขนาดและดัชนีภายใน บนแพลตฟอร์ม X86-64 unsigned มีความกว้าง 32 บิตในขณะที่ size_t กว้าง 64 บิต คำแนะนำ 64 บิตใช้คำนำหน้าคำสั่งไบต์เพิ่มเติมทำให้เกิดแรงกดดันมากขึ้นเล็กน้อยในแคชคำสั่ง CPU และส่วนหน้า ดังนั้นดัชนี unsigned 32 บิตจึงถูกใช้เพื่อเพิ่มประสิทธิภาพสูงสุด นั่น จำกัด ขนาดคิวไว้ที่ 4,294,967,295 องค์ประกอบซึ่งดูเหมือนจะเป็นขีด จำกัด ที่สมเหตุสมผลสำหรับแอปพลิเคชันจำนวนมาก

ในขณะที่คิวอะตอมสามารถใช้กับองค์ประกอบองค์ประกอบที่เคลื่อนย้ายได้ (รวมถึง std::unique_ptr ) สำหรับปริมาณงานที่ดีที่สุดและเวลา push องค์ประกอบคิวควรมีราคาถูกในการคัดลอกและปราศจากล็อค (เช่น pop unsigned หรือ T* )

การรับประกันฟรีล็อค

แนวคิด การดำเนินการ push หรือ pop ทำสองขั้นตอนอะตอม:

1. การเรียกร้องดัชนีสล็อตคิวแบบอะตอมและเฉพาะเพื่อจัดเก็บ/โหลดองค์ประกอบไป/จาก นั่นคือผู้ผลิตที่เพิ่มดัชนี head ผู้บริโภคเพิ่มดัชนี tail แต่ละช่องสามารถเข้าถึงได้โดยผู้ผลิตรายหนึ่งและหนึ่งเธรดผู้บริโภคเท่านั้น
2. เก็บ/โหลดองค์ประกอบใน/จากสล็อต ผู้ผลิตที่จัดเก็บลงในสล็อตจะเปลี่ยนสถานะให้ไม่ใช่ NIL การโหลดผู้บริโภคจากสล็อตจะเปลี่ยนสถานะให้เป็น NIL สล็อตเป็นสปินล็อคสำหรับผู้ผลิตรายเดียวและเธรดผู้บริโภคหนึ่งตัว

คิวเหล่านี้คาดการณ์ว่าเธรดที่ทำ push หรือ pop อาจเสร็จสมบูรณ์ขั้นตอนที่ 1 จากนั้นจะถูกจองล่วงหน้าก่อนที่จะทำตามขั้นตอนที่ 2

อัลกอริทึมนั้น ปราศจากล็อค หากมีการรับประกันความคืบหน้าของระบบ คิวการรับประกันเหล่านี้ความคืบหน้าของระบบทั่วทั้งคุณสมบัติต่อไปนี้:

• push แต่ละครั้งนั้นเป็นอิสระจาก push ก่อนหน้านี้ push ที่ push สมบูรณ์
• pop แต่ละตัวเป็นอิสระจาก pop ก่อนหน้านี้ pop อปที่ pop สมบูรณ์
• pop push ที่ไม่สมบูรณ์ หัวข้ออื่น ๆ ทั้งหมด pop ได้รับผลกระทบ
• pop ที่ไม่สมบูรณ์ (preempted) จากเธรดผู้บริโภคหนึ่งตัวส่งผลกระทบต่อเธรดผู้ผลิตเพียงรายเดียว push องค์ประกอบเข้าไปใน pop คิวนี้โดยเฉพาะในขณะที่คาดว่าจะใช้เวลานานมาแล้วในสถานการณ์ที่ค่อนข้างไม่น่าเป็นไปได้ เธรดอื่น ๆ ทั้งหมด push s และ pop s ไม่ได้รับผลกระทบ

การได้รับ

การตรวจสอบเธรดงาน Linux Task Scheduler เป็นสิ่งที่ไม่มีกระบวนการพื้นที่ผู้ใช้ควรจะสามารถส่งผลกระทบหรือหลบหนีไม่เช่นนั้นแอปพลิเคชันที่เป็นอันตรายใด ๆ/ทุกอย่างจะใช้ประโยชน์จากสิ่งนั้น

ยังมีบางสิ่งที่เราสามารถทำได้เพื่อลดการยกเว้นของภารกิจที่สำคัญของแอปพลิเคชันที่สำคัญของภารกิจ:

• ใช้คลาส SCHED_FIFO แบบเรียลไทม์สำหรับเธรดของคุณเช่น chrt --fifo 50 <app> เธรด SCHED_FIFO ลำดับความสำคัญที่สูงกว่าหรือตัวจัดการอินเตอร์รัปต์เคอร์เนลยังคงสามารถนำเสนอเธรด SCHED_FIFO ของคุณได้
• ใช้ลำดับความสำคัญของการตั้งเวลาแบบเรียลไทม์แบบเรียลไทม์แบบเดียวกันสำหรับเธรดทั้งหมดที่เข้าถึงวัตถุคิวเดียวกัน เธรดแบบเรียลไทม์ที่มีลำดับความสำคัญของการตั้งเวลาที่แตกต่างกันการปรับเปลี่ยนวัตถุคิวหนึ่งชิ้นอาจทำให้เกิดการผกผันลำดับความสำคัญและการหยุดชะงัก การใช้คลาสการตั้งเวลาเริ่มต้น SCHED_OTHER พร้อมลำดับความสำคัญที่ปรับแบบไดนามิกเอาชนะวัตถุประสงค์ของการใช้คิวเหล่านี้
• ปิดการใช้งานเธรดเรียลไทม์เพื่อป้องกันไม่ให้เธรดแบบเรียลไทม์ SCHED_FIFO ถูกควบคุมตัว
• แยกแกน CPU เพื่อไม่ให้ตัวจัดการขัดจังหวะหรือแอปพลิเคชันที่เคยทำงาน แอปพลิเคชั่นที่สำคัญของภารกิจควรวางไว้อย่างชัดเจนบนแกนแยกเหล่านี้ด้วย taskset
• pin threads ไปยังแกนเฉพาะมิฉะนั้นตัวกำหนดตารางเวลางานจะเคลื่อนย้ายเธรดไปยังแกน CPU ที่ไม่ได้ใช้งานอื่น ๆ ไปยังระดับแรงดันไฟฟ้า/การสึกหรอที่เกิดจากความร้อนแกนซีพียูซีพียู การทำให้เธรดทำงานบน CPU Core เดียวกันหนึ่งอัตราการเพิ่มอัตราการตีแคช CPU การย้ายเธรดไปยังคอร์ CPU อื่นเกิดขึ้นเป็นอย่างอื่น CPU แคชที่ไม่จำเป็น

ผู้คนมักจะเสนอ จำกัด การรอคอยที่ยุ่งด้วยการเรียกร้องให้ std::this_thread::yield() / sched_yield / pthread_yield อย่างไรก็ตาม sched_yield เป็นเครื่องมือที่ไม่ถูกต้องสำหรับการล็อคเพราะมันไม่ได้สื่อสารกับเคอร์เนลระบบปฏิบัติการสิ่งที่เธรดกำลังรออยู่ดังนั้นตัวกำหนดตารางเวลาเธรด OS ไม่สามารถกำหนดเวลาเธรดการโทรเพื่อกลับมาใช้งานได้ในเวลาที่เหมาะสมเมื่อสถานะที่ใช้ร่วมกันมีการเปลี่ยนแปลง (เว้นแต่จะไม่มีเธรดอื่น ๆ ดูส่วนหมายเหตุใน man sched_yield และเธรดเคอร์เนล Linux เกี่ยวกับ sched_yield และ spinlocks สำหรับรายละเอียดเพิ่มเติม

ใน Linux มี mutex type PTHREAD_MUTEX_ADAPTIVE_NP ซึ่งยุ่งอยู่กับการล็อค mutex สำหรับการวนซ้ำจำนวนมากจากนั้นทำให้การปิดกั้น syscall เข้าไปในเคอร์เนลเพื่อกำหนดด้ายรอ ในเกณฑ์มาตรฐานมันเป็นนักแสดงที่แย่ที่สุดและฉันไม่สามารถหาวิธีที่จะทำให้มันทำงานได้ดีขึ้นและนั่นคือเหตุผลที่ไม่รวมอยู่ในเกณฑ์มาตรฐาน

บน Intel CPU หนึ่งสามารถใช้การลงทะเบียนควบคุมการดีบัก 4 เพื่อตรวจสอบภูมิภาคหน่วยความจำ Spinlock สำหรับการเข้าถึงการเขียนและรอโดยใช้ select (และเพื่อนของมัน) หรือ sigwait (ดู perf_event_open และ uapi/linux/hw_breakpoint.h สำหรับรายละเอียดเพิ่มเติม) บริกรสปินล็อคสามารถระงับตัวเองด้วย select หรือ sigwait จนกว่าสถานะ Spinlock ได้รับการปรับปรุง แต่มีเพียง 4 ของการลงทะเบียนเหล่านี้ดังนั้นวิธีการแก้ปัญหาดังกล่าวจะไม่ปรับขนาด

เกณฑ์มาตรฐาน

ดูข้อมูลการรับส่งข้อมูลและการตรวจสอบความหน่วงแฝง

วิธีการ

มีพฤติกรรมระบบปฏิบัติการเล็กน้อยที่ทำให้การเปรียบเทียบซับซ้อน:

• CPU Scheduler สามารถวางเธรดบนคอร์ CPU ที่แตกต่างกันในแต่ละการทำงาน เพื่อหลีกเลี่ยงว่าเธรดจะถูกตรึงไว้ในแกน CPU เฉพาะ
• CPU Scheduler สามารถยึดเธรดได้ เพื่อหลีกเลี่ยงการกำหนดลำดับความสำคัญ SCHED_FIFO 50 แบบเรียลไทม์นั้นใช้เพื่อปิดใช้งานควอนตัมเวลาของตารางเวลาการหมดอายุและทำให้เธรดไม่สามารถยกเว้นได้โดยกระบวนการ/เธรดลำดับความสำคัญที่ต่ำกว่า
• การควบคุมการควบคุมปริมาณแบบเรียลไทม์
• การสุ่มพื้นที่ที่อยู่ที่ไม่พึงประสงค์อาจทำให้เกิดความขัดแย้งแคช CPU พิเศษรวมถึงกระบวนการอื่น ๆ ที่ทำงานบนระบบ เพื่อลดผลกระทบของ benchmarks ที่ปฏิบัติการได้นั้นทำงานได้อย่างน้อย 33 ครั้ง แผนภูมิมาตรฐานแสดงค่าเฉลี่ย คำแนะนำเครื่องมือแผนภูมิยังแสดงค่าเบี่ยงเบนมาตรฐานค่าต่ำสุดและค่าสูงสุด

ประสิทธิภาพของเกณฑ์มาตรฐานของคิวผู้ผลิต-ผู้บริโภคเดี่ยว boost::lockfree::spsc_queue , moodycamel::ReaderWriterQueue และคิวเหล่านี้ในโหมดผู้ผลิตเครื่องจักรเดียวควรเหมือนกันเพราะพวกเขาใช้อัลกอริธึมเดียวกัน boost::lockfree::spsc_queue การใช้งานมาตรฐานในเวลานั้นไม่มีการปรับให้เหมาะสมสำหรับการลดการโต้แย้งแคช L1D, สาขาเย็นที่ผิดพลาดหรือแผงขายของท่อจากปัญหาย่อยที่เห็นได้ชัดในรหัสประกอบที่สร้างขึ้นเท่านั้น

ฉันสามารถเข้าถึงเครื่อง X86-64 เพียงไม่กี่เครื่องเท่านั้น หากคุณสามารถเข้าถึงฮาร์ดแวร์ที่แตกต่างกันได้โปรดส่งไฟล์เอาต์พุตของ scripts/run-benchmarks.sh และฉันจะรวมผลลัพธ์ของคุณไว้ในหน้ามาตรฐาน

หน้าใหญ่

เมื่อมีหน้าขนาดใหญ่ที่มีการเปรียบเทียบใช้หน้าขนาดใหญ่ 1x1GB หรือ 16x2MB สำหรับคิวเพื่อลดการพลาด TLB เพื่อให้หน้าจำนวนมากทำอย่างใดอย่างหนึ่ง:

 sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16

อีกทางเลือกหนึ่งคุณอาจต้องการเปิดใช้งานหน้าเว็บขนาดใหญ่ที่โปร่งใสในระบบของคุณและใช้การจัดสรรที่รับรู้จำนวนมากเช่น TCMALLOC

การควบคุมปริมาณแบบเรียลไทม์

โดยค่าเริ่มต้นเธรดแบบเรียลไทม์ของ Linux Scheduler จากการบริโภค CPU 100% และเป็นอันตรายต่อการเปรียบเทียบ รายละเอียดทั้งหมดสามารถพบได้ในการกำหนดเวลากลุ่มแบบเรียลไทม์ เพื่อปิดการใช้งานเธรดแบบเรียลไทม์ Do:

 echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null

เกณฑ์มาตรฐานปริมาณงานและความยืดหยุ่น

n เธรดผู้ผลิตดันจำนวนเต็ม 4 ไบต์ลงในคิวเดียวกันหนึ่งเธรดผู้บริโภคจะปรากฏจำนวนเต็มจากคิว ผู้ผลิตทั้งหมดโพสต์ข้อความทั้งหมด 1,000,000 ข้อความ ใช้เวลาทั้งหมดในการส่งและรับข้อความทั้งหมด เกณฑ์มาตรฐานดำเนินการสำหรับผู้ผลิต 1 รายและผู้บริโภค 1 รายถึง (total-number-of-cpus / 2) ผู้ผลิต / ผู้บริโภคเพื่อวัดความสามารถในการปรับขนาดของคิวที่แตกต่างกัน

เกณฑ์มาตรฐาน Ping-Pong

หนึ่งเธรดโพสต์จำนวนเต็มไปยังเธรดอื่นผ่านหนึ่งคิวและรอการตอบกลับจากคิวอื่น (ทั้งหมด 2 คิว) มาตรฐานวัดเวลาทั้งหมด 100,000 ปิงปองที่ดีที่สุดจาก 10 วิ่ง การโต้แย้งนั้นน้อยที่สุดที่นี่ (1-producer-1-consumer, 1 องค์ประกอบในคิว) เพื่อให้สามารถบรรลุและวัดเวลาแฝงต่ำสุด รายงานเวลาการเดินทางไปกลับโดยเฉลี่ย

การบริจาค

การมีส่วนร่วมเป็นมากกว่าการต้อนรับ .editorconfig และ .clang-format สามารถใช้เพื่อจับคู่การจัดรูปแบบรหัสโดยอัตโนมัติ

สื่อการอ่าน

หนังสือบางเล่มเกี่ยวกับการเขียนโปรแกรมแบบมัลติเธรดฉันพบว่าค่อนข้างให้คำแนะนำ:

• การเขียนโปรแกรมด้วย Posix Threads โดย David R. Butenhof
• ศิลปะการเขียนโปรแกรมหลายโปรเซสเซอร์ โดย Maurice Herlihy, Nir Shavit

---

ลิขสิทธิ์ (c) 2019 Maxim Egorushkin ใบอนุญาต MIT ดูใบอนุญาตเต็มรูปแบบในใบอนุญาตไฟล์