Day 02Part 04 – Operating system for gate computer – First come first serve basic algorithms (FCFS)

Day 02Part 04 – Operating system for gate computer – First come first serve basic algorithms (FCFS)



play-rounded-fill play-rounded-outline play-sharp-fill play-sharp-outline
pause-sharp-outline pause-sharp-fill pause-rounded-outline pause-rounded-fill
00:00

First Come First Serve (FCFS) Scheduling Algorithm

Introduction

First Come First Serve (FCFS) is the simplest CPU scheduling algorithm, where the process that arrives first in the ready queue gets executed first. It follows the FIFO (First In, First Out) principle.

Characteristics of FCFS:

Non-Preemptive: Once a process starts execution, it cannot be stopped until it completes.
Simple and Easy: The implementation is straightforward using a queue.
Fairness: Every process gets CPU time based on arrival order.
Not Optimal: High waiting time due to the Convoy Effect (slower processes delay faster ones).

Example of FCFS Scheduling:

Let’s consider 3 processes with the following arrival and burst times:

Process Arrival Time Burst Time
P1 0 ms 5 ms
P2 1 ms 3 ms
P3 2 ms 8 ms

Step-by-Step Execution Order (Gantt Chart):

| P1 | P2 | P3 |
0 5 8 16

Calculations in FCFS:

1. Completion Time (CT):

  • P1 finishes at 5 ms

  • P2 finishes at 8 ms

  • P3 finishes at 16 ms

2. Turnaround Time (TAT):

TAT=CT−ArrivalTimeTAT = CT – Arrival Time

  • P1 = 5 – 0 = 5

  • P2 = 8 – 1 = 7

  • P3 = 16 – 2 = 14

3. Waiting Time (WT):

WT=TAT−BurstTimeWT = TAT – Burst Time

  • P1 = 5 – 5 = 0

  • P2 = 7 – 3 = 4

  • P3 = 14 – 8 = 6

Average Turnaround Time:

(5+7+14)/3=8.67ms(5 + 7 + 14) / 3 = 8.67 ms

Average Waiting Time:

(0+4+6)/3=3.33ms(0 + 4 + 6) / 3 = 3.33 ms

Advantages of FCFS:

Easy to implement (uses a queue).
Fair for all processes (executes in order of arrival).

Disadvantages of FCFS:

Convoy Effect (a long process can delay all others).
Higher Average Waiting Time compared to other scheduling algorithms.

Conclusion

FCFS is a simple but inefficient CPU scheduling algorithm, suitable for basic systems but not ideal for time-sharing systems due to high waiting times. Other scheduling algorithms like SJF (Shortest Job First) and Round Robin perform better in most real-world scenarios.

Day 02Part 04 – Operating system for gate computer – First come first serve basic algorithms (FCFS)

OPERATING SYSTEM Lecture Notes On

Lab Manual – OPERATING SYSTEMS

Unit IV – CPU Scheduling and Algorithm



Leave a Reply

Your email address will not be published. Required fields are marked *

error: