Various scheduling algorithms in Python.

schedule.py

#!/usr/bin/env python3

import argparse
import itertools

class Process():
    def __init__(self, /,
            name=None,
            burst=None,
            arrival_time=None,
            priority=None,
            time_slice=None,
            waiting_time=None,
            turnaround_time=None):
        self.name            = name
        self.burst           = burst
        self.arrival_time    = arrival_time
        self.priority        = priority
        self.time_slice      = time_slice
        self.waiting_time    = waiting_time
        self.turnaround_time = turnaround_time

    def __repr__(self):
        args = [('name',         self.name),
                ('burst',        self.burst),
                ('arrival_time', self.arrival_time),
                ('priority',     self.priority),
                ('time_slice',   self.time_slice)]
        if self.waiting_time is not None:    args.append(('waiting_time',    self.waiting_time))
        if self.turnaround_time is not None: args.append(('turnaround_time', self.turnaround_time))
        args = [f'{arg[0]}={repr(arg[1])}' for arg in args]
        return f'Process({", ".join(args)})'

def parse_line(line):
    line = line.strip()
    assert(line[0] == '@' and line[-1] == '&')
    line = line[1:-1]
    fields = line.split(';')
    assert(len(fields) == 5)
    process = Process()
    process.name         = fields[0]
    process.burst        = int(fields[1])
    process.arrival_time = int(fields[2])
    process.priority     = int(fields[3])
    process.time_slice   = int(fields[4])
    return process

def read_file(filename):
    with open(filename) as file:
        return [parse_line(line) for line in file.readlines() if line]

# First Come First Serve
#
# The simplest scheduling algorithm, mainly because it does basically no
# scheduling at all! It just runs processes as they arrive until their
# completion.
def fcfs(processes):
    processes.sort(key=lambda process: process.arrival_time)
    # Start simulation at the first arrival.
    current_time = processes[0].arrival_time
    result = []
    for process in processes:
        # Adjust current time if CPU was idle.
        if process.arrival_time > current_time:
            current_time = process.arrival_time
        process.waiting_time = current_time - process.arrival_time
        current_time += process.burst
        process.turnaround_time = current_time - process.arrival_time
        result.append(process)
    return result

# Shortest Job First
#
# The simplest scheduling algorithm that actually does some scheduling. It
# chooses the process with the smallest burst time and runs it to completion.
# This is the non-preemptive version of the algorithm, for the preemptive
# version see `srtf`.
def sjf(processes):
    processes.sort(key=lambda process: process.arrival_time)
    # Start simulation at the first arrival.
    current_time = processes[0].arrival_time
    # Yields the job with the shortest burst that has already arrived.
    def next_process():
        while True:
            nonlocal current_time
            if not processes: return
            next = 0
            # Adjust current time if CPU was idle.
            if processes[next].arrival_time > current_time:
                current_time = processes[next].arrival_time
            for i in range(1, len(processes)):
                # This condition relies on the list being sorted.
                if processes[i].arrival_time > current_time:
                    break
                if processes[i].burst < processes[next].burst:
                    next = i
            # `pop` removes the process from the `processes` list.
            yield processes.pop(next)
    result = []
    for process in next_process():
        process.waiting_time = current_time - process.arrival_time
        current_time += process.burst
        process.turnaround_time = current_time - process.arrival_time
        result.append(process)
    return result

