How Does FCFS CPU Scheduling Work With Examples?

TL;DR

FCFS allocates the CPU to whichever process arrived first, running each to completion because it is non-preemptive. Using a Gantt chart with four processes arriving at 0, 1, 5 and 6, all finish at time 12, producing an average turnaround time of 3.5 and an average waiting time of 0.75. The CPU sits idle from 4 to 5 when no process has arrived.

Transcript

Hello Friends, welcome to Gate smashers The topic is FCFS First come first serve scheduling algorithm Let's understand with the numerical So in numerical first of all we are given the process number P1, P2, P3, P4 Means 4 processes are here, along with arrival time... Means which process arrived at what time Burst time... You can call it execution ... Read More

Key Insights

• FCFS scheduling uses arrival time as its only criterion, so the process that reaches the ready queue first is the one handed to the CPU, managed through a FIFO queue as described in the video description.
• FCFS is non-preemptive, meaning once the CPU starts executing a process it will not stop in the middle; the process runs to full completion and only then gets terminated and leaves the CPU.
• Burst time, also called execution time, is the duration a process declares it needs to finish executing. Its unit does not matter in these numericals, whether it represents 2 minutes, seconds or hours.
• A Gantt chart is the easiest tool for solving FCFS numericals because completion time, waiting time and response time can all be read directly off the chart's left and right boundaries.
• CPU idle time occurs in FCFS when no process has arrived yet. In the example the CPU is idle from time 4 to 5 because P3 arrives at 5 and P4 at 6.
• Turnaround time is calculated as completion time minus arrival time, and it measures how long a process stayed in the system overall from arrival until it finished executing.
• Waiting time equals turnaround time minus burst time, since burst time is the useful time and turnaround time is the total time spent in the system, so the difference is pure waiting.
• Response time is the moment a process first receives the CPU minus its arrival time. In non-preemptive FCFS it always equals waiting time, so it matters more for round robin and SJF.

Questions & Answers

Q: How does the First Come First Serve CPU scheduling algorithm work?

FCFS uses arrival time as its single working criterion. It checks which process arrived first and serves that one, allocating the CPU to whichever process requested it earliest. The processes are managed through a FIFO queue. Because the mode is non-preemptive, once a process is given to the CPU and execution starts, it will not be stopped in between; it runs for its complete burst time and then terminates and leaves. The algorithm is described as the easiest and simplest CPU scheduling algorithm.

Q: What does non-preemptive mean in FCFS scheduling?

Non-preemptive means that if a process has arrived and the CPU has started executing it, that execution will not be halted partway through. The process runs to completion for its full burst time and only afterwards gets terminated and removed from the CPU. In the worked example P1 declares it needs 2 units of time, so it runs for the complete 2 units without any break. No other arriving process can interrupt it during that window, which is what distinguishes non-preemptive from preemptive scheduling.

Q: How do you draw a Gantt chart for an FCFS numerical?

Start the chart at time 0 and check which process has arrived at that moment. In the example only P1 has arrived at 0, so it is placed first and run for its 2 units. At time 2 you check again: P2 arrived at 1 so it is already sitting in the ready queue, and it runs from 2 to 4. At time 4 neither P3 nor P4 has arrived, so the CPU is left idle until 5. P3 then runs 5 to 8 and P4 runs 8 to 12.

Q: Why is the CPU idle in this FCFS example?

The CPU goes idle from time 4 to time 5 because no process is available to execute at that point. P1 and P2 have already finished by time 4, while P3 does not arrive until 5 and P4 not until 6. Idle means the CPU has no process to execute, so nothing can be done at time 4 and the CPU simply stays idle for that one unit of time. Once P3 arrives at 5, execution resumes immediately.

Q: How do you calculate turnaround time in CPU scheduling?

Turnaround time is the amount of time a process stayed in the system, computed as completion time minus arrival time. In the worked example P1 completes at 2 and arrived at 0, giving 2. P2 completes at 4 and arrived at 1, giving 3. P3 completes at 8 and arrived at 5, giving 3. P4 completes at 12 and arrived at 6, giving 6. These four values sum to 14, which is then used to compute the average turnaround time.

Q: What is the formula for waiting time in FCFS scheduling?

Waiting time equals turnaround time minus burst time. Burst time represents the useful time a process actually needed, while turnaround time is how long it stayed in the system in total, so the difference is time spent waiting. In the example the waiting times are 2 minus 2 equals 0 for P1, 3 minus 2 equals 1 for P2, 3 minus 3 equals 0 for P3, and 6 minus 4 equals 2 for P4. P2 waits 1 unit because it arrived at 1 but got the CPU at 2.

Q: Why does response time equal waiting time in FCFS?

Response time is defined as the time at which a process first gets the CPU minus its arrival time. Because FCFS is non-preemptive, a process that receives the CPU keeps it until completion, so the first time it gets the CPU is also the only time it gets the CPU. That makes response time always come out equal to waiting time, meaning there is no benefit in calculating it separately here. Response time becomes a more meaningful question in preemptive cases such as round robin and SJF.

Q: How do you calculate average turnaround time and average waiting time?

Add up all the individual values and divide by the total number of processes. In this numerical the turnaround times of 2, 3, 3 and 6 sum to 14, and dividing 14 by the 4 processes gives an average turnaround time of 3.5. The waiting times of 0, 1, 0 and 2 sum to 3, and dividing 3 by the 4 processes gives an average waiting time of 0.75. These two averages are the standard follow-up question after the per-process tables are filled in.

Summary & Key Takeaways

• The numerical presents four processes P1 to P4 with arrival times 0, 1, 5 and 6 and burst times 2, 2, 3 and 4. FCFS checks arrival time only and serves whichever process came first, running it non-preemptively on the CPU until it finishes without any interruption in between.

• Building the Gantt chart from time 0, P1 runs from 0 to 2, P2 from 2 to 4, then the CPU stays idle from 4 to 5 because P3 has not yet arrived. P3 runs 5 to 8 and P4 runs 8 to 12, so all four processes complete at time 12.

• Completion times are 2, 4, 8 and 12. Turnaround times computed as completion minus arrival are 2, 3, 3 and 6, and waiting times as turnaround minus burst are 0, 1, 0 and 2. Response times are 0, 1, 0 and 2, identical to waiting time in this non-preemptive case.

• Averages are found by summing and dividing by the four processes. Turnaround times sum to 14 giving an average turnaround time of 3.5, and waiting times sum to 3 giving an average waiting time of 0.75. The video notes examiners rarely ask beyond these time metrics.