FCFS Scheduling Overview

In this video, we are going to discuss about first come first serve scheduling algorithm. In short, we can call as FCFS. FCFS is the simplest scheduling algorithm among all the scheduling algorithms. The name itself specifies the meaning. First come first served. That means the process which comes first into the radio queue will be served first. So the process which enters first into the ready cube will be executed first by the cpu let's take this example here we have five processes from p0 to p4 and the arrival time as well as burst time is given the arrival time for process p0 is 0 the arrival time for process p1 is 2 milliseconds the arrival time for process p2 is 4 seconds 4 milliseconds likewise arrival times are given next to burst times are given Barastu time means how much time that a process requires for its execution. In order to execute process P0, we need to execute that process for how many milliseconds? 3 milliseconds. Next to process P1 requires 6 milliseconds for its execution. Process P2 requires 4 milliseconds for its execution. So, likewise process P3 requires 5 milliseconds, process P4 requires 2 milliseconds. Now, we have to calculate average waiting time and average turn around time so you know how to solve the problem just we draw the gantt chart so this is nothing but gantt chart so g a n t d gantt chart so this is nothing but our gantt chart so which process has entered into the ready queue first arrival time is for process p naught it is zero that means p naught has entered first so first cpu start executing process p naught so what is the burst time of process p naught three milliseconds so zero plus three means three milliseconds so at three milliseconds p naught completed its execution next what is the next process for p1 the arrival time is two that means this is the smaller one when we compare it with these four values so next p1 next cpu starts executing p1 so at three milliseconds cpu starts executing p1 what is the burst time of p1 6 milliseconds. So how many more seconds it requires? So it requires 6 milliseconds. So this 3 plus 6 is equal to 9. So that means at a time 9 milliseconds P1 completed its execution. Next what are the other processes? P2, P3, P4. Arrival times are 4, 6, 8. So 4 is the smaller value. That means P2 enters first into the ready queue. So CPU starts executing P2. so at that time 9 milliseconds cpu starts executing p2 what is the burst time of p2 4 milliseconds so 9 plus 4 means 13. so at 13 milliseconds cpu has completed p2 execution next p3 process will comes into the execution by this cpu so at 13 milliseconds cpu has starts executing p3 process p3 burst to time is 5 milliseconds so 13 plus 5 means 18. so at 18 milliseconds p3 completed its execution the next process is before so at 18 milliseconds cpu starts executing before process and before burst time what is the burst time of p4 2 milliseconds so 18 plus 2 means 20 milliseconds so 0 plus 3 3 3 plus 6 9 9 plus 4 30 13 plus 5 18 18 plus 20 20 next We have to calculate turnaround time and waiting time. Before that, we need to calculate completion time. Completion time, in short, we can call it as CT. So, CT stands for completion time. So, what is the completion time of process P0? P0 completed its execution at 3 milliseconds. Next, P1 completed its execution at 9 milliseconds. P2 completed its execution at 13 milliseconds. p3 completed its execution at 18 milliseconds next p4 completed its execution at 20 milliseconds here fcfs is non-primitive scheduling algorithm we know that fcfs is non-primitive scheduling algorithm non-primitive means once cpu starts executing that process then cpu cannot release the process until and unless it has completed its execution okay so here CPU can't print the process. Only after executing the process execution, CPU can release the process. So, completion time is... Next we have to calculate turnaround time. So we know what is turnaround time. So turnaround time, let us assume that it is denoted by TAT, turnaround time. So turnaround time means the time between completion of the process and its submission. The time between completion of the process and its submission. So turnaround time, completion is nothing but CT whereas arrival is nothing but AT. So the formula for the turnaround time is completion time minus arrival time. So that time duration between completion of the process and its submission. So completion is denoted by Ct and submission of the process into the ready queue is denoted by At. So completion time minus arrival time. So this is the formula for turnaround time. So let us calculate turnaround time for process P0. So P0 enters into the... P0 enters into the ready queue at 0 milliseconds whereas it has completed its execution at 3 milliseconds. So turnaround time is equal to completion time minus arrival time. So 3 minus 0 means 3. So P1 arrival time is 2, completion time is 9. So 9 minus 2 means 7. P2 arrival time 4, P2 completion time 13. 13 minus 4 means 9. Next P3 arrival time is 6. P3 completion time is 18. 18 minus 6 means 12. Next P4 arrival time is 8. P4 completion time is 20. So 20 minus 8 means 12. So these are all the turnaround times. So next we have to calculate waiting time. Next we have to calculate waiting time. So waiting time is denoted by WT. So we know what is waiting time. Waiting time means how much time that a process waits in the radii cube for its execution. The formula for the waiting time is very very simple. Waiting time is equal to turnaround time minus burst time. So turnaround time we gives that process execution time whereas it we gives burst time. So this turnaround time minus burst time is nothing but the process that is waiting for execution in the radii cube. So the formula here is waiting time is equal to turnaround time minus burst time. So for P0 what is the burst time? 3 milliseconds. For P0 the turnaround time is 3 milliseconds. So 3 minus 3 means 0. For P1, 6 burst time, 7 turnaround time. So 7 minus 6 means 1. For P2, for P2 what is the burst time? 4 milliseconds. Whereas what is the turnaround time? 9 milliseconds. So 9 minus 4 means 5 is the waiting time. For P3, 5 is the bursted time, 12 is the turnaround time. So, 12 minus 5 means 7. For P4, bursted time is 2, whereas turnaround time is 12. So, 12 minus 2 means 10. So, what is the formula here? Turnaround time minus bursted time. So, 3 minus 3, 0. 7 minus 6, 1. 9 minus 4, 5. 12 minus 5, 7. 12 minus 2, 10. Next we have to calculate Yawaray's turnaround time and Yawaray's waiting time. So Yawaray's turnaround time is equal to sum of all these values. 3 plus 7, 10. 10 plus 9, 19. Next 19 plus 12, 31. So 31 plus 12, 43. So 43 by 5 processors are there. So 8 plus 6. So 8 plus 6 milliseconds is nothing but Yawaray's turnaround time. Likewise calculate Yawaray's waiting time. So 0 plus 1, 1. 1 plus 5, 6. 6 plus 7, 13. So, 13 plus 10, 23. So, 23 by 5. So, 5 4's are 10. 4 plus 6. So, here the average turnaround time is 8.6 milliseconds. Whereas, average waiting time is 4.6 milliseconds. If you solve this problem. Now, let us solve one more problem. So, with the help of in that problem, what we are doing is, we are not taking any error on time. So by considering in different outlets we will discuss convoy effect. FCFS suffers with a problem called convoy effect. We will discuss that problem also. Let us take an example here. Let us assume that here we have three processes P0, P1 and P2. Here we do not have any arrival times. We have only burst time. Let for process P0 the burst time is 24 milliseconds. Let for process P1 the burst time is 3 milliseconds. Let for process 2 the burst time is 3 milliseconds. If the arrival times are not given. then there is no need to draw the grand chart okay grand chart directly we can solve the problem okay yeah if you want we can draw the grand chart also there is no problem let us draw the grand chart so here how many processes are there here we have three processes p naught here we don't have any arrival times so let us assume that first p naught enters into the ready queue next p1 enters into the ready Next, P2 enters into the relative. So first CPU starts executing P0 process. What is the burst time of P0 process? 24 milliseconds. So 0 plus 24 means 24. Next CPU starts executing P1 process. So P1 starts its execution at 24 milliseconds. Whereas P1 burst time is 3 milliseconds. So 24 plus 3 means 27. Next P2 burst time is 3 milliseconds. So 27 plus 3 means 30 milliseconds. Here there is no need to calculate completion time, arrive completion time, turnaround time and waiting time. Directly we can calculate from this grand chart. Why? Because in this example we do not have any arrival time. If there is no arrival time then there is no need to draw the remaining columns. Directly we can calculate. Let us calculate average waiting time. So what is the waiting time of process peanut? 0 milliseconds. What is the waiting time of process P1? 24 milliseconds. What is the waiting time of process P2? 27 milliseconds. So 0 plus 24 means 24, 24 plus 27 means 51. So 51 by 3 means what? 3 17ths are 51. So this is nothing but average waiting time. If the processes comes in this order, next let us calculate average turnaround time. average turnaround time. Here arrival time is not given. So turnaround time will become completion time only. So what is the P0 turnaround time? 24. Next P1, 27. Next P2, 30 by 3. So we will get some value here. So in this way we can calculate. Let us assume that the processes arises in the order P1, P2, P0. P1, P2 and P0. So instead of P0, P1 and P2, assumes that the processes enters into in this order. Then let us calculate the average waiting time. So first which process enters into the ready queue? Assumes that first P1 process enters into the ready queue. So first CPU starts executing P1 process. So at 0 milliseconds CPU starts executing P1. So what is the burst time here? 3 milliseconds. so 0 plus 3 means 3 next assumes that p2 enters into the ready cube so cpu starts executing p2 so what is the burst time of p2 3 milliseconds so 3 plus 3 means 6 milliseconds next p naught cpu starts executing p naught so 6 plus 24 means 30 okay now let us calculate average waiting time what is the waiting time of p naught 6 milliseconds what is the waiting time of p1 6 millisecond 0 a second What is the waiting time of P2? 3 milliseconds. So P0 waiting time is 6, P1 waiting time is 0, P2 waiting time is 3. So what is the waiting time here? 6 plus 0 means 6, 6 plus 3 means 9, by 3 means 1 millisecond. So if we calculate this problem by assuming the processes arrives in this order, then the average waiting time is 17 milliseconds. Whereas if we assume that the processes arrives in this order, then the average waiting time is... one this problem is known as convoy effect convoy effect why we got this problem if we observe this problem then process p0 has highest burst time when compared with p1 and p2 so that means process p0 is taking more cpu time for its execution so during that time p1 and p2 has to wait for their done Whereas if we consider this example, P1 first in which order the processes enters into the queue? First P1 and P2 enters into the queue. So P1 burst time is 3, P2 burst time is 3. Whereas the process that is P0, so P0 has highest burst time. But the process P0 enters into the ready queue yet last. So now easily P1 and P2 can execute its execution. So there is no need of any waiting for P1 and P2. Whereas if you take this problem, if the processes arrives in this order, then process P1 and process P2 has to wait for so much amount of time for their execution. Whereas if the processes arrives in this order, then there is no need of any waiting here. Why? Because process P1 burst time is very very small. Process P2 burst time is also very very small. So this problem is known as. Convai effect. So if we execute FCFS algorithm then for some examples we will get this problem. So when we will get this problem if there is a convai that means if there is a process which is having highest to barrage to time comes first into the ready queue then the remaining processes needs to wait so much of time. So this problem is known as convai effect. So this is about first come first serve scheduling algorithm as well as convai effect.

