🧮 **Lab: CPU Scheduling – FCFS and SJF (Non-Preemptive)**
🎯 **Objective**
To understand and implement **First Come First Serve (FCFS)** and **Shortest Job First (SJF)** CPU scheduling algorithms using tabular calculations and Gantt charts.
🧠 **Given Data (Sample Input)**
| Process | Arrival Time (AT) | Burst Time (BT) |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
🧩 **1️⃣ FCFS (First Come First Serve) Scheduling**
Step 1: Arrange processes in order of **Arrival Time**.
| Process | AT | BT | Start Time (ST) | Completion Time (CT) | Turnaround Time (TAT = CT–AT) | Waiting Time (WT = TAT–BT) |
|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 0 | 8 | 8 | 0 |
| P2 | 1 | 4 | 8 | 12 | 11 | 7 |
| P3 | 2 | 9 | 12 | 21 | 19 | 10 |
| P4 | 3 | 5 | 21 | 26 | 23 | 18 |
Step 2:
⇒ **Average Turnaround Time (TAT)** = (8 + 11 + 19 + 23) / 4 = **15.25**
⇒ **Average Waiting Time (WT)** = (0 + 7 + 10 + 18) / 4 = **8.75**
Step 3: Gantt Chart (FCFS)
🧩 **2️⃣ SJF (Shortest Job First, Non-Preemptive)**
Step 1: At each point, select the process that has arrived and has the **shortest burst time**.
Execution Order: P1 → P2 → P4 → P3
| Process | AT | BT | Start Time (ST) | Completion Time (CT) | Turnaround Time (TAT = CT–AT) | Waiting Time (WT = TAT–BT) |
|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 0 | 8 | 8 | 0 |
| P2 | 1 | 4 | 8 | 12 | 11 | 7 |
| P4 | 3 | 5 | 12 | 17 | 14 | 9 |
| P3 | 2 | 9 | 17 | 26 | 24 | 15 |
Step 2:
⇒ **Average Turnaround Time (TAT)** = (8 + 11 + 14 + 24) / 4 = **14.25**
⇒ **Average Waiting Time (WT)** = (0 + 7 + 9 + 15) / 4 = **7.75**
Step 3: Gantt Chart (SJF)
📊 **3️⃣ Comparison Table**
| Algorithm | Average TAT | Average WT | Remarks |
|---|---|---|---|
| FCFS | 15.25 | 8.75 | Simpler, but may cause long waiting (Convoy effect) |
| SJF | 14.25 | 7.75 | Better average time, but requires knowing burst time |
🧾 **How to Create in Excel**
You can prepare one Excel sheet with two worksheets:
Sheet 1 — FCFS
Columns: Process | AT | BT | ST | CT | TAT | WT
Formulas you can use:
ST= previousCT(orATif CPU is idle)CT=ST + BTTAT=CT - ATWT=TAT - BT
At the end, use:
AVERAGE(TAT range)for Average TATAVERAGE(WT range)for Average WT
Sheet 2 — SJF
Follow the same columns, but sort processes dynamically based on **minimum BT among arrived processes**.
🎓 **Learning Outcomes**
- Understand how scheduling affects CPU performance.
- Learn to calculate waiting and turnaround times.
- Identify why SJF performs better in most cases.
Understanding Key Terms in CPU Scheduling (Operating Systems – BCA)
CPU Scheduling problems such as FCFS, SJF, Priority Scheduling, and Round Robin require you to understand a few important time parameters. These values help us measure how long a process stays in the system and how efficiently the CPU executes tasks. The explanation below is simple and student-friendly.
1. Arrival Time (AT)
Arrival Time is the time at which a process enters the ready queue. It is the moment the process arrives in the system and becomes available for CPU scheduling.
Example:
- If Process P1 arrives at time 0 → AT = 0
- If Process P2 arrives at time 2 → AT = 2
Processes are usually arranged in ascending order of Arrival Time before applying scheduling algorithms.
2. Burst Time (BT)
Burst Time is the total CPU time required by a process to complete its execution. It represents how long the CPU needs to run the process without interruption.
Example: A process that requires 5 units of CPU time has BT = 5.
3. Start Time (ST)
Start Time is the time when the CPU begins executing a process for the first time.
Example:
- P1 starts at time 0 → ST = 0
- P2 starts after P1 finishes at time 5 → ST = 5
4. Completion Time (CT)
Completion Time is the time at which the CPU finishes executing a process completely.
Example: If a process finishes at time 7 → CT = 7
5. Turnaround Time (TAT)
Turnaround Time represents the total time a process spends in the system, from arrival to completion. It includes waiting time and execution time.
Formula: TAT = CT – AT
Example: Process arrives at time 2 and completes at time 10 → TAT = 10 − 2 = 8
6. Waiting Time (WT)
Waiting Time is the amount of time a process spends waiting in the ready queue before it gets CPU time. It excludes execution time.
Formula: WT = TAT – BT
Example: If TAT = 8 and BT = 5 → WT = 8 − 5 = 3
Complete Example for Better Understanding
Consider the following two processes:
| Process | Arrival Time (AT) | Burst Time (BT) |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 2 | 3 |
FCFS Execution:
- P1 arrives first → Starts at 0, finishes at 4
- P2 arrives at 2 → Starts at 4, finishes at 7
Final Table (FCFS Scheduling)
| Process | AT | BT | ST | CT | TAT = CT − AT | WT = TAT − BT |
|---|---|---|---|---|---|---|
| P1 | 0 | 4 | 0 | 4 | 4 | 0 |
| P2 | 2 | 3 | 4 | 7 | 5 | 2 |