مراقبة (مزامنة)

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

يُعرَّف المُراقِب أيضًا بأنه كائن أو فئة أو وحدة نمطية آمنة للاستخدام في بيئات متعددة الخيوط ، تحتوي على مُؤمِّن مُتبادل (mutex) وتستخدمه للسماح بالوصول الآمن إلى أساليبها أو متغيراتها من قِبَل أكثر من خيط واحد . السمة المُميِّزة للمُراقِب هي أن أساليبه تُنفَّذ باستبعاد مُتبادل : في أي لحظة زمنية، لا يُمكن لأكثر من خيط واحد تنفيذ أيٍّ من أساليب المُراقِب . باستخدام مُتغير شرط واحد أو أكثر، يُمكنه أيضًا توفير إمكانية انتظار الخيوط لشرط مُعين (وبذلك باستخدام التعريف الأول لـ "المُراقِب"). في بقية هذه المقالة، سيُشار إلى هذا المعنى لـ "المُراقِب" باسم "كائن/فئة/وحدة نمطية آمنة للاستخدام في بيئات متعددة الخيوط".

تم اختراع الشاشات بواسطة بير برينش هانسن ^{[ 1 ]} وكار هوار [ ²^] وتم تنفيذها لأول مرة في ^لغة برينش هانسن المتزامنة باسكال . ^[³^]

الاستبعاد المتبادل

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

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

متغيرات الحالة

بيان المشكلة

في العديد من التطبيقات، لا يكفي الاستبعاد المتبادل. قد تحتاج الخيوط التي تحاول تنفيذ عملية ما إلى الانتظار حتى يتحقق شرط معين (P) . حلقة انتظار نشطة

بينما ليس ( P ) قم بالتخطي

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

دراسة حالة: مشكلة المنتج/المستهلك الكلاسيكية المحدودة

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

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

غير صحيح بدون مزامنة

يتمثل النهج الساذج في تصميم الكود باستخدام الانتظار النشط وعدم وجود تزامن، مما يجعل الكود عرضة لحالات التنافس:

قائمة انتظار حلقية عامة ؛ // مخزن مؤقت حلقي غير آمن للخيوط للمهام.// دالة تمثل سلوك كل خيط إنتاج: public method producer () { while ( true ) { task myTask = ...; // يقوم المُنتِج بإنشاء مهمة جديدة لإضافتها. while ( queue . isFull ()) {} // انتظار نشط حتى يصبح الطابور غير ممتلئ. queue . enqueue ( myTask ); // إضافة المهمة إلى الطابور. } }// دالة تمثل سلوك كل خيط مستهلك: public method consumer ( ) { while ( true ) { while ( queue.isEmpty ( )) {} // انتظار نشط حتى يصبح الطابور غير فارغ. myTask = queue.dequeue (); // سحب مهمة من الطابور. doStuff ( myTask ) ; // تنفيذ إجراء ما على المهمة. } }

يُعاني هذا الكود من مشكلة خطيرة تتمثل في إمكانية مقاطعة عمليات الوصول إلى قائمة الانتظار وتداخلها مع عمليات وصول الخيوط الأخرى إليها. من المرجح أن تحتوي الدالتان `queue.enqueue` و` queue.dequeue` على تعليمات لتحديث متغيرات قائمة الانتظار، مثل حجمها وموقعي بدايتها ونهايتها، بالإضافة إلى تعيين عناصرها وتخصيصها، وما إلى ذلك. علاوة على ذلك، تقرأ الدالتان ` queue.isEmpty()` و` queue.isFull()` هذه الحالة المشتركة أيضًا. إذا سُمح بتداخل خيوط المُنتِج/المُستهلِك أثناء استدعاء الدالتين `enqueue` و`dequeue`، فقد يؤدي ذلك إلى حالة غير متناسقة لقائمة الانتظار، مما يُسبب حالات تضارب. إضافةً إلى ذلك، إذا قام أحد المُستهلِكين بإفراغ قائمة الانتظار بين خروج مُستهلِك آخر من حالة الانتظار النشط واستدعائه للدالة `dequeue`، فسيحاول المُستهلِك الثاني إزالة عنصر من قائمة انتظار فارغة، مما يؤدي إلى حدوث خطأ. وبالمثل، إذا قام منتج بملء قائمة الانتظار بين خروج منتج آخر من حالة الانتظار المشغول واستدعاء "enqueue"، فسيحاول المنتج الثاني الإضافة إلى قائمة انتظار ممتلئة مما يؤدي إلى حدوث خطأ.

انتظار الدوران

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

global RingBuffer queue ; // مخزن مؤقت حلقي غير آمن للاستخدام في بيئة متعددة الخيوط. global Lock queueLock ; // قفل تبادلي لمخزن المهام الحلقي.// طريقة تمثل سلوك كل سلسلة إنتاج: public method producer () { while ( true ) { task myTask = ...; // يقوم المنتج بإنشاء مهمة جديدة لإضافتها.queueLock.acquire ( ); // الحصول على القفل لإجراء فحص الانتظار النشط الأولي. while ( queue.isFull ( )) { // الانتظار النشط حتى يصبح الطابور غير ممتلئ. queueLock.release ( ); // تحرير القفل مؤقتًا لإتاحة الفرصة للخيوط الأخرى // التي تحتاج إلى تشغيل queueLock حتى يتمكن المستهلك من أخذ مهمة. queueLock.acquire ( ) ; // إعادة الحصول على القفل للاستدعاء التالي لـ "queue.isFull()". }queue.enqueue ( myTask ) ; // إضافة المهمة إلى قائمة الانتظار. queueLock.release ( ); // تحرير قفل قائمة الانتظار حتى نحتاجه مرة أخرى لإضافة المهمة التالية. } }// دالة تمثل سلوك كل خيط مستهلك: public method consumer ( ) { while ( true ) { queueLock.acquire (); // الحصول على القفل لإجراء فحص الانتظار النشط الأولي. while ( queue.isEmpty ( )) { // الانتظار النشط حتى تصبح قائمة الانتظار غير فارغة. queueLock.release (); // تحرير القفل مؤقتًا لإتاحة الفرصة للخيوط الأخرى // التي تحتاج إلى queueLock للتشغيل حتى يتمكن المنتج من إضافة مهمة. queueLock.acquire ( ) ; // إعادة الحصول على القفل للاستدعاء التالي لـ "queue.isEmpty()". } myTask = queue.dequeue ( ); // إزالة مهمة من قائمة الانتظار. queueLock.release (); // تحرير قفل قائمة الانتظار حتى نحتاجه مرة أخرى لإزالة المهمة التالية. doStuff ( myTask ) ; // تنفيذ مهمة ما على المهمة. } }

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

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

متغيرات الحالة

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

وبالتالي، هناك ثلاث عمليات رئيسية على متغيرات الشرط:

wait c, mحيث cيمثل متغير شرط، و mيمثل قفلًا (mutex) مرتبطًا بالشاشة. يتم استدعاء هذه العملية بواسطة خيط يحتاج إلى الانتظار حتى يصبح التأكيد P _c صحيحًا قبل المتابعة. أثناء انتظار الخيط، فإنه لا يشغل الشاشة. تتمثل وظيفة عملية "الانتظار"، وعقدها الأساسي، في تنفيذ الخطوات التالية:
1. على المستوى الذري :
  قم بتحرير القفل المتبادل m،
  انقل هذا الخيط من قائمة "التشغيل" إلى cقائمة "الانتظار" (أو "قائمة السكون") الخاصة بالخيوط، و
  قم بإيقاف هذا الخيط مؤقتًا. (يتم تسليم السياق بشكل متزامن إلى خيط آخر.)
2. بمجرد إخطار/إشارة هذا الخيط لاحقًا (انظر أدناه) واستئنافه، فإنه يعيد الحصول على mutex تلقائيًا m.
يمكن تنفيذ الخطوتين 1أ و1ب بأي ترتيب، وعادةً ما تحدث الخطوة 1ج بعدهما. أثناء سكون الخيط ووجوده في قائمة انتظار البرنامج، يكون عداد البرنامجc التالي المراد تنفيذه في الخطوة 2، في منتصف دالة/ روتين "الانتظار" . وبالتالي، يسكن الخيط ثم يستيقظ لاحقًا في منتصف عملية "الانتظار".
يُعدّ تنفيذ العمليات في الخطوة 1 بشكل ذري أمرًا بالغ الأهمية لتجنب حالات التزامن التي قد تنجم عن تبديل خيط معالجة استباقي بينها. أحد أنماط الفشل المحتملة في حال عدم تنفيذ هذه العمليات بشكل ذري هو عدم إيقاظ الخيط ، حيث قد يكون الخيط في cقائمة انتظار السكون الخاصة بالخيط الآخر وقد حرر القفل، ولكن حدث تبديل خيط معالجة استباقي قبل دخول الخيط في حالة السكون، وقام خيط آخر باستدعاء عملية إشارة (انظر أدناه) cلإعادة الخيط الأول من cقائمة انتظار الخيط الآخر. بمجرد عودة الخيط الأول المعني إلى الخيط الآخر، سيعود عداد برنامجه إلى الخطوة 1ج، وسيدخل في حالة السكون ولن يتمكن من الإيقاظ مرة أخرى، مما يُخالف الشرط الأساسي المتمثل في وجوده في قائمة انتظار cالسكون الخاصة بالخيط الآخر عند دخوله في حالة السكون. تعتمد حالات التزامن الأخرى على ترتيب الخطوتين 1أ و1ب، وعلى مكان حدوث تبديل السياق .
signal cتُستدعى الدالة `signal`، المعروفة أيضًا باسم `signal` notify c، بواسطة أحد الخيوط للإشارة إلى صحة العبارة $`P c`$ . وبحسب نوع وتنفيذ نظام المراقبة، تنقل هذه الدالة خيطًا واحدًا أو أكثر من cقائمة انتظار السكون الخاصة بالخيط `signal` إلى قائمة الانتظار الجاهزة، أو إلى قائمة انتظار أخرى لتنفيذها. يُعتبر من أفضل الممارسات عادةً تنفيذ عملية الإشارة قبل تحرير القفل mالمرتبط بالخيط `signal` c، ولكن طالما أن الكود مصمم بشكل صحيح للتزامن، وبحسب تنفيذ نظام الخيوط، فإنه غالبًا ما يكون من المقبول أيضًا تحرير القفل قبل الإشارة. وبحسب تنفيذ نظام الخيوط، قد يؤثر ترتيب هذه العملية على أولوية الجدولة. ( يُفضل بعض المؤلفين تحرير القفل قبل الإشارة). يجب على نظام الخيوط توثيق أي قيود خاصة على هذا الترتيب.
broadcast cتُعرف أيضًا باسم notifyAll c، وهي عملية مشابهة تُوقظ جميع الخيوط في قائمة انتظار لغة C، مما يُفرغ قائمة الانتظار. عمومًا، عندما يرتبط أكثر من شرط شرطي بنفس متغير الشرط، سيحتاج التطبيق إلى البث بدلًا من الإشارة، لأن الخيط الذي ينتظر الشرط الخاطئ قد يُوقظ ثم يعود فورًا إلى وضع السكون دون إيقاظ الخيط الذي ينتظر الشرط الصحيح الذي أصبح صحيحًا للتو. أما إذا كان الشرط الشرطي مرتبطًا بمتغير الشرط ارتباطًا مباشرًا، فقد تكون الإشارة أكثر كفاءة من البث .

كقاعدة تصميمية، يمكن ربط متغيرات شرطية متعددة بنفس القفل المتبادل، ولكن ليس العكس. (هذه علاقة واحد إلى متعدد ). والسبب هو أن الشرط $P c$ هو نفسه لجميع الخيوط التي تستخدم المراقب، ويجب حمايته بالاستبعاد المتبادل من جميع الخيوط الأخرى التي قد تتسبب في تغيير الشرط أو التي قد تقرأه أثناء قيام الخيط المعني بتغييره، ولكن قد تكون هناك خيوط مختلفة ترغب في انتظار شرط مختلف على نفس المتغير، مما يتطلب استخدام نفس القفل المتبادل. في مثال المنتج والمستهلك الموضح أعلاه ، يجب حماية قائمة الانتظار بواسطة كائن قفل متبادل فريد m. سترغب خيوط "المنتج" في الانتظار على مراقب باستخدام قفل mومتغير شرطي. $c_{full}$ والذي يحجب العملية حتى يصبح الطابور غير ممتلئ. سترغب خيوط "المستهلك" في الانتظار على شاشة عرض مختلفة باستخدام نفس القفل المتبادل mولكن بمتغير شرط مختلف. $c_{empty}$ يُوقف هذا الإجراء التنفيذ حتى يصبح الطابور غير فارغ. عادةً، لا يُنصح باستخدام عدة مؤشرات تزامن (mutexes) لنفس متغير الشرط، لكن هذا المثال الكلاسيكي يُوضح لماذا يكون من المنطقي في كثير من الأحيان استخدام عدة متغيرات شرطية تستخدم نفس مؤشر التزامن. يمكن أيضًا مشاركة مؤشر التزامن المستخدم من قِبل متغير شرطي واحد أو أكثر (مراقب واحد أو أكثر) مع التعليمات البرمجية التي لا تستخدم متغيرات الشرط (والتي ببساطة تحصل عليه/تُحرره دون أي عمليات انتظار/إشارة)، إذا لم تتطلب تلك الأجزاء الحرجة انتظار شرط معين على البيانات المتزامنة.

مراقبة الاستخدام

الاستخدام الأساسي الصحيح للشاشة هو:

acquire ( m ); // الحصول على قفل هذا المُراقِب. while ( ! p ) { // طالما أن الشرط/المسند/التأكيد الذي ننتظره غير صحيح... wait ( m , cv ); // انتظار قفل هذا المُراقِب ومتغير الشرط. } // ... الجزء الحرج من الكود هنا ... signal ( cv2 ); // أو: broadcast(cv2); // قد يكون cv2 هو نفسه cv أو مختلفًا. release ( m ); // تحرير قفل هذا المُراقِب.

فيما يلي نفس الشفرة الزائفة ولكن مع تعليقات أكثر تفصيلاً لشرح ما يحدث بشكل أفضل:

// ... (الكود السابق) // على وشك الدخول إلى وضع المراقبة. // الحصول على قفل التزامن الاستشاري المرتبط بالبيانات المتزامنة // المشتركة بين الخيوط، // لضمان عدم إمكانية تداخل خيطين بشكل استباقي أو // تشغيلهما في وقت واحد على أنوية مختلفة أثناء التنفيذ في أقسام حرجة // تقرأ أو تكتب نفس البيانات المتزامنة. إذا كان خيط آخر // يحتفظ بهذا القفل، فسيتم وضع هذا الخيط في وضع السكون // (حظره) ووضعه في قائمة انتظار السكون الخاصة بـ m. (يجب ألا يكون القفل "m" // قفلًا دورانيًا.) acquire ( m ); // الآن، نحن نحتفظ بالقفل ويمكننا التحقق من الشرط لأول مرة.// في المرة الأولى التي ننفذ فيها شرط حلقة while بعد ما سبق // "acquire"، فإننا نسأل، "هل الشرط/المسند/التأكيد // الذي ننتظره صحيح بالفعل؟"while ( ! p ()) // "p" هو أي تعبير (مثل متغير أو // استدعاء دالة) يتحقق من الشرط ويُقيّم إلى قيمة منطقية. هذا بحد ذاته قسم حرج ، لذا *يجب* عليك الاحتفاظ بالقفل عند // تنفيذ شرط حلقة "while" هذا! // إذا لم تكن هذه هي المرة الأولى التي يتم فيها التحقق من شرط "while"، // فإننا نطرح السؤال التالي: "الآن بعد أن قام مؤشر ترابط آخر يستخدم هذا // المراقب بإخطاري وإيقاظي، وتم تبديل السياق // إليّ مرة أخرى، هل ظل الشرط/المسند/التأكيد الذي ننتظره صحيحًا // بين وقت إيقاظي ووقت استعادة // القفل داخل استدعاء "wait" في التكرار الأخير لهذه الحلقة، أم // تسبب مؤشر ترابط آخر في أن يصبح الشرط خاطئًا مرة أخرى في هذه الأثناء، مما يجعل هذا إيقاظًا زائفًا؟{ // إذا كانت هذه هي الدورة الأولى للحلقة، فالإجابة هي // "لا" - الشرط غير جاهز بعد. وإلا، فالإجابة هي: // الخيار الثاني. كان هذا تنبيهًا زائفًا، فقد حدث خيط آخر // أولًا وتسبب في أن يصبح الشرط خاطئًا مرة أخرى، ويجب علينا // الانتظار مرة أخرى.انتظر ( m ، cv )؛ // منع أي خيط آخر على أي نواة مؤقتًا من إجراء عمليات على m أو cv. // تحرير (m) // تحرير القفل "m" بشكل ذري حتى يتمكن الكود الآخر الذي يستخدم هذه البيانات المتزامنة من العمل، // // ونقل هذا الخيط إلى قائمة انتظار cv بحيث يتم إخطاره // // عندما يصبح الشرط صحيحًا، // // وإيقاف هذا الخيط مؤقتًا. إعادة تمكين الخيوط والنوى الأخرى لإجراء عمليات على m و cv. // // يحدث تبديل السياق على هذه النواة. // // في وقت لاحق، يصبح الشرط الذي ننتظره صحيحًا، // ويقوم خيط آخر يستخدم هذا المراقب (m، cv) إما بإرسال إشارة لإيقاظ هذا الخيط، أو بثًا لإيقاظنا، مما يعني أنه تم إخراجنا من قائمة انتظار cv. // // خلال هذا الوقت، قد تتسبب خيوط أخرى في أن يصبح الشرط خاطئًا مرة أخرى، // أو قد يتغير الشرط مرة واحدة أو أكثر، // أو قد يبقى صحيحًا. // // يتم التبديل إلى هذا الخيط مرة أخرى على بعض النوى. // // acquire(m) // يتم إعادة الحصول على القفل "m". // إنهاء تكرار هذه الحلقة وإعادة التحقق من شرط حلقة "while" للتأكد من // أن الشرط لا يزال صحيحًا. }// الشرط الذي ننتظره صحيح! // ما زلنا نحتفظ بالقفل، إما من قبل الدخول إلى الشاشة أو من // آخر تنفيذ لـ "انتظار".// يُوضع هنا الجزء الحرج من الكود، والذي يتضمن شرطًا مسبقًا بأن يكون المسند الخاص بنا صحيحًا. // قد يجعل هذا الكود شرط المتغير cv خاطئًا، و/أو يجعل مسندات متغيرات الشرط الأخرى صحيحة.// استدعاء الإشارة أو البث، اعتمادًا على متغيرات الشرط // التي تم جعلها صحيحة أو ربما تم جعلها صحيحة، // ونوع الدلالات المستخدمة للمراقبة.for ( cv_x in cvs_to_signal ) { signal ( cv_x ); // Or: broadcast(cv_x); } // تم تنبيه خيط واحد أو أكثر، ولكن سيتم حظره بمجرد محاولته // الحصول على m.// تحرير القفل المتبادل حتى تتمكن الخيوط المُخطرة وغيرها من الدخول إلى أقسامها الحرجة. release ( m );

حل مشكلة المنتج/المستهلك المحدود

بعد أن تعرفنا على استخدام متغيرات الحالة، دعونا نستخدمها لإعادة النظر في مسألة المنتج/المستهلك المحدودة الكلاسيكية وحلها. يتمثل الحل الكلاسيكي في استخدام مراقبين، يتألف كل منهما من متغيري حالة يشتركان في قفل واحد على قائمة الانتظار.

global volatile RingBuffer queue ; // مخزن مؤقت حلقي غير آمن للاستخدام المتزامن. global Lock queueLock ; // قفل تبادلي لمخزن المهام الحلقي. (ليس قفل دوراني). global CV queueEmptyCV ; // متغير حالة لخيوط المستهلك التي تنتظر // أن يصبح الطابور غير فارغ. القفل المرتبط به هو "queueLock". global CV queueFullCV ; // متغير حالة لخيوط المنتج التي تنتظر // أن يصبح الطابور غير ممتلئ. القفل المرتبط به هو أيضًا "queueLock".// دالة تمثل سلوك كل خيط إنتاج: public method producer () { while ( true ) { // يقوم المنتج بإنشاء مهمة جديدة لإضافتها. task myTask = ...;// الحصول على " queueLock " لإجراء فحص الشرط الأولي. queueLock.acquire ();// قسم حرج يتحقق مما إذا كانت قائمة الانتظار غير ممتلئة. while ( queue.isFull ( )) { // تحرير "queueLock"، وإضافة هذا الخيط إلى "queueFullCV" ، وإيقاف هذا الخيط مؤقتًا. wait ( queueLock , queueFullCV ); // عند إيقاظ هذا الخيط، يتم استعادة "queueLock" لإجراء فحص الشرط التالي. }// القسم الحرج الذي يضيف المهمة إلى قائمة الانتظار (لاحظ أننا نحتفظ بـ "queueLock") . queue.enqueue ( myTask ) ;// تنبيه واحد أو جميع خيوط المستهلك التي تنتظر أن تكون قائمة الانتظار غير فارغة // الآن وقد أصبح ذلك مضمونًا، حتى يتولى خيط المستهلك المهمة. signal ( queueEmptyCV ); // أو: broadcast(queueEmptyCV); // نهاية الأقسام الحرجة.// حرر "queueLock" حتى نحتاجه مرة أخرى لإضافة المهمة التالية. queueLock.release ( ) ; } }// دالة تمثل سلوك كل خيط مستهلك: public method consumer () { while ( true ) { // الحصول على "queueLock" للتحقق الأولي من الشرط. queueLock . acquire ();// قسم حرج يتحقق مما إذا كانت قائمة الانتظار غير فارغة. while ( queue.isEmpty ( ) ) { // تحرير "queueLock"، وإضافة هذا الخيط إلى "queueEmptyCV" وإيقاف هذا الخيط مؤقتًا. wait ( queueLock , queueEmptyCV ); // عند إيقاظ هذا الخيط، يتم استعادة "queueLock" لإجراء فحص الشرط التالي. }// قسم حرج يقوم بإزالة مهمة من قائمة الانتظار (لاحظ أننا نحتفظ بقفل قائمة الانتظار). myTask = queue.dequeue ( );// تنبيه واحد أو جميع خيوط الإنتاج التي تنتظر عدم امتلاء قائمة الانتظار // الآن وقد أصبح ذلك مضمونًا، بحيث يضيف خيط الإنتاج مهمة. signal ( queueFullCV ); // أو: broadcast(queueFullCV); // نهاية الأقسام الحرجة.// حرر "queueLock" حتى نحتاجه مرة أخرى لتنفيذ المهمة التالية. queueLock.release ( ) ;// انطلق وافعل شيئًا ما بالمهمة. doStuff ( myTask ); } }

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

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

إليك الصيغة التي تستخدم متغير شرط واحد فقط وبثه:

global volatile RingBuffer queue ; // مخزن مؤقت حلقي غير آمن للاستخدام في بيئة متعددة الخيوط. global Lock queueLock ; // قفل تبادلي لمخزن المهام الحلقي. (ليس قفل دوراني). global CV queueFullOrEmptyCV ; // متغير شرط واحد يُستخدم عندما لا يكون الطابور جاهزًا لأي خيط // أي لخيوط الإنتاج التي تنتظر امتلاء الطابور // وخيوط الاستهلاك التي تنتظر امتلاء الطابور. // القفل المرتبط به هو "queueLock". // من غير الآمن استخدام "signal" العادي لأنه مرتبط // بشروط متعددة (تأكيدات).// دالة تمثل سلوك كل خيط إنتاج: public method producer () { while ( true ) { // يقوم المنتج بإنشاء مهمة جديدة لإضافتها. task myTask = ...;// الحصول على " queueLock " لإجراء فحص الشرط الأولي. queueLock.acquire ();// قسم حرج يتحقق مما إذا كانت قائمة الانتظار غير ممتلئة. while ( queue.isFull ( )) { // تحرير "queueLock"، وإضافة هذا الخيط إلى "queueFullOrEmptyCV" وإيقاف هذا الخيط مؤقتًا. wait ( queueLock , queueFullOrEmptyCV ) ; // عند إيقاظ هذا الخيط، يتم استعادة "queueLock" لإجراء فحص الشرط التالي. }// القسم الحرج الذي يضيف المهمة إلى قائمة الانتظار (لاحظ أننا نحتفظ بـ "queueLock") . queue.enqueue ( myTask ) ;// إيقاظ جميع خيوط الإنتاج والاستهلاك التي تنتظر امتلاء قائمة الانتظار وعدم فراغها على التوالي // الآن وقد تم ضمان عدم فراغها، حتى يتولى خيط الاستهلاك المهمة. broadcast ( queueFullOrEmptyCV ); // لا تستخدم "signal" (لأنها قد توقظ خيط إنتاج آخر فقط). // نهاية الأقسام الحرجة.// حرر "queueLock" حتى نحتاجه مرة أخرى لإضافة المهمة التالية. queueLock.release ( ) ; } }// دالة تمثل سلوك كل خيط مستهلك: public method consumer () { while ( true ) { // الحصول على "queueLock" للتحقق الأولي من الشرط. queueLock . acquire ();// قسم حرج يتحقق مما إذا كانت قائمة الانتظار غير فارغة. while ( queue.isEmpty ( ) ) { // تحرير "queueLock"، وإضافة هذا الخيط إلى "queueFullOrEmptyCV" وإيقاف هذا الخيط مؤقتًا. wait ( queueLock , queueFullOrEmptyCV ); // عند إيقاظ هذا الخيط، يتم استعادة "queueLock" لإجراء فحص الشرط التالي. }// قسم حرج يقوم بإزالة مهمة من قائمة الانتظار (لاحظ أننا نحتفظ بقفل قائمة الانتظار). myTask = queue.dequeue ( );// إيقاظ جميع خيوط الإنتاج والاستهلاك التي تنتظر امتلاء قائمة الانتظار وعدم فراغها على التوالي // الآن بعد ضمان امتلاء قائمة الانتظار وعدم فراغها، حتى يتمكن خيط الإنتاج من إضافة مهمة. broadcast ( queueFullOrEmptyCV ); // لا تستخدم "signal" (لأنها قد توقظ خيط استهلاك آخر فقط). // نهاية الأقسام الحرجة.// حرر "queueLock" حتى نحتاجه مرة أخرى لتنفيذ المهمة التالية. queueLock.release ( ) ;// انطلق وافعل شيئًا ما بالمهمة. doStuff ( myTask ); } }

عناصر التزامن الأساسية

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

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

نموذج لتنفيذ Mesa-monitor مع اختبار وتعيين

// الأجزاء الأساسية لنظام الخيوط: // افترض أن "ThreadQueue" يدعم الوصول العشوائي. public volatile ThreadQueue readyQueue ; // قائمة انتظار غير آمنة للخيوط للخيوط الجاهزة. العناصر هي (Thread*). public volatile global Thread * currentThread ; // افترض أن هذا المتغير خاص بكل نواة. (المتغيرات الأخرى مشتركة.)// يُنفذ قفلًا دورانيًا على حالة التزامن لنظام الخيوط نفسه فقط. // يُستخدم هذا مع اختبار وتعيين كأداة تزامن أساسية. public volatile global bool threadingSystemBusy = false ;// روتين خدمة مقاطعة تبديل السياق (ISR): // على نواة المعالج الحالية، يتم التبديل استباقيًا إلى مؤشر ترابط آخر. public method contextSwitchISR () { if ( testAndSet ( threadingSystemBusy )) { return ; // لا يمكن تبديل السياق الآن. }// تأكد من عدم تكرار هذا المقاطعة، مما قد يؤدي إلى تعطيل تبديل السياق: systemCall_disableInterrupts ();// استرجاع جميع سجلات العملية قيد التشغيل حاليًا. // بالنسبة لعداد البرنامج (PC)، سنحتاج إلى موقع تعليمة // علامة "استئناف" أدناه. يعتمد الحصول على قيم السجلات على النظام الأساسي وقد يتضمن // قراءة إطار المكدس الحالي، وتعليمات JMP/CALL، وما إلى ذلك . (التفاصيل خارج نطاق هذا الشرح.) currentThread- > registers = getAllRegisters (); // تخزين السجلات في كائن "currentThread" في الذاكرة. currentThread- > registers.PC = resume ; // تعيين قيمة PC التالية إلى علامة "استئناف" أدناه في هذه الطريقة.readyQueue.enqueue ( currentThread ); // إعادة هذا الخيط إلى قائمة الانتظار الجاهزة للتنفيذ لاحقًا. Thread * otherThread = readyQueue.dequeue ( ); // إزالة الخيط الحالي من قائمة الانتظار الجاهزة والحصول على الخيط التالي للتنفيذ. currentThread = otherThread ; // استبدال قيمة مؤشر الخيط الحالي العام ليكون جاهزًا للخيط التالي.// استعادة سجلات الخيط الحالي/الخيط الآخر، بما في ذلك الانتقال إلى عداد البرنامج المخزن للخيط الآخر // (عند "استئناف" أدناه). مرة أخرى، تفاصيل كيفية القيام بذلك خارج نطاق هذا الشرح. restoreRegisters ( otherThread . registers );// *** الآن يتم تشغيل "otherThread" (وهو الآن "currentThread")! الخيط الأصلي في حالة "سكون". ***استئناف : // هنا يجب أن يقوم استدعاء contextSwitch() آخر بتعيين PC عند تبديل السياق مرة أخرى هنا.// العودة إلى حيث توقف الخيط الآخر.threadingSystemBusy = false ; // يجب أن يكون تعيينًا ذريًا. systemCall_enableInterrupts (); // إعادة تفعيل التبديل الاستباقي على هذه النواة. }// دالة إيقاف مؤقت للخيط: // على نواة المعالج الحالية، يتم التبديل المتزامن للسياق إلى خيط آخر دون وضع // الخيط الحالي في قائمة الانتظار. // يجب الاحتفاظ بـ "threadingSystemBusy" وتعطيل المقاطعات حتى لا تتم مقاطعة هذه الدالة // بواسطة مؤقت تبديل الخيوط الذي سيستدعي contextSwitchISR(). // بعد العودة من هذه الدالة، يجب مسح "threadingSystemBusy". public method threadSleep () { // الحصول على جميع سجلات العملية قيد التشغيل حاليًا. // بالنسبة لعداد البرنامج (PC)، سنحتاج إلى موقع التعليمات الخاصة بعلامة "resume" أدناه. الحصول على قيم السجلات يعتمد على النظام الأساسي وقد يتضمن // قراءة إطار المكدس الحالي، وتعليمات JMP/CALL، وما إلى ذلك. (التفاصيل خارج نطاق هذا الشرح.) currentThread -> registers = getAllRegisters (); // تخزين السجلات في كائن "currentThread" في الذاكرة. currentThread -> registers . PC = resume ; // قم بتعيين جهاز الكمبيوتر التالي إلى تسمية "استئناف" أدناه في هذه الطريقة.// على عكس contextSwitchISR()، لن نعيد currentThread إلى readyQueue. // بدلاً من ذلك، تم وضعه بالفعل في قائمة انتظار mutex أو متغير الشرط. Thread * otherThread = readyQueue.dequeue (); // إزالة الخيط الحالي من قائمة الانتظار الجاهزة وجلب الخيط التالي للتشغيل. currentThread = otherThread ; // استبدال قيمة مؤشر الخيط الحالي العام ليكون جاهزًا للخيط التالي.// استعادة سجلات الخيط الحالي/الخيط الآخر، بما في ذلك الانتقال إلى عداد البرنامج المخزن للخيط الآخر // (عند "استئناف" أدناه). مرة أخرى، تفاصيل كيفية القيام بذلك خارج نطاق هذا الشرح. restoreRegisters ( otherThread . registers );// *** الآن يتم تشغيل "otherThread" (وهو الآن "currentThread")! الخيط الأصلي في حالة "سكون". ***استئناف : // هنا يجب أن يقوم استدعاء contextSwitch() آخر بتعيين PC عند تبديل السياق مرة أخرى هنا.// العودة إلى حيث توقف الخيط الآخر. }public method wait ( Mutex m , ConditionVariable c ) { // قفل دوران داخلي أثناء وصول سلاسل العمليات الأخرى على أي نواة إلى // "held" و "threadQueue" أو "readyQueue" لهذا الكائن. while ( testAndSet ( threadingSystemBusy )) {} // ملاحظة: "threadingSystemBusy" الآن صحيح. // استدعاء نظام لتعطيل المقاطعات على هذه النواة حتى لا تتم مقاطعة threadSleep() بواسطة // مؤقت تبديل سلاسل العمليات على هذه النواة والذي سيستدعي contextSwitchISR(). // يتم ذلك خارج threadSleep() لمزيد من الكفاءة بحيث يتم إيقاف هذه السلسلة مؤقتًا // مباشرة بعد وضعها في قائمة انتظار متغير الشرط. systemCall_disableInterrupts (); assert m . held ; // (على وجه التحديد، يجب أن تكون هذه السلسلة هي التي تحتفظ بها.) m . release (); c . waitingThreads . enqueue ( currentThread ); threadSleep (); // يدخل الخيط في وضع السكون... يتم إيقاظ الخيط بواسطة إشارة/بث. threadingSystemBusy = false ; // يجب أن يكون تعيينًا ذريًا. systemCall_enableInterrupts (); // إعادة تفعيل التبديل الاستباقي على هذه النواة. // نمط ميسا: // يمكن الآن حدوث تبديلات السياق هنا، مما يجعل شرط المتصل من جانب العميل خاطئًا. m.acquire (); }public method signal ( ConditionVariable c ) { // قفل دوران داخلي أثناء وصول سلاسل العمليات الأخرى على أي نواة إلى // "held" و "threadQueue" أو "readyQueue" لهذا الكائن. while ( testAndSet ( threadingSystemBusy )) {} // ملاحظة: "threadingSystemBusy" الآن صحيح. // استدعاء نظام لتعطيل المقاطعات على هذه النواة حتى لا تتم مقاطعة threadSleep() بواسطة // مؤقت تبديل سلاسل العمليات على هذه النواة والذي سيستدعي contextSwitchISR(). // يتم ذلك خارج threadSleep() لمزيد من الكفاءة بحيث يتم وضع سلسلة العمليات هذه في وضع السكون // مباشرة بعد الانتقال إلى قائمة انتظار متغير الشرط. systemCall_disableInterrupts (); if ( ! c . waitingThreads . isEmpty ()) { wokenThread = c . waitingThreads . dequeue (); readyQueue . enqueue ( wokenThread ); } threadingSystemBusy = false ; // يجب أن يكون تعيينًا ذريًا. systemCall_enableInterrupts (); // إعادة تفعيل التبديل الاستباقي على هذه النواة. // نمط ميسا: // لا تُعطى أي أولوية للخيط المُستيقظ. }public method broadcast ( ConditionVariable c ) { // قفل دوران داخلي أثناء وصول سلاسل العمليات الأخرى على أي نواة إلى // "held" و "threadQueue" أو "readyQueue" لهذا الكائن. while ( testAndSet ( threadingSystemBusy )) {} // ملاحظة: "threadingSystemBusy" الآن صحيح. // استدعاء نظام لتعطيل المقاطعات على هذه النواة حتى لا تتم مقاطعة threadSleep() بواسطة // مؤقت تبديل سلاسل العمليات على هذه النواة والذي سيستدعي contextSwitchISR(). // يتم ذلك خارج threadSleep() لمزيد من الكفاءة بحيث يتم وضع سلسلة العمليات هذه في وضع السكون // مباشرة بعد الانتقال إلى قائمة انتظار متغير الشرط. systemCall_disableInterrupts (); while ( ! c . waitingThreads . isEmpty ()) { wokenThread = c . waitingThreads . dequeue (); readyQueue . enqueue ( wokenThread ); } threadingSystemBusy = false ; // يجب أن يكون تعيينًا ذريًا. systemCall_enableInterrupts (); // إعادة تفعيل التبديل الاستباقي على هذه النواة. // نمط ميسا: // لا تُعطى الخيوط المُستيقظة أي أولوية. }class Mutex { protected volatile bool held = false ; private volatile ThreadQueue blockingThreads ; // قائمة انتظار غير آمنة للخيوط للخيوط المحظورة. العناصر من نوع (Thread*). public method acquire () { // قفل دوران داخلي أثناء وصول الخيوط الأخرى على أي نواة إلى // "held" و"threadQueue" أو "readyQueue" لهذا الكائن. while ( testAndSet ( threadingSystemBusy )) {} // ملاحظة: "threadingSystemBusy" الآن صحيح. // استدعاء النظام لتعطيل المقاطعات على هذه النواة حتى لا تتم مقاطعة threadSleep() بواسطة // مؤقت تبديل الخيوط على هذه النواة والذي سيستدعي contextSwitchISR(). // يتم ذلك خارج threadSleep() لمزيد من الكفاءة بحيث يتم وضع هذا الخيط في وضع السكون // مباشرة بعد دخوله قائمة انتظار القفل. systemCall_disableInterrupts ();assert ! blockingThreads . contains ( currentThread );إذا كان ( مُحتفظًا به ) { // ضع "currentThread" في قائمة انتظار هذا القفل بحيث يُعتبر // "في حالة سكون" على هذا القفل. // لاحظ أنه لا يزال يتعين التعامل مع "currentThread" بواسطة threadSleep(). readyQueue.remove ( currentThread ) ; blockingThreads.enqueue ( currentThread ); threadSleep (); // الآن تم إيقاظنا، وهو ما يجب أن يكون بسبب أن "مُحتفظًا به" أصبح خطأ. assert !مُحتفظًا به; assert !blockingThreads.contains(currentThread ) ; } مُحتفظ به = صحيح ; نظام مشغول = خطأ ; // يجب أن يكون تعيينًا ذريًا . systemCall_enableInterrupts ( ) ; // أعد تشغيل التبديل الاستباقي على هذه النواة. } public method release () { // قفل دوران داخلي أثناء وصول الخيوط الأخرى على أي نواة إلى // "مُحتفظ به" و"threadQueue" أو "readyQueue" لهذا الكائن . بينما ( اختبار وتعيين ( انشغال النظام ) {} // ملاحظة: "انشغال النظام" أصبح الآن صحيحًا. // استدعاء النظام لتعطيل المقاطعات على هذه النواة لتحسين الكفاءة. استدعاء النظام لتعطيل المقاطعات (); تأكيد الاحتفاظ ؛ // (يجب تحرير القفل فقط أثناء الاحتفاظ به.)held = false ; if ( ! blockingThreads.isEmpty ( )) { Thread * unblockedThread = blockingThreads.dequeue (); readyQueue.enqueue ( unblockedThread ) ; } threadingSystemBusy = false ; // يجب أن يكون تعيينًا ذريًا. systemCall_enableInterrupts (); // إعادة تفعيل التبديل الاستباقي على هذه النواة. } }struct ConditionVariable { volatile ThreadQueue waitingThreads ; }

