انتقل إلى محتوى الدرس
الدرس 34
تاريخ النشر: تاريخ التحديث:
دورة أنظمة التشغيل

خوارزميات جدولة المعالج الأساسيةCore CPU Scheduling Algorithms قارن خوارزميات جدولة المعالج FCFS وأثر القافلة و SJF و SRTF و Round Robin والشريحة الزمنية و MLFQ، واستكشف مجدول Linux CFS/EEVDF ومستويات أولوية Windows وأوامر الفحص الآمن.

قارن بين خوارزميات FCFS و SJF و Round Robin و MLFQ إلى جانب مجدول Linux الحديث وأرتال Windows، وافهم موازنات الشريحة الزمنية والعدالة بوضوح دون حسابات معقدة.
أقسام الدرس
6
الأمثلة
3
اللغة
العربية
المشاهدات
6
محتوى الدرس
في هذا الدرس 6تصفّح المواضيع

آلية رتل FCFS وتراكم أثر القافلة

استكمالاً لما درسته في أهداف الجدولة وعدالة الأولويات حول الموازنة بين استغلال المعالج وسرعة الاستجابة، تبرز خوارزمية القادم أولاً يُخدم أولاً FCFS بوصفها أبسط سياسة جدولة؛ إذ تصطف المهام الجاهزة في رتل FIFO واحد، فيختار الموزّع المهمة التي وصلت أولاً.

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

تفصيل تقني متقدم: إذا وصلت ثلاث مهام عند اللحظة صفر: مهمة ثقيلة P1 مدتها 24 ms تليها مهمتان خفيفتان P2 و P3 مدة كل منهما 3 ms، فستنتظر P2 مدة 24 ms وتنتظر P3 مدة 27 ms بمتوسط انتظار 17 ms، بينما يهبط المتوسط إلى 3 ms فقط عند تقديم المهام القصيرة.

مقارنة أثر القافلة في FCFS مع تقديم المهام القصيرة

مخطط زمني يوضح كيف تحجز مهمة طويلة المعالج في رتل FCFS وتؤخر المهام القصيرة مقارنة بترتيب الأقصر أولاً.

مخطط يقارن بين أثر القافلة في رتل FCFS حيث تؤخر المهمة الطويلة P1 المهام القصيرة P2 و P3 وبين ترتيب SJF الذي يخفض زمن الانتظار
مخطط يقارن بين أثر القافلة في رتل FCFS حيث تؤخر المهمة الطويلة P1 المهام القصيرة P2 و P3 وبين ترتيب SJF الذي يخفض زمن الانتظار

مثالية SJF وتحدي تخمين مدة الدفعة في SRTF

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

أما النسخة الاستباقية المسماة أقصر زمن متبقٍ أولاً SRTF فتمضي خطوة إضافية؛ فكلما وصلت مهمة جديدة زمنُ دفعتها أقصر من الزمن المتبقي للمهمة الجارية، يوقف الموزّع المهمة الحالية عبر آلية تبديل السياق والجدولة الاستباقية ويشغّل المهمة الأقصر فوراً.

تفصيل تقني متقدم: في أنظمة التشغيل العامة لا تعلم النواة مسبقاً كم ستستغرق دفعة المعالج القادمة للمهمة، لذا تعتمد نماذج SJF على التنبؤ الاستقرائي من السلوك السابق للمهمة. وإلى جانب صعوبة التخمين، يهدد تدفق المهام القصيرة المتواصل المهام الطويلة بمجاعة دائمة إذا طُبّقت الخوارزمية دون آلية حماية.

مقارنة خوارزميات FCFS و SJF و SRTF

الخوارزمية نوع الجدولة متوسط زمن الانتظار خطر المجاعة العقبة الهندسية الرئيسية
FCFS غير استباقية مرتفع عند تباين الأحجام معدوم أثر القافلة خلف المهام الطويلة
SJF غير استباقية مثالي ضمن غير الاستباقية مرتفع للمهام الطويلة صعوبة معرفة زمن الدفعة مسبقاً
SRTF استباقية الأقل نظرياً لمتوسط الانتظار مرتفع للمهام الطويلة تبديل سياق إضافي مع حتمية التخمين

