Optimization: CPU Scheduling التحسين: جدولة وحدة المعالجة المركزية (CPU Scheduling)

Deciding which process runs next. Maximizing CPU utilization through smart algorithms. اتخاذ القرار بشأن أي عملية ستعمل تالياً. تعظيم استخدام وحدة المعالجة المركزية من خلال خوارزميات ذكية.

Preemptive vs Non-Preemptive Preemptive vs Non-Preemptive FCFS FCFS SJF SJF Round Robin (RR) Round Robin (RR) Multilevel Queue Multilevel Queue

Basic Concepts مفاهيم أساسية

Process execution consists of a cycle of CPU execution and I/O wait. تنفيذ العملية يتكون من دورة من تنفيذ CPU و انتظار I/O.

graph LR A[Load Store] --> B(CPU Burst) B --> C[Read File] C --> D(I/O Burst) D --> E[Store Increment] E --> F(CPU Burst)
CPU-bound Process CPU-bound Process Spends more time doing computations. Few very long CPU bursts. تقضي وقتاً أطول في الحسابات. دفقات CPU (Bursts) قليلة وطويلة جداً.
I/O-bound Process I/O-bound Process Spends more time doing I/O. Many short CPU bursts. تقضي وقتاً أطول في الإدخال/الإخراج. دفقات CPU كثيرة وقصيرة.

The Dispatcher The Dispatcher (المرسل)

The module that gives control of the CPU to the process selected by the short-term scheduler. الوحدة التي تعطي التحكم في وحدة المعالجة المركزية للعملية المختارة من قبل المجدول قصير الأجل (short-term scheduler).

  • Switching context.تبديل السياق (Context).
  • Switching to user mode.التحويل إلى وضع المستخدم.
  • Jumping to the proper location in the user program to restart that program.القفز إلى الموقع المناسب في برنامج المستخدم لإعادة تشغيله.

Dispatch Latency: Time it takes for the dispatcher to stop one process and start another. Dispatch Latency: الوقت الذي يستغرقه الـ dispatcher لإيقاف عملية وبدء أخرى.

Optimization Criteria معايير التحسين

What are we trying to maximize or minimize? ما الذي نحاول تعظيمه أو تقليله؟

Maximize تعظيم (Maximize)

CPU Utilization

Throughput

Minimize تقليل (Minimize)

Turnaround Time

Waiting Time

Response Time

Definitions تعريفات

Throughput:Throughput: # of processes completing per time unit. عدد العمليات المكتملة لكل وحدة زمنية.

Turnaround:Turnaround: Submission to Completion. من التقديم إلى الإنجاز.

Waiting:Waiting: Time spent in Ready Queue. الوقت المستغرق في طابور الجاهزية.

Algorithms الخوارزميات (Algorithms)

FCFS (First-Come, First-Served)

Non-Preemptive

Processes are executed in the order they arrive. Simple (FIFO Queue) but can cause the Convoy Effect (short process stuck behind long process). يتم تنفيذ العمليات بالترتيب الذي وصلت به. بسيطة (طابور FIFO) ولكن قد تسبب تأثير القافلة (Convoy Effect) (عملية قصيرة عالقة خلف عملية طويلة).

SJF (Shortest Job First)

Optimal (Avg Wait)

Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time. اربط كل عملية بطول دفق الـ CPU التالي لها. استخدم هذه الأطوال لجدولة العملية ذات الوقت الأقصر.

Non-Preemptive SJF:Non-Preemptive SJF: Once CPU given, it cannot be preempted until completion. بمجرد إعطاء الـ CPU، لا يمكن مقاطعته حتى الانتهاء.
Preemptive SJF (SRTF):Preemptive SJF (SRTF): If a new process arrives with shorter burst than remaining time of current, preempt! (Shortest Remaining Time First). إذا وصلت عملية جديدة بـ Burst أقصر من الوقت المتبقي للحالية، قاطعها!

Round Robin (RR)

Preemptive

Designed for time-sharing. Each process gets a small unit of CPU time (Time Quantum q), usually 10-100ms. After this time, the process is preempted and added to the end of the ready queue. صممت للمشاركة الزمنية. تحصل كل عملية على وحدة صغيرة من وقت الـ CPU (Time Quantum q)، عادة 10-100 مللي ثانية. بعد هذا الوقت، تتم مقاطعة العملية وإضافتها إلى نهاية طابور الجاهزية.

*If q is too large $\to$ FCFS. If q is too small $\to$ Excessive context switch overhead. *إذا كانت q كبيرة جداً $\to$ FCFS. إذا كانت q صغيرة جداً $\to$ تكلفة تبديل سياق مفرطة.

Priority Scheduling

A priority number (integer) is associated with each process. CPU is allocated to the process with highest priority (smallest integer usually).
Problem: Starvation (Low priority processes may never execute).
Solution: Aging (Increase priority as time progresses). رقم أولوية (عدد صحيح) يرتبط بكل عملية. يخصص الـ CPU للعملية ذات الأولوية الأعلى (عادة العدد الأصغر).
المشكلة: Starvation (المجاعة) (العمليات ذات الأولوية المنخفضة قد لا تنفذ أبداً).
الحل: Aging (التقادم) (زيادة الأولوية مع مرور الوقت).

Advanced Queuing الاصطفاف المتقدم (Advanced Queuing)

Multilevel Queue

Ready queue is partitioned into separate queues (e.g., foreground/interactive, background/batch).
Each queue has its own scheduling algorithm.
Scheduling must be done between queues (Fixed priority or Time slice). يتم تقسيم طابور الجاهزية إلى طوابير منفصلة (مثل: الأمامية/التفاعلية، الخلفية/الدفعية).
كل طابور له خوارزمية جدولة خاصة به.
يجب أن تتم الجدولة بين الطوابير (أولوية ثابتة أو شريحة زمنية).

Multilevel Feedback Queue

A process can move between queues.
If a process uses too much CPU time $\to$ move to lower priority queue.
If a process waits too long in lower priority queue $\to$ move to higher priority (Aging).
Most complex and general algorithm. يمكن للعملية الانتقال بين الطوابير.
إذا استخدمت العملية وقتاً كبيراً من الـ CPU $\to$ تنتقل لطابور أولوية أقل.
إذا انتظرت العملية طويلاً في طابور أولوية منخفضة $\to$ تنتقل لأولوية أعلى (Aging).
الخوارزمية الأكثر تعقيداً وشمولاً.

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: SJF Prediction فخ: تنبؤ SJF

SJF is optimal, but we cannot know the length of the next CPU burst. We can only estimate it using exponential averaging:
$\tau_{n+1} = \alpha t_n + (1 - \alpha)\tau_n$
(New Estimate = $\alpha \times$ Actual Last + $(1-\alpha) \times$ Old Estimate). SJF مثالية، لكننا لا نستطيع معرفة طول دفق الـ CPU التالي. يمكننا فقط تقديره باستخدام المتوسط الأسي (exponential averaging).

TRAP: Turnaround Time Calculation فخ: حساب Turnaround Time

Turnaround Time = Completion Time - Arrival Time.
Waiting Time = Turnaround Time - Burst Time.
Don't just sum up the waiting periods; using the formula is safer and faster. Turnaround Time = وقت الانتهاء - وقت الوصول.
Waiting Time = Turnaround Time - وقت الـ Burst.
لا تقم فقط بجمع فترات الانتظار؛ استخدام المعادلة أكثر أماناً وسرعة.

SECRET: FCFS Convoy Effect سر: تأثير القافلة في FCFS

If a CPU-bound process arrives first, all I/O-bound processes pile up behind it, leaving the I/O devices idle. When the CPU-bound process finally does I/O, the CPU sits idle. This lowers both CPU and I/O utilization. إذا وصلت عملية CPU-bound أولاً، تتكدس جميع عمليات I/O-bound خلفها، مما يترك أجهزة I/O خاملة. عندما تقوم عملية الـ CPU-bound أخيراً بعمل I/O، يظل الـ CPU خاملاً. هذا يخفض استخدام كلاً من الـ CPU والـ I/O.

KEY CONCEPT: Context Switch مفهوم أساسي: Context Switch

Context Switch time is overhead. The system does no useful work. It depends on hardware support (multiple register sets). وقت تبديل السياق هو overhead. النظام لا يقوم بأي عمل مفيد. يعتمد على دعم الأجهزة (مجموعات سجلات متعددة).