That means the process which comes first into the radio queue will be served first. So the process which enters first into the ready cube will be executed first by the cpu let's take this example here we have five processes from p0 to p4 and the arrival time as well as burst time is given the arrival time for process p0 is 0 the arrival time for process p1 is 2 milliseconds the arrival time for process p2 is 4 seconds 4 milliseconds likewise arrival times are given next to burst times are given Barastu time means how much time that a process requires for its execution. In order to execute process P0, we need to execute that process for how many milliseconds?

3 milliseconds. Next to process P1 requires 6 milliseconds for its execution. Process P2 requires 4 milliseconds for its execution. So, likewise process P3 requires 5 milliseconds, process P4 requires 2 milliseconds. Now, we have to calculate average waiting time and average turn around time so you know how to solve the problem just we draw the gantt chart so this is nothing but gantt chart so g a n t d gantt chart so this is nothing but our gantt chart so which process has entered into the ready queue first arrival time is for process p naught it is zero that means p naught has entered first so first cpu start executing process p naught so what is the burst time of process p naught three milliseconds so zero plus three means three milliseconds so at three milliseconds p naught completed its execution next what is the next process for p1 the arrival time is two that means this is the smaller one when we compare it with these four values so next p1 next cpu starts executing p1 so at three milliseconds cpu starts executing p1 what is the burst time of p1 6 milliseconds.

So how many more seconds it requires? So it requires 6 milliseconds. So this 3 plus 6 is equal to 9. So that means at a time 9 milliseconds P1 completed its execution. Next what are the other processes? P2, P3, P4.

Arrival times are 4, 6, 8. So 4 is the smaller value. That means P2 enters first into the ready queue. So CPU starts executing P2.

so at that time 9 milliseconds cpu starts executing p2 what is the burst time of p2 4 milliseconds so 9 plus 4 means 13. so at 13 milliseconds cpu has completed p2 execution next p3 process will comes into the execution by this cpu so at 13 milliseconds cpu has starts executing p3 process p3 burst to time is 5 milliseconds so 13 plus 5 means 18. so at 18 milliseconds p3 completed its execution the next process is before so at 18 milliseconds cpu starts executing before process and before burst time what is the burst time of p4 2 milliseconds so 18 plus 2 means 20 milliseconds so 0 plus 3 3 3 plus 6 9 9 plus 4 30 13 plus 5 18 18 plus 20 20 next We have to calculate turnaround time and waiting time. Before that, we need to calculate completion time. Completion time, in short, we can call it as CT. So, CT stands for completion time.

So, what is the completion time of process P0? P0 completed its execution at 3 milliseconds. Next, P1 completed its execution at 9 milliseconds. P2 completed its execution at 13 milliseconds. p3 completed its execution at 18 milliseconds next p4 completed its execution at 20 milliseconds here fcfs is non-primitive scheduling algorithm we know that fcfs is non-primitive scheduling algorithm non-primitive means once cpu starts executing that process then cpu cannot release the process until and unless it has completed its execution okay so here CPU can't print the process.

