مجموعة ترايبر

خوارزمية مكدس تريبر هي مكدس قابل للتوسع وخالٍ من الأقفال، يستخدم عملية المقارنة والتبديل الدقيقة للتزامن . ^{[ 1 ]} يُعتقد أن ر. كينت تريبر كان أول من نشرها في مقالته عام 1986 بعنوان " برمجة الأنظمة : التعامل مع التوازي". ^{[ 2 ]}

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

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

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

قد يكون اختبار حالات الفشل مثل ABA صعبًا للغاية، لأن تسلسل الأحداث الإشكالي نادر الحدوث. يُعدّ التحقق من النموذج طريقة ممتازة للكشف عن هذه المشكلات. انظر على سبيل المثال التمرين 7.3.3 في كتاب "نمذجة وتحليل الأنظمة المتصلة". ^{[ 3 ]}

فيما يلي تطبيق لمكدس تريبر في جافا ، استنادًا إلى التطبيق المقدم في كتاب Java Concurrency in Practice . ^{[ 4 ]}

استيراد java.util.concurrent.atomic.* ;استيراد net.jcip.annotations.* ;/** * ConcurrentStack * * مكدس غير حظري باستخدام خوارزمية تريبر * * @author Brian Goetz and Tim Peierls */ @ThreadSafe public class ConcurrentStack < E > { AtomicReference < Node < E >> top = new AtomicReference < Node < E >> ();public void push ( E item ) { Node < E > newHead = new Node < E > ( item ); Node < E > oldHead ;do { oldHead = top.get ( ) ; newHead.next = oldHead ; } while ( ! top.compareAndSet ( oldHead , newHead ) ) ; }​​public E pop () { Node < E > oldHead ; Node < E > newHead ;كرر { oldHead = top.get ( ) ; إذا كان ( oldHead == null ) أرجع null ؛ newHead = oldHead.next ; } بينما ( ! top.compareAndSet ( oldHead , newHead ) ) ;​return oldHead.item ; }​​فئة ثابتة خاصة Node <E> { عنصر عام نهائي E ؛ عنصر عام Node <E> التالي ؛​​​public Node ( E item ) { this . item = item ; } } }