Disk Scheduling Algorithms - Jonh Alexis Buot (LaplaceXD)

# ===========================================================
# Authors:  Jonh Alexis Buot
# Github:   https://github.com/LaplaceXD
# Date:     December 03, 2023
# Course:   CS 3104 - Operating Systems
# Activity: Disk Scheduling Algorithms
# ===========================================================

def fcfs(tracks, track_bounds):
    return tracks.copy()

def sstf(tracks, track_bounds):
    tracks_buffer = tracks.copy()
    sorted_tracks = [tracks_buffer.pop(0)]

    while len(tracks_buffer) > 0:
        min_sstf_track_idx = min((i for i in range(len(tracks_buffer))), key=lambda i : abs(tracks_buffer[i] - sorted_tracks[-1]))
        track = tracks_buffer.pop(min_sstf_track_idx)
        sorted_tracks.append(track)

    return sorted_tracks

def scan(tracks, track_bounds):
    higher_tracks = sorted(track for track in tracks if track >= tracks[0])
    lower_tracks = sorted((track for track in tracks[1:] if track < tracks[0]), reverse=True)

    if len(lower_tracks) > 0 and track_bounds[1] not in higher_tracks:
        higher_tracks.append(track_bounds[1])

    return higher_tracks + lower_tracks

def cscan(tracks, track_bounds):
    higher_tracks = sorted(track for track in tracks if track >= tracks[0])
    lower_tracks = sorted(track for track in tracks[1:] if track < tracks[0])

    if len(lower_tracks) > 0:
        if track_bounds[1] not in higher_tracks:
            higher_tracks.append(track_bounds[1])
        if track_bounds[0] not in lower_tracks:
            lower_tracks.insert(0, track_bounds[0])

    return higher_tracks + lower_tracks

def look(tracks, track_bounds):
    higher_tracks = sorted(track for track in tracks if track >= tracks[0])
    lower_tracks = sorted((track for track in tracks[1:] if track < tracks[0]), reverse=True)

    return higher_tracks + lower_tracks

def clook(tracks, track_bounds):
    higher_tracks = sorted(track for track in tracks if track >= tracks[0])
    lower_tracks = sorted(track for track in tracks[1:] if track < tracks[0])

    return higher_tracks + lower_tracks

def graph_it(tracks, track_bounds, title = "", print_calcs_to_console = False):
    import matplotlib.pyplot as plt

    time = list(range(len(tracks)))
    _, ax = plt.subplots()

    plt.plot(time, tracks, color="lightblue", linestyle="-", linewidth=2)
    plt.scatter(time, tracks, color="blue", marker="o", clip_on=False, zorder=2)

    for i, track in enumerate(tracks):
        ax.text(i, track + 7.5, track, color="blue", ha="center")

    plt.title(title)

    plt.xlabel("Time")
    plt.xticks(time)
    plt.xlim(0, time[-1])

    plt.ylabel("Track Number")
    y_ticks = [i for i in range(0, track_bounds[1], 20)]
    if track_bounds[1] not in y_ticks:
        y_ticks.append(track_bounds[1])
    plt.yticks(y_ticks)
    plt.ylim(track_bounds[0], track_bounds[1])

    seek_pairs = [(max(curr_track, next_track), min(curr_track, next_track)) for curr_track, next_track in zip(tracks[:-1], tracks[1:])]
    calculations = " + ".join(f"({curr} - {next})" for curr, next in seek_pairs)
    total_seek_time = sum(curr - next for curr, next in seek_pairs)

    if print_calcs_to_console:
        print(f"Total Seek Time = {calculations}")
        print(f"Total Seek Time = {total_seek_time}")
    else:
        plt.figtext(0.125, -0.05, f"Total Seek Time = {calculations}", fontsize = 10, ha="left", va="bottom")
        plt.figtext(0.125, -0.1, f"Total Seek Time = {total_seek_time}", fontsize = 10, ha="left", va="bottom")

    plt.grid(True)
    plt.show()

# Configurations
num_cylinders = 200
starting_point = 55
tracks = [96, 120, 156, 80, 130, 9, 48, 32, 50, 12, 2]

# Other Configurations, can leave as is
track_bounds = (0, num_cylinders - 1)
tracks.insert(0, starting_point)

disk_schedulers = [
    ("First-Come-First-Serve (FCFS)", fcfs),
    ("Shortest Seek Time First", sstf),
    ("SCAN", scan),
    ("C-SCAN", cscan),
    ("LOOK", look),
    ("C-LOOK", clook),
]

for name, fn in disk_schedulers:
    sorted_tracks = fn(tracks, track_bounds)
    graph_it(sorted_tracks, track_bounds, title=name, print_calcs_to_console=False)