اختبر واضبط

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
الموسوعة الحرة

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

يمكن إنشاء القفل باستخدام تعليمة الاختبار والتعيين الذرية [ 1 ] كما يلي:

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

أثبت موريس هيرليهي (1991) أن خوارزمية الاختبار والضبط (باستخدام مُقارِن أحادي البت) لها عدد توافق محدود، ويمكنها حل مشكلة التوافق بدون انتظار لعمليتين متزامنتين على الأكثر. [ 2 ] في المقابل، تُقدم خوارزمية المقارنة والتبديل (باستخدام مُقارِن 32 بت) حلاً أكثر عمومية لهذه المشكلة، وفي بعض التطبيقات، تتوفر أيضًا خوارزمية مقارنة وتبديل أوسع (باستخدام مُقارِن 64 أو 128 بت) لزيادة فائدتها.

التنفيذ المادي لاختبار وضبط

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

التباين 1

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

سواءً حاول المعالج 2 الوصول إلى موقع الذاكرة أم لا، فإن ذاكرة الوصول العشوائي الديناميكية (DPRAM) تُجري الاختبار المُحدد من قِبل المعالج 1. إذا نجح الاختبار، تُعيّن ذاكرة الوصول العشوائي الديناميكية موقع الذاكرة إلى القيمة المُحددة من قِبل المعالج 1. ثم تمسح ذاكرة الوصول العشوائي الديناميكية "ملاحظتها الداخلية" التي تُشير إلى أن المعالج 1 كان يكتب هناك. عند هذه النقطة، يُمكن للمعالج 2 إصدار أمر اختبار وتعيين، والذي سينجح.

التباين 2

يُصدر المعالج المركزي 1 تعليمة اختبار وتعيين للكتابة إلى "موقع الذاكرة A". لا يقوم ذاكرة الوصول العشوائي الديناميكية (DPRAM) بتخزين القيمة في موقع الذاكرة A مباشرةً، بل ينقل القيمة الحالية إلى سجل خاص، مع تعيين محتويات موقع الذاكرة A إلى "قيمة علامة" خاصة. إذا أصدر المعالج المركزي 2 في هذه المرحلة تعليمة اختبار وتعيين لموقع الذاكرة A، فإن ذاكرة الوصول العشوائي الديناميكية (DPRAM) تكتشف قيمة العلامة الخاصة، وكما في الحالة 1، تُصدر مقاطعة BUSY.

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

تنفيذ برمجي لاختبار وضبط

تتضمن بعض مجموعات التعليمات تعليمات لغة الآلة التي تعتمد على اختبار وتعيين ذري . ومن الأمثلة على ذلك x86 [ 3 ] و IBM System/360 وخلفائها (بما في ذلك z/Architecture ) [ 4 ] . أما تلك التي لا تتضمن هذه التعليمات، فيمكنها مع ذلك تنفيذ اختبار وتعيين ذري باستخدام تعليمات القراءة والتعديل والكتابة أو المقارنة والتبديل .

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

دالة TestAndSet(boolean_ref lock) { boolean initial = lock; lock = true; أعد القيمة الأولية؛ }

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

في لغة البرمجة C ، سيكون التنفيذ على النحو التالي:

#define LOCKED 1int test_and_set ( int * lock_ptr ) { int old_value ;// -- بداية المقطع الذري -- // يجب تفسير هذا على أنه رمز زائف لأغراض التوضيح فقط. // لن يضمن التجميع التقليدي لهذا الكود الذرية، أو استخدام الذاكرة المشتركة (أي القيم غير المخزنة مؤقتًا)، أو الحماية من تحسينات المُجمِّع، أو الخصائص الأخرى المطلوبة. old_value = * lock_ptr ; * lock_ptr = LOCKED ; // -- نهاية المقطع الذري --return old_value ; }

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

الاستبعاد المتبادل باستخدام اختبار المجموعة

إحدى طرق تطبيق الاستبعاد المتبادل هي استخدام قفل قائم على الاختبار والتعيين [ 5 ] [ 6 ] كما يلي:

تنفيذ قفل الدوران بلغة شبه C