# Shortest Remaining Time First
#
# The preemptive version of `sjf`. The key difference is that whenever a new
# process arrives the scheduler switches if its burst in shorter than the
# remaining burst of the currently running process.
#
# This simulation looks for the shortest remaining burst every unit of time,
# which results in behavior identical to the described above.
def srtf(processes):
    processes.sort(key=lambda process: process.arrival_time)
    # Since this is a preemptive algorithm, that is, processes will not
    # necessarily run until completion uninterrupted, we need to keep track of
    # the remaining burst.
    for i in range(len(processes)):
        processes[i].remaining_burst = processes[i].burst
    # Start simulation at the first arrival.
    current_time = processes[0].arrival_time
    result = []
    while True:
        if not processes: break
        # Find the process with the shortest remaining time.
        next = 0
        # Adjust current time if CPU was idle.
        if processes[next].arrival_time > current_time:
            current_time = processes[next].arrival_time
        for i in range(1, len(processes)):
            # This condition relies on the list being sorted.
            if processes[i].arrival_time > current_time:
                break
            if processes[i].remaining_burst < processes[next].remaining_burst:
                next = i
        # Simulate one unit of time at the time in case another processes
        # arrives.
        processes[next].remaining_burst -= 1
        current_time += 1
        if processes[next].remaining_burst == 0:
            processes[next].completion_time = current_time
            result.append(processes.pop(next))
    for i in range(len(result)):
        result[i].waiting_time = result[i].completion_time - result[i].arrival_time - result[i].burst
        result[i].turnaround_time = result[i].completion_time - result[i].arrival_time
    return result

# Round Robin
#
# This algorithm cycles between every process giving each a time slice to run.
def rr(processes):
    processes.sort(key=lambda process: process.arrival_time)
    # Since this is a preemptive algorithm, that is, processes will not
    # necessarily run until completion uninterrupted, we need to keep track of
    # the remaining burst.
    for i in range(len(processes)):
        processes[i].remaining_burst = processes[i].burst
    # Start simulation at the first arrival.
    current_time = processes[0].arrival_time
    for i in itertools.cycle(range(len(processes))):
        # Terminate if all processes are done.
        if all(process.remaining_burst == 0 for process in processes):
            break
        # Skip this process if it has not yet arrived or if it is completed.
        if processes[i].arrival_time > current_time or processes[i].remaining_burst == 0:
            continue
        current_burst = min(processes[i].remaining_burst, processes[i].time_slice)
        processes[i].remaining_burst -= current_burst
        current_time += current_burst
        if processes[i].remaining_burst == 0:
            processes[i].completion_time = current_time
    for i in range(len(processes)):
        processes[i].waiting_time = processes[i].completion_time - processes[i].arrival_time - processes[i].burst
        processes[i].turnaround_time = processes[i].completion_time - processes[i].arrival_time
    return processes

if __name__ == '__main__':
    arg = argparse.ArgumentParser()
    option = arg.add_mutually_exclusive_group()
    option.add_argument('--fcfs', help='First Come First Serve (default)', action='store_true', default=True)
    option.add_argument('--sjf',  help='Shortest Job First',               action='store_true')
    option.add_argument('--srtf', help='Shortest Remaining Time First',    action='store_true')
    option.add_argument('--rr',   help='Round Robin',                      action='store_true')
    arg.add_argument('file', help='Input file', type=str)
    arg = arg.parse_args()

    algorithm = fcfs
    if arg.sjf:  algorithm = sjf
    if arg.srtf: algorithm = srtf
    if arg.rr:   algorithm = rr

    processes = read_file(arg.file)
    processes = algorithm(processes)
    for process in processes:
        print(process)
    print(f'Average waiting time: {sum(process.waiting_time for process in processes) / len(processes)}')
    print(f'Average turnaround time: {sum(process.turnaround_time for process in processes) / len(processes)}')

z.md

Test Files

File #1 (fcfs_1.txt)

@p1;24;0;0;0&
@p2;3;0;0;0&
@p3;3;0;0;0&

$ python schedule.py --fcfs fcfs_1.txt 
Process(name='p1', burst=24, arrival_time=0, priority=0, time_slice=0, waiting_time=0, turnaround_time=24)
Process(name='p2', burst=3, arrival_time=0, priority=0, time_slice=0, waiting_time=24, turnaround_time=27)
Process(name='p3', burst=3, arrival_time=0, priority=0, time_slice=0, waiting_time=27, turnaround_time=30)
Average waiting time: 17.0
Average turnaround time: 27.0

File #2 (fcfs_2.txt)

@p1;3;0;0;0&
@p2;3;0;0;0&
@p3;24;0;0;0&

$ python schedule.py --fcfs fcfs_2.txt 
Process(name='p1', burst=3, arrival_time=0, priority=0, time_slice=0, waiting_time=0, turnaround_time=3)
Process(name='p2', burst=3, arrival_time=0, priority=0, time_slice=0, waiting_time=3, turnaround_time=6)
Process(name='p3', burst=24, arrival_time=0, priority=0, time_slice=0, waiting_time=6, turnaround_time=30)
Average waiting time: 3.0
Average turnaround time: 13.0

File #3 (sjf_1.txt)

@p1;24;0;0;0&
@p2;3;0;0;0&
@p3;3;0;0;0&

$ python schedule.py --sjf sjf_1.txt 
Process(name='p2', burst=3, arrival_time=0, priority=0, time_slice=0, waiting_time=0, turnaround_time=3)
Process(name='p3', burst=3, arrival_time=0, priority=0, time_slice=0, waiting_time=3, turnaround_time=6)
Process(name='p1', burst=24, arrival_time=0, priority=0, time_slice=0, waiting_time=6, turnaround_time=30)
Average waiting time: 3.0
Average turnaround time: 13.0

File #4 (sjf_2.txt)

@p1;6;0;0;0&
@p2;8;0;0;0&
@p3;7;0;0;0&
@p4;3;0;0;0&

$ python schedule.py --sjf sjf_2.txt 
Process(name='p4', burst=3, arrival_time=0, priority=0, time_slice=0, waiting_time=0, turnaround_time=3)
Process(name='p1', burst=6, arrival_time=0, priority=0, time_slice=0, waiting_time=3, turnaround_time=9)
Process(name='p3', burst=7, arrival_time=0, priority=0, time_slice=0, waiting_time=9, turnaround_time=16)
Process(name='p2', burst=8, arrival_time=0, priority=0, time_slice=0, waiting_time=16, turnaround_time=24)
Average waiting time: 7.0
Average turnaround time: 13.0

File #5 (sjf_3.txt)

@p1;8;0;0;0&
@p2;4;1;0;0&
@p3;9;2;0;0&
@p4;5;3;0;0&

$ python schedule.py --sjf sjf_3.txt 
Process(name='p1', burst=8, arrival_time=0, priority=0, time_slice=0, waiting_time=0, turnaround_time=8)
Process(name='p2', burst=4, arrival_time=1, priority=0, time_slice=0, waiting_time=7, turnaround_time=11)
Process(name='p4', burst=5, arrival_time=3, priority=0, time_slice=0, waiting_time=9, turnaround_time=14)
Process(name='p3', burst=9, arrival_time=2, priority=0, time_slice=0, waiting_time=15, turnaround_time=24)
Average waiting time: 7.75
Average turnaround time: 14.25

File #6 (srtf_1.txt)

@p1;8;0;0;0&
@p2;4;1;0;0&
@p3;9;2;0;0&
@p4;5;3;0;0&

$ python schedule.py --srtf srtf_1.txt 
Process(name='p2', burst=4, arrival_time=1, priority=0, time_slice=0, waiting_time=0, turnaround_time=4)
Process(name='p4', burst=5, arrival_time=3, priority=0, time_slice=0, waiting_time=2, turnaround_time=7)
Process(name='p1', burst=8, arrival_time=0, priority=0, time_slice=0, waiting_time=9, turnaround_time=17)
Process(name='p3', burst=9, arrival_time=2, priority=0, time_slice=0, waiting_time=15, turnaround_time=24)
Average waiting time: 6.5
Average turnaround time: 13.0

File #7 (srtf_2.txt)

@p1;5;0;0;0&
@p2;15;3;0;0&
@p3;11;5;0;0&
@p4;5;7;0;0&

$ python schedule.py --srtf srtf_2.txt 
Process(name='p1', burst=5, arrival_time=0, priority=0, time_slice=0, waiting_time=0, turnaround_time=5)
Process(name='p4', burst=5, arrival_time=7, priority=0, time_slice=0, waiting_time=0, turnaround_time=5)
Process(name='p3', burst=11, arrival_time=5, priority=0, time_slice=0, waiting_time=5, turnaround_time=16)
Process(name='p2', burst=15, arrival_time=3, priority=0, time_slice=0, waiting_time=18, turnaround_time=33)
Average waiting time: 5.75
Average turnaround time: 14.75

File #8 (rr_1.txt)

@p1;53;0;0;20&
@p2;17;0;0;20&
@p3;68;0;0;20&
@p4;24;0;0;20&

$ python schedule.py --rr rr_1.txt
Process(name='p1', burst=53, arrival_time=0, priority=0, time_slice=20, waiting_time=81, turnaround_time=134)
Process(name='p2', burst=17, arrival_time=0, priority=0, time_slice=20, waiting_time=20, turnaround_time=37)
Process(name='p3', burst=68, arrival_time=0, priority=0, time_slice=20, waiting_time=94, turnaround_time=162)
Process(name='p4', burst=24, arrival_time=0, priority=0, time_slice=20, waiting_time=97, turnaround_time=121)
Average waiting time: 73.0
Average turnaround time: 113.5

File #9 (rr_2.txt)

@p1;10;0;0;10&
@p2;10;0;0;10&
@p3;10;0;0;10&
@p4;10;0;0;10&
@p5;10;0;0;10&
@p6;10;0;0;10&
@p7;10;0;0;10&
@p8;10;0;0;10&
@p9;10;0;0;10&
@p10;10;0;0;10&

$ python schedule.py --rr rr_2.txt
Process(name='p1', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=0, turnaround_time=10)
Process(name='p2', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=10, turnaround_time=20)
Process(name='p3', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=20, turnaround_time=30)
Process(name='p4', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=30, turnaround_time=40)
Process(name='p5', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=40, turnaround_time=50)
Process(name='p6', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=50, turnaround_time=60)
Process(name='p7', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=60, turnaround_time=70)
Process(name='p8', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=70, turnaround_time=80)
Process(name='p9', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=80, turnaround_time=90)
Process(name='p10', burst=10, arrival_time=0, priority=0, time_slice=10, waiting_time=90, turnaround_time=100)
Average waiting time: 45.0
Average turnaround time: 55.0

File #10 (rr_3.txt)

@p1;10;0;0;1&
@p2;10;0;0;1&
@p3;10;0;0;1&
@p4;10;0;0;1&
@p5;10;0;0;1&
@p6;10;0;0;1&
@p7;10;0;0;1&
@p8;10;0;0;1&
@p9;10;0;0;1&
@p10;10;0;0;1&

$ python schedule.py --rr rr_3.txt
Process(name='p1', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=81, turnaround_time=91)
Process(name='p2', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=82, turnaround_time=92)
Process(name='p3', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=83, turnaround_time=93)
Process(name='p4', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=84, turnaround_time=94)
Process(name='p5', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=85, turnaround_time=95)
Process(name='p6', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=86, turnaround_time=96)
Process(name='p7', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=87, turnaround_time=97)
Process(name='p8', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=88, turnaround_time=98)
Process(name='p9', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=89, turnaround_time=99)
Process(name='p10', burst=10, arrival_time=0, priority=0, time_slice=1, waiting_time=90, turnaround_time=100)
Average waiting time: 85.5
Average turnaround time: 95.5

@IdanBanani I've added a bunch of examples. Thanks for the comment.

@pedrominicz Can you please give me the link of the examples?

@saeid114 the examples were already provided here but maybe in a confusing way. I reformatted it to make it clearer.