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.