Scheduling Metrics

How do we know if a Scheduler is good?

In the previous section, we learned that the Scheduler is responsible for determining which Thread or Process will get its turn and run on the CPU

But we have an important question:

How do we know if a Scheduling algorithm is really good?

Suppose we have three Processes:

A
B
C

Scheduler
can run these in different orders

So we need to have a set of criteria so that we can compare the performance of different algorithms

This is where we come to Scheduling Metrics

Turnaround Time

The first concept:

Turnaround Time

In simple terms, it means:

How much time has passed from the moment a Job enters the system to the moment its work is completely completed?

The formula is:

Turnaround Time =

Completion Time - Arrival Time

For example:

Arrival Time = 0

Completion Time = 10

So:

Turnaround Time = 10 - 0
= 10

That means this Process has been in the system for 10 time units from the moment it entered until the end

Waiting Time

Now another question:

How much time did the Process
just wait for the CPU?

Here we come to:

Waiting Time

Assume the state of a Process is as follows:

Arrival
↓
Waiting
↓
Running
↓
Waiting
↓
Running
↓
Finished

Any time the Process waits in the Ready Queue for the CPU is counted as Waiting Time

So very simple:

Waiting Time =
The amount of time the Process has been waiting for the CPU

Response Time

This one is especially important for interactive programs

Response Time
How long did it take from the time the Job entered the system until the first time the CPU reached it?

For example:

Arrival
│
│ 5ms
▼
First Run

So:

Response Time = 5ms

Now pay close attention to the difference with Turnaround Time

Response Time

Only until the first run:

Arrival → First Run

Turnaround Time

Until the complete end of the job:

Arrival → Completion

So a Process may run very quickly the first time, but it may take a long time to finish its work

A complete example

Let's assume we have three Jobs:

Job A
Arrival = 0
Runtime = 5

Job B
Arrival = 0
Runtime = 3

Job C
Arrival = 0
Runtime = 2

Let's assume the Scheduler decides to run in this order:

A → B → C

So the Timeline becomes:

0 5 8 10
|--------|--------|--------|
A B C

Now let's calculate one by one

Job A

A
started at:

0

and finished at:

5

So:

Turnaround = 5 - 0

= 5

Since A was executed immediately:

Response = 0

Job B

B
started at:

5

and finished at:

8

.

So:

Turnaround = 8 - 0
= 8

And since B waited for the CPU from time 0 to 5:

Response = 5

Job C

C
started at time:

8

and finished at:

10

So:

Turnaround = 10 - 0
= 10

And:

Response = 8

Because C waited until time 8 to finally get the CPU

The average is also important

Usually we are not going to examine just one Process

We want to see how our algorithm performed overall

So we take the average

For example:

Turnaround:

A = 5

B = 8

C = 10

Average:

(5 + 8 + 10) / 3
= 7.67

So:

Average Turnaround Time = 7.67

We can do the same for other metrics like Let's do Response Time too

A Simple Scheduler Problem

Now let's look at a more interesting case.

Suppose we have:

A = 100ms
B = 2ms
C = 2ms

And the Scheduler says:

A → B → C

Timeline
It becomes:

0 100 102 104
|-------------------------|------|------|
A B C

That means B and C have to wait until A finishes its work

As a result:

Response Time B = 100ms
Response Time C = 102ms

While B and C themselves only have 2ms of work

That means a heavy job can make small jobs wait for a long time

This is where Shortest Job First comes in handy

If we know in advance how long the jobs will take, we can execute the shorter jobs first

For example:

A = 100ms
B = 2ms
C = 2ms

So instead of:

A → B → C

we can have:

B → C → A

Timeline:

0 2 4 104
|----|----|--------------------------------|
B C A

Now B and C get their first response very quickly

This is the basic idea of ​​the algorithm:

Shortest Job First (SJF)

But here we have a problem

The operating system usually does not know in advance exactly: