The aim of this exercise is to have students use the knowledge they have acquired so far in the second part of the course to implement a set of scheduling algorithms.

You will be using and extending a simple discrete event simulator written in Python, creating classes that simulate the scheduling and dispatching of processes performed by four scheduling algorithms: First-Come- First-Served (FCFS), Shortest-Job- First (SJF), Round- Robin (RR), and Shortest- Remaining-Time- First (SRTF).

This  assessed  exercise  will  also  act  as  a gentle  introduction to  such  concepts  as queuing theory, discrete event simulation, and object-oriented software engineering.

Object-Oriented Software Engineering Primer

You   should   already   be   familiar   with   the   basic   concepts   of   object-oriented programming in Java from the JP2 course. Specifically, you should already know:

•   What a class is and what member variables and functions/methods are.

•   What an object (or instance of a class) is.

•   How to create (instantiate) an object of a class.

•   How  to   refer  to   member  variables/methods   using  dot   notation   (e.g., ClassX.func()).

•   What the meaning of ‘this’ is in Java.

•   What inheritance is and how you can override class methods in a subclass.

•   What  encapsulation  is – the  act  of  bundling  together  data/variables  and functions/methods that operate on said data/variables in a single unit: the object (or instance of a class) .

Python also allows object-oriented programming with classes . In Python, a class is defined using the keyword ‘class’, like so:

The equivalent of Java’s ‘this’ is Python’s ‘self’. As Python is not a pure object- oriented programming language, all class methods need to have ‘self’ as their first argument. All variables and methods defined in this class (i.e., indented one level – and indention is not optional in Python) are class variables and class methods. Also, the constructor of a class does not have the same name as the class but is rather called ‘__init__’ in Python. Furthermore, in Python, it is customary to create and initialise instance variables in a class’s __init__ method.

Subclassing,  or inheritance,   is  one  of  the   mainstays  of   many  object-oriented programming languages. Each subclass S (sometimes also referred to as a child class) of  a  Class  C  has  access  to  all  members  and  methods  of  its  parent  class  (a .k.a. superclass).

In Python, subclassing is done by including the name of the parent class in parentheses after the name of the new child class. When a subclass S has a method M with the exact same name and input parameters as those of a superclass C, we say that S’s M overrides (in essence, provides a new implementation of) C’s M. In other words, if one creates an object of S and calls M on it, it will be S’s implementation of M that will be executed,  not  C’s  M.  While  other  object-oriented  programming  languages  offer mechanisms for controlling the access to a parent class’s  members and  methods, Python doesn’t offer such a feature. However, by convention subclasses shouldn’t use

and/or access members/methods whose name starts with one or more underscores.

Putting all this together, have a look at the example code below:

If you save it in a file and execute it, the output should be:

Discrete Event Simulation Primer

A discrete event simulation (DES) simulates the operation of a system via a series of discrete events ordered in time. That is, given a set of events ordered by time of occurrence from earliest to latest, the internal clock of the simulator does not take on every  possible value but rather jumps from one event to the next. The simulated system is considered to be in a constant state in between any pair of successive events, while events trigger a possible change to the system’s state. The DES, in essence, implements the following algorithm:

where service(current_event) may end up adding new events to the queue.

Note that  it  is  not  necessary that  events that  are  removed from the  queue  and serviced lie in the future, but they can and, if they do, it moves the system time along.

In the simple discrete event simulator provided for this assessed exercise, we have three types of events:

•   PROC_ ARRIVES: A new process arrives in the system.

•   PROC_CPU_REQ: An existing process requests access to the CPU .

•   PROC_CPU_DONE: A process has run its course and, thus, terminates.

Similarly, simulated processes can be in one of the following states:

•   NEW: A new process arrives in the system at some point.

•   READY: A process is waiting for the CPU to be allocated; note that this can be a new process that just arrived, an older process that was never scheduled, or an older process that was pre-empted.

•   RUNNING: A process currently executes on the CPU.

•   TERMINATED: A process has used up its service time and, thus, terminates.

Originally the simulator creates a list of processes to be simulated . Each process has the following attributes:

•   Process ID: A number uniquely identifying the process in the system. As all processes are added to a table (aka the process table), their ID is simply the table index for the cell at which their info is stored, starting from 0.

•   Arrival time: The time of arrival of the process.

•   State: The state in which the process currently is, as discussed above.

•   Service time: The total amount of CPU time required by the process.

•   Remaining time: The remaining CPU burst time for the process

Each process keeps track of its execution time and offers a set of utility functions, comprising:

•   A function that returns its departure time, after the process has terminated.

•   A function that computes and returns its total waiting time.

•   A function that computes and returns its turnaround time.

•   A function that executes the process for up to a specified amount of time.

All processes start off in the NEW state. Along the same lines, the simulator populates the event queue with PROC_ARRIVES events for all processes to be simulated. The simulator’s service function then looks like the following (in abstract terms):

The  service  function  makes  use  of  two  more  functions,  printed  in  italics  above: scheduler_func(event) and dispatcher_func(process). The former takes the current event into consideration and selects the next process to be given access to the CPU, based on the scheduling policy/algorithm. The latter takes as an argument the process selected by the scheduler and executes it on the CPU; this translates to transitioning the process to the RUNNING state, allowing it to run for a specific amount of time (dependent on the scheduling algorithm used), then transitioning it to either the READY or the TERMINATED state (depending on whether it used up its service time), generating and returning an appropriate event (PROC_CPU_REQ in the former case, PROC_CPU_DONE in the latter case). If the event is a PROC_CPU_REQ one, it is added to the events queue, as it will require further processing in the future. Finally, the simulator’s internal (simulated) clock is updated to the time of the returned event. With  this  in  hand,  you  should  be  able  to  implement  simple  process  scheduling algorithms, as outlined below.

