Different Terms You Should Be Aware Of Before Learning About CPU Scheduling Algorithms (Part-2)
Before we move on to discussing various CPU Scheduling algorithms,We need to understand various terms which would help us to understand these algorithms in a better way.The terms listed below are:
Burst Time
For Every process to be able to get executed on the CPU,a certain amount of time is required by the process. More Precisely, this time is a combination of CPU time as well as I/O time.The I/O time, which is time consumed by process in doing I/O operation is generally ignored and CPU time, which is time taken by CPU to execute a certain process on it is only considered for a process.Hence This total time is known as Burst Time.
Arrival Time
Arrival time of a process refers to the time at which a particular process enters into Ready State(or ready queue).By this time, that process is ready for its execution.
From the above diagram, we can say that the arrival time of process P1, P2, and P3 are 0 , 1, and 2 ms respectively.
Completion Time
Once the process which is currently being executed by CPU gets completely executed with a certain burst time.So a point of time when process execution gets completed.
Response Time
Response Time of a process refers to the Time duration spent by that process in the ready queue until it gets CPU for the first time.
Mathematically, we can define the response time in the following way:
Response Time = {(Time at which Process gets CPU for first time) - (Arrival Time)}
To understand it more clearly, let’s consider the following example:
The above table shows different processes with their arrival time in ready queue along with the burst time of each of them.
We will understand response time with respect to “The FIRST COME FIRST SERVE” as a CPU scheduling algorithm. In layman terms, in this algorithm the process whose arrival time is earliest, acquires the CPU resource for its execution first.
So the response time for each process has been calculated as follows:
For Process P1:
Since its arrival time is at earliest, hence this process will acquire CPU resource first, Hence there is no waiting time in the ready queue for this processes as the scheduler will directly pick up this process to get it executed on CPU first because of its earliest arrival time. Hence time at which Process gets CPU for first time=Arrival Time.
So Response time for P1 is 0.
For Process P2:
Now P2 process would be picked up by the schedular to get it executed on the CPU. But as P1 process is already getting executed on CPU, so P2 has to wait till the burst time of P1 for P1 to get completely executed. Hence waiting time of P2 = 8ms and arrival time=1ms.
Hence Response time for P2 is:
=Time at which Process gets CPU for first time-Arrival Time = 8 – 1=7ms
For process P3:
Similarly now, process P3 has to wait till the burst time of P1 and P2 for them to get executed on CPU.
Hence Waiting time of process P3 is: burst time of P1+Burst time of P2 = 8+7=15 ms and, the arrival time of P3 is 2 ms.
Therefore, response time = Time at which Process gets CPU for first time-Arrival Time = 15 – 2= 13ms
Turn Around Time
Turn around time for any process is defined as a time taken by a process starting from entering into the ready queue( that is ARRIVAL TIME) to the completion time of that process.
Mathematically, we can define the waiting time in the following way: Turnaround time= {(Burst time) + (Waiting time)}
Think: 🤔
Some individuals define turn around time as the time elapsed between completion and arrival. Do you have any thoughts on why this is the case and when it will be more beneficial than the old definition?
To understand it better, let’s consider an example: Say P1,P2,P3 be the three processes with the order of arrival as p1->p2->p3 with their bursts time as 2, 5, and10 ms respectively.
So Turnaround time of various processes are:
For process P1:
Since it arrives at the earliest,CPU is allocated to it first. So waiting time of P1=0;And given Burst time=2 ms; Hence Turn Around Time is:0+2ms=2ms.
For process P2:
P2 has to wait for P1 to get completely executed
So waiting time of P1=burst time of P0=2ms;And given burst time of P2=5ms. Hence Turn Around Time is:2+5=7ms.
For process P3:
Similarly, P3 has to wait for P1 and P2 to get completely executed So waiting time of P3=burst time of P0+burst time of P1=2+5=7ms; And given burst time of P3=10ms.
Hence Turn Around Time is:7+10=17ms.
Waiting Time
Waiting time for a process is referred to as total time for which a process remains in a ready queue waiting for its turn to get executed on CPU.
Mathematically, we can define the waiting time in the following way:
Waiting time={(Turnaround time) - (Burst time)}
Throughput
For a given amount of time, throughput is defined as the total number of processes executed by the CPU. It is also considered as a way to find the efficiency of CPU.
To understand it better, let’s consider an example of 3 processes P1, P2 and P3 with their burst time as 3, 5, and10 s respectively. Hence in this case,
Throughput=(burst time for P1+burst time for P2+burst time for P3)/Total processes =(3+5+10)/3 = 6s.
CPU Scheduling Criteria
A CPU scheduling algorithm tries to maximise and minimise the following:
Maximize:
CPU utilisation: CPU utilisation is the main task in which the operating system needs to make sure that CPU remains as busy as possible. It can range from 0 to 100 percent. However, for the RTOS, it can be range from 40 percent for low-level and 90 percent for the high-level system.
Throughput: The number of processes that finish their execution per unit time is known Throughput. So, when the CPU is busy executing the process, at that time, work is being done, and the work completed per unit time is called Throughput.
Minimize:
Waiting time: Waiting time is an amount that specific process needs to wait in the ready queue.
Response time: It is an amount to time in which the request was submitted until the first response is produced.
Turnaround Time: Turnaround time is an amount of time to execute a specific process. It is the calculation of the total time spent waiting to get into the memory, waiting in the queue and, executing on the CPU. The period between the time of process submission to the completion time is the turnaround time.
Numerical Question:
We have three processes P1, P2 and P3 having burst time as 24, 3 and 4 ms respectively and the gantt chart according to the given policy fixed by the CPU is given below. Find the average turnaround time and waiting time.
Quiz Time
- Orders are processed in the sequence they arrive if _______ rule sequences the jobs.
a) earliest due date
b) slack time remaining
c) first come, first served
d) critical ratio - Under multiprogramming, turnaround time for short jobs is usually ________ and that for long jobs is slightly ___________
a) Lengthened; Shortened
b) Shortened; Lengthened
c) Shortened; Shortened
d) Shortened; Unchanged
This completes the part-2 of this blog series on CPU Scheduling.
Thanks for reading!
We hope you found the content interesting. If you enjoy it, please share it with your friends. Something not stated, or would you want to offer your thoughts? Please leave a remark below, and we will respond as soon as possible. 😉