متغيرات حالة الحجب

كانت المقترحات الأصلية التي قدمها كار هوار وبير برينش هانسن تتعلق بمتغيرات الشرط المُعطِّلة . مع متغير الشرط المُعطِّل، يجب على خيط الإشارة الانتظار خارج الشاشة (على الأقل) حتى يتخلى خيط الإشارة عن الشاشة إما بالعودة أو بالانتظار مرة أخرى على متغير الشرط. تُسمى الشاشات التي تستخدم متغيرات الشرط المُعطِّلة غالبًا بشاشات نمط هوار أو شاشات الإشارة والانتظار العاجل .

نفترض وجود طابورين من الخيوط مرتبطين بكل كائن مراقبة

eطابور الدخول
sهي قائمة انتظار للخيوط التي أرسلت إشارات.

بالإضافة إلى ذلك، نفترض أنه لكل متغير شرطي $c$ ، يوجد طابور

$c$ .q، وهو عبارة عن طابور للخيوط التي تنتظر متغير الشرط $c$

عادةً ما يتم ضمان أن تكون جميع قوائم الانتظار عادلة ، وفي بعض التطبيقات، قد يتم ضمان أن تكون الأولوية لمن يدخل أولاً ويخرج أولاً .

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

أدخل الشاشة: أدخل الطريقة إذا كانت الشاشة مقفلة أضف هذا الموضوع إلى البريد الإلكتروني قم بحظر هذا الموضوع آخر قم بقفل الشاشة اترك الشاشة: جدول العودة من الدالة انتظر  $ج$  :أضف هذا الموضوع إلى  $c.q$  جدول قم بحظر هذا الموضوع الإشارة  $c$  : إذا كان هناك خيط ينتظر  $c.q$ حدد واحذف أحد هذه الخيوط t من  $c.q$  (يُطلق عليه اسم "الخيط المُشار إليه") أضف هذا الموضوع إلى s إعادة تشغيل t (لذا سيشغل الشاشة التالية) قم بحظر هذا الموضوع جدول: إذا كان هناك موضوع على s حدد أحد الخيوط وأزله من s ثم أعد تشغيله (سيشغل هذا الموضوع الشاشة لاحقًا) وإلا إذا كان هناك موضوع على e حدد أحد الخيوط من e وأزله ثم أعد تشغيله (سيشغل هذا الموضوع الشاشة لاحقًا) آخر افتح قفل الشاشة (ستصبح الشاشة غير مستخدمة)

يقوم الروتين scheduleباختيار الخيط التالي لشغل الشاشة، أو في حالة عدم وجود أي خيوط مرشحة، يقوم بإلغاء قفل الشاشة.

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

توفر بعض التطبيقات عملية إشارة وإرجاع تجمع بين الإشارة والإرجاع من إجراء ما.

 أرسل الإشارة  $c$ وقم بالعودة : إذا كان هناك خيط ينتظر  $c.q$ حدد واحذف أحد هذه الخيوط t من  $c.q$  (يُطلق عليه اسم "الخيط المُشار إليه") إعادة تشغيل t (لذا سيشغل الشاشة التالية) آخر جدول العودة من الدالة

في كلتا الحالتين ("الإشارة والانتظار العاجل" أو "الإشارة والانتظار")، عندما يتم إرسال إشارة إلى متغير شرطي، وكان هناك خيط واحد على الأقل ينتظر هذا المتغير، يقوم الخيط المُرسِل بتسليم الإشغال إلى الخيط المُستقبَل بسلاسة، بحيث لا يمكن لأي خيط آخر الحصول على الإشغال بينهما. إذا كانت $P c$ صحيحة في بداية كل عملية إشارة $c$ ، فستكون صحيحة في نهاية كل عملية انتظار $c$ . يلخص ذلك العقود التالية . في هذه العقود، $I هو$ ثابت المُراقب .

أدخل الشاشة: حالة ما بعد المعالجة  $I$  اترك الشاشة: الشرط المسبق  $الأول$ انتظر  $ج$  : الشرط المسبق  $I$ يُعدّل حالة الشاشة. الشرط اللاحق  $P ج$  و  $I$ الإشارة  $c$  : الشرط المسبق  $P c$  و  $I$ يُعدّلان حالة الشاشة . الشرط اللاحق  $I$ الإشارة  $c$ والعودة : الشرط المسبق  $P c$  و  $I$

في هذه العقود، يُفترض أن $I$ و $P c$ لا يعتمدان على محتويات أو أطوال أي طوابير.

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

انتظر  $ج$  : الشرط المسبق الأول  $يُعدّل$  حالة الشاشة. الشرط اللاحق  $ب ج$ تُعدّل الإشارة  $c$ الشرط المسبق ( ليس فارغًا(  $c$  ) و  $P c$  ) أو (فارغ(  $c$  ) و  $I$  ) حالة الشاشة، والشرط اللاحق  $I$

(انظر هوارد ^{[ 4 ]} وبوهر وآخرون ^{[ 5 ]} للمزيد.)

إن التأكيد $P c$ متروك تمامًا للمبرمج؛ فهو أو هي يحتاج فقط إلى أن يكون متسقًا بشأن ماهيته.

نختتم هذا القسم بمثال على فئة آمنة للخيوط تستخدم مراقبًا مانعًا يقوم بتنفيذ مكدس محدود وآمن للخيوط .

فئة المراقبة SharedStack { ثابت خاص السعة := 10 عدد صحيح خاص [السعة] عدد صحيح خاص الحجم := 0 ثابت 0 <= الحجم والحجم <= السعة شرط الحظر الخاص المكدس غير فارغ /* مرتبط بـ 0 < الحجم والحجم <= السعة */ شرط الحظر الخاص المكدس غير ممتلئ /* مرتبط بـ 0 <= الحجم والحجم < السعة */دالة عامة push( قيمة عددية صحيحة ) { إذا كان الحجم يساوي السعة، فانتظر حتى يصبح المكدس غير ممتلئ. تأكد من أن 0 ≤ الحجم و 0 ≤ السعة. A[size] := value ; size := size + 1 تحقق من أن 0 < الحجم و الحجم <= السعة، ثم أرسل إشارة إلى المكدس غير فارغ وأرجعه. } دالة عامة int pop() { إذا كان الحجم = 0، فانتظر حتى يصبح المكدس غير فارغ. تأكد من أن 0 < الحجم و الحجم <= السعة الحجم := الحجم - 1 ؛ تحقق من أن 0 <= الحجم و الحجم < السعة، قم بالإشارة إلى أن المكدس ليس ممتلئًا وقم بإرجاع A[الحجم]. } }

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

متغيرات الحالة غير المحظورة

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

في حالة متغيرات الشرط غير المحظورة، تُسمى عملية الإشارة غالبًا "إشعارًا" - وهو المصطلح الذي سنتبعه هنا. ومن الشائع أيضًا توفير عملية "إشعار الكل" التي تنقل جميع الخيوط المنتظرة لمتغير شرط إلى eقائمة الانتظار.

يُوضح هنا معنى العمليات المختلفة. (نفترض أن كل عملية تعمل بشكل مستقل عن العمليات الأخرى؛ وبالتالي، لا تبدأ الخيوط المعاد تشغيلها بالتنفيذ حتى تكتمل العملية).

أدخل الشاشة: أدخل الطريقة إذا كانت الشاشة مقفلة أضف هذا الموضوع إلى البريد الإلكتروني قم بحظر هذا الموضوع آخر قم بقفل الشاشة اترك الشاشة: جدول العودة من الدالة انتظر  $ج$  :أضف هذا الموضوع إلى  $c.q$  جدول قم بحظر هذا الموضوع إشعار  $c$  : إذا كان هناك خيط ينتظر تنفيذ  $c$  .q حدد واحذف أحد الخيوط t من  $c.q$  (يُطلق عليه اسم "الخيط المُبلّغ") انقل t إلى e إخطار جميع  $c$  : انقل جميع الخيوط المنتظرة على  $c.q$  إلى e جدول : إذا كان هناك موضوع على e حدد أحد الخيوط من e وأزله ثم أعد تشغيله وإلا قم بإلغاء قفل الشاشة

كبديل لهذا المخطط، يمكن نقل الخيط المُبلَّغ عنه إلى قائمة انتظار تُسمى w، والتي لها الأولوية على e. انظر هوارد ^{[ 4 ]} وبوهر وآخرون ^{[ 5 ]} لمزيد من التفاصيل.

من الممكن ربط تأكيد $P c$ بكل متغير شرطي $c$ بحيث يكون $P c$ صحيحًا حتمًا عند العودة من العملية . مع ذلك، يجب ضمان بقاء $P$ $c$ صحيحًا من لحظة تخلي الخيط المُبلِّغ عن الشغل حتى يتم اختيار الخيط المُبلَّغ عنه لإعادة الدخول إلى الشاشة. خلال هذه الفترة، قد يكون هناك نشاط من قِبل خيطين آخرين. لذا، من الشائع أن يكون $P$ $c$ صحيحًا ببساطة .wait $c$

لهذا السبب، من الضروري عادةً وضع كل عملية انتظار داخل حلقة تكرارية كهذه.

بينما ليس (  $P$  ) انتظر ج

حيث $P$ شرط أقوى من $P c$ . تُعامل العمليات كـ"تلميحات" تشير إلى أن $P$ قد يكون صحيحًا بالنسبة لبعض الخيوط المنتظرة. كل تكرار لهذه الحلقة بعد التكرار الأول يمثل إشعارًا مفقودًا؛ لذا، مع أجهزة المراقبة غير الحظرية، يجب توخي الحذر لضمان عدم فقدان عدد كبير جدًا من الإشعارات.notify $c$ notify all $c$

كمثال على "التلميح"، لنفترض حسابًا مصرفيًا ينتظر فيه برنامج السحب حتى يتوفر في الحساب رصيد كافٍ قبل المتابعة.

فئة المراقبة Account { رصيد خاص int := 0 ثابت الرصيد >= 0 شرط غير مانع خاص الرصيد قد يكون كبيرًا بما فيه الكفايةدالة عامة للسحب ( عدد صحيح المبلغ) شرط مسبق المبلغ >= 0 { بينما الرصيد < المبلغ، انتظر حتى يصبح الرصيد كافيًا، ثم تحقق من أن الرصيد >= المبلغ الرصيد := الرصيد - المبلغ } دالة عامة للإيداع ( عدد صحيح المبلغ) شرط مسبق المبلغ >= 0 { الرصيد := الرصيد + المبلغ إخطار الجميع بأن الرصيد قد يكون كبيرًا بما فيه الكفاية } }

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

مراقبة متغيرات الحالة الضمنية

في لغة جافا ، يمكن استخدام كل كائن كمراقب. يجب وضع علامة صريحة على الطرق التي تتطلب استبعادًا متبادلًا باستخدام الكلمة المفتاحية synchronized . كما يمكن وضع علامة synchronized على كتل من التعليمات البرمجية . ^{[ 6 ]}

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

الإشارة الضمنية

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

انتظر P : الشرط المسبق I يُعدّل حالة الشاشة. الشرط اللاحق P و I

تاريخ

طوّر برينش هانسن وهور مفهوم المراقبة في أوائل سبعينيات القرن العشرين، استنادًا إلى أفكار سابقة خاصة بهما وبإدسكر ديكسترا . ^{[ 8 ]} نشر برينش هانسن أول تدوين للمراقبة، معتمدًا مفهوم الفئة من سيمولا 67 ، ^{[ 1 ]} وابتكر آلية للانتظار في الطابور. ^{[ 9 ]} حسّن هور قواعد استئناف العمليات. ^{[ 2 ]} أنشأ برينش هانسن أول تطبيق للمراقبة، في كونكرنت باسكال . ^{[ 8 ]} أثبت هور تكافؤها مع الإشارات الثنائية .

سرعان ما تم استخدام الشاشات (و Concurrent Pascal) لهيكلة مزامنة العمليات في نظام التشغيل Solo . ^{[ 10 ]}^{[ 11 ]}

تشمل لغات البرمجة التي تدعم الشاشات ما يلي:

لغة آدا منذ الإصدار 95 (ككائنات محمية)
لغة سي شارب (وغيرها من اللغات التي تستخدم إطار عمل .NET )
إقليدس المتزامن
باسكال المتزامن
د
دلفي (دلفي 2009 وما فوق، عبر TObject.Monitor)
جافا (عبر طريقتي الانتظار والإشعار)
اذهب ^{[ 12 ]}^{[ 13 ]}
ميسا
مودولا-3
بايثون (عبر كائن threading.Condition )
روبي
حديث قصير غير واضح
تورينج ، تورينج+ ، وتورينج الموجهة للكائنات
μC++
مقدمة مرئية

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

انظر أيضاً

الاستبعاد المتبادل
التواصل بشأن العمليات المتسلسلة - وهو تطوير لاحق لأجهزة المراقبة من قِبل كار هوار
السيمفور (البرمجة)

ملحوظات

1 2 برينش هانسن، بير (1973). "7.2 مفهوم الفئة" (ملف PDF) . مبادئ نظام التشغيل . برنتيس هول. ISBN 978-0-13-637843-3.
1 2 هوار، سي. إيه. آر. (أكتوبر 1974). "المراقبون: مفهوم هيكلة نظام التشغيل". مجلة الاتصالات ACM . 17 (10): 549-557 . CiteSeerX 10.1.1.24.6394 . doi : 10.1145/355620.361161 . S2CID 1005769 .
↑ هانسن، بي. بي. (يونيو 1975). "لغة البرمجة كونكرنت باسكال" (ملف PDF) . مجلة IEEE للمعاملات في هندسة البرمجيات، SE-1 (2): 199-207 . رمز Bibcode : 1975ITSEn...1..199H . doi : 10.1109/TSE.1975.6312840 . S2CID 2000388 .
1 2 هوارد، جون هـ. (1976). "الإشارات في الشاشات" . وقائع المؤتمر الدولي الثاني لهندسة البرمجيات ICSE '76 . المؤتمر الدولي لهندسة البرمجيات. لوس ألاميتوس، كاليفورنيا، الولايات المتحدة الأمريكية: مطبعة جمعية مهندسي الكهرباء والإلكترونيات. الصفحات 47-52 .
1 2 بوهر، بيتر أ.؛ فورتييه، ميشيل؛ كوفين، مايكل هـ. (مارس 1995). "تصنيف الشاشات" . مجلة ACM Computing Surveys . 27 (1): 63-107 . doi : 10.1145/214037.214100 . S2CID 207193134 .
↑ بلوخ 2018 ، ص 311-316، §البند 11: مزامنة الوصول إلى البيانات القابلة للتغيير المشتركة.
↑ Bloch 2018 ، ص 325-329 ، §الفصل 11 البند 81: تفضيل أدوات التزامن للانتظار والإخطار.
1 2 هانسن، بير برينش (1993). "الشاشات وباسكال المتزامنة: تاريخ شخصي". HOPL-II: المؤتمر الثاني لجمعية ACM SIGPLAN حول تاريخ لغات البرمجة . تاريخ لغات البرمجة. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM . الصفحات 1-35 . doi : 10.1145/155360.155361 . ISBN 0-89791-570-4.
↑ برينش هانسن، بير (يوليو 1972). "البرمجة المتعددة المهيكلة (ورقة بحثية مدعوة)" . مجلة اتصالات رابطة مكائن الحوسبة . 15 (7): 574-578 . doi : 10.1145/361454.361473 . S2CID 14125530 .
↑ برينش هانسن، بير (أبريل 1976). "نظام التشغيل سولو: برنامج باسكال متزامن" (ملف PDF) . البرمجيات: الممارسة والخبرة .
↑ برينش هانسن، بير (1977). هندسة البرامج المتزامنة . برنتيس هول. ISBN 978-0-13-044628-2.
↑ "sync - لغة برمجة Go" . golang.org . تم الاطلاع عليه بتاريخ 17-06-2021 .
↑ "ما هو "sync.Cond" | dtyler.io" . dtyler.io . مؤرشف من الأصل بتاريخ 2021-10-01 . تم الاطلاع عليه بتاريخ 2021-06-17 .

للمزيد من القراءة

بلوخ، جوشوا (2018). "جافا الفعّالة: دليل لغة البرمجة" ( الطبعة الثالثة). أديسون-ويسلي. ISBN 978-0134685991.
الشاشات: مفهوم هيكلة نظام التشغيل، كار هوار - اتصالات رابطة آلات الحوسبة ، المجلد 17، العدد 10، الصفحات 549-557، أكتوبر 1974
تصنيف الشاشة: PA Buhr، M. Fortier، MH Coffin – ACM Computing Surveys ، 1995

روابط خارجية

مراقبو جافا (شرح واضح)
" الشاشات: مفهوم هيكلة نظام التشغيل " بقلم سي. آر. هوار
" الإشارات في الشاشات "

[:0-1] 1 2 برينش هانسن، بير (1973). "7.2 مفهوم الفئة" (ملف PDF) . مبادئ نظام التشغيل . برنتيس هول. ISBN 978-0-13-637843-3.

[:1-2] 1 2 هوار، سي. إيه. آر. (أكتوبر 1974). "المراقبون: مفهوم هيكلة نظام التشغيل". مجلة الاتصالات ACM . 17 (10): 549-557 . CiteSeerX 10.1.1.24.6394 . doi : 10.1145/355620.361161 . S2CID 1005769 .

[3] هانسن، بي. بي. (يونيو 1975). "لغة البرمجة كونكرنت باسكال" (ملف PDF) . مجلة IEEE للمعاملات في هندسة البرمجيات، SE-1 (2): 199-207 . رمز Bibcode : 1975ITSEn...1..199H . doi : 10.1109/TSE.1975.6312840 . S2CID 2000388 .

[1976_Howard-4] 1 2 هوارد، جون هـ. (1976). "الإشارات في الشاشات" . وقائع المؤتمر الدولي الثاني لهندسة البرمجيات ICSE '76 . المؤتمر الدولي لهندسة البرمجيات. لوس ألاميتوس، كاليفورنيا، الولايات المتحدة الأمريكية: مطبعة جمعية مهندسي الكهرباء والإلكترونيات. الصفحات 47-52 .

[1995_Buhr-Fortier-Coffin-5] 1 2 بوهر، بيتر أ.؛ فورتييه، ميشيل؛ كوفين، مايكل هـ. (مارس 1995). "تصنيف الشاشات" . مجلة ACM Computing Surveys . 27 (1): 63-107 . doi : 10.1145/214037.214100 . S2CID 207193134 .

[FOOTNOTEBloch2018311-316§Item_11:_Synchronize_access_to_shared_mutable_data-6] بلوخ 2018 ، ص 311-316، §البند 11: مزامنة الوصول إلى البيانات القابلة للتغيير المشتركة.

[FOOTNOTEBloch2018325-329§Chapter_11_Item_81:_Prefer_concurrency_utilities_to_wait_and_notify-7] Bloch 2018 ، ص 325-329 ، §الفصل 11 البند 81: تفضيل أدوات التزامن للانتظار والإخطار.

[:2-8] 1 2 هانسن، بير برينش (1993). "الشاشات وباسكال المتزامنة: تاريخ شخصي". HOPL-II: المؤتمر الثاني لجمعية ACM SIGPLAN حول تاريخ لغات البرمجة . تاريخ لغات البرمجة. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM . الصفحات 1-35 . doi : 10.1145/155360.155361 . ISBN 0-89791-570-4.

[9] برينش هانسن، بير (يوليو 1972). "البرمجة المتعددة المهيكلة (ورقة بحثية مدعوة)" . مجلة اتصالات رابطة مكائن الحوسبة . 15 (7): 574-578 . doi : 10.1145/361454.361473 . S2CID 14125530 .

[10] برينش هانسن، بير (أبريل 1976). "نظام التشغيل سولو: برنامج باسكال متزامن" (ملف PDF) . البرمجيات: الممارسة والخبرة .

[11] برينش هانسن، بير (1977). هندسة البرامج المتزامنة . برنتيس هول. ISBN 978-0-13-044628-2.

[12] "sync - لغة برمجة Go" . golang.org . تم الاطلاع عليه بتاريخ 17-06-2021 .

[13] "ما هو "sync.Cond" | dtyler.io" . dtyler.io . مؤرشف من الأصل بتاريخ 2021-10-01 . تم الاطلاع عليه بتاريخ 2021-06-17 .

لغة

[ 4 ]

[ 5 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]