CPU Scheduling: Practice and a C# Simulation

The lecture introduced the scheduling algorithms one by one. This section is where you get fast and accurate with them. We take one set of processes, schedule it with FCFS, SJF, SRTF, Priority (both kinds) and Round Robin, and draw every Gantt chart one decision at a time, the way a scheduling simulator does it. Then a short C# program runs the same six algorithms and prints the same charts, so you can check any answer you work out by hand.

Objectives

By the end of the section you should be able to:

• Build the Gantt chart for FCFS, SJF, SRTF, Priority (non-preemptive and preemptive) and Round Robin.
• Compute the completion time (CT), turnaround time (TAT) and waiting time (WT) of every process, and their averages.
• Apply the tie rules: equal arrival times, equal bursts, equal priorities, and the order of the Round Robin queue.
• Compute the efficiency of a schedule when every dispatch costs one unit of overhead.
• Explain starvation and aging, and describe multilevel queue and multilevel feedback queue scheduling.
• Read, run and extend a C# program that simulates these algorithms.

Part 1: the toolkit

Reading a Gantt chart

A Gantt chart shows which process holds the CPU at every moment. Here is the lecture's FCFS example: P3 arrives at 0, P1 at 4, P5 at 5, and P2 and P4 both at 6.

| P3 | idle |   P1  |  P5 |  P2 | P4 |
0    3      4       9     13    17   19

• Each box is one process holding the CPU. The numbers under the edges are clock times.
• The idle box from 3 to 4 means nobody is ready: P3 has finished and P1 has not arrived yet, so the CPU waits.
• The completion time (CT) of a process is the right edge of its last box: P1 completes at 9, P4 at 19.

Every question in this section is solved the same way: draw the chart first, then read every number off it.

Three formulas and a shortcut

TAT = CT - AT
WT  = TAT - BT
ΣTAT / n    ΣWT / n

TAT (turnaround) is everything from arrival to finish, and WT (waiting) is the part of TAT not spent running. An average is a column sum (ΣTAT or ΣWT) divided by the number of processes n.

When a process is preempted it appears in several boxes. You can then read its waiting time straight off the chart:

WT = S - R - AT
WT = S - AT - k x q

Here S is the start of its last box and R the time it ran before that box. The second line is the Round Robin form: every earlier box is a full quantum, so R = k x q, where k is the number of preemptions. Both give exactly the same WT as TAT - BT. Use one to compute and the other to check yourself.

The rules that break ties

• Same arrival time: the process with the smaller ID goes first.
• Equal burst or equal priority: fall back to FCFS, the earlier arrival first.
• Priority numbers: read the question. The lecture examples use both conventions: sometimes the lower number is the higher priority (0 is the best), sometimes the higher number is.
• Preemptive algorithms: a newcomer takes the CPU only when it is strictly better. On a tie, the running process keeps the CPU (the FCFS tie rule). None of the problems in this section contains such a tie.
• Round Robin: if a process arrives at the same moment another process's quantum ends, the new arrival joins the ready queue first and the preempted process goes behind it.

Set A: one input for every algorithm

All the worked examples use the same five processes, so you can compare the algorithms directly. Times are in milliseconds and here a lower number means a higher priority.

The total burst is 24, and no algorithm ever leaves the CPU idle on this input, so every chart ends at 24.

Part 2: FCFS and SJF

Both algorithms are non-preemptive: once a process has the CPU it keeps it until it finishes. The scheduler makes a decision only when the CPU becomes free.

FCFS and the convoy effect

First-come, first-served runs processes in arrival order, using a FIFO ready queue. It is simple, but its average waiting time depends heavily on the order. Take three processes that arrive at time 0 with bursts 18, 3 and 3:

The work is identical, yet the first order waits more than four times as long: the short processes are stuck behind the long one. This is the convoy effect.

Worked example: FCFS on Set A

Serve strictly by arrival: P1 at 0, P2 at 2, P3 at 3, P4 at 4, P5 at 6. Every process has arrived before the CPU becomes free, so there is no idle time.

|     P1    | P2 |  P3 | P4 |    P5   |
0           8    11    15   17        24

Average TAT = 60 / 5 = 12. Average WT = 36 / 5 = 7.2.

Worked example: efficiency with one unit of overhead

The lecture's second FCFS problem adds a cost to scheduling: before the CPU is given to a process, the system spends one unit of time (marked del). The same idea on Set A:

| del |   P1   | del | P2 | del | P3 | del | P4 | del |   P5  |
0     1        9     10   13    14   18    19   21    22      29

• Total time T: the last process finishes at 29.
• Wasted time D: 5 delays of 1 unit = 5.
• Useful time T - D: 29 - 5 = 24, which is exactly the total burst.

The efficiency η is the useful share of the total time:

η = (T - D) / T = 24 / 29 = 0.8276 = 82.76%

Worked example: SJF (non-preemptive) on Set A

Shortest job first gives the free CPU to the waiting process with the smallest next CPU burst; ties go to the earlier arrival. At time 0 only P1 is present, so it runs from 0 to 8, and because SJF here is non-preemptive nobody can interrupt it. At 8 all the others are waiting:

|     P1    | P4 | P2 |  P3 |    P5   |
0           8    10   13    17        24

Average TAT = 57 / 5 = 11.4. Average WT = 33 / 5 = 6.6.

P4 arrived last of the four but runs first: SJF looks at the burst, not the arrival. The average WT drops from 7.2 (FCFS) to 6.6.

Part 3: SRTF, preemptive SJF

Shortest remaining time first is SJF with preemption. At every arrival, compare the newcomer's burst with the remaining time of the running process, and switch only if the newcomer is strictly shorter. A preempted process keeps its remaining time and competes again later.

Worked example: SRTF on Set A

The trap is at time 4: P4 needs only 2, which is less than P2's full burst of 3, but P2 has just 1 unit left. Always compare with the remaining time.

| P1 | P2 | P4 |  P3 |   P1   |    P5   |
0    2    5    7     11       17        24

Waiting times with the shortcut (last start - time run before - AT):

Average TAT = 49 / 5 = 9.8. Average WT = 25 / 5 = 5.

SRTF gives the smallest average waiting time of all six algorithms on Set A (5, against 6.6 for non-preemptive SJF). The catch, as the lecture explains, is that the operating system cannot know the length of the next CPU burst. It can only predict it, assuming the next burst will be similar in length to the previous ones, and schedule by the predicted value.

Part 4: priority scheduling

Every process has a priority and the CPU goes to the highest-priority ready process; equal priorities are served FCFS. Non-preemptive priority puts a better newcomer at the head of the ready queue, where it waits for the running process to finish. Preemptive priority gives the CPU to a better newcomer at once. SJF is itself a priority algorithm whose priority is the (predicted) next CPU burst: the longer the burst, the lower the priority.

For Set A, the lower number is the higher priority: 1 is the best and 5 the worst.

Worked example: non-preemptive priority on Set A

P1 (priority 4) starts at 0 and runs to 8. P3 (priority 2) and P4 (priority 1) arrive meanwhile and are better, but they must wait: the algorithm is non-preemptive. At 8 the waiting processes run in priority order: P4 (1), P3 (2), P5 (3), P2 (5).

|     P1    | P4 |  P3 |    P5   | P2 |
0           8    10    14        21   24

Average TAT = 62 / 5 = 12.4. Average WT = 38 / 5 = 7.6.

Worked example: preemptive priority on Set A

| P1 | P3 | P4 | P3 |    P5   |   P1  | P2 |
0    3    4    6    9         16      21   24

Average TAT = 61 / 5 = 12.2. Average WT = 37 / 5 = 7.4.

Starvation and aging

P2 has the worst priority and waits 19 of the 24 units in both priority charts. With a steady stream of higher-priority arrivals it could wait forever. A ready process that never gets the CPU is blocked, and this problem is called indefinite blocking or starvation.

The fix is aging: gradually raise the priority of a process the longer it waits. In the lecture's example, priorities run from 127 (lowest) to 0 (highest) and a waiting process moves up by one every 15 minutes, so even a process that starts at 127 eventually reaches the top:

127 x 15 = 1905
1905 / 60 = 31.75

That is 1905 minutes, or 31.75 hours.

Part 5: Round Robin

Round Robin is designed for time-sharing systems. It is FCFS with preemption added through a time quantum (the lecture quotes 10 to 100 ms in real systems):

