queues.py

class CircularQueue: # Creates a new empty queue: def __init__(self, capacity): # Check validity of capacity type and value assert isinstance(capacity, int), ('Error: Type error: %s' % (type(capacity))) assert capacity >= 0, ('Error: Illegal capacity: %d' % (capacity))

# Initialize private attributes self.__items = [] self.__capacity = capacity self.__count=0 self.__head=0 self.__tail=0

# Allocate space for the circular queue for i in range(self.__capacity): self.__items.append(None) # Adds a new item to the back of the queue, and returns nothing: def enqueue(self, item): ''' This function enqueues the item into the back of the queue :param item: The item to be queued :return: No returns ''' if self.__count == self.__capacity: raise Exception('Error: Queue is Full') if len(self.__items)

# Removes and returns the front-most item in the queue. # Returns nothing if the queue is empty. def dequeue(self): ''' Dequeue the the element from the front of the queue and return the value :return: Returns the object that is dequeued ''' if self.__count == 0: raise Exception('Error: Queue is empty') item = self.__items[self.__head] self.__items[self.__head] = None self.__count -= 1 self.__head = (self.__head+1)%self.__capacity return item ''' Remember to check the proper conditions (some hints) 1. get item at the head of queue 2. remove the item from the head of queue 3. decrease stored size of queue 4. Shift the head 5. return the item ''' # Returns the front-most item in the queue, and DOES NOT change the queue. def peek(self): if self.__count == 0: raise Exception('Error: Queue is empty') return self.__items[self.__head]

# Returns True if the queue is empty, and False otherwise: def is_empty(self): return self.__count == 0 # Returns True if the queue is full, and False otherwise: def is_full(self): return self.__count == self.__capacity # Returns the number of items in the queue: def size(self): return self.__count # Returns the capacity of the queue: def capacity(self): return self.__capacity # Removes all items from the queue, and sets the size to 0 # clear() should not change the capacity def clear(self): self.__items = [] self.__count = 0 self.__head = 0 self.__tail = 0 # Returns a string representation of the queue: def __str__(self): str_exp = "]" i = self.__head for j in range(self.__count): str_exp += str(self.__items[i]) + " " i = (i+1) % self.__capacity return str_exp + "]"

# Returns a string representation of the object CircularQueue def __repr__(self): return str(self.__items) + " H= " + str(self.__head) + " T="+str(self.__tail) + " (" +str(self.__count)+"/"+str(self.__capacity)+")"

import random from queues import CircularQueue

class Job: def __init__(self, priority = 0, process_name = None): ''' Object for job description of various types :param priority: 0 for low and 1 for high priority :param process_name: Description of the process (optional) ''' self.__id = random.randint(1,1000) self.__priority = priority if process_name is None: if self.high_priority(): self.__process_name = random.choice(['[OS] File Write', '[OS] File Read', '[OS] Display']) else: self.__process_name = random.choice(['[USER] Browser', '[USER] Music', '[USER] Calculator'])

def high_priority(self): ''' Priority of the job :return: True if process of high priority ''' return self.__priority == 1

def process_name(self): ''' Process name of the job :return: returns the process name for the job ''' return self.__process_name

def __str__(self): return '{:

def get_job(): ''' Return a job type , trying to simulate a queueing process for the CPU :return: Returns the Job Object or none ''' if random.random()

def process_complete(): ''' Returns a boolean value telling if the current process is complete executing or not :return: True/False depending the process is complete or not ''' if random.random()

def main(): process_running = False # tells the state of the processor True if a process is running current_job = None high_priority_queue = CircularQueue(1000) low_priority_queue = CircularQueue(1000) # we will run our computer for 10 time steps time_steps = 10 for t in range(time_steps): print("######## RUN : {} ######## ".format(t+1)) job = get_job() # get a job if job: print("Job {} generated ".format(job.process_name()))

# Put the job in the appropriate queue ######################## ### ENTER YOUR CODE #### ########################

######################## #### END OF CODE ###### ########################

################################### ## Get the status of current job ## ################################### if process_running: current_process_status = process_complete() if current_process_status: process_running = False print("JOB COMPLETED {}".format(current_job)) current_job = None

####################### # depending on the status fo current job # get the next job and load on the processer ######################## if not process_running: ######################## ### ENTER YOUR CODE #### ######################## ## Remove the pass ## Check the status of queue , and dequeue the appropriate job ## set the job to current_job ## set process_running to True if job dequeued pass

######################## #### END OF CODE ###### ######################## if not process_running: print(" [PROCESSOR] Idle") else: print(" [PROCESSOR] Busy") # status of queues print("Jobs waiting in High Priority Queue :{}".format(high_priority_queue.size())) print("Jobs waiting in Low Priority Queue :{} ".format(low_priority_queue.size()))

if __name__ == '__main__': main()

