44 comments Notes, Operating System Concepts, Solve

Preemptive Shortest Job First (SJF) CPU Scheduling Algorithm in C++ with Explanation

Posted by

Last updated on June 13th, 2020 at 08:36 pm

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

Preemptive Shortest Job First (SJF) CPU Scheduling Algorithm in C++ with Explanation

Preemptive Shortest Job First (SJF) CPU Scheduling Algorithm in C++ with Explanation:

Preemptive Shortest Job First (SJF) is a CPU scheduling algorithm in which the CPU, at any given time, looks for the job with the shortest burst time among the jobs in hand and starts processing it. In SJF the processor will not just pick the job that arrived first, rather will compare them based on their required CPU time and will pick the one which requires lowest amount of time.

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

Now let’s consider that following are three different jobs currently in the queue for the CPU to process:

Jobs
Arrival Time (seconds)
Burst Time (seconds)
JOB-1
0
3
JOB-1
1
2
JOB-1
2
1

Here, Arrival Time is the time when a process has arrived the queue, Job ID is used instead of the job name, and Burst Time is the amount of time CPU will need to process a job. Well, as the unit of time you can take anything like nano-second, second, minute etc whatever, we are considering it as seconds.
Now for an instance, consider the above queue as the ready queue for the CPU, that is, the CPU will be taking jobs from this queue and will process it.
In Shortest Job First (SJF), CPU will be processing the jobs as follows,

@Second 0:

There is only 1 job, that is JOB-1 with a burst time of 3 seconds. So CPU will do 1 second job of JOB-1. Thus JOB-1 has 2 seconds more job to be done.

@Second 1:

Now there are 2 jobs,
JOB-1 that arrived at Second 0 and has 2 seconds of job remaining
JOB-2 that arrived at Second 1 and has 2 seconds of job remaining
So as both of the jobs has equal amount of jobs to be done, CPU will follow First Come First Served method and do the job that arrived earlier, which is JOB-1. So CPU will process JOB-1 for 1 second. Finally, JOB-1 has 1 second of job remaining.

@Second 2:

Now there are 3 jobs,
JOB-1 that arrived at Second 0 and has 1 second of job remaining
JOB-2 that arrived at Second 1 and has 2 seconds of job remaining
JOB-3 that arrived at Second 2 and has 1 seconds of job remaining

Here, 2 jobs has the shortest amount of job to be done, which are JOB-1 and JOB-2. CPU will do the job that arrived earlier, which is JOB-1. So CPU will process JOB-1 for 1 second. Finally, JOB-1 has is done.

@Second 3:

Now there are 2 jobs,
JOB-2 that arrived at Second 1 and has 2 seconds of job remaining
JOB-3 that arrived at Second 2 and has 1 second of job remaining

Here, JOB-3 has the shortest amount of job to be done. CPU will do 1 second of job of JOB-3. So JOB-3 has is done.

@Second 4:

There is only 1 job, which is JOB-2 with remaining 2 seconds of job. So CPU will do 1 second of job of JOB-2. Thus JOB-2 has 1 seconds of job remaining

@second 5:

There is only 1 job, which is JOB-2 with remaining 1 seconds of job. So CPU will do 1 second of job of JOB-2. Thus JOB-2 is done.
We can show the above thing as the following time-line
JOB-1
JOB-1
JOB-1
JOB-3
JOB-2
JOB-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. Okay, Look carefully,
JOB-2 Arrived at the queue at second 1 with a Burst Time of 2 seconds. But CPU started processing JOB-2 at 4th second. So JOB-2 waited for 3 seconds.But JOB-1 didn’t wait.

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

 

AND JOB-3 Arrived at the queue at second 2 with a Burst Time of 1 second. CPU started processing JOB-3 at 3rd second. So JOB-3 waited for 1 second.

JOB-1
JOB-1
JOB-1
JOB-3
JOB-2
JOB-2
0s
1s
2s
3s
4s
5s
Thus total waiting time = (Waiting Time of JOB-1)+(Waiting Time of JOB-2)
+(Waiting Time of JOB-3)
= (0+3+1) seconds
= 4 seconds
Thus the average waiting time is = (Total waiting time / Number of JOB) seconds
= (4/3) seconds
= 1.33 seconds

The Program

Input: 

You will ask the user for the number of jobs. Then for each job 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.

44 comments

  7. Thanks,It works accurately.
    i have not coded yet ,During couple of days i am thinking about it and how coded it,
    but i can't solve it

  11. Hi,
    can u please explain this condition/situation…
    what if we put a condition that CPU remain idle for 2 seconds/unit of time in start…
    does it mean the arrival time will change or waiting time will change?

  12. Processor only remain IDLE when there is no process to process, this means the WAIT TIME doesn't change.

    Also, my program wouldn't show you the IDLE mark if the processor stay idle on the start-up, it only shows the IDLE mark if processor has nothing to do while it has started working, that means, only shows the IDLE mark from when the processor has turned to BUSY state from the IDLE state.

    Check this input,

    Arrival—–Process—–Burst
    2———–1———–2
    4———–2———–3
    7———–3———–3

    You will see, wait time = 0, though the processor stayed idle for 2 seconds at start-up.

  23. My assignment is like this: Job 1,2,3,4,5 Burst Time 1,8,5.4,1 Arrival time 5, 12,22,21,8. Help me. Thanks. I need the turn around time and waiting time and the round robin too.

  27. No, not really, I am studying that. But if you have experience in HTML, CSS, JS then you can start developing android app with these, search google for developing android app with HTML, CSS, JS/.

  28. Hey, your programs (sjf and rr) were super useful while I was preparing my exam! I just wanted to say thank you very much for your work.

    Have a good day 🙂

  36. what if we get priority with arrival and burst time in sjf ….???
    did we have to consider priority…..??
    really getting confused help me please..!!!!

  41. my problem is
    Arrival—–Process—–Burst
    0.0.———–1———–6
    0.1———–2———–5
    0.8———–3———–2
    1.0………..4………..1
    2.0………..5………..8
    can you solve this problem with sjf

  42. This demo program is just a simulation of the process. We know how fast today's processors are, right? So obviously in actual case, these arrival and burst times are calculated in miliseconds or nanoseconds. There's nothing wrong with having fractional values for arrival and burst times. Just convert them miliseconds, it will still remain the same.

Comments are closed.