OS Menu9>
- OS Home
- Introduction
- CPU Scheduling
- What is Process?
- Process Lifecyle
- Process Control Block
- Process Scheduling
- Context Switching
- CPU Scheduling
- FCFS Scheduling
- SJF (non-preemptive)
- SJF (Preemptive - SRTF)
- Round Robin
- Priority Scheduling
- Convoy Effect
- Scheduler Vs Dispatcher
- Preemptive Vs non
- Preemptive scheduling
- Non preemptive scheduling
- Process Synchronization
- Deadlock
- Popular Algorithms
- Memory Management
- Memory Management Introduction
- Partition Allocation Method
- First Fit
- First Fit (Intro)
- First Fit in C
- First Fit in C++
- First Fit in Python
- First Fit in Java
- Best Fit
- Best Fit (Intro)
- Best Fit in C
- Best Fit in C++
- Best Fit in Java
- Worst Fit
- Worst Fit (Intro)
- Worst Fit in C++
- Worst Fit in C
- Worst Fit in Java
- Worst Fit in Python
- Next Fit
- First fit best fit worst fit (Example)
- Memory Management 2
- Memory Management 3
- Page Replacement Algorithms
- LRU (Intro)
- LRU in C++
- LRU in Java
- LRU in Python
- FIFO
- Optimal Page Replacement algorithm
- Optimal Page Replacement (Intro)
- Optimal Page Replacement Algo in C
- Optimal Page Replacement Algo in C++
- Optimal Page Replacement Algo in Java
- Optimal Page Replacement Algo in Python
- Thrashing
- Belady’s Anomaly
- Static vs Dynamic Loading
- Static vs Dynamic Linking
- Swapping
- Translational Look Aside Buffer
- Process Address Space
- Difference between Segmentation and Paging
- File System
- Off-campus Drive Updates
- Get Hiring Updates
- Contact us
PREPINSTA PRIME
FCFS Scheduling Algorithm in Operating System
FCFS Scheduling Algorithm in Operating System
In the world of computer science and operating systems, the way processes are managed can greatly impact the overall system performance. One of the simplest and earliest scheduling algorithms used in operating systems is the First Come, First Served (FCFS) algorithm.
There are various scheduling algorithm in Operating System but today we will learn about FCFS(First Come First Served) scheduling algorithm in operating system. Here we learn from basic knowledge to and various effects in it so you understand the topic as efficiently as possible.
First Come First Served Scheduling Algorithm in Operating System
This is the most basic algorithm in Operating System, as the name suggests, first come first serve (FCFS) the process which enters the system first gets the CPU time first.
Consider the following scenario –
Lets say you’re waiting at a railway station’s ticket counter at the front of the queue the person who arrived first will be given chance to buy the ticket, and you will have to wait for your turn until all the people in front of you in the queue or those who have arrived earlier have bought tickets.
These are the traits of FCFS algorithm –
- It is parallel to how FIFO in stack is
- Process which arrives firsts gets CPU time first
- It is a non preemptive type of algorithm
Let us try to understand FCFS Scheduling with the help of an example –
Note – If order and arrival time is not given then consider the order as is and arrival time to be 0 for all the processes.
[table id=241 /]
- Turn Around Time = Completion Time – Arrival Time
- Waiting Time = Turnaround time – Burst Time
Lets make a gantt Chart for this first.
Waiting time –
- P1 waiting time – 0ms
- P2 waiting time – 12ms
- P3 waiting time – 19ms
- P4 waiting time – 21ms
Thus, average waiting time – (0 + 12 + 19 + 21)/4 = 13ms
Turn around time – Time when process entered the system and when its out of the system
- P1 turn around time – (12 – 0) ms
- P2 turn around time – (19 – 0) ms
- P3 turn around time – (21 – 0) ms
- P4 turn around time – (26 – 0) ms
Average turn around time (12 + 19 + 21 + 26)/4 = 19.5 ms
Disadvantages of FCFS Algorithm
- Since, its a non preemptive algorithm thus, there is no intelligence applied and no priority can be given to processes.
- If critical system process arrives it may have to wait for a process like calculator.
- Waiting time may get too high, along with the turn around time.
- Causes convoy effect
What is convoy effect?
FCFS may suffer from the convoy effect if the burst time of the first job is the highest among all. As in the real life, if a convoy is passing through the road then the other persons may get blocked until it passes completely. This can be simulated in the Operating System also.
If the CPU gets the processes of the higher burst time at the front end of the ready queue then the processes of lower burst time may get blocked which means they may never get the CPU if the job in the execution has a very high burst time. This is called convoy effect or starvation.
The 2 seconds in the start can be avoided as the system only starts at 2 ms when the first process arrives.
Here have close watch on the arrival time for each process –
arrival time –
- P1 arrival time – 0 ms
- P2 arrival time – 4 ms
- P3 arrival time – 6 ms
- P4 arrival time – 13 ms
Waiting time –
- P1 waiting time – 0 ms
- P2 waiting time – (5 – 4) = 1 ms
- P3 waiting time – (14 – 6) = 8 ms
- P4 waiting time – (18 – 13) = 5 ms
Thus, average waiting time – (0 + 1 + 8 + 5)/4 = 3.50ms
Turn Around time –
- P1 turn around time – 5 ms
- P2 turn around time – (14 – 4) = 10 ms
- P3 turn around time – (18 – 6) = 12 ms
- P4 turn around time – (26 – 13) = 13 ms
Thus, average Turn Around time – (5 + 10 + 12 + 13)/4 = 12.5 ms
Prepare for Interview with us:
Key Concepts in FCFS Scheduling
- Non-preemptive Scheduling: Once a process starts executing, it will not be interrupted until completion.
- First Come, First Served: The process that arrives first will be executed first, similar to a queue in real life.
- Fairness: FCFS is fair in terms of the order of execution; each process is executed in the order it arrives.
- Burst Time: The total time a process needs to complete its execution. It is a key factor in determining the total time a process will spend in the system.
Comparison with Other Scheduling Algorithms
Let’s compare FCFS with some other popular scheduling algorithms to better understand its limitations and advantages.
1. FCFS vs. Shortest Job First (SJF)
SJF scheduling is another non-preemptive algorithm, but it schedules processes based on their burst time. The process with the shortest burst time is executed first. Compared to FCFS:
- Waiting Time: SJF reduces the waiting time significantly compared to FCFS, especially in cases where short jobs come after long jobs.
- Convoy Effect: SJF minimizes the convoy effect because shorter jobs are given preference.
- Drawback: However, SJF can be hard to implement because the operating system needs to know the burst time of processes in advance, which is not always feasible.
2. FCFS vs. Round Robin (RR)
Round Robin (RR) is a preemptive algorithm that allocates the CPU to each process for a fixed time slice, or quantum. After the time slice is over, the CPU is given to the next process in the ready queue.
- Fairness: Round Robin is more responsive to all processes since it divides the CPU time equally.
- FCFS: In FCFS, processes can suffer from long waiting times if long processes arrive first, whereas RR ensures that each process gets a fair share of CPU time.
- Efficiency: FCFS can be more efficient than RR if there are few processes or if the processes have similar burst times.
3. FCFS vs. Priority Scheduling
Priority Scheduling assigns priority levels to each process. Processes with higher priority are executed first. If two processes have the same priority, FCFS is used to decide the order of execution.
- Customization: Priority Scheduling allows more customization based on process importance, whereas FCFS is simple but lacks flexibility.
- Efficiency: Priority Scheduling can be more efficient in systems where certain processes are critical, but it can suffer from starvation if low-priority processes are always preempted.
Real-World Applications of FCFS Scheduling
FCFS may not always be the most efficient in modern operating systems, but it can still be useful in specific scenarios:
- Batch Processing: In scenarios where jobs are submitted in batches and the order doesn’t matter, FCFS can be effective.
- Non-Interactive Systems: For systems where real-time or interactive performance is not a priority, FCFS can provide a straightforward scheduling method.
- Simple Use Cases: FCFS can be used in simple embedded systems or systems with low process load.
Final Thoughts:
The FCFS Scheduling Algorithm offers a simple and intuitive approach to process management in operating systems. While it guarantees fairness by giving each process a turn based on their arrival time, its limitations – particularly the convoy effect and long waiting times – make it unsuitable for real-time and interactive applications.
Understanding the strengths and weaknesses of FCFS can help developers choose the best scheduling algorithm based on their specific system requirements.
FAQs
The FCFS (First Come, First Served) scheduling algorithm operates on the principle that the process which arrives first is executed first. It follows a queue-based system and does not interrupt a process once it starts executing (non-preemptive).
The main drawbacks include the convoy effect – where short processes are stuck waiting behind long ones – and high average waiting time. It also lacks prioritization and is not suitable for interactive or real-time systems.
FCFS is best suited for batch processing systems, simple embedded systems, and environments where real-time responsiveness is not critical. Its simplicity and fairness make it useful for basic scheduling needs.
While FCFS runs processes in order of arrival without interruption, Round Robin uses time slices to share CPU time among all processes, and SJF (Shortest Job First) prioritizes processes with the shortest burst time. FCFS is simpler but can result in longer waiting times compared to these algorithms.
Login/Signup to comment