How to Implement a Scheduling Algorithm: A Practical Guide

Implementing Scheduling Algorithms: A Practical Guide 🚀

Scheduling algorithms are crucial for operating systems to manage processes efficiently. This guide provides a step-by-step approach to implementing various scheduling algorithms with code examples.

1. Understanding Scheduling Algorithms 🧠

Before diving into implementation, it's essential to understand the different types of scheduling algorithms:

• First-Come, First-Served (FCFS): Processes are executed in the order they arrive.
• Shortest Job First (SJF): Processes with the shortest burst time are executed first.
• Priority Scheduling: Processes are executed based on their priority.
• Round Robin: Each process gets a fixed time slice (quantum) to execute.

2. Setting Up the Environment 🛠️

Choose a programming language (e.g., Python, C++) and set up your development environment. For demonstration, we'll use Python.

3. Implementing FCFS ⏳

FCFS is the simplest scheduling algorithm. Here's a Python implementation:

def fcfs(processes):
    """Implements First-Come, First-Served scheduling."""
    current_time = 0
    waiting_times = {}
    turnaround_times = {}
    
    for process, arrival_time, burst_time in processes:
        waiting_time = max(0, current_time - arrival_time)
        waiting_times[process] = waiting_time
        
        current_time += burst_time
        turnaround_time = current_time - arrival_time
        turnaround_times[process] = turnaround_time
        
    return waiting_times, turnaround_times

# Example Usage
processes = [
    ('P1', 0, 8),
    ('P2', 1, 4),
    ('P3', 2, 9),
    ('P4', 3, 5)
]

waiting_times, turnaround_times = fcfs(processes)
print("Waiting Times:", waiting_times)
print("Turnaround Times:", turnaround_times)

4. Implementing SJF ⏱️

SJF requires sorting processes by burst time. Here’s the Python implementation:

def sjf(processes):
    """Implements Shortest Job First scheduling."""
    processes.sort(key=lambda x: x[2])  # Sort by burst time
    
    current_time = 0
    waiting_times = {}
    turnaround_times = {}
    
    for process, arrival_time, burst_time in processes:
        waiting_time = max(0, current_time - arrival_time)
        waiting_times[process] = waiting_time
        
        current_time += burst_time
        turnaround_time = current_time - arrival_time
        turnaround_times[process] = turnaround_time
        
    return waiting_times, turnaround_times

# Example Usage
processes = [
    ('P1', 0, 8),
    ('P2', 1, 4),
    ('P3', 2, 9),
    ('P4', 3, 5)
]

waiting_times, turnaround_times = sjf(processes)
print("Waiting Times:", waiting_times)
print("Turnaround Times:", turnaround_times)

5. Implementing Priority Scheduling 🥇

Priority scheduling assigns a priority to each process. Here's the Python implementation:

def priority_scheduling(processes):
    """Implements Priority scheduling."""
    processes.sort(key=lambda x: x[3])  # Sort by priority (lower value = higher priority)
    
    current_time = 0
    waiting_times = {}
    turnaround_times = {}
    
    for process, arrival_time, burst_time, priority in processes:
        waiting_time = max(0, current_time - arrival_time)
        waiting_times[process] = waiting_time
        
        current_time += burst_time
        turnaround_time = current_time - arrival_time
        turnaround_times[process] = turnaround_time
        
    return waiting_times, turnaround_times

# Example Usage
processes = [
    ('P1', 0, 8, 3),
    ('P2', 1, 4, 1),
    ('P3', 2, 9, 4),
    ('P4', 3, 5, 2)
]

waiting_times, turnaround_times = priority_scheduling(processes)
print("Waiting Times:", waiting_times)
print("Turnaround Times:", turnaround_times)

6. Implementing Round Robin 🔄

Round Robin uses a time quantum to switch between processes. Here's a Python implementation:

def round_robin(processes, quantum):
    """Implements Round Robin scheduling."""
    remaining_time = {process: burst_time for process, _, burst_time in processes}
    waiting_times = {}
    turnaround_times = {}
    current_time = 0
    queue = [process[0] for process in processes]  # Queue of process names

    while queue:
        process = queue.pop(0)
        arrival_time = next(p[1] for p in processes if p[0] == process)
        burst_time = next(p[2] for p in processes if p[0] == process)

        if process not in waiting_times:
            waiting_times[process] = max(0, current_time - arrival_time)
        else:
            waiting_times[process] += max(0, current_time - arrival_time - sum(quantum for p, t in turnaround_times.items() if p == process))

        time_to_execute = min(quantum, remaining_time[process])
        current_time += time_to_execute
        remaining_time[process] -= time_to_execute

        if remaining_time[process] == 0:
            turnaround_times[process] = current_time - arrival_time
        else:
            queue.append(process)

    return waiting_times, turnaround_times

# Example Usage
processes = [
    ('P1', 0, 8),
    ('P2', 1, 4),
    ('P3', 2, 9),
    ('P4', 3, 5)
]

quantum = 2
waiting_times, turnaround_times = round_robin(processes, quantum)
print("Waiting Times:", waiting_times)
print("Turnaround Times:", turnaround_times)

7. Testing and Evaluation 🧪

Test your implementations with various scenarios to ensure correctness. Evaluate the performance of each algorithm based on metrics like average waiting time and average turnaround time.

Conclusion 🎉

Implementing scheduling algorithms provides valuable insights into operating system design. By understanding and implementing these algorithms, you can optimize process execution and improve system performance.