Only after executing the process execution, CPU can release the process. So, completion time is... Next we have to calculate turnaround time. So we know what is turnaround time. So turnaround time, let us assume that it is denoted by TAT, turnaround time.

So turnaround time means the time between completion of the process and its submission. The time between completion of the process and its submission. So turnaround time, completion is nothing but CT whereas arrival is nothing but AT. So the formula for the turnaround time is completion time minus arrival time.

So that time duration between completion of the process and its submission. So completion is denoted by Ct and submission of the process into the ready queue is denoted by At. So completion time minus arrival time. So this is the formula for turnaround time. So let us calculate turnaround time for process P0.

So P0 enters into the... P0 enters into the ready queue at 0 milliseconds whereas it has completed its execution at 3 milliseconds. So turnaround time is equal to completion time minus arrival time.

So 3 minus 0 means 3. So P1 arrival time is 2, completion time is 9. So 9 minus 2 means 7. P2 arrival time 4, P2 completion time 13. 13 minus 4 means 9. Next P3 arrival time is 6. P3 completion time is 18. 18 minus 6 means 12. Next P4 arrival time is 8. P4 completion time is 20. So 20 minus 8 means 12. So these are all the turnaround times. So next we have to calculate waiting time. Next we have to calculate waiting time. So waiting time is denoted by WT.

So we know what is waiting time. Waiting time means how much time that a process waits in the radii cube for its execution. The formula for the waiting time is very very simple. Waiting time is equal to turnaround time minus burst time. So turnaround time we gives that process execution time whereas it we gives burst time.

So this turnaround time minus burst time is nothing but the process that is waiting for execution in the radii cube. So the formula here is waiting time is equal to turnaround time minus burst time. So for P0 what is the burst time?

3 milliseconds. For P0 the turnaround time is 3 milliseconds. So 3 minus 3 means 0. For P1, 6 burst time, 7 turnaround time. So 7 minus 6 means 1. For P2, for P2 what is the burst time? 4 milliseconds.

Whereas what is the turnaround time? 9 milliseconds. So 9 minus 4 means 5 is the waiting time.

For P3, 5 is the bursted time, 12 is the turnaround time. So, 12 minus 5 means 7. For P4, bursted time is 2, whereas turnaround time is 12. So, 12 minus 2 means 10. So, what is the formula here? Turnaround time minus bursted time. So, 3 minus 3, 0. 7 minus 6, 1. 9 minus 4, 5. 12 minus 5, 7. 12 minus 2, 10. Next we have to calculate Yawaray's turnaround time and Yawaray's waiting time. So Yawaray's turnaround time is equal to sum of all these values.

3 plus 7, 10. 10 plus 9, 19. Next 19 plus 12, 31. So 31 plus 12, 43. So 43 by 5 processors are there. So 8 plus 6. So 8 plus 6 milliseconds is nothing but Yawaray's turnaround time. Likewise calculate Yawaray's waiting time. So 0 plus 1, 1. 1 plus 5, 6. 6 plus 7, 13. So, 13 plus 10, 23. So, 23 by 5. So, 5 4's are 10. 4 plus 6. So, here the average turnaround time is 8.6 milliseconds. Whereas, average waiting time is 4.6 milliseconds.

If you solve this problem. Now, let us solve one more problem. So, with the help of in that problem, what we are doing is, we are not taking any error on time.

So by considering in different outlets we will discuss convoy effect. FCFS suffers with a problem called convoy effect. We will discuss that problem also. Let us take an example here. Let us assume that here we have three processes P0, P1 and P2.

