Source Code With Schedule/Algorithm

by ADMIN 36 views

Alright, let's dive into the world of source code and scheduling algorithms! In this comprehensive guide, we'll explore everything you need to know to get started, from understanding the basics to implementing advanced techniques. Whether you're a student, a seasoned developer, or just curious about how things work under the hood, this article is for you. So grab your favorite beverage, settle in, and let's get coding!

Understanding the Basics

Before we jump into the code, it's essential to understand the fundamental concepts behind scheduling algorithms. At its core, a scheduling algorithm is a set of rules that determine the order in which tasks or processes are executed. These algorithms are crucial in operating systems, real-time systems, and various other applications where efficient resource management is paramount.

Why is scheduling important? Well, imagine a single-core processor trying to juggle multiple tasks simultaneously. Without a proper scheduling algorithm, some tasks might hog all the resources, while others starve. A well-designed scheduling algorithm ensures fairness, efficiency, and responsiveness.

There are several types of scheduling algorithms, each with its own strengths and weaknesses. Some common ones include:

  • First-Come, First-Served (FCFS): This is the simplest algorithm, where tasks are executed in the order they arrive. It's easy to implement but can lead to long waiting times for short tasks if a long task arrives first.
  • Shortest Job First (SJF): This algorithm prioritizes tasks with the shortest execution time. It minimizes average waiting time but requires knowing the execution time in advance, which is not always possible.
  • Priority Scheduling: Tasks are assigned priorities, and the algorithm executes tasks with higher priorities first. It's flexible but can lead to starvation if low-priority tasks never get a chance to run.
  • Round Robin: Each task is given a fixed time slice (quantum), and the algorithm cycles through the tasks, giving each one a chance to run. It's fair and prevents starvation but can introduce overhead due to context switching.

Implementing a Simple Scheduling Algorithm

Now that we have a basic understanding of scheduling algorithms, let's implement a simple one in code. We'll start with the First-Come, First-Served (FCFS) algorithm, as it's the easiest to grasp.

Here's a Python implementation:

def fcfs_scheduling(tasks):
    """Implements the First-Come, First-Served (FCFS) scheduling algorithm."""
    
    # Initialize variables
    current_time = 0
    waiting_times = []
    turnaround_times = []
    
    # Iterate through the tasks
    for task in tasks:
        arrival_time, burst_time = task
        
        # Calculate waiting time
        waiting_time = max(0, current_time - arrival_time)
        waiting_times.append(waiting_time)
        
        # Calculate turnaround time
        turnaround_time = waiting_time + burst_time
        turnaround_times.append(turnaround_time)
        
        # Update current time
        current_time += burst_time
    
    # Calculate average waiting time and turnaround time
    average_waiting_time = sum(waiting_times) / len(tasks)
    average_turnaround_time = sum(turnaround_times) / len(tasks)
    
    return waiting_times, turnaround_times, average_waiting_time, average_turnaround_time

# Example usage
tasks = [(0, 8), (1, 4), (2, 9), (3, 5), (4, 7)]  # (arrival_time, burst_time)
waiting_times, turnaround_times, average_waiting_time, average_turnaround_time = fcfs_scheduling(tasks)

print("Waiting Times:", waiting_times)
print("Turnaround Times:", turnaround_times)
print("Average Waiting Time:", average_waiting_time)
print("Average Turnaround Time:", average_turnaround_time)

In this code, the fcfs_scheduling function takes a list of tasks as input, where each task is represented as a tuple of (arrival_time, burst_time). The function calculates the waiting time and turnaround time for each task and returns the average waiting time and turnaround time.

Visualizing the Schedule with a Gantt Chart

To better understand the schedule, we can visualize it using a Gantt chart. A Gantt chart is a graphical representation of the schedule, showing the start and end times of each task.

Here's how we can generate a Gantt chart using the matplotlib library in Python:

import matplotlib.pyplot as plt

def visualize_gantt_chart(tasks, waiting_times):
    """Visualizes the schedule using a Gantt chart."""
    
    # Initialize variables
    start_times = []
    end_times = []
    current_time = 0
    
    # Calculate start and end times for each task
    for i, task in enumerate(tasks):
        arrival_time, burst_time = task
        start_time = max(current_time, arrival_time)
        end_time = start_time + burst_time
        start_times.append(start_time)
        end_times.append(end_time)
        current_time = end_time
    
    # Create the Gantt chart
    fig, ax = plt.subplots()
    ax.set_xlabel("Time")
    ax.set_ylabel("Tasks")
    ax.set_title("Gantt Chart")
    ax.set_yticks(range(len(tasks)))
    ax.set_yticklabels([f"Task {i+1}" for i in range(len(tasks))])
    
    # Add bars for each task
    for i in range(len(tasks)):
        ax.barh(i, end_times[i] - start_times[i], left=start_times[i], height=0.5)
    
    # Show the Gantt chart
    plt.show()

# Example usage
visualize_gantt_chart(tasks, waiting_times)

This code generates a Gantt chart that visually represents the schedule, making it easier to understand the execution order and timing of each task.

Diving Deeper: Advanced Scheduling Algorithms

While FCFS is a good starting point, it's not always the most efficient algorithm. Let's explore some more advanced scheduling algorithms.

Shortest Job First (SJF)

Shortest Job First (SJF) prioritizes tasks with the shortest execution time. This can significantly reduce the average waiting time, but it requires knowing the execution time in advance.

Here's a Python implementation:

def sjf_scheduling(tasks):
    """Implements the Shortest Job First (SJF) scheduling algorithm."""
    
    # Sort tasks by burst time
    tasks.sort(key=lambda task: task[1])
    
    # Initialize variables
    current_time = 0
    waiting_times = []
    turnaround_times = []
    
    # Iterate through the tasks
    for task in tasks:
        arrival_time, burst_time = task
        
        # Calculate waiting time
        waiting_time = max(0, current_time - arrival_time)
        waiting_times.append(waiting_time)
        
        # Calculate turnaround time
        turnaround_time = waiting_time + burst_time
        turnaround_times.append(turnaround_time)
        
        # Update current time
        current_time += burst_time
    
    # Calculate average waiting time and turnaround time
    average_waiting_time = sum(waiting_times) / len(tasks)
    average_turnaround_time = sum(turnaround_times) / len(tasks)
    
    return waiting_times, turnaround_times, average_waiting_time, average_turnaround_time

# Example usage
tasks = [(0, 8), (1, 4), (2, 9), (3, 5), (4, 7)]  # (arrival_time, burst_time)
waiting_times, turnaround_times, average_waiting_time, average_turnaround_time = sjf_scheduling(tasks)

print("Waiting Times:", waiting_times)
print("Turnaround Times:", turnaround_times)
print("Average Waiting Time:", average_waiting_time)
print("Average Turnaround Time:", average_turnaround_time)

Priority Scheduling

Priority Scheduling assigns priorities to tasks, and the algorithm executes tasks with higher priorities first. This is useful when some tasks are more important than others.

Here's a Python implementation:

def priority_scheduling(tasks):
    """Implements the Priority Scheduling algorithm."""
    
    # Sort tasks by priority (lower value = higher priority)
    tasks.sort(key=lambda task: task[2])
    
    # Initialize variables
    current_time = 0
    waiting_times = []
    turnaround_times = []
    
    # Iterate through the tasks
    for task in tasks:
        arrival_time, burst_time, priority = task
        
        # Calculate waiting time
        waiting_time = max(0, current_time - arrival_time)
        waiting_times.append(waiting_time)
        
        # Calculate turnaround time
        turnaround_time = waiting_time + burst_time
        turnaround_times.append(turnaround_time)
        
        # Update current time
        current_time += burst_time
    
    # Calculate average waiting time and turnaround time
    average_waiting_time = sum(waiting_times) / len(tasks)
    average_turnaround_time = sum(turnaround_times) / len(tasks)
    
    return waiting_times, turnaround_times, average_waiting_time, average_turnaround_time

# Example usage
tasks = [(0, 8, 2), (1, 4, 1), (2, 9, 3), (3, 5, 0), (4, 7, 4)]  # (arrival_time, burst_time, priority)
waiting_times, turnaround_times, average_waiting_time, average_turnaround_time = priority_scheduling(tasks)

print("Waiting Times:", waiting_times)
print("Turnaround Times:", turnaround_times)
print("Average Waiting Time:", average_waiting_time)
print("Average Turnaround Time:", average_turnaround_time)

Round Robin

Round Robin gives each task a fixed time slice (quantum) and cycles through the tasks, giving each one a chance to run. This prevents starvation and ensures fairness.

def round_robin_scheduling(tasks, quantum):
    """Implements the Round Robin scheduling algorithm."""
    
    # Initialize variables
    remaining_times = [task[1] for task in tasks]
    waiting_times = [0] * len(tasks)
    turnaround_times = [0] * len(tasks)
    current_time = 0
    
    # Continue until all tasks are completed
    while any(remaining_times):
        for i, task in enumerate(tasks):
            if remaining_times[i] > 0:
                # Calculate execution time for this quantum
                execution_time = min(quantum, remaining_times[i])
                
                # Update remaining time
                remaining_times[i] -= execution_time
                
                # Update waiting times for other tasks
                for j in range(len(tasks)):
                    if j != i and remaining_times[j] > 0:
                        waiting_times[j] += execution_time
                
                # Update current time
                current_time += execution_time
                
                # Calculate turnaround time if task is completed
                if remaining_times[i] == 0:
                    turnaround_times[i] = current_time - task[0]
    
    # Calculate average waiting time and turnaround time
    average_waiting_time = sum(waiting_times) / len(tasks)
    average_turnaround_time = sum(turnaround_times) / len(tasks)
    
    return waiting_times, turnaround_times, average_waiting_time, average_turnaround_time

# Example usage
tasks = [(0, 8), (1, 4), (2, 9), (3, 5), (4, 7)]  # (arrival_time, burst_time)
quantum = 2
waiting_times, turnaround_times, average_waiting_time, average_turnaround_time = round_robin_scheduling(tasks, quantum)

print("Waiting Times:", waiting_times)
print("Turnaround Times:", turnaround_times)
print("Average Waiting Time:", average_waiting_time)
print("Average Turnaround Time:", average_turnaround_time)

Conclusion

Scheduling algorithms are a fundamental part of computer science and play a crucial role in managing resources efficiently. In this article, we've covered the basics of scheduling algorithms, implemented a simple FCFS algorithm, visualized the schedule with a Gantt chart, and explored more advanced algorithms like SJF, Priority Scheduling, and Round Robin. By understanding these concepts and implementing them in code, you'll be well-equipped to tackle real-world scheduling problems.

Remember, the best scheduling algorithm depends on the specific requirements of your application. Consider factors like fairness, efficiency, and responsiveness when choosing an algorithm. And don't be afraid to experiment and create your own custom algorithms to meet your unique needs. Happy coding, guys!