UNISA Chatter – Operating System Concepts: Part 14 ... Scheduling Revisited

See 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

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.