Chapter 5: CPU Scheduling

CS330 - Operating Systems

Scheduling Algorithms, Performance Metrics, and Analysis

5.1 Basic Concepts

CPU scheduling is the basis of multiprogrammed operating systems. By switching the CPU among processes, the OS can make the computer more productive.

CPU-I/O Burst Cycle

Process execution consists of a cycle of CPU execution and I/O wait:

  • CPU burst: When process is being executed in CPU
  • I/O burst: When process waits for I/O operation

Process execution begins with a CPU burst, followed by an I/O burst, then another CPU burst, and so on.

CPU Scheduler

The CPU scheduler selects from among the processes in the ready queue and allocates a CPU core to one of them.

Dispatcher

The dispatcher gives control of the CPU to the process selected by the scheduler. This involves:

  • Switching context
  • Switching to user mode
  • Jumping to the proper location in the user program

Dispatch latency: Time it takes for the dispatcher to stop one process and start another running.

5.2 Scheduling Criteria

⚙️ CPU Utilization

Keep the CPU as busy as possible. In real systems, should range from 40% (light load) to 90% (heavy load).

📊 Throughput

Number of processes that complete execution per time unit. Higher is better.

⏱️ Turnaround Time

Amount of time to execute a particular process. Sum of periods spent waiting, ready queue, executing, and doing I/O.

⏳ Waiting Time

Amount of time a process has been waiting in the ready queue.

💬 Response Time

Time from submission of request until first response is produced. Important for interactive systems.

Key Formulas:

Turnaround Time = Completion Time - Arrival Time
Waiting Time = Turnaround Time - Burst Time
Response Time = First CPU Time - Arrival Time

Optimization Criteria

Criterion Optimization Goal
CPU Utilization Maximize
Throughput Maximize
Turnaround Time Minimize
Waiting Time Minimize
Response Time Minimize

5.3 Preemptive vs Non-preemptive Scheduling

CPU scheduling decisions may take place when a process:

  1. Switches from running to waiting state (I/O request)
  2. Switches from running to ready state (interrupt)
  3. Switches from waiting to ready (I/O completion)
  4. Terminates

Non-preemptive Scheduling

  • Scheduling only under circumstances 1 and 4
  • Process keeps CPU until it releases it
  • No interruption in the middle of execution
  • Examples: FCFS, SJF (non-preemptive)

Preemptive Scheduling

  • Scheduling under all circumstances (1, 2, 3, 4)
  • Process can be interrupted
  • Better response time
  • Examples: RR, SJF (preemptive), Priority

⚠️ Important:

Virtually all modern operating systems including Windows, macOS, Linux, and UNIX use preemptive scheduling algorithms.

5.4 First-Come, First-Served (FCFS) Scheduling

FCFS Algorithm

  • Simplest CPU scheduling algorithm
  • Process that requests CPU first is allocated CPU first
  • Implemented with FIFO queue
  • Non-preemptive

Example 1: FCFS

Process Burst Time
P1 24
P2 3
P3 3

Arrival Order: P1, P2, P3

Gantt Chart:

P1
P2
P3
0
24
27
30
Process Waiting Time Turnaround Time
P1 0 24
P2 24 27
P3 27 30
Average 17 27

Convoy Effect

⚠️ Convoy Effect:

Short processes behind long process. All other processes wait for one big process to get off CPU. This effect results in lower CPU and device utilization.

📝 Practice:

If arrival order changes to P2, P3, P1:

  • Average waiting time = (6 + 0 + 3) / 3 = 3
  • Much better than previous case!

5.5 Shortest-Job-First (SJF) Scheduling

SJF Algorithm

  • Associate with each process the length of its next CPU burst
  • Schedule process with shortest burst time
  • SJF is optimal - gives minimum average waiting time
  • Can be either preemptive or non-preemptive

Two Versions:

Non-preemptive SJF

Once CPU given to process, it cannot be preempted until completes its CPU burst

Preemptive SJF (SRTF)

If new process arrives with CPU burst length less than remaining time of current process, preempt. Also known as Shortest-Remaining-Time-First

Example: Preemptive SJF

Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5

Gantt Chart (Preemptive SJF):

P1
P2
P4
P1
P3
0
1
5
10
17
26

Average waiting time = [(10-1) + (1-1) + (17-2) + (5-3)] / 4 = 26/4 = 6.5

5.6 Priority Scheduling

Priority Algorithm

  • A priority number (integer) is associated with each process
  • CPU allocated to process with highest priority
  • Convention: Smaller integer = Higher priority
  • Can be preemptive or non-preemptive

Example: Priority Scheduling

Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

Gantt Chart:

P2
P5
P1
P3
P4
0
1
6
16
18
19

⚠️ Problem - Starvation:

Low priority processes may never execute.

✅ Solution - Aging:

As time progresses, increase the priority of the process.

5.7 Round Robin (RR) Scheduling

Round Robin Algorithm

  • Each process gets small unit of CPU time (time quantum q)
  • After time elapsed, process preempted and added to end of ready queue
  • Ready queue treated as circular queue
  • Preemptive
  • Designed for time-sharing systems

Performance:

  • If q large → FIFO (FCFS)
  • If q small → Processor sharing (appears all processes run simultaneously)
  • q must be large with respect to context switch time
  • q usually 10-100 milliseconds, context switch < 10 microseconds

Example: Round Robin (q = 4)

Process Burst Time
P1 24
P2 3
P3 3

Gantt Chart (Time Quantum = 4):

P1
P2
P3
P1
P1
P1
P1
P1
0
4
7
10
14
18
22
26
30
Process Waiting Time Turnaround Time
P1 6 30
P2 4 7
P3 7 10
Average 5.66 15.66

⚠️ Time Quantum Selection:

  • Too small: Too many context switches, CPU utilization decreases
  • Too large: Becomes FCFS, poor response time
  • Rule of thumb: 80% of CPU bursts should be shorter than q

5.8 Multilevel Queue Scheduling

Ready queue is partitioned into separate queues based on process characteristics.

Multiple Queues Example:

System Processes (Highest Priority)
Interactive Processes
Interactive Editing Processes
Batch Processes
Student Processes (Lowest Priority)

Characteristics:

Multilevel Feedback Queue

Allows process to move between queues. The idea is to separate processes according to characteristics of their CPU bursts.

Example: Three Queues

Scheduling:

  1. New job enters Q0 (highest priority)
  2. Gets 8 ms; if not finished, moves to Q1
  3. At Q1 gets 16 ms; if not finished, moves to Q2
  4. Q2 is FCFS (lowest priority)

5.9 Algorithm Comparison

Algorithm Preemptive Advantages Disadvantages Best For
FCFS No Simple, Fair Convoy effect, Poor waiting time Batch systems
SJF Both Optimal average waiting time Starvation, Need to know burst time When burst times known
Priority Both Important jobs first Starvation Real-time systems
Round Robin Yes Good response time, Fair Higher turnaround time Time-sharing systems

5.10 Complete Example Problem

CS330 Exam Problem

Consider the following set of processes with arrival time 0:

Process Burst Time Priority
P1 2 2
P2 1 1
P3 8 4
P4 4 2
P5 5 3

Calculate waiting and turnaround times for:

  1. Priority Scheduling (lower number = higher priority)
  2. Round Robin (q = 2)
  3. SJF

Solution: Priority Scheduling

Order: P2 → P1 → P4 → P5 → P3

Process Waiting Time Turnaround Time
P1 1 3
P2 0 1
P3 12 20
P4 3 7
P5 7 12

Solution: Round Robin (q = 2)

Order: P1(2) → P2(1) → P3(2) → P4(2) → P5(2) → P3(2) → P4(2) → P5(2) → P3(2) → P5(1) → P3(2)

Process Waiting Time Turnaround Time
P1 0 2
P2 2 3
P3 12 20
P4 9 13
P5 13 18

Solution: SJF

Order: P2 → P1 → P4 → P5 → P3

Process Waiting Time Turnaround Time
P1 1 3
P2 0 1
P3 12 20
P4 3 7
P5 7 12

5.11 Exam-Style Practice Questions

Multiple Choice Questions

Q1. Which scheduling algorithm is non-preemptive?

  • a) FCFS
  • b) Round Robin
  • c) Priority (preemptive)
  • d) SRTF

Q2. Which scheduling algorithm gives the best average response time?

  • a) Shortest-Job First
  • b) Round Robin
  • c) FCFS
  • d) Priority Scheduling

Q3. If time quantum is too small in RR scheduling:

  • a) CPU utilization will decrease
  • b) Throughput will increase
  • c) Response time will worsen
  • d) It becomes FCFS

Q4. Which problem is associated with Priority Scheduling?

  • a) Convoy effect
  • b) Starvation
  • c) Poor response time
  • d) High overhead

Q5. SJF scheduling is optimal because it gives:

  • a) Minimum average waiting time
  • b) Maximum CPU utilization
  • c) Best response time
  • d) Maximum throughput

Short Answer Questions

Q6. Define turnaround time and throughput. (3 marks)

Answer:

  • Turnaround time: The interval from time of submission of a process to the time of completion.
  • Throughput: The number of processes that complete their execution per time unit.

Q7. What is the convoy effect in FCFS scheduling? (2 marks)

Answer:

Convoy effect occurs when short processes get stuck behind a long process. All other processes wait for one big process to release the CPU, resulting in lower CPU and device utilization.

Q8. How does aging solve the starvation problem in Priority Scheduling? (2 marks)

Answer:

Aging gradually increases the priority of processes that wait in the system for a long time. This ensures that even low-priority processes will eventually get high enough priority to be executed.

5.12 Key Terms and Definitions

Term Definition
CPU Burst Time process spends being executed in CPU
I/O Burst Time process spends waiting for I/O operation
CPU Scheduler Selects process from ready queue for execution
Dispatcher Gives control of CPU to selected process
Dispatch Latency Time to stop one process and start another
Preemptive Process can be interrupted during execution
Non-preemptive Process runs until completion or I/O
Time Quantum Time slice in Round Robin scheduling
Convoy Effect Short processes waiting behind long process
Starvation Process never gets CPU time
Aging Increasing priority over time
Gantt Chart Visual representation of process scheduling

5.13 Diagrams from Slides

📊 CPU-I/O Burst Cycle

[Insert diagram showing alternating CPU and I/O bursts]

📊 Dispatcher Operation

[Insert dispatcher switching diagram from slides]

📊 Multilevel Feedback Queue

[Insert multilevel queue diagram]

Note: Please provide the actual diagrams from your Chapter_5.pdf slides to replace these placeholders.