nicholaskajoh/round_robin.py

## round_robin.py
import random
import matplotlib.pyplot as plt
import numpy as np

def generateWorkload():
    n = 20 # size of workload
    inter_arrival_time_range = (1, 15) # nanoseconds
    burst_time_range = (70, 130) # nanoseconds
    processes = []
    for i in range(n):
        arrival_time = random.randint(*inter_arrival_time_range)
        burst_time = random.randint(*burst_time_range)
        processes.append({
            'process_name': 'P' + str(i),
            'arrival_time': 0 if i == 0 else arrival_time + processes[i - 1]['arrival_time'],
            'burst_time': burst_time,
            'waiting_time': 0,
            'time_to_burst': burst_time,
            'completion_time': -1,
        })

    processes = sorted(processes, key=lambda process: process['arrival_time']) # sort processes by arrival time

    return processes


class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

    def peek(self):
        return self.items[-1]

    def getItems(self):
        return self.items


def roundRobin(q):
    process_queue = Queue()
    all_processes = generateWorkload()
    time = 0
    idle_time = 0
    MAX_IDLE_TIME = 500
    redux = []
    is_idle = True
    current_process_time = 0

    while idle_time < MAX_IDLE_TIME:
        # find all processes that have arrived and enqueue them
        for process in all_processes:
            if process['arrival_time'] == time:
                process_queue.enqueue(process)

        # give next process in queue cpu time
        if is_idle and process_queue.size() > 0:
            is_idle = False
            current_process = process_queue.peek()
            redux.append({
                'process_name': current_process['process_name'],
                'action': 'IN',
                'time': time,
            })

        # dequeue if process has been completed
        if process_queue.size() > 0:
            current_process = process_queue.peek()
            if current_process['time_to_burst'] == 0:
                process_queue.dequeue()
                current_process['completion_time'] = time
                is_idle = True

        # dequeue process if quantum time has been exausted
        # enqueue same process if it hasn't yet been completed
        if current_process_time == q and process_queue.size() > 0:
            current_process_time = 0
            is_idle = True
            dequeued_process = process_queue.dequeue()
            if dequeued_process['time_to_burst'] > 0:
                process_queue.enqueue(dequeued_process)
            redux.append({
                'process_name': dequeued_process['process_name'],
                'action': 'OUT',
                'time': time,
            })

        # update time
        if is_idle:
            idle_time += 1
        else:
            current_process_time += 1
            current_process = process_queue.peek()
            current_process['time_to_burst'] -= 1
        time += 1
        if process_queue.size() > 0:
            current_process = process_queue.peek()
            processes_in_queue = process_queue.getItems()
            for process in processes_in_queue:
                if process != current_process:
                    process['waiting_time'] += 1


    waiting_times = []
    turn_around_times = []

    for process in all_processes:
        waiting_times.append(process['waiting_time'])
        turn_around_times.append(process['completion_time'] - process['arrival_time'])

    average_waiting_time = sum(waiting_times) / float(len(waiting_times))
    average_turn_around_time = sum(turn_around_times) / float(len(turn_around_times))
    num_context_switches = len(redux) - 1 # minus first process that enters the cpu

    # print processes
    print('q =', q)
    for process in all_processes:
        print(process)
    print('\n')

    return (num_context_switches, average_waiting_time, average_turn_around_time, redux)


def drawHistogram(figure, data, y_label):
    figure = plt.figure(figure)
    x = np.arange(3)
    plt.bar(x, data)
    plt.xticks(x, ['q=10', 'q=25', 'q=50'])
    plt.ylabel(y_label)
    return figure

def drawTimeSeries(figure, redux, title):
    x, y, ylabels = [], [], []
    processes = set()
    for event in redux:
        x.append(event['time'])
        ylabels.append(event['process_name'])
        processes.add(event['process_name'])
    processes = list(processes)
    for ylabel in ylabels:
        y.append(processes.index(ylabel))

    fig, ax = plt.subplots()
    fig.suptitle(title, fontsize=12)
    ax.plot(x, y, '-o', markersize=1)
    ax.yaxis.set_ticks(np.arange(len(processes)))
    ax.yaxis.set_ticklabels(processes)
    plt.xlabel("Time")
    plt.ylabel("Process")
    return fig

if __name__ =="__main__":
    qs = [10, 25, 50]
    average_tats = [] # turn around times
    average_wts = [] # waiting times
    numbers_css = [] # numbers of context switches

    tseries_plots = [None, None, None]

    for q in qs:
        num_context_switches, average_waiting_time, average_turn_around_time, redux = roundRobin(q)
        average_tats.append(average_turn_around_time)
        average_wts.append(average_waiting_time)
        numbers_css.append(num_context_switches)
        tseries_plots[qs.index(q)] = drawTimeSeries(qs.index(q) + 1, redux, 'Time series for q=' + str(q))

    fig1 = drawHistogram(8, average_tats, 'Average turn around time (ns)')
    fig2 = drawHistogram(9, average_wts, 'Average waiting time (ns)')
    fig3 = drawHistogram(10, numbers_css, 'Number of context switches')
    fig1.show()
    fig2.show()
    fig3.show()
    tseries_plots[0].show()
    tseries_plots[1].show()
    tseries_plots[2].show()
    input()

# Comment on the effect of the different values of Q on the behavior of the algorithm based on the histogram
# Larger values of Q lead to shorter turn around times, waiting times and number of context switches, and vice versa
# A larger time quantum (Q) is therefore recommended when scheduling processes with Round Robin
	import random
	import matplotlib.pyplot as plt
	import numpy as np

	def generateWorkload():
	n = 20 # size of workload
	inter_arrival_time_range = (1, 15) # nanoseconds
	burst_time_range = (70, 130) # nanoseconds
	processes = []
	for i in range(n):
	arrival_time = random.randint(*inter_arrival_time_range)
	burst_time = random.randint(*burst_time_range)
	processes.append({
	'process_name': 'P' + str(i),
	'arrival_time': 0 if i == 0 else arrival_time + processes[i - 1]['arrival_time'],
	'burst_time': burst_time,
	'waiting_time': 0,
	'time_to_burst': burst_time,
	'completion_time': -1,
	})

	processes = sorted(processes, key=lambda process: process['arrival_time']) # sort processes by arrival time

	return processes


	class Queue:
	def __init__(self):
	self.items = []

	def isEmpty(self):
	return self.items == []

	def enqueue(self, item):
	self.items.insert(0, item)

	def dequeue(self):
	return self.items.pop()

	def size(self):
	return len(self.items)

	def peek(self):
	return self.items[-1]

	def getItems(self):
	return self.items


	def roundRobin(q):
	process_queue = Queue()
	all_processes = generateWorkload()
	time = 0
	idle_time = 0
	MAX_IDLE_TIME = 500
	redux = []
	is_idle = True
	current_process_time = 0

	while idle_time < MAX_IDLE_TIME:
	# find all processes that have arrived and enqueue them
	for process in all_processes:
	if process['arrival_time'] == time:
	process_queue.enqueue(process)

	# give next process in queue cpu time
	if is_idle and process_queue.size() > 0:
	is_idle = False
	current_process = process_queue.peek()
	redux.append({
	'process_name': current_process['process_name'],
	'action': 'IN',
	'time': time,
	})

	# dequeue if process has been completed
	if process_queue.size() > 0:
	current_process = process_queue.peek()
	if current_process['time_to_burst'] == 0:
	process_queue.dequeue()
	current_process['completion_time'] = time
	is_idle = True

	# dequeue process if quantum time has been exausted
	# enqueue same process if it hasn't yet been completed
	if current_process_time == q and process_queue.size() > 0:
	current_process_time = 0
	is_idle = True
	dequeued_process = process_queue.dequeue()
	if dequeued_process['time_to_burst'] > 0:
	process_queue.enqueue(dequeued_process)
	redux.append({
	'process_name': dequeued_process['process_name'],
	'action': 'OUT',
	'time': time,
	})

	# update time
	if is_idle:
	idle_time += 1
	else:
	current_process_time += 1
	current_process = process_queue.peek()
	current_process['time_to_burst'] -= 1
	time += 1
	if process_queue.size() > 0:
	current_process = process_queue.peek()
	processes_in_queue = process_queue.getItems()
	for process in processes_in_queue:
	if process != current_process:
	process['waiting_time'] += 1


	waiting_times = []
	turn_around_times = []

	for process in all_processes:
	waiting_times.append(process['waiting_time'])
	turn_around_times.append(process['completion_time'] - process['arrival_time'])

	average_waiting_time = sum(waiting_times) / float(len(waiting_times))
	average_turn_around_time = sum(turn_around_times) / float(len(turn_around_times))
	num_context_switches = len(redux) - 1 # minus first process that enters the cpu

	# print processes
	print('q =', q)
	for process in all_processes:
	print(process)
	print('\n')

	return (num_context_switches, average_waiting_time, average_turn_around_time, redux)


	def drawHistogram(figure, data, y_label):
	figure = plt.figure(figure)
	x = np.arange(3)
	plt.bar(x, data)
	plt.xticks(x, ['q=10', 'q=25', 'q=50'])
	plt.ylabel(y_label)
	return figure

	def drawTimeSeries(figure, redux, title):
	x, y, ylabels = [], [], []
	processes = set()
	for event in redux:
	x.append(event['time'])
	ylabels.append(event['process_name'])
	processes.add(event['process_name'])
	processes = list(processes)
	for ylabel in ylabels:
	y.append(processes.index(ylabel))

	fig, ax = plt.subplots()
	fig.suptitle(title, fontsize=12)
	ax.plot(x, y, '-o', markersize=1)
	ax.yaxis.set_ticks(np.arange(len(processes)))
	ax.yaxis.set_ticklabels(processes)
	plt.xlabel("Time")
	plt.ylabel("Process")
	return fig

	if __name__ =="__main__":
	qs = [10, 25, 50]
	average_tats = [] # turn around times
	average_wts = [] # waiting times
	numbers_css = [] # numbers of context switches

	tseries_plots = [None, None, None]

	for q in qs:
	num_context_switches, average_waiting_time, average_turn_around_time, redux = roundRobin(q)
	average_tats.append(average_turn_around_time)
	average_wts.append(average_waiting_time)
	numbers_css.append(num_context_switches)
	tseries_plots[qs.index(q)] = drawTimeSeries(qs.index(q) + 1, redux, 'Time series for q=' + str(q))

	fig1 = drawHistogram(8, average_tats, 'Average turn around time (ns)')
	fig2 = drawHistogram(9, average_wts, 'Average waiting time (ns)')
	fig3 = drawHistogram(10, numbers_css, 'Number of context switches')
	fig1.show()
	fig2.show()
	fig3.show()
	tseries_plots[0].show()
	tseries_plots[1].show()
	tseries_plots[2].show()
	input()

	# Comment on the effect of the different values of Q on the behavior of the algorithm based on the histogram
	# Larger values of Q lead to shorter turn around times, waiting times and number of context switches, and vice versa
	# A larger time quantum (Q) is therefore recommended when scheduling processes with Round Robin