CS643 S12 - 21 February

I promised a sample problem having to do with scheduling jobs using first-come first-served (FCFS) and shortest-job-first (SJF) strategies.

Suppose we have these tasks, and expected CPU times required:

Process  CPU Time
 P1        3
 P2        5
 P3        2

They will be batch-processed, not multi-tasked. We wait for each job to complete before moving on to the next.

The first-come first-served (FCFS) schedule just takes them in order:

FCFS schedule

Whereas shortest-job first (SJF) will do exactly that:

SJF schedule

To compute the average turn-around time using FCFS, we take the completion time and subtract the arrival time. (In this example, all arrival times are zero, because all three processes were ready to go from the beginning.)

FCFS average turn-around

To compute the average turn-around using SJF, it’s the same procedure:

SJF average turn-around

SJF is actually an optimal strategy, so its result should always be less than or equal to the turn-around for FCFS.

Non-zero arrival times

The one complication you might see is if some processes arrive (become available) later than others. That means when you are making a decision about what to run next (whether SJF or FCFS), you can only consider those processes that are ready at the time you make the decision.

Process  Arrival Time  CPU Time
 P1        0            5
 P2        0            3
 P3        2            2

FCFS is the same order:

FCFS

SJF must select P2 first. Although P3 is shorter, it is not ready to go at time zero. By the time P2 finishes, it can run.

SJF