قابلية الخطية

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

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

1. يمكن إعادة التعبير عن القائمة الممتدة كتاريخ متسلسل (قابل للتسلسل ).
2. إن هذا التاريخ المتسلسل هو جزء من القائمة الأصلية غير الممتدة.

بشكل غير رسمي، يعني هذا أن قائمة الأحداث غير المعدلة يمكن تحويلها إلى خطية إذا وفقط إذا كانت استدعاؤها قابلة للتسلسل، ولكن بعض استجابات الجدول التسلسلي لم تعود بعد. ^[1]

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

تم تقديم الخطية لأول مرة كنموذج تناسق بواسطة Herlihy و Wing في عام 1987. وقد شملت تعريفات أكثر تقييدًا للذرة، مثل "العملية الذرية هي العملية التي لا يمكن مقاطعتها (أو لا يمكن مقاطعتها) بواسطة العمليات المتزامنة"، والتي عادة ما تكون غامضة حول متى تعتبر العملية بداية ونهاية.

يمكن فهم الكائن الذري على الفور وبشكل كامل من خلال تعريفه المتسلسل، باعتباره مجموعة من العمليات التي يتم تنفيذها بالتوازي والتي تبدو دائمًا وكأنها تحدث واحدة تلو الأخرى؛ ولا يجوز ظهور أي تناقضات. على وجه التحديد، تضمن الخطية أن يتم ملاحظة الثوابت في النظام والحفاظ عليها من خلال جميع العمليات: إذا حافظت جميع العمليات بشكل فردي على ثابت، فإن النظام ككل سوف يحافظ على الثوابت.

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

التاريخ هو سلسلة من الاستدعاءات والاستجابات التي يتم إجراؤها لكائن ما بواسطة مجموعة من الخيوط أو العمليات. يمكن اعتبار الاستدعاء بمثابة بداية لعملية، والاستجابة بمثابة نهاية مُشار إليها لهذه العملية. سيكون لكل استدعاء لوظيفة استجابة لاحقة. يمكن استخدام هذا لنمذجة أي استخدام لكائن ما. افترض، على سبيل المثال، أن خيطين، A وB، يحاولان الاستيلاء على قفل، ويتراجعان إذا تم الاستيلاء عليه بالفعل. سيتم نمذجة هذا على أنه يستدعي كلا الخيطين عملية القفل، ثم يتلقى كلا الخيطين استجابة، أحدهما ناجح والآخر غير ناجح.

أ يستدعي القفل

ب يستدعي القفل

أ يحصل على استجابة "فشل"

ب يحصل على استجابة "ناجحة"

التاريخ المتسلسل هو التاريخ الذي تكون فيه جميع الاستدعاءات لها استجابات فورية؛ أي أن الاستدعاء والاستجابة يعتبران أنهما يحدثان في لحظة. يجب أن يكون من السهل التفكير في التاريخ المتسلسل، لأنه لا يوجد تزامن حقيقي؛ لم يكن المثال السابق متسلسلاً، وبالتالي يصعب التفكير فيه. وهنا يأتي دور الخطية.

يكون التاريخ قابلاً للخطية إذا كان هناك ترتيب خطي للعمليات المكتملة مثل: ${\displaystyle \sigma }$

1. بالنسبة لكل عملية مكتملة في ، تعيد العملية نفس النتيجة في التنفيذ كما ستعيدها العملية إذا تم إكمال كل عملية واحدة تلو الأخرى بالترتيب .${\displaystyle \sigma }$${\displaystyle \sigma }$
2. إذا اكتملت عملية op ₁ (حصلت على استجابة) قبل أن تبدأ op ₂ (استدعاء)، فإن op ₁ تسبق op ₂ في . ^[1]${\displaystyle \sigma }$

بعبارة أخرى:

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

لاحظ أن النقطتين الأوليين هنا تتوافقان مع قابلية التسلسل : يبدو أن العمليات تحدث بترتيب معين. النقطة الأخيرة هي التي تنفرد بها قابلية الخطية، وبالتالي فهي المساهمة الرئيسية لـ Herlihy و Wing. ^[1]

