CPU Schedulingجدولة المعالج
مقدمة الفصل
ماذا ستتعلم في هذا الفصل
- Basic concepts: the CPU–I/O burst cycle, the CPU scheduler, preemptive vs nonpreemptive scheduling, the dispatcher.
- Scheduling criteria: CPU utilization, throughput, turnaround, waiting and response time.
- Scheduling algorithms: FCFS, SJF (and SRTF), priority, round robin, multilevel queues and multilevel feedback queues.
أقسام الفصل
- 1Basic concepts: CPU–I/O burst cycleالمفاهيم الأساسية: دورة الدفعات
- 2The CPU scheduler: preemptive vs nonpreemptiveمجدول المعالج: بالمقاطعة وبدونها
- 3The dispatcherالمُرسِل (Dispatcher)
- 4Scheduling criteriaمعايير الجدولة
- 5First-Come, First-Served (FCFS)الأسبق وصولًا يُخدم أولًا (FCFS)
- 6Shortest-Job-First (SJF) and SRTFالأقصر مهمة أولًا (SJF) وSRTF
- 7Predicting the next CPU burst: exponential averagingتقدير طول الدفعة التالية: المتوسط الأسي
- 8Priority schedulingالجدولة بالأولوية
- 9Round Robin (RR)التناوب الدائري (Round Robin)
- 10Multilevel queueالطوابير متعددة المستويات
- 11Multilevel feedback queueالطوابير متعددة المستويات ذات التغذية الراجعة
تلميح: استخدم أسهم لوحة المفاتيح للتنقل بين الشرائح.
CPU–I/O burst cycleدورة الدفعات
- Maximum CPU utilization is obtained with multiprogramming.
- CPU–I/O burst cycle: process execution consists of a cycle of CPU execution and I/O wait.
- CPU bursts vary greatly, but in general follow an exponential distribution: many short bursts, few long bursts (slide 6).
When does the CPU scheduler decide?قرارات الجدولة
The CPU scheduler: preemptive vs nonpreemptive
Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them.
| #رقم | The process…العملية… | Schedulingنوع الجدولة |
|---|---|---|
| 1 | Switches from running to waiting state | Nonpreemptive |
| 2 | Switches from running to ready state | Preemptive |
| 3 | Switches from waiting to ready | Preemptive |
| 4 | Terminates | Nonpreemptive |
Nonpreemptive vs preemptiveالمقاطعة وعدمها
The CPU scheduler: preemptive vs nonpreemptive
Nonpreemptiveغير قابلة للمقاطعة
- Once a process is allocated the CPU, it does not leave unless:
- 1. it has to wait (e.g., for an I/O request or for a child to terminate)
- 2. it terminates
Preemptiveقابلة للمقاطعة
- The OS can force (preempt) a process from the CPU at any time
- Say, to allocate the CPU to another higher-priority process
Preemptive is harder: it needs to maintain consistency of data shared between processes and, more importantly, kernel data structures (e.g., I/O queues) — think of a preemption while the kernel is executing a system call on behalf of a process (many OSs wait for the system call to finish).
The dispatcherالمُرسِل
The module that gives control of the CPU to the process selected by the short-term scheduler.
This involves
- 1
Switching context
- 2
Switching to user mode
- 3
Jumping to the proper location in the user program to restart that program
Time it takes for the dispatcher to stop one process and start another running.
Scheduling criteriaمعايير الجدولة
| Criterionالمعيار | Definition (slide 10)التعريف | Goalالهدف |
|---|---|---|
| CPU utilization | Keep the CPU as busy as possible | Maximize |
| Throughput | # of processes that complete their execution per time unit | Maximize |
| Turnaround time | Amount of time to execute a particular process (time from submission to termination) | Minimize |
| Waiting time | Amount of time a process has been waiting in the ready queue | Minimize |
| Response time | Time from when a request is submitted until the first response is produced, not output (for timesharing environment) | Minimize |
- In most cases we optimize the average measure; sometimes the min or max — e.g., minimize the max response time so all users get good service (slide 11).
FCFS and the convoy effectFCFS
First-Come, First-Served (FCFS)
المسألة
P1 = 24, P2 = 3, P3 = 3 arrive in the order P1, P2, P3 (slide 13).
خطوات الحل
- Gantt chart: P1 0–24, P2 24–27, P3 27–30.
- Waiting time: P1 = 0, P2 = 24, P3 = 27.
النتيجة
Average waiting time = (0 + 24 + 27)/3 = 17.
المسألة
The same processes arrive in the order P2, P3, P1 (slide 14).
خطوات الحل
- Gantt chart: P2 0–3, P3 3–6, P1 6–30.
- Waiting time: P1 = 6, P2 = 0, P3 = 3.
النتيجة
Average waiting time = (6 + 0 + 3)/3 = 3 — much better. Convoy effect: short process behind long process.
المسألة
FCFS with arrival times (slide 15): P1 burst 7, arrives 0; P2 burst 12, arrives 3; P3 burst 2, arrives 6.
خطوات الحل
- Gantt chart: Job 1 runs 0–7, Job 2 runs 7–19, Job 3 runs 19–21.
- Waiting times: P1 = 0, P2 = 7 − 3 = 4, P3 = 19 − 6 = 13.
النتيجة
Average waiting time = (0 + 4 + 13) / 3 = 5.6 time unit (as printed on the slide).
FCFS: fairness and drawbacksتقييم FCFS
First-Come, First-Served (FCFS)
- FCFS is fair in the formal sense or human sense of fairness…
- …but unfair in the sense that long jobs take priority over short jobs and unimportant jobs make important jobs wait.
- Major drawback: the waiting time and the average turnaround time is often quite long.
- Not useful in scheduling interactive users because it cannot guarantee good response time.
- The code for FCFS scheduling is simple to write and understand.
Shortest-Job-First (SJF)SJF
Associate with each process the length of its next CPU burst; schedule the process with the shortest time.
Nonpreemptiveغير قابلة للمقاطعة
- Once the CPU is given to the process it cannot be preempted until it completes its CPU burst.
Preemptive (SRTF)قابلة للمقاطعة
- If a new process arrives with CPU burst length less than the remaining time of the current process, preempt.
- Known as Shortest-Remaining-Time-First (SRTF).
- SJF is optimal — gives minimum average waiting time for a given set of processes.
- The difficulty is knowing the length of the next CPU request.
المسألة
All at time 0: P1 = 6, P2 = 8, P3 = 7, P4 = 3 (slide 19).
خطوات الحل
- Order by burst: P4 (0–3), P1 (3–9), P3 (9–16), P2 (16–24).
- Waiting: P1 = 3, P2 = 16, P3 = 9, P4 = 0.
النتيجة
Average waiting time = (3 + 16 + 9 + 0)/4 = 7.
SJF with arrival times: nonpreemptive vs SRTFSJF وSRTF
Shortest-Job-First (SJF) and SRTF
| Processالعملية | Arrival timeزمن الوصول | Burst timeزمن الدفعة |
|---|---|---|
| P1 | 0.0 | 7 |
| P2 | 2.0 | 4 |
| P3 | 4.0 | 1 |
| P4 | 5.0 | 4 |
المسألة
Nonpreemptive SJF (slide 20).
خطوات الحل
- P1 runs 0–7 (only P1 has arrived at 0).
- At 7 the shortest waiting job is P3 (7–8), then P2 (8–12), then P4 (12–16).
- Waiting: P1 = 0, P2 = 8 − 2 = 6, P3 = 7 − 4 = 3, P4 = 12 − 5 = 7.
النتيجة
Average waiting time = (0 + 6 + 3 + 7)/4 = 4.
المسألة
Preemptive SJF — SRTF (slide 24).
خطوات الحل
- P1 0–2; P2 arrives (4 < 5 remaining) → P2 2–4; P3 arrives (1 < 2 remaining) → P3 4–5.
- P2 5–7, P4 7–11, P1 11–16.
- Waiting: P1 = 9, P2 = 1, P3 = 0, P4 = 2.
النتيجة
Average waiting time = (9 + 1 + 0 + 2)/4 = 3.
Predicting the next CPU burstالمتوسط الأسي
المسألة
Exponential averaging (slide 21).
المعطيات
- tₙ
- actual length of the nth CPU burst
- τₙ₊₁
- predicted value for the next CPU burst
- α
- 0 ≤ α ≤ 1
الصيغة
τₙ₊₁ = α tₙ + (1 − α) τₙ
النتيجة
The next burst is estimated from the length of previous CPU bursts.
α = 0
- τₙ₊₁ = τₙ
- Recent history does not count
α = 1
- τₙ₊₁ = tₙ
- Only the actual last CPU burst counts
- Since both α and (1 − α) are ≤ 1, each successive term has less weight than its predecessor (slide 23).
Priority schedulingالأولوية
- A priority number (integer) is associated with each process; the CPU goes to the highest priority (smallest integer ≡ highest priority); preemptive or nonpreemptive.
- SJF is a priority scheduling where priority is the predicted next CPU burst time.
Low-priority processes may never execute.
As time progresses, increase the priority of the process.
المسألة
Nonpreemptive priority, all arrive at 0 (slide 26): P1 10 (pr. 3), P2 1 (pr. 1), P3 2 (pr. 4), P4 1 (pr. 5), P5 5 (pr. 2).
خطوات الحل
- Order by priority: P2 (0–1), P5 (1–6), P1 (6–16), P3 (16–18), P4 (18–19).
- Waiting: P1 = 6, P2 = 0, P3 = 16, P4 = 18, P5 = 1.
النتيجة
Average waiting time = (6 + 0 + 16 + 18 + 1)/5 = 8.2.
Round Robin (RR)التناوب الدائري
- Each process gets a small unit of CPU time (time quantum), usually 10–100 milliseconds; after it elapses, the process is preempted and added to the end of the ready queue.
- n processes, quantum q → each gets 1/n of the CPU time in chunks of at most q; no process waits more than (n − 1)q time units.
- Performance: q large ⇒ FIFO; q small ⇒ q must be large with respect to context switch, otherwise overhead is too high.
المسألة
RR with q = 4: P1 = 24, P2 = 3, P3 = 3 (slide 28).
خطوات الحل
- P1 0–4, P2 4–7, P3 7–10.
- Only P1 remains: 10–14, 14–18, 18–22, 22–26, 26–30.
النتيجة
Typically, higher average turnaround than SJF, but better response.
Time quantum and context switch timeالكم وتبديل السياق
Round Robin (RR)
| Quantumالكم | Context switchesعدد تبديلات السياق |
|---|---|
| 12 | 0 |
| 6 | 1 |
| 1 | 9 |
Multilevel queueالطوابير متعددة المستويات
- The ready queue is partitioned into separate queues, e.g., foreground (interactive) and background (batch).
- Each queue has its own scheduling algorithm: foreground — RR; background — FCFS.
Fixed priority preemptiveأولوية ثابتة
- Serve all from foreground, then from background
- Possibility of starvation
Time sliceتقسيم الوقت
- Each queue gets a certain amount of CPU time to schedule amongst its processes
- E.g., 80% to foreground in RR, 20% to background in FCFS
Multilevel feedback queueالتغذية الراجعة
- A process can move between the various queues; aging can be implemented this way.
Example: Q0 (RR, 8 ms), Q1 (RR, 16 ms), Q2 (FCFS) — slide 33
- 1
A new job enters Q0; when it gains the CPU it receives 8 ms.
- 2
If it does not finish in 8 ms, it is moved to Q1, served RR, and receives 16 additional ms.
- 3
If it still does not complete (in 24 ms), it is preempted and moved to Q2.
- 4
At Q2 the job is served FCFS.
Notes (slide 34)
- Short processes get served faster (higher priority) → more responsive.
- Long processes (CPU bound) sink to the bottom → served FCFS → more throughput.
Parameters of a multilevel feedback queueمعاملات المجدول
- 1Number of queues
- 2Scheduling algorithms for each queue
- 3Method used to determine when to upgrade a process
- 4Method used to determine when to demote a process
- 5Method used to determine which queue a process will enter when that process needs service
الخلاصة
أنهيت الدرس
الخطوة التالية: ثبّت المعلومات بالبطاقات، ثم اختبر نفسك بالأسئلة.
ما راجعته في هذا الدرس
- Basic concepts: CPU–I/O burst cycleالمفاهيم الأساسية: دورة الدفعات
- The CPU scheduler: preemptive vs nonpreemptiveمجدول المعالج: بالمقاطعة وبدونها
- The dispatcherالمُرسِل (Dispatcher)
- Scheduling criteriaمعايير الجدولة
- First-Come, First-Served (FCFS)الأسبق وصولًا يُخدم أولًا (FCFS)
- Shortest-Job-First (SJF) and SRTFالأقصر مهمة أولًا (SJF) وSRTF
- Predicting the next CPU burst: exponential averagingتقدير طول الدفعة التالية: المتوسط الأسي
- Priority schedulingالجدولة بالأولوية
- Round Robin (RR)التناوب الدائري (Round Robin)
- Multilevel queueالطوابير متعددة المستويات
- Multilevel feedback queueالطوابير متعددة المستويات ذات التغذية الراجعة