1. The ready queue is a FIFO queue; new processes join the tail.
2. The process at the head gets the CPU for at most one quantum.
3. If it needs less than a quantum, it finishes and releases the CPU voluntarily.
4. If the quantum runs out, the timer interrupts, a context switch saves its state, and it goes to the tail of the queue.
5. If a process arrives at the same moment a quantum ends, the new arrival joins the queue first and the preempted process goes behind it.

Worked example: Round Robin on Set A, q = 3

The table lists every moment the CPU or the queue changes. The queue is written head first, after the decision at that time.

The moments worth a closer look:

• t = 3: P3 arrives exactly when P1's quantum ends. P3 joins the queue first, then P1, so the queue is P3, P1 while P2 runs.
• t = 6: P2 needed only 3, so it finished inside its quantum and released the CPU.
• t = 20: P5 is alone. Its quantum ends at 23, it goes to the (empty) queue and gets the CPU straight back, which is why the chart shows two P5 boxes.

| P1 | P2 | P3 | P1 | P4 | P5 | P3 | P1 | P5 | P5 |
0    3    6    9    12   14   17   18   20   23   24

Average TAT = 67 / 5 = 13.4. Average WT = 43 / 5 = 8.6.

Check with the Round Robin shortcut, WT = last start - AT - preemptions x q:

The tie rule matters: if P1 were put back in the queue before P3 at time 3, the average WT would be 8.8 instead of 8.6.

Choosing the quantum

The same Set A with different quanta. A "process switch" here is a boundary in the chart where one process hands the CPU to a different one.

• Too large: with q = 8 no process is ever cut, and Round Robin draws exactly the FCFS chart (4 switches).
• Too small: with q = 1 the CPU switches processes 20 times; each switch is a context switch, which costs time in a real system.
• The quantum has to strike a balance between the two.

Interactive: build the chart tick by tick

Pick an algorithm, edit the process table and press Play: the Gantt chart grows one time unit at a time, with the ready queue, the reason for every decision, and the CT, TAT and WT of each process as it finishes.

Open the Gantt chart scheduler full screen

Part 6: comparing the six schedulers

SRTF has the smallest average waiting time. Round Robin has the largest average here; its strength is response time, since every waiting process gets a turn once per lap of the queue.

The second widget runs all six algorithms on the same input with one shared clock. Change the quantum, switch the priority rule or draw a random set and watch the averages move.

Open the comparison widget full screen

Part 7: multilevel queues

Multilevel queue scheduling

When processes fall into clear groups, the ready queue can be split into several queues. Each process is permanently assigned to one queue, based on a property such as its type, priority or memory size. Each queue has its own algorithm (for example, Round Robin for the interactive foreground queue and FCFS for the background queue), and there is also scheduling between the queues, usually fixed-priority preemptive: a queue runs only when every queue above it is empty, and an arrival in a higher queue preempts a process from a lower one. The lecture's example has five queues, from highest to lowest priority:

1. System processes
2. Interactive processes
3. Interactive editing processes
4. Batch processes
5. Student processes

A student process runs only when the four queues above it are all empty.

Multilevel feedback queue scheduling

The feedback version lets processes move between queues. A process that uses too much CPU time moves down; a process that waits too long in a low queue moves up, a form of aging that prevents starvation. In the lecture's example, Q0 gives a quantum of 8 ms, Q1 a quantum of 16 ms, and Q2 runs FCFS; a lower queue runs only when the queues above it are empty.

new process -> Q0 (quantum 8) --not done in 8--> Q1 (quantum 16) --not done in 16--> Q2 (FCFS)

A process with a 30 ms burst runs 8 ms in Q0, 16 ms in Q1 and its last 6 ms in Q2. A multilevel feedback queue scheduler is defined by five parameters: the number of queues, the algorithm of each queue, the method that decides when to upgrade a process, the method that decides when to demote it, and the method that decides which queue a process enters when it needs service.

Quick check

These are the exam-style questions solved in the lecture's problem video. Try them before reading the answers at the end.

1. A set of n tasks with known run times runs on one processor. Which algorithm gives the maximum throughput: Round Robin, SJF, highest response ratio next, or FCFS?
2. Which of these is non-preemptive: Round Robin, FIFO, multilevel queue, or multilevel queue with feedback?
3. True or false: SRTF may cause starvation; preemptive scheduling may cause starvation; Round Robin is better than FCFS in response time.
4. An algorithm makes priority proportional to waiting time, every process starts at priority 0, and priorities are re-evaluated every T time units. All processes arrive at 0 and do no I/O. Which algorithm is it equivalent to?

Part 8: a C# simulation

The program below schedules Set A with all six algorithms and prints each Gantt chart with its table and averages. Create a console project (in Visual Studio: a new Console App; or in a terminal: dotnet new console -n CpuScheduling), replace Program.cs with the listing at the end of this part, and run it.

The data

public class Process
{
    public string Id { get; }
    public int Arrival { get; }
    public int Burst { get; }
    public int Priority { get; }
    public int Remaining { get; set; }   // burst still to run
    public int Completion { get; set; }  // CT, set when Remaining reaches 0
    // constructor sets Remaining = burst
}
 
public record Slice(string Id, int Start, int End);

• Id, Arrival, Burst and Priority are the inputs from the question; they never change.
• Remaining drops by 1 for every time unit the process runs; SRTF ranks processes by it.
• Completion is the CT, set when Remaining reaches 0. TAT and WT are computed from it with the usual formulas.
• A Slice is one box of the Gantt chart.

One engine for FCFS, SJF, SRTF and priority

while (done < ps.Count)
{
    var ready = ps.Where(p => p.Arrival <= time && p.Remaining > 0 && p != running)
                  .OrderBy(rank).ThenBy(p => p.Arrival).ThenBy(p => p.Id).ToList();
    if (running == null)
        running = ready.FirstOrDefault();            // CPU free: take the best
    else if (preemptive && ready.Count > 0 && rank(ready[0]) < rank(running))
        running = ready[0];                          // strictly better: preempt
    AddTick(gantt, running?.Id ?? "idle", time, false);
    if (running != null && --running.Remaining == 0)
    {
        running.Completion = time + 1; running = null; done++;
    }
    time++;
}

• The clock time moves one unit per loop, exactly like stepping through the chart.
• ready holds every process that has arrived, is not finished and is not running, sorted by rank, then by arrival, then by ID: these are the tie rules.
• rank is the only thing that changes between algorithms: p => p.Arrival for FCFS, p => p.Burst for SJF, p => p.Remaining for SRTF, p => p.Priority for priority (lower is better).
• When the CPU is free the best ready process gets it. If preemptive is true, a strictly better ready process also takes the CPU from the running one.
• AddTick extends the last box by one unit or starts a new one.

Round Robin needs a real queue

foreach (var p in ps.Where(p => p.Arrival == time).OrderBy(p => p.Id))
    queue.Enqueue(p);                            // 1. new arrivals join first
if (running != null && used == quantum)
{
    queue.Enqueue(running);                      // 2. then the preempted process
    running = null;
}
bool dispatched = false;
if (running == null && queue.Count > 0)
{
    running = queue.Dequeue();                   // 3. the head gets the CPU
    used = 0;
    dispatched = true;
}

The order of steps 1 and 2 is the tie rule: processes arriving at this moment are enqueued before the process whose quantum just ended. Swap the two blocks and the program reproduces the wrong answer from Part 5.

Running it

var ps = SetA();
Report.Print("FCFS", ps, Scheduler.Run(ps, p => p.Arrival, false));
ps = SetA();
Report.Print("SJF (non-preemptive)", ps, Scheduler.Run(ps, p => p.Burst, false));
ps = SetA();
Report.Print("SRTF (preemptive SJF)", ps, Scheduler.Run(ps, p => p.Remaining, true));
ps = SetA();
Report.Print("Priority (non-preemptive)", ps, Scheduler.Run(ps, p => p.Priority, false));
ps = SetA();
Report.Print("Priority (preemptive)", ps, Scheduler.Run(ps, p => p.Priority, true));
ps = SetA();
Report.Print("Round Robin q=3", ps, Scheduler.RoundRobin(ps, 3));

SetA() builds a new list for every run, because a run changes Remaining and Completion: reusing the list would start the next algorithm with finished processes. The output:

=== FCFS
P1 0-8 | P2 8-11 | P3 11-15 | P4 15-17 | P5 17-24
P1  AT= 0  BT= 8  CT= 8  TAT= 8  WT= 0
P2  AT= 2  BT= 3  CT=11  TAT= 9  WT= 6
P3  AT= 3  BT= 4  CT=15  TAT=12  WT= 8
P4  AT= 4  BT= 2  CT=17  TAT=13  WT=11
P5  AT= 6  BT= 7  CT=24  TAT=18  WT=11
Average WT = 7.20   Average TAT = 12.00
 
=== SJF (non-preemptive)
P1 0-8 | P4 8-10 | P2 10-13 | P3 13-17 | P5 17-24
P1  AT= 0  BT= 8  CT= 8  TAT= 8  WT= 0
P2  AT= 2  BT= 3  CT=13  TAT=11  WT= 8
P3  AT= 3  BT= 4  CT=17  TAT=14  WT=10
P4  AT= 4  BT= 2  CT=10  TAT= 6  WT= 4
P5  AT= 6  BT= 7  CT=24  TAT=18  WT=11
Average WT = 6.60   Average TAT = 11.40
 
=== SRTF (preemptive SJF)
P1 0-2 | P2 2-5 | P4 5-7 | P3 7-11 | P1 11-17 | P5 17-24
P1  AT= 0  BT= 8  CT=17  TAT=17  WT= 9
P2  AT= 2  BT= 3  CT= 5  TAT= 3  WT= 0
P3  AT= 3  BT= 4  CT=11  TAT= 8  WT= 4
P4  AT= 4  BT= 2  CT= 7  TAT= 3  WT= 1
P5  AT= 6  BT= 7  CT=24  TAT=18  WT=11
Average WT = 5.00   Average TAT = 9.80
 
=== Priority (non-preemptive)
P1 0-8 | P4 8-10 | P3 10-14 | P5 14-21 | P2 21-24
P1  AT= 0  BT= 8  CT= 8  TAT= 8  WT= 0
P2  AT= 2  BT= 3  CT=24  TAT=22  WT=19
P3  AT= 3  BT= 4  CT=14  TAT=11  WT= 7
P4  AT= 4  BT= 2  CT=10  TAT= 6  WT= 4
P5  AT= 6  BT= 7  CT=21  TAT=15  WT= 8
Average WT = 7.60   Average TAT = 12.40
 
=== Priority (preemptive)
P1 0-3 | P3 3-4 | P4 4-6 | P3 6-9 | P5 9-16 | P1 16-21 | P2 21-24
P1  AT= 0  BT= 8  CT=21  TAT=21  WT=13
P2  AT= 2  BT= 3  CT=24  TAT=22  WT=19
P3  AT= 3  BT= 4  CT= 9  TAT= 6  WT= 2
P4  AT= 4  BT= 2  CT= 6  TAT= 2  WT= 0
P5  AT= 6  BT= 7  CT=16  TAT=10  WT= 3
Average WT = 7.40   Average TAT = 12.20
 
=== Round Robin q=3
P1 0-3 | P2 3-6 | P3 6-9 | P1 9-12 | P4 12-14 | P5 14-17 | P3 17-18 | P1 18-20 | P5 20-23 | P5 23-24
P1  AT= 0  BT= 8  CT=20  TAT=20  WT=12
P2  AT= 2  BT= 3  CT= 6  TAT= 4  WT= 1
P3  AT= 3  BT= 4  CT=18  TAT=15  WT=11
P4  AT= 4  BT= 2  CT=14  TAT=10  WT= 8
P5  AT= 6  BT= 7  CT=24  TAT=18  WT=11
Average WT = 8.60   Average TAT = 13.40

Every chart and every average matches the hand solutions above.

The complete program

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace CpuScheduling
{
    // One process: what the scheduler knows about it, plus two fields it fills in.
    public class Process
    {
        public string Id { get; }
        public int Arrival { get; }
        public int Burst { get; }
        public int Priority { get; }
        public int Remaining { get; set; }   // burst still to run
        public int Completion { get; set; }  // CT, set when Remaining reaches 0
 
        public Process(string id, int arrival, int burst, int priority = 0)
        {
            Id = id;
            Arrival = arrival;
            Burst = burst;
            Priority = priority;
            Remaining = burst;
        }
    }
 
    // One bar of the Gantt chart.
    public record Slice(string Id, int Start, int End);
 
    public static class Scheduler
    {
        // FCFS, SJF, SRTF and Priority share one engine. The clock moves one unit
        // at a time; "rank" says which ready process is best (smaller is better).
        public static List<Slice> Run(List<Process> ps, Func<Process, int> rank, bool preemptive)
        {
            var gantt = new List<Slice>();
            Process? running = null;
            int time = 0, done = 0;
 
            while (done < ps.Count)
            {
                var ready = ps.Where(p => p.Arrival <= time && p.Remaining > 0 && p != running)
                              .OrderBy(rank).ThenBy(p => p.Arrival).ThenBy(p => p.Id).ToList();
                if (running == null)
                    running = ready.FirstOrDefault();            // CPU free: take the best
                else if (preemptive && ready.Count > 0 && rank(ready[0]) < rank(running))
                    running = ready[0];                          // strictly better: preempt
                AddTick(gantt, running?.Id ?? "idle", time, false);
                if (running != null && --running.Remaining == 0)
                {
                    running.Completion = time + 1; running = null; done++;
                }
                time++;
            }
            return gantt;
        }
 
        // Round Robin: a FIFO ready queue and a time quantum.
        public static List<Slice> RoundRobin(List<Process> ps, int quantum)
        {
            var gantt = new List<Slice>();
            var queue = new Queue<Process>();
            Process? running = null;
            int time = 0, used = 0, done = 0;
 
            while (done < ps.Count)
            {
                foreach (var p in ps.Where(p => p.Arrival == time).OrderBy(p => p.Id))
                    queue.Enqueue(p);                            // 1. new arrivals join first
                if (running != null && used == quantum)
                {
                    queue.Enqueue(running);                      // 2. then the preempted process
                    running = null;
                }
                bool dispatched = false;
                if (running == null && queue.Count > 0)
                {
                    running = queue.Dequeue();                   // 3. the head gets the CPU
                    used = 0;
                    dispatched = true;
                }
 
                AddTick(gantt, running?.Id ?? "idle", time, dispatched);
                if (running != null)
                {
                    used++;
                    if (--running.Remaining == 0)
                    {
                        running.Completion = time + 1;
                        running = null;
                        done++;
                    }
                }
                time++;
            }
            return gantt;
        }
 
        // Extend the last bar by one unit, or start a new bar.
        static void AddTick(List<Slice> gantt, string id, int time, bool newDispatch)
        {
            if (!newDispatch && gantt.Count > 0 && gantt[^1].Id == id && gantt[^1].End == time)
                gantt[^1] = gantt[^1] with { End = time + 1 };
            else
                gantt.Add(new Slice(id, time, time + 1));
        }
    }
 
    public static class Report
    {
        public static void Print(string title, List<Process> ps, List<Slice> gantt)
        {
            Console.WriteLine($"=== {title}");
            Console.WriteLine(string.Join(" | ", gantt.Select(s => $"{s.Id} {s.Start}-{s.End}")));
 
            double sumTat = 0, sumWt = 0;
            foreach (var p in ps.OrderBy(p => p.Id))
            {
                int tat = p.Completion - p.Arrival;   // TAT = CT - AT
                int wt = tat - p.Burst;               // WT  = TAT - BT
                sumTat += tat;
                sumWt += wt;
                Console.WriteLine($"{p.Id}  AT={p.Arrival,2}  BT={p.Burst,2}  CT={p.Completion,2}  TAT={tat,2}  WT={wt,2}");
            }
            Console.WriteLine($"Average WT = {sumWt / ps.Count:0.00}   Average TAT = {sumTat / ps.Count:0.00}");
            Console.WriteLine();
        }
    }
 
    public static class Program
    {
        // Set A from the lesson. Lower priority number = higher priority.
        // A new list every call: each run changes Remaining and Completion.
        static List<Process> SetA() => new()
        {
            new("P1", 0, 8, 4),
            new("P2", 2, 3, 5),
            new("P3", 3, 4, 2),
            new("P4", 4, 2, 1),
            new("P5", 6, 7, 3),
        };
 
        public static void Main()
        {
            var ps = SetA();
            Report.Print("FCFS", ps, Scheduler.Run(ps, p => p.Arrival, false));
            ps = SetA();
            Report.Print("SJF (non-preemptive)", ps, Scheduler.Run(ps, p => p.Burst, false));
            ps = SetA();
            Report.Print("SRTF (preemptive SJF)", ps, Scheduler.Run(ps, p => p.Remaining, true));
            ps = SetA();
            Report.Print("Priority (non-preemptive)", ps, Scheduler.Run(ps, p => p.Priority, false));
            ps = SetA();
            Report.Print("Priority (preemptive)", ps, Scheduler.Run(ps, p => p.Priority, true));
            ps = SetA();
            Report.Print("Round Robin q=3", ps, Scheduler.RoundRobin(ps, 3));
        }
    }
}

