خوارزميات جدولة وحدة المعالجة المركزية في أنظمة التشغيل

ما هي جدولة وحدة المعالجة المركزية؟

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

أنواع جدولة وحدة المعالجة المركزية

فيما يلي نوعان من أساليب الجدولة:

أنواع جدولة وحدة المعالجة المركزية

جدولة وقائية

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

جدولة غير استباقية

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

متى تكون الجدولة وقائية أم غير وقائية؟

لتحديد ما إذا كانت الجدولة وقائية أم غير وقائية، ضع في اعتبارك هذه المعلمات الأربع:

  1. تتحول العملية من حالة التشغيل إلى حالة الانتظار.
  2. تقوم عملية محددة بالتبديل من حالة التشغيل إلى حالة الاستعداد.
  3. تتحول عملية محددة من حالة الانتظار إلى حالة الاستعداد.
  4. انتهت العملية من تنفيذها وإنهائها.

يتم تطبيق الشرطين 1 و4 فقط، وتسمى الجدولة غير وقائية.

جميع الجدولة الأخرى وقائية.

مصطلحات مهمة لجدولة وحدة المعالجة المركزية

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

معايير جدولة وحدة المعالجة المركزية

تحاول خوارزمية جدولة وحدة المعالجة المركزية زيادة حجم المتابعة وتقليلهاwing:

معايير جدولة وحدة المعالجة المركزية

تعظيم

استخدام وحدة المعالجة المركزية:يعد استخدام وحدة المعالجة المركزية المهمة الرئيسية التي يحتاج فيها نظام التشغيل إلى التأكد من أن وحدة المعالجة المركزية تظل مشغولة قدر الإمكان. يمكن أن تتراوح من 0 إلى 100 بالمائة. ومع ذلك، بالنسبة لنظام RTOS، يمكن أن تتراوح بين 40 بالمائة للنظام منخفض المستوى و90 بالمائة للنظام عالي المستوى.

الإنتاجية: يُعرف عدد العمليات التي تنتهي من تنفيذها لكل وحدة زمنية بالإنتاجية. لذلك، عندما تكون وحدة المعالجة المركزية مشغولة بتنفيذ العملية، في ذلك الوقت، يتم إنجاز العمل، ويسمى العمل المكتمل لكل وحدة زمنية بالإنتاجية.

تقليل

وقت الانتظار: وقت الانتظار هو المبلغ الذي تحتاج عملية معينة إلى انتظاره في قائمة الانتظار الجاهزة.

وقت الاستجابة: وهو مقدار الوقت الذي تم فيه تقديم الطلب حتى يتم إصدار الرد الأول.

الفترة الزمنية: وقت الاستجابة هو مقدار الوقت اللازم لتنفيذ عملية معينة. إنه حساب إجمالي الوقت المستغرق في انتظار الوصول إلى الذاكرة، والانتظار في قائمة الانتظار، والتنفيذ على وحدة المعالجة المركزية. الفترة بين وقت تقديم العملية ووقت الانتهاء هي وقت الاستجابة.

الفاصل الزمني

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

تستخدم معظم أنظمة التشغيل متعددة البرامج شكلاً من أشكال المؤقت لمنع العملية من تقييد النظام إلى الأبد.

ما هو المرسل؟

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

الوظائف التي يؤديها المرسل:

  • تبديل السياق
  • التبديل إلى وضع المستخدم
  • الانتقال إلى الموقع الصحيح في البرنامج الذي تم تحميله حديثا.

أنواع خوارزمية جدولة وحدة المعالجة المركزية

هناك بشكل رئيسي ستة أنواع من خوارزميات جدولة العمليات

  1. First Come First Serve (FCFS) أولاً يأتي أولاً
  2. جدولة أقصر مهمة أولاً (SJF).
  3. أقصر الوقت المتبقي
  4. جدولة الأولوية
  5. جدولة روبن الجولة
  6. جدولة طوابير متعددة المستويات
خوارزميات الجدولة
خوارزميات الجدولة

الخدمة بأسبقية الوصول

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

عندما تدخل العملية إلى قائمة الانتظار الجاهزة، يتم ربط PCB (كتلة التحكم في العملية) الخاصة بها بذيل قائمة الانتظار. لذلك، عندما تصبح وحدة المعالجة المركزية مجانية، يجب تعيينها للعملية في بداية قائمة الانتظار.

خصائص طريقة FCFS

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

أقصر الوقت المتبقي

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

خصائص طريقة جدولة SRT

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

الجدولة على أساس الأولوية

جدولة الأولوية هي طريقة لجدولة العمليات على أساس الأولوية. في هذه الطريقة، يقوم المجدول باختيار المهام للعمل حسب الأولوية.

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

جدولة جولة روبن

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

خصائص جدولة جولة روبن

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

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

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

خصائص جدولة SJF

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

جدولة قوائم الانتظار متعددة المستويات

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

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

خصائص جدولة قوائم الانتظار متعددة المستويات

  • يجب الاحتفاظ بقوائم انتظار متعددة للعمليات ذات بعض الخصائص.
  • قد يكون لكل قائمة انتظار خوارزميات جدولة منفصلة.
  • يتم إعطاء الأولويات لكل قائمة انتظار.

الغرض من خوارزمية الجدولة

فيما يلي أسباب استخدام خوارزمية الجدولة:

  • تستخدم وحدة المعالجة المركزية الجدولة لتحسين كفاءتها.
  • يساعدك على تخصيص الموارد بين العمليات المتنافسة.
  • يمكن الحصول على أقصى استفادة من وحدة المعالجة المركزية من خلال البرمجة المتعددة.
  • العمليات التي سيتم تنفيذها موجودة في قائمة الانتظار الجاهزة.

نبذة عامة

  • جدولة وحدة المعالجة المركزية هي عملية تحديد العملية التي ستمتلك وحدة المعالجة المركزية للتنفيذ أثناء انتظار عملية أخرى.
  • في الجدولة الوقائية، يتم تعيين المهام في الغالب وفقًا لأولوياتها.
  • في طريقة الجدولة غير الوقائية، تم تخصيص وحدة المعالجة المركزية لعملية محددة.
  • وقت الاندفاع هو الوقت اللازم للعملية لإكمال التنفيذ. ويسمى أيضًا وقت التشغيل.
  • يعد استخدام وحدة المعالجة المركزية المهمة الرئيسية التي يحتاج نظام التشغيل فيها إلى التأكد من بقاء وحدة المعالجة المركزية مشغولة قدر الإمكان.
  • يُعرف عدد العمليات التي تنتهي من تنفيذها لكل وحدة زمنية بالإنتاجية.
  • وقت الانتظار هو المبلغ الذي تحتاج عملية معينة إلى انتظاره في قائمة الانتظار الجاهزة.
  • هو مقدار الوقت الذي تم فيه تقديم الطلب حتى يتم إصدار الرد الأول.
  • وقت الاستجابة هو مقدار الوقت اللازم لتنفيذ عملية معينة.
  • انقطاع المؤقت هو أسلوب يرتبط ارتباطًا وثيقًا بالشفعة.
  • المرسل هو وحدة توفر التحكم في وحدة المعالجة المركزية للعملية.
  • ستة أنواع من خوارزميات جدولة العمليات هي: من يأتي أولاً يخدم أولاً (FCFS)، 2) جدولة أقصر مهمة أولاً (SJF)، 3) أقصر وقت متبقي، 4) جدولة الأولوية، 5) جدولة جولة روبن، 6) جدولة قائمة الانتظار متعددة المستويات .
  • في مجلة طريقة من يأتي أولاً يخدم أولاً، العملية التي تطلب وحدة المعالجة المركزية تحصل على تخصيص وحدة المعالجة المركزية أولاً.
  • في أقصر وقت متبقي، سيتم تخصيص العملية للمهمة الأقرب إلى اكتمالها.
  • في جدولة الأولويات، يقوم المجدول بتحديد المهام للعمل حسب الأولوية.
  • جدولة جولة روبن يعمل على مبدأ حصول كل شخص بدوره على حصة متساوية من شيء ما.
  • في أقصر مهمة أولاً، يجب تحديد أقصر وقت للتنفيذ للتنفيذ بعد ذلك.
  • تقوم طريقة الجدولة متعددة المستويات بفصل قائمة الانتظار الجاهزة إلى قوائم انتظار منفصلة مختلفة. في هذه الطريقة، يتم تعيين العمليات إلى قائمة انتظار بناءً على خاصية معينة.
  • تستخدم وحدة المعالجة المركزية الجدولة لتحسين كفاءتها.