j0444170See UNISA – Summary of 2010 Posts for a list of related UNISA posts.

This is one of the final exam preparation posts and looks at some of the common scheduling algorithms and reviews the associated assignment from this year as an example. If you are not studying at UNISA, you should probably skip this post Smile

What common scheduling algorithms are we going to review?

Algorithm

Description

Pre-emptive

Challenges

First-Come, First-Served (FCFS) The process that requests the CPU is serviced first. No

Starvation
Average waiting time can be long

Shortest-Job-First (SJF)

The process with the shortest “next CPU burst” time is scheduled first.
In pre-emptive mode, this algorithm is also known as the shortest-remaining-time-first scheduling algorithm.

Yes|No

Starvation
Difficult to determine next burst time

Round-Robin (RR) Processing is split up into time quantum's or time slice, ranging from 10 to 100 milliseconds. Yes

Difficult to determine correct quantum
If quantum is large we get FCFS,
If quantum too small, overhead is huge.

Priority

Each process has an associated priority and the highest priority processes are scheduled first.
In pre-emotive mode, a lower priority process will be interrupted to make place for a higher priority process.

Yes|No  

Sample Data

Assignment 1 claims that the following the following processes hit us, the one and only processor in the machine:

Process ID

Arrival Time

Burst Time

Priority

P1 0 3 3
P2 2 6 1
P3 3 10 3
P4 7 1 2
P5 8 5 4
P6 15 7 2
  • Burst time … the processing duration that is required by the process, for example milliseconds of processor time.
  • Quantum … time quantum or duration that the processor will allocate to a process, resulting in process slicing if burst time > quantum.
  • Priority … the smaller the value the higher the priority in this case.

Gant Charts … useful visualization

I added the following to help me keep track of the chaos:

  1. Arrival queue at the top which shows when processes arrive
  2. Wait queue at the bottom which shows the waiting process and remaining burst time (PROCESS.BURSTTIME) for the Round Robin. Let’s hope that the exam will not have one of these RR algorithms, because it is very easy to get the wait queue wrong.

The formulas we need to remember

  • Turnaround time (TT) = Time completed – Arrival time
  • Waiting Time (WT) = Turnaround time – Sum of burst time

Calculations

The verdict

The “Shortest-Job-First (SJF)” is the most effective algorithm for this set of process test data.