CPU SCHEDULING

ALGORITHMS

First Come First Served · Round Robin

A Deep Dive into Process Scheduling with C Implementations

What is CPU Scheduling?

Definition

CPU scheduling is the process by which the OS decides which process in the ready queue gets CPU time next.

​

Goal:

Maximize CPU utilization, minimize waiting time, and ensure fairness.

​

The scheduler runs whenever a process:

▸ Arrives and is ready to run

▸ Finishes its CPU burst

▸ Is preempted (in preemptive algorithms)

Non-Preemptive

Once a process starts, it runs to completion.

Ex: FCFS, SJF (non-preemptive)

Preemptive

CPU can be taken away mid-burst and given

to another process. Ex: Round Robin, SRTF

Key Metrics Used in Both Algorithms

Arrival Time (AT)

The moment a process enters the ready queue. Processes may not arrive at time 0. The scheduler must respect this boundary.

Burst Time (BT)

The total CPU time required by a process from start to finish. Generated randomly in our code: rand()%10+1 (1–10 units).

Waiting Time (WT)

Total time a process spends waiting in the ready queue before it gets CPU.

WT = Turnaround Time − Burst Time

Turnaround Time (TAT)

Total time from arrival to completion.

TAT = Completion Time − Arrival Time

TAT = WT + BT

SECTION 01

First Come, First Served

FCFS

The simplest scheduling algorithm — processes are executed in the order they arrive.

FCFS — How It Works

1

Generate Processes

Create N processes with random Arrival Time (0–19) and Burst Time (1–10) using rand().

2

Sort by Arrival Time

Use bubble sort to order all processes so the earliest-arriving process is first.

3

Advance Clock

Start current_time = 0. If CPU is idle when next process arrives, jump clock forward to that arrival.

4

Calculate Waiting Time

WT = current_time − arrival_time. The process waited from when it arrived until the CPU was free.

5

Update Clock & TAT

current_time += burst_time. TAT = current_time − arrival_time. Move to next process.

6

Output Results

Print the table and average WT / TAT across all N processes.

FCFS — Random Generation & Sorting

// Generate random values

for (int i = 0; i < N; i++) {

arrival_time[i] = rand() % 20; // 0–19

burst_time[i] = rand() % 10 + 1; // 1–10

}

​

// Bubble-sort by arrival time

for (int i = 0; i < N-1; i++)

for (int j = 0; j < N-i-1; j++)

if (arrival_time[j] > arrival_time[j+1]) {

swap(arrival_time[j], arrival_time[j+1]);

swap(burst_time[j], burst_time[j+1]);

}

Why sort?

FCFS is non-preemptive, so it processes jobs in arrival order. Sorting ensures we simulate a real-world FIFO queue.

Key points:

▸ rand() seeded with time(NULL) → different values every run

▸ Both arrays swapped together to keep data aligned

▸ O(N²) bubble sort — fine for small N

FCFS — Core Calculation Loop

int current_time = 0;

​

for (int i = 0; i < N; i++) {

​

// CPU idle gap: jump to arrival

if (current_time < arrival_time[i])

current_time = arrival_time[i];

​

// Waiting = time spent in queue

waiting_time[i] = current_time

- arrival_time[i];

​

// Run the process

current_time += burst_time[i];

​

// Total time = finish - arrival

turnaround_time[i] = current_time

- arrival_time[i];

}

Idle CPU Handling

If no process has arrived yet, skip clock forward to the next arrival. Avoids negative waiting times.

Waiting Time = 0 for P1

The first process (if arriving at time 0) has WT = 0 since current_time == arrival_time.

No Preemption

Once a process starts (current_time += burst_time), it runs uninterrupted to completion.

FCFS — Worked Example

Gantt Chart

P1

P2

P3

P4

P5

0

4

7

12

14

17

Trace

t=0: P1 arrives, starts (no wait)

t=1: P2 arrives, waits in queue

t=2: P3 arrives, waits in queue

t=4: P1 done. P2 starts. WT=3

t=4: P4 arrives, waits in queue

t=6: P5 arrives, waits in queue

t=7: P2 done. P3 starts. WT=5

t=12: P3 done. P4 starts. WT=8

t=14: P4 done. P5 starts. WT=7

t=17: P5 done. All finished.

Avg WT: 4.60

Avg TAT: 8.00

FCFS — Advantages & Disadvantages

✓ Advantages

Simple to implement

Just sort by arrival time — no complex state.

No starvation

Every process eventually gets the CPU.

Low overhead

No preemption means no context-switch overhead.

Fair in arrival order

Processes served strictly FIFO.

✗ Disadvantages

Convoy Effect

Short processes stuck behind a long one — all wait unnecessarily.

High average WT

If a long process arrives first, all others suffer.

Not suitable for interactive

Unresponsive for time-sharing systems.

No priority awareness

Urgent processes wait like any other.

SECTION 02

Round Robin

RR

Each process gets a fixed CPU time slice (Quantum = 3). If not done, it goes back to the queue.

Round Robin — How It Works

1

Generate & Sort

Same as FCFS: generate random AT/BT and sort by arrival. Also copy BT → remaining_time[].

2

Outer While Loop

Loop until finished == N. Each iteration scans all processes in order — one round-robin pass.

3

Check Eligibility

A process runs only if: remaining_time[i] > 0 AND arrival_time[i] ≤ current_time.

4

Run for Quantum

If remaining > QUANTUM: subtract QUANTUM from remaining, add QUANTUM to current_time.

5

Final Burst

If remaining ≤ QUANTUM: run the rest, set remaining=0, calc TAT & WT, increment finished.

6

Idle CPU

If no process ran in a full scan (did_something=0), advance clock by 1 to wait for arrivals.

Round Robin — Core Scheduling Loop

while (finished < N) {

int did_something = 0;

​

for (int i = 0; i < N; i++) {

if (remaining[i]>0 &&

arrival[i]<=current_time) {

did_something = 1;

​

if (remaining[i] <= QUANTUM) {

current_time += remaining[i];

remaining[i] = 0;

TAT[i] = current_time - AT[i];

WT[i] = TAT[i] - BT[i];

finished++;

} else {

current_time += QUANTUM;

remaining[i] -= QUANTUM;

}

}

}

if (!did_something) current_time++;

}

did_something flag

Tracks whether any process ran in this pass. If nothing ran (all waiting to arrive), the CPU idles for 1 tick.

remaining_time array

Unique to RR. Tracks leftover CPU needed per process. Initialized equal to burst_time.

Two execution paths

If remaining ≤ QUANTUM → final burst, mark done.

If remaining > QUANTUM → run for quantum, come back later.

Round Robin — Worked Example (Quantum = 3)

Gantt Chart

P1

P2

P3

P4

P5

P1

P3

0

3

6

9

11

14

15

17

Execution Trace (Q=3)

t=0: P1 runs [3 of 4] → rem=1

t=3: P2 runs [3 of 3] → done ✓

t=6: P3 runs [3 of 5] → rem=2

t=9: P4 runs [2 of 2] → done ✓

t=11: P5 runs [3 of 3] → done ✓

t=14: P1 runs [1 of 1] → done ✓

t=15: P3 runs [2 of 2] → done ✓

t=17: All processes finished.

Avg WT: 5.20

Avg TAT: 8.60

Round Robin — Advantages & Disadvantages

✓ Advantages

No Starvation

Every process gets CPU time in each cycle — no indefinite blocking.

Fair Time Sharing

Ideal for time-sharing/interactive systems.

Responsive

Bounded response time: max wait ≤ (N−1) × Quantum.

Preemptive

Handles bursts gracefully by splitting execution.

✗ Disadvantages

Quantum Sensitivity

Too small → excessive context switches. Too large → behaves like FCFS.

Higher avg TAT

Processes finish later due to frequent interruptions.

Context switch cost

Each quantum expiry = a context switch overhead.

Not priority-aware

No distinction between high and low priority jobs.

FCFS vs Round Robin — Comparison

Key Takeaways

FCFS is ideal for simple batch systems where simplicity and low overhead matter more than response time.

Round Robin excels in interactive environments, guaranteeing bounded response time at the cost of more context switches.

The Quantum value in RR is critical — tuning it for your workload is key to balancing throughput vs responsiveness.

Both algorithms use the same foundation: random process generation, bubble sort by arrival, and clock-driven simulation.

FCFS · Round Robin · C Implementation · CPU Scheduling