volatile int lock = 0 ;void critical () {// قفل الدوران: نكرر العملية إلى ما لا نهاية حتى نحصل على القفل. // نعلم أنه تم الحصول على القفل بنجاح بعد الخروج من // حلقة while هذه لأن الدالة test_and_set() تقفل القفل ولكنها تُرجع قيمة القفل السابقة. // إذا (وفقط إذا) كانت قيمة القفل السابقة 1، فهذا يعني أن القفل كان // **مقفلاً بالفعل** بواسطة مؤشر ترابط أو عملية أخرى، لذلك نبقى في // الحلقة ونعيد المحاولة. // عندما كانت قيمة القفل السابقة 0، فهذا يشير إلى أن // القفل لم يكن **مقفلاً** قبل أن نقفله. إنه **مقفل** الآن // لأننا قمنا بقفله، لذلك نحن نملك القفل ويمكننا الخروج من حلقة الدوران. while ( test_and_set ( & lock ) == 1 );القسم الحرج // لا يمكن أن يكون في هذا القسم إلا عملية واحدة في كل مرة// تحرير القفل عند الانتهاء من القسم الحرج. // كانت قيمته 1 (لأننا قمنا بقفله). // أي عملية أخرى "غيرته" منذ ذلك الحين // لم تكن في القسم الحرج، لذا // قامت العمليات الأخرى أيضًا بتعيينه إلى 1، لكنها // لم تحصل على القفل أو تدخل // القسم الحرج، و(إما استسلمت أو) // لا تزال تنتظر في حلقات التكرار الخاصة بها. lock = 0 ; }

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

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

تنفيذ التجميع

enter_region: ; علامة "انتقال إلى"؛ نقطة دخول الدالة.tsl reg , flag ; اختبار وتعيين القفل؛ flag هو المتغير المشترك؛ يتم نسخه إلى السجل reg و flag ؛ ثم يتم تعيينه بشكل ذري إلى 1.cmp reg , #0 ; هل كانت العلامة صفرًا في منطقة الإدخال؟jnz enter_region ; انتقل إلى enter_region إذا كانت قيمة reg غير صفرية؛ أي أن قيمة flag كانت غير صفرية عند الدخول.ret ؛ خروج؛ أي أن قيمة العلم كانت صفرًا عند الدخول. إذا وصلنا إلى هنا، فإن tsl ؛ ستكون قد عيّنتها إلى قيمة غير صفرية؛ وبالتالي،؛ نكون قد حجزنا المورد ؛ المرتبط بالعلم.leave_region: move flag , #0 ; store 0 in flag ret ; return to the caller

هذه tslتعليمة ذرية، و flagهو متغير القفل. لا تعود العملية إلا بعد الحصول على القفل.

تقييم أداء الأقفال التي تعمل بنظام الاختبار والضبط

تتمثل معايير التقييم الرئيسية الأربعة للأقفال بشكل عام في زمن استجابة الحصول على القفل غير المتنازع عليه، وحركة مرور ناقل البيانات، والإنصاف، والتخزين. [ 7 ]

حصلت الاختبارات والمجموعات على درجات منخفضة في اثنين منها، وهما: ازدحام الحافلات الشديد وعدم الإنصاف.

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

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

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

انظر أيضاً

مراجع

  1. ↑ أندرسون، تي إي (1990-01-01). "أداء بدائل قفل الدوران للمعالجات المتعددة ذات المال المشترك". معاملات IEEE في الأنظمة المتوازية والموزعة . 1 (1): 6-16 . doi : 10.1109/71.80120 . ISSN 1045-9219 . 
  2. ↑ هيرليهي، موريس (يناير 1991). "المزامنة بدون انتظار" (ملف PDF) . مجلة ACM للمعاملات في لغات البرمجة والأنظمة ، 13 (1): 124-149 . CiteSeerX 10.1.1.56.5659 . doi : 10.1145/114005.102808 . S2CID 2181446. تاريخ الاسترجاع: 20 مايو 2007 .  
  3. ↑ "BTS—اختبار وضبط البتات" . www.felixcloutier.com . تم الاطلاع عليه بتاريخ 21-11-2016 .
  4. ↑ "مركز معارف IBM" . www.ibm.com . تاريخ الاسترجاع: 21-11-2016 .
  5. ↑ رمزي ح. أرباتشي-دوسو وأندريا س. أرباتشي-دوسو (2015). أنظمة التشغيل: ثلاثة أجزاء سهلة ( الطبعة 0.91). كتب أرباتشي-دوسو. 
  6. ↑ سوليهين، يان (2009). أساسيات بنية الحاسوب المتوازي: أنظمة متعددة الرقاقات ومتعددة النوى . ص 252. ISBN  9780984163007.
  7. ^ سوليهين، يان (2016). أساسيات العمارة الموازية . بوكا راتون، فلوريدا: مطبعة اتفاقية حقوق الطفل. رقم ISBN 978-1-4822-1118-4.