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

01. First Come First Served (FCFS).

02. Shortest Job First (SJF).
03. Round Robin (RR).

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,

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,

            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.

            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.

            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.

            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.

            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.

            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,

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,

Then the shortened time-line will be,

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,

                                             

Beneath this, you will have to show the Average Waiting Time.

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,

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,