مؤشرات المخاطر ومشكلة ABA

في التعليمات البرمجية الخالية من الأقفال التي تستخدم المؤشرات، قد تكون القيمة A، ثم تتغير إلى B، ثم تعود إلى A. ولا يستطيع CAS الذي يقارن القيمة فقط معرفة أن شيئًا ما تغيّر في أثناء ذلك.

يقرأ الخيط 1 المؤشر A ويستعد لتنفيذ CAS. وفي هذه الأثناء، يحذف الخيط 2 العنوان A، ثم يخصص عقدة جديدة تصادف أن تعيد استخدام العنوان A، فينجح CAS الذي ينفذه الخيط 1، ولكن على نحو غير صحيح.

أحد الحلول هو تخزين عدّاد إلى جانب المؤشر. تتغير القيمة المدمجة عند كل عملية، ولذلك يمكن اكتشاف ABA.

تتطلب الوسوم عمليات ذرية بعرض مزدوج، مثل CMPXCHG16B على x86. وهي تستهلك مساحة أكبر، وقد لا تتوفر على كل منصة.

المشكلة الأساسية هي: كيف يمكن حذف عقدة قد تظل خيوط أخرى تصل إليها؟ لا يمكن للتعليمات البرمجية الخالية من الأقفال استخدام delete البسيط.

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

لكل عملية وصول:

1. اقرأ المؤشر ذريًا
2. انشره بوصفه مؤشر خطر
3. أعد قراءته للتأكد من أنه لم يتغير، وتجنبًا لحدوث تعارض
4. استخدمه
5. امسح مؤشر الخطر

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

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

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

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

هياكل البيانات الخالية من الأقفال مليئة بالمخاطر. استخدم تنفيذات موثوقة من Folly أو Boost أو Crossbeam (Rust). ولا تكتب تنفيذك الخاص إلا لأغراض تعليمية أو لمسارات محددة حساسة للأداء، وبعد إجراء قياسات دقيقة.

يكتشف ThreadSanitizer تعارضات البيانات، لكنه لا يكتشف جميع مشكلات صحة التنفيذ الخالي من الأقفال. وتستكشف أدوات التحقق الشكلي، مثل CDSChecker وRelacy، التداخلات بين الخيوط بطريقة منهجية.

إلى ماذا تشير مشكلة ABA في البرمجة الخالية من الأقفال؟

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