مقدمة في أنظمة التشغيل

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

يمكن العثور على العمل المختبري حول هذا الموضوع هنا:

أجزاء أخرى:

ويمكنك إلقاء نظرة على قناتي في برقية =)

التخطيط: قائمة انتظار ردود الفعل متعددة المستويات

في هذه المحاضرة سوف نتحدث عن مشاكل تطوير واحدة من أشهر النهج
التخطيط يسمى قائمة انتظار التعليقات متعددة المستويات (MLFQ). تم وصف جدولة MLFQ لأول مرة في عام 1962 من قبل فرناندو ج. كورباتو في نظام يسمى نظام مشاركة الوقت المتوافق (CTSS). تم إرسال هذه الأعمال (بما في ذلك الأعمال اللاحقة على Multics) لاحقًا إلى Turing Award. تم تحسين الجدولة لاحقًا واكتسبت نظرة يمكن العثور عليها بالفعل في بعض الأنظمة الحديثة.

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

جوهر المشكلة: كيف تخطط لصياغة المهام دون معرفة كاملة؟ كيفية تطوير برنامج جدولة يقلل وقت الاستجابة للمهام التفاعلية في نفس الوقت ويقلل في نفس الوقت وقت الدوران دون معرفة الوقت لإكمال المهمة؟

ملاحظة: التعلم من الأحداث السابقة

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

ومع ذلك ، ينبغي أن يكون المرء حذراً في مثل هذه التقنية ، لأن التنبؤات يمكن أن تتحول بسهولة إلى خطأ وتؤدي إلى اتخاذ قرارات أسوأ مما قد يكون بدون المعرفة على الإطلاق.

MLFQ: القواعد الأساسية

النظر في القواعد الأساسية لخوارزمية MLFQ. على الرغم من وجود العديد من تطبيقات هذه الخوارزمية ، إلا أن الطرق الأساسية متشابهة.

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

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

وبالتالي نصل إلى قاعدتين أساسيتين لـ MLFQ:

القاعدة 1: إذا كانت الأولوية (أ)> الأولوية (ب) ، فستبدأ المهمة (أ) (ب)
القاعدة 2: إذا كانت الأولوية (A) = الأولوية (B) ، يتم تشغيل A&B باستخدام RR

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

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

دعنا نرسم مثالًا على كيفية ظهور قوائم الانتظار في وقت ما ومن ثم نحصل على شيء مثل هذا:

في هذا المخطط ، توجد عمليتان A و B في قائمة الانتظار ذات الأولوية القصوى. العملية C في مكان ما في الوسط ، والعملية D في نهاية قائمة الانتظار. وفقًا للأوصاف المذكورة أعلاه لخوارزمية MLFQ ، فإن المجدول سوف ينفذ المهام فقط بأولوية قصوى وفقًا للوائح الراديو ، وستكون المهام C و D غير صالحة للعمل.

بطبيعة الحال ، لن تعطي لقطة ثابتة صورة كاملة عن كيفية عمل MLFQ.
من المهم أن نفهم بالضبط كيف تتغير الصورة مع مرور الوقت.

محاولة 1: كيفية تغيير الأولوية

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

القاعدة 3: عندما تدخل مهمة ما إلى النظام ، يتم وضعها في قائمة الانتظار مع الأعلى
الأولوية.
Rule4a: إذا كانت المهمة تستخدم إطار الوقت بالكامل المخصص لها ، فستكون لها
الأولوية تنخفض.
Rule4b: إذا قامت المهمة بتحرير وحدة المعالجة المركزية قبل انتهاء الإطار الزمني الخاص بها ، فحينئذٍ تحررها
يبقى مع نفس الأولوية.

مثال 1: مهمة واحدة طويلة المدى

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

مثال 2: لقد طرحوا مهمة قصيرة

الآن ، دعونا نرى مثالًا على كيفية محاولة MLFQ الاقتراب من SJF. يوجد في هذا المثال مهمتان: A ، وهي مهمة طويلة الأمد تستهلك وحدة المعالجة المركزية باستمرار ، و B ، وهي مهمة تفاعلية قصيرة. افترض أن A عملت بالفعل لبعض الوقت في الوقت الذي تصل فيه المهمة B.

في هذا الرسم البياني ، تكون نتائج البرنامج النصي مرئية. المهمة A ، مثل أي مهمة تستخدم وحدة المعالجة المركزية ، هي في أسفلها. ستصل المهمة B إلى T = 100 وسيتم وضعها في قائمة الانتظار ذات الأولوية القصوى. بما أن وقت عملها قصير ، فسوف ينتهي قبل أن يصل إلى المرحلة الأخيرة.

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

مثال 3: ماذا عن I / O؟

الآن نلقي نظرة على المثال I / O. كما هو مذكور في القاعدة 4 ب ، إذا كانت العملية تحرر معالجًا دون الاستفادة الكاملة من وقت المعالج ، فستظل عند نفس مستوى الأولوية. الهدف من هذه القاعدة بسيط للغاية - إذا نفذت مهمة تفاعلية العديد من عمليات الإدخال / الإخراج ، على سبيل المثال ، في انتظار قيام المستخدم بالضغط على مفتاح أو ماوس ، فإن هذه المهمة ستحرر المعالج قبل النافذة المخصصة. لا نريد حذف هذه المهمة حسب الأولوية ، وبالتالي ستبقى على نفس المستوى.

يوضح هذا المثال كيف ستعمل الخوارزمية مع مثل هذه العمليات - مهمة تفاعلية B ، تحتاج إلى وحدة المعالجة المركزية لمدة 1 مللي ثانية فقط قبل تنفيذ عملية الإدخال / الإخراج ، ومهمة طويلة A ، والتي تستخدم وحدة المعالجة المركزية طوال الوقت.

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

مشاكل مع خوارزمية MLFQ الحالية

في الأمثلة السابقة ، قمنا ببناء الإصدار الأساسي من MLFQ. ويبدو أنه يؤدي وظيفته بشكل جيد وبصراحة ، حيث يوزع وقت المعالج بأمانة بين المهام الطويلة ويسمح للمهام أو المهام القصيرة بالوصول المكثف إلى I / O بسرعة. لسوء الحظ ، يحتوي هذا النهج على العديد من المشكلات الخطيرة.

أولاً ، مشكلة الجوع: إذا كان هناك الكثير من المهام التفاعلية في النظام ، فسوف تستهلك كل وقت المعالج ، وبالتالي لن تكون هناك مهمة طويلة يمكن تنفيذها (وهي تتضور جوعًا).

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

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

سؤال للجمهور: ما هي الهجمات على المخطط الذي يمكن القيام به في العالم الحديث؟

محاولة 2: رفع الأولوية

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

القاعدة 5 : بعد فترة معينة من S ، نقل جميع المهام في النظام إلى أعلى أولوية.

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

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

محاولة 3: أفضل المحاسبة

الآن لدينا مشكلة واحدة أخرى تحتاج إلى حل: كيف لا
اسمحوا خداع مخططنا؟ مذنب هذه الفرصة
القواعد 4 أ ، 4 ب ، والتي تسمح للمهمة بالحفاظ على الأولوية ، وتحرير المعالج
قبل انتهاء الوقت المخصص. كيفية التعامل مع هذا؟
يمكن اعتبار الحل في هذه الحالة أفضل محاسبة لوقت وحدة المعالجة المركزية في كل مرة
مستوى MLFQ. بدلا من نسيان الوقت الذي يستخدمه البرنامج
المعالج للفترة المخصصة ، يجب عليك النظر وحفظه. بعد
لقد أنفقت العملية الوقت المخصص لذلك يجب تخفيضها إلى التالي
مستوى الأولوية. الآن مهما كانت العملية تستخدم وقتها - كيف
الحوسبة باستمرار على المعالج أو العديد من المكالمات. بهذه الطريقة
يجب إعادة كتابة القاعدة 4 على النحو التالي:

القاعدة 4 : بعد أن تستهلك المهمة الوقت المخصص لها في قائمة الانتظار الحالية (بغض النظر عن عدد المرات التي تحرر فيها وحدة المعالجة المركزية) ، تتناقص أولوية هذه المهمة (تتحرك لأسفل في قائمة الانتظار).

لنلقِ نظرة على مثال:

"

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

تحسين MLFQ وغيرها من القضايا

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

على سبيل المثال ، تسمح لك معظم تطبيقات MLFQ بتعيين مختلف
فترات زمنية لقوائم مختلفة. طوابير ذات أولوية عالية عادة
يتم تعيين فترات زمنية قصيرة. تتكون قوائم الانتظار هذه من مهام تفاعلية ،
التبديل بين الذي هو حساس للغاية ويجب أن يستغرق 10 أو أقل
مللي ثانية. في المقابل ، تتكون قوائم الانتظار المنخفضة من المهام الطويلة باستخدام
وحدة المعالجة المركزية. وفي هذه الحالة ، فواصل زمنية طويلة تناسب بشكل جيد للغاية (100ms).

في هذا المثال ، توجد مهمتان عملتا في قائمة انتظار الأولوية العالية 20
مللي ، كسرها ويندوز لمدة 10ms. 40ms في قائمة الانتظار المتوسطة (نافذة في 20ms) وفي أولوية منخفضة
أصبحت نافذة قائمة الانتظار 40 مللي ثانية ، حيث أكملت المهام عملها.

تطبيق Solaris OS MLFQ هو فئة من برامج جدولة مشاركة الوقت.
يوفر المجدول مجموعة من الجداول التي تحدد بالضبط كيف ينبغي
تغيير أولوية العملية على مدى حياتها ، ما ينبغي أن يكون الحجم
النافذة المحددة وعدد المرات التي تحتاج فيها إلى رفع أولويات المهمة. مدير
يمكن للأنظمة التفاعل مع هذا الجدول وجعل المجدول يتصرف
بطريقة مختلفة. بشكل افتراضي ، هناك 60 قائمة انتظار تزايدي في هذا الجدول.
حجم النافذة من 20 مللي ثانية (أولوية عالية) إلى عدة مئات من مللي ثانية (أدنى أولوية) و
أيضا مع دفعة من جميع المهام مرة واحدة في الثانية.

لا يستخدم مخططي MLFQ الآخرين جدولًا أو أي جدول محدد
القواعد الموضحة في هذه المحاضرة ، على العكس من ذلك فإنها تحسب الأولويات باستخدام
الصيغ الرياضية. لذلك ، على سبيل المثال ، يستخدم المجدول في FreeBSD الصيغة لـ
حساب الأولوية الحالية للمهمة بناءً على مقدار العملية
وحدة المعالجة المركزية المستخدمة. بالإضافة إلى ذلك ، يتحلل استخدام وحدة المعالجة المركزية بمرور الوقت ، وهكذا
وبالتالي ، فإن الزيادة ذات الأولوية تحدث بشكل مختلف إلى حد ما عما هو موضح أعلاه. إنه كذلك
دعا خوارزميات الاضمحلال. منذ الإصدار 7.1 ، يستخدم FreeBSD جدولة ULE.

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

MLFQ: ملخص

وصفنا نهج تخطيط يسمى MLFQ. اسمه
وخلص في مبدأ العمل - لديه العديد من قوائم الانتظار ويستخدم التغذية المرتدة
لتحديد أولوية المهمة.
الشكل النهائي للقواعد سيكون على النحو التالي:

القاعدة 1 : إذا كانت الأولوية (أ)> الأولوية (ب) ، فستبدأ المهمة (أ) (ب)
القاعدة 2 : إذا كانت الأولوية (A) = الأولوية (B) ، يتم تشغيل A&B باستخدام RR
القاعدة 3 : عندما تدخل مهمة ما إلى النظام ، يتم وضعها في قائمة الأولويات القصوى.
القاعدة 4 : بعد أن تستهلك المهمة الوقت المخصص لها في قائمة الانتظار الحالية (بغض النظر عن عدد المرات التي حررت فيها وحدة المعالجة المركزية) ، تنخفض أولوية هذه المهمة (تتحرك لأسفل في قائمة الانتظار).
القاعدة 5 : بعد فترة معينة من S ، نقل جميع المهام في النظام إلى أعلى أولوية.

تعد MLFQ مثيرة للاهتمام للسبب التالي - بدلاً من المطالبة بمعرفة
طبيعة المهمة مسبقًا ، تقوم الخوارزمية بفحص السلوك السابق للمهمة وتحديد
الأولويات وفقًا لذلك. وبالتالي ، فهو يحاول الجلوس على كرسيين في وقت واحد - لتحقيق الإنتاجية للمهام الصغيرة (SJF ، STCF) وتشغيل
مهام تحميل وحدة المعالجة المركزية بأمانة لفترة طويلة . لذلك ، تستخدم العديد من الأنظمة ، بما في ذلك BSD ومشتقاتها ،
Solaris و Windows و Mac ، شكلاً من أشكال خوارزمية
MLFQ كجدول زمني.

أنظمة التشغيل: ثلاث قطع سهلة. الجزء 5: التخطيط: قائمة انتظار التعليقات متعددة المستويات (ترجمة)