scheduling_algorithms.py

# coding: utf-8

import os
import random
from structures import *


class SchedulingAlgorithm(object):
	"""
	Classe base para todos os algoritmos
	de escalonamento, contendo os metodos
	e atributos comuns
	"""
	def __init__(self, proccess_list):
		self.proccess_list = proccess_list
		self.proccess_list_len = len(proccess_list)
		self.turnaround_per_proccess = {p.id: 0 for p in self.proccess_list}
		self.proccess_tuple = tuple(self.proccess_list)
		self.waiting_times = {p.id: set() for p in self.proccess_list}
		self.waiting_times_count = {
			p.id: -(p.pcb.arrive_time) for p in self.proccess_list
		}

	@classmethod
	def __repr__(cls):
		return cls.__name__
	
	def _clean_waiting_times_count(self):
		"""
		zera os contadores de tempo de espera
		"""
		self.waiting_times_count = {
			p.id: -(p.pcb.arrive_time) for p in self.proccess_tuple
		}	

	def get_turnaround_time(self, proccess_id):
		"""
		retorna o tempo de turnaround de um processo
		definido pelo seu id
		"""
		return self.turnaround_per_proccess[proccess_id]
		
	def get_average_turnaround_time(self):
		"""
		retorna o tempo medio de turnaround 
		dos processos
		"""
		return sum(self.turnaround_per_proccess.values()) / self.proccess_list_len

	def _set_turnaround_time(self, time, proccess):
		"""
		seta o turnaround de um processo
		"""
		self.turnaround_per_proccess[proccess.id] = (time - proccess.pcb.arrive_time)

	def sort_proccesses(self):
		"""
		define como os processos serao priorizados
		deve ser implementado em uma sub classe
		"""
		pass

	def _increment_wait_time(self, time, actual_proccess):
		"""
		incrementa o tempo de espera para todos os
		processos, exceto para o que esta executando
		"""
		for proccess in self.proccess_list:
			if proccess != actual_proccess:
				self.waiting_times_count[proccess.id] += time
			else:
				self.waiting_times[actual_proccess.id] = self.waiting_times_count[proccess.id]

	def get_waiting_time(self, proccess_id):
		"""
		retorna o tempo de espera de um processo
		"""
		return float(self.waiting_times[proccess_id])

	def get_average_waiting_time(self):
		"""
		retorna o tempo de espera medio de todos
		os processos
		"""
		return sum([self.get_waiting_time(p.id) for p in self.proccess_tuple]) / self.proccess_list_len

	def run(self):
		"""
		roda o algoritmo de escalonamento
		"""
		time = 0
		for index, proccess in enumerate(self.proccess_list):
			self._increment_wait_time(time, proccess)
			time += proccess.pcb.burst
			self._set_turnaround_time(time, proccess)



class FCFS(SchedulingAlgorithm):
	"""
	FCFS
	Primeiro que chega eh o primeiro que sai
	Nao premptivo
	"""
	def __init__(self, proccess_list):
		super(FCFS, self).__init__(proccess_list)
		self.sort_proccesses()
		
	def sort_proccesses(self):
		"""
		ordena os processos pelo tempo de chegada
		"""
		return self.proccess_list.sort(key=lambda proccess: proccess.pcb.arrive_time)

	def _increment_wait_time(self, time, proccess):
		self.waiting_times_count[proccess.id] += time
	
	def get_waiting_time(self, proccess_id):
		return float(self.waiting_times_count[proccess_id])
	
	
class SJF(SchedulingAlgorithm):
	"""
	Executa primeiro os processos com menor burst.
	Se os processos chegarem em tempos diferentes, entao
	ordena [1:] por tempo de burst e o primeiro por tempo
	de chegada
	Nao premptivo
	"""
	def __init__(self, proccess_list):
		super(SJF, self).__init__(proccess_list)
		self.sort_proccesses()

	def sort_proccesses(self):
		"""
		ordena os processos pelo menor tempo de burst
		"""
		equals = True
		for proccess in self.proccess_list[1:]:
			if proccess.pcb.arrive_time != self.proccess_list[0].pcb.arrive_time:
				equals = False

		if equals:
			self.proccess_list.sort(key=lambda proccess: proccess.pcb.burst)
		else:
			self.proccess_list.sort(key=lambda proccess: proccess.pcb.arrive_time)
			self.proccess_list = [self.proccess_list.pop(0)]
			new_list = list(self.proccess_tuple[1:])
			new_list.sort(key=lambda proccess: proccess.pcb.burst)
			self.proccess_list.extend(new_list)

	def _increment_wait_time(self, time, proccess):
		self.waiting_times_count[proccess.id] += time
	
	def get_waiting_time(self, proccess_id):
		return float(self.waiting_times_count[proccess_id])

class SRTF(SchedulingAlgorithm):
	"""
	Shortest Remaining Time First
	prioriza os processos que tem o menor
	tempo de burst restante. Eh premptivo
	"""
	def __init__(self, proccess_list):
		super(SRTF, self).__init__(proccess_list)
		self.sort_proccesses()

	def sort_proccesses(self, by_burst=None):
		if by_burst is not None:
			self.proccess_list.sort(key=lambda  proccess: proccess.pcb.burst)
		else:
			self.proccess_list.sort(key=lambda  proccess: proccess.pcb.arrive_time)

	def _has_proccess_arrived_in_current_time(self, time):
		"""
		verifica se algum processo chegou
		no tempo atual
		"""
		for proccess in self.proccess_list: 
			if proccess.pcb.arrive_time == time:
				return proccess
		return None

	def _context_change(self, time, actual_proccess):
		"""
		verifica se eh necessario fazer troca de contexto
		entre processos
		"""
		proccess = self._has_proccess_arrived_in_current_time(time)
		if proccess is not None:
			if proccess.pcb.burst < actual_proccess.pcb.burst:
				return proccess
		return actual_proccess

	def _proccess_finished(self, time, proccess):
		"""
		metodo chamado com o processo termina
		"""
		self.proccess_list.remove(proccess)
		self.turnaround_per_proccess[proccess.id] = time - proccess.pcb.arrive_time

	def run(self):
		time = 0
		proccess = self.proccess_list[0]
		while True:
			proccess = self._context_change(time, proccess)

			if proccess.pcb.burst == 0:
				self._proccess_finished(time, proccess)
				if not self.proccess_list:
					return
				if time > self.proccess_list[-1].pcb.arrive_time:
					self.sort_proccesses(by_burst=True)
				proccess = self.proccess_list[0]
			proccess.pcb.burst -= 1
			self._increment_wait_time(1, proccess)
			time += 1


class RoundRobin(SchedulingAlgorithm):
	"""
	Define quantum de tempo para cada processo executar
	padrao eh 20
	premptivo
	"""
	def __init__(self, proccess_list, quantum=20, break_on_cicle=False):
		super(RoundRobin, self).__init__(proccess_list)
		self.sort_proccesses()
		self.quantum = quantum
		self.break_on_cicle = break_on_cicle
		self.index = 0

	def _context_change(self, proccess):
		if self.index < len(self.proccess_list) - 1:
			self.index += 1
			return self.proccess_list[self.index]
		else:
			self.index = 0
			return self.proccess_list[self.index]

	def _proccess_finished(self, time, proccess):
		self.proccess_list.remove(proccess)
		self.index -= 1
		self._set_turnaround_time(time, proccess)

	def run(self):
		time = 0
		cicle = 0
		proccess = self.proccess_list[0]
		while self.proccess_list:
			if proccess.pcb.burst <= self.quantum:
				time += proccess.pcb.burst
				self._increment_wait_time(proccess.pcb.burst, proccess)
				self._proccess_finished(time, proccess)

				if not self.proccess_list:
					break
			else:
				proccess.pcb.burst -= self.quantum
				time += self.quantum
				self._increment_wait_time(self.quantum, proccess)

			if self.break_on_cicle:
				cicle += 1
				self._set_turnaround_time(time, proccess)
			proccess = self._context_change(proccess)
			if self.break_on_cicle and cicle == len(self.proccess_tuple):
				break


class FilaMultiNivelComFeedBack(SchedulingAlgorithm):
	"""
	Uma Fila Multinivel contem 3 filas
	Q0 = RoundRobin com quantum de 8
	Q1 = RoundRobin com quantum de 16
	Q2 = FCFS
	premptivo
	"""
	def __init__(self, proccess_list):
		super(FilaMultiNivelComFeedBack, self).__init__(proccess_list)
		self.sort_proccesses()
		self.proccess_tuple = tuple(proccess_list)
		self.turnaround_per_proccess = {p.id: 0 for p in self.proccess_tuple}
		self.q0 = RoundRobin(self.proccess_list, quantum=8, break_on_cicle=True)
		self.q1 = None
		self.q2 = None
		self.waiting_count = {
			p.id: -(p.pcb.arrive_time) for p in self.proccess_list
		}

	def sort_proccesses(self):
		return

	def get_waiting_time(self, proccess_id):
		return self.waiting_times_count[proccess_id]

	def _caulculate_waiting_and_turnaround_in_all_queues(self):
		"""
		calcula o tempo de espera  e turnaroud dos processos somando o tempo de 
		cada fila
		"""
		self._clean_waiting_times_count()
		for queue in [self.q0, self.q1, self.q2]:
			for proccess in self.proccess_tuple:
				if proccess.id in queue.waiting_times:
					self.waiting_times_count[proccess.id] += queue.get_waiting_time(proccess.id)
				if proccess.id in queue.turnaround_per_proccess:
					self.turnaround_per_proccess[proccess.id] += queue.get_turnaround_time(proccess.id)
		
	def run(self):
		self.q0.run()
		if self.proccess_list:
			self.q1 = RoundRobin(self.proccess_list, quantum=16, break_on_cicle=True)
			self.q1.run()
		if self.proccess_list:
			self.q2 = FCFS(self.proccess_list)
			self.q2.run()

		self._caulculate_waiting_and_turnaround_in_all_queues()


def main():
	menu = Menu([FCFS, SJF, SRTF, RoundRobin, FilaMultiNivelComFeedBack])
	menu.quantity = int(input("Entre com a quantidade de processos: "))
	os.system("clear")

	scheduling_algorithms_map = {
		1: FCFS,
		2: SJF,
		3: SRTF,
		4: RoundRobin,
		5: FilaMultiNivelComFeedBack
	}

	for i in range(menu.quantity):
		burst = int(input("Entre com o burst do processo[%i]: " % (i + 1)))
		os.system("clear")
		arrive_time = int(input("Entre com o tempo de chegada do processo[%i]: " % (i + 1)))
		os.system("clear")
		priority = int(input("Entre com a prioridade do processo[%i]: " % (i + 1)))
		os.system("clear")

		menu.proccess_list.append(Process(PCB(burst, arrive_time, priority), random.randint(0,100)))

	menu.print_options()
	Scheduler = None
	while Scheduler is None:
		menu.scheduling_algorithm = int(input('Entre com o algoritmo de escalonamento:'))
		os.system("clear")
		Scheduler = scheduling_algorithms_map.get(menu.scheduling_algorithm)

		if Scheduler is None:
			print TermColors.RED + "Entre com um número entre 1 - 5" + TermColors.ENDC
	

	scheduler = Scheduler(menu.proccess_list)
	if isinstance(scheduler, RoundRobin):
		quantum = int(input("Entre com o quantum de tempo: "))
		os.system("clear")
		scheduler.quantum = quantum

	menu.print_proccesses()
	print "Rodando o escalonador: " + TermColors.RED + str(scheduler) + TermColors.ENDC + "\n"
	scheduler.run()

	menu.print_metrics(scheduler)
	menu.print_averages(scheduler)
	print "\n"

if __name__ == '__main__':
	main()

scheduling_algorithms_tests.py

# coding: utf-8

import unittest
from scheduling_algorithms import FCFS, SJF, SRTF, RoundRobin, FilaMultiNivelComFeedBack
from structures import Process, PCB

