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

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

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

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

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

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

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

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

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

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

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

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

بعبارة أخرى:

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

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

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

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

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

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

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

• القراءة والكتابة الذرية؛
• التبديل الذري (تعليمات RDLK في بعض أجهزة Burroughs الرئيسية ، وتعليمات XCHG x86 )؛
• اختبار وتعيين ؛
• جلب وإضافة ؛
• قارن وبدّل ؛
• load-link/store-conditional .

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

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

يُتيح معيار لغة 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 إلى هذا المبدأ باسم الذرية ). إذا فشلت العملية (عادةً بسبب عمليات متزامنة)، يجب على المستخدم إعادة المحاولة، وعادةً ما يُنفذ عملية مختلفة. على سبيل المثال:

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

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

• هيرليهي، موريس ب.؛ وينغ، جانيت م. (1987). "مسلمات الكائنات المتزامنة". وقائع الندوة الرابعة عشرة لجمعية ACM SIGACT-SIGPLAN حول مبادئ لغات البرمجة - 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=تجاهله ( مساعدة )
• هيرليهي، موريس ب.؛ وينغ، جانيت م. (1990). "الخطية: شرط صحة للكائنات المتزامنة". معاملات ACM في لغات البرمجة والأنظمة . 12 (3): 463-492 . CiteSeerX 10.1.1.142.5315 . doi : 10.1145/78969.78972 . S2CID 228785 .  
• أفير. "نماذج الاتساق القوي" . aphyr.com . أفير . تم الاطلاع عليه بتاريخ 13 أبريل 2018 .