كيف تعمل جدولة الـ CPU (CPU scheduling)، وما هي الخوارزميات الشائعة؟

Question

IT Interview Practice · Accepted Answer

**جدولة الـ CPU (CPU scheduling)** هي قرار الـ kernel بشأن *أيّ* خيط جاهز يحصل على الـ CPU *تاليًا*، و*لكم من الوقت*. وبما أن الخيوط القابلة للتشغيل عادةً أكثر من الـ cores، يقوم الـ **scheduler** بمناوبتها (multiplex)، ساعيًا إلى موازنة أهداف متنافسة — **throughput**، و**latency / زمن استجابة منخفض**، و**العدالة (fairness)** — مع تفادي **التجويع (starvation)**.

## الخوارزميات الشائعة

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

يوضّح **Round-robin** المِقبض الجوهري — الـ **quantum**:

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## الـ schedulers الحقيقية

الافتراضي العريق في لينكس كان **CFS (Completely Fair Scheduler)**: فبدل شرائح ثابتة، يتتبّع **زمن التشغيل الافتراضي (virtual runtime أو vruntime)** لكل مهمة ويشغّل دائمًا الخيط الذي نال أقلّ قدر من الـ CPU حتى الآن، موزونًا بقيمة **nice** الخاصة به — مقارِبًا فكرة "ينال الجميع حصة عادلة". ويفهرس شجرة حمراء-سوداء (red-black tree) بحسب vruntime، فيكون اختيار المهمة التالية بتعقيد O(log n). (تستخدم النوى الأحدث EEVDF، وهو تنقيح بالهدف العادل نفسه مع حدود latency أضيق.)

**Preemptive مقابل cooperative:** أنظمة التشغيل الحديثة **preemptive** (استباقية) — إذ يتيح timer interrupt للـ scheduler أن يستردّ الـ CPU قسرًا، فلا يستطيع خيط احتكار core.

## لماذا يهم

تشكّل الجدولة مباشرةً الـ latency والـ throughput اللذين يشعر بهما المستخدمون. يسبر المُقابِلون هذا الموضوع ليروا إن كنت تفهم المفاضلات — لماذا يريد العبء التفاعلي quantum قصيرًا أو دفعة أولوية، ولماذا تحتاج priority scheduling إلى **aging** لمنع الـ starvation، وكيف تحقّق MLFQ/CFS سلوكًا تفاعليًّا جيدًا دون معرفة أطوال المهام مسبقًا. كما أنه النموذج الذهني وراء ضبط `nice`، وأولويات real-time، وتشخيص خدمة مُجوَّعة أو متقطّعة.

الخوارزميات الشائعة

الـ schedulers الحقيقية

لماذا يهم

أسئلة ذات صلة