C#: first-come-first-served versus shortest-job-first

Before you start

C# arrays and LINQ.

Compare the average waiting time of two scheduling policies for the same set of jobs.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A CPU scheduler chooses which ready job runs next. In first-come, first-served (FCFS) scheduling, jobs run in the order they arrive. In shortest-job-first (SJF) scheduling, the job with the smallest CPU burst runs next. A job's waiting time is the time it spends in the ready queue before it first runs.

When all jobs arrive at time 0 and run to completion, SJF gives the smallest possible average waiting time, because short jobs delay fewer others. Its drawback is that long jobs can be starved if short ones keep arriving, and the burst length has to be known or predicted.

Code example

using System;
using System.Globalization;
using System.Linq;

class Program {
  static double AverageWait(int[] bursts) {
    int clock = 0, totalWait = 0;
    foreach (int burst in bursts) {
      totalWait += clock;
      clock += burst;
    }
    return (double)totalWait / bursts.Length;
  }

  static void Main() {
    int[] bursts = { 8, 4, 9, 5 };
    Console.WriteLine("FCFS average wait: " + AverageWait(bursts).ToString("F2", CultureInfo.InvariantCulture));
    int[] shortestFirst = bursts.OrderBy(b => b).ToArray();
    Console.WriteLine("SJF  average wait: " + AverageWait(shortestFirst).ToString("F2", CultureInfo.InvariantCulture));
  }
}

Output

FCFS average wait: 10.25
SJF  average wait: 7.50

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1using System;

2using System.Globalization;

3using System.Linq;

5class Program {

6 static double AverageWait(int[] bursts) {

7 int clock = 0, totalWait = 0;

8 foreach (int burst in bursts) {

9 totalWait += clock;

10 clock += burst;

11 }

12 return (double)totalWait / bursts.Length;

13 }

15 static void Main() {

16 int[] bursts = { 8, 4, 9, 5 };

17 Console.WriteLine("FCFS average wait: " + AverageWait(bursts).ToString("F2", CultureInfo.InvariantCulture));

18 int[] shortestFirst = bursts.OrderBy(b => b).ToArray();

19 Console.WriteLine("SJF average wait: " + AverageWait(shortestFirst).ToString("F2", CultureInfo.InvariantCulture));

20 }

21}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A job waits for everything that ran before it. With order 8, 4, 9, 5 the waits are 0, 8, 12, and 21.	`waits = 0, 8, 12, 21`	—
(0 + 8 + 12 + 21) / 4 = 10.25.	`waits = 0, 8, 12, 21`	FCFS average wait: 10.25
Run the short jobs first: 4, 5, 8, 9, with waits 0, 4, 9, and 17.	`waits = 0, 8, 12, 21`	FCFS average wait: 10.25
(0 + 4 + 9 + 17) / 4 = 7.50, which is better.	`waits = 0, 8, 12, 21`	FCFS average wait: 10.25 SJF average wait: 7.50

Behind the scenes

How C# processes this code

C# compiles to code for the .NET runtime, which invokes the program entry point.

Cost and common mistakes

O(n log n) for the sort, then O(n) to compute the waits.

This model assumes all jobs arrive together and nothing is preempted. Real arrivals change the result.
The preemptive version of SJF is called shortest-remaining-time-first.
Formatting with CultureInfo.InvariantCulture keeps the decimal point the same on every machine.

Try it yourself

What is the average SJF wait for bursts 3, 1, 2?

Reveal answer and reasoning

Sorted order 1, 2, 3 gives waits 0, 1, and 3, so the average is 4 / 3 ≈ 1.33.