Here we do not have any arrival times. We have only burst time. Let for process P0 the burst time is 24 milliseconds.

Let for process P1 the burst time is 3 milliseconds. Let for process 2 the burst time is 3 milliseconds. If the arrival times are not given. then there is no need to draw the grand chart okay grand chart directly we can solve the problem okay yeah if you want we can draw the grand chart also there is no problem let us draw the grand chart so here how many processes are there here we have three processes p naught here we don't have any arrival times so let us assume that first p naught enters into the ready queue next p1 enters into the ready Next, P2 enters into the relative.

So first CPU starts executing P0 process. What is the burst time of P0 process? 24 milliseconds. So 0 plus 24 means 24. Next CPU starts executing P1 process.

So P1 starts its execution at 24 milliseconds. Whereas P1 burst time is 3 milliseconds. So 24 plus 3 means 27. Next P2 burst time is 3 milliseconds.

So 27 plus 3 means 30 milliseconds. Here there is no need to calculate completion time, arrive completion time, turnaround time and waiting time. Directly we can calculate from this grand chart. Why?

Because in this example we do not have any arrival time. If there is no arrival time then there is no need to draw the remaining columns. Directly we can calculate.

Let us calculate average waiting time. So what is the waiting time of process peanut? 0 milliseconds. What is the waiting time of process P1?

24 milliseconds. What is the waiting time of process P2? 27 milliseconds. So 0 plus 24 means 24, 24 plus 27 means 51. So 51 by 3 means what? 3 17ths are 51. So this is nothing but average waiting time.

If the processes comes in this order, next let us calculate average turnaround time. average turnaround time. Here arrival time is not given. So turnaround time will become completion time only.

So what is the P0 turnaround time? 24. Next P1, 27. Next P2, 30 by 3. So we will get some value here. So in this way we can calculate. Let us assume that the processes arises in the order P1, P2, P0.

P1, P2 and P0. So instead of P0, P1 and P2, assumes that the processes enters into in this order. Then let us calculate the average waiting time. So first which process enters into the ready queue? Assumes that first P1 process enters into the ready queue.

So first CPU starts executing P1 process. So at 0 milliseconds CPU starts executing P1. So what is the burst time here?

3 milliseconds. so 0 plus 3 means 3 next assumes that p2 enters into the ready cube so cpu starts executing p2 so what is the burst time of p2 3 milliseconds so 3 plus 3 means 6 milliseconds next p naught cpu starts executing p naught so 6 plus 24 means 30 okay now let us calculate average waiting time what is the waiting time of p naught 6 milliseconds what is the waiting time of p1 6 millisecond 0 a second What is the waiting time of P2? 3 milliseconds. So P0 waiting time is 6, P1 waiting time is 0, P2 waiting time is 3. So what is the waiting time here? 6 plus 0 means 6, 6 plus 3 means 9, by 3 means 1 millisecond.

So if we calculate this problem by assuming the processes arrives in this order, then the average waiting time is 17 milliseconds. Whereas if we assume that the processes arrives in this order, then the average waiting time is... one this problem is known as convoy effect convoy effect why we got this problem if we observe this problem then process p0 has highest burst time when compared with p1 and p2 so that means process p0 is taking more cpu time for its execution so during that time p1 and p2 has to wait for their done Whereas if we consider this example, P1 first in which order the processes enters into the queue?

First P1 and P2 enters into the queue. So P1 burst time is 3, P2 burst time is 3. Whereas the process that is P0, so P0 has highest burst time. But the process P0 enters into the ready queue yet last. So now easily P1 and P2 can execute its execution.

So there is no need of any waiting for P1 and P2. Whereas if you take this problem, if the processes arrives in this order, then process P1 and process P2 has to wait for so much amount of time for their execution. Whereas if the processes arrives in this order, then there is no need of any waiting here. Why?

Because process P1 burst time is very very small. Process P2 burst time is also very very small. So this problem is known as.

Convai effect. So if we execute FCFS algorithm then for some examples we will get this problem. So when we will get this problem if there is a convai that means if there is a process which is having highest to barrage to time comes first into the ready queue then the remaining processes needs to wait so much of time. So this problem is known as convai effect. So this is about first come first serve scheduling algorithm as well as convai effect.

Transcript for:FCFS Scheduling Overview

Transcript for:
FCFS Scheduling Overview