التناوب الدائري وموازنة حجم الشريحة الزمنية

تحتاج الأنظمة التفاعلية متعددة المهام إلى استجابة سريعة لكل مستخدم دون الحاجة لتخمين مدة التنفيذ. تعالج خوارزمية التناوب الدائري Round Robin ذلك عبر رتل دوري مدمج بمؤقت يخصص لكل مهمة شريحة زمنية ثابتة تُسمى Time Quantum، وغالباً ما تراوح بين 1 ms و 100 ms في الأنظمة التقليدية؛ فإن لم تنتهِ المهمة قبل انقضاء الشريحة تُعاد إلى ذيل الرتل ليأخذ التالي دوره.

يمثّل ضبط حجم الشريحة الزمنية موازنة هندسية حساسة بين نقيضين:

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

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

حلقة التناوب الدائري وتأثير حجم الشريحة الزمنية

دورة الإرسال والرجوع عند انتهاء الشريحة في Round Robin مع مقارنة أثر صغر الشريحة أو كبرها.

مخطط يوضح دورة التناوب الدائري بين رتل الجاهزية والمعالج وفق الشريحة الزمنية ومقارنة آثار صغر الشريحة وتوازنها وكبرها
مخطط يوضح دورة التناوب الدائري بين رتل الجاهزية والمعالج وفق الشريحة الزمنية ومقارنة آثار صغر الشريحة وتوازنها وكبرها

تصنيف المهام ديناميكياً عبر أرتال MLFQ والشيخوخة

تعامل خوارزمية التناوب الدائري مهمةً خلفيةً ثقيلةً ومعالجاً تفاعلياً لنقرات لوحة المفاتيح بالقدر نفسه، بينما تحتاج SJF لتوقع المستقبل. لذلك صُمّم الرتل متعدد المستويات بالتغذية الراجعة MLFQ ليجمع الحسنيين معاً دون معرفة مسبقة بزمن التنفيذ، عبر مراقبة سلوك المهمة أثناء التشغيل.

يعتمد MLFQ على أرتال متدرجة الأولوية من الأعلى Q0 بشريحة قصيرة حتى الأدنى Q2 بشريحة أطول:

  • بداية متفائلة في القمة: تدخل كل مهمة جديدة الرتل الأعلى Q0 لتحصل على استجابة فورية إن كانت قصيرة أو تفاعلية.
  • تخفيض تلقائي عند الاستهلاك: إذا استنفدت المهمة كامل شريحتها الزمنية دون طلب إدخال أو إخراج، تُخفض إلى رتل أدنى؛ أما المهام التي تتوقف مبكراً للـ I/O فتبقى في الأولوية المرتفعة.
  • رفع دوري لمنع المجاعة: تطبيقاً لمفهوم الشيخوخة، تُرفع المهام المنتظرة دورياً إلى Q0 كي لا تجوع المهام الحسابية الطويلة وكي تستعيد أولويتها إن تحوّلت إلى طور تفاعلي.

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

مخطط أرتال MLFQ ومسار التخفيض والرفع الدوري

أرتال MLFQ الثلاثة التي توضح دخول المهمة الجديدة إلى Q0 والتخفيض التدريجي والرفع الدوري لمنع المجاعة.

مخطط أرتال MLFQ من Q0 إلى Q2 يوضح مسار تخفيض الأولوية عند استنفاد الشريحة ومسار الرفع الدوري لمنع المجاعة
مخطط أرتال MLFQ من Q0 إلى Q2 يوضح مسار تخفيض الأولوية عند استنفاد الشريحة ومسار الرفع الدوري لمنع المجاعة

مجدول Linux العادل CFS و EEVDF مقابل أرتال Windows

تدمج أنظمة التشغيل الحديثة هذه المبادئ الكلاسيكية في مجدولات عالية الكفاءة. فمنذ نواة لينكس 2.6.23، اعتمدت السياسة الافتراضية SCHED_OTHER على المجدول العادل تماماً CFS الذي يحاكي معالجاً متعدد المهام مثالياً عبر حساب الوقت الافتراضي vruntime بالنانوثانية داخل شجرة حمراء-سوداء بتعقيد O(log N)، ليختار دائماً المهمة صاحبة أقل وقت مستهلك موزوناً بقيمة اللطف nice من -20 إلى +19.

وبدءاً من نواة لينكس 6.6، بدأ الانتقال إلى خوارزمية EEVDF التي تحسب قيمة التأخر lag لكل مهمة مؤهلة ثم تنتقي أقرب موعد افتراضي Virtual Deadline، مما يمنح المهام الحساسة للتأخير شرائح قصيرة واستجابة أدق. وإلى جانب الجدولة العادلة، يحتفظ لينكس بسياسات الزمن الحقيقي SCHED_FIFO و SCHED_RR و SCHED_DEADLINE، وأضاف دعم التوسعة عبر sched_ext في لينكس 6.12.

على الجانب الآخر، تعتمد نواة Windows الحديثة مجدولاً استباقياً من 32 مستوى أولوية من 0 إلى 31 بنمط MLFQ؛ إذ تغطي المستويات 0..15 الخيوط العادية المتغيرة بينما تُخصص 16..31 لمهام الزمن الحقيقي الثابتة، وتدور الخيوط المتساوية في أعلى رتل غير فارغ وفق التناوب الدائري.

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

مقارنة مجدول Linux الحديث ومجدول Windows

المعيار نظام Linux الحديث نظام Windows الحديث
نموذج الجدولة الافتراضي جدولة عادلة عبر vruntime و EEVDF أرتال أولوية من 32 مستوى 0..31
نطاق الأولويات العادية والزمن الحقيقي لطف -20..+19 وللزمن الحقيقي 1..99 عادية متغيرة 0..15 وزمن حقيقي 16..31
تسريع التفاعل والاستجابة أقل vruntime وأقرب موعد افتراضي رفع ديناميكي عند نافذة المقدمة والإدخال والـ I/O
التناوب عند تساوي الأولوية ترتيب شجرة الوقت الافتراضي والـ lag تناوب دائري Round Robin داخل كل رتل

Inspect Process Scheduling Classes Safelyفحص فئات الجدولة والأولويات بأمان

اعرض فئة الجدولة cls والأولوية pri وقيمة اللطف ni للعمليات الجارية بأمان.

Shell
ps -eo pid,cls,pri,ni,comm | head -n 8

Process Scheduling Columns Output Previewمعاينة أعمدة الجدولة في مخرجات ps

معاينة طرفية تعرض فئات الجدولة TS و FF وقيم الأولوية واللطف للعمليات.

فحص سياسات الجدولة وإحصاءات النواة للقراءة فقط

يستطيع أي مستخدم عادي في لينكس فحص سياسة الجدولة وإحصاءات المجدول بأمان للقراءة فقط دون صلاحيات الجذر. فيُظهر الأمر chrt -p $$ سياسة الجدولة الحالية وأولوية طرفيتك الجارية التي تعتمد افتراضياً على SCHED_OTHER بأولوية 0، بينما يعرض chrt -m حدود الأولويات الصالحة لكل سياسة.

كما يكشف الملف الافتراضي /proc/schedstat عند تفعيله عدادات النواة التراكمية لكل معالج، مثل إجمالي زمن التنفيذ وزمن الانتظار في رتل الجاهزية بالنانوثانية وعدد الشرائح الزمنية المنفذة، مما يتيح مراقبة سلوك الجدولة الفعلي دون أي تغيير في حالة النظام.

Query Current Shell Scheduling Policyاستعلام سياسة جدولة الطرفية الحالية

افحص سياسة الجدولة والأولوية الساكنة لعملية الطرفية الجارية عبر chrt -p $$ بأمان.

Shell
chrt -p $$

chrt Read Only Output Previewمعاينة مخرجات chrt -p في الطرفية

معاينة طرفية تُظهر انتماء الطرفية الحالية إلى سياسة SCHED_OTHER وأولوية 0.

Read Kernel Scheduler Statistics Countersقراءة عدادات إحصاءات مجدول النواة

اقرأ الأسطر الأولى من /proc/schedstat لمعاينة زمن التنفيذ والانتظار وعدد الشرائح.

Shell
head -n 6 /proc/schedstat

Kernel schedstat Counters Previewمعاينة عدادات /proc/schedstat في لينكس

معاينة طرفية تعرض عدادات النواة للوقت المستغرق في التشغيل والانتظار لكل نواة.

خلاصة المعرفة ومحطة الانتقال

ملخص الدرس

حصاد الدرس

مراجعة مركّزة لأهم المفاهيم والقواعد الهندسية التي أتقنتها في هذا الدرس قبل التطبيق العملي

ماذا تعلّمت في هذا الدرس؟

استعرضت في هذا الدرس تطور خوارزميات جدولة المعالج بدءاً من بساطة FCFS ومشكلة أثر القافلة، ومثالية SJF و SRTF في تقليص الانتظار مقابل صعوبة توقع المدة وخطر المجاعة، وصولاً إلى التناوب الدائري Round Robin وموازنة الشريحة الزمنية، وأرتال MLFQ المتكيفة بالشيخوخة، وأخيراً تطبيقات Linux الحديثة مثل CFS و EEVDF و Windows مع فحصها بأمان عبر ps -eo و chrt -p $$ و /proc/schedstat.

الخطوة التالية والدرس القادم

لقد أتممت وحدة جدولة المعالج بنجاح! انتقل الآن إلى بداية وحدة إدارة الذاكرة في الدرس التالي هرمية الذاكرة ومشكلة التجزؤ برمز memory-hierarchy-and-fragmentation لتكتشف كيف يعمل هرم الكاش والرام وتحديات تجزؤ الذاكرة.

مشاركة

هل كان هذا الدرس مفيدًا؟

جارٍ تحميل الآراء…

ابنِ لغتك البرمجية

المصطلحات4

راجع المعنى، اشرحه لنفسك، ثم علّم البطاقة كمفهومة.

0 / 4 مفهومةأول بطاقة، أول خطوة
01 Convoy Effect أثر القافلة
اختناق يحدث في جدولة FCFS عندما تحتجز عملية حسابية طويلة المعالج وتجبر عدة مهام قصيرة وتفاعلية على الانتظار خلفها، مما يرفع متوسط زمن الانتظار.
للمراجعة
02 Time Quantum الشريحة الزمنية
المدة الزمنية القصوى الثابتة التي تُمنح لكل مهمة في جولة التناوب الدائري قبل أن يقاطعها المؤقت ويعيدها إلى نهاية رتل الجاهزية.
للمراجعة
03 Multi-Level Feedback Queue الرتل متعدد المستويات بالتغذية الراجعة
مجدول أولويات متكيف يبدأ المهام الجديدة في أعلى رتل ويخفض المهام كثيفة المعالجة عند استنفاد شريحتها، مع رفع دوري لمنع المجاعة.
للمراجعة
04 Virtual Runtime (vruntime) الوقت الافتراضي vruntime
مقياس في مجدول CFS بنواة لينكس يحسب بالنانوثانية الزمن الفعلي الموزون بقيمة اللطف لاختيار المهمة التي نالت أقل نصيب عادل من المعالج.
للمراجعة

اقرأ البطاقات بحرية. سجّل الدخول لحفظ تقدم مراجعتك.

حروف قليلة. معنى كامل.

الاختصارات4

راجع المعنى، اشرحه لنفسك، ثم علّم البطاقة كمفهومة.

0 / 4 مفهومةأول بطاقة، أول خطوة
01 FCFS FCFS
First-Come, First-Served
القادم أولاً يُخدم أولاً
للمراجعة
02 SRTF SRTF
Shortest Remaining Time First
أقصر زمن متبقٍ أولاً
للمراجعة
03 MLFQ MLFQ
Multi-Level Feedback Queue
الرتل متعدد المستويات بالتغذية الراجعة
للمراجعة
04 EEVDF EEVDF
Earliest Eligible Virtual Deadline First
أقرب موعد افتراضي للمهام المؤهلة أولاً
للمراجعة

اقرأ البطاقات بحرية. سجّل الدخول لحفظ تقدم مراجعتك.

من الفهم للتطبيق

مهامك قبل الاختبار

خطوة صغيرة كل مرة. وإنجاز تقدر ترجع له.

0/4مهام منجزة
  1. شغّل أمر ps -eo pid,cls,pri,ni,comm | head -n 10 في طرفية لينكس لمعاينة فئات الجدولة TS و FF وقيم اللطف بأمان.

  2. نفّذ الأمر chrt -p $$ لعرض سياسة الجدولة النشطة وأولوية طرفيتك الحالية للقراءة فقط دون صلاحيات الجذر.

  3. شغّل الأمر chrt -m لاستعراض الحد الأدنى والأقصى للأولويات المسموحة لكل سياسة جدولة في لينكس.

  4. نفّذ head -n 6 /proc/schedstat في لينكس لمعاينة زمن التنفيذ وزمن الانتظار وعدد الشرائح الزمنية على المعالج بأمان.

تأشير المهمة إقرار منك بإتمامها، وليس تصحيحًا آليًا للكود. يُحفظ تقدمك في حسابك.

مساحة التحدي

اختبر فهمك.
ووصلها للإتقان.

كل سؤال خطوة لقدّام. اختار، اكتب كود، وشوف نتيجتك فورًا.

9أسئلة 2أنواع تحديات 100%هدف الإتقان
تصحيح تلقائي. فرص بلا حدود.

أكمل المهام، واجمع كل الإجابات الصحيحة. أقل من 100%؟ راجع وأعد المحاولة.

الأسئلة متاحة للاطلاع. سجّل الدخول للتفاعل وحفظ تقدمك.

لمحة عن التحدي9 أسئلة تنتظرك
01

ما السبب المباشر لحدوث أثر القافلة في خوارزمية FCFS؟

ما السبب المباشر لحدوث أثر القافلة في خوارزمية FCFS؟

02

لماذا يصعب تطبيق خوارزمية SJF أو SRTF بصورتها الصافية في أنظمة التشغيل التفاعلية العامة؟

لماذا يصعب تطبيق خوارزمية SJF أو SRTF بصورتها الصافية في أنظمة التشغيل التفاعلية العامة؟

03

في جدولة التناوب الدائري Round Robin، ما أثر اختيار شريحة زمنية صغيرة جداً أو كبيرة جداً؟

في جدولة التناوب الدائري Round Robin، ما أثر اختيار شريحة زمنية صغيرة جداً أو كبيرة جداً؟

04

أيّ من العبارات التالية تصف جدولة MLFQ بدقة؟

أيّ من العبارات التالية تصف جدولة MLFQ بدقة؟

05

كيف يختار مجدول Linux العادل تماماً CFS المهمة الجاهزة التالية للتنفيذ؟

كيف يختار مجدول Linux العادل تماماً CFS المهمة الجاهزة التالية للتنفيذ؟

06

ما الميزة الأساسية التي قدمتها خوارزمية EEVDF منذ نواة Linux 6.6 مقارنة بـ CFS؟

ما الميزة الأساسية التي قدمتها خوارزمية EEVDF منذ نواة Linux 6.6 مقارنة بـ CFS؟

07

كيف يتعامل نظام Windows مع الرفع الديناميكي للأولوية عبر مستوياته الـ 32 من 0 إلى 31؟

كيف يتعامل نظام Windows مع الرفع الديناميكي للأولوية عبر مستوياته الـ 32 من 0 إلى 31؟

08

أيّ أمر في لينكس يفحص سياسة الجدولة وأولوية الطرفية الجارية بأمان ودون صلاحيات تعديل؟

أيّ أمر في لينكس يفحص سياسة الجدولة وأولوية الطرفية الجارية بأمان ودون صلاحيات تعديل؟

09

لماذا ترتبط وحدة إدارة الذاكرة التالية مباشرة بكفاءة عمل مجدول المعالج؟

لماذا ترتبط وحدة إدارة الذاكرة التالية مباشرة بكفاءة عمل مجدول المعالج؟