Cpu Scheduling

14 min read2,668 words

CPU Scheduling

What is CPU Scheduling?

CPU scheduling is the process by which the operating system selects one process from the ready queue and allocates the CPU to it.

CPU Scheduling = Deciding which ready process gets the CPU next.

Ready Queue ┌────┬────┬────┬────┐ │ P1 │ P2 │ P3 │ P4 │ └────┴────┴────┴────┘ | ↓ CPU Scheduler | ↓ Selected P2 | ↓ CPU

CPU scheduling is especially important in multiprogramming and multitasking systems, where many processes compete for CPU time.

1. Why CPU Scheduling Is Needed

Suppose four processes are ready:

P1 P2 P3 P4

But only one CPU core is available:

P1 ─┐ P2 ─┤ P3 ─┼──→ CPU P4 ─┘

The OS must determine:

  • Which process runs first?
  • How long should it run?
  • When should it be interrupted?
  • Which process should run next?

These decisions are made using CPU scheduling algorithms.

2. CPU-I/O Burst Cycle

A process normally alternates between CPU work and I/O operations.

CPU Burst ↓ I/O Burst ↓ CPU Burst ↓ I/O Burst ↓ CPU Burst ↓ Termination

CPU Burst

Time during which a process is actively using the CPU.

I/O Burst

Time during which a process performs or waits for I/O.

For example:

Process ↓ Calculate something ↓ Read from disk ↓ Calculate ↓ Network request ↓ Calculate

When one process is waiting for I/O, the OS can give the CPU to another ready process.

3. CPU Scheduling Objectives

A good CPU scheduling algorithm tries to achieve several goals.

1. Maximize CPU Utilization

Keep the CPU busy as much as possible.

CPU utilization = 95%

is generally better than:

CPU utilization = 50%

2. Maximize Throughput

Throughput = number of processes completed per unit of time.

For example:

20 processes / second

Higher throughput is generally desirable.

3. Minimize Turnaround Time

Turnaround time is the total time from process arrival/submission until completion.

Turnaround Time = Completion Time − Arrival Time

4. Minimize Waiting Time

Waiting time is the time a process spends waiting in the ready queue.

Ready Queue ↓ waiting ↓ CPU

5. Minimize Response Time

Response time is the time from arrival until the process first receives CPU service.

Response Time = First CPU Start Time − Arrival Time

This is especially important for interactive systems.

6. Ensure Fairness

The scheduler should avoid indefinitely ignoring processes.

4. Important CPU Scheduling Terms

Before learning algorithms, understand these terms.

Arrival Time (AT)

The time at which a process enters the ready queue.

Example:

P1 → AT = 0 P2 → AT = 2 P3 → AT = 4

Burst Time (BT)

The amount of CPU time required by a process for a particular CPU burst.

Example:

P1 → BT = 5 ms

means P1 needs 5 ms of CPU time for that burst.

Completion Time (CT)

The time at which a process finishes execution.

Turnaround Time (TAT)

TAT = CT − AT

Waiting Time (WT)

For the standard single-CPU scheduling calculations:

WT = TAT − BT

Therefore:

WT = CT − AT − BT

Response Time (RT)

RT = First Start Time − Arrival Time

5. Gantt Chart

A Gantt chart is used to represent CPU scheduling visually.

Example:

0 5 8 10 |-------|-------|-------| P1 P2 P3

Meaning:

0–5 → P1 5–8 → P2 8–10 → P3

Gantt charts are extremely important when solving scheduling problems.

6. Preemptive vs Non-Preemptive Scheduling

CPU scheduling algorithms can be classified as:

CPU Scheduling | +── Non-Preemptive | └── Preemptive

Non-Preemptive Scheduling

Once a process gets the CPU, the OS normally lets it continue until:

  • It terminates
  • It blocks for I/O
  • It voluntarily gives up the CPU

Example:

P1 running ↓ P1 continues ↓ P1 finishes ↓ P2 runs

Common examples:

  • FCFS
  • Non-preemptive SJF
  • Non-preemptive Priority

Preemptive Scheduling

The OS can interrupt a running process and assign the CPU to another process.

P1 running ↓ Interrupt ↓ P1 paused ↓ P2 runs

Common examples:

  • SRTF
  • Round Robin
  • Preemptive Priority

7. Major CPU Scheduling Algorithms

The important algorithms are:

CPU Scheduling Algorithms | ├── FCFS ├── SJF ├── SRTF ├── Priority ├── Round Robin ├── Multilevel Queue └── Multilevel Feedback Queue

Let's understand each.

8. FCFS — First-Come, First-Served

FCFS is one of the simplest scheduling algorithms.

The process that arrives first gets the CPU first.

It is normally non-preemptive.

Example:

ProcessArrival TimeBurst Time
P105
P213
P322

Arrival order:

P1 → P2 → P3

Therefore:

0 5 8 10 |-------|-------|-------| P1 P2 P3

Advantages of FCFS

  • Very simple
  • Easy to implement
  • Fair according to arrival order
  • No starvation in the basic form

Disadvantages

  • Poor average waiting time in some workloads
  • Poor response time for short jobs behind long jobs
  • Can suffer from the convoy effect

9. Convoy Effect

Suppose a long process arrives first:

P1 = 20 ms P2 = 2 ms P3 = 2 ms P4 = 1 ms

FCFS:

0 20 22 24 25 |--------------------|----|----|----| P1 P2 P3 P4

P2, P3 and P4 are very short, but they have to wait for P1.

This is called the:

Convoy Effect

10. SJF — Shortest Job First

Shortest Job First selects the process with the smallest CPU burst.

Shortest CPU burst gets selected first.

Example:

ProcessBurst Time
P18
P23
P35

Order:

P2 → P3 → P1

Gantt chart:

0 3 8 16 |---|-------|---------------| P2 P3 P1

Advantage

SJF can produce a very low average waiting time when burst times are known accurately.

Disadvantage

The OS generally cannot know the exact future CPU burst length in advance.

Also, long processes may experience starvation if short processes keep arriving.

11. SRTF — Shortest Remaining Time First

SRTF is the preemptive version of SJF.

The process with the shortest remaining CPU time gets the CPU.

Suppose:

P1 → remaining 7 ms P2 → remaining 3 ms

P2 gets the CPU because:

3 < 7

If a new shorter process arrives while another process is running, the current process can be preempted.

P1 running ↓ P2 arrives ↓ P2 has shorter remaining time ↓ P1 paused ↓ P2 runs

12. SJF vs SRTF

SJFSRTF
Usually non-preemptivePreemptive
Shortest burst selectedShortest remaining time selected
Running process normally continuesRunning process can be interrupted
SimplerMore complex
Can cause starvationCan also cause starvation

Memory trick:

SJF → Shortest Job
SRTF → Shortest Remaining Time

13. Priority Scheduling

Each process has a priority.

The scheduler selects the process with the highest priority according to the system's priority convention.

Example:

ProcessPriority
P13
P21
P32

If 1 means highest priority:

P2 → P3 → P1

Priority scheduling can be:

  • Preemptive
  • Non-preemptive

14. Starvation

A low-priority process may wait for a very long time if higher-priority processes keep arriving.

High Priority → CPU High Priority → CPU High Priority → CPU High Priority → CPU ↓ Low Priority → Still waiting

This is called:

Starvation

15. Aging

Aging is a technique used to reduce starvation.

The priority of a waiting process is gradually increased.

Example:

Initially: P4 → Priority 10 After waiting: P4 → Priority 8 After more waiting: P4 → Priority 5 Later: P4 → Priority 1

Eventually, the process becomes important enough to receive CPU time.

Aging prevents starvation by gradually increasing the priority of waiting processes.

16. Round Robin (RR)

Round Robin is one of the most important preemptive scheduling algorithms.

It is commonly associated with time-sharing systems.

Each process gets a fixed amount of CPU time called a:

Time Quantum

Example:

Time Quantum = 2 ms

Processes:

P1 → P2 → P3 → P1 → P2 → ...

Example:

0 2 4 6 8 10 |----|----|----|----|----| P1 P2 P3 P1 P2

After its quantum expires, a process that still needs CPU time is generally placed back into the ready queue.

17. Round Robin Example

Suppose:

ProcessBurst Time
P15
P23
P32

Time quantum:

2 ms

Execution:

0 2 4 6 8 9 10 |----|----|----|----|----|-----| P1 P2 P3 P1 P2 P1

Explanation:

0–2 → P1 2–4 → P2 4–6 → P3 finishes 6–8 → P1 8–9 → P2 finishes 9–10 → P1 finishes

18. Effect of Time Quantum

The time quantum is very important.

Very large quantum

Round Robin starts behaving similarly to FCFS.

Large Quantum ↓ Less preemption ↓ More like FCFS

Very small quantum

There can be many context switches.

Very Small Quantum ↓ Many Context Switches ↓ Higher Overhead

Therefore, the time quantum should be chosen appropriately.

19. Multilevel Queue Scheduling

Processes are divided into different queues based on characteristics such as process type or priority.

Example:

Ready Processes | +--------------+--------------+ ↓ ↓ Interactive Queue Batch Queue ↓ ↓ Round Robin FCFS

For example:

Queue 1 → System processes Queue 2 → Interactive processes Queue 3 → Batch processes

Each queue can have its own scheduling algorithm.

20. Multilevel Feedback Queue

Multilevel Feedback Queue (MLFQ) is more flexible.

Processes can move between queues depending on their behavior.

High Priority ┌─────────────┐ │ Queue 1 │ └──────┬──────┘ ↓ ┌─────────────┐ │ Queue 2 │ └──────┬──────┘ ↓ ┌─────────────┐ │ Queue 3 │ └─────────────┘ Low Priority

For example:

  • CPU-intensive processes may move to lower-priority queues.
  • Interactive/short processes may remain in higher-priority queues.
  • Aging can be used to prevent starvation.