فكر في طريقتين لإعادة ترتيب مثال القفل أعلاه.

أ يستدعي القفل

أ يحصل على استجابة "فشل"

ب يستدعي القفل

ب يحصل على استجابة "ناجحة"

يؤدي إعادة ترتيب استدعاء B أسفل استجابة A إلى إنشاء تاريخ متسلسل. ومن السهل التفكير في هذا الأمر، حيث تتم جميع العمليات الآن بترتيب واضح. ومع ذلك، فإن هذا لا يتطابق مع التعريف التسلسلي للكائن (لا يتطابق مع دلالات البرنامج): كان ينبغي أن يحصل A على القفل بنجاح، وكان ينبغي لـ B أن يلغيه لاحقًا.

ب يستدعي القفل

ب يحصل على استجابة "ناجحة"

أ يستدعي القفل

أ يحصل على استجابة "فشل"

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

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

فكر في التاريخ التالي، مرة أخرى، لكائنين يتفاعلان مع قفل:

أ يستدعي القفل

تم القفل بنجاح

B يستدعي إلغاء القفل

تم فتح القفل بنجاح

أ يدعو إلى إلغاء القفل

تم فتح القفل بنجاح

هذا التاريخ غير صالح لأن هناك نقطة حيث يحتفظ كل من A وB بالقفل؛ وعلاوة على ذلك، لا يمكن إعادة ترتيبه إلى تاريخ متسلسل صالح دون انتهاك قاعدة الترتيب. وبالتالي، فهو غير قابل للخطية. ومع ذلك، في ظل إمكانية التسلسل، يمكن نقل عملية إلغاء القفل الخاصة بـ B إلى ما قبل قفل A الأصلي، وهو تاريخ صالح (على افتراض أن الكائن يبدأ التاريخ في حالة قفل):

B يستدعي إلغاء القفل

تم فتح القفل بنجاح

أ يستدعي القفل

تم القفل بنجاح

أ يدعو إلى إلغاء القفل

تم فتح القفل بنجاح

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

هذا التعريف للخطية يعادل ما يلي:

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

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

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

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

• القراءة والكتابة الذرية؛
• المبادلة الذرية (تعليمات RDLK في بعض أجهزة الكمبيوتر المركزية من Burroughs ، وتعليمات XCHG x86 )؛
• اختبار وضبط ؛
• جلب وإضافة ؛
• المقارنة والتبديل ؛
• رابط التحميل/التخزين المشروط .

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

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

يوفر معيار C و SUSv3sig_atomic_t قراءات وكتابات ذرية بسيطة؛ ولا يُضمن أن يكون التزايد أو التناقص ذريًا. ^[3] تتوفر عمليات ذرية أكثر تعقيدًا في C11 ، والتي توفر stdatomic.h. تستخدم المترجمات ميزات الأجهزة أو الطرق الأكثر تعقيدًا لتنفيذ العمليات؛ ومن الأمثلة على ذلك libatomic من GCC.

توفر مجموعة تعليمات ARMLDREX تعليمات STREXيمكن استخدامها لتنفيذ الوصول الذري إلى الذاكرة باستخدام شاشات حصرية تم تنفيذها في المعالج لتتبع عمليات الوصول إلى الذاكرة لعنوان معين. ^[4] ومع ذلك، إذا حدث تبديل سياق بين المكالمات إلى LDREXو STREX، فإن ملاحظات الوثائق تشير إلى أن STREXذلك سيفشل، مما يشير إلى أنه يجب إعادة محاولة العملية. في حالة بنية ARMv8-A ذات 64 بت، فإنها توفر LDXRتعليمات STXRلحجم البايت ونصف الكلمة والكلمة والكلمة المزدوجة. ^[5]

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

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

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

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

• تكتب عملية المقارنة والتبديل قيمة جديدة في موقع ما فقط إذا كانت محتويات الموقع الأخير تتطابق مع القيمة القديمة المقدمة. تُستخدم هذه العملية عادةً في تسلسل القراءة والتعديل وCAS: يقرأ المستخدم الموقع، ويحسب قيمة جديدة للكتابة، ويكتبها باستخدام CAS (مقارنة وتبديل)؛ إذا تغيرت القيمة في نفس الوقت، فسوف تفشل عملية المقارنة والتبديل ويحاول المستخدم مرة أخرى.
• يقوم Load-link/store-conditional بتشفير هذا النمط بشكل أكثر مباشرة: يقرأ المستخدم الموقع باستخدام load-link، ويحسب قيمة جديدة للكتابة، ويكتبها باستخدام store-conditional؛ إذا تغيرت القيمة في نفس الوقت، فسوف تفشل SC (store-conditional) ويحاول المستخدم مرة أخرى.
• في معاملة قاعدة البيانات ، إذا لم تتمكن المعاملة من إكمالها بسبب عملية متزامنة (على سبيل المثال في حالة جمود )، فسيتم إلغاء المعاملة ويجب على المستخدم المحاولة مرة أخرى.

لإثبات قوة وضرورة الخطية، سننظر في عداد بسيط يمكن لعمليات مختلفة زيادته.

نود تنفيذ كائن عداد يمكن لعمليات متعددة الوصول إليه. تستخدم العديد من الأنظمة الشائعة العدادات لتتبع عدد المرات التي حدث فيها حدث ما.

يمكن الوصول إلى كائن العداد من خلال عمليات متعددة وله عمليتان متاحتان.

1. الزيادة - إضافة 1 إلى القيمة المخزنة في العداد، وإرجاع الإقرار
2. قراءة - إرجاع القيمة الحالية المخزنة في العداد دون تغييرها.

سنحاول تنفيذ كائن العداد هذا باستخدام السجلات المشتركة .

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

التنفيذ الساذج غير الذري:

زيادة:

1. قراءة القيمة في السجل R
2. أضف واحدا إلى القيمة
3. يكتب القيمة الجديدة مرة أخرى في السجل R

يقرأ:

قراءة السجل R

هذا التنفيذ البسيط ليس خطيًا، كما هو موضح بالمثال التالي.

تخيل أن هناك عمليتين يتم تشغيلهما للوصول إلى كائن عداد واحد تم تهيئته ليكون له قيمة 0:

1. تقوم العملية الأولى بقراءة القيمة الموجودة في السجل على أنها 0.
2. تضيف العملية الأولى واحدًا إلى القيمة، ويجب أن تكون قيمة العداد 1، ولكن قبل أن تنتهي من كتابة القيمة الجديدة مرة أخرى إلى السجل، قد تصبح معلقة، وفي الوقت نفسه يتم تشغيل العملية الثانية:
3. تقوم العملية الثانية بقراءة القيمة الموجودة في السجل، والتي لا تزال تساوي 0؛
4. العملية الثانية تضيف واحدا إلى القيمة؛
5. العملية الثانية تكتب القيمة الجديدة في السجل، والآن أصبح السجل يحمل القيمة 1.

تم الانتهاء من تشغيل العملية الثانية وتستمر العملية الأولى في التشغيل من حيث توقفت:

1. تكتب العملية الأولى القيمة 1 في السجل، دون أن تدرك أن العملية الأخرى قامت بالفعل بتحديث القيمة في السجل إلى 1.

في المثال أعلاه، استدعت عمليتان أمر زيادة، لكن قيمة الكائن زادت فقط من 0 إلى 1، بدلاً من 2 كما كان ينبغي. وقد ضاعت إحدى عمليات الزيادة نتيجة لعدم إمكانية تحويل النظام إلى خطي.

يوضح المثال أعلاه الحاجة إلى التفكير بعناية في تنفيذات هياكل البيانات وكيف يمكن أن يكون للخطية تأثير على صحة النظام.

لتنفيذ كائن عداد خطي أو ذري، سنقوم بتعديل تنفيذنا السابق بحيث تستخدم كل عملية P i سجلها الخاص R i

