L-2.3: First Come First Serve(FCFS) CPU Scheduling Algorithm with Example
Understanding FCFS Scheduling Algorithm
Introduction to FCFS
- The video introduces the First Come First Serve (FCFS) scheduling algorithm, explaining its basic premise and application in process management.
- It emphasizes that the burst time or execution time of processes is crucial for understanding how FCFS operates, regardless of the unit of measurement.
Working Criteria of FCFS
- The algorithm prioritizes processes based on their arrival times; the first process to arrive is served first.
- It is a non-preemptive scheduling method, meaning once a process starts executing on the CPU, it runs to completion without interruption.
Gantt Chart Utilization
- A Gantt chart is introduced as a tool to visualize and solve scheduling problems effectively.
- The presenter begins analyzing specific processes (P1, P2, P3, P4), checking their arrival times and determining which one will execute first.
Execution Process Breakdown
- At time 0, only P1 has arrived; thus it starts executing immediately for 2 units of time until time 2.
- After P1 completes at time 2, P2 is next in line since it arrived at time 1 and was waiting in the ready queue.
Idle Time and Subsequent Executions
- After executing P2 for 2 units until time 4, there’s an idle period from time 4 to 5 because no new processes have arrived.
- At time 5, P3 arrives and executes for 3 units until time 8. Following this, P4 executes from time 8 to completion at time 12.
Completion Times and Turnaround Time Calculation
- All processes complete by time 12. The completion times are recorded:
- P1: completed at 2
- P2: completed at 4
- P3: completed at 8
- P4: completed at 12.
Turnaround Time (TAT)
- TAT is calculated as CT (Completion Time) minus AT (Arrival Time):
- For example:
- TAT for P1 = CT(2)-AT(0)=2,
- TAT for P2 = CT(4)-AT(1)=3,
- TAT for P3 = CT(8)-AT(5)=3,
- TAT for P4 = CT(12)-AT(6)=6.
Waiting Time (WT)
- WT measures how long each process waited before execution:
- Calculated as TAT minus Burst Time:
- WT for each process results in values like:
- For P1: WT = TAT(2)-BT(2)=0,
- For others similarly calculated leading to respective waiting times.
Response Time Analysis
- Response Time indicates when a process gets CPU access relative to its arrival:
- Example calculations show that:
- For instance, response times are derived from initial CPU access timestamps compared with arrival times leading to values such as:
- For example:
- Response Time for P1 = CPU Access (0)- Arrival (0)=0,
- Response Time for other processes follows similar logic.
Response Time and Waiting Time in Scheduling
Understanding Response Time
- The speaker explains that calculating response time is unnecessary in this context, as it will always equal waiting time.
- Response time becomes more relevant in scheduling algorithms like Round Robin and Shortest Job First (SJF), particularly in preemptive cases.
- The speaker reassures that the audience won't be asked about different times beyond this point.
Average Turnaround and Waiting Times
- A follow-up question regarding average turnaround time is anticipated; it can be calculated by dividing the total turnaround time (14) by the number of processes (4).