Round Robin using Queue

391 Views Asked by At

My function Round Robin takes 2 parameters; the first is the list of Processes inputted and the time quantum. It Should use a queue or Priority Queue, which is a requirement.

I have a problem with the outputs of the Completion Time. It outputs incorrectly.
I also use the Class Process.

class Process:
    def __init__(self, process_id, arrival_time, burst_time, priority):
        self.process_id = process_id
        self.arrival_time = arrival_time
        self.burst_time = burst_time
        self.priority = priority
        self.completion_time = 0
        self.waiting_time = 0
        self.turnaround_time = 0
        self.remaining_time = burst_time

    def __lt__(self, other):
        if self.priority == other.priority:
            if self.arrival_time == other.arrival_time:
                return self.process_id < other.process_id
            return self.arrival_time < other.arrival_time
        if self.priority < other.priority:
            return self.priority < other.priority
        if self.burst_time == other.burst_time:
            return self.process_id < other.process_id
        if self.arrival_time == 0 and other.arrival_time != 0:
            return True
        elif self.arrival_time != 0 and other.arrival_time == 0:
            return False
        elif self.arrival_time == other.arrival_time:
            return self.burst_time < other.burst_time
        return self.burst_time < other.burst_time

I use the __lt __ for other OS Scheduling Function such as Preemptive Priority and SJF.

and Here is my Round Robin Function.

def round_robin(processes, time_quantum):
    rr = Queue()

    for process in processes:
        rr.put(process)

    waiting_time = [0] * len(processes)
    turn_around_time = [0] * len(processes)
    curr_time = 0

    while not rr.empty():
        process = rr.get()
        if process.remaining_time <= time_quantum:
            curr_time += process.remaining_time
            process.completion_time = curr_time
            process.remaining_time = 0
        else:
            curr_time += time_quantum
            process.remaining_time -= time_quantum
            rr.put(process)

        if process.remaining_time > 0:
            rr.put(process)

    for i in range(len(processes)):
        turn_around_time[i] = processes[i].completion_time - processes[i].arrival_time
        processes[i].waiting_time = turn_around_time[i] - processes[i].burst_time
        processes[i].turnaround_time = turn_around_time[i]

    return processes

This uses a queue and when the time remaining is not zero it will put it back to the queue. But the problem is that the sequence it computes.
For Example:
my inputs are:

processes = [
        Process(1, 0, 24, 4),
        Process(2, 0, 3, 3),
        Process(3, 0, 3, 2)
    ]

    time_quantum = 2

This inputs gives an incorrect output which is:

Process 1 Completion Time: 30
Process 2 Completion Time: 11
Process 3 Completion Time: 12

When it is supposed to be:

Process 1 Completion Time: 30
Process 2 Completion Time: 9
Process 3 Completion Time: 10

Please help me correct my code!

I tried another method for Round Robin.

def round_robin(processes: List[Process], time_quantum: int) -> List[Process]:
    queue = Queue()
    total_time = 0
    total_time_counted = 0
    wait_time = 0
    turnaround_time = 0
    completed_processes = []

    for process in processes:
        total_time += process.burst_time
        queue.put(process)

    while not queue.empty():
        current_process = queue.get()

        if current_process.remaining_time <= time_quantum:
            total_time_counted += current_process.remaining_time
            total_time -= current_process.remaining_time
            current_process.completion_time = total_time_counted
            current_process.turnaround_time = total_time_counted - current_process.arrival_time
            current_process.waiting_time = current_process.turnaround_time - current_process.burst_time
            completed_processes.append(current_process)
            current_process.remaining_time = 0
        else:
            total_time_counted += time_quantum
            total_time -= time_quantum
            current_process.remaining_time -= time_quantum
            queue.put(current_process)

    return completed_processes

This now uses a List. It takes the List of the Processes done. Although with the given input above.

my inputs are:

processes = [
        Process(1, 0, 24, 4),
        Process(2, 0, 3, 3),
        Process(3, 0, 3, 2)
    ]

    time_quantum = 2

It gives a correct answer:

Process 1 Completion Time: 30
Process 2 Completion Time: 9
Process 3 Completion Time: 10

but if I try other inputs such as:

processes = [
        Process(1, 0, 7, 4),
        Process(2, 2, 4, 3),
        Process(3, 4, 1, 2),
        Process(3, 5, 4, 1)
    ]

    time_quantum = 2

It gives an incorrect answer:

Process 1 Completion Time: 16
Process 2 Completion Time: 11
Process 3 Completion Time: 5
Process 4 Completion Time: 13

When the outputs should be:

Process 1 Completion Time: 16
Process 2 Completion Time: 9
Process 3 Completion Time: 7
Process 4 Completion Time: 15
0

There are 0 best solutions below