CPU Scheduling Algorithms - FCFS

Introduction

• Tutorial on CPU scheduling algorithms.
• Focus on First Come First Serve (FCFS) algorithm.
• CPU scheduling algorithms determine how a CPU schedules and processes jobs and processes.

Key Definitions

• Arrival Time: Time at which the process enters the queue.
• Burst Time: Time required by a process to complete.
• Completion Time (CT): Time when the process is finished by the CPU.
• Turnaround Time (TAT): Total time spent by a process inside the queue.
• Waiting Time (WT): Time spent in the queue waiting for CPU time.

Given Data

• Processes: P0, P1, P2, P3
• Arrival times (milliseconds):
  • P0: 0
  • P1: 1
  • P2: 2
  • P3: 3
• Burst times (milliseconds):
  • P0: 5
  • P1: 3
  • P2: 8
  • P3: 6

Gantt Chart Calculation

1. P0:
   • Arrival: 0 ms, Burst: 5 ms
   • Completion: 5 ms
2. P1:
   • Arrival: 1 ms, Burst: 3 ms
   • Completion: 8 ms
3. P2:
   • Arrival: 2 ms, Burst: 8 ms
   • Completion: 16 ms
4. P3:
   • Arrival: 3 ms, Burst: 6 ms
   • Completion: 22 ms

Gantt Chart Timeline:

• P0: 0 - 5
• P1: 5 - 8
• P2: 8 - 16
• P3: 16 - 22

Calculation of Times

Completion Times

• P0: 5
• P1: 8
• P2: 16
• P3: 22

Turnaround Times (TAT)

• Formula: TAT = CT - Arrival Time
• P0: 5 - 0 = 5
• P1: 8 - 1 = 7
• P2: 16 - 2 = 14
• P3: 22 - 3 = 19

Waiting Times (WT)

• Formula: WT = TAT - Burst Time
• P0: 5 - 5 = 0
• P1: 7 - 3 = 4
• P2: 14 - 8 = 6
• P3: 19 - 6 = 13

Summary of Calculated Values

• Turnaround Times (TAT): 5, 7, 14, 19

• Total TAT: 5 + 7 + 14 + 19 = 45 ms

• Average TAT: 45 / 4 = 11.25 ms

• Waiting Times (WT): 0, 4, 6, 13

• Total WT: 0 + 4 + 6 + 13 = 23 ms

• Average WT: 23 / 4 = 5.75 ms

Conclusion

• Calculated individual parameters (CT, TAT, WT) using Gantt chart.
• Total and average values for TAT and WT provided.
• Understanding of FCFS CPU scheduling algorithm and its calculations.