هل البرمجة المجانية المتعددة مؤشرات الترابط تجعل أي شيء أسهل؟

Question

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

إذن الأمر كله يتعلق بالأداء - هل هذا صحيح؟

Answer 1

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

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

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

Answer 2

زوجين من القضايا.

سنواجه قريبًا أنظمة سطح المكتب مع 64 و 128 و 256 نوى. إن المنظر في هذا المجال يختلف عن تجربتنا الحالية المتمثلة في 2 ، 4 ، 8 النوى ؛ سيتم تشغيل الخوارزميات التي تعمل بنجاح على مثل هذه الأنظمة الصغيرة أبطأ على أنظمة متوازية للغاية بسبب الخلاف.

وبهذا المعنى ، يعد قفلًا مهمًا لأنه يساهم بقوة في حل قابلية التوسع.

هناك أيضًا بعض المناطق المحددة للغاية حيث تكون القفل مريحة للغاية ، مثل نوافذ النوافذ ، حيث توجد أنماط التنفيذ حيث يتم حظر النوم من أي نوع (مثل الانتظار) ، وهو أمر محدود للغاية فيما يتعلق بهياكل البيانات ، ولكن حيث يوفر Lock Free حلاً جيدًا.

أيضًا ، غالبًا ما لا تحتوي هياكل البيانات الخالية من القفل على أوضاع الفشل ؛ لا يمكنهم بالفعل أن يفشلوا ، حيث يمكن للطبعات أن تفشل هياكل البيانات المستندة إلى القفل في الحصول على أقفالها. عدم القلق بشأن الفشل يبسط الكود.

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

Answer 3

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

الطريقة التقليدية للقيام بذلك هي قفل هياكل البيانات التي تتطلب الوصول الموازي ولكن كلما زاد عدد الخيوط التي يمكنك تشغيلها بشكل متوازي حقًا ، كلما أصبح عنق الزجاجة أكبر.

لذا نعم ، إنه يتعلق بالأداء ...

Answer 4

بالنسبة للخيوط الاستباقية ، يمكن أن تُعلق المواضيع أثناء حمل القفل خيوطًا من شأنها إحراز تقدم إلى الأمام. لا يملك Lock-Free هذه المشكلة لأنه من خلال تعريف Herlihy ، يمكن لبعض الخيوط الأخرى دائمًا إحراز تقدم إلى الأمام.

بالنسبة للخيوط غير المعززة ، لا يهم أن الحلول القائمة على قفل الدوران خالية من القفل من خلال تعريف Herlihy.

Answer 5

يتعلق الأمر بالعروض - ولكن أيضًا حول القدرة على أخذ الأحمال المتعددة:

• أقفال منح الوصول الحصري إلى جزء من التعليمات البرمجية: على الرغم من أن الخيط يحتوي على قفل ، إلا أن الخيوط الأخرى تدور (حلقة أثناء محاولة الحصول على القفل) أو حظرها ، والنوم حتى يتم إطلاق القفل (والذي يحدث عادة إذا استمر الغزل لفترة طويلة) ؛

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

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

(*) طالما عدد عدد وحدات المعالجة المركزية المتزامنة إن محاولة الوصول إلى نفس المورد لا تنشئ عنق الزجاجة - لكن ليس لدينا ما يكفي من نوى وحدة المعالجة المركزية حتى الآن لنرى هذا يمثل مشكلة.

لقد عملت في هذا الأمر لكتابة أ خالية من الانتظار (خالية من القفل بدون حالات الانتظار) متجر قيمة المفاتيح للخادم الذي أعمل عليه.

تعتمد المكتبات مثل خزانة طوكيو (حتى معدة TC ، وهي صفيف بسيط) على أقفال للحفاظ على سلامة قاعدة البيانات:

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

نتائج الاختبار دون تزامن (اختبار واحد):

SQLite   time: 56.4 ms (a B-tree)
TC       time: 10.7 ms (a hash table)
TC-FIXED time:  1.3 ms (an array)
G-WAN KV time:  0.4 ms (something new which works, but I am not sure a name is needed)

مع التزامن (العديد من الخيوط كتابة وقراءة في نفس DB) ، نجا فقط G-Wan KV من نفس الاختبار لأنه (على النقيض من الآخرين) لا يحجب أبدًا.

لذا ، نعم ، هذا المتجر KV يجعل من السهل على التطوير استخدامه لأنه لا يتعين عليهم الاهتمام بمشكلات الخيوط. جعلها تعمل بهذه الطريقة لم يكن تافها.

Answer 6

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

في ملاحظة جانبية ، وجدت أيضًا دليلًا آخر أظهر أن أي خوارزمية خالية من القفل يمكن اعتبارها بالفعل خالية من الانتظار بسبب قوانين الاحتمالات وعوامل أخرى مختلفة.

Answer 7

1. قابلية التوسع هي قضية مهمة حقًا في برمجة Manicore الفعالة. أكبر عامل محدد هو في الواقع قسم التعليمات البرمجية الذي يجب تنفيذه في المسلسل (انظر قانون أمدال). ومع ذلك ، فإن الادعاءات على الأقفال هي أيضا مشكلة كبيرة.

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

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

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

لا يزال طويل جدًا: ملخص جملان.

بنية البيانات الخالية من القفل ليست دواءً لبرمجة Multithreading المستندة إلى القفل (حتى TM ليست كذلك. إذا كنت بحاجة إلى قابلية التوسع بشكل خطير ولديك مشكلات في خلاف القفل ، ففكر في بنية البيانات الخالية من القفل.