Last Updated: 7 Apr, 2021

FCFS CPU Scheduling

Easy

Asked in company

Solve now

Problem statement

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

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

Note:

The process that comes first will be executed first. 

Assume all the process has arrived at same time and you have to consider the process with low process id to have arrived first.

The next process starts only after the previous gets fully executed.

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 integers denoting the ‘burst’ time of each process.

Output Format:

For each test case, print the two lines.

The first will contain the “waiting time” of each process separated by the space in the same order in which they are input.

The second will contain the “turn-around time” of each process separated by the space in the same order in which they are input.

Output for each test case will be printed in a separate line.

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^6
1 <= BURST[i], ARRIVAL[i]<= 1000

Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of processes, ‘BURST’ represents the ‘burst time’ of each process, and ‘ARRIVAL’ represents the ‘arrival time’ of each process.   

Time Limit: 1sec

Solve now

Approaches

01 Approach

Approach:

Recall the following:
- 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.
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.
We know that the Waiting Time of a process is actually the sum of the Burst Time of the previous process and the Waiting Time of the previous process.
You can refer to this, to read more about the FCFS CPU Scheduling.

Steps:

Create 2 new vectors named WAITINGTIME, and TURNAROUNDTIME[].
Call the function FINDWAITINGTIME(BURSTTIME, WAITINGTIME), and both these parameters are already defined.
Now, call the function FINDTURNAROUNDTIME(BURSTTIME, WAITINGTIME, TURNAROUNDTIME).
After completing the above function calls, we have found the waiting and turn-around time of each process. So, we just need to return the waiting time and the turn-around time of each process.

void findWaitingTime(burstTime, waitingTime):

The first process doesn’t have to wait, so WAITINGTIME[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 < n, in each iteration, do:
- The waiting time of the ith process will become equal to the sum of the burst time of the previous process and the waiting time of the previous process. So, WAITINGTIME[i] = BURSTTIME[i - 1] + WAITINGTIME[i - 1].

void findTurnAroundTime(burstTime, waitingTime, turnAroundTime):

Run a loop from i = 0 to i < n, in each iteration do:
- TURNAROUNDTIME[i] = WAITINGTIME[i] + BURSTTIME[i].

Solve now