Practice

About 30 minutes. Solve each problem on paper first: draw the chart, fill the table, then compute the averages. Check yourself with the Gantt chart widget or by putting the data into SetA() in the C# program. The answers are at the end.

Practice 1: FCFS with an idle CPU

Draw the FCFS Gantt chart (mark any idle time) and find CT, TAT and WT for every process, the average TAT and the average WT. Note that P3 and P4 arrive together.

Practice 2: SRTF

Schedule with preemptive SJF (SRTF). Find the average WT and the average TAT. Then schedule the same processes with non-preemptive SJF and compare.

Practice 3: preemptive priority, higher number is higher priority

In this problem a higher number means a higher priority (5 is the best). Draw the preemptive priority chart and find the average WT and the average TAT.

Practice 4: Round Robin with six processes, q = 2

Draw the chart, keeping track of the ready queue, and find the average WT and the average TAT. Pay attention to what happens at t = 7.

Practice 5 (optional, C#)

Add a method SetPractice4() to the program with the data of Practice 4, run Scheduler.RoundRobin on it with a quantum of 2, and confirm your answer. Then swap the two blocks marked 1 and 2 in RoundRobin and run it again: which process's waiting time changes, and why?

Answers

Practice 1

| P2 |  P1 | P3 | P4 | idle | P5 |
0    2     6    9    10     13   15

Average TAT = 22 / 5 = 4.4. Average WT = 10 / 5 = 2.

P3 and P4 both arrive at 3, so P3 (smaller ID) goes first. The CPU is idle from 10 to 13 waiting for P5.

Practice 2

| P1 | P2 | P1 | P4 | P1 |   P3  |
0    2    4    7    8    11      16

Average TAT = 24 / 4 = 6. Average WT = 8 / 4 = 2.

At 6, P3 needs 5 while P1 has only 4 left, so P1 keeps the CPU. With non-preemptive SJF:

|     P1    | P4 | P2 |   P3  |
0           8    9    11      16

Average TAT = 29 / 4 = 7.25. Average WT = 13 / 4 = 3.25.

Preemption lowers the average WT here because the short processes P2 and P4 no longer wait behind P1.

Practice 3

| P1 | P2 | P1 | P5 | P1 | P3 |  P4 |
0    2    4    7    10   11   14    18

Average TAT = 41 / 5 = 8.2. Average WT = 23 / 5 = 4.6.

If you read the priorities the other way round (lower number = higher priority) you get a different chart and an average WT of 6.2: always check the convention first.

Practice 4

| P1 | P2 | P1 | P3 | P4 | P5 | P3 | P6 | P4 | P5 | P3 |
0    2    4    5    7    9    11   13   15   16   18   19

Average TAT = 51 / 6 = 8.5. Average WT = 32 / 6 = 5.33.

At t = 7, P5 arrives exactly when P3's quantum ends, so P5 joins the queue before P3.

Practice 5

static List<Process> SetPractice4() => new()
{
    new("P1", 0, 3), new("P2", 1, 2), new("P3", 4, 5),
    new("P4", 6, 3), new("P5", 7, 4), new("P6", 8, 2),
};

Call it in Main with var ps = SetPractice4(); Report.Print("Practice 4, q=2", ps, Scheduler.RoundRobin(ps, 2));.

With the correct order the program prints average WT 5.33 and average TAT 8.5, the same as the hand solution. With the two blocks swapped, a preempted process re-enters the queue before the processes arriving at that moment. At t = 7, P3's quantum ends just as P5 arrives, so P3 now goes ahead of P5: P3's WT drops from 10 to 8 and P5's rises from 7 to 8, and the average WT becomes 5.17. The lecture's rule is the first order.

Quick check

1. SJF: the shortest jobs finish first, so the most processes complete per unit of time.
2. FIFO, which is another name for FCFS: a process keeps the CPU until it finishes.
3. All three are true. A long process can be passed over forever under SRTF, any preemptive scheme can starve a process, and Round Robin gives every process a turn once per lap of the queue.
4. Round Robin: re-evaluating every T units and favouring whoever has waited longest behaves like a time quantum of T.