atomic_queue
1.0.0
C ++ 14 قوائم قوائم قفل C ++ متعددة المنتجات المستهلكة القائمة على المخزن المؤقت الدائري و std::atomic .
تم تصميمه بهدف لتقليل الكمون بين مؤشر ترابط واحد يدفع عنصرًا إلى قائمة انتظار وخيط آخر يبرزه من قائمة الانتظار.
تم تطويره واختباره وقياسه على Linux ، ولكن يجب أن يدعم أي منصات C ++ 14 التي تنفذ std::atomic . تم الإبلاغ عنها على أنها متوافقة مع Windows ، ولكن يتم إعداد التكامل المستمر الذي تستضيفه Github حاليًا فقط لمنصة X86_64 على Ubuntu-20.04 و Ubuntu-22.04. يتم الترحيب بطلبات السحب لتوسيع عمليات التكامل المستمرة لتشغيلها على البنى الأخرى و/أو المنصات.
عند التقليل من زمن الوصول ، لا يوجد تصميم جيد عندما لا يوجد شيء يبقى لإضافته ، ولكن عندما لا يوجد شيء يبقى لإزالته ، كما تمثل قوائم الانتظار هذه.
تقليل الكمون بشكل طبيعي يزيد من الإنتاجية. انخفاض الكمون المتبادل هو ارتفاع الظهر ، بمعنى الهندسة الرياضية والعملية المثالية. لا يتوافق الكمون المنخفض مع أي تأخير و/أو تجميع ، والذي يدمر ترتيب الوقت الأصلي للأحداث (الأجهزة) للأحداث في قائمة انتظار واحدة بواسطة مؤشرات ترابط مختلفة. تعظيم الإنتاجية ، من ناحية أخرى ، يمكن القيام به على حساب الكمون من خلال تأخير وتجميع تحديثات متعددة.
مبدأ التصميم الرئيسي هذه قوائم الانتظار تتبعها هو بساطتها ، والتي تؤدي إلى خيارات التصميم مثل:
push / pop ، ولا يمكن الحصول على أي مرجع/مؤشر إلى عناصر في قائمة الانتظار.إن تأثير كل من خيارات التصميم الصغيرة هذه من تلقاء نفسها بالكاد يكون قابلاً للقياس ، لكن تأثيرها الكلي أكبر بكثير من مبلغ بسيط من آثار المكونات ، ويعرف أيضًا باسم المركب الفائق أو التآزر. إن التآزر الناشئ من الجمع بين عدة خيارات التصميم الصغيرة هذه معًا هو ما يسمح لوحدة المعالجة المركزية بالأداء بسعة الذروة التي تعوقها الأقل إعاقة.
خيارات التصميم هذه هي أيضًا قيود:
تحتاج تطبيقات Low-Low-Lownency إلى ذلك تمامًا ولا شيء أكثر من ذلك. تؤتي ثمارها ، انظر معايير الإنتاجية والكمون.
تُستخدم العديد من الحاويات الأخرى الآمنة التي آمنت الخيوط للمرجع في المعايير:
std::mutex - مختصر حلقة ثابتة الحجم مع std::mutex .pthread_spinlock - حلق حلقة ثابتة الحجم مع pthread_spinlock_t .boost::lockfree::spsc_queue قائمة انتظار مستهلك خالية من الانتظار من مكتبة Boost.boost::lockfree::queue انتظار خالية من القفل متعددة المنتجات-مستهلك من مكتبة Boost.moodycamel::ConcurrentQueue قائمة انتظار خالية من القفل متعددة المنتجات-مستهلك مستهلك تستخدم في وضع عدم الحظر. تم تصميم قائمة الانتظار هذه لزيادة الإنتاجية إلى أقصى حد على حساب الكمون وتجنب ترتيب الوقت العالمي للعناصر التي يتم دفعها إلى قائمة انتظار واحدة بواسطة مؤشرات ترابط مختلفة. لا يعادل قوائم الانتظار الأخرى القياسية هنا في هذا الصدد.moodycamel::ReaderWriterQueue قائمة انتظار مستهلك خالية من القفل من المنتجين المستخدمة في وضع عدم الحظر.xenium::michael_scott_queue قائمة انتظار خالية من القفل متعددة المنتجات-المستهلك الذي اقترحه مايكل وسكوت (يشبه قائمة الانتظار هذه boost::lockfree::queue التي تستند أيضًا إلى نفس الاقتراح).xenium::ramalhete_queue قائمة انتظار خالية من القفل متعددة المنتجات والمواد المستهلك التي اقترحها Ramalhete و Correia.xenium::vyukov_bounded_queue قائمة انتظار متعددة المنتجات المحدودة المستهلك بناءً على الإصدار الذي اقترحه Vyukov.tbb::spin_mutex - مختصر حلقة ثابتة مقفل مع tbb::spin_mutex من لبنات بناء ترابط Intel.tbb::concurrent_bounded_queue - قائمة انتظار مسمى مستخدمة في وضع عدم الحظر من لبنات بناء خيوط Intel.الحاويات المقدمة هي قوالب فئة رأس فقط ، لا يوجد أي بناء/تثبيت ضروري.
git clone https://github.com/max0x7ba/atomic_queue.git
atomic_queue/include (استخدم المسار الكامل) إلى مسارات نظام البناء.#include <atomic_queue/atomic_queue.h> في مصدر C ++ الخاص بك. 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.
يتم دعم وضع المستهلك المنفرد المنتشر. في هذا الوضع ، لا توجد تعليمات باهظة الثمن من وحدة المعالجة المركزية القراءة ذات القراءة الذرية ضرورية ، فقط أرخص الأحمال والمتاجر الذرية. أن يحسن إنتاجية قائمة الانتظار بشكل كبير.
يتم دعم أنواع عناصر قائمة الانتظار فقط بالكامل. على سبيل المثال ، ستكون قائمة انتظار 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 (المتفائل) - يزيل عنصرًا من مقدمة قائمة الانتظار. مشغول الانتظار عندما تكون قائمة الانتظار فارغة. أسرع من try_pop عندما لا تكون قائمة الانتظار فارغة. اختياري FIFO المستهلك قائمة الانتظار والترتيب الكلي.was_size - إرجاع عدد العناصر غير المستهلكة أثناء المكالمة. قد تكون الدولة قد تغيرت بحلول الوقت الذي يتم فيه فحص قيمة الإرجاع.was_empty - إرجاع true إذا كانت الحاوية فارغة أثناء المكالمة. قد تكون الدولة قد تغيرت بحلول الوقت الذي يتم فيه فحص قيمة الإرجاع.was_full - إرجاع true إذا كانت الحاوية ممتلئة أثناء المكالمة. قد تكون الدولة قد تغيرت بحلول الوقت الذي يتم فيه فحص قيمة الإرجاع.capacity - إرجاع الحد الأقصى لعدد العناصر التي يمكن أن يحملها قائمة الانتظار. العناصر الذرية هي تلك ، التي true std::atomic<T>{T{}}.is_lock_free() ، وينتج عن ميزات C ++ 17 ، std::atomic<T>::is_always_lock_free تُقيّم إلى true at time. بمعنى آخر ، يمكن لوحدة المعالجة المركزية تحميل وتخزين ومقارنة مثل هذه العناصر أصلاً ذريًا. في x86-64 هذه العناصر هي جميع أنواع الحساب والمؤشرات القياسية C ++.
تحتفظ قوائم انتظار العناصر الذرية بقيمة واحدة لتكون بمثابة علامة عنصر فارغة NIL ، وهي قيمتها الافتراضية هي 0 . يجب ألا يتم دفع قيمة NIL إلى قائمة انتظار وهناك بيان assert في وظائف push للحراسة مقابل بناء وضع التصحيح. يؤدي دفع عنصر NIL إلى قائمة انتظار في وضع الإصدار إلى سلوك غير محدد ، مثل Deadlocks و/أو عناصر قائمة الانتظار المفقودة.
لاحظ أن التفاؤل هو اختيار تدفق التحكم في عملية قائمة الانتظار ، بدلاً من نوع قائمة الانتظار. يكون push المتفائل أسرع عندما لا يكون قائمة الانتظار ممتلئة معظم الوقت ، pop المتفائل - عندما لا تكون قائمة الانتظار فارغة معظم الوقت. يمكن خلط العمليات المتفائلة وليس لذلك مع عدم وجود قيود. يستخدم OptimistAtomicQueue s في المعايير فقط push المتفائل pop .
انظر example.cc للحصول على مثال الاستخدام.
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 لعنصر في قائمة انتظار مرئية في مؤشر ترابط المستهلك try_pop pop العنصر المحدد. تستخدم قوائم الانتظار المتاحة هنا صفيفًا لخزانة الخاتم لتخزين العناصر. يتم إصلاح قدرة قائمة الانتظار في وقت الترجمة أو وقت البناء.
في سيناريو الإنتاج متعددة المنتجات-المستهلك ، يجب ضبط سعة مختلقي الحلقة على الحد الأقصى لحجم قائمة الانتظار المتوقع. عندما يمتلك المخلب الدائري ، فهذا يعني أن المستهلكين لا يمكنهم استهلاك العناصر بسرعة كافية. إصلاح لذلك هو أي من:
push and pop دائمًا بعض دورات وحدة المعالجة المركزية باهظة الثمن للحفاظ على سلامة حالة قائمة الانتظار بطريقة ذرية/متسقة/معزولة فيما يتعلق بالخيوط الأخرى وزيادة هذه التكاليف بشكل خطي مع نمو طابور قائمة الانتظار. غالبًا ما يكون تجميع المنتجين لعناصر أو عناصر صغيرة ناتجة عن حدث واحد إلى رسالة قائمة انتظار واحدة حلاً معقولًا.يتيح استخدام حجم صفيف Power-Of-2 Ring Buffer مجموعة من التحسينات المهمة:
% SIZE المبلغ الثنائي المتبقي. عادةً ما يقوم المشغل الثنائي المتبقي % بإنشاء تعليمات في قسم وحدة المعالجة المركزية التي ليست رخيصة ، ولكن باستخدام دوران في الحجم الثاني 2 ، فإن مشغل الباقي إلى تعليمات ثنائية and المعالجة المركزية واحدة رخيصة وهذا بالسرعة التي يحصل عليها.N مع مستهلكي M الذين يتنافسون على العناصر اللاحقة في نفس خط ذاكرة التخزين المؤقت ذات الحلقة نفسها في أسوأ الحالات ، فإن منتجًا واحدًا فقط يتنافس مع مستهلك واحد (بشكل متقلبين ، عندما لا يكون عدد وحدات المعالجة المركزية أكبر من عدد العناصر التي يمكن أن تتناسب مع خط ذاكرة التخزين المؤقت واحدة). يتجه هذا التحسين بشكل أفضل مع عدد المنتجين والمستهلكين ، وحجم العنصر. مع انخفاض عدد المنتجين والمستهلكين (ما يصل إلى حوالي 2 من كل منهم في هذه المعايير) ، قد يؤدي تعطيل هذا التحسين إلى إنتاجية أفضل (ولكن تباين أعلى عبر عمليات التشغيل). تستخدم الحاويات نوع unsigned للحجم والفهارس الداخلية. على منصة x86-64 unsigned 32 بت ، في حين أن size_t بعرض 64 بت. تستخدم الإرشادات 64 بت بادئة تعليمات بايت إضافية مما يؤدي إلى زيادة الضغط على ذاكرة التخزين المؤقت لاتخاذ تعليمات وحدة المعالجة المركزية والواجهة الأمامية. وبالتالي ، يتم استخدام فهارس 32 بت unsigned لزيادة الأداء. هذا يحد من حجم قائمة الانتظار إلى 4،294،967،295 عنصرًا ، والذي يبدو أنه حد صعب معقول للعديد من التطبيقات.
في حين يمكن استخدام قوائم الانتظار الذرية مع أي أنواع عناصر متحركة (بما في ذلك std::unique_ptr ) ، لأفضل الإنتاجية والكمون ، يجب أن تكون عناصر قائمة الانتظار رخيصة لنسخها وخالية من القفل (على سبيل المثال unsigned أو T* ) ، بحيث تكتمل عمليات push pop أسرع.
من الناحية المفاهيمية ، تقوم عملية push أو pop بخطوتين ذرية:
head ، يقوم المستهلكون بزيادة مؤشر tail . يتم الوصول إلى كل فتحة بواسطة منتج واحد وخيوط مستهلك واحدة فقط.NIL ، ويؤدي التحميل للمستهلك من فتحة إلى تغيير حالتها لتكون NIL . الفتحة هي spinlock لمنتج واحد وخيوط المستهلك. تتوقع قوائم الانتظار هذه أن يقوم مؤشر الترابط الذي يقوم push أو pop بإكمال الخطوة 1 ثم يتم استباقه قبل الانتهاء من الخطوة 2.
الخوارزمية خالية من القفل إذا كان هناك تقدم مضمون على مستوى النظام. هذه قائمة الانتظار تضمن التقدم على مستوى النظام حسب الخصائص التالية:
push مستقلة عن أي push سابقة. لا يؤثر push غير مكتملة (مبدعة) بواسطة مؤشر ترابط منتج واحد push أي مؤشر ترابط آخر.pop مستقلة عن أي pop السابقة. لا يؤثر pop غير المكتمل (الاستبقاء) بواسطة مؤشر ترابط مستهلك واحد pop لأي مؤشر ترابط آخر.push غير مكتملة (استباقية) من مؤشر ترابط منتج واحد فقط على مؤشر pop المستهلك واحد من العنصر من فتحة قائمة الانتظار هذه. جميع المواضيع الأخرى pop لا تتأثر.pop غير المكتملة (غير المحفوظة) من خيط مستهلك واحد فقط على مؤشر ترابط منتج واحد فقط push عنصرًا في فتحة قائمة pop هذه مع توقع أن يكون قد تم استهل جميع المواضيع الأخرى push S و pop s لا تتأثر. يعد عملية الاستمتاع بجدولة Linux Task Screduler شيءًا لا يجب أن تكون عملية مساحة المستخدم قادرة على التأثير أو الهروب ، وإلا فإن أي تطبيق ضار سيستغل ذلك.
ومع ذلك ، هناك بعض الأشياء التي يمكن للمرء القيام بها لتقليل استقرار مؤشرات ترابط التطبيق المهمة:
SCHED_FIFO في الوقت الفعلي لمروحانك ، على سبيل المثال chrt --fifo 50 <app> . لا يزال بإمكان مؤشر ترابط SCHED_FIFO الأعلى أو معالج مقاطعة kernel استباق موضوعات SCHED_FIFO .SCHED_OTHER مع أولوياتها المعدلة ديناميكيًا ، تهزم الغرض من استخدام هذه القوائم.SCHED_FIFO في الوقت الحقيقي من الاختناق.taskset . غالبًا ما يقترح الناس الحد من الانتظار المشغول من خلال مكالمة لاحقة إلى std::this_thread::yield() / sched_yield / pthread_yield . ومع ذلك ، sched_yield هو أداة خاطئة للقفل لأنها لا تتواصل مع kernel OS ما ينتظره مؤشر الترابط ، بحيث لا يمكن لمجدول مؤشر ترابط OS فقط جدولة سلسلة الاتصال للاستئناف في الوقت المناسب عندما تتغير الحالة المشتركة (ما لم يكن هناك أي مؤشرات ترابط أخرى يمكن تشغيلها على قلب وحدة المعالجة المركزية ، بحيث يستأنف المتصل على الفور). راجع قسم الملاحظات في man sched_yield وخيط Linux kernel حول sched_yield و Spinlocks لمزيد من التفاصيل.
في Linux ، هناك نوع Mutex PTHREAD_MUTEX_ADAPTIVE_NP الذي ينشغل بكتابة مقفلة لعدد من التكرارات ثم تجعل سيسال حظر في kernel لإخنان خيط الانتظار. في المعايير ، كان هذا هو أسوأ أداء ولم أتمكن من إيجاد طريقة لجعلها أفضل ، وهذا هو السبب في عدم تضمينه في المعايير.
على وحدة المعالجة المركزية Intel ، يمكن للمرء استخدام سجلات التحكم في التصحيح الأربعة لمراقبة منطقة ذاكرة Spinlock للوصول إلى الكتابة والانتظار باستخدام select (وأصدقائها) أو sigwait (انظر perf_event_open و uapi/linux/hw_breakpoint.h لمزيد من التفاصيل). يمكن لنادل Spinlock تعليق نفسه بـ select أو sigwait حتى يتم تحديث حالة Spinlock. ولكن لا يوجد سوى 4 من هذه السجلات ، بحيث لا يتوسع مثل هذا الحل.
عرض مخططات المعايير الإنتاجية والكمون.
هناك بعض سلوكيات OS التي تعقد القياس:
SCHED_FIFO في الوقت الفعلي ، يتم استخدام أولوية 50 لتعطيل وقت جدولة وقت انتهاء الصلاحية وجعل المواضيع غير معفاة من خلال عمليات/مؤشرات الترابط ذات الأولوية المنخفضة.benchmarks القابلة للتنفيذ يتم تشغيل 33 مرة على الأقل. تعرض المخططات القياسية قيمًا متوسطًا. تعرض Tooltip المخطط أيضًا الانحراف المعياري والحد الأدنى والحد الأقصى للقيم. يجب أن تكون الأداء المعياري لقوائم قوائم الانتظار المستهلكة ذات المنتجين الواحد boost::lockfree::spsc_queue ، moodycamel::ReaderWriterQueue هذه في وضع قوائم الانتظار في وضع مستهلك منفرد للمنتجات الواحدة متطابقة لأنها تنفذ نفس الخوارزمية بالضبط باستخدام نفس الحمل والتخزين. boost::lockfree::spsc_queue تنفيذ المعياري في ذلك الوقت لم يكن لديه أي تحسينات لتقليل خلاف ذاكرة التخزين المؤقت L1D إلى أدنى حد من خلاف ذاكرة التخزين المؤقت ، أو خاطئ الفرع البارد أو أكشاك خطوط الأنابيب من القضايا الدهنية فقط في رمز التجميع الذي تم إنشاؤه.
لدي فقط الوصول إلى بضع آلات X86-64. إذا كان لديك إمكانية الوصول إلى أجهزة مختلفة ، فلا تتردد في إرسال ملف الإخراج من scripts/run-benchmarks.sh .
عندما تتوفر صفحات ضخمة ، تستخدم المعايير صفحات ضخمة 1 × 1 جيجابايت أو 16 × 2 ميغابايت لقوائم الانتظار لتقليل تفويات TLB. لتمكين صفحات ضخمة تفعل واحدة من:
sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16
بدلاً من ذلك ، قد ترغب في تمكين الصفحات الضخمة الشفافة في نظامك واستخدام تخصيص مخصص للمساحة الضخمة ، مثل TCMALLOC.
بشكل افتراضي ، يخنق Linux Scheduler Threads في الوقت الفعلي من استهلاك 100 ٪ من وحدة المعالجة المركزية وهذا يضر بالقياس. يمكن العثور على التفاصيل الكاملة في جدولة المجموعة في الوقت الفعلي. لتعطيل اختناق الموضوع في الوقت الحقيقي:
echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null
تقوم مؤشرات ترابط المنتجين بالضغط على عدد صحيح من 4 بايت في قائمة انتظار واحدة ، وتأمل مؤشرات الترابط المستهلك في الأعداد الصحيحة من قائمة الانتظار. جميع المنتجين ينشرون 1،000،000 رسالة في المجموع. يتم قياس إجمالي الوقت لإرسال واستقبال جميع الرسائل. يتم تشغيل المعيار من منتج واحد ومستهلك واحد يصل إلى (total-number-of-cpus / 2) المنتجين / المستهلكين لقياس قابلية التوسيع في قوائم الانتظار المختلفة.
ينشر مؤشر ترابط واحد عدد صحيح إلى مؤشر ترابط آخر من خلال قائمة انتظار واحدة وينتظر الرد من قائمة انتظار أخرى (قوائم انتظار في المجموع). يقيس المعايير إجمالي الوقت البالغ 100000 Ping-Pongs ، أفضل 10 أشواط. يكون الخلاف ضئيلًا هنا (1-Producer-1-Consumer ، عنصر واحد في قائمة الانتظار) ليكون قادرًا على تحقيق أدنى زمن انتقال. تقارير متوسط وقت الرحلة.
المساهمات أكثر من موضع ترحيب. يمكن استخدام .editorconfig و .clang-format لمطابقة تنسيق الكود تلقائيًا.
بعض الكتب حول موضوع البرمجة متعددة الخيوط وجدت مفيدة للغاية:
حقوق الطبع والنشر (C) 2019 Maxim Egorushkin. رخصة معهد ماساتشوستس للتكنولوجيا. انظر الترخيص الكامل في ترخيص الملف.
