خوارزمية مخبز لامبورت

في هذا المثال، تقوم جميع الخيوط بتنفيذ نفس الدالة "الرئيسية"، Thread . في التطبيقات الحقيقية، غالبًا ما يكون للخيوط المختلفة دوال "رئيسية" مختلفة.

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

// تعريف وقيم أولية للمتغيرات العامةإدخال : مصفوفة [ 1. . NUM_THREADS ] من نوع bool = { false };الرقم : مصفوفة [ 1. . NUM_THREADS ] من الأعداد الصحيحة = { 0 };قفل ( عدد صحيح i ) {إدخال [ i ] = صحيح ؛Number [ i ] = 1 + max ( Number [ 1 ], ..., Number [ NUM_THREADS ]);إدخال [ i ] = خطأ ؛for ( integer j = 1 ; j <= NUM_THREADS ; j ++ ) {// انتظر حتى يتلقى الخيط j رقمه:بينما ( يتم إدخال [ j ]) { /* لا شيء */ }// انتظر حتى تنتهي جميع الخيوط ذات الأرقام الأصغر أو ذات الأرقام نفسها// رقم، ولكن بأولوية أعلى، يكملون عملهم:بينما (( الرقم [ j ] != 0 ) && (( الرقم [ j ], j ) < ( الرقم [ i ], i ))) { /* لا شيء */ }}}فك القفل ( العدد الصحيح i ) {الرقم [ i ] = 0 ؛}Thread ( عدد صحيح i ) {بينما ( صحيح ) {قفل ( i );// القسم الحرج يوضع هنا...فك القفل ( i );// قسم غير حرج...}}

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

قد لا تكون ضرورة المتغير Entering واضحةً لعدم وجود أي "قفل" حول الأسطر من 7 إلى 13. مع ذلك، لنفترض أنه تم حذف المتغير وأن عمليتين قامتا بحساب نفس القيمة Number[i]. إذا تمت مقاطعة العملية ذات الأولوية الأعلى قبل تعيين القيمة Number[i]، فسترى العملية ذات الأولوية المنخفضة أن العملية الأخرى لديها قيمة صفرية، وتدخل القسم الحرج؛ لاحقًا، ستتجاهل العملية ذات الأولوية الأعلى تساوي القيمة Number[i]للعمليات ذات الأولوية المنخفضة، وتدخل هي الأخرى القسم الحرج. نتيجةً لذلك، يمكن لعمليتين دخول القسم الحرج في الوقت نفسه. تستخدم خوارزمية المخبز المتغير Entering لجعل عملية التعيين في السطر 6 تبدو وكأنها عملية ذرية؛ فلن ترى العملية i أبدًا قيمة صفرية للعملية j التي ستختار نفس القيمة التي اختارتها i .

عند تطبيق الشفرة الزائفة في نظام أحادي العملية أو في ظل تعدد المهام التعاوني ، يُفضّل استبدال أقسام "عدم القيام بأي شيء" بشفرة تُعلم نظام التشغيل بالانتقال فورًا إلى الخيط التالي. يُشار إلى هذه العملية غالبًا باسم yield.

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

نعلن أن N هو عدد العمليات، ونفترض أن N هو عدد طبيعي .

ثابت ن افترض أن N ∈ Nat 

نُعرّف P على أنها مجموعة {1، 2، ...، N} من العمليات.

P == 1..N 

تم تعريف المتغيرين num و flag كمتغيرين عامين.

--algorithm AtomicBakery { المتغير num = [i \in P |-> 0]، flag = [i \in P |-> FALSE]؛ 

يُعرّف ما يلي LL(j, i)بأنه صحيح إذا وفقط إذا كان <<num[j], j>> أقل من أو يساوي <<num[i], i>> في الترتيب المعجمي المعتاد .

define { LL(j, i) == \/ num[j] < num[i] num[i] = num[j] j =< i } 

لكل عنصر في المجموعة P، توجد عملية بمتغيرات محلية هي unread وmax وnxt. تُعتبر الخطوات بين التسميات المتتالية p1، ...، p7، cs خطوات ذرية. تقوم العبارة بتعيين المعرّف id إلى عنصر مُختار عشوائيًا من المجموعة S، ثم تُنفّذ نص العملية. لا يُمكن تنفيذ خطوة تحتوي على العبارة await expr إلا إذا كانت قيمة expr هي TRUE .(x \in S) { body }

العملية (p \in P) المتغيرات غير المقروءة في المجموعة الفرعية P، أقصى قيمة في الطبيعة، nxt \in P; { p1: بينما (صحيح) { غير مقروء := P \ {self} ; الحد الأقصى := 0؛ flag[self] := TRUE; p2: بينما (غير مقروء # {}) { مع (i \in unread) { unread := unread \ {i}; إذا كان (num[i] > max) { max := num[i]; } } }; p3: num[self] := max + 1; p4: flag[self] := FALSE; غير مقروء := P \ {self} ; ص5: بينما (عدد غير مقروء {}) { مع (i \in unread) { nxt := i ; }; انتظر ~ flag[nxt]؛ p6: await \/ num[nxt] = 0 \/ LL(self, nxt) ; غير مقروء := غير مقروء \ {التالي}; } ; cs: تخطي ; * القسم الحرج؛ p7: num[self] := 0; }} } 

نستخدم فئة AtomicIntegerArray ليس لعملياتها الذرية المدمجة، بل لأن دوال get و set فيها تعمل كعمليات قراءة وكتابة متغيرة. في نموذج ذاكرة جافا، يضمن هذا أن تكون عمليات الكتابة مرئية فورًا لجميع الخيوط.

AtomicIntegerArray ticket = new AtomicIntegerArray ( threads ); // تذكرة للخيوط في السطر، n - عدد الخيوط// تقوم جافا بتهيئة كل عنصر من عناصر 'ticket' إلى 0AtomicIntegerArray entries = new AtomicIntegerArray ( threads ); // 1 عند دخول الخيط في السطر// تقوم جافا بتهيئة كل عنصر من عناصر 'entering' إلى 0public void lock ( int pid ) // معرف الخيط{enter.set ( pid , 1 ) ;​int max = 0 ;for ( int i = 0 ; i < threads ; i ++ ){int current = ticket.get ( i ) ;​إذا ( الحالي > الحد الأقصى ){الحد الأقصى = الحالي ؛}}ticket.set ( pid , 1 + max ) ;​enter.set ( pid , 0 ) ;​for ( int i = 0 ; i < ticket.length ( ) ; ++ i ){إذا كان ( i != pid ){بينما ( entering.get ( i ) == 1 ) { Thread.yield ( ) ; } // انتظر حتى يختار خيط آخر تذكرةبينما ( التذكرة . الحصول على ( i ) != 0 && ( التذكرة . الحصول على ( i ) < التذكرة . الحصول على ( pid ) ||( ticket . get ( i ) == ticket . get ( pid ) && i < pid ))){ Thread . yield (); }}}// القسم الحرج يوضع هنا...}public void unlock ( int pid ){ticket.set ( pid , 0 ) ;​}