CPU Scheduling Algorithms

A comprehensive implementation of various CPU scheduling algorithms in C++. This project demonstrates different approaches to process scheduling and includes visual Gantt charts for better understanding of execution sequences.

🚀 Features

• 6 CPU Scheduling Algorithms implemented
• Visual Gantt Charts showing execution sequence
• Process Statistics including waiting time, turnaround time, and averages
• Clean Console Output with proper formatting
• Cross-platform C++ implementation

📋 Implemented Algorithms

1. First Come First Serve (FCFS)

• Type: Non-preemptive
• Principle: Processes are executed in the order they arrive
• Use Case: Simple systems where fairness is important
• File: src/fcfs.cpp

2. Shortest Job First (SJF)

• Type: Non-preemptive
• Principle: Process with shortest burst time gets executed first
• Use Case: Minimizes average waiting time
• File: src/sjf.cpp

3. Shortest Remaining Time First (SRTF)

• Type: Preemptive
• Principle: Process with shortest remaining burst time gets CPU
• Use Case: Optimal for minimizing waiting time
• File: src/srtf.cpp

4. Round Robin (RR)

• Type: Preemptive
• Principle: Each process gets a fixed time quantum
• Use Case: Fair scheduling for time-sharing systems
• File: src/round_robin.cpp

5. Preemptive Priority

• Type: Preemptive
• Principle: Process with highest priority gets CPU
• Use Case: Systems with priority-based requirements
• File: src/preemptive_priority.cpp

6. Non-Preemptive Priority

• Type: Non-preemptive
• Principle: Process with highest priority gets CPU (no interruption)
• Use Case: Systems where priority is more important than responsiveness
• File: src/non_preemptive_priority.cpp

🛠️ Compilation

Prerequisites

• GCC compiler (g++)
• C++11 or later support

Compile All Algorithms

# Compile each algorithm individually
g++ -Wall -std=c++11 src/fcfs.cpp -o fcfs
g++ -Wall -std=c++11 src/sjf.cpp -o sjf
g++ -Wall -std=c++11 src/srtf.cpp -o srtf
g++ -Wall -std=c++11 src/round_robin.cpp -o round_robin
g++ -Wall -std=c++11 src/preemptive_priority.cpp -o preemptive_priority
g++ -Wall -std=c++11 src/non_preemptive_priority.cpp -o non_preemptive_priority

Quick Compilation Script

# Compile all at once
for file in src/*.cpp; do
    g++ -Wall -std=c++11 "$file" -o "$(basename "$file" .cpp)"
done

🎯 Usage

Running an Algorithm

# Example: Run FCFS algorithm
./fcfs

# Example: Run SJF algorithm
./sjf

# Example: Run Round Robin algorithm
./round_robin

Input Format

Each algorithm will prompt for:

1. Number of processes (integer)
2. Process details for each process:
   • Arrival Time (when process arrives)
   • Burst Time (execution time needed)
   • Priority (for priority-based algorithms)

Example Input

Enter the number of processes: 3
Enter arrival time and burst time for process 1 (e.g., 0 10): 0 5
Enter arrival time and burst time for process 2 (e.g., 0 10): 1 3
Enter arrival time and burst time for process 3 (e.g., 0 10): 2 2

📊 Output Format

Gantt Chart

The Gantt chart shows the execution sequence with timing:

Gantt Chart:
0 {P1} 5 {P2} 8 {P3} 10

Format Explanation:

• 0 - Start time
• {P1} - Process 1 executing
• 5 - Time when P1 completes and P2 starts
• {P2} - Process 2 executing
• 8 - Time when P2 completes and P3 starts
• {P3} - Process 3 executing
• 10 - Final completion time

Process Table

Processes      AT      BT      CT     TAT      WT
        1       0       5       5       5       0
        2       1       3       8       7       4
        3       2       2      10       8       6

Column Headers:

• AT - Arrival Time
• BT - Burst Time
• CT - Completion Time
• TAT - Turnaround Time
• WT - Waiting Time

Statistics

Average waiting time = 3.33
Average turn around time = 6.67

📁 Project Structure

scheduling algos/
├── README.md
├── src/
│   ├── fcfs.cpp
│   ├── sjf.cpp
│   ├── srtf.cpp
│   ├── round_robin.cpp
│   ├── preemptive_priority.cpp
│   └── non_preemptive_priority.cpp
├── fcfs
├── sjf
├── srtf
├── round_robin
├── preemptive_priority
└── non_preemptive_priority

🔧 Algorithm Details

FCFS (First Come First Serve)

• Advantages: Simple, fair, no starvation
• Disadvantages: Poor performance for varying burst times
• Time Complexity: O(n log n) for sorting

SJF (Shortest Job First)

• Advantages: Minimizes average waiting time
• Disadvantages: May cause starvation
• Time Complexity: O(n²) in worst case

SRTF (Shortest Remaining Time First)

• Advantages: Optimal for minimizing waiting time
• Disadvantages: Complex implementation, overhead
• Time Complexity: O(n²) in worst case

Round Robin

• Advantages: Fair, no starvation, good for time-sharing
• Disadvantages: Performance depends on time quantum
• Time Complexity: O(n)

Priority Scheduling

• Advantages: Supports priority-based requirements
• Disadvantages: May cause starvation
• Time Complexity: O(n log n) for sorting

🧪 Testing Examples

Test Case 1: Simple 3-Process Scenario

echo -e "3\n0 5\n1 3\n2 2" | ./fcfs

Test Case 2: Priority Scheduling

echo -e "3\n0 5 1\n1 3 2\n2 2 3" | ./preemptive_priority

Test Case 3: Round Robin with Time Quantum

echo -e "3\n0 5\n1 3\n2 2" | ./round_robin

🐛 Troubleshooting

Common Issues

1. Compilation Error: Ensure g++ is installed
2. Permission Denied: Make sure executables have execute permissions
3. Input Format: Follow the exact input format shown in examples

Debug Mode

Add -g flag during compilation for debugging:

g++ -Wall -std=c++11 -g src/fcfs.cpp -o fcfs

📝 Notes

• All algorithms handle idle time when no process is available
• Context switching is properly handled in preemptive algorithms
• Gantt chart shows exact execution sequence with timing
• Process IDs start from 1 for better readability
• Time units are arbitrary (can represent milliseconds, seconds, etc.)

🤝 Contributing

Feel free to contribute by:

• Adding new scheduling algorithms
• Improving the Gantt chart visualization
• Adding more test cases
• Optimizing the code

📄 License

This project is open source and available under the MIT License.

---

Happy Scheduling! 🎯