Operating System - First Come First Served (FCFS)

<<Previous

Next >>




First Come First Serve (FCFS) is the simplest CPU Scheduling algorithm.

What This Algorithm Means?

  • When a process requests the CPU first before other processes, then the CPU time will be first provided to that process.

  • That is, process will get the CPU time based on where it stands in the queue of processes waiting for CPU to execute it.

  • This algorithm uses the FIFO queue for ready queue management.

  • Algorithm is the simplest to write and has lesser complexity.

Scheduling Type

  • This algorithm follows the non-preemptive scheduling.

For Processes Arring At Almost Same Time

Let us see how this works. Consider the set of processes that arrive at the same time 0 and CPU-burst time in millisecond as shown below:


ProcessCPU-Burst Time
P120
P24
P33

If the processes P1, P2, P3 arrive in order with negligible time difference, then the processes will be executed as shown below.

P1
20P2
4P3
3

Waiting time for each process will be the time taken from its arrival on the process queue until it is processed. It is calculated by the sum of time taken by all processes before it minus the time at which it arrived


Process
Arrival
Time
CPU
Burst
Waiting
Time
Turn
around
time
P1020020
P2042024
P3032427

For Processes Arring At Different Times

Suppose, the processes arrive in the different arrival time, then these processes will be served in FCFS order.


ProcessArrival TimeCPU-Burst Time
P1020
P214
P333

Processes will be executed as shown below

P1
20P2
4P3
3

The waiting time, finish time and turn around time for each process will be as shown below:


Process
Arrival
Time
CPU
Burst
Start
Time
Waiting Time =
Start Time -
Arrival Time
Finish
Time
Turnaround
time=
Finish Time -
Arrival Time
P102000-0=02020-0=20
P2142020-1=192424-1=23
P3332424-3=212727-3=24

Average Waiting Time = (0+19+21)/3 = 16.333 ms

Average Turnaround Time = (20+23+24)/3 = 22.333 ms


Advantages

  • There is no issue in switching context between processes. Once one process completes or terminates, next one is automatically chosen
  • There is no need to maintain priority of processes.
  • As long processes get terminated one by one, there is lesser risk of process hanging without being run for an unknown time. A process in queue, will always run provided its previous processes, were terminated

Disadvantages

  • Priorities cannot be set. Hence, a higher priority process that starts late wonuld still have to wait for CPU time just like other processes
  • If a process pauses without terminating, no other process would run

Performance of Algorithm

  • For the OS implementing this algorithm, the average waiting time for a process to get CPU time is quite long.

  • Performance of this algorithm is very low. Hence, it is rarely used in Modern Operating Systems.




<<Previous

Next >>









Operating System - First Come First Served (FCFS)

<<Previous

Next >>




First Come First Serve (FCFS) is the simplest CPU Scheduling algorithm.

What This Algorithm Means?

  • When a process requests the CPU first before other processes, then the CPU time will be first provided to that process.

  • That is, process will get the CPU time based on where it stands in the queue of processes waiting for CPU to execute it.

  • This algorithm uses the FIFO queue for ready queue management.

  • Algorithm is the simplest to write and has lesser complexity.

Scheduling Type

  • This algorithm follows the non-preemptive scheduling.

For Processes Arring At Almost Same Time

Let us see how this works. Consider the set of processes that arrive at the same time 0 and CPU-burst time in millisecond as shown below:


ProcessCPU-Burst Time
P120
P24
P33

If the processes P1, P2, P3 arrive in order with negligible time difference, then the processes will be executed as shown below.

P1
20P2
4P3
3

Waiting time for each process will be the time taken from its arrival on the process queue until it is processed. It is calculated by the sum of time taken by all processes before it minus the time at which it arrived


Process
Arrival
Time
CPU
Burst
Waiting
Time
Turn
around
time
P1020020
P2042024
P3032427

For Processes Arring At Different Times

Suppose, the processes arrive in the different arrival time, then these processes will be served in FCFS order.


ProcessArrival TimeCPU-Burst Time
P1020
P214
P333

Processes will be executed as shown below

P1
20P2
4P3
3

The waiting time, finish time and turn around time for each process will be as shown below:


Process
Arrival
Time
CPU
Burst
Start
Time
Waiting Time =
Start Time -
Arrival Time
Finish
Time
Turnaround
time=
Finish Time -
Arrival Time
P102000-0=02020-0=20
P2142020-1=192424-1=23
P3332424-3=212727-3=24

Average Waiting Time = (0+19+21)/3 = 16.333 ms

Average Turnaround Time = (20+23+24)/3 = 22.333 ms


Advantages

  • There is no issue in switching context between processes. Once one process completes or terminates, next one is automatically chosen
  • There is no need to maintain priority of processes.
  • As long processes get terminated one by one, there is lesser risk of process hanging without being run for an unknown time. A process in queue, will always run provided its previous processes, were terminated

Disadvantages

  • Priorities cannot be set. Hence, a higher priority process that starts late wonuld still have to wait for CPU time just like other processes
  • If a process pauses without terminating, no other process would run

Performance of Algorithm

  • For the OS implementing this algorithm, the average waiting time for a process to get CPU time is quite long.

  • Performance of this algorithm is very low. Hence, it is rarely used in Modern Operating Systems.




<<Previous

Next >>









Learn about Stack Data Structure

Learn about Heap Data Structure

Learn about Operating System

Learn AVL Tree

Learn Djikstra's Algorithm