21. Scheduling Algorithm Comparison

AlgorithmPreemptive?Main IdeaMain Problem
FCFSUsually NoFirst arrival firstConvoy effect
SJFNoShortest burst firstStarvation / burst prediction
SRTFYesShortest remaining timeStarvation / overhead
PriorityEitherHighest priority firstStarvation
Round RobinYesFixed time quantumQuantum selection
Multilevel QueueUsually dependsSeparate queuesInflexibility/starvation
MLFQYesProcesses can move between queuesComplexity

22. Important Scheduling Formulas

These formulas are extremely important for numerical questions.

Turnaround Time

TAT = Completion Time − Arrival Time

Waiting Time

WT = Turnaround Time − Burst Time

Therefore:

WT = CT − AT − BT

Response Time

RT = First Start Time − Arrival Time

23. Average Waiting Time

If there are n processes:

Average Waiting Time = Sum of Waiting Times / Number of Processes

Example:

P1 = 2 ms P2 = 4 ms P3 = 6 ms

Then:

Average WT = (2 + 4 + 6) / 3 = 12 / 3 = 4 ms

24. Average Turnaround Time

Similarly:

Average TAT = Sum of Turnaround Times / Number of Processes

25. Context Switching in CPU Scheduling

When the scheduler changes the running process:

P1 Running ↓ Save P1 context ↓ Load P2 context ↓ P2 Running

This is called a context switch.

Context switching consumes CPU time.

Therefore:

More context switches ↓ More overhead ↓ Potentially lower performance

26. Dispatcher Latency

Dispatcher latency is the time required for the dispatcher to stop one process and start another.

Scheduler selects P2 ↓ Dispatcher ↓ Context switch ↓ P2 starts

Lower dispatcher latency is desirable, especially for interactive systems.

27. CPU Scheduling Example

Let's solve a basic FCFS problem.

Given:

ProcessATBT
P105
P213
P322

FCFS order:

P1 → P2 → P3

Gantt chart:

0 5 8 10 |-------|-------|-------| P1 P2 P3

P1

CT = 5 TAT = 5 − 0 = 5 WT = 5 − 5 = 0 RT = 0 − 0 = 0

P2

CT = 8 TAT = 8 − 1 = 7 WT = 7 − 3 = 4 RT = 5 − 1 = 4

P3

CT = 10 TAT = 10 − 2 = 8 WT = 8 − 2 = 6 RT = 8 − 2 = 6

Therefore:

Average Waiting Time = (0 + 4 + 6) / 3 = 10 / 3 ≈ 3.33 ms
Average Turnaround Time = (5 + 7 + 8) / 3 = 20 / 3 ≈ 6.67 ms

28. What Makes a Good CPU Scheduling Algorithm?

A good algorithm tries to:

Good Scheduler | +-------------+-------------+ ↓ ↓ ↓ Low Waiting Low Response High Throughput | ↓ Low Turnaround | ↓ High CPU Utilization | ↓ Fairness

But there is no single algorithm that is best for every workload.

For example:

  • FCFS → simple
  • SJF → good average waiting time under suitable assumptions
  • Round Robin → good for interactive systems
  • Priority → useful when tasks have different importance
  • MLFQ → flexible but more complex

29. CPU Scheduling vs Process Scheduling

These terms are closely related.

Process Scheduling

A broader concept involving the management and selection of processes.

CPU Scheduling

Specifically focuses on:

Selecting a ready process to execute on the CPU.

So:

Process Scheduling ↓ CPU Scheduling ↓ Select Ready Process ↓ CPU

30. Complete CPU Scheduling Flow

Processes | ↓ Ready Queue | ↓ ┌─────────────────┐ │ CPU Scheduler │ └────────┬────────┘ ↓ Select Process | ↓ Dispatcher | ↓ Context Switch | ↓ CPU | +------+------+ | | I/O Wait Finish | | ↓ ↓ Waiting Terminated | ↓ Ready Queue

🧠 Quick Revision

Remember the major algorithms:

FCFS ↓ First arrival first SJF ↓ Shortest job first SRTF ↓ Shortest remaining time Priority ↓ Highest priority first Round Robin ↓ Fixed time quantum Multilevel Queue ↓ Separate fixed queues MLFQ ↓ Processes can move between queues

Most important exam points

  1. CPU scheduling selects a ready process for CPU execution.
  2. FCFS is generally non-preemptive.
  3. SJF selects the shortest CPU burst.
  4. SRTF is the preemptive form of SJF.
  5. Priority scheduling selects according to priority.
  6. Round Robin uses a time quantum and is preemptive.
  7. Starvation can occur when a process waits indefinitely.
  8. Aging helps prevent starvation.
  9. Context switching introduces overhead.
  10. Important formulas:
  • TAT = CT − AT
  • WT = TAT − BT
  • RT = First Start Time − AT
  1. Important performance criteria:
  • CPU utilization
  • Throughput
  • Waiting time
  • Turnaround time
  • Response time
  • Fairness

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy