كيف يمكنني كتابة هيكل خالي من القفل؟
https://stackoverflow.com/questions/92455
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
في تطبيقي متعدد مؤشرات الترابط، أرى تنافسًا شديدًا على القفل فيه، مما يمنع قابلية التوسع الجيدة عبر مراكز متعددة.لقد قررت استخدام البرمجة المجانية للقفل لحل هذه المشكلة.
كيف يمكنني كتابة هيكل خالي من القفل؟
المحلول
الإجابة المختصرة هي:
انت لا تستطيع.
الجواب الطويل هو:
إذا كنت تطرح هذا السؤال، فمن المحتمل أنك لا تعرف ما يكفي لتتمكن من إنشاء بنية خالية من القفل.يعد إنشاء هياكل خالية من الأقفال أمرًا صعبًا للغاية، ولا يستطيع القيام بذلك سوى الخبراء في هذا المجال.بدلاً من كتابة ما تريده، ابحث عن تطبيق موجود.عندما تجده، تحقق من مدى انتشار استخدامه، ومدى جودة توثيقه، وإذا تم إثباته جيدًا، وما هي القيود - حتى أن بعض الهياكل الخالية من القفل التي نشرها أشخاص آخرون معطلة.
إذا لم تجد بنية خالية من القفل تتوافق مع البنية التي تستخدمها حاليًا، فبدلاً من ذلك قم بتعديل الخوارزمية بحيث يمكنك استخدام بعض الهياكل الموجودة.
إذا كنت لا تزال مصرًا على إنشاء هيكل خالٍ من القفل خاص بك، فتأكد مما يلي:
- ابدأ بشيء بسيط جدًا
- فهم نموذج الذاكرة للنظام الأساسي المستهدف (بما في ذلك قيود إعادة ترتيب القراءة/الكتابة، وما هي العمليات الذرية)
- ادرس الكثير عن المشكلات التي واجهها الأشخاص الآخرون عند تنفيذ الهياكل الخالية من القفل
- لا تخمن فقط ما إذا كانت ستنجح، بل أثبت ذلك
- اختبار النتيجة بشدة
المزيد من القراءة:
نصائح أخرى
استخدم مكتبة مثل اللبنات الأساسية لخيوط Intel, ، فهو يحتوي على عدد لا بأس به من الهياكل والخوارزميات الخالية من القفل.لا أوصي حقًا بمحاولة كتابة تعليمات برمجية خالية من القفل بنفسك، فهي عرضة للخطأ للغاية ويصعب الحصول عليها بشكل صحيح.
من الصعب كتابة كود مجاني لقفل آمن للخيط؛لكن هذه المقالة من هيرب سوتر سوف تحصل على انك بدأته.
مثل sblundy كما أشار، إذا كانت جميع الكائنات غير قابلة للتغيير، للقراءة فقط، فلا داعي للقلق بشأن القفل، ومع ذلك، فإن هذا يعني أنك قد تضطر إلى نسخ الكائنات كثيرًا.يتضمن النسخ عادة استخدام malloc و malloc القفل لمزامنة تخصيصات الذاكرة عبر سلاسل الرسائل، لذا فإن الكائنات غير القابلة للتغيير قد تشتري لك أقل مما تعتقد (malloc نفسه يتوسع بشكل سيء إلى حد ما و malloc هو بطيء;إذا قمت بالكثير من عمليات Malloc في قسم حرج للأداء، فلا تتوقع أداءً جيدًا).
عندما تحتاج فقط إلى تحديث المتغيرات البسيطة (على سبيل المثال.32 أو 64 بت أو مؤشرات)، قم بإجراء عمليات الجمع أو الطرح عليها ببساطة أو قم فقط بتبديل قيم متغيرين، معظم المنصات تقدم "عمليات ذرية" لذلك (المزيد من دول مجلس التعاون الخليجي تقدم هذه أيضًا). الذرية ليست مثل الخيط الآمن.ومع ذلك، يتأكد atomic من أنه إذا كتب أحد الخيوط قيمة 64 بت إلى موقع في الذاكرة على سبيل المثال وقام خيط آخر بالقراءة منه، فإن القراءة إما تحصل على القيمة قبل عملية الكتابة أو بعد عملية الكتابة، ولكن لا تحصل أبدًا على القيمة. مكسور القيمة بين عملية الكتابة (على سبيل المثالحيث تكون أول 32 بت هي القيمة الجديدة بالفعل، وآخر 32 بت لا تزال هي القيمة القديمة!يمكن أن يحدث هذا إذا كنت لا تستخدم الوصول الذري على مثل هذا المتغير).
ومع ذلك، إذا كان لديك بنية C تحتوي على 3 قيم، وتريد تحديثها، حتى إذا قمت بتحديث الثلاثة جميعًا بعمليات ذرية، فهذه ثلاث عمليات مستقلة، وبالتالي قد يرى القارئ البنية ذات قيمة واحدة يتم تحديثها بالفعل واثنتان لا يتم تحديثهما محدث.ستحتاج هنا إلى قفل إذا كان عليك التأكد من أن القارئ إما يرى أن جميع القيم في البنية هي القيم القديمة أو الجديدة.
إحدى الطرق لتحسين حجم الأقفال هي استخدام أقفال R/W.في كثير من الحالات، تكون تحديثات البيانات نادرة إلى حد ما (عمليات الكتابة)، ولكن الوصول إلى البيانات متكرر جدًا (قراءة البيانات)، فكر في المجموعات (جداول التجزئة والأشجار).في هذه الحالة، ستشتري لك أقفال R/W مكاسب هائلة في الأداء، حيث يمكن للعديد من الخيوط الاحتفاظ بقفل القراءة في نفس الوقت (لن تحظر بعضها البعض) وفقط إذا كان أحد الخيوط يريد قفل الكتابة، فإن جميع الخيوط الأخرى محظورة في الوقت الذي يتم فيه إجراء التحديث.
أفضل طريقة لتجنب مشكلات سلاسل الرسائل هي عدم مشاركة أي بيانات عبر سلاسل الرسائل.إذا كان كل مؤشر ترابط يتعامل معظم الوقت مع البيانات التي لا يستطيع أي مؤشر ترابط آخر الوصول إليها، فلن تحتاج إلى قفل تلك البيانات على الإطلاق (أيضًا لا توجد عمليات ذرية).لذا حاول مشاركة أقل قدر ممكن من البيانات بين سلاسل الرسائل.فأنت تحتاج فقط إلى طريقة سريعة لنقل البيانات بين سلاسل الرسائل إذا كان عليك فعل ذلك (ITC، Inter Thread Communication).اعتمادًا على نظام التشغيل والنظام الأساسي ولغة البرمجة لديك (للأسف لم تخبرنا بأي منهما)، قد تكون هناك طرق قوية متعددة لمركز التجارة الدولية (ITC).
وأخيرًا، هناك خدعة أخرى للعمل مع البيانات المشتركة ولكن دون أي قفل وهي التأكد من عدم وصول سلاسل الرسائل إلى نفس الأجزاء من البيانات المشتركة.على سبيل المثال.إذا كان هناك خيطان يشتركان في مصفوفة، ولكن أحدهما لن يتمكن من الوصول إلا إلى فهارس فردية، فإن الآخر لن يحتاج إلا إلى فهارس فردية، فلن تحتاج إلى القفل.أو إذا كان كلاهما يشتركان في نفس كتلة الذاكرة ويستخدم أحدهما النصف العلوي فقط، والآخر يستخدم النصف السفلي فقط، فلن تحتاج إلى القفل.على الرغم من أنه لم يُقال أن هذا سيؤدي إلى أداء جيد؛لا سيما على وحدات المعالجة المركزية متعددة النواة.قد تؤدي عمليات كتابة مؤشر ترابط واحد إلى هذه البيانات المشتركة (تشغيل نواة واحدة) إلى مسح ذاكرة التخزين المؤقت لمؤشر ترابط آخر (يعمل على نواة أخرى) وغالبًا ما تكون عمليات مسح ذاكرة التخزين المؤقت هذه بمثابة عنق الزجاجة لتطبيقات مؤشرات الترابط المتعددة التي تعمل على وحدات المعالجة المركزية الحديثة متعددة النواة.
كما قال أستاذي (نير شافيت من "فن برمجة المعالجات المتعددة") للفصل:من فضلك لا تفعل ذلك.السبب الرئيسي هو قابلية الاختبار - لا يمكنك اختبار رمز المزامنة.يمكنك تشغيل عمليات المحاكاة، ويمكنك حتى إجراء اختبار التحمل.لكنه تقريب تقريبي في أحسن الأحوال.ما تحتاجه حقًا هو إثبات الصحة الرياضية.وقليلون هم القادرون على فهمها، ناهيك عن كتابتها.ولذلك كما قال آخرون:استخدام المكتبات الموجودة. مدونة جو دافي يستعرض بعض التقنيات (القسم 28).أول شيء يجب أن تجربه هو تقسيم الأشجار - تقسيم المهام الصغيرة والجمع بينها.
الثبات هو أحد الأساليب لتجنب القفل.يرى مناقشة اريك ليبرت وتنفيذ أشياء مثل الأكوام وقوائم الانتظار غير القابلة للتغيير.
في إعادة.إجابة سوما، يظهر موريس هيرليثي في فن برمجة المعالجات المتعددة ذلك في الواقع أي شئ يمكن كتابتها بدون أقفال (انظر الفصل 6).iirc، يتضمن هذا بشكل أساسي تقسيم المهام إلى عناصر عقدة المعالجة (مثل إغلاق الوظيفة)، ووضع كل منها في قائمة الانتظار.ستقوم الخيوط بحساب الحالة من خلال متابعة جميع العقد من أحدث عقدة مخبأة.من الواضح أن هذا قد يؤدي، في أسوأ الحالات، إلى أداء تسلسلي، لكنه يتمتع بخصائص مهمة غير قابلة للقفل، مما يمنع السيناريوهات التي يمكن فيها جدولة سلاسل العمليات لفترات طويلة من الوقت عندما تكون مقفلة.يحقق Herlithy أيضًا أداءً نظريًا خاليًا من الانتظار، مما يعني أن مؤشر ترابط واحد لن ينتهي به الأمر إلى الانتظار إلى الأبد للفوز بقائمة الانتظار الذرية (هذا كثير من التعليمات البرمجية المعقدة).
تعد قائمة الانتظار/المكدس متعددة الخيوط صعبة بشكل مدهش (راجع ملف مشكلة أبا).أشياء أخرى قد تكون بسيطة جدا.اعتد على الكتل while(true) { atomicCAS حتى قمت بتبديلها }؛إنهم أقوياء بشكل لا يصدق.إن الحدس بشأن ما هو صحيح في CAS يمكن أن يساعد في التطوير، على الرغم من أنه يجب عليك استخدام اختبارات جيدة وربما أدوات أكثر قوة (ربما رسم, ، معهد ماساتشوستس للتكنولوجيا القادم كندو, ، أو يلف؟) للتحقق من صحتها إذا كان بإمكانك اختصارها إلى بنية بسيطة.
يرجى نشر المزيد عن مشكلتك.من الصعب إعطاء إجابة جيدة دون تفاصيل.
يحرر الثبات أمر جميل ولكن قابليته للتطبيق محدودة، إذا كنت أفهم ذلك بشكل صحيح.إنه لا يتغلب حقًا على مخاطر الكتابة بعد القراءة؛فكر في تنفيذ خيطين "mem = NewNode(mem)";كان بإمكانهما قراءتها، ثم كتابتها؛ليست صحيحة لوظيفة الزيادة الكلاسيكية.ومن المحتمل أيضًا أن يكون بطيئًا بسبب تخصيص الكومة (الذي يجب مزامنته عبر سلاسل العمليات).
سيكون للثبات هذا التأثير.تؤدي التغييرات التي يتم إجراؤها على الكائن إلى ظهور كائن جديد.تعمل Lisp بهذه الطريقة تحت الأغطية.
البند 13 من جافا فعالة يشرح هذه التقنية.
أجرى Cliff Click بعض الأبحاث الرئيسية حول هياكل البيانات الخالية من القفل من خلال استخدام أجهزة الحالة المحدودة ونشر أيضًا الكثير من التطبيقات لـ Java.يمكنك العثور على أوراقه وشرائحه وتطبيقاته على مدونته: http://blogs.azulsystems.com/cliff/
استخدم تطبيقًا موجودًا، حيث أن مجال العمل هذا هو مجال خبراء المجال وحملة الدكتوراه (إذا كنت تريد أن يتم ذلك بشكل صحيح!)
على سبيل المثال توجد مكتبة أكواد هنا:
تبدأ معظم الخوارزميات أو الهياكل الخالية من القفل ببعض العمليات الذرية، أي.سيتم إكمال التغيير في بعض مواقع الذاكرة التي بدأها مؤشر ترابط قبل أن يتمكن أي مؤشر ترابط آخر من تنفيذ نفس العملية.هل لديك مثل هذه العملية في بيئتك؟
يرى هنا للورقة القانونية حول هذا الموضوع.
جرب هذا أيضًا مقالة ويكيبيديا مقالة لمزيد من الأفكار والروابط.
المبدأ الأساسي للمزامنة الخالية من القفل هو:
عندما تقرأ البنية، تتبع القراءة باختبار لمعرفة ما إذا كانت البنية قد تحورت منذ أن بدأت القراءة، ثم أعد المحاولة حتى تنجح في القراءة دون أن يأتي شيء آخر ويتحور أثناء قيامك بذلك؛
عندما تقوم بتغيير البنية، فإنك تقوم بترتيب الخوارزمية والبيانات الخاصة بك بحيث تكون هناك خطوة ذرية واحدة والتي، إذا تم اتخاذها، تجعل التغيير بأكمله مرئيًا للخيوط الأخرى، وترتب الأشياء بحيث لا يكون أي من التغيير مرئيًا إلا إذا تم اتخاذ هذه الخطوة.يمكنك استخدام أي آلية ذرية خالية من القفل موجودة على النظام الأساسي الخاص بك لهذه الخطوة (على سبيل المثال.مقارنة وتعيين، تحميل مرتبط + تخزين مشروط، وما إلى ذلك).في هذه الخطوة، يجب عليك بعد ذلك التحقق لمعرفة ما إذا كان هناك أي مؤشر ترابط آخر قد قام بتحويل الكائن منذ بدء عملية التحويل، والالتزام إذا لم يحدث ذلك والبدء من جديد إذا حدث ذلك.
هناك الكثير من الأمثلة على الهياكل الخالية من القفل على الويب؛دون معرفة المزيد حول ما تقوم بتنفيذه وعلى أي منصة من الصعب أن تكون أكثر تحديدًا.
إذا كنت تكتب هياكل البيانات الخاصة بك الخالية من القفل لوحدة المعالجة المركزية متعددة النواة، فلا تنس حواجز الذاكرة!أيضا، النظر في النظر ذاكرة المعاملات البرمجية التقنيات.
حسنًا، يعتمد الأمر على نوع البنية، ولكن عليك إنشاء البنية بحيث تكتشف التعارضات المحتملة وتتعامل معها بعناية وصمت.
أشك في أنه يمكنك صنع واحدة خالية من القفل بنسبة 100%، ولكن مرة أخرى، يعتمد ذلك على نوع الهيكل الذي تحتاج إلى بنائه.
قد تحتاج أيضًا إلى تقسيم البنية بحيث تعمل مؤشرات الترابط المتعددة على عناصر فردية، ثم تتم مزامنتها/إعادة دمجها لاحقًا.
كما ذكرنا سابقًا، يعتمد الأمر حقًا على نوع الهيكل الذي تتحدث عنه.على سبيل المثال، يمكنك كتابة قائمة انتظار محدودة خالية من القفل، ولكن ليس قائمة انتظار تسمح بالوصول العشوائي.
تقليل أو إزالة الحالة المشتركة القابلة للتغيير.
في Java، استخدم الحزم java.util.concurrent في JDK 5+ بدلاً من كتابة حزمتك الخاصة.كما ذكرنا سابقًا، يعد هذا مجالًا للخبراء حقًا، وما لم يكن لديك سنة أو سنتين إضافيتين، فإن البدء في العمل الخاص بك ليس خيارًا.
هل يمكنك توضيح ما تقصده بالهيكل؟
الآن، أفترض أنك تقصد البنية الشاملة.يمكنك تحقيق ذلك من خلال عدم مشاركة الذاكرة بين العمليات، وباستخدام نموذج الممثل لعملياتك.
نلقي نظرة على بلدي ربط ConcurrentLinkedHashMap للحصول على مثال لكيفية كتابة بنية بيانات خالية من القفل.لا يعتمد على أي أوراق أكاديمية ولا يتطلب سنوات من البحث كما يشير البعض الآخر.يتطلب الأمر ببساطة هندسة دقيقة.
يستخدم التنفيذ الخاص بي ConcurrentHashMap، وهو عبارة عن خوارزمية قفل لكل مجموعة، ولكنه لا يعتمد على تفاصيل التنفيذ تلك.يمكن استبداله بسهولة بتطبيق Cliff Click الخالي من القفل.لقد استعرت فكرة من كليف، لكنني استخدمتها بشكل أكثر وضوحًا، وهي نمذجة جميع عمليات CAS باستخدام آلة الحالة.يؤدي هذا إلى تبسيط النموذج إلى حد كبير، حيث سترى أن لدي أقفال زائفة عبر حالات ing.الحيلة الأخرى هي السماح بالكسل والتصميم حسب الحاجة.ستشاهد هذا غالبًا مع التراجع أو السماح لسلاسل الرسائل الأخرى "بالمساعدة" في التنظيف.في حالتي، قررت السماح بإخلاء العقد الميتة في القائمة عندما تصل إلى الرأس، بدلاً من التعامل مع تعقيد إزالتها من منتصف القائمة.قد أغير ذلك، لكنني لم أثق تمامًا في خوارزمية التراجع الخاصة بي وأردت تأجيل تغيير كبير مثل اعتماد نهج القفل ثلاثي العقد.
يعد كتاب "فن برمجة المعالجات المتعددة" كتابًا تمهيديًا رائعًا.بشكل عام، على الرغم من ذلك، أوصي بتجنب التصميمات الخالية من القفل في كود التطبيق.في كثير من الأحيان يكون الأمر مجرد مبالغة حيث تكون التقنيات الأخرى الأقل عرضة للخطأ أكثر ملاءمة.
إذا رأيت تنافسًا على القفل، فسأحاول أولاً استخدام المزيد من الأقفال الدقيقة على هياكل البيانات الخاصة بك بدلاً من خوارزميات خالية تمامًا من القفل.
على سبيل المثال، أعمل حاليًا على تطبيق متعدد الخيوط، يحتوي على نظام مراسلة مخصص (قائمة قوائم الانتظار لكل سلسلة رسائل، تحتوي قائمة الانتظار على رسائل لسلسلة الرسائل المراد معالجتها) لتمرير المعلومات بين سلاسل الرسائل.يوجد قفل عالمي على هذا الهيكل.في حالتي، لا أحتاج إلى السرعة كثيرًا، لذلك لا يهم حقًا.ولكن إذا أصبح هذا القفل مشكلة، فيمكن استبداله بأقفال فردية في كل قائمة انتظار، على سبيل المثال.ثم لن تؤثر إضافة/إزالة العنصر من/إلى قائمة الانتظار المحددة على قوائم الانتظار الأخرى.سيظل هناك قفل عالمي لإضافة قائمة انتظار جديدة وما شابه، ولكن لن يكون هناك الكثير من الجدل بشأنه.
حتى قائمة انتظار واحدة متعددة المنتجات/المستهلك يمكن كتابتها بقفل محبب لكل عنصر، بدلاً من وجود قفل عام.قد يؤدي هذا أيضًا إلى القضاء على الخلاف.
إذا قرأت العديد من التطبيقات والأوراق المتعلقة بالموضوع، ستلاحظ أن هناك الموضوع المشترك التالي:
1) كائنات الحالة المشتركة هي نمط lisp/clojure غير قابل للتغيير:أي أنه يتم تنفيذ جميع عمليات الكتابة من خلال نسخ الحالة الموجودة في كائن جديد وإجراء تعديلات على الكائن الجديد ثم محاولة تحديث الحالة المشتركة (يتم الحصول عليها من مؤشر محاذي يمكن تحديثه باستخدام CAS البدائي).بمعنى آخر، لا يمكنك مطلقًا تعديل كائن موجود قد تتم قراءته بواسطة أكثر من مؤشر الترابط الحالي.يمكن تحسين قابلية التغيير باستخدام دلالات النسخ عند الكتابة للكائنات الكبيرة والمعقدة، ولكن هذه شجرة أخرى من المكسرات
2) تحدد بوضوح التحولات المسموح بها بين الحالة الحالية والحالة التالية الصالحة:ومن ثم يصبح التحقق من صحة الخوارزمية أمرًا أسهل
3) التعامل مع المراجع المهملة في قوائم مؤشرات المخاطر لكل موضوع.بعد أن تصبح الكائنات المرجعية آمنة، أعد استخدامها إن أمكن
اطلع على منشور آخر ذي صلة خاص بي حيث يتم إعادة تنفيذ بعض التعليمات البرمجية التي تم تنفيذها باستخدام الإشارات وكائنات المزامنة (جزئيًا) بأسلوب خالٍ من القفل:الاستبعاد المتبادل والإشارات
