Explain and Solve : Priority Scheduling CPU Scheduling Algorithm in C++ with Explanation

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

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

Priority Scheduling CPU Scheduling Algorithm in C++ with Explanation: 

This method is quite same as the SJF but the difference is that instead of choosing the next process to work on by the shortest burst time, CPU chooses the next process by the shortest priority value. Here, all the processes are given a priority value. The process with the shortest (The most shortest is 1) priority will be worked on first and so on. Now consider a CPU and also consider a list in which the processes are listed as follows,

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

Here, Arrival is the time when the process has arrived the list, Process Number is used instead of the process name, Burst Time is the amount of time required by the process from CPU, Priority value is what we described in the first paragraph. 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 Priority Scheduling, what will happen is as follows,
AT 0s:
            There is only 1 job, that is Process-1 with Burst Time 3 and Priority 2. 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 with Priority 2.
                        Process-2 that arrived at 1s and has 2s job to be done with Priority 1.
            Here, Priority of the job Process-2 is higher (Lower value of priority is higher, that is shortest priority value is higher), So 1s job of Process-2 will be done. Thus process-2 has more 1s job.
AT 2s:
            Now there are 3 jobs,
                        Process-1 that arrived at 0s and has 2s job to be done with Priority 2.
                        Process-2 that arrived at 1s and has 1s job to be done with Priority 1.
                        Process-3 that arrived at 2s and has 1s job to be done with Priority 3.
            Here, Process-2 has the highest priority, thus CPU will do 1s job of Process-2. So process-2 has more 0s job.
AT 3s:
            Now there are 2 jobs,
                        Process-1 that arrived at 0s and has 2s job to be done with Priority 2.
                        Process-3 that arrived at 2s and has 1s job to be done with Priority 3.
            Here, as Process-1 is with the highest priority (which is 2) so CPU will do 1s job of Process-1. So process-1 has more 1s job.
AT 4s:
            There are 2 jobs,
                        Process-1 that arrived at 0s and has 1s job to be done with Priority 2.
                        Process-3 that arrived at 2s and has 1s job to be done with Priority 3.
            Again, CPU will do 1s job of Process-1 as it is with the highest priority. Thus Process-1 has 0s more job to be done.
AT 5s:
            There is only 1 job, that is Process-3 with burst time 1 and priority 3. So CPU will do 1s job of Process-3. Thus Process-3 has 0s more job to be done.
All Job Done.
We can show the above thing as the following time-line
Process-1
Process-2
Process-2
Process-1
Process-1
Process-3
0s
1s
2s
3s
4s
5s
A shortened view of the above time-line is as follows,
| Process-1
| Process-2
| Process-1
| Process-3
|
0                
1
3
5
6
So now came the main thing, Waiting Time. Okay, Look carefully,
See the following time-line for Process-1. Here, RED marked seconds symbolizes the seconds while Process-1 was waiting and GREEN marked second symbolizes the seconds while Process-1 was working.
Process-1
Process-2
Process-2
Process-1
Process-1
Process-3
0s
1s
2s
3s
4s
5s
Thus Process-1 waited for 2 seconds.
Process-2 did not wait, it came at 1s and worked at 1s and 2s.
But Process-3 Arrived at the List of Process at 2s with a Burst Time of 1s. But CPU started processing Process-3 at 5s. So process-3 waited for 3s.
Process-1
Process-2
Process-2
Process-1
Process-1
Process-3
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)
                                   = (2+0+3)s
                                   = 5s
So the average waiting time is = (Total waiting time / Number of Processes)s
                                                 = (5/3)s
                                                 = 1.66s
Okay … I think you have understood the thing. Now lets talk about the program in the next part.
Input: You will ask the user for the number of processes. Then for each process you will take its Process Number, Arrival Time, Burst time and Priority. 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. Priority values of 2 processes wont be same.
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
Priority
0
1
3
2
1
2
2
1
2
3
1
3
Then the shortened time-line will be,
| Process-1
| Process-2
| Process-1
| Process-3
|
0                
1
3
5
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
2
1
2
2
0
1
0
4
3
2
3
2
5
1
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
Priority
0
1
3
2
55
2
2
1
60
3
1
3

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 the program (.exe) I written By Clicking Here.

Source Code Published! Get the source code now!

33 comments

  1. i have 3 process:
    Process BurstTime Arrival Time Priority
    1 1 1 2
    2 5 3 1
    3 5 0 3

    this is the result:

    P1 IDLE P2 P3
    1 2 3 8 13

    the question is, how come that P1 was processed first when it is actually 2nd in its priority?

  2. Its because, P1 arrived at 1s when there was no more processes(P2 came at 3s), thus CPU process 1s of P1 at 1s, then remained IDLE at 2s, then the P2 arrived and got processed.

    Also NOTE: I stated, in my program each process will have Arrival Time greater or equal to its previous process. You gave Arrival Time 0 to P3 where P2 is having Arrival Time 3, which is a wrong input. I thought these limitations will be challenges for those who will code it later.

  3. oh i see, thanks for the help! by the way i am done with the round robin scheduling using magic software and i really wanna thank you and your notes for helping me :3

  4. how i wish i can output the same as what you have. We will have a program Priority scheduling for our final. I do hope this blog can help. Thanks and more power to you sir.

  5. A lower priority job can block a high priority one (e.g., priority inversion
    problem) even a priority scheduling is used ..

  6. /*hey ..ty for responding..i hav done othrs i need sjf premptive and priority..all with different arrival times and shd be given using rand()..u can check my code and lastly in menu u shd add compare tat vl compare all the waiting and turnaround time in a table…hep me in this…u can compile my progra m and check..help me asap*/

  7. Hi, Could you please source codes of these algorithm series ? They are so important and your explanation is excellent. so i want to examine the source code for learning how implemantation . Is it possible?

Leave a Reply

Your email address will not be published. Required fields are marked *