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:
- Arrival queue at the top which shows when processes arrive
- 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.