Last updated on June 13th, 2020 at 08:36 pm
If you haven’t read/tried the earlier problems then click the links follow:
@Second 1:
@Second 4:
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,
You can download my program to try it out.
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.
its good thanks.
Welcome. And, have tried to code it?
how about with interrupt?
help me a lot. thanks!
Glad to know…welcome.
Nice pick. However, interrupt will work mostly the same way as "IDLE" is working here. So, have you coded it?
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
You can do it….and I am sure you will comment here again as "I did it …"…
Good job
Thank you…
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?
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.
BOOOOO
What does it mean?
I dnt understand…..:-(
Why not ! Where did you stuck?
thanks friend helped a lot…………………………
Welcome …
your lesson is easy to understand. thanks for the help, i am looking forward to reprogram it using magic software
What is Magic Software? Welcome by the way..:-)
Nice to know that.
This comment has been removed by the author.
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.
Its a kind of RAD, the same with unipaas.
I will think about it … though I am not free anymore, always busy with office work, but still will think about it.
Do you have any tutorial related with android os using java?
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/.
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 🙂
Thank you too and glad to know these are helping.
Source code C++?please
Please don't mind but I would like to see how far you have tired and whats the problem now…
not satisfied..!!
Uppppssss
Free ethical hacking course
it is preemptive or non-preemptive.
what if we get priority with arrival and burst time in sjf ….???
did we have to consider priority…..??
really getting confused help me please..!!!!
We can implement that, but that would become a mixture of priority and shortest job first scheduling method.
Can you elaborate please.
is this sjf preemptive mode ??
This comment has been removed by the author.
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
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.
preemptive or non preemptive sjf??
This comment has been removed by the author.