Howzit,
So while I have been preparing for the exam I came across difficulty in understanding the calculations to work out SJF scheduling without preemption and with non-preemption. I didn't find out Tutorial letter 102 helpul in this regard. So came across this post from a previous year and found it very helpful to me. So I am posting it here and will hopefully help some who are struggling to understand this as well.
An example
Process Arrival time Burst time Priority
P1 0 3 3
P2 1 6 1
P3 3 9 3
P4 6 1 2
P5 10 6 4
P6 15 7 2
For Shortest-Job-First without preemption: (ignore the priority column, given above, for this one, priority is used in the non-preemptive priority algorithm) Check the arrival times. P1 arrives at time = 0, and its burst time is time = 3, so P1 will complete its execution at time = 3, because it starts at time = 0 and its burst time is time = 3, it will create a total time = 0 + 3 = 3 (running total 1).
In that time, if you look at the arrival times, in the arrival time column above, P2 arrives at time = 1, but P3 also arrives at time = 3, and by this time P1 has finished executing, so you look at both P2 and P3, and you start executing the process with the shorter burst time, which is P2 with a time = 6. So P2 will run until it has finished its execution, its burst time = 6. You add this burst time = 6 onto the total which was calculated above when P1 was executed (which was time = 3), so the new total is time = 3 + 6 = 9 (running total 2).
Now, with executing up to time = 9 so far, you look through the list of arrival times in the arrival column above, you will see that not only is P3 ready but a shorter job, P4, arrived while P2 was executing as well, so among the two waiting processes, P4 will be chosen as its burst time is less, P3's burst time = 9, whereas P4's burst time is only 1, this is why it is called shortest-Job-First scheduling algorithm, it looks at the arrival times, and compares the jobs it has waiting, and chooses the job with the shortest burst length. If you add P4's burst time to the running total (time = 9), the new total execution time is, time = 9 + 1 = 10 (running total 3).
If you look at the arrival times in the arrival column now, P5 arrives at time = 10 as well, so we must choose between the already waiting P3, and the newly arrived P5, by comparing their burst times, the time that is shortest is chosen, looking through their burst times in the burst time column above, P3's burst time = 9, and P5's burst time is time = 6. This means that P5 will be chosen, because its burst length is less, so P3 will still have to wait. So, adding P5's burst time to the running total (time = 10) for execution time so far, time = 10 + 6 = 16. So the new running total is time = 16 (running total 4).
Now, with executing up to time = 16 so far, you look at the arrival times (in the arrival times column above), while P5 was executing, you will see that P6 arrived at time = 15. If you check P6's burst time, which is time = 7, it is less than P3, which has a burst time of time = 9, so P3 will have to wait again, and P6 will be given preference, as its burst time is less. So the new running total is time = 16 + 7 = 23. (running total 5).
No new processes arrive in this time, so P3 is finally free to execute. The burst time , time = 9, is added to the running total, which gives the final total time, time = 23 + 9 = 32. (running total 6)
All the processes have now finished executing.
The running order was: P1 -> P2 -> P4 -> P5 -> P6 -> P3.
To draw the Gantt chart, label the type of scheduling algorithm, in this case, SJF without preemption, at the top. The scale underneath starts at 0, and the number order under the Gantt chart (refer to question 5, tutorial letter 201), corresponds to the running totals above calculated at each stage of processing. Draw this to scale using a ruler (using centimeters to represent the burst times).
-----------------------------------------------------------------------------------
For the Non-premptive priority algorithm: (you can now use the priority column above)
Check the arrival times. P0 starts, as it is the only process that starts at 0. Its burst time = 3. The running total time will be time = 0 + 3 = 3 (running total 1).
In this time (time = 3), both P2 and P3 have arrived to be executed (refer to the arrival times in the arrival time column above), P2 arriving at time = 1, and P3 arriving at time = 3 respectively. Now you don't compare the burst times, you compare the priorities. The priority that is lower, will be the first to be executed. In this case P2 has a lower priority of priority = 1 (refer to priority column above), than P3 which has a priority = 3. So P2 will be executed, P3 will have to wait. The burst time for P2, which is, time = 6 will be added to the running total so far, time = 3 + 6 = 9. (running total 2).
In this time (time = 9), P4 arrives at time = 6. It joins P3 which is still waiting to be executed. Their priorities are compared, referring to the priority column above, P3 has a priority = 3, and P4 has a priority = 2. P4 has a lower priority than P3, so P4 will be chosen to execute first. P4 has a burst time of time = 1. If you add this to the running total so far, time = 9 + 1 = 10. (running total 3).
In this time (time = 10), P5 arrives at time = 10. It joins P3 which is still waiting to be executed. Their priorities are compared, referring to the priority column above, P3 has a priority = 3, and P5 has a priority = 4. P3 has a lower priority than P5, so P3 will be chosen to execute first. P3 has a burst time of time = 9. If you add this to the running total so far, time = 10 + 9 = 19. (running total 4).
In this time (time = 19), P6 arrives at time = 15. It joins P5 which is still waiting to be executed. Their priorities are compared, referring to the priority column above, P5 has a priority = 4, and P6 has a priority = 2. P6 has a lower priority than P5, so P6 will be chosen to execute first. P6 has a burst time of time = 7. If you add this to the running total so far, time = 19 + 7 = 26. (running total 5).
In this time (time = 26), no new processes have arrived, so P5 which is still waiting, is now free to execute. P5 has a burst time of time = 6. If you add this to the running total so far, time = 26 + 6 = 32. (running total 6).
The running order was: P1 -> P2 -> P4 -> P3 -> P6 -> P5.
To draw the Gantt chart, label the type of scheduling algorithm, in this case, non-preemptive priority algorithm, at the top. The scale underneath starts at 0, and the number order under the Gantt chart (refer to question 5, tutorial letter 201) corresponds to the running totals above calculated at each stage of processing, for non-preemptive. Draw this to scale using a ruler (using centimeters to represent the burst times).
I hope this helps.
Cheers
Brad
