خوارزمية غير حظرية

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
الموسوعة الحرة

في علوم الحاسوب ، يُطلق على الخوارزمية اسم "غير حظرية" إذا كان فشل أو تعليق أي خيط لا يُمكن أن يُسبب فشلًا أو تعليقًا لخيط آخر؛ [ 1 ] بالنسبة لبعض العمليات، تُوفر هذه الخوارزميات بديلاً مفيدًا للتطبيقات الحظرية التقليدية . تُعتبر الخوارزمية غير الحظرية خالية من الأقفال إذا كان هناك ضمان لتقدم النظام ككل ، وخالية من الانتظار إذا كان هناك أيضًا ضمان لتقدم كل خيط على حدة. استُخدم مصطلح "غير حظرية" كمرادف لمصطلح "خالية من الأقفال" في المراجع حتى ظهور مفهوم "التحرر من العوائق" في عام 2003. [ 2 ]

كان مصطلح "غير مانع" يُستخدم تقليديًا لوصف شبكات الاتصالات التي يمكنها توجيه الاتصال عبر مجموعة من المرحلات "دون الحاجة إلى إعادة ترتيب المكالمات القائمة" (انظر شبكة كلوز ). كذلك، إذا كان مقسم الهاتف "غير معطل، فإنه يستطيع دائمًا إتمام الاتصال" (انظر مفتاح التبديل الأدنى غير المانع ).

تحفيز

تعتمد الطريقة التقليدية للبرمجة متعددة الخيوط على استخدام الأقفال لمزامنة الوصول إلى الموارد المشتركة . وتُعدّ أدوات المزامنة الأساسية، مثل الأقفال المتبادلة (mutexes ) والإشارات الثنائية (semaphores ) والأقسام الحرجة ، آلياتٍ تمكّن المبرمج من ضمان عدم تنفيذ أجزاء معينة من التعليمات البرمجية بالتزامن، إذا كان ذلك قد يُؤدي إلى تلف هياكل الذاكرة المشتركة. فإذا حاول أحد الخيوط الحصول على قفلٍ مُستخدمٍ بالفعل من قِبل خيطٍ آخر، فسيتوقف هذا الخيط حتى يتم تحرير القفل.

قد يكون حظر سلسلة العمليات أمرًا غير مرغوب فيه لأسباب عديدة. أحد الأسباب الواضحة هو أنه أثناء حظر سلسلة العمليات، لا يمكنها إنجاز أي شيء: فإذا كانت سلسلة العمليات المحظورة تؤدي مهمة ذات أولوية عالية أو مهمة فورية ، فسيكون من غير المرغوب فيه إيقاف تقدمها.

توجد مشاكل أخرى أقل وضوحًا. على سبيل المثال، قد تؤدي بعض التفاعلات بين الأقفال إلى حالات خطأ مثل التعطل التام ، والتعطل المستمر ، وانعكاس الأولوية . كما ينطوي استخدام الأقفال على مفاضلة بين القفل العام، الذي قد يقلل بشكل كبير من فرص التوازي ، والقفل الدقيق، الذي يتطلب تصميمًا أكثر دقة، ويزيد من تكلفة القفل، وهو أكثر عرضة للأخطاء.

Unlike blocking algorithms, non-blocking algorithms do not suffer from these downsides, and in addition are safe for use in interrupt handlers: even though the preempted thread cannot be resumed, progress is still possible without it. In contrast, global data structures protected by mutual exclusion cannot safely be accessed in an interrupt handler, as the preempted thread may be the one holding the lock. While this can be rectified by masking interrupt requests during the critical section, this requires the code in the critical section to have bounded (and preferably short) running time, or excessive interrupt latency may be observed.[3]

A lock-free data structure can be used to improve performance. A lock-free data structure increases the amount of time spent in parallel execution rather than serial execution, improving performance on a multi-core processor, because access to the shared data structure does not need to be serialized to stay coherent.[4]

Implementation

With few exceptions, non-blocking algorithms use atomicread–modify–write primitives that the hardware must provide, the most notable of which is compare and swap (CAS). Critical sections are almost always implemented using standard interfaces over these primitives (in the general case, critical sections will be blocking, even when implemented with these primitives). In the 1990s all non-blocking algorithms had to be written "natively" with the underlying primitives to achieve acceptable performance. However, the emerging field of software transactional memory promises standard abstractions for writing efficient non-blocking code.[5][6]