Exercise 3: Using High and Low Priority Queues: Background information: Computing devices like laptops and smartphones may have multiple computing cores, which allow us to run multiple programs at once. But what happens when the number of programs that we want to run is more than the number of cores in our device? For example, what if we want to run & programs on a device with only 2 CPU cores? Job scheduling helps the device to run the most important programs first. Imagine that each program we want to run submits a job request to the operating system before it is actually run. Those jobs are stored in either a high-priority queue or a low-priority queue, depending on how important the program is. For example, processes that are fundamental to how the device operates (e.g. displaying things to the screen, dealing with system input and output) have a higher priority than user-installed applications (e.g. web browsers, music playing app, calculator app). At any given time, jobs waiting in the high-priority queue will be executed first, in the order that they were requested in. If there are no high-priority jobs waiting to be executed, then the jobs in the low-priority queue can be executed. Problem: 1. Download labb_priority.py from eClass, and save in the same folder as your other lab files. This file contains a Job class definition, as well as two functions that have already been completed for you (get_job (), and process_complete()). Read the comments for this code to understand what it does. 2. Add code to the main() function in this file so that every time a new job is created (i.e. every time get_job() is called), that job object is enqueued to the appropriate queue: high_priority_queue or low_priority_queue. Hint: use the Job's high_priority() method to check if a job is high-priority (True) or low- priority (False). Notice that get_job() may also return no job (None) which will NOT go into either queue, so that must be checked for as well. 3. Complete the main() function so that whenever a process has finished (indicated when process_complete() returns True), a new process is started by dequeuing a job from the appropriate queue. i.e. If there is at least one job in the high-priority queue, it should be dequeued and assigned to the current job variable. However, if the high-priority queue is empty and there is at least one job in the low-priority queue, then it should be dequeued and assigned to the current_job variable. If a job has been successfully dequeued from either queue, the process_running variable should be set to True. Sample Output (your output may differ since the jobs are generated randomly): ######## RUN : 1 ######## Job [USER] Music generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue :0 ######## RUN : 2 ######## Job [OS] Display generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :1 Jobs waiting in Low Priority Queue :0 #### #### RUN : 3 ######## Job [USER] Browser generated JOB COMPLETED ID Process Name Priority : 142 : [USER] Music : LOW [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue :1 ######## RUN : 4 ######## Job [USER] Browser generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue : 2 #### #### RUN : 5 ######## Job [OS] File Read generated JOB COMPLETED ID : 329 Process Name Priority : [OS] Display : HIGH [PROCESSOR] Busy Jobs waiting in High Priority Queue : 0 Jobs waiting in Low Priority Queue : 2 ######## RUN : 6 ######## Job [USER] Calculator generated JOB COMPLETED : 167 Process Name : [OS] File Read Priority : HIGH ID [PROCESSOR] Busy Jobs waiting in High Priority Queue : 0 Jobs waiting in Low Priority Queue :2 ## ### ### RUN : 7 ######## Job [USER] Music generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue :3 # # # # # ### RUN : 8 ## ### ### Job [OS] File Read generated JOB COMPLETED ID Process Name Priority : 486 : [USER) Browser : LOW [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue :3 ## ### ### RUN : 9 ######## Job [USER] Browser generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue : 4 ######## RUN : 10 #### ### # Job [USER] Calculator generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue : 5 Exercise 3: Using High and Low Priority Queues: Background information: Computing devices like laptops and smartphones may have multiple computing cores, which allow us to run multiple programs at once. But what happens when the number of programs that we want to run is more than the number of cores in our device? For example, what if we want to run & programs on a device with only 2 CPU cores? Job scheduling helps the device to run the most important programs first. Imagine that each program we want to run submits a job request to the operating system before it is actually run. Those jobs are stored in either a high-priority queue or a low-priority queue, depending on how important the program is. For example, processes that are fundamental to how the device operates (e.g. displaying things to the screen, dealing with system input and output) have a higher priority than user-installed applications (e.g. web browsers, music playing app, calculator app). At any given time, jobs waiting in the high-priority queue will be executed first, in the order that they were requested in. If there are no high-priority jobs waiting to be executed, then the jobs in the low-priority queue can be executed. Problem: 1. Download labb_priority.py from eClass, and save in the same folder as your other lab files. This file contains a Job class definition, as well as two functions that have already been completed for you (get_job (), and process_complete()). Read the comments for this code to understand what it does. 2. Add code to the main() function in this file so that every time a new job is created (i.e. every time get_job() is called), that job object is enqueued to the appropriate queue: high_priority_queue or low_priority_queue. Hint: use the Job's high_priority() method to check if a job is high-priority (True) or low- priority (False). Notice that get_job() may also return no job (None) which will NOT go into either queue, so that must be checked for as well. 3. Complete the main() function so that whenever a process has finished (indicated when process_complete() returns True), a new process is started by dequeuing a job from the appropriate queue. i.e. If there is at least one job in the high-priority queue, it should be dequeued and assigned to the current job variable. However, if the high-priority queue is empty and there is at least one job in the low-priority queue, then it should be dequeued and assigned to the current_job variable. If a job has been successfully dequeued from either queue, the process_running variable should be set to True. Sample Output (your output may differ since the jobs are generated randomly): ######## RUN : 1 ######## Job [USER] Music generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue :0 ######## RUN : 2 ######## Job [OS] Display generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :1 Jobs waiting in Low Priority Queue :0 #### #### RUN : 3 ######## Job [USER] Browser generated JOB COMPLETED ID Process Name Priority : 142 : [USER] Music : LOW [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue :1 ######## RUN : 4 ######## Job [USER] Browser generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue : 2 #### #### RUN : 5 ######## Job [OS] File Read generated JOB COMPLETED ID : 329 Process Name Priority : [OS] Display : HIGH [PROCESSOR] Busy Jobs waiting in High Priority Queue : 0 Jobs waiting in Low Priority Queue : 2 ######## RUN : 6 ######## Job [USER] Calculator generated JOB COMPLETED : 167 Process Name : [OS] File Read Priority : HIGH ID [PROCESSOR] Busy Jobs waiting in High Priority Queue : 0 Jobs waiting in Low Priority Queue :2 ## ### ### RUN : 7 ######## Job [USER] Music generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue :3 # # # # # ### RUN : 8 ## ### ### Job [OS] File Read generated JOB COMPLETED ID Process Name Priority : 486 : [USER) Browser : LOW [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue :3 ## ### ### RUN : 9 ######## Job [USER] Browser generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue : 4 ######## RUN : 10 #### ### # Job [USER] Calculator generated [PROCESSOR] Busy Jobs waiting in High Priority Queue :0 Jobs waiting in Low Priority Queue : 5