جدولة وحدة المعالجة المركزية Algorithms in Operaتينج سيستمز
ناثانيال بروكس
⚡ ملخص ذكي
تحدد جدولة وحدة المعالجة المركزية العملية الجاهزة التي سيقوم نظام التشغيل بتشغيلها تالياً، احتفظping المعالج مشغول ويعمل على تحسين الأداء من خلال خوارزميات مثل First Come First Serve و Shortest Job First و Priority و Round Robin.
ما هي جدولة وحدة المعالجة المركزية؟
جدولة وحدة المعالجة المركزية هي عملية تحديد العملية التي ستستحوذ على وحدة المعالجة المركزية للتنفيذ بينما تكون عملية أخرى في حالة انتظار. تتمثل المهمة الرئيسية لجدولة وحدة المعالجة المركزية في ضمان اختيار نظام التشغيل لعملية واحدة على الأقل من العمليات المتاحة في قائمة الانتظار الجاهزة للتنفيذ، وذلك عندما تكون وحدة المعالجة المركزية في وضع الخمول. تتم عملية الاختيار بواسطة مُجدول وحدة المعالجة المركزية، الذي يختار إحدى العمليات الجاهزة للتنفيذ في الذاكرة.
أنواع جدولة وحدة المعالجة المركزية
فيما يلي نوعان من طرق الجدولة:
جدولة وقائية
في الجدولة الاستباقية، تُحدد أولويات المهام في الغالب. أحيانًا يكون من المهم تشغيل مهمة ذات أولوية أعلى قبل مهمة أخرى ذات أولوية أقل، حتى لو كانت المهمة ذات الأولوية الأقل لا تزال قيد التشغيل. تبقى المهمة ذات الأولوية الأقل قيد التشغيل لفترة من الوقت، ثم تستأنف عملها عند انتهاء المهمة ذات الأولوية الأعلى من تنفيذها.
جدولة غير استباقية
في هذا النوع من جدولة المهام، تُخصص وحدة المعالجة المركزية لعملية محددة. تقوم العملية التي تشغل وحدة المعالجة المركزية بتحريرها إما عن طريق تغيير سياقها أو إنهاء عملها. وهي الطريقة الوحيدة التي يمكن استخدامها على مختلف منصات الأجهزة، لأنها لا تتطلب أجهزة خاصة (مثل المؤقت) كما هو الحال في جدولة المهام الاستباقية.
متى يكون الجدولة استباقية أو غير استباقية؟
لتحديد ما إذا كانت الجدولة استباقية أم غير استباقية، ضع في اعتبارك هذه المعايير الأربعة:
- تتحول العملية من حالة التشغيل إلى حالة الانتظار.
- تنتقل عملية محددة من حالة التشغيل إلى حالة الجاهزية.
- تنتقل عملية محددة من حالة الانتظار إلى حالة الجاهزية.
- تنتهي العملية من تنفيذها وتتوقف.
إذا انطبق الشرطان 1 و4 فقط، يُطلق على الجدولة اسم الجدولة غير الاستباقية. أما جميع حالات الجدولة الأخرى فهي استباقية.
مصطلحات مهمة في جدولة وحدة المعالجة المركزية
- وقت الاندفاع / وقت التنفيذ: الوقت اللازم لإتمام عملية ما. ويُسمى أيضاً وقت التشغيل.
- وقت الوصول: الوقت الذي تدخل فيه العملية في حالة الجاهزية.
- وقت الانتهاء: الوقت الذي تكتمل فيه العملية وتخرج من النظام.
- البرمجة المتعددة: عدد من البرامج التي يمكن أن تكون موجودة في الذاكرة في نفس الوقت.
- وظائف: نوع من البرامج بدون أي نوع من تفاعل المستخدم.
- مستخدم: نوع من البرامج التي تتضمن تفاعل المستخدم.
- عملية: المرجع المستخدم لكل من الوظيفة والمستخدم.
- دورة انفجار CPU / IO: يُحدد هذا الأسلوب تنفيذ العمليات، الذي يتناوب بين نشاط وحدة المعالجة المركزية ونشاط الإدخال/الإخراج. وعادةً ما تكون أوقات وحدة المعالجة المركزية أقصر من أوقات الإدخال/الإخراج.
معايير جدولة وحدة المعالجة المركزية
تحاول خوارزمية جدولة وحدة المعالجة المركزية تعظيم وتقليل ما يلي:
تعظيم
استخدام وحدة المعالجة المركزية: يُعدّ استهلاك وحدة المعالجة المركزية المهمة الرئيسية التي يجب على نظام التشغيل من خلالها ضمان بقاء وحدة المعالجة المركزية مشغولة قدر الإمكان. ويتراوح هذا الاستهلاك بين 0 و100%. أما بالنسبة لأنظمة التشغيل في الوقت الحقيقي (RTOS)، فقد يتراوح بين 40% للأنظمة منخفضة المستوى و90% للأنظمة عالية المستوى.
الإنتاجية: يُعرف عدد العمليات التي تُنهي تنفيذها في وحدة زمنية واحدة باسم الإنتاجية. لذا، عندما يكون المعالج مشغولاً بتنفيذ عملية ما، يتم إنجاز عمل، ويُطلق على العمل المنجز في وحدة زمنية واحدة اسم الإنتاجية.
تقليل
وقت الانتظار: وقت الانتظار هو مقدار الوقت الذي يجب أن تنتظره عملية معينة في قائمة الانتظار الجاهزة.
وقت الاستجابة: وهو مقدار الوقت المستغرق من وقت تقديم الطلب حتى يتم إنتاج أول رد.
الفترة الزمنية: زمن الاستجابة هو مقدار الوقت المستغرق لتنفيذ عملية معينة. وهو إجمالي الوقت الذي يقضيه البرنامج في انتظار الوصول إلى الذاكرة، والانتظار في قائمة الانتظار، والتنفيذ على وحدة المعالجة المركزية. الفترة الزمنية بين وقت إرسال العملية ووقت اكتمالها هي زمن الاستجابة.
الفاصل الزمني
انقطاع المؤقت هو أسلوب يرتبط ارتباطًا وثيقًا بالشفعة. عندما تحصل عملية معينة على تخصيص وحدة المعالجة المركزية، فقد يتم ضبط المؤقت على فاصل زمني محدد. يفرض كل من انقطاع المؤقت والإجراء الاستباقي على العملية إعادة وحدة المعالجة المركزية قبل اكتمال انفجار وحدة المعالجة المركزية الخاصة بها.
تستخدم معظم أنظمة التشغيل متعددة البرامج شكلاً من أشكال المؤقت لمنع عملية ما من شل النظام إلى الأبد.
ما هو المرسل؟
المُوَزِّع هو وحدة تُتيح التحكم في وحدة المعالجة المركزية للعملية. يجب أن يكون المُوَزِّع سريعًا ليتمكن من العمل عند كل تبديل سياق. زمن استجابة الإرسال هو مقدار الوقت الذي يحتاجه مُجدوِل وحدة المعالجة المركزية لإيقاف عملية وبدء أخرى.
الوظائف التي يؤديها الموزع:
- تبديل السياق.
- الانتقال إلى وضع المستخدم.
- الانتقال إلى الموقع الصحيح في البرنامج الذي تم تحميله حديثا.
أنواع جدولة وحدة المعالجة المركزية Algorithms
هناك بشكل رئيسي ستة أنواع من خوارزميات جدولة العمليات:
- First Come First Serve (FCFS) أولاً يأتي أولاً
- جدولة أقصر مهمة أولاً (SJF).
- أقصر الوقت المتبقي
- جدولة الأولوية
- جدولة روبن الجولة
- جدولة طوابير متعددة المستويات
جدولة Algorithms
الخدمة بأسبقية الوصول
FCFS تعني الخدمة بأسبقية الوصولإنها أسهل وأبسط خوارزمية لجدولة وحدة المعالجة المركزية. في هذا النوع من الخوارزميات، يحصل البرنامج الذي يطلب وحدة المعالجة المركزية على تخصيصها أولاً. ويمكن إدارة هذه الطريقة باستخدام قائمة انتظار FIFO.
عندما تدخل عملية ما إلى قائمة الانتظار، يتم ربط وحدة التحكم الخاصة بها (PCB) بنهاية القائمة. لذا، عندما يصبح المعالج المركزي (CPU) متاحًا، يجب تخصيصه للعملية الموجودة في بداية القائمة.
خصائص طريقة FCFS
- إنها خوارزمية جدولة غير استباقية.
- يتم تنفيذ المهام دائمًا على أساس أسبقية الحضور.
- إنه سهل التنفيذ والاستخدام.
- ومع ذلك، فإن هذا الأسلوب ضعيف في الأداء، كما أن وقت الانتظار العام مرتفع جدًا.
أقصر الوقت المتبقي
يُعرف اختصار SRT اختصارًا لـ Shortest Remaining Time، ويُطلق عليه أيضًا اسم جدولة SJF الاستباقية. في هذه الطريقة، تُخصص العملية للمهمة الأقرب إلى الاكتمال، مما يمنع عمليةً جديدةً جاهزةً من تأخير إتمام عمليةٍ أقدم.
خصائص طريقة جدولة SRT
- تُطبق هذه الطريقة في الغالب في بيئات المعالجة الدفعية حيث يجب إعطاء الأولوية للوظائف القصيرة.
- هذه ليست طريقة مثالية للتنفيذ في نظام مشترك حيث يكون وقت وحدة المعالجة المركزية المطلوب غير معروف.
- ترتبط كل عملية بطول فترة استخدام وحدة المعالجة المركزية التالية، لذلك يستخدم نظام التشغيل هذه الأطوال لجدولة العملية بأقصر وقت ممكن.
الجدولة على أساس الأولوية
جدولة الأولوية هي طريقة لجدولة العمليات بناءً على الأولوية. في هذه الطريقة، يختار المجدول المهام التي سيعمل عليها وفقًا لأولويتها.
تساعد جدولة الأولويات نظام التشغيل على تحديد الأولويات. تُنفذ العمليات ذات الأولوية الأعلى أولاً، بينما تُنفذ المهام ذات الأولويات المتساوية بالتناوب أو وفقًا لأسلوب "الأسبقية لمن يأتي أولاً". ويمكن تحديد الأولوية بناءً على متطلبات الذاكرة والوقت وعوامل أخرى.
جدولة جولة روبن
جولة روبن تُعدّ هذه الخوارزمية من أقدم وأبسط خوارزميات الجدولة. اسمها مشتق من مبدأ التناوب الدوري، حيث يحصل كل شخص على حصة متساوية من شيء ما بالتناوب. تُستخدم هذه الخوارزمية بشكل أساسي لجدولة المهام في الأنظمة متعددة المهام، وتساعد على ضمان تنفيذ العمليات بسلاسة ودون انقطاع.
خصائص جدولة جولة روبن
- نظام التناوب الدوري هو نموذج هجين يعتمد على التوقيت.
- ينبغي أن تكون الفترة الزمنية المخصصة لمعالجة مهمة معينة قصيرة قدر الإمكان. ومع ذلك، قد تختلف هذه الفترة باختلاف العمليات.
- يتصرف كنظام مشاركة الوقت الذي يستجيب لكل عملية ضمن حد زمني محدد.
أقصر وظيفة أولا
خوارزمية SJF (أقصر مهمة أولاً) هي خوارزمية جدولة تُختار فيها العملية ذات أقصر وقت تنفيذ لتنفيذها تالياً. يمكن أن تكون هذه الطريقة استباقية أو غير استباقية. وهي تُقلل بشكل ملحوظ متوسط وقت انتظار العمليات الأخرى التي تنتظر التنفيذ.
خصائص جدولة SJF
- ترتبط كل مهمة بوحدة زمنية لإنجازها.
- في هذه الطريقة، عندما تكون وحدة المعالجة المركزية متاحة، يتم تنفيذ العملية أو المهمة التالية ذات أقصر وقت إنجاز أولاً.
- يتم تطبيق ذلك بسياسة غير استباقية.
- تُعد هذه الخوارزمية مفيدة للمعالجة الدفعية، حيث لا يكون انتظار اكتمال المهام أمرًا بالغ الأهمية.
- فهو يحسن إنتاجية العمل من خلال تنفيذ المهام الأقصر أولاً، والتي يكون وقت إنجازها أقصر في الغالب.
جدولة قوائم الانتظار متعددة المستويات
تقسم هذه الخوارزمية قائمة الانتظار الجاهزة إلى عدة قوائم انتظار منفصلة. في هذه الطريقة، تُخصص العمليات لقائمة انتظار بناءً على خاصية محددة للعملية، مثل أولوية العملية، وحجم الذاكرة، وما إلى ذلك.
ومع ذلك، فإن هذه ليست خوارزمية جدولة مستقلة، لأنها تحتاج إلى استخدام أنواع أخرى من الخوارزميات من أجل جدولة المهام.
خصائص جدولة قوائم الانتظار متعددة المستويات
- ينبغي الحفاظ على قوائم انتظار متعددة للعمليات ذات الخصائص المشتركة.
- قد يكون لكل طابور خوارزمية جدولة منفصلة خاصة به.
- يتم تحديد الأولويات لكل طابور.
الغرض من خوارزمية الجدولة
فيما يلي أسباب استخدام خوارزمية الجدولة:
- تستخدم وحدة المعالجة المركزية الجدولة لتحسين كفاءتها.
- يساعدك ذلك على تخصيص الموارد بين العمليات المتنافسة.
- يمكن تحقيق أقصى استفادة من وحدة المعالجة المركزية من خلال البرمجة المتعددة.
- يتم الاحتفاظ بالعمليات التي سيتم تنفيذها في قائمة الانتظار الجاهزة.
