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.
2
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. 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 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:
To print the help message, do the following:
To increase the verbosity level to full debug output, do the following:
args = parser.parse_args(['-S', '851898649'])
args = parser.parse_args(['-h'])
3
And for combinations of the above, simply add more arguments to the list, like so:
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. The seed used is
printed on the screen when the simulator starts. If you want to ensure that your code
works correctly, we suggest you turn on debug logging (-vv), fix the random seed to a
value (e.g., -S 0), and walk your way through the trace step-by-step. If the execution
trace you get by hand (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.
args = parser.parse_args(['-v', ‘-v’])
args = parser.parse_args(['-S', '851898649', '-v', ‘-v’])
4
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.
Appendix A – The Discrete Event Simulator
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 preempted.
• RUNNING: A process currently executes on the CPU.
• TERMINATED: A process has run its service time and, thus, terminates.
Initially, 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 burst 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:
• 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 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 ScheduerDES’s run() function makes use of two more functions:
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 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), and then transitioning it to either the READY or the TERMINATED
5
state (depending on whether it ran its service time). Finally, the function generates
and returns an appropriate event (PROC_CPU_REQ if the process requires more time
or, else, PROC_CPU_DONE if the process is completed). If the event is a
PROC_CPU_REQ one, it is added to the events queue again, as it will require further
processing in the future. Finally, the simulator’s internal clock is updated to the time
of the returned event.
The basic simulator logic is implemented in a class – namely, SchedulerDES. Then, four
new scheduler-specific subclasses of it are provided; namely, FCFS, SJF, RR, and SRTF
– one for each of the scheduling algorithms to be implemented. 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
itself. You will notice that the source code of the simulator 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 two
functions in each subclass, as these will be used by the main() function of the
simulator. Remember that you have access to all methods/members of SchedulerDES,
although by convention you should not use those with leading underscores.
Appendix B – The Four Classic Scheduling Algorithms
As part of this assessed exercise, you are asked to implement the following four
textbook scheduling algorithms:
• FCFS/FIFO (non-preemptive): Processes should be executed in the order in
which they arrive. Conceptually, when a process arrives, it is added to a queue.
The scheduling algorithm always picks the first process in the queue and
executes it to completion. It will then proceed with the next process in the
queue, and so on.
• SJF (non-preemptive): Processes are prioritized 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 always
picks the first process in the queue and executes it to completion. It will then
proceed with the next process in the queue, and so on.
• RR (preemptive): On arrival, processes are added to the end of a queue.
Conceptually, the algorithm always picks the first process in the queue,
executes 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 (preemptive): This is a preemptive 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 preempted again when a new
change occurs that results in another process being ready and switching to that
new process will see it finish before the currently running process would finish.
6
Appendix C – Two Sample Outputs
Using seed: 1523376833
Processes to be executed:
[#0]: State: ProcessStates.NEW, Arrival: 0.8965518035211827,
Service: 0.4772854990859405, Remaining: 0.4772854990859405
[#1]: State: ProcessStates.NEW, Arrival: 1.0476559314160219,
Service: 3.177651950380589, Remaining: 3.177651950380589
[#2]: State: ProcessStates.NEW, Arrival: 1.0699502089969615,
Service: 0.6431423507594756, Remaining: 0.6431423507594756
[#3]: State: ProcessStates.NEW, Arrival: 1.133575330296856,
Service: 0.21095976155023272, Remaining: 0.21095976155023272
[#4]: State: ProcessStates.NEW, Arrival: 1.5419034712499409,
Service: 3.519113233731405, Remaining: 3.519113233731405
[#5]: State: ProcessStates.NEW, Arrival: 2.268572897370114,
Service: 6.1209365033748995, Remaining: 6.1209365033748995
[#6]: State: ProcessStates.NEW, Arrival: 2.622213160578937,
Service: 0.6057431641679517, Remaining: 0.6057431641679517
[#7]: State: ProcessStates.NEW, Arrival: 2.8181529993918173,
Service: 0.603425465615895, Remaining: 0.603425465615895
[#8]: State: ProcessStates.NEW, Arrival: 3.0484632504147853,
Service: 1.2052874280418702, Remaining: 1.2052874280418702
[#9]: State: ProcessStates.NEW, Arrival: 3.213418227642897,
Service: 2.892823843272308, Remaining: 2.892823843272308
-----
FCFS [#Processes: 10, Avg arrivals per time unit: 3.0, Avg CPU burst
time: 2, Context switch time: 0.0]:
Avg. turnaround time: 9.055465010768293
Avg. waiting time: 7.109828090770234
-----
SJF [#Processes: 10, Avg arrivals per time unit: 3.0, Avg CPU burst
time: 2, Context switch time: 0.0]:
Avg. turnaround time: 5.667330888524098
Avg. waiting time: 3.721693968526041
-----
RR [#Processes: 10, Avg arrivals per time unit: 3.0, Avg CPU burst
time: 2, Context switch time: 0.0, Quantum: 0.5]:
Avg. turnaround time: 8.6057126790477
Avg. waiting time: 6.660075759049643
-----
SRTF [#Processes: 10, Avg arrivals per time unit: 3.0, Avg CPU burst
time: 2, Context switch time: 0.0]:
Avg. turnaround time: 5.071064581670328
Avg. waiting time: 3.1254276616722705
7
Using seed: 3672961927
Processes to be executed:
[#0]: State: ProcessStates.NEW, Arrival: 0.9967930942538261,
Service: 1.7805632589480833, Remaining: 1.7805632589480833
[#1]: State: ProcessStates.NEW, Arrival: 1.026222231111286,
Service: 1.7022393172998072, Remaining: 1.7022393172998072
[#2]: State: ProcessStates.NEW, Arrival: 1.8916853352121672,
Service: 2.3302464408938315, Remaining: 2.3302464408938315
[#3]: State: ProcessStates.NEW, Arrival: 2.0051880828926594,
Service: 5.220529617260626, Remaining: 5.220529617260626
[#4]: State: ProcessStates.NEW, Arrival: 3.0218802368513096,
Service: 2.226205967193615, Remaining: 2.226205967193615
[#5]: State: ProcessStates.NEW, Arrival: 3.255766032372033,
Service: 4.047087113201036, Remaining: 4.047087113201036
[#6]: State: ProcessStates.NEW, Arrival: 3.3862860082130255,
Service: 3.0229686771601187, Remaining: 3.0229686771601187
[#7]: State: ProcessStates.NEW, Arrival: 3.723246678844583,
Service: 0.3318700244392102, Remaining: 0.3318700244392102
[#8]: State: ProcessStates.NEW, Arrival: 3.8174183504968853,
Service: 3.021590099896377, Remaining: 3.021590099896377
[#9]: State: ProcessStates.NEW, Arrival: 4.056820014748351,
Service: 2.448209295878759, Remaining: 2.448209295878759
-----
FCFS [#Processes: 10, Avg arrivals per time unit: 3.0, Avg CPU burst
time: 2, Context switch time: 0.0]:
Avg. turnaround time: 12.626963581749276
Avg. waiting time: 10.01381260053213
-----
SJF [#Processes: 10, Avg arrivals per time unit: 3.0, Avg CPU burst
time: 2, Context switch time: 0.0]:
Avg. turnaround time: 9.484330868807557
Avg. waiting time: 6.871179887590411
-----
RR [#Processes: 10, Avg arrivals per time unit: 3.0, Avg CPU burst
time: 2, Context switch time: 0.0, Quantum: 0.5]:
Avg. turnaround time: 16.262966521167005
Avg. waiting time: 13.649815539949861
-----
SRTF [#Processes: 10, Avg arrivals per time unit: 3.0, Avg CPU burst
time: 2, Context switch time: 0.0]:
Avg. turnaround time: 9.436993491606682
Avg. waiting time: 6.823842510389535