تتزايد كل عملية وتقرأ وفقًا للخوارزمية التالية:

زيادة:

1. قراءة القيمة في السجل R i .
2. أضف واحداً إلى القيمة.
3. اكتب القيمة الجديدة مرة أخرى في R i

يقرأ:

1. قراءة السجلات R 1، R 2، ... R n .
2. إرجاع مجموع جميع السجلات.

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

هذا مثال تافه. في النظام الحقيقي، يمكن أن تكون العمليات أكثر تعقيدًا والأخطاء التي يتم إدخالها دقيقة للغاية. على سبيل المثال، يمكن تنفيذ قراءة قيمة 64 بت من الذاكرة في الواقع كقراءتين متتاليتين لموقعين في الذاكرة 32 بت . إذا قرأت عملية فقط أول 32 بت، وقبل أن تقرأ البتات الـ 32 الثانية تتغير القيمة في الذاكرة، فلن يكون لها القيمة الأصلية ولا القيمة الجديدة ولكن قيمة مختلطة.

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

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

1. قراءة القيمة الموجودة في موقع الذاكرة؛
2. أضف واحدًا إلى القيمة؛
3. استخدم المقارنة والتبديل لكتابة القيمة المتزايدة مرة أخرى؛
4. أعد المحاولة إذا كانت القيمة المقروءة بواسطة المقارنة والتبديل لا تتطابق مع القيمة التي قرأناها في الأصل.

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

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

1. استخدم fetch-and-increment لقراءة القيمة القديمة وكتابة القيمة المتزايدة مرة أخرى.

إن استخدام الجلب والزيادة أفضل دائمًا (يتطلب مراجع ذاكرة أقل) لبعض الخوارزميات - مثل تلك الموضحة هنا - من المقارنة والتبديل، ^[6] على الرغم من أن هيرليهي أثبت سابقًا أن المقارنة والتبديل أفضل لبعض الخوارزميات الأخرى التي لا يمكن تنفيذها على الإطلاق باستخدام الجلب والزيادة فقط. لذا فإن تصميمات وحدة المعالجة المركزية مع كل من الجلب والزيادة والمقارنة والتبديل (أو التعليمات المكافئة) قد تكون خيارًا أفضل من التصميمات التي تحتوي على أحدهما فقط أو الآخر. ^[6]

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

1. الحصول على قفل، واستبعاد الخيوط الأخرى من تشغيل القسم الحرج (الخطوات 2-4) في نفس الوقت؛
2. قراءة القيمة في موقع الذاكرة؛
3. أضف واحدًا إلى القيمة؛
4. اكتب القيمة المتزايدة مرة أخرى إلى موقع الذاكرة؛
5. أطلق القفل.

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

• المعاملات الذرية
• نموذج الاتساق
• حامض
• قراءة-نسخ-تحديث (RCU)
• قراءة-تعديل-كتابة
• وقت الفحص إلى وقت الاستخدام

• Herlihy, Maurice P.; Wing, Jeannette M. (1987). "Axioms for concurrent objects". Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming language - POPL '87. ص.  13– 26. doi :10.1145/41625.41627. ISBN 978-0-89791-215-0. S2CID  16017451.
• هيرليهي، موريس ب. (1990). منهجية لتنفيذ هياكل البيانات المتزامنة للغاية . المجلد 25. ص  197- 206. CiteSeerX  10.1.1.186.6400 . doi :10.1145/99164.99185. ISBN 978-0-89791-350-8. {{cite book}}: |journal=تم تجاهله ( مساعدة )
• Herlihy, Maurice P.; Wing, Jeannette M. (1990). "Linearizability: A Correctness Condition for Concurrent Objects". ACM Transactions on Programming Languages ​​and Systems . 12 (3): 463– 492. CiteSeerX  10.1.1.142.5315 . doi :10.1145/78969.78972. S2CID  228785.
• Aphyr. "Strong Consistency Models". aphyr.com . Aphyr . تم الاسترجاع في 13 أبريل 2018 .