program代写、代做Python程序设计

日期：2023-11-20 08:46

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