The design of the simple discrete event simulator provided for this assessed exercise, follows  an  object-oriented  approach.  The  information  and  methods  required  for events and processes are implemented in a set of classes (Event, EventTypes, Process, ProcessStates). The basic simulator logic is also implemented in a class of its own – namely,  SchedulerDES.  Then,  four  new  scheduler-specific  classes  are  provided; namely, FCFS, SJF, RR, and SRTF – one for each of the scheduling algorithms to be implemented. The classes are defined as subclasses of SchedulerDES.

Method overriding is used in the provided source code to allow you to implement the various scheduling algorithms without having to touch the discrete event simulator implementation. You will notice that the source code of the latter includes skeleton definitions for the scheduler and dispatcher functions discussed above, and that these same functions are defined in the subclasses as well. You only need to edit the latter, as it is these implementations that will be used by the main function of the simulator. Remember that you still have full access to all methods/members of SchedulerDES, yet you should only really use those without one or more leading underscores.

Scheduling Algorithms

As part of this assessed exercise, you are asked to implement the following scheduling algorithms:

•   FCFS/FIFO (non-pre-emptive): Processes should be executed in the order in which they arrive at the system. Conceptually, when a process arrives, it is added to a queue. The scheduling algorithm will always pick the first process in the queue and will execute it to completion. It will then proceed with the next process in the queue, and so on.

•   SJF (non-pre-emptive): Processes are prioritised based on their service time. Conceptually, on arrival, processes are added to a  priority queue, which  is sorted in ascending order of service time. The scheduling algorithm will then always remove the first process in the queue and will execute it to completion. It will then proceed with the next process in the queue, and so on.

•   RR (pre-emptive): On arrival, processes are added to a queue. Conceptually, the algorithm will pick the first process in the queue, execute it for a specified amount of time (also known as a time slice or quantum), and, if the process needs more time, it will be added to the end of the queue again.

•   SRTF (pre-emptive): This is a pre-emptive version of the SJF algorithm above. Conceptually, whenever a change occurs in the system (i.e., a new process arrives, a running process terminates, etc.), the scheduler is called to select the process  among  those  in  the  READY  state  with  the  minimum  remaining execution time. This process might then be pre-empted when a new change occurs that results in another process a.) being ready and b.) having a lower remaining execution time than the one currently executing.

Pseudo- Random Number Generation

The main simulator code makes use of a pseudo-random number generator (PRNG) to  generate  the  process  arrival  and  service  times,  following  the  M/M/1  queue equations  (as  briefly  discussed  on  last  week’s  lab sheet). The “pseudo“  in  PRNG denotes that these generators do not really produce completely random numbers.

Instead, they compute a new “random” output based on a deterministic computation on state  kept  internally  by the  PRNG  implementation. Consequently,  if one could control the original internal state, they would be able to force the PRNG into producing repeatable sequences of “random” outputs. Most implementations of PRNGs support this functionality through seeding; in other words, they provide a method that allows the user to define an initial seed (usually taking the form of an integer), based on which the PRNG initialises its internal state in a deterministic manner. For example, execute the following code in your favourite Python environment:

You should get three sequences of ten random floats, each different to the next. Then, execute the following code:

You should now get three sequences of ten random floats, but all three sequences are identical to each other. This is because we have reset the seed to the same value (1) before the generation of each of these sequences.

This is used in the provided implementation to allow for repeatable experiments . The PRNG defaults to a random initial seed. This seed is printed on the screen when the simulator starts. The program also features a command-line argument that allows you to set the seed to a user-defined value, as well as arguments to enable verbose logging of the internal state of the simulator. You can use this whenever a run of the simulator produces counter-intuitive results, to allow you to dig into the problem and identify the cause of the discrepancy between actual and expected results.

For your consideration, here is a set of “interesting” seeds: 1797410758, 2688744162, 3399474557. These are interesting in the sense that the respective workloads make some algorithms win over others. What you should do in these cases, is execute the program with debug logging on, examine the sequence of events/scheduling decisions and address the points laid out in the spec below.

Miscellanea

Start by reading and trying to understand the provided code. Please feel free to ask us if you have any questions that cannot be answered by a simple online search. You should not need to read up on the concepts outlined earlier (queuing theory, discrete event simulation, object-oriented programming) much, but feel free to do so if you deem it necessary to understand the provided code (or if you are interested).

You should only need to change the code in schedulers.py. The list of imports in said file includes all imports that you should need for the assessed exercise. Please ask us if you think more imports are necessary, as this might indicate a misunderstanding.

Please make sure that your code is well formatted and documented, and that an appropriate function/variable naming scheme has been used.

The main function (main.py) provides several command-line options that allow you to change various  parameters of the system.  Executing the  program with ‘ -h’ or ‘ --help’ will print a help message that explains the supported options.

A set of sane defaults is provided in the source code, but feel free to play around with other values. You can do so by either executing the simulator on the command line and  providing  different  arguments,  by  changing  the  defaults  in  the  source  code (main.py),     or     by     providing     your     own     parameters     as     input     to    the parser.parse_args(…) function;  as  an  example  of  the  latter,  to  execute  the program with the command-line arguments -S 851898649, do the following:

To print the help message, do the following: