الجدولة

8. الجدولة

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

قبل المضي في هذا الفصل، يُرجى قراءة kernel/proc.h، وkernel/swtch.S، وyield() وsched() وscheduler() في kernel/proc.c.

8.1 تعدّد الإتاحة

يُحقّق xv6 تعدّد الإتاحة بتبديل كلّ معالجٍ من عمليةٍ إلى أخرى في موقفين. أوّلًا، يبدّل xv6 عندما تُجري عمليةٌ نداء نظامٍ يحجب التنفيذ (أي إنّ عليها أن تنتظر)، مثل read أو wait. وثانيًا، يُجري xv6 تبديلًا قسريًّا دوريًّا للتعامل مع العمليات التي تحسب مددًا طويلة دون أن تحجب. ويُسمّى النوع الأوّل بالتبديلات الطوعية، والثاني بالتبديلات اللاإرادية.

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

8.2 نظرة عامة على تبديل السياق

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

الشكل 8.1: التبديل من عملية مستخدمٍ إلى أخرى. في هذا المثال، يعمل xv6 بمعالجٍ واحد (وبالتالي خيط مُجدولٍ واحد).

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

8.3 الشيفرة: تبديل السياق

تحتوي الدالّة swtch() في kernel/swtch.S على قلب تبديل سياق الخيوط: فهي تحفظ سجلات المعالج الخاصّة بالخيط المُبدَّل منه، وتستعيد السجلات المحفوظة سابقًا للخيط المُبدَّل إليه. والسبب الأساسي لكون هذا كافيًا هو أنّ حالة الخيط تتألّف من بياناتٍ في الذاكرة (مثل مكدّسه) مضافًا إليها سجلات المعالج؛ فلا حاجة إلى حفظ ذاكرة الخيط واستعادتها لأنّ الخيوط المختلفة تحتفظ ببياناتها في مناطق مختلفة من RAM؛ أمّا المعالج فلديه مجموعةٌ واحدة فقط من السجلات، فيجب تبديلها (حفظها واستعادتها) بين الخيوط.

تتضمّن struct proc الخاصّة بكلّ خيطٍ بنية struct context تحمل السجلات المحفوظة للخيط حين لا يكون قيد التشغيل. أمّا struct context الخاصّة بخيط مُجدول معالجٍ ما فتقع في struct cpu الخاصّة بذلك المعالج. وحين يريد الخيط X التبديل إلى الخيط Y، ينادي الخيط X swtch(&X’s context, &Y’s context). فتحفظ swtch() سجلات المعالج الحالية في سياق X، ثمّ تحمّل محتوى سياق Y إلى سجلات المعالج، ثمّ ترجع.

وهذه نسخةٌ مختصرة من swtch:

swtch:
        sd ra, 0(a0)
        sd sp, 8(a0)
        sd s0, 16(a0)
        ...
        sd s11, 104(a0)

        ld ra, 0(a1)
        ld sp, 8(a1)
        ld s0, 16(a1)
        ...
        ld s11, 104(a1)
        
        ret

يحمل a0 الوسيط الأوّل للدالّة، وa1 الوسيط الثاني؛ وهما في هذه الحالة مؤشّرا struct context. ويشير 16(a0) إلى إزاحةٍ قدرها 16 بايتًا داخل الذاكرة التي يشير إليها a0؛ وبالرجوع إلى تعريف struct context في kernel/proc.h، نجد أنّ هذا هو حقل البنية المسمّى s0.

فإلى أين يرجع swtch من خلال ret؟ إنّه يرجع إلى التعليمة التي يشير إليها السجلّ ra. وفي المثال الذي ينادي فيه الخيط X swtch() للتبديل إلى Y، فإنّه حين تُنفَّذ ret يكون ra قد حُمّل لتوّه من struct context الخاصّة بـY. وra الموجود في struct context الخاصّة بالأخير قد حُفظ أصلًا بنداء الأخير لـswtch حين تخلّى عن المعالج في الماضي. لذا يرجع ret إلى التعليمة التالية للنقطة التي نادى فيها الأخير swtch()؛ أي أنّ نداء X لـswtch() يرجع كأنّه رجوعٌ من نداء الأخير الأصلي لـswtch(). وسيكون sp هو مؤشّر مكدّس الأخير، إذ حمّل swtch القيمة sp من struct context الخاصّة به؛ وبذلك ينفّذ الأخير على مكدّسه الخاصّ عند الرجوع. ولا تحتاج swtch() إلى حفظ عدّاد البرنامج أو استعادته مباشرةً؛ فيكفيها حفظ ra واستعادته.

تحفظ swtch السجلات المحفوظة من طرف المُنادَى (ra,sp,s0..s11) ولا تحفظ السجلات المحفوظة من طرف المُنادِي. ويتطلّب اصطلاح النداء في RISC-V أنّ الشيفرة التي تحتاج إلى الحفاظ على قيمة سجلٍّ محفوظٍ من طرف المُنادِي عبر نداء دالّة، يجب أن يُولّد المصرِّف تعليماتٍ تحفظ السجلّ في المكدّس قبل نداء الدالّة، وتستعيده من المكدّس عند رجوع الدالّة. وبالتالي تستطيع swtch الاعتماد على أنّ الدالّة التي نادتها قد حفظت السجلات المحفوظة من طرف المُنادِي مسبقًا (وإمّا ذلك، أو أنّ الدالّة المُنادية لم تكن بحاجةٍ إلى قيم تلك السجلات).

8.4 الشيفرة: الجدولة

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

يجب على العمليّة التي تريد التخلّي عن المعالج أن تحوز قفل عمليتهما p->lock، وأن تُطلق أيّ أقفال أخرى تحتجزها، وأن تحدّث حالتها (p->state)، ثمّ تنادي sched. ويمكنك رؤية هذا التسلسل في yield وsleep وkexit. وتنادي sched الدالّة swtch لحفظ السياق الحالي في p->context والتبديل إلى سياق المُجدول في cpu->context. وترجع swtch على مكدّس المُجدول كأنّ نداء scheduler للدالّة swtch قد رجع (proc.c:453).

تدير scheduler حلقة: تجد عمليةً للتشغيل، وتتبدّل إليها بـswtch()، وفي النهاية ستردّ هي بدورها بـswtch() إلى المُجدول، الذي يواصل حلقته. ويطوف المُجدول على جدول العمليات بحثًا عن عمليةٍ قابلةٍ للتشغيل، أي أنّ حالتها p->state == RUNNABLE. وبمجرّد أن يجد عمليةً، يضبط المتغيّر c->proc للعملية الحالية الخاصّة بكلّ معالجٍ، ويوسم العملية بـRUNNING، ثمّ ينادي swtch لبدء تشغيلها (proc.c:448-453). وفي مرحلةٍ ما من الماضي، لا بدّ أنّ العملية الهدف قد نادت swtch()؛ ونداء المُجدول لـswtch() يرجع فعليًا من ذلك النداء الأسبق. ويوضّح الشكل 8.2 هذا النمط.

الشكل 8.2: يكون خيط المُجدول دائمًا إمّا مصدرًا أو مقصدًا في swtch()، والقفل p->lock المعنيّ محجوزٌ دائمًا.

يحتفظ xv6 بالقفل p->lock عبر نداءات swtch: فالمُنادي لـswtch يحوز القفل، لكنّه يُطلَق في الهدف بعد رجوع swtch. وهذا الترتيب غير معتاد: فالأكثر شيوعًا هو أن يُطلق الخيط الذي يحوز القفل هو نفسه أيضًا. وتكسر تبديلات السياق في xv6 هذا الاصطلاح لأنّه يجب تحديث p->state وp->context معًا ذرّيًّا. فمثلًا، لو أُطلق p->lock قبل استدعاء swtch، فقد يقرّر معالجٌ آخر $c$ تشغيل العملية لأنّ حالتها RUNNABLE. وسيستدعي المعالج $c$ الدالّة swtch التي ستستعيد من p->context بينما المعالج الأصلي ما زال يحفظ في p->context. وستكون النتيجة استعادة العملية بسجلاتٍ محفوظةٍ جزئيًّا على المعالج $c$، واستخدام كلٍّ من المعالجين المكدّس نفسه، وهذا ما سيسبّب فوضى. وبمجرّد أن تبدأ yield في تعديل حالة عمليةٍ عاملةٍ لجعلها RUNNABLE، يجب أن يبقى p->lock محجوزًا حتّى تحفظ العملية جميع سجلاتها ويعمل المُجدول على مكدّسها. وأقرب نقطةٍ صحيحةٍ للإطلاق هي بعد أن يمسح scheduler (العامل على مكدّسه الخاصّ) المتغيّر c->proc. وبالمثل، بمجرّد أن يبدأ scheduler في تحويل عمليةٍ RUNNABLE إلى RUNNING، فلا يمكن إطلاق القفل حتّى يعمل خيط نواة العملية كاملًا (بعد swtch، مثلًا في yield).

هناك حالةٌ واحدة لا ينتهي فيها نداء swtch الصادر عن المُجدول في sched. إذ تضبط allocproc سجلّ ra في سياق العملية الجديدة على forkret، حتّى «يرجع» أوّل swtch إلى بداية تلك الدالّة. وظيفة forkret هي إطلاق القفل p->lock وضبط بعض سجلات التحكّم وبعض حقول إطار المصيدة المطلوبة من أجل الرجوع إلى فضاء المستخدم. وفي النهاية، تحاكي forkret مسار الرجوع المعتاد من نداء نظامٍ إلى فضاء المستخدم.

8.5 الشيفرة: mycpu وmyproc

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

وبينما يكون معالجٌ معيّنٍ منفّذًا في النواة، يضمن xv6 أنّ سجلّ tp لدى المعالج يحمل دائمًا معرّف قلب (hartid) ذلك المعالج. وترقّم RISC-V معالجاتها، مُعطيةً كلًّا منها معرّف قلبٍ فريدًا. ويستخدم mycpu السجلّ tp لفهرسة مصفوفةٍ من بنى cpu وإعادة تلك الخاصّة بالمعالج الحالي. وتحمل struct cpu مؤشّرًا إلى بنية proc الخاصّة بالعملية التي تعمل حاليًا على ذلك المعالج (إن وُجدت)، والسجلات المحفوظة لخيط المُجدول الخاصّ بالمعالج، وعدد أقفال الدوران المتداخلة اللازمة لإدارة تعطيل المقاطعات.

وضمان أنّ سجلّ tp لدى معالجٍ ما يحمل معرّف قلب ذلك المعالج يتطلّب بعض العمل، إذ إنّ شيفرة المستخدم حرّة في تعديل tp. وتضبط start السجلّ tp في وقتٍ مبكّرٍ من تسلسل إقلاع المعالج، وما زالت في وضع الآلة (start.c:48). وبينما تستعدّ للرجوع إلى فضاء المستخدم، تحفظ prepare_return القيمة tp في صفحة الترامبولين، تحسّبًا لتعديل شيفرة المستخدم لها. وأخيرًا، تستعيد uservec تلك القيمة tp المحفوظة عند الدخول إلى النواة من فضاء المستخدم (trampoline.S:78). ويضمن المصرِّف ألّا يعدّل tp في شيفرة النواة أبدًا. وكان سيكون من الأنسب أن يستطيع xv6 سؤال عتاد RISC-V عن معرّف القلب الحالي عند الحاجة، لكنّ RISC-V لا يسمح بذلك إلّا في وضع الآلة، لا في وضع المشرف.

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

تُعيد الدالّة myproc مؤشّر struct proc الخاصّ بالعملية التي تعمل على المعالج الحالي. وتعطّل myproc المقاطعات، وتنادي mycpu، وتجلب مؤشّر العملية الحالي (c->proc) من struct cpu، ثمّ تُفعّل المقاطعات. وقيمة myproc المُعادة آمنة الاستخدام حتى لو كانت المقاطعات مفعّلة: فإذا نقلت مقاطعة مؤقّتٍ العملية المُنادية إلى معالجٍ آخر، فسيبقى مؤشّر struct proc الخاصّ بها على ما هو عليه.

8.6 عالم الواقع

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