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

الموسوعة الحرة

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

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

تحفيز

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

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

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

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

يمكن استخدام بنية بيانات غير مقفلة لتحسين الأداء. تزيد بنية البيانات غير المقفلة من الوقت المستغرق في التنفيذ المتوازي مقارنةً بالتنفيذ التسلسلي، مما يحسن الأداء على المعالجات متعددة النوى ، لأن الوصول إلى بنية البيانات المشتركة لا يحتاج إلى تسلسل للحفاظ على التماسك. [ 4 ]

تطبيق

باستثناءات قليلة، تستخدم الخوارزميات غير المتزامنة عمليات قراءة-تعديل-كتابة ذرية يجب أن يوفرها الجهاز، وأبرزها عملية المقارنة والتبديل (CAS) . تُنفذ الأقسام الحرجة عادةً باستخدام واجهات قياسية لهذه العمليات (في الحالة العامة، ستكون الأقسام الحرجة متزامنة، حتى عند تنفيذها باستخدام هذه العمليات). في تسعينيات القرن الماضي، كان لا بد من كتابة جميع الخوارزميات غير المتزامنة "أصليًا" باستخدام العمليات الأساسية لتحقيق أداء مقبول. مع ذلك، يعد مجال ذاكرة المعاملات البرمجية الناشئ بتوفير تجريدات قياسية لكتابة شيفرة غير متزامنة فعالة. [ 5 ] [ 6 ]

كما أُجريت العديد من الأبحاث في مجال توفير هياكل البيانات الأساسية مثل المكدسات ، والطوابير ، والمجموعات ، وجداول التجزئة . وتتيح هذه الهياكل للبرامج تبادل البيانات بسهولة بين الخيوط بشكل غير متزامن.

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

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

تستخدم العديد من المكتبات داخليًا تقنيات خالية من الأقفال، [ 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.