CPU Scheduling

 

1. What is CPU Scheduling? 

CPU scheduling is the policy decision of which process runs on the CPU and for how long when multiple processes are ready.

The chapter separates scheduling into:

• Mechanism → context switch, timer interrupts (already discussed earlier)

• Policy → who should run next?

The key question posed is:

How should we design scheduling policies, and what metrics should we optimize? 

---

2. Workload Assumptions (Simplified Model)

To reason about scheduling, the chapter begins with simplifying assumptions:

1. All jobs run for the same time

2. All jobs arrive at the same time

3. Jobs run to completion (non-preemptive)

4. Jobs are CPU-bound (no I/O)

5. Job run-time is known in advance

These assumptions are unrealistic, but they allow us to understand fundamental ideas before relaxing them one by one

---

3. Scheduling Metrics

3.1 Turnaround Time (Primary Metric)

Turnaround time measures how long a job takes to finish:

$${𝑇}_{𝑡𝑢𝑟𝑛𝑎𝑟𝑜𝑢𝑛𝑑}={𝑇}_{𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛}-{𝑇}_{𝑎𝑟𝑟𝑖𝑣𝑎𝑙}$$

Initially, since all jobs arrive at time 0:

$${𝑇}_{𝑡𝑢𝑟𝑛𝑎𝑟𝑜𝑢𝑛𝑑}={𝑇}_{𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛}$$

This metric focuses on system performance, not fairness

---

4. First In, First Out (FIFO / FCFS)

4.1 Algorithm

• Jobs are executed in the order they arrive

• Non-preemptive

• Simple to implement

4.2 Example (Equal Job Lengths)

Jobs A, B, C arrive together, each runs 10 seconds:

Job	Completion Time
A	10
B	20
C	30

Average turnaround time:

$$(10+20+30)\mathrm{/}3=20$$

FIFO works well only when jobs are similar in length

---

4.3 Convoy Effect (Major Problem)

If a long job arrives first, short jobs wait unnecessarily.

Example:

• A = 100 seconds

• B, C = 10 seconds each

Average turnaround time becomes 110 seconds, which is very poor.

This phenomenon is called the Convoy Effect, where short jobs get stuck behind a long one

5. Shortest Job First (SJF)

5.1 Algorithm

• Run the job with the smallest CPU burst first

• Non-preemptive

• Requires knowing job lengths in advance

5.2 Why It Works

By completing short jobs first, average turnaround time is minimized.

Using the same example:

• Run B → C → A

• Average turnaround = 50 seconds

SJF is provably optimal for minimizing turnaround time under the chapter’s assumptions

5.3 Limitation of SJF

• New short jobs arriving later must wait for a long running job

• Still suffers convoy-like behavior when arrivals are staggered

Thus we arrive upon a good approach to scheduling with SJF, but our assumptions are still fairly unrealistic. Let’s relax another. In particular, we can target assumption 2, and now assume that jobs can arrive at any time instead of all at once. What problems does this lead to?

Here we can illustrate the problem again with an example. This time, assume A arrives at t = 0 and needs to run for 100 seconds, whereas B and C arrive at t = 10 and each need to run for 10 seconds. With pure SJF, we’d get the schedule seen in Figure 7.4.

As you can see from the figure, even though B and C arrived shortly after A, they still are forced to wait until A has completed, and thus suffer the same convoy problem. Average turnaround time for these three jobs is 103.33 seconds ( 100+(110−10)+(120−10) /3 ).

6. Shortest Time to Completion First (STCF)

6.1 Algorithm

• Preemptive version of SJF-Preemptive Shortest Job First (PSJF)

• At every scheduling decision, run the job with the least remaining time

• New arrivals can preempt running jobs

6.2 Example

• A arrives at time 0 (100s)

• B, C arrive at time 10 (10s each)

STCF:

• Preempts A

• Runs B and C first

• Resumes A later

Average turnaround time improves dramatically to 50 seconds ( ((120-0)+(20-10)+(30-10))/3)

6.3 Key Insight

STCF combines:

• Optimal turnaround

• Preemption

• Better handling of late arrivals

---

7. A New Metric: Response Time

7.1 Definition

Response time measures how quickly a job starts:

