الصفحة الرئيسية>المتعلقة بالبرمجة>ج/ج++
تنزيل

السينيوم

Xenium هي مكتبة رأسية فقط توفر مجموعة من بنيات البيانات المتزامنة وخوارزميات استعادة الذاكرة. يتم تحديد معلمات هياكل البيانات بحيث يمكن استخدامها مع مخططات الاسترداد المختلفة (على غرار الطريقة التي تسمح بها المحكمة الخاصة بلبنان بتخصيص المخصصات).

  • رأس فقط
  • قابلة للتخصيص بدرجة كبيرة
  • لا حاجة إلى رمز التهيئة
  • يدعم العدد الديناميكي للخيوط (لا توجد مواصفات ثابتة لوقت الترجمة)

توفر الوثائق المزيد من التفاصيل.

يعتمد هذا المشروع على عملي السابق في 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 - قائمة انتظار غير محدودة متعددة المنتجين/مستهلكين متعددين مقترحة من قبل مايكل وسكوت [MS96].
  • ramalhete_queue - قائمة انتظار سريعة وغير محدودة ومتعددة المنتجين/المستهلكين مقترحة من قبل Ramalhete [Ram16].
  • vyukov_bounded_queue - قائمة انتظار FIFO محدودة متعددة المنتجين/متعددة المستهلكين استنادًا إلى الإصدار الذي اقترحه Vyukov [Vyu10].
  • kirsch_kfifo_queue - قائمة انتظار غير محدودة متعددة المنتجين/متعددة المستهلكين k-FIFO مقترحة من قبل Kirsch et al. [كلب13].
  • kirsch_bounded_kfifo_queue - قائمة انتظار k-FIFO محددة متعددة المنتجين/متعددة المستهلكين مقترحة من قبل Kirsch et al. [كلب13].
  • nikolaev_queue - قائمة انتظار غير محدودة متعددة المنتجين/متعددة المستهلكين اقترحها نيكولاييف [Nik19].
  • nikolaev_bounded_queue - قائمة انتظار محدودة متعددة المنتجين/متعددة المستهلكين اقترحها نيكولاييف [Nik19].
  • harris_michael_list_based_set - حاوية خالية من القفل تحتوي على مجموعة مرتبة من الكائنات الفريدة. تعتمد بنية البيانات هذه على الحل الذي اقترحه مايكل [Mic02] والذي يعتمد على الاقتراح الأصلي الذي قدمه هاريس [Har01].
  • harris_michael_hash_map - خريطة تجزئة خالية من القفل تعتمد على الحل الذي اقترحه مايكل [Mic02] والذي يعتمد على الاقتراح الأصلي المقدم من Harris [Har01].
  • chase_work_stealing_deque - مجموعة من سرقة العمل بناءً على اقتراح تشيس وليف [CL05].
  • vyukov_hash_map - خريطة تجزئة متزامنة تستخدم قفلًا دقيقًا لعمليات التحديث. هذا التنفيذ مستوحى بشكل كبير من الإصدار الذي اقترحه Vyukov [Vyu08].
  • left_right - تطبيق عام لخوارزمية LeftRight التي اقترحها Ramalhete وCoreia [RC15].
  • 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، ومن ثم فمن المعروف أنها مدعومة:

  • دول مجلس التعاون الخليجي9
  • clang10
  • فيجوال ستوديو 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] تريفور الكسندر براون. استعادة الذاكرة لهياكل البيانات الخالية من القفل: يجب أن تكون هناك طريقة أفضل. في وقائع ندوة ACM لعام 2015 حول مبادئ الحوسبة الموزعة (PODC) ، الصفحات 261-270. ايه سي ام، 2015.
