التزامن من جديد

12. التزامن من جديد

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

12.1 أنماط القفل

غالبًا ما يكون إقفالُ العناصر المُخزَّنة مؤقّتًا تحدّيًا. فمثلًا، يخزّن مخزن كتل نظام الملفّات المؤقّت (bio.c:25) نسخًا من كتلٍ قرصيّةٍ يصل عددها إلى NBUF. ومن الحيويّ أن يكون لكتلة قرصٍ معيّنةٍ نسخةٌ واحدةٌ على الأكثر في المخزن المؤقّت؛ وإلّا فقد تُجري عمليّاتٌ مختلفة تعديلاتٍ متعارضةً على نسخٍ مختلفةٍ ممّا يجب أن يكون الكتلةَ نفسها. وكلّ كتلةٍ محفوظةٍ في المخزن المؤقّت مخزّنةٌ في struct buf. ويملك struct buf حقل قفلٍ يساعد على ضمان أنّ عمليّةً واحدةً فقط تستخدم كتلةَ قرصٍ معيّنةً في كلّ مرّة. لكنّ هذا القفل غير كافٍ: فماذا لو لم تكن كتلةٌ موجودةً في المخزن المؤقّت إطلاقًا، وأرادت عمليّتان استخدامها في الوقت نفسه؟ فليس هناك struct buf (إذ لم تُخزَّن الكتلة مؤقّتًا بعد)، وبالتالي لا شيءَ يُقفَل. ويتعامل xv6 مع هذا الموقف بإقران قفلٍ إضافيّ (bcache.lock) بمجموعة هويّات الكتل المخزّنة. وعلى الشيفرة التي تحتاج إلى فحص ما إذا كانت كتلةٌ مخزّنةً (مثل bget)، أو إلى تغيير مجموعة الكتل المخزّنة، أن تحوز bcache.lock؛ وبعد أن تجد تلك الشيفرة الكتلةَ وstruct buf اللذين تحتاجهما، يمكنها تحرير bcache.lock وقفل الكتلة الخاصّة وحدها. وهذا نمطٌ شائع: قفلٌ واحد لمجموعة العناصر، وقفلٌ واحد لكلّ عنصر.

عادةً ما تكون الدالّة نفسها التي تحوز قفلًا هي التي تحرّره. لكنّ طريقةً أدقّ لرؤية الأمور هي أنّ القفل يُحاز في بداية تتابعٍ يجب أن يبدو ذرّيًّا، ويُحرَّر عند انتهاء ذلك التتابع. فإن بدأ التتابع وانتهى في دوالّ مختلفة، أو في خيوط مختلفة، أو على معالجات مختلفة، فعلى حيازة القفل وتحريره أن يفعلا المثل. ووظيفة القفل هي إجبار الاستخدامات الأخرى على الانتظار، لا تثبيت جزءٍ من البيانات بفاعلٍ معيّن. ومثالٌ على ذلك acquire في yield، الذي يُحرَّر في خيط المجدول بدلًا من العمليّة الحازة. ومثالٌ آخر هو acquiresleep في ilock؛ وهذه الشيفرة تنام غالبًا أثناء قراءة القرص؛ وقد تستيقظ على معالجٍ مختلف، ومعنى ذلك أنّ القفل قد يُحاز ويُحرَّر على معالجين مختلفين.

إنّ تحرير كائنٍ يحميه قفلٌ مُدمَجٌ فيه عملٌ دقيق، إذ إنّ حيازة القفل لا تكفي لضمان أنّ التحرير سيكون صحيحًا. وتنشأ الحالة المُشكِلة عندما يكون خيطٌ آخر منتظرًا في acquire ليستخدم الكائن؛ فتحرير الكائن يحرّر ضمنيًّا القفل المدمج، ممّا سيُسبّب خللًا في الخيط المنتظر. وأحد الحلول هو تتبّع عدد الإشارات (reference count) الموجودة إلى الكائن، بحيث لا يُحرَّر إلّا عند اختفاء الإشارة الأخيرة. وانظر pipeclose مثلًا؛ فـpi->readopen وpi->writeopen يتتبّعان ما إذا كانت للأنبوب واصفاتُ ملفّاتٍ تُشير إليه.

ترى عادةً أقفالًا حول تتابعاتٍ من القراءات والكتابات لمجموعاتٍ من العناصر المترابطة؛ وتكفل هذه الأقفال ألّا ترى الخيوط الأخرى إلّا تتابعاتٍ مكتملةً من التحديثات (طالما أنّها تُقفِل هي أيضًا). فماذا عن المواقف التي يكون التحديث فيها كتابةً بسيطةً إلى متغيّرٍ مشتركٍ وحيد؟ فمثلًا، تُقفل setkilled وkilled حول استخداماتهما البسيطة لـp->killed. ولو لم يكن هناك قفل، لأمكن خيطٌ أن يكتب p->killed في اللحظة التي يقرؤها فيها خيطٌ آخر. وهذا تسابقٌ، وتقول مواصفة لغة C إنّ التسابق يُفضي إلى سلوكٍ غير محدّد (undefined behavior)، أي أنّ البرنامج قد ينهار أو يُنتج نتائجَ خاطئة^[1]. وتمنع الأقفال التسابقَ وتتجنّب السلوك غير المحدّد.

وأحد الأسباب التي تجعل التسابق يُعطّل البرامج هو أنّ المصرّف، إن لم تكن هناك أقفالٌ أو بنى مكافئة، قد يُنشئ شيفرةً آليةً تقرأ الذاكرة وتكتب فيها بطرائق تختلف تمامًا عن شيفرة C الأصليّة. فمثلًا، قد تنسخ الشيفرة الآلية لخيطٍ ينادي killed p->killed إلى مسجّلٍ وتقرأ تلك القيمة المخزّنة مؤقّتًا وحدها؛ ومعنى ذلك أنّ الخيط قد لا يرى كتابةً إلى p->killed أبدًا. وتمنع الأقفال مثل هذا التخزين المؤقّت.

12.2 أنماط شبيهة بالقفل

تستخدم xv6 في أماكنَ كثيرةٍ عدّادَ إشاراتٍ أو رايةً (flag) بطريقةٍ شبيهة بالقفل للإشارة إلى أنّ كائنًا مُخصَّصٌ ينبغي ألّا يُحرَّر أو يُعاد استخدامه. ويعمل p->state الخاصّ بالعمليّة على هذا النحو، كما يعمل عددُ الإشارات في البنى file وinode وbuf. ومع أنّ قفلًا يحمي الراية أو عدّاد الإشارات في كلّ حالة، إلّا أنّ الأخير هو الذي يمنع تحرير الكائن قبل أوانه.

ويستخدم نظام الملفّات عدّادات إشارات struct inode بوصفها نوعًا من القفل المشترك الذي تستطيع حيازته عمليّاتٌ متعدّدة، لتجنّب الجمود الذي كان سيقع لو استُخدمت الأقفال العاديّة. فمثلًا، تقفل الحلقة في namex الدليل الذي يسمّيه كلّ مُكوِّنٍ من مُكوّنات اسم المسار بالتتابع. لكنّ namex مضطرّ إلى تحرير كلّ قفلٍ في نهاية الحلقة، إذ إنّه لو حاز أقفالًا متعدّدةً لأمكن أن يجمد مع نفسه إن تضمّن اسم المسار نقطةً (مثل a/./b). وقد يجمد أيضًا مع بحثٍ متزامنٍ يتعلّق بالدليل وبـ... وكما يشرح الفصل 10، فالحلّ هو أن تحمل الحلقة عقدة الدليل (inode) إلى التكرار التالي بعد زيادة عدّاد إشاراتها، دون أن تقفلها.

وبعضُ بنى البيانات محميّةٌ بآليّاتٍ مختلفةٍ في أزمنةٍ مختلفة، وقد تكون محميّةً في بعض الأحيان من الوصول المتزامن ضمْنًا ببنية شيفرة xv6 ذاتها بدلًا من أقفالٍ صريحة. فمثلًا، حين تكون صفحةٌ فيزيائيّة حرّة، فإنّها محميّةٌ بـkmem.lock. فإذا خُصِّصت الصفحة بعدئذٍ لأنبوبٍ (pipe.c:23)، فهي محميّةٌ بقفلٍ مختلف (pi->lock المدمج). وإذا أُعيد تخصيص الصفحة لذاكرة مستخدم عمليّةٍ جديدة، فهي غير محميّةٍ بقفلٍ على الإطلاق. وبدلًا من ذلك، يحميها من الوصول المتزامن كونُ المخصّص لا يُعطي تلك الصفحة لأيّ عمليّةٍ أخرى (حتّى تُحرَّر). وملكيّة ذاكرة العمليّة الجديدة مركّبة: فأوّلًا يخصّصها الأب ويعمل عليها في fork، ثمّ يستخدمها الولد، و(بعد خروج الولد) يعود الأب مالكًا للذاكرة ويسلّمها إلى kfree. وهناك درسان هنا: قد يُحمى كائنُ البيانات من التزامن بطرائق مختلفةٍ في نقاطٍ مختلفةٍ من مدّة حياته، وقد تأخذ الحماية صورةَ بنيةٍ ضمْنيّةٍ بدلًا من أقفالٍ صريحة.

ومثالٌ أخير شبه القفل هو الحاجة إلى تعطيل المقاطعات حول نداءات mycpu()، كما في myproc(). فتعطيل المقاطعات يجعل الشيفرة المُنادِيَة ذرّيّةً بالنسبة إلى مقاطعات المؤقّت التي قد تُجبر على تبديل السياق، فتنقل العمليّة إلى معالجٍ مختلف.

12.3 بلا أقفالٍ على الإطلاق

هناك بضعة مواضع تتشارك فيها xv6 بياناتٍ قابلة للتغيير بغير أقفالٍ على الإطلاق. أحدها في تنفيذ الأقفال الدورانية، مع أنّ المرء قد يرى تعليمات RISC-V الذرّية باعتبارها تعتمد على أقفالٍ مُنفَّذةٍ في العتاد. وهناك أيضًا المتغيّر started في main.c، المستخدم لمنع المعالجات الأخرى من التشغيل حتّى تُتمّ المعالجة صفر تهيئة xv6؛ ويضمن volatile أنّ المصرّف يُنشئ تعليمات تحميلٍ وتخزينٍ فعلًا.

وتحتوي xv6 على حالاتٍ تكتب فيها معالجةٌ أو خيطٌ بعض البيانات، وتقرؤها معالجةٌ أو خيطٌ آخر، دون أن يكون هناك قفلٌ خاصٌّ مخصَّصٌ لحماية تلك البيانات. فمثلًا، في fork، يكتب الأب صفحات ذاكرة المستخدم الخاصّة بالولد، ويقرؤها الولد (خيطٌ مختلف، ربّما على معالجٍ مختلف)؛ ولا يحمي تلك الصفحات قفلٌ صريح. وهذه ليست مشكلةَ إقفالٍ بالمعنى الدقيق، إذ إنّ الولد لا يبدأ التنفيذ إلّا بعد أن يُتمّ الأب الكتابة. لكنّها مشكلةُ ترتيب ذاكرة (memory ordering) محتملة (انظر الفصل 7)، إذ لا سببَ لتوقّع أن ترى معالجةٌ كتاباتِ معالجةٍ أخرى دون حاجز ذاكرة (memory barrier). غير أنّ الأب يحرّر الأقفال، والولد يحوز الأقفال حين يبدأ تشغيله، لذا فإنّ حواجز الذاكرة في acquire وrelease تضمن أنّ معالجة الولد ترى كتابات الأب.

12.4 التوازي

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

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

أمّا تبديل السياق فمثالٌ أعقد. فيستطيع خيطا نواة، كلٌّ منهما ينفّذ على معالجه الخاصّ، مناداة yield وsched وswtch في الوقت نفسه، فتُنفّذ النداءات توازيًّا. وكلٌّ من الخيطين يحوز قفلًا، لكنّهما قفلان مختلفان، فلا يضطرّان إلى انتظار أحدهما الآخر. لكنّ المعالجين، حال وصولهما إلى scheduler، قد يتنازعان على الأقفال أثناء البحث في جدول العمليّات عن عمليّةٍ حالتها RUNNABLE. أي أنّ xv6 يُرجَّح أن يجني فائدةً في الأداء من المعالجات المتعدّدة أثناء تبديل السياق، لكن ربّما ليس بالقدر الممكن.

ومثالٌ آخر هو النداءات المتزامنة على fork من عمليّاتٍ مختلفةٍ على معالجاتَ مختلفة. فقد يضطرّ النداءان إلى انتظار أحدهما الآخر بخصوص pid_lock وkmem.lock، وبخصوص الأقفال الخاصّة بكلّ عمليّة واللازمة للبحث في جدول العمليّات عن عمليّةٍ حالتها UNUSED. ومن ناحية أخرى، تستطيع العمليّتان المُفرّعتان نسخَ صفحات ذاكرة المستخدم وتهيئةَ صفحات جدول الصفحات نسخًا وتهيئةً تامَّي التوازي.

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