CPU scheduling is a key responsibility of an operating system, determining how and when processes are given access to the processor. Since multiple processes may compete for CPU time at the same moment, a scheduling algorithm is required to manage execution order in a fair and efficient way.
Different scheduling approaches aim to optimise system performance by balancing factors such as response time, turnaround time, fairness, and resource utilisation.
This topic explores several common CPU scheduling algorithms, including First-Come, First-Served (FCFS), EASY Backfilling, and Round Robin. Each algorithm uses a different strategy to decide which process should run next, offering distinct advantages and disadvantages depending on system requirements.
Introduction to FCFS
First-Come, First-Served (FCFS) is one of the simplest CPU scheduling algorithms used by operating systems. It follows the straightforward principle of “first come, first served”, meaning that processes are executed in the exact order in which they arrive in the ready queue.
The scheduler does not consider process priority, execution time, or resource requirements; arrival order alone determines which process runs next.
Which statement correctly describes the First-Come, First-Served (FCFS) scheduling algorithm?
FCFS Example
Here is this example the FCFS performs poorly because large processes monopolise the processor.
Here small processes have to wait a long time due to job 1 being processed first, a in issue known as the convoy effect and the average waiting time is high.
Average waiting time = (0 + 10 + 11 + 13) / 4 = 8.5
Example Jobs Table
In this example we have a number of different processes to be executed, each arriving at a specified time and with different requirements:
Job Number - Indicates the order in which the jobs arrive
Arrival Time - When the job was added to the queue
Duration / Burst Time - How long a job will take
Number of CPUs - How many CPUs will need to be allocated for the job to run.
Non Preemptive Scheduling
FCFS is generally implemented as a non-preemptive scheduling algorithm. Once a process is allocated the CPU and begins execution, it continues running until it completes its CPU burst or voluntarily enters a waiting state (such as waiting for I/O).
The operating system cannot interrupt or suspend the process to allow another process to run, which makes FCFS simple to implement but can lead to inefficiencies when long-running processes block shorter ones.
In first come first served scheduling, the process that arrives first is given the priority.
Calculating Turnaround Time
Turnaround time is total time taken to execute a process from the moment it enters the system until it completes execution and exits the system.
Turnaround Time = Completion Time − Arrival Time
Reducing turnaround time is often a goal in system optimization, as it can lead to improved user experience, faster job completion, and better resource utilization.
The average waiting time of processes in first come first served scheduling can be calculated using the formula: Total waiting time / of processes.
Pros of First Come First Served Scheduling
Simplicity
FCFS is one of the simplest scheduling algorithms to implement. It doesn't require complex calculations or data structures.
Fairness
FCFS treats all processes equally in terms of priority, giving precedence to the first process that arrives.
No starvation
FCFS ensures that no process remains indefinitely in the ready queue without getting a chance to execute. Every process eventually gets CPU time, even if it's not immediately after arrival.
Disadvantages of First Come First Served Scheduling
Poor turnaround time
FCFS may lead to longer average turnaround times, especially if processes with shorter execution times are waiting behind longer processes.
Convoy effect
If a long process arrives first, shorter processes might get stuck waiting behind it, resulting in a convoy effect where short processes suffer from increased waiting times.
Non-preemptive
FCFS is a non-preemptive scheduling algorithm, meaning once a process starts execution, it continues until it completes or enters the waiting state voluntarily. This lack of preemption can lead to inefficiencies, especially in systems where certain processes are more time-sensitive or critical.
First come first served scheduling is a non-preemptive scheduling algorithm, which means that once a process starts running, it cannot be stopped until it its execution.
One of the main drawbacks of first come first served scheduling is the issue of effect, where short processes are held up behind longer processes.
Which statement about First Come First Served (FCFS) scheduling is true?
