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

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

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

أجزاء أخرى:

يمكنك أيضًا التحقق من قناتي على برقية =)

مقدمة إلى المجدول

جوهر المشكلة: كيفية تطوير سياسة الجدولة
كيف ينبغي تصميم أطر سياسة الجدولة الأساسية؟ ما ينبغي أن تكون الافتراضات الرئيسية؟ ما هي المقاييس المهمة؟ ما هي التقنيات الأساسية التي استخدمت في أنظمة الحوسبة المبكرة؟

افتراضات عبء العمل

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

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

يتم تنفيذ كل مهمة لنفس القدر من الوقت،
يتم تعيين كافة المهام في وقت واحد،
المهمة المعينة تعمل حتى الانتهاء منها،
جميع المهام تستخدم وحدة المعالجة المركزية فقط،
وقت تشغيل كل مهمة معروف.

مقاييس الجدولة

بالإضافة إلى بعض الافتراضات حول الحمل، هناك حاجة إلى أداة أخرى لمقارنة سياسات الجدولة المختلفة: مقاييس الجدولة. المقياس هو مجرد مقياس لشيء ما. هناك عدد من المقاييس التي يمكن استخدامها لمقارنة المجدولين.

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

Tturnaround=Tالاكتمال−الوصول

وبما أننا افترضنا أن جميع المهام وصلت في نفس الوقت، فإن Ta=0 وبالتالي Tt=Tc. ومن الطبيعي أن تتغير هذه القيمة عندما نغير الافتراضات المذكورة أعلاه.

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

أول ما يدخل أولاً يخرج أولاً (FIFO)

الخوارزمية الأساسية التي يمكننا تنفيذها تسمى FIFO أو من يأتي أولاً (يدخل) يخدم أولاً (يخرج). تتمتع هذه الخوارزمية بالعديد من المزايا: فهي سهلة التنفيذ للغاية وتتناسب مع جميع افتراضاتنا وتقوم بالمهمة بشكل جيد.

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

وبحساب القيم - 10+20+30 والقسمة على 3، نحصل على متوسط وقت تنفيذ البرنامج يساوي 20 ثانية.
الآن دعونا نحاول تغيير افتراضاتنا. على وجه الخصوص، الافتراض 1، وبالتالي لن نفترض بعد الآن أن كل مهمة تستغرق نفس القدر من الوقت للتنفيذ. كيف سيتم أداء FIFO هذه المرة؟

كما اتضح، فإن أوقات تنفيذ المهام المختلفة لها تأثير سلبي للغاية على إنتاجية خوارزمية FIFO. لنفترض أن المهمة A ستستغرق 100 ثانية لإكمالها، في حين أن المهمة B وC ستستغرق 10 ثوانٍ لكل منهما.

وكما يتبين من الشكل فإن متوسط الزمن للنظام سيكون (100+110+120)/3=110. ويسمى هذا التأثير تأثير القافلة، عندما يصطف بعض المستهلكين لمورد ما على المدى القصير بعد مستهلك ثقيل. إنه مثل الطابور في متجر البقالة عندما يكون هناك عميل أمامك بعربة ممتلئة. أفضل حل للمشكلة هو محاولة تغيير ماكينة تسجيل المدفوعات النقدية أو الاسترخاء والتنفس بعمق.

أقصر وظيفة أولا

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

في هذا المثال، ستكون نتيجة تشغيل نفس العمليات تحسنًا في متوسط وقت تنفيذ البرنامج وسيكون مساويًا لـ 50 بدلاً من 110، وهو أفضل مرتين تقريبًا.

وبالتالي، بالنسبة للافتراض بأن جميع المهام تصل في نفس الوقت، يبدو أن خوارزمية SJF هي الخوارزمية الأكثر مثالية. ومع ذلك، فإن افتراضاتنا لا تزال غير واقعية. هذه المرة نغير الافتراض 2 وهذه المرة نتخيل أن المهام يمكن أن تكون موجودة في أي وقت، وليس كلها في نفس الوقت. ما هي المشاكل التي يمكن أن يؤدي إليها هذا؟

لنتخيل أن المهمة A (100c) تصل أولاً وتبدأ في التنفيذ. عند t=10، تصل المهمتان B وC، وتستغرق كل منهما 10 ثوانٍ. لذا فإن متوسط وقت التنفيذ هو (100+(110-10)+(120-10))3 = 103. ما الذي يمكن أن يفعله المجدول لتحسين ذلك؟

أقصر وقت للاكتمال أولاً (STCF)

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

ستكون نتيجة هذا المخطط هي النتيجة التالية: ((120-0)+(20-10)+(30-10))/3=50. وبالتالي، يصبح مثل هذا المجدول أكثر مثالية لمهامنا.

وقت الاستجابة المتري

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

يتم حساب زمن الاستجابة على النحو التالي:

Tresponse=Tfirstrun−Tarrival

وهكذا، في المثال السابق، سيكون زمن الاستجابة: A=0، B=0، C=10 (abg=3,33).

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

إذن نحن نواجه مشكلة أخرى - كيف يمكننا بناء برنامج جدولة حساس لوقت الاستجابة؟

جولة روبن

تم تطوير خوارزمية لحل هذه المشكلة جولة روبن (ص ر). الفكرة الأساسية بسيطة للغاية: بدلاً من تشغيل المهام حتى اكتمالها، سنقوم بتشغيل المهمة لفترة معينة من الوقت (تسمى شريحة زمنية) ثم ننتقل إلى مهمة أخرى من قائمة الانتظار. تكرر الخوارزمية عملها حتى تكتمل جميع المهام. في هذه الحالة، يجب أن يكون وقت تشغيل البرنامج مضاعفًا للوقت الذي سيقطع بعده المؤقت العملية. على سبيل المثال، إذا قام مؤقت بمقاطعة عملية ما كل x=10ms، فيجب أن يكون حجم نافذة تنفيذ العملية من مضاعفات 10 وأن يكون 10,20 أو x*10.

دعونا نلقي نظرة على مثال: تصل مهام ABC في وقت واحد إلى النظام ويريد كل منها تشغيلها لمدة 5 ثوانٍ. ستكمل خوارزمية SJF كل مهمة قبل بدء مهمة أخرى. في المقابل، فإن خوارزمية RR مع نافذة الإطلاق = 1s سوف تمر بالمهام على النحو التالي (الشكل 4.3):

(SJF مرة أخرى (سيء لوقت الاستجابة)

(Round Robin (جيد لوقت الاستجابة)

متوسط وقت الاستجابة لخوارزمية RR هو (0+1+2)/3=1، بينما لخوارزمية SJF (0+5+10)/3=5.

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

يعد RR أداة جدولة رائعة إذا كنا نتحدث فقط عن مقياس وقت الاستجابة. ولكن كيف سيتصرف مقياس وقت إنجاز المهمة مع هذه الخوارزمية؟ خذ بعين الاعتبار المثال أعلاه، عندما يكون وقت التشغيل لـ A وB وC = 5s ويصل في نفس الوقت. ستنتهي المهمة A عند 13، وB عند 14، وC عند 15 ثانية، وسيكون متوسط وقت الاستجابة 14 ثانية. وبالتالي، فإن RR هي أسوأ خوارزمية لمقياس الدوران.

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

وبالتالي، لدينا العديد من الخوارزميات المتناقضة وفي الوقت نفسه لا يزال هناك العديد من الافتراضات المتبقية - أن وقت المهمة معروف وأن المهمة تستخدم وحدة المعالجة المركزية فقط.

المزج مع الإدخال/الإخراج

أولاً، دعونا نزيل الافتراض 4 بأن العملية تستخدم وحدة المعالجة المركزية (CPU) فقط؛ وبطبيعة الحال، ليس هذا هو الحال ويمكن للعمليات الوصول إلى معدات أخرى.

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

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

في هذا المثال سوف نستخدم جدولة STCF. كيف سيتصرف المجدول إذا تم إطلاق عملية مثل A عليه؟ سيقوم بما يلي: أولاً سيعمل على حل العملية "أ" بالكامل، ثم العملية "ب".

يتمثل النهج التقليدي لحل هذه المشكلة في التعامل مع كل مهمة فرعية مدتها 10 مللي ثانية من العملية A كمهمة منفصلة. وبالتالي، عند البدء بخوارزمية STJF، يكون الاختيار بين مهمة مدتها 50 مللي ثانية ومهمة مدتها 10 مللي ثانية أمرًا واضحًا. بعد ذلك، عند اكتمال المهمة الفرعية A، سيتم إطلاق العملية B والإدخال/الإخراج. بعد اكتمال عملية الإدخال/الإخراج، سيكون من المعتاد بدء العملية A التي تستغرق 10 مللي ثانية بدلاً من العملية B. وبهذه الطريقة، من الممكن تنفيذ التداخل، حيث يتم استخدام وحدة المعالجة المركزية بواسطة عملية أخرى بينما تنتظر العملية الأولى عملية الإدخال/الإخراج. الإدخال/الإخراج. ونتيجة لذلك، يتم استخدام النظام بشكل أفضل - في اللحظة التي تنتظر فيها العمليات التفاعلية الإدخال/الإخراج، يمكن تنفيذ عمليات أخرى على المعالج.

أوراكل لم تعد موجودة

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

مجموع

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

المصدر: www.habr.com

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