Much research has also been done in providing basic data structures such as stacks, queues, sets, and hash tables. These allow programs to easily exchange data between threads asynchronously.

Additionally, some non-blocking data structures are weak enough to be implemented without special atomic primitives. These exceptions include:

  • a single-reader single-writer ring bufferFIFO, with a size which evenly divides the overflow of one of the available unsigned integer types, can unconditionally be implemented safely using only a memory barrier
  • Read-copy-update with a single writer and any number of readers. (The readers are wait-free; the writer is usually lock-free, until it needs to reclaim memory).
  • يدعم هذا النظام القراءة والنسخ والتحديث مع عدة كُتّاب وأي عدد من القراء. (القراء لا ينتظرون؛ أما الكُتّاب المتعددون فيقومون عادةً بالتسلسل مع قفل، ولا يكونون خاليين من العوائق).

تستخدم العديد من المكتبات داخليًا تقنيات خالية من الأقفال، [ 7 ] [ 8 ] [ 9 ] ولكن من الصعب كتابة كود خالٍ من الأقفال يكون صحيحًا. [ 10 ] [ 11 ] [ 12 ] [ 13 ]

تتضمن الخوارزميات غير الحظرية عمومًا سلسلة من تعليمات القراءة، والقراءة-التعديل-الكتابة، والكتابة، بترتيب مُصمم بعناية. يمكن للمُترجمات المُحسّنة إعادة ترتيب العمليات بشكل مُكثف. حتى عندما لا تفعل ذلك، فإن العديد من وحدات المعالجة المركزية الحديثة غالبًا ما تُعيد ترتيب هذه العمليات (لديها " نموذج اتساق ضعيف ")، ما لم يتم استخدام حاجز ذاكرة لإخبار وحدة المعالجة المركزية بعدم إعادة الترتيب. يمكن لمبرمجي C++11 استخدام std::atomic`in` ، ويمكن لمبرمجي C11 استخدام `in`، وكلاهما يُوفر أنواعًا ووظائف تُخبر المُترجم بعدم إعادة ترتيب هذه التعليمات، وإدراج حواجز الذاكرة المُناسبة. [ 14 ]<atomic><stdatomic.h>

حرية الانتظار

يُعدّ مبدأ عدم الانتظار أقوى ضمانة غير مانعة للتقدم، إذ يجمع بين ضمان إنتاجية النظام ككل وعدم التعرض لنقص الموارد . وتكون الخوارزمية خالية من الانتظار إذا كان لكل عملية حدٌّ أقصى لعدد الخطوات التي ستتخذها الخوارزمية قبل إتمام العملية. [ 15 ] هذه الخاصية بالغة الأهمية لأنظمة الوقت الحقيقي، ومن المستحسن وجودها طالما أن تكلفة الأداء ليست مرتفعة للغاية.

لقد ثبت في ثمانينيات القرن الماضي [ 16 ] إمكانية تنفيذ جميع الخوارزميات دون انتظار، وتم إثبات العديد من التحويلات من التعليمات البرمجية التسلسلية، والتي تُسمى بالبنى الشاملة . ومع ذلك، فإن الأداء الناتج لا يُضاهي عمومًا حتى أبسط تصميمات الحجب. وقد حسّنت عدة أبحاث لاحقة أداء البنى الشاملة، ولكن لا يزال أداؤها أقل بكثير من تصميمات الحجب.

تناولت العديد من الأبحاث صعوبة إنشاء خوارزميات خالية من الانتظار. على سبيل المثال، تم إثبات [ 17 ] أن الأدوات الشرطية الذرية المتاحة على نطاق واسع ، CAS و LL/SC ، لا يمكنها توفير تطبيقات خالية من التجويع للعديد من هياكل البيانات الشائعة دون أن تتزايد تكاليف الذاكرة بشكل خطي مع عدد الخيوط.

مع ذلك، لا تُشكّل هذه الحدود الدنيا عائقًا حقيقيًا في التطبيق العملي، إذ  لا يُعتبر إنفاق سطر ذاكرة تخزين مؤقت أو وحدة حجز حصرية (تصل إلى 2 كيلوبايت على معالجات ARM) من مساحة التخزين لكل خيط في الذاكرة المشتركة مكلفًا للغاية بالنسبة للأنظمة العملية. عادةً، تكون مساحة التخزين المطلوبة منطقيًا كلمة واحدة، ولكن عمليات CAS على سطر ذاكرة التخزين المؤقت نفسه ستتصادم، وكذلك عمليات LL/SC في وحدة الحجز الحصرية نفسها، لذا فإن مساحة التخزين المطلوبة فعليًا أكبر.

