Priority CPU Scheduling : 2

Easy
0/40
Average time to solve is 10m
profile
Contributed by
5 upvotes
Asked in companies
QuikrMicrosoftInfosys

Problem statement

You are given the arrival times, the burst times and the priority of ‘N’ processes in a CPU. You need to find the order of process scheduling according to Priority Based CPU Scheduling. Along with the order, also find the individual waiting and turnaround time for all the processes in order of their schedule.

Note: 
1. The processes are numbered from 1 to 'N'.
2. The process with lowest arrival time will be scheduled first, followed by the next lowest arrival time, and so on.
3. If any two processes have the same arrival time, then you have to run the process based on the priority of the process. The highest priority process will be scheduled first, followed by the next highest priority, and so on.
4. If the two processes have the same priority, then you have to run the process with the lowest process number first.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains ‘N’ space-separated integers denoting the Arrival Times. 

The second line of each test case contains ‘N’ space-separated integers denoting the Burst Times.

The third line of each test case contains ‘N’ space-separated integers denoting the Priorities of the processes.
Output Format: 
For each test case, print three lines:

The first line should contain ‘N’ space-separated integers denoting the order of the processes in which they are scheduled.

The second line should contain ‘N’ space-separated integers denoting the waiting time of the processes. 

The third line should contain ‘N’ space-separated integers denoting the turnaround time of the processes.   

Print the output of each test case in three separate lines.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^4
1 <= X, Y, Z <= 10^4

Where ‘T’ is the number of test cases, ‘N’ denotes the number of processes, ‘X’, ‘Y’, Z’ denotes the arrival time, burst time and priority of a process respectively.

Time Limit: 1 sec
Sample Input 1:
1
5
0 1 3 2 4
3 6 1 2 4
3 4 9 7 8
Sample Output 1:
1 2 4 3 5
0 2 7 8 8 
3 8 9 9 12
Explanation For Sample Input 1:
In the first test case, 
The table of the processes is shown below and with the help of this table we can find the turnaround and waiting time of each individual process:

Gantt chart:

Sample Input 2:
1
4
8 5 1 0
1 2 3 4
1 2 3 4
Sample Output 2:
4 3 2 1
0 3 2 1
4 6 4 2
Explanation For Sample Input 2:
In the first test case, 
The table of the processes is shown below and with the help of this table we can find the turnaround and waiting time of each individual process:

Gantt Chart:

Hint

Can you think of sorting processes according to requirement?

Approaches (1)
Sorting

Approach: In order to implement priority based scheduling, let us first understand what priority based CPU scheduling actually means. 

Priority Scheduling basically is a non-preemptive algorithm. As the name suggests it is based on priorities given to the processes. The processes with a higher priority are processed first and ones with the lowest priority are processed at last.

The flow of processes in priority scheduling is:

 

 

Now, let’s recall some terms:

  • Finish Time: The time at which the process completes and exits from the system.
  • Turn Around Time: The total time taken by the process. In other words, Turn Around time = Finish Time - Arrival Time.
  • Waiting Time: The total time taken by the process in the ready queue. In other words, Waiting Time = Turnaround Time - Burst Time.

 

So, the algorithm for priority scheduling:

  1. Sort processes in ascending order according to arrival time.
    • If two arrival times are same:
      • Sort in descending order according to process priority
        • If two priorities are same:
          • Sort in ascending order according to process number
  2. Now, apply the First Come First Serve method on the processes.
  3. Create 2 new arrays named WAITINGTIME[], and TURNAROUNDTIME[].
  4. Call the function findWaitingTime(), for calculating waiting time
  5. Now, call the function findTurnAroundTime(), for calculating turnaround time.
  6. Calculate turnaround time by subtracting the arrival time from the completion time of the process.
  7. Similarly calculate waiting time by subtracting the burst time from the turnaround time of the process.
  8. After completing the above function calls, we have found the waiting and turn-around time of each process. So, we just need to add them into the new array and return that array.
Time Complexity

O((N * log(N)), where N is the number of processes.


As we are sorting the processes based on different comparisons, the time complexity of this approach is O(N * log(N)).

Space Complexity

O(N), where N is the number of processes.


 

As we are creating an extra array of the size ‘N’ to store the ‘burst time’ and ‘priority’ of each process. Hence, space complexity will be O(N).

Code Solution
(100% EXP penalty)
Priority CPU Scheduling : 2
Full screen
Console