How Does First Come First Served Scheduling Work?

TL;DR

FCFS allocates the CPU to processes in the order they enter the ready queue, using a first-in, first-out structure. It is simple to understand and implement, but its average waiting time can be long and varies substantially with process arrival order and CPU burst times, as shown by averages of 17 milliseconds and 3 milliseconds for the same three processes in different orders.

Transcript

from this lecture onwards we are going to start studying about the different scheduling algorithms so in this lecture we are going to discuss the first scheduling algorithm which is first come first serve scheduling so we will see what is this first come first serve scheduling how does it work and if this is a good scheduling algorithm so this firs... Read More

Key Insights

• FCFS is the simplest CPU scheduling algorithm described in the lecture, allocating the CPU first to the process that requests it first. Later processes receive their opportunities in the same order in which they entered the ready queue.
• FCFS is implemented with a first-in, first-out queue. The process at the head is selected next, while every newly ready process has its process control block linked to the tail of the queue.
• A running process is removed from the ready queue after receiving the CPU. The process immediately behind it then becomes the new head, and newly arriving processes continue to join at the tail.
• Burst time is the period for which a process needs to hold the CPU to complete its execution. In the examples, P1 requires 24 milliseconds, while P2 and P3 each require 3 milliseconds.
• The order P1, P2, P3 produces waiting times of 0, 24, and 27 milliseconds. P2 waits for P1, while P3 waits for both P1 and P2, resulting in an average waiting time of 17 milliseconds.
• The order P2, P3, P1 produces waiting times of 0, 3, and 6 milliseconds in execution order. The resulting average waiting time is 3 milliseconds, even though the processes and their burst times remain unchanged.
• Process order strongly affects FCFS performance. Placing the 24-millisecond process before both 3-millisecond processes produces a much higher average waiting time than allowing the two shorter processes to execute first.
• The average waiting time under FCFS is generally not minimal. It may vary substantially according to the order in which processes arrive and the lengths of their CPU bursts, despite the policy being simple and straightforward to implement.

Questions & Answers

Q: What is First Come First Served CPU scheduling?

First Come First Served, or FCFS, is a CPU scheduling policy that allocates the CPU to processes in the order they request it. The first process to enter the ready queue receives the CPU first, the second process receives it second, and later processes follow in arrival order. The lecture describes it as the simplest CPU scheduling algorithm.

Q: How does a FIFO queue implement FCFS scheduling?

A FIFO queue implements FCFS by keeping the earliest arriving process at the head and adding each new process to the tail. When the CPU becomes free, it is allocated to the process at the head. That process is removed from the ready queue, the next process becomes the new head, and later arrivals join the tail.

Q: What happens when a process enters the FCFS ready queue?

When a process becomes ready for execution, its process control block, or PCB, is linked to the tail of the ready queue. It waits behind every process that arrived earlier. When it eventually reaches the head and the CPU becomes available, it receives the CPU for execution and is then removed from the ready queue.

Q: How is waiting time calculated in the P1, P2, P3 example?

With burst times of 24 milliseconds for P1 and 3 milliseconds each for P2 and P3, P1 waits 0 milliseconds because it executes first. P2 waits 24 milliseconds for P1 to finish. P3 waits 27 milliseconds for both P1 and P2. Their average waiting time is calculated as 0 plus 24 plus 27, divided by 3, which equals 17 milliseconds.

Q: Why does P3 wait 27 milliseconds in the first FCFS order?

P3 waits 27 milliseconds because it arrives behind P1 and P2 in the order P1, P2, P3. P1 occupies the CPU for 24 milliseconds, and P2 then occupies it for another 3 milliseconds. P3 cannot receive the CPU until both earlier processes complete, so its waiting time is 24 plus 3, or 27 milliseconds.

Q: What changes when the process order is P2, P3, P1?

When the order changes to P2, P3, P1, the two processes with 3-millisecond burst times execute before P1, whose burst time is 24 milliseconds. P2 waits 0 milliseconds, P3 waits 3 milliseconds, and P1 waits 6 milliseconds. The average waiting time becomes 6 plus 0 plus 3, divided by 3, which equals 3 milliseconds.

Q: Why can FCFS average waiting time vary substantially?

FCFS average waiting time varies because the algorithm follows arrival order without rearranging processes according to their burst times. In the lecture's examples, the same three processes produce an average wait of 17 milliseconds when the 24-millisecond process runs first, but only 3 milliseconds when the two 3-millisecond processes run before it.

Q: Is FCFS an efficient CPU scheduling algorithm?

FCFS is simple to understand, follow, and implement, but the lecture indicates that its average waiting time is often quite long and generally not minimal. Its performance depends heavily on process arrival order and CPU burst times. The examples demonstrate that merely changing the order of identical processes can reduce the average waiting time from 17 milliseconds to 3 milliseconds.

Summary & Key Takeaways

• First Come First Served scheduling gives the CPU to the process that requests it first. Its implementation uses a FIFO queue: each arriving process has its process control block linked to the tail, while the process at the head receives the CPU when it becomes free and is removed from the queue.

• The first example uses P1, P2, and P3, which all arrive at time zero with burst times of 24, 3, and 3 milliseconds. When executed in the order P1, P2, P3, their waiting times are 0, 24, and 27 milliseconds, producing an average waiting time of 17 milliseconds.

• The second example retains the same processes and burst times but changes their order to P2, P3, P1. Their waiting times become 0, 3, and 6 milliseconds in execution order, producing an average of 3 milliseconds. Therefore, FCFS waiting time is generally not minimal and can vary substantially with ordering.