كانت الخوارزميات الخالية من الانتظار نادرة حتى عام 2011، سواءً في البحث أو التطبيق. مع ذلك، في عام 2011، قدّم كوجان وبيترانك [ 18 ] طابورًا خاليًا من الانتظار مبنيًا على وحدة CAS الأساسية، المتوفرة عمومًا على الأجهزة الشائعة. وقد وسّع تصميمهما طابور مايكل وسكوت الخالي من الأقفال [ 19 ] ، وهو طابور فعّال يُستخدم كثيرًا في التطبيقات العملية. وقدّمت ورقة بحثية لاحقة لكوجان وبيترانك [ 20 ] طريقةً لتسريع الخوارزميات الخالية من الانتظار، واستخدما هذه الطريقة لجعل الطابور الخالي من الانتظار سريعًا عمليًا مثل نظيره الخالي من الأقفال. وقدّمت ورقة بحثية لاحقة لتيمنات وبيترانك [ 21 ] آليةً تلقائيةً لتوليد هياكل بيانات خالية من الانتظار من هياكل بيانات خالية من الأقفال. وهكذا، أصبحت تطبيقات خالية من الانتظار متاحة الآن للعديد من هياكل البيانات.

في ظل افتراضات معقولة، أثبت أليستار، وسينسور-هيلل، وشافيت أن الخوارزميات الخالية من الأقفال تكاد تكون خالية من الانتظار. [ 22 ] وبالتالي، في غياب مواعيد نهائية صارمة، قد لا تكون الخوارزميات الخالية من الانتظار جديرة بالتعقيد الإضافي الذي تُدخله.

حرية القفل

يسمح مبدأ عدم وجود أقفال للخيوط الفردية بالتوقف مؤقتًا مع ضمان إنتاجية النظام ككل. تُعتبر الخوارزمية خالية من الأقفال إذا أحرز خيط واحد على الأقل تقدمًا (وفقًا لتعريف منطقي للتقدم) عند تشغيل خيوط البرنامج لفترة كافية. جميع الخوارزميات الخالية من الانتظار خالية من الأقفال.

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

تُعتبر الخوارزمية خالية من الأقفال إذا نجحت كل عملية على أي معالج في عدد محدود من الخطوات. على سبيل المثال، إذا حاولت N معالجات تنفيذ عملية ما، فستنجح بعض هذه المعالجات في إتمام العملية في عدد محدود من الخطوات، بينما قد تفشل معالجات أخرى وتعيد المحاولة لاحقًا. الفرق بين الخوارزمية الخالية من الانتظار والخوارزمية الخالية من الأقفال هو أن العملية الخالية من الانتظار التي تُنفذها كل معالج مضمونة النجاح في عدد محدود من الخطوات، بغض النظر عن المعالجات الأخرى.

بشكل عام، يمكن لخوارزمية غير مقفلة أن تعمل على أربع مراحل: إكمال العملية الخاصة، ومساعدة عملية معيقة، وإلغاء عملية معيقة، والانتظار. يُعدّ إكمال العملية الخاصة أمرًا معقدًا نظرًا لاحتمالية المساعدة والإلغاء المتزامنين، ولكنه دائمًا ما يكون المسار الأسرع نحو الإكمال.

تقع مسؤولية اتخاذ القرار بشأن وقت تقديم المساعدة أو الإلغاء أو الانتظار عند مواجهة عائق على عاتق مدير التنافس . قد يكون هذا القرار بسيطًا للغاية (تقديم المساعدة للعمليات ذات الأولوية الأعلى، وإلغاء العمليات ذات الأولوية الأقل)، أو قد يكون أكثر كفاءة لتحقيق إنتاجية أفضل، أو لتقليل زمن استجابة العمليات ذات الأولوية.

عادة ما تكون المساعدة المتزامنة الصحيحة هي الجزء الأكثر تعقيدًا في الخوارزمية الخالية من الأقفال، وغالبًا ما تكون مكلفة للغاية للتنفيذ: لا يقتصر الأمر على إبطاء الخيط المساعد فحسب، بل بفضل آليات الذاكرة المشتركة، سيتم إبطاء الخيط الذي تتم مساعدته أيضًا إذا كان لا يزال قيد التشغيل.

