COMPSCI2024 Networks & Operating Systems Essentials 2 (NOSE 2) Assessed Exercise 2: Scheduling
Networks & Operating Systems Essentials 2 (NOSE 2) – Assessed Exercise 2: Scheduling
Objective: The aim of this exercise is for you to apply the knowledge you have acquired on events, waiting queues, processes, and process scheduling and dispatching to implement and discuss scheduling algorithms (NOSE2 ILOs 10 and 9).
Context: The exercise builds on the lectures on processes and process scheduling (Lecture topics 10 and 11) as well as the first two OS labs (Labs 4 and 5). Since the exercise requires you to implement scheduling algorithms in Python, you might want to refresh your knowledge using the short Python refresher provided.
Tasks
There are two tasks for you to complete in the context of the discrete event simulator (DES) code that we provide (“Assessed Exercise 2 – Code” on Moodle; further explanations are provided in Appendix A). These two tasks are:
-
Task 1 – Implementation of scheduling algorithms: Use the provided discrete event simulation (DES) code and implement the four classes in schedulers.py so they simulate the scheduling and dispatching of processes following four scheduling algorithms:
-
First-Come-First-Served (FCFS), Shortest-Job-First (SJF), Round-Robin (RR), and Shortest-Remaining-Time-First (SRTF).
-
See Appendix B for short descriptions of the four algorithms.
-
-
Task 2 – Discussion of resulting schedules: Once the scheduling algorithms are implemented, run the simulator with the random seeds 1797410758, 2688744162, and 3399474557 and discuss the schedules produced by the four
scheduling algorithms for each seed.
-
Discuss: e.g. What was the relative performance of the four schedules?
Does this deviate from your expectations? What do you think is the
cause of any deviation based on the internal state of the simulation?
-
See Lab 4 for a short explanation of seeding.
How and What to Submit
For this assessed exercise, you are encouraged to work in teams of two students (but you can also work and submit on your own).
Submit your amended schedulers.py file (Task 1) and short report in pdf format (Task 2) on Moodle (look for the “Assessed Exercise 2 - Submission” link).
You should only change the code in schedulers.py. Moreover, the list of imports in said file already includes all imports that you can use for the assessed exercise.
Your report must include a heading stating your full name(s), matriculation number(s), and lab group(s). Only one submission should be done per team.
-
1
How Exercise 2 Will be Marked
Following a timely submission on Moodle, the exercise will be given a numerical mark, between 0 (no submission) and 100 (outstanding in every way). These numerical marks will then be converted to a band (C2 etc.).
The marking scheme is given below:
• 15 marks for each of FCFS and SJF (Task 1; 30 marks in total):
o 7 marks for correct selection of the next process to execute (scheduler
function)
o 8 marks for correct state keeping and process execution (dispatcher
function)
• 20 marks for each of RR and SRTF (Task 1; 40 marks in total):
o 7 marks for correct selection of the next process to execute (scheduler
function)
o 13 marks for correct state keeping and process execution (dispatcher
function)
• 30 marks for the discussion of schedules in your report (Task 2): 10 marks for
each of the discussions of the schedules of each of the three specified seeds
Please also ensure that your code is well formatted and documented and that an appropriate function/variable naming scheme has been used.
Working With the Provided Simulation Framework
We suggest you start by reading and trying to understand the provided code. Running the code in a debugger – to set a breakpoint and inspect the values of the various variables used – might also be helpful.
The main function (main.py) provides several command-line options that allow you to change various system parameters. Executing the program with ‘-h’ or ‘--help’ will print a help message that explains the supported options.
A set of defaults is provided in the source code, but feel free to play around with other values or by providing your 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 and, thereby, specify the seed value, do the following:
args = parser.parse_args(['-S', '851898649'])
To print the help message, do the following:
args = parser.parse_args(['-h'])
To increase the verbosity level to full debug output, do the following:
2
args = parser.parse_args(['-v', ‘-v’])
And for combinations of the above, simply add more arguments to the list, like so:
args = parser.parse_args(['-S', '851898649', '-v', ‘-v’])
However, executing your code from the command line is probably faster and easier.
Please also note that:
-
You should not need to add any new queues or other variables to the
simulator. All the state required by the simulator is already there in
SchedulerDES.
-
If you need to walk through the list of processes, use self.processes. Given
a process ID (say, id), you can access its state via self.processes[id].X,
where X is either an attribute of the process or one of its methods.
-
To peek ahead to the time of the next event at the current point in time, use
self.next_event_time().
-
If you want direct access to the queue of events (which you, however, should
not need to), use self.events_queue.
-
You can also get the currently executing process (self.process_on_cpu)
and the current simulator time (self.time).
-
The scheduler function is called with a single event as an argument, but it also
has full access to the process table and other internal data structures of the simulator (e.g., events queue, etc.). In other words, the scheduler does not need to decide based solely on the process that created the current event.
The simulator is written in a way that facilitates abstracting out the functions for scheduling and dispatching. As such, the code you need to write is minimal. As a yardstick, the model solution adds around two dozen lines of code to schedulers.py. Your mileage may vary, of course, but this should give you an idea of how much code might be needed for this assessed exercise.
Sample results (random seed, processes, timings, etc.) to compare your implementation’s output to are provided in Appendix C. The framework gives the option of seeding for repeatable experiments as explained in Lab 4. (i.e., process A runs first for X time units, then process B for Y time units, etc.) does not match the simulator's output, then there is something wrong. In that case, revisit your hand trace and code, rerun with the same seed, and see if the two agree; rinse and repeat as needed.
The debug logging should also help examine the sequence of events/scheduling decisions for the random seeds you will discuss as part of this exercise.
We suggest you run the simulator with different context switch times as well, as the default value in the simulator is set to 0.0.
