Program for Priority CPU Scheduling | Set 1

Easy
0/40
Average time to solve is 15m
profile
Contributed by
7 upvotes
Asked in companies
SamsungVisaBarclays

Problem statement

You are given the ‘N’ processes with their “burst times”, and the “arrival time” for all processes is ‘0’. You are also given the ‘priority’ of each process.

Your task is to find the “waiting time” and the “turn-around time” of each process using the ‘Priority CPU Scheduling’ algorithm.

Note:

1. The highest priority process will be scheduled first, followed by the next highest priority, and so on.

2. If the two processes have the same priority, then you have to run the process with the lowest number (id) first.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the 'T' test cases follow. 

The first line of each test case contains a single positive integer, ‘N’, denoting the number of Processes.

The second line of each test case contains ‘N’ space-separated non-negative integer denoting the ‘burst’ time of each process.

The last line of each test case contains ‘N’ space-separated non-negative integers denoting the ‘priority’ of each process.
Output Format: 
For each test case, return an array of arrays, where the 1st array will represent the ‘waiting time, and the 2nd array will denote the ‘turn-around time’ of each process.
Note: 
You do not 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 <= BURST[i],PRIORITY[i] <= 10^4

Time Limit: 1sec
Sample Input 1:
1
5
2 1 3 2 1
3 4 1 2 5
Sample Output 1:
2 1 6 4 0
4 2 9 6 1
Explanation for sample input 1:

altImage

Sample Input 2:
1
1
3
1
Sample Output 2:
0
3
Explanation for sample input 2:
We have only one process, so it starts at time 0 and ends at time 3.
Hint

Sort according to the priority.

Approaches (1)
Sorting

Approach:

 

  • Recall the following:
    • Finish Time: The time at which the process complete 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 = Turn Around Time - Burst Time.
  • We also have the ’priority’ of each process. The highest priority process will be scheduled first, followed by the next highest priority, and so on.
  • First, we need to calculate each process’s waiting time, and then we calculate the turn-around time of each process, which is nothing but the Waiting Time + Burst Time.
     

Steps:

  • We can create a 2D array named 'PROCESS_DATA', where the 1st element of the ith row denotes the id of the process, the 2nd element of the ith row represents the burst time, and the 3rd element indicates the priority of the ith process.
  • Sort the array 'PROCESS_DATA' according to the priority in descending order.
  • Now, we have to apply only the FCFS algorithm.
  • Create 2 new arrays named WAITING_TIME[], and TURN_AROUND_TIME[].
  • Call the function FIND_WAITING_TIME(PROCESS_DATA, WAITING_DATA), and both these parameters are already defined.
  • Now, call the function FIND_TURN_AROUND_TIME(PROCESS_DATA, WAITING_TIME, TURN_AROUND_TIME).
  • 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.

 

void findWaitingTime(PROCESS_DATA[][], WAITING_TIME[]):

  • The first process in the array 'PROCESS_DATA' doesn’t have to wait, so WAITING_TIME[PROCESS_DATA[0][0]] = 0.
  • Now, the ith process will be executed after the completion of (i-1)th process. So, run a loop from ‘i’ = 1 to ‘i’ < |'PROCESS_DATA'|, in each iteration do:
    • Waiting time of ith will become the waiting time plus the burst time of (i-1)th process. So, WAITING_TIME[PROCESS_DATA[i][0]] = WAITING_TIME[PROCESS_DATA[i-1][0]] + PROCESS_DATA[i-1][1].

 

void findTurnAroundTime(PROCESS_DATA[][], WAITING_TIME[], TURN_AROUND_TIME[]):

  • The Turn around time is the summation of the ‘WAITING’ time and the ‘BURST’ time.
  • Run a loop from ‘i’ = 0 to ‘i’ < |PROCESS_DATA|, in each iteration do:
    • TURN_AROUND_TIME[PROCESS_DATA[i][0]] = PROCESS_DATA[i][1] + WAITING_TIME[PROCESS_DATA[i][0]].
Time Complexity

O(N*logN), where ‘N’ is the number of processes.

 

We are sorting the process according to their ‘priority’, and the sorting takes O(N*logN) time.

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)
Program for Priority CPU Scheduling | Set 1
Full screen
Console