حرية من العوائق

يُعدّ ضمان عدم وجود عوائق أضعف ضمان طبيعي لتقدم العمليات دون حجب. وتكون الخوارزمية خالية من العوائق إذا كان بإمكان خيط واحد، عند تنفيذه بمعزل عن باقي الخيوط (أي مع تعليق جميع الخيوط المعيقة)، إكمال عمليته لعدد محدود من الخطوات. [ 15 ] جميع الخوارزميات غير المعتمدة على الأقفال خالية من العوائق.

لا يتطلب مبدأ عدم وجود عوائق سوى إمكانية إيقاف أي عملية غير مكتملة واستعادة التغييرات التي أُجريت. غالبًا ما يؤدي التخلي عن المساعدة المتزامنة إلى خوارزميات أبسط بكثير وأسهل في التحقق من صحتها. أما منع النظام من التعطل المستمر فهو مهمة مدير التنازع.

تستخدم بعض الخوارزميات الخالية من العوائق زوجًا من "علامات الاتساق" في بنية البيانات. تقرأ العمليات التي تقرأ بنية البيانات أولًا إحدى علامتي الاتساق، ثم تقرأ البيانات ذات الصلة في مخزن مؤقت داخلي، ثم تقرأ العلامة الأخرى، ثم تقارن العلامتين. تكون البيانات متسقة إذا كانت العلامتان متطابقتين. قد لا تكون العلامتان متطابقتين عندما تتم مقاطعة القراءة بواسطة عملية أخرى تُحدِّث بنية البيانات. في هذه الحالة، تتجاهل العملية البيانات الموجودة في المخزن المؤقت الداخلي وتعاود المحاولة.

انظر أيضاً

مراجع

  1. ↑ غوتز، برايان؛ بيرلز، تيم؛ بلوخ ، جوشوا؛ بوبير، جوزيف؛ هولمز، ديفيد؛ ليا، دوغ (2006). التزامن في جافا عمليًا . أبر سادل ريفر، نيوجيرسي: أديسون-ويسلي. ص 41. ISBN  9780321349606.
  2. ↑ هيرليهي، م.؛ لوتشانغكو، ف.؛ موير، م. (2003). التزامن الخالي من العوائق: قوائم الانتظار ذات الطرفين كمثال (ملف PDF) . المؤتمر الدولي الثالث والعشرون لأنظمة الحوسبة الموزعة . ص 522. 
  3. ↑ باتلر دبليو. لامبسون ؛ ديفيد د. ريديل (فبراير 1980). "تجربة مع العمليات والمراقبين في ميسا" . اتصالات رابطة مكائن ​​الحوسبة . 23 (2): 105-117 . CiteSeerX 10.1.1.142.5765 . doi : 10.1145/358818.358824 . S2CID 1594544. مؤرشف من الأصل في 25 سبتمبر 2008. تم الاسترجاع في 21 مارس 2018 .  
  4. ↑ غيوم ماركيه، وكارل كينغسفورد. "نهج سريع وخالٍ من الأقفال للعد المتوازي الفعال لتكرارات k-mers" . المعلوماتية الحيوية (2011) 27(6): 764-770. doi : 10.1093/bioinformatics/btr011 "عداد mers في قنديل البحر" .
  5. ↑ هاريس، تيم؛ فريزر، كير (26 نوفمبر 2003). "دعم اللغة للمعاملات الخفيفة" (ملف PDF) . إشعارات ACM SIGPLAN . 38 (11): 388. CiteSeerX 10.1.1.58.8466 . doi : 10.1145/949343.949340 . مؤرشف من الأصل (ملف PDF) في 21 يناير 2012. تم الاسترجاع في 23 ديسمبر 2011 . 
  6. ↑ هاريس، تيم؛ مارلو، س.؛ بيتون-جونز، س.؛ هيرليهي، م. (15-17 يونيو 2005). "معاملات الذاكرة القابلة للتركيب". وقائع ندوة ACM SIGPLAN لعام 2005 حول مبادئ وممارسات البرمجة المتوازية، PPoPP '05 : شيكاغو، إلينوي . نيويورك، نيويورك: مطبعة ACM. الصفحات 48-60 . doi : 10.1145/1065944.1065952 . ISBN   978-1-59593-080-4. S2CID 53245159 . 
  7. ↑ libcds - مكتبة C++ لحاويات غير مقفلة ونظام استعادة ذاكرة آمن
  8. ↑ liblfds - مكتبة لهياكل البيانات غير القابلة للقفل، مكتوبة بلغة C
  9. ↑ مجموعة أدوات التزامن - مكتبة AC لتصميم وتنفيذ الأنظمة غير المتزامنة
  10. ↑ هيرب ساتر. "الرمز الخالي من الأقفال: شعور زائف بالأمان" . مؤرشف من الأصل بتاريخ 2015-09-01.
  11. ↑ هيرب ساتر. "كتابة التعليمات البرمجية بدون قفل: قائمة انتظار مصححة" . مؤرشف من الأصل في 2008-12-05.
  12. ↑ هيرب ساتر. "كتابة قائمة انتظار متزامنة معممة" . مؤرشف بتاريخ 20 نوفمبر 2009 في أرشيف الإنترنت (Wayback Machine).
  13. ↑ هيرب ساتر. "مشكلة الأقفال" . مؤرشف بتاريخ 21 مارس 2009 في أرشيف الإنترنت
  14. ↑ بروس داوسون. "معالجات ARM والبرمجة غير المقيدة" .
  15. 1 2 أنتوني ويليامز. "الأمان: معطل: كيف لا تطلق النار على قدمك باستخدام العمليات الذرية في لغة C++" . 2015. ص 20.
  16. ↑ هيرليهي، موريس ب. (1988). نتائج الاستحالة والشمولية للتزامن الخالي من الانتظار . وقائع الندوة السنوية السابعة لجمعية الحوسبة الآلية حول مبادئ الحوسبة الموزعة. الصفحات 276-290 . doi : 10.1145/62546.62593 . ISBN  0-89791-277-2.
  17. ↑ فيش، فيث ؛ هندلر، داني؛ شافيت، نير (2004). حول الضعف المتأصل في بدائيات التزامن الشرطي . وقائع الندوة السنوية الثالثة والعشرين لجمعية الحوسبة الآلية حول مبادئ الحوسبة الموزعة (PODC). الصفحات 80-87 . doi : 10.1145/1011767.1011780 . ISBN  1-58113-802-4.
  18. ↑ كوجان، أليكس؛ بيترانك، إيريز (2011). طوابير الانتظار الخالية من الانتظار مع مُضيفين ومُزيلين متعددين (ملف PDF) . وقائع الندوة السادسة عشرة لجمعية ACM SIGPLAN حول مبادئ وممارسات البرمجة المتوازية (PPOPP). الصفحات 223-234 . doi : 10.1145/1941553.1941585 . ISBN  978-1-4503-0119-0.
  19. ↑ مايكل، ماجد؛ سكوت، مايكل (1996). خوارزميات طوابير متزامنة بسيطة وسريعة وعملية، مع وبدون حظر . وقائع الندوة السنوية الخامسة عشرة لجمعية الحوسبة الآلية حول مبادئ الحوسبة الموزعة (PODC). الصفحات 267-275 . doi : 10.1145/248052.248106 . ISBN  0-89791-800-2.
  20. ↑ كوجان، أليكس؛ بيترانك، إيريز (2012). طريقة لإنشاء هياكل بيانات سريعة وخالية من الانتظار . وقائع الندوة السابعة عشرة لجمعية ACM SIGPLAN حول مبادئ وممارسات البرمجة المتوازية (PPOPP). الصفحات 141-150 . doi : 10.1145/2145816.2145835 . ISBN  978-1-4503-1160-1.
  21. ↑ تيمنات، شاهار؛ بيترانك، إيريز (2014). محاكاة عملية خالية من الانتظار لهياكل البيانات غير المقفلة . وقائع الندوة السابعة عشرة لجمعية ACM SIGPLAN حول مبادئ وممارسات البرمجة المتوازية (PPOPP). الصفحات 357-368 . doi : 10.1145/2692916.2555261 . ISBN  978-1-4503-2656-8.
  22. ↑ أليستار، دان؛ سينسور-هيلل، كيرين؛ شافيت، نير (2014). هل الخوارزميات المتزامنة الخالية من الأقفال خالية عمليًا من الانتظار؟ وقائع الندوة السنوية السادسة والأربعين لجمعية الحوسبة الآلية حول نظرية الحوسبة (STOC'14). الصفحات 714-723 . arXiv : 1311.3200 . doi : 10.1145/2591796.2591836 . ISBN  978-1-4503-2710-7.