class ScheduleAlgorithm(unittest.TestCase):

	def test_fcfs(self):
		p1 = Process(PCB(24 ,0 ,1), 1)
		p2 = Process(PCB(3 ,1 ,1), 2)
		p3 = Process(PCB(3 ,2 ,1), 3)

		schedule = FCFS([p1, p2, p3])
		schedule.run()

		self.assertEquals(schedule.get_turnaround_time(p1.id), 24)
		self.assertEquals(schedule.get_turnaround_time(p2.id), 26)
		self.assertEquals(schedule.get_turnaround_time(p3.id), 28)

		self.assertEquals(schedule.get_waiting_time(p1.id), 0)
		self.assertEquals(schedule.get_waiting_time(p2.id), 23)
		self.assertEquals(schedule.get_waiting_time(p3.id), 25)

		self.assertEquals(schedule.get_average_waiting_time(), 16)
		self.assertEquals(schedule.get_average_turnaround_time(), 26)

	def test_fcfs_2(self):
		p1 = Process(PCB(6 ,0 ,1), 1)
		p2 = Process(PCB(8 ,0 ,1), 2)
		p3 = Process(PCB(7 ,0 ,1), 3)
		p4 = Process(PCB(3 ,0 ,1), 4)

		schedule = FCFS([p1, p2, p3, p4])
		schedule.run()

		self.assertEquals(schedule.get_waiting_time(p1.id), 0)
		self.assertEquals(schedule.get_waiting_time(p2.id), 6)
		self.assertEquals(schedule.get_waiting_time(p3.id), 14)
		self.assertEquals(schedule.get_average_waiting_time(), 10.25)

		self.assertEquals(schedule.get_turnaround_time(p1.id), 6)
		self.assertEquals(schedule.get_turnaround_time(p2.id), 14)
		self.assertEquals(schedule.get_turnaround_time(p3.id), 21)
		self.assertEquals(schedule.get_turnaround_time(p4.id), 24)

		self.assertEquals(schedule.get_average_turnaround_time(), 16)		

	def test_sjf(self):
		p1 = Process(PCB(6 ,0 ,1), 1)
		p2 = Process(PCB(8 ,0 ,1), 2)
		p3 = Process(PCB(7 ,0 ,1), 3)
		p4 = Process(PCB(3 ,0 ,1), 4)

		schedule = SJF([p1, p2, p3, p4])
		schedule.run()

		self.assertEquals(schedule.get_turnaround_time(p1.id), 9)
		self.assertEquals(schedule.get_turnaround_time(p2.id), 24)
		self.assertEquals(schedule.get_turnaround_time(p3.id), 16)
		self.assertEquals(schedule.get_turnaround_time(p4.id), 3)

		self.assertEquals(schedule.get_waiting_time(p1.id), 3)
		self.assertEquals(schedule.get_waiting_time(p2.id), 16)
		self.assertEquals(schedule.get_waiting_time(p3.id), 9)
		self.assertEquals(schedule.get_waiting_time(p4.id), 0)

		self.assertEquals(schedule.get_average_waiting_time(), 7)
		self.assertEquals(schedule.get_average_turnaround_time(), 13)

	def test_sjf_2(self):
		p1 = Process(PCB(8 ,0 ,1), 1)
		p2 = Process(PCB(4 ,1 ,1), 2)
		p3 = Process(PCB(9 ,2 ,1), 3)
		p4 = Process(PCB(5 ,3 ,1), 4)

		schedule = SJF([p1, p2, p3, p4])
		schedule.run()

		self.assertEquals(schedule.get_turnaround_time(p1.id), 8)
		self.assertEquals(schedule.get_turnaround_time(p2.id), 11)
		self.assertEquals(schedule.get_turnaround_time(p3.id), 24)
		self.assertEquals(schedule.get_turnaround_time(p4.id), 14)

		self.assertEquals(schedule.get_waiting_time(p1.id), 0)
		self.assertEquals(schedule.get_waiting_time(p2.id), 7)
		self.assertEquals(schedule.get_waiting_time(p3.id), 15)
		self.assertEquals(schedule.get_waiting_time(p4.id), 9)

		self.assertEquals(schedule.get_average_waiting_time(), 7.75)
		self.assertEquals(schedule.get_average_turnaround_time(), 14)

	def test_srtf(self):
		p1 = Process(PCB(8 ,0 ,1), 1)
		p2 = Process(PCB(4 ,1 ,1), 2)
		p3 = Process(PCB(9 ,2 ,1), 3)
		p4 = Process(PCB(5 ,3 ,1), 4)

		schedule = SRTF([p1, p2, p3, p4])
		schedule.run()

		self.assertEquals(schedule.get_waiting_time(p1.id), 9)
		self.assertEquals(schedule.get_waiting_time(p2.id), 0)
		self.assertEquals(schedule.get_waiting_time(p3.id), 15)
		self.assertEquals(schedule.get_waiting_time(p4.id), 2)

		self.assertEquals(schedule.get_turnaround_time(p1.id), 17)
		self.assertEquals(schedule.get_turnaround_time(p2.id), 4)
		self.assertEquals(schedule.get_turnaround_time(p3.id), 24)
		self.assertEquals(schedule.get_turnaround_time(p4.id), 7)

		self.assertEquals(schedule.get_average_waiting_time(), 6.5)
		self.assertEquals(schedule.get_average_turnaround_time(), 13)

	def test_round_robin(self):
		p1 = Process(PCB(53 ,0 ,0), 1)
		p2 = Process(PCB(17 ,0 ,0), 2)
		p3 = Process(PCB(68 ,0 ,0), 3)
		p4 = Process(PCB(24 ,0 ,0), 4)

		schedule = RoundRobin([p1, p2, p3, p4], quantum=20)
		schedule.run()
		self.assertEquals(schedule.get_waiting_time(p1.id), 81)
		self.assertEquals(schedule.get_waiting_time(p2.id), 20)
		self.assertEquals(schedule.get_waiting_time(p3.id), 94)
		self.assertEquals(schedule.get_waiting_time(p4.id), 97)
		self.assertEquals(schedule.get_turnaround_time(p1.id), 134)
		self.assertEquals(schedule.get_turnaround_time(p2.id), 37)
		self.assertEquals(schedule.get_turnaround_time(p3.id), 162)
		self.assertEquals(schedule.get_turnaround_time(p4.id), 121)
		self.assertEquals(schedule.get_average_waiting_time(), 73)
		self.assertEquals(schedule.get_average_turnaround_time(), 113)

	def test_multinivel(self):
		p1 = Process(PCB(8 ,0 ,0), 1)
		p2 = Process(PCB(8 ,0 ,0), 2)
		p3 = Process(PCB(16 ,0 ,0), 3)
		p4 = Process(PCB(16 ,0 ,0), 4)
		p5 = Process(PCB(40 ,0 ,0), 5)

		schedule = FilaMultiNivelComFeedBack([p1, p2, p3, p4, p5])
		schedule.run()

		self.assertEquals(schedule.get_waiting_time(p1.id), 0)
		self.assertEquals(schedule.get_waiting_time(p2.id), 8)
		self.assertEquals(schedule.get_waiting_time(p3.id), 16)
		self.assertEquals(schedule.get_waiting_time(p4.id), 32)
		self.assertEquals(schedule.get_waiting_time(p5.id), 48)
		self.assertEquals(schedule.get_turnaround_time(p1.id), 8)
		self.assertEquals(schedule.get_turnaround_time(p2.id), 16)
		self.assertEquals(schedule.get_turnaround_time(p3.id), 32)
		self.assertEquals(schedule.get_turnaround_time(p4.id), 48)
		self.assertEquals(schedule.get_turnaround_time(p5.id), 88)
		self.assertEquals(schedule.get_average_waiting_time(), 20.8)
		self.assertEquals(schedule.get_average_turnaround_time(), 38)


if __name__ == '__main__':
	unittest.main()

structures.py

# coding: utf-8


class PCB(object):

	def __init__(self, burst, arrive_time, priority):
		self.burst = burst
		self.arrive_time  = arrive_time
		self.priority = priority

	def __repr__(self):
		return TermColors.BLUE + "Arrive Time: %s \npriority: %s \nBurst: %s \n" % tuple(self.__dict__.values()) + TermColors.ENDC


class Menu(object):
	def __init__(self, algorithms):	
		self.proccess_list = []
		self.algorithms = algorithms

	def print_proccesses(self):
		print TermColors.YELLOW + "Processos \n" + TermColors.ENDC
		for proccess in self.proccess_list:
			print proccess

	@staticmethod
	def print_metrics(scheduler):
		for proccess in scheduler.proccess_tuple:
			print "Tempo de espera para o processo[%i] = %4.2f" % (proccess.id, scheduler.get_waiting_time(proccess.id))
			print "Tempo de turnaround para o processo[%i] = %4.2f" % (proccess.id, scheduler.get_turnaround_time(proccess.id))

	@staticmethod
	def print_averages(scheduler):
		print "Tempo de espera médio = %4.2f" % scheduler.get_average_waiting_time()
		print "Tempo de turnaround médio = %4.2f" % scheduler.get_average_turnaround_time()

	def print_options(self):
		for index, algorithm in enumerate(self.algorithms):
			print TermColors.BLUE + str(index + 1) + TermColors.ENDC + " : " + TermColors.RED + algorithm.__name__ + TermColors.ENDC

class TermColors(object):
	BLUE = '\033[94m'
	GREEN = '\033[92m'
	YELLOW = '\033[93m'
	RED = '\033[91m'
	ENDC = '\033[0m'

class Process(object):
	def __init__(self, pcb, _id):
		self.pcb =  pcb
		self.id = _id

	def __repr__(self):
		return TermColors.BLUE + "Id: %s \n" % self.id + TermColors.ENDC +  self.pcb.__repr__() + TermColors.GREEN + "---------------" + TermColors.ENDC