Last Updated: 7 Apr, 2021

Priority CPU Scheduling : 2

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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:

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
Now, apply the First Come First Serve method on the processes.
Create 2 new arrays named WAITINGTIME[], and TURNAROUNDTIME[].
Call the function findWaitingTime(), for calculating waiting time
Now, call the function findTurnAroundTime(), for calculating turnaround time.
Calculate turnaround time by subtracting the arrival time from the completion time of the process.
Similarly calculate waiting time by subtracting the burst time from the turnaround time of the process.
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.

Solve now