CS330 - أنظمة التشغيل
خوارزميات الجدولة، مقاييس الأداء، والتحليل
جدولة المعالج هي أساس أنظمة التشغيل متعددة البرمجة. بتبديل المعالج بين العمليات، يمكن لنظام التشغيل جعل الكمبيوتر أكثر إنتاجية.
تنفيذ العملية يتكون من دورة من تنفيذ المعالج وانتظار الإدخال/الإخراج:
تنفيذ العملية يبدأ بانفجار معالج، يتبعه انفجار إدخال/إخراج، ثم انفجار معالج آخر، وهكذا.
جدول المعالج يختار من بين العمليات في قائمة الانتظار الجاهزة ويخصص نواة معالج لواحدة منها.
الموزع يعطي التحكم في المعالج للعملية التي اختارها الجدول. هذا يتضمن:
كمون التوزيع: الوقت الذي يستغرقه الموزع لإيقاف عملية وبدء تشغيل أخرى.
إبقاء المعالج مشغولاً قدر الإمكان. في الأنظمة الحقيقية، يجب أن يتراوح من ٤٠٪ (تحميل خفيف) إلى ٩٠٪ (تحميل ثقيل).
عدد العمليات التي تكمل التنفيذ لكل وحدة زمنية. الأكبر هو الأفضل.
مقدار الوقت لتنفيذ عملية معينة. مجموع الفترات التي تقضيها في الانتظار، قائمة الانتظار الجاهزة، التنفيذ، وأداء الإدخال/الإخراج.
مقدار الوقت الذي قضته العملية في الانتظار في قائمة الانتظار الجاهزة.
الوقت من تقديم الطلب حتى ظهور أول استجابة. مهم للأنظمة التفاعلية.
| المعيار | هدف التحسين |
|---|---|
| استغلال المعالج | تعظيم |
| الإنتاجية | تعظيم |
| زمن الإنجاز | تقليل |
| زمن الانتظار | تقليل |
| زمن الاستجابة | تقليل |
قرارات جدولة المعالج قد تحدث عندما:
تقريبًا كل أنظمة التشغيل الحديثة بما فيها ويندوز، ماك أو إس، لينكس، ويونكس تستخدم خوارزميات جدولة استباقية.
| العملية | وقت الانفجار |
|---|---|
| P1 | ٢٤ |
| P2 | ٣ |
| P3 | ٣ |
ترتيب الوصول: P1, P2, P3
| العملية | زمن الانتظار | زمن الإنجاز |
|---|---|---|
| P1 | ٠ | ٢٤ |
| P2 | ٢٤ | ٢٧ |
| P3 | ٢٧ | ٣٠ |
| المتوسط | ١٧ | ٢٧ |
العمليات القصيرة خلف عملية طويلة. كل العمليات الأخرى تنتظر عملية كبيرة واحدة لتترك المعالج. هذا التأثير يؤدي إلى انخفاض استغلال المعالج والأجهزة.
إذا تغير ترتيب الوصول إلى P2, P3, P1:
بمجرد إعطاء المعالج لعملية، لا يمكن استباقها حتى تكمل انفجار المعالج الخاص بها
إذا وصلت عملية جديدة بطول انفجار معالج أقل من الوقت المتبقي للعملية الحالية، يتم استباقها. تُعرف أيضًا بأقصر وقت متبقي أولاً
| العملية | وقت الوصول | وقت الانفجار |
|---|---|---|
| P1 | ٠ | ٨ |
| P2 | ١ | ٤ |
| P3 | ٢ | ٩ |
| P4 | ٣ | ٥ |
متوسط زمن الانتظار = [(١٠-١) + (١-١) + (١٧-٢) + (٥-٣)] / ٤ = ٢٦/٤ = ٦.٥
| العملية | وقت الانفجار | الأولوية |
|---|---|---|
| P1 | ١٠ | ٣ |
| P2 | ١ | ١ |
| P3 | ٢ | ٤ |
| P4 | ١ | ٥ |
| P5 | ٥ | ٢ |
العمليات ذات الأولوية المنخفضة قد لا تُنفذ أبدًا.
مع مرور الوقت، زيادة أولوية العملية.
| العملية | وقت الانفجار |
|---|---|
| P1 | ٢٤ |
| P2 | ٣ |
| P3 | ٣ |
| العملية | زمن الانتظار | زمن الإنجاز |
|---|---|---|
| P1 | ٦ | ٣٠ |
| P2 | ٤ | ٧ |
| P3 | ٧ | ١٠ |
| المتوسط | ٥.٦٦ | ١٥.٦٦ |
قائمة الانتظار الجاهزة مقسمة إلى قوائم منفصلة بناءً على خصائص العملية.
تسمح للعملية بالتنقل بين القوائم. الفكرة هي فصل العمليات وفقًا لخصائص انفجارات المعالج الخاصة بها.
| الخوارزمية | استباقية | المزايا | العيوب | الأفضل لـ |
|---|---|---|---|---|
| FCFS | لا | بسيطة، عادلة | تأثير القافلة، زمن انتظار سيئ | أنظمة الدفعات |
| SJF | كلاهما | أفضل متوسط زمن انتظار | تجويع، تحتاج معرفة وقت الانفجار | عند معرفة أوقات الانفجار |
| Priority | كلاهما | المهام المهمة أولاً | تجويع | أنظمة الزمن الحقيقي |
| Round Robin | نعم | زمن استجابة جيد، عادلة | زمن إنجاز أعلى | أنظمة المشاركة الزمنية |
تأمل مجموعة العمليات التالية بوقت وصول ٠:
| العملية | وقت الانفجار | الأولوية |
|---|---|---|
| P1 | ٢ | ٢ |
| P2 | ١ | ١ |
| P3 | ٨ | ٤ |
| P4 | ٤ | ٢ |
| P5 | ٥ | ٣ |
الترتيب: P2 → P1 → P4 → P5 → P3
| العملية | زمن الانتظار | زمن الإنجاز |
|---|---|---|
| P1 | ١ | ٣ |
| P2 | ٠ | ١ |
| P3 | ١٢ | ٢٠ |
| P4 | ٣ | ٧ |
| P5 | ٧ | ١٢ |
الترتيب: P1(٢) → P2(١) → P3(٢) → P4(٢) → P5(٢) → P3(٢) → P4(٢) → P5(٢) → P3(٢) → P5(١) → P3(٢)
| العملية | زمن الانتظار | زمن الإنجاز |
|---|---|---|
| P1 | ٠ | ٢ |
| P2 | ٢ | ٣ |
| P3 | ١٢ | ٢٠ |
| P4 | ٩ | ١٣ |
| P5 | ١٣ | ١٨ |
الترتيب: P2 → P1 → P4 → P5 → P3
| العملية | زمن الانتظار | زمن الإنجاز |
|---|---|---|
| P1 | ١ | ٣ |
| P2 | ٠ | ١ |
| P3 | ١٢ | ٢٠ |
| P4 | ٣ | ٧ |
| P5 | ٧ | ١٢ |
س١. أي خوارزمية جدولة غير استباقية؟
س٢. أي خوارزمية جدولة تعطي أفضل متوسط زمن استجابة؟
س٣. إذا كان الكم الزمني صغيرًا جدًا في جدولة RR:
س٤. أي مشكلة مرتبطة بجدولة الأولويات؟
س٥. جدولة SJF مثالية لأنها تعطي:
س٦. عرّف زمن الإنجاز والإنتاجية. (٣ درجات)
س٧. ما هو تأثير القافلة في جدولة FCFS؟ (٢ درجات)
تأثير القافلة يحدث عندما تعلق العمليات القصيرة خلف عملية طويلة. كل العمليات الأخرى تنتظر عملية واحدة كبيرة لتفرج المعالج، مما يؤدي إلى انخفاض استغلال المعالج والأجهزة.
س٨. كيف يحل التقادم مشكلة التجويع في جدولة الأولويات؟ (٢ درجات)
التقادم يزيد تدريجيًا أولوية العمليات التي تنتظر في النظام لفترة طويلة. هذا يضمن أن حتى العمليات منخفضة الأولوية ستحصل في النهاية على أولوية عالية كافية ليتم تنفيذها.
| المصطلح | التعريف |
|---|---|
| انفجار معالج | الوقت الذي تقضيه العملية في التنفيذ في المعالج |
| انفجار إدخال/إخراج | الوقت الذي تقضيه العملية في انتظار عملية إدخال/إخراج |
| جدول المعالج | يختار عملية من قائمة الانتظار الجاهزة للتنفيذ |
| الموزع | يعطي التحكم في المعالج للعملية المختارة |
| كمون التوزيع | الوقت لإيقاف عملية وبدء أخرى |
| استباقي | يمكن مقاطعة العملية أثناء التنفيذ |
| غير استباقي | العملية تعمل حتى الاكتمال أو الإدخال/الإخراج |
| الكم الزمني | شريحة الوقت في جدولة Round Robin |
| تأثير القافلة | عمليات قصيرة تنتظر خلف عملية طويلة |
| التجويع | العملية لا تحصل على وقت معالج أبدًا |
| التقادم | زيادة الأولوية بمرور الوقت |
| مخطط جانت | تمثيل مرئي لجدولة العمليات |
[إدراج مخطط يظهر انفجارات المعالج والإدخال/الإخراج المتناوبة]
[إدراج مخطط تبديل الموزع من الشرائح]
[إدراج مخطط قائمة انتظار متعددة المستويات]
ملاحظة: يرجى توفير المخططات الفعلية من شرائح Chapter_5.pdf لاستبدال هذه العناصر النائبة.