$${𝑇}_{𝑟𝑒𝑠𝑝𝑜𝑛𝑠𝑒}={𝑇}_{𝑓𝑖𝑟𝑠𝑡\mathrm{\_}𝑟𝑢𝑛}-{𝑇}_{𝑎𝑟𝑟𝑖𝑣𝑎𝑙}$$

This metric is crucial for interactive systems (time-sharing, terminals)

---

7.2 Problem with SJF/STCF

If many jobs arrive together:

• Later jobs wait a long time before first execution

• Poor user experience

Thus, optimizing turnaround time hurts interactivity.

8. Round Robin (RR) Scheduling

8.1 Algorithm

• Each process runs for a fixed time slice (quantum)

• CPU cycles through ready processes

• Preemptive and fair

8.2 Example

Three jobs, quantum = 1 second:

• Execution alternates: A → B → C → A → B → C …

8.3 Strength

• Excellent response time

• Fair sharing of CPU

Average response time drops drastically compared to SJF

8.4 Weakness

• Terrible turnaround time

• Jobs finish much later than necessary

This shows a fundamental trade-off:

You cannot optimize both turnaround time and response time simultaneously

The average response time of RR is: (0+1+2)/3= 1;

 

9. Time Slice Trade-off

• Small quantum → better response, high context-switch overhead

• Large quantum → fewer switches, worse interactivity

Context switches also flush:

• CPU caches

• TLBs

• Branch predictors

This makes quantum selection critical

10. Incorporating I/O into Scheduling

Real processes perform I/O.

Key idea:

• When a process blocks for I/O → schedule another process

• Treat each CPU burst as a separate job

This allows:

• Overlap of CPU and I/O

• Higher CPU utilization

• Better responsiveness for interactive jobs

  Example: CPU Scheduling with I/O (STCF Perspective)

  Let us consider two jobs, A and B, each requiring a total of 50 ms of CPU time.
  However, the two jobs differ significantly in how they use the CPU.

  Job Characteristics

  • Job A (I/O-bound)

    • Runs for 10 ms on the CPU

    • Then issues an I/O request

    • Each I/O operation takes 10 ms

    • This pattern repeats 5 times

    • Thus, Job A consists of five 10-ms CPU bursts, separated by I/O

  • Job B (CPU-bound)

    • Uses the CPU continuously for 50 ms

    • Performs no I/O

  ---

  Naive Scheduling: Poor Resource Utilization

  Assume the scheduler runs Job A first, and then runs Job B after A completes all its CPU bursts.

  Timeline Behavior

  • Job A runs for 10 ms → blocks for I/O

  • CPU sits idle during I/O

  • Job B is not scheduled until Job A fully finishes

  This results in wasted CPU time, as shown conceptually below:

  Figure 7.8: Poor Use of Resources

  Problem

  • The CPU is idle while Job A performs I/O

  • Job B could have run during those idle periods

  • Overall system throughput is poor

  ---

  Improved Scheduling: Overlapping CPU and I/O

  A better approach is to overlap Job A’s I/O with Job B’s CPU execution.

  Key Idea

  • When Job A blocks for I/O, immediately schedule Job B

  • When A’s I/O completes, allow A to resume if appropriate

  • Treat each CPU burst as an independent scheduling unit

  ---

  Figure 7.9: Efficient Resource Utilization Through Overlap

  Benefits

  • CPU and disk are both kept busy

  • Total execution time is reduced

  • System throughput improves significantly

  ---

  Key Scheduling Insight (STCF with I/O)

  Under Shortest Time to Completion First (STCF):

  • The scheduler should not treat Job A as a single 50-ms job

  • Instead, each CPU burst of A should be treated as a separate job

  • When A blocks for I/O, it should not hold the CPU

  Important Takeaway

  Efficient scheduling must consider I/O behavior, not just total CPU time.

---

11. The Fundamental Problem: No Oracle

The OS:

• Does not know job lengths

• Cannot predict future behavior

Thus:

• SJF/STCF are impractical directly

• RR alone is inefficient

12. Summary Table

Algorithm	Preemptive	Optimizes	Major Problem
FIFO	No	Simplicity	Convoy effect
SJF	No	Turnaround	Late arrivals
STCF	Yes	Turnaround	Needs job length
RR	Yes	Response time	Poor turnaround