[CL05] ديفيد تشيس ويوسي ليف. ديناميكية دائرية لسرقة العمل. في وقائع الندوة السنوية السابعة عشرة لـ ACM حول التوازي في الخوارزميات والمعماريات (SPAA) ، الصفحات 21-28. ايه سي ام، 2005.
[Fra04] كير فريزر. حرية القفل العملي . أطروحة دكتوراه، مختبر الحاسوب بجامعة كامبريدج، 2004.
[Har01] تيموثي إل هاريس. تنفيذ عملي للقوائم المرتبطة غير المحظورة. في وقائع المؤتمر الدولي الخامس عشر للحوسبة الموزعة (DISC) ، الصفحات 300-314. سبرينغر-فيرلاغ، 2001.
[HMBW07] توماس إي هارت، بول إي ماكيني، أنجيلا ديمكي براون، وجوناثان والبول. أداء استعادة الذاكرة للمزامنة بدون قفل. مجلة الحوسبة المتوازية والموزعة، 67(12):1270-1285، 2007.
[KLP13] كريستوف كيرش، ومايكل ليبوتز، وهانس باير. قوائم انتظار k-FIFO سريعة وقابلة للتطوير وخالية من القفل. في وقائع المؤتمر الدولي لتقنيات الحوسبة المتوازية (PaCT) ، الصفحات 208-223، Springer-Verlag، 2013.
[ميكروفون02] ماجد م. مايكل. جداول تجزئة ديناميكية عالية الأداء وخالية من القفل ومجموعات قائمة على القائمة. في وقائع ندوة ACM السنوية الرابعة عشرة حول الخوارزميات والمعماريات المتوازية (SPAA) ، الصفحات 73-82. ايه سي ام، 2002.
[ميكروفون04] ماجد م. مايكل. مؤشرات الخطر: استعادة الذاكرة الآمنة للكائنات الخالية من القفل. معاملات IEEE على الأنظمة المتوازية والموزعة، 15(6):491-504، 2004.
[MS95] ماجد م. مايكل ومايكل ل. سكوت. تصحيح طريقة إدارة الذاكرة لهياكل البيانات الخالية من القفل. التقرير الفني، جامعة روتشستر، 1995.
[MS96] ماجد م. مايكل ومايكل ل. سكوت. خوارزميات قائمة الانتظار المتزامنة بسيطة وسريعة وعملية وغير قابلة للحظر. في وقائع ندوة ACM السنوية الخامسة عشرة حول مبادئ الحوسبة الموزعة (PODC) ، الصفحات 267-275. ايه سي ام، 1996.
[نيك19] رسلان نيكولاييف قائمة انتظار قابلة للتطوير ومحمولة وفعالة في الذاكرة وخالية من القفل. في وقائع الندوة الدولية الثالثة والثلاثين للحوسبة الموزعة (DISC) ، 2019.
[PT18a] مانويل بوتر وجيسبر لارسون تراف. إعلان موجز: Stamp-it، وهو نظام أكثر فعالية لاستعادة الذاكرة المتزامنة في نموذج الذاكرة C++. في وقائع ندوة ACM السنوية الثلاثين حول التوازي في الخوارزميات والمعماريات (SPAA) ، الصفحات من 355 إلى 358. ايه سي ام، 2018.
[PT18b] مانويل بوتر وجيسبر لارسون تراف. Stamp-it، وهو نظام أكثر فعالية لاستعادة الذاكرة المتزامنة في نموذج الذاكرة C++. التقرير الفني، 2018.
[رام16] بيدرو رامالهيت. FAAArrayQueue - قائمة انتظار MPMC الخالية من القفل (الجزء 4 من 4). المدونة، نوفمبر 2016.
[RC15] بيدرو رامالهيتي وأندريا كوريا. اليسار واليمين - أسلوب التحكم في التزامن مع القراءات الغافلة الخالية من الانتظار. أكتوبر 2015
[RC17] بيدرو رامالهيتي وأندريا كوريا. إعلان موجز: عصور الخطر - استعادة الذاكرة غير المحظورة. في وقائع الندوة السنوية التاسعة والعشرين لـ ACM حول التوازي في الخوارزميات والمعماريات (SPAA) ، الصفحات من 367 إلى 369. ايه سي ام، 2017.
[روب 13] القوس د.روبيسون. تصميم قائم على السياسات للتدمير الآمن في الحاويات المتزامنة. ورقة لجنة معايير C++، 2013.
[Val95] جون د. فالوا. هياكل البيانات الخالية من القفل . أطروحة دكتوراه، معهد رينسيلار للفنون التطبيقية، 1995.
[Vyu08] ديمتري فيوكوف. خريطة تجزئة قابلة للتطوير. منشور مجموعات جوجل، 2008.
[فيو10] ديمتري فيوكوف. قائمة انتظار MPMC بسيطة وفعالة. نشر مجموعات جوجل، 2010.
يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل