جدولة وحدة المعالجة المركزية
دراسة خوارزميات جدولة وحدة المعالجة المركزية، معايير التقييم، وجدولة المعالجات المتعددة والأنظمة متعددة النواة.
CPU Scheduling
Study of CPU scheduling algorithms, evaluation criteria, and multiprocessor/multicore scheduling.
أهداف التعلم
- وصف خوارزميات جدولة وحدة المعالجة المركزية والاختلافات بينها.
- تقييم خوارزميات جدولة وحدة المعالجة المركزية بناءً على معايير الجدولة.
- شرح القضايا المتعلقة بجدولة المعالجات المتعددة والأنظمة متعددة النواة.
- Describe CPU scheduling algorithms and their differences.
- Evaluate CPU scheduling algorithms based on scheduling criteria.
- Explain the issues related to multiprocessor and multicore scheduling.
1 مجدول وحدة المعالجة المركزية والمُرحّل
1 CPU Scheduler and Dispatcher
المجدول يختار العملية التالية للتنفيذ، والمُرحّل يمنحها السيطرة الفعلية على المعالج.
The scheduler selects the next process to run, and the dispatcher gives it actual control of the CPU.
يقوم مجدول وحدة المعالجة المركزية (CPU Scheduler) باختيار عملية من طابور الانتظار (Ready Queue) لتخصيص المعالج لها. يمكن أن تكون الجدولة استباقية (Preemptive) حيث يمكن مقاطعة العملية، أو غير استباقية (Nonpreemptive) حيث تحتفظ العملية بالمعالج حتى تنتهي أو تنتظر.
المُرحّل (Dispatcher) هو الوحدة التي تمنح السيطرة للعملية المختارة، ويتضمن ذلك تبديل السياق (Context Switch)، التبديل لوضع المستخدم، والقفز للموقع المناسب لاستئناف البرنامج. الوقت المستغرق في هذه العملية يسمى زمن انتقال المُرحّل (Dispatch Latency).
The CPU Scheduler selects a process from the ready queue to allocate the CPU to. Scheduling can be Preemptive (process can be interrupted) or Nonpreemptive (process keeps CPU until it terminates or waits).
The Dispatcher is the module that gives control of the CPU to the selected process, involving context switching, switching to user mode, and jumping to the proper location to restart the program. The time this takes is called Dispatch Latency.
الجدولة الاستباقية ضرورية للأنظمة الحديثة لضمان الاستجابة، لكنها قد تسبب حالات تسابق (Race Conditions) إذا تمت مقاطعة عملية أثناء تحديث بيانات مشتركة.
زمن انتقال المُرحّل يجب أن يكون في حده الأدنى لأن هذا الوقت يعتبر وقتاً ضائعاً لا يتم فيه تنفيذ أي عمل مفيد للمستخدم.
Preemptive scheduling is essential for modern OS responsiveness but can lead to Race Conditions if a process is preempted while updating shared data.
Dispatch latency must be minimized because it is pure overhead during which no useful user work is accomplished.
| الجدولة الاستباقية Preemptive | الجدولة غير الاستباقية Nonpreemptive | |
|---|---|---|
| التحكم بالمعالجCPU Control | يمكن مقاطعة العملية وإجبارها على التخلي عن المعالجProcess can be interrupted and forced to release CPU | تحتفظ العملية بالمعالج حتى تنتهي أو تنتظرProcess keeps CPU until it terminates or waits |
| الاستجابةResponsiveness | عالية، مناسبة للأنظمة التفاعليةHigh, suitable for interactive systems | منخفضة، قد تحتكر عملية واحدة النظامLow, one process can monopolize the system |
| التعقيد وحالات التسابقComplexity & Race Conditions | معقدة، قد تسبب حالات تسابق في البيانات المشتركةComplex, can cause race conditions in shared data | بسيطة، لا تسبب مقاطعات غير متوقعةSimple, no unexpected interruptions |
لماذا تستخدم جميع أنظمة التشغيل الحديثة تقريباً الجدولة الاستباقية رغم تعقيدها؟ Why do almost all modern operating systems use preemptive scheduling despite its complexity?
لأنها تمنع العمليات الطويلة من احتكار المعالج، مما يضمن استجابة سريعة للمستخدمين والعمليات التفاعلية.
Because it prevents long-running processes from monopolizing the CPU, ensuring fast response times for users and interactive processes.
2 معايير الجدولة
2 Scheduling Criteria
المقاييس المستخدمة لتقييم ومقارنة خوارزميات الجدولة المختلفة.
The metrics used to evaluate and compare different scheduling algorithms.
لتقييم خوارزميات الجدولة، نستخدم عدة معايير:
- استخدام المعالج (CPU utilization): إبقاء المعالج مشغولاً قدر الإمكان (الهدف: الحد الأقصى).
- الإنتاجية (Throughput): عدد العمليات المكتملة في وحدة الزمن (الهدف: الحد الأقصى).
- وقت الاستدارة (Turnaround time): الوقت الإجمالي لتنفيذ عملية معينة من لحظة وصولها حتى اكتمالها (الهدف: الحد الأدنى).
- وقت الانتظار (Waiting time): الوقت الذي تقضيه العملية في طابور الانتظار (الهدف: الحد الأدنى).
- وقت الاستجابة (Response time): الوقت من تقديم الطلب حتى إنتاج أول استجابة (الهدف: الحد الأدنى).
To evaluate scheduling algorithms, we use several criteria:
- CPU utilization: keep the CPU as busy as possible (Max).
- Throughput: number of processes completed per time unit (Max).
- Turnaround time: amount of time to execute a particular process from submission to completion (Min).
- Waiting time: amount of time a process has been waiting in the ready queue (Min).
- Response time: amount of time it takes from when a request was submitted until the first response is produced (Min).
لا يمكن لخوارزمية واحدة تحسين جميع المعايير في وقت واحد. على سبيل المثال، تحسين وقت الاستجابة (عبر التبديل السريع للسياق) قد يقلل من الإنتاجية بسبب زيادة العبء الإضافي (Overhead) لتبديل السياق.
No single algorithm can optimize all criteria simultaneously. For example, optimizing response time (via frequent context switching) might decrease overall throughput due to the increased context switch overhead.
أيهما أكثر أهمية في الأنظمة التفاعلية: وقت الاستدارة أم وقت الاستجابة؟ Which is more important in interactive systems: turnaround time or response time?
وقت الاستجابة، لأن المستخدم يتوقع رؤية نتائج أو تفاعل فوري حتى لو استغرق إكمال المهمة بالكامل وقتاً أطول.
Response time, because the user expects to see immediate feedback or interaction even if the full task takes longer to complete.
3 جدولة القادم أولاً يُخدم أولاً (FCFS)
3 First-Come, First-Served (FCFS) Scheduling
العملية التي تطلب المعالج أولاً تحصل عليه أولاً، مثل الطابور في المتجر.
The process that requests the CPU first is allocated the CPU first, like a queue in a store.
خوارزمية FCFS هي أبسط خوارزميات الجدولة. يتم تنفيذ العمليات بالترتيب الذي تصل به. هي خوارزمية غير استباقية.
العيب الرئيسي لها هو تأثير القافلة (Convoy Effect)، حيث تنتظر العمليات القصيرة خلف عملية واحدة طويلة جداً، مما يؤدي إلى زيادة كبيرة في متوسط وقت الانتظار.
The FCFS algorithm is the simplest scheduling algorithm. Processes are executed in the order they arrive. It is a nonpreemptive algorithm.
Its main drawback is the Convoy Effect, where short processes wait behind one very long process, leading to a significantly higher average waiting time.
تأثير القافلة يظهر بوضوح عندما يكون لدينا عملية واحدة تعتمد بشدة على المعالج (CPU-bound) والعديد من العمليات التي تعتمد على الإدخال/الإخراج (I/O-bound). ستنتظر عمليات الإدخال/الإخراج طويلاً حتى تنتهي عملية المعالج، مما يقلل من استخدام أجهزة الإدخال/الإخراج.
The convoy effect is especially problematic when there is one CPU-bound process and many I/O-bound processes. The I/O-bound processes will wait a long time for the CPU-bound process to finish, leading to poor utilization of I/O devices.
كيف يمكن ترتيب العمليات في FCFS لتقليل متوسط وقت الانتظار؟ How could processes be ordered in FCFS to minimize average waiting time?
بترتيبها من الأقصر إلى الأطول، وهو ما يقودنا إلى خوارزمية SJF.
By ordering them from shortest to longest, which essentially leads to the SJF algorithm.
4 جدولة أقصر وظيفة أولاً (SJF)
4 Shortest-Job-First (SJF) Scheduling
تخصيص المعالج للعملية ذات أقصر وقت تنفيذ قادم لتقليل وقت الانتظار.
Allocating the CPU to the process with the shortest next CPU burst to minimize waiting time.
خوارزمية SJF تربط كل عملية بطول فترة استخدام المعالج القادمة لها. يتم جدولة العملية ذات الوقت الأقصر. تعتبر هذه الخوارزمية مثالية (Optimal) لأنها تعطي أقل متوسط وقت انتظار لمجموعة معينة من العمليات.
النسخة الاستباقية منها تسمى أقصر وقت متبقي أولاً (Shortest-Remaining-Time-First).
الصعوبة الرئيسية هي معرفة طول فترة المعالج القادمة، ولذلك يتم تقديرها باستخدام المتوسط الأسي (Exponential Averaging) بناءً على الفترات السابقة.
The SJF algorithm associates each process with the length of its next CPU burst. The process with the shortest time is scheduled. It is optimal as it gives the minimum average waiting time for a given set of processes.
Its preemptive version is called Shortest-Remaining-Time-First (SRTF).
The main difficulty is knowing the length of the next CPU request, so it is estimated using Exponential Averaging based on previous bursts.
في المتوسط الأسي، نستخدم المعادلة $\tau_{n+1} = \alpha t_n + (1 - \alpha)\tau_n$. حيث $t_n$ هو الطول الفعلي الأخير، و $\tau_n$ هو التوقع السابق، و $\alpha$ يحدد وزن التاريخ الحديث مقابل القديم (عادة $\alpha = 0.5$).
إذا كانت $\alpha = 1$، فإننا نعتمد فقط على آخر فترة فعلية.
In exponential averaging, we use $\tau_{n+1} = \alpha t_n + (1 - \alpha)\tau_n$. Here, $t_n$ is the actual length of the $n^{th}$ burst, $\tau_n$ is the past prediction, and $\alpha$ controls the weight of recent vs past history (commonly $\alpha = 1/2$).
If $\alpha = 1$, only the most recent actual burst counts.
ماذا يحدث لمعادلة التوقع إذا جعلنا قيمة ألفا (α) تساوي صفراً؟ What happens to the prediction formula if we set alpha (α) to zero?
تصبح المعادلة تعتمد فقط على التوقع الأولي، ويتم تجاهل التاريخ الحديث بالكامل (التوقع لا يتغير أبداً).
The formula relies entirely on the initial prediction, and recent history does not count at all (the prediction never changes).
5 جدولة راوند روبن (Round Robin)
5 Round Robin (RR) Scheduling
إعطاء كل عملية حصة زمنية صغيرة متساوية بالتناوب.
Giving each process a small, equal time slice in turn.
في خوارزمية Round Robin (RR)، تحصل كل عملية على وحدة صغيرة من وقت المعالج تسمى الحصة الزمنية (Time Quantum - q)، عادة بين 10-100 مللي ثانية.
بعد انقضاء هذا الوقت، تتم مقاطعة العملية (Preempted) وإضافتها إلى نهاية طابور الانتظار. لا تنتظر أي عملية أكثر من $(n-1)q$ من الوقت.
أداء الخوارزمية يعتمد بشدة على حجم $q$.
In Round Robin (RR) scheduling, each process gets a small unit of CPU time called a time quantum (q), usually 10-100 milliseconds.
After this time elapses, the process is preempted and added to the end of the ready queue. No process waits more than $(n-1)q$ time units.
Performance depends heavily on the size of $q$.
إذا كانت الحصة الزمنية $q$ كبيرة جداً، فإن RR تتصرف مثل FCFS. وإذا كانت $q$ صغيرة جداً، فإن العبء الإضافي لتبديل السياق (Context Switch Overhead) يصبح مرتفعاً جداً ويضيع وقت المعالج في التبديل بدلاً من التنفيذ.
يجب أن تكون $q$ كبيرة مقارنة بوقت تبديل السياق.
If $q$ is very large, RR behaves like FCFS. If $q$ is very small, the context switch overhead becomes too high, wasting CPU time on switching rather than executing.
$q$ must be large with respect to the context switch time.
لماذا يعتبر متوسط وقت الاستدارة في خوارزمية RR غالباً أسوأ من SJF؟ Why is the average turnaround time in RR often worse than in SJF?
لأن RR تقاطع العمليات بشكل متكرر، مما يؤخر اكتمال العمليات الطويلة، بينما SJF تنهي العمليات القصيرة بالكامل أولاً.
Because RR frequently preempts processes, delaying the completion of longer processes, whereas SJF finishes shorter processes completely first.
6 جدولة الأولوية
6 Priority Scheduling
تنفيذ العمليات بناءً على رقم أولوية محدد؛ الأعلى أولوية يُنفذ أولاً.
Executing processes based on an assigned priority number; highest priority runs first.
في جدولة الأولوية، يتم ربط رقم أولوية (عدد صحيح) بكل عملية. يُخصص المعالج للعملية ذات الأولوية الأعلى (عادةً الرقم الأصغر يعني أولوية أعلى). يمكن أن تكون استباقية أو غير استباقية.
المشكلة الكبرى هنا هي المجاعة (Starvation)، حيث قد لا يتم تنفيذ العمليات ذات الأولوية المنخفضة أبداً إذا استمرت العمليات ذات الأولوية العالية بالوصول.
الحل هو التقادم (Aging)، وهو زيادة أولوية العملية تدريجياً بمرور الوقت.
In Priority Scheduling, a priority number (integer) is associated with each process. The CPU is allocated to the process with the highest priority (usually smallest integer = highest priority). It can be preemptive or nonpreemptive.
The major problem is Starvation, where low-priority processes may never execute if high-priority processes keep arriving.
The solution is Aging, which gradually increases the priority of a process over time.
خوارزمية SJF هي في الواقع حالة خاصة من جدولة الأولوية، حيث تكون الأولوية هي المعكوس لطول فترة المعالج القادمة المتوقعة (كلما قصر الوقت، زادت الأولوية).
يمكن دمج الأولوية مع Round Robin لتنفيذ العمليات ذات نفس الأولوية بالتناوب.
SJF is actually a special case of priority scheduling, where the priority is the inverse of the predicted next CPU burst time (shorter time = higher priority).
Priority scheduling can be combined with Round Robin to run processes of the same priority in a time-sliced manner.
بدون استخدام التقادم (Aging)، ما هو المصير المحتمل لعملية ذات أولوية منخفضة جداً في نظام مزدحم؟ Without using Aging, what is the likely fate of a very low-priority process in a busy system?
ستعاني من المجاعة (Starvation) وقد لا يتم تنفيذها أبداً.
It will suffer from Starvation and may never be executed.
7 الطوابير متعددة المستويات
7 Multilevel Queues
تقسيم طابور الانتظار إلى عدة طوابير منفصلة بناءً على نوع العملية.
Partitioning the ready queue into several separate queues based on process type.
في الطوابير متعددة المستويات (Multilevel Queue)، يتم تقسيم طابور الانتظار إلى طوابير منفصلة (مثل: عمليات النظام، العمليات التفاعلية، عمليات الدفعات). كل طابور له خوارزمية الجدولة الخاصة به. يتم جدولة العمليات في الطابور ذي الأولوية الأعلى أولاً.
طابور الملاحظات متعدد المستويات (Multilevel Feedback Queue) يسمح للعمليات بالانتقال بين الطوابير؛ فإذا استهلكت العملية وقت معالج كبير، يتم نقلها لطابور ذي أولوية أقل، مما يمنع احتكار المعالج.
In a Multilevel Queue, the ready queue is partitioned into separate queues (e.g., system processes, interactive processes, batch processes). Each queue has its own scheduling algorithm. Processes in the highest-priority queue are scheduled first.
A Multilevel Feedback Queue allows processes to move between queues; if a process uses too much CPU time, it is moved to a lower-priority queue, preventing CPU monopolization.
طابور الملاحظات متعدد المستويات هو الأكثر مرونة ولكنه الأكثر تعقيداً. يتم تعريفه بعدة معلمات: عدد الطوابير، خوارزمية الجدولة لكل طابور، طريقة ترقية العملية (متى تنتقل لطابور أعلى)، وطريقة تخفيض العملية (متى تنتقل لطابور أدنى).
The Multilevel Feedback Queue is the most flexible but also the most complex. It is defined by several parameters: number of queues, scheduling algorithm for each queue, method to upgrade a process, and method to demote a process.
لماذا يتم وضع العمليات التفاعلية في طوابير ذات أولوية أعلى من عمليات الدفعات (Batch)؟ Why are interactive processes placed in higher-priority queues than batch processes?
لأن العمليات التفاعلية تتطلب وقت استجابة سريع جداً لضمان تجربة مستخدم سلسة، بينما عمليات الدفعات يمكن أن تعمل في الخلفية.
Because interactive processes require very fast response times to ensure a smooth user experience, whereas batch processes can run in the background.
8 جدولة المعالجات المتعددة والأنظمة متعددة النواة
8 Multiprocessor and Multicore Scheduling
توزيع العمليات على عدة معالجات أو أنوية لضمان الكفاءة وتوازن الحمل.
Distributing processes across multiple processors or cores to ensure efficiency and load balancing.
في المعالجة المتعددة المتماثلة (SMP)، يقوم كل معالج بجدولة نفسه. للحفاظ على الكفاءة، نستخدم موازنة الحمل (Load Balancing) عبر الترحيل بالدفع (Push migration) (دفع المهام من المعالج المزدحم) أو الترحيل بالسحب (Pull migration) (سحب المهام بواسطة المعالج الخامل).
تقارب المعالج (Processor Affinity) يعني محاولة إبقاء العملية على نفس المعالج للاستفادة من البيانات المخزنة في الذاكرة المخبئية (Cache).
في الأنظمة متعددة النواة (Multicore)، يمكن لكل نواة تشغيل عدة خيوط أجهزة (Hardware threads) للاستفادة من أوقات توقف الذاكرة (Memory Stall).
In Symmetric Multiprocessing (SMP), each processor is self-scheduling. To maintain efficiency, we use Load Balancing via Push migration (pushing tasks from an overloaded CPU) or Pull migration (idle CPU pulls tasks).
Processor Affinity means trying to keep a process on the same processor to benefit from cache contents.
In Multicore systems, each core can run multiple hardware threads to take advantage of memory stalls.
التقارب المرن (Soft affinity) يعني أن النظام يحاول إبقاء العملية على نفس المعالج ولكن دون ضمانات، بينما التقارب الصلب (Hard affinity) يحدد بدقة المعالجات المسموح للعملية بالعمل عليها.
في أنظمة NUMA (الوصول غير المنتظم للذاكرة)، يقوم المجدول بتخصيص الذاكرة الأقرب للمعالج الذي تعمل عليه العملية لتقليل وقت الوصول.
Soft affinity means the OS attempts to keep a thread on the same processor but makes no guarantees, while hard affinity allows a process to specify exactly which processors it may run on.
In NUMA (Non-Uniform Memory Access) systems, the scheduler assigns memory closest to the CPU the thread is running on to minimize access time.
| الترحيل بالدفع Push Migration | الترحيل بالسحب Pull Migration | |
|---|---|---|
| المبادر بالعمليةInitiator | مهمة دورية تفحص الحمل وتدفع المهام من المعالج المزدحمPeriodic task checks load and pushes tasks from overloaded CPU | المعالج الخامل يسحب المهام من المعالج المزدحمIdle processor pulls waiting tasks from busy processor |
| التقارب المرن Soft Affinity | التقارب الصلب Hard Affinity | |
|---|---|---|
| الضماناتGuarantees | يحاول النظام إبقاء العملية على نفس المعالج، لكن لا توجد ضماناتOS attempts to keep thread on same processor, but no guarantees | يسمح للعملية بتحديد مجموعة المعالجات التي يجب أن تعمل عليهاAllows process to specify a set of processors it may run on |
كيف يتعارض مفهوم موازنة الحمل (Load Balancing) مع تقارب المعالج (Processor Affinity)؟ How does Load Balancing conflict with Processor Affinity?
موازنة الحمل تنقل العمليات بين المعالجات لتوزيع العمل، مما يؤدي إلى فقدان البيانات المخزنة في الذاكرة المخبئية للمعالج الأصلي، وهو ما يحاول تقارب المعالج تجنبه.
Load balancing moves processes between processors to distribute work, which causes the loss of cache contents on the original processor, exactly what processor affinity tries to avoid.