Welcome! Log In Create A New Profile

Advanced

CPU Scheduling

Posted by BongaM 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
CPU Scheduling
October 06, 2008 04:06PM
Somebody please help!!! I didnt submit assignment one and now am having problems understanding the calculations regarding SJF without preemption and non-preemptive priority algorithm.

I just dont get how the processes are scheduled using these algorithms when arrival times are considered. I have read tut 201 a thousand times and each time I look at it I get more confused and the study guide aint making things easier either.

I dont really need a lot just a few hints on how to draw the GANTT CHARTS for these algorithms.

Thanking anyone in advance who can help in this regard.
Re: CPU Scheduling
October 06, 2008 11:47PM
Hi BongaM,

For question 5 in tutorial letter 201:
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
Dougie
Re: CPU Scheduling
October 11, 2008 02:35PM
Will the SJF type of questions always be asked without preemption and non-preemptive priority algorithms. ?

What is preemption then ? will you get a type of question to draw it WITH preemption ?
Re: CPU Scheduling
October 13, 2008 03:09PM
Dougie u the shiznizz...thanx a million. I got a clear picture now.

And to answer you Cornelvdw, I think u have to master all these algorithms considering that calcutions make up about 55% of the paper its definately worth studying everything.

Shots
Re: CPU Scheduling
October 19, 2008 09:09AM
Hi

Correct me if I am wrong

So in a nutshell,

Without Preemption you ignore the Priority Column, and you focus on the burst time in conjunction with the arrival time.

NON Preemption you take the priority column into account but the next job is not realy focused on the Burst time but rather on the Priority there of ?

Can you explain SJF with preemption ?
Re: CPU Scheduling
October 19, 2008 04:04PM
can someone explain round robin too pls?
avatar Re: CPU Scheduling
October 21, 2008 05:49PM
Dougie my hero!! thank you so much grinning smileygrinning smiley

---------
I'm Year '0110' Computer Student!
Sorry, only registered users may post in this forum.

Click here to login