[VIDEO] Explain and Solve : Shortest Job First (SJF) of Operating System Concepts



If you haven't read/tried the earlier problems then click the links follow:



Shortest Job First (SJF): 

This method is quite same as the FCFS but the difference is the in this case the processor will not process the jobs (processes) as they will come. Instead, a scheduler after a complete cycle (consider this as a 1 second job done) will check which is the job with the shortest burst time right now and will work on that. Now consider a CPU and also consider a list in which the processes are listed as follows,

Arrival
Process
Burst Time
0
1
3
1
2
2
2
3
1


Bored with Text? Watch this video explaining the Shortest Job First with animation and simulation


Here, Arrival is the time when the process has arrived the list, Process Number is used instead of the process name, and Burst Time is the amount of time required by the process from CPU. Well, as the unit of time you can take anything like nano-second, second, minute etc whatever. We consider it as second.

Now for an instance, consider the above list as the ready queue for the CPU, that is the CPU will take processes from this list and will process it.

Here in SJF, what will happen is as follows,

AT 0s:
            There is only 1 job, that is Process-1 with burst time 3. So CPU will do 1 second job of Process-1. Thus Process-1 has 2s more job to be done.

AT 1s:
            Now there are 2 jobs,
                        Process-1 that arrived at 0s and has 2s job to be done.
                        Process-2 that arrived at 1s and has 2s job to be done.

            So as both of the jobs as equal amount of jobs to be done, CPU will do the job that arrived earlier, that is 1s job of Process-1. So process-1 has more 1s job.

AT 2s:
            Now there are 3 jobs,
                        Process-1 that arrived at 0s and has 1s job to be done.
                        Process-2 that arrived at 1s and has 2s job to be done.
                        Process-3 that arrived at 2s and has 1s job to be done.

            Here, 2 jobs has the shortest amount of job to be done, that is 1s. Both Process-1 and Process-2 has 1s job. CPU will do the job that arrived earlier, that is 1s job of Process-1. So process-1 has more 0s job.

AT 3s:
            Now there are 2 jobs,
                        Process-2 that arrived at 1s and has 2s job to be done.
                        Process-3 that arrived at 2s and has 1s job to be done.

            Here, Process-3 has the shortest amount of job to be done, that is 1s. CPU will do 1s job of Process-3. So process-3 has more 0s job.

AT 4s:
            There is only 1 job, that is Process-2 with burst time 2. So CPU will do 1 second job of Process-2. Thus Process-2 has 1s more job to be done.

AT 5s:
            There is only 1 job, that is Process-2 with burst time 1. So CPU will do 1 second job of Process-2. Thus Process-2 has 0s more job to be done.

All Job Done.

We can show the above thing as the following time-line

Process-1
Process-1
Process-1
Process-3
Process-2
Process-2
0s
1s
2s
3s
4s
5s

A shortened view of the above time-line is as follows,

| Process-1
| Process-3
| Process-2
|
0                
3
4
6

So now came the main thing, Waiting Time. Ok, Look carefully,
Process-2 Arrived at the List of Process at 1s with a Burst Time of 2s. But CPU started processing Process-2 at 4s. So process-2 waited for 3s.

Process-1
Process-1
Process-1
Process-3
Process-2
Process-2
0s
1s
2s
3s
4s
5s

But process-1 didn’t  wait.

But Process-3 Arrived at the List of Process at 2s with a Burst Time of 1s. But CPU started processing Process-3 at 3s. So process-3 waited for 1s.

Process-1
Process-1
Process-1
Process-3
Process-2
Process-2
0s
1s
2s
3s
4s
5s

So total waiting time = (Waiting Time of Process-1)+ (Waiting Time of Process-2)
                                      + (Waiting Time of Process-3)
                                   = (0+3+1)s
                                   = 4s

So the average waiting time is = (Total waiting time / Number of Processes)s
                                                 = (4/3)s
                                                 = 1.33s

Ok...I think you have understood the thing. Now lets talk about the program in the next part.

PartDivider


Input: 

You will ask the user for the number of processes. Then for each process you will take its Process Number, Arrival Time and its Burst time. You don’t have to worry, the number of processes wont be more than 5 or 6, Arrival time of a process can only be equal or greater than the arrival time of its previous process and Process will be entered as a serial number, so no problem.

Output: 

In the output you will have to print out the shortened time-line we showed you above. For example, if the input is as follows,

Arrival
Process
Burst Time
0
1
3
1
2
2
2
3
1

Then the shortened time-line will be,

| Process-1
| Process-3
| Process-2
|
0                
3
4
6

You can also print out the time-line vertically if you want (thats what I have done, see the output of my program)

Ok beneath this shortened time-line you will have to print a table as follows,

Process
Arrival
Finish
Total
Wait
1
0
2
3
0
3
2
3
1
1
2
1
5
2
3
                                             
Beneath this, you will have to show the Average Waiting Time.

I know you have understood, now see a screen-shot of exactly what I was talking about,



Exception:

One exception is that, I said “Arrival time of a process can only be equal or greater than the arrival time of its previous process”. So take a look at the following list of process,

Arrival
Process
Burst Time
0
1
3
55
2
2
60
3
1


You see, the Job of Process-1 will complete at 2s, thus from 3s to 54s the CPU will remain idle. Again the job of Process-2 will complete at 56s and thus from 57s to 59s the CPU will again remain as idle. You have to show this in the output and also notice that none of the processes has waited. See the following screenshot,









After you have written the program upload the .exe (not the code) and let me and others try it. I am sure you will enjoy it. However, this is the second program of Process Scheduling and a bit harder than FCFS. Later we will work on, Priority Scheduling and Round Robin. I am sure you will love them all.

Recommended Recommends

Comments

Contact Us