代做COMP 3430代写编程、C++程序调试、c/c++语言编程代写

日期：2021-03-22 10:56

COMP 3430 - Operating Systems Winter 2021

Contents

Description 1

General submission requirements 2

Question 1 - Simulating Scheduling 3

Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

CPUs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Overall structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Loading tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Running . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Tracking time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Sample output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Submitting your assignment 10

Description

For assignment 3, we’re looking for you to be able to implement scheduling policies, and to write

programs that use threads and locks.

You’re going to do this by implementing scheduling policies, and simulating a multi-CPU system with

threads as a producer-consumer-like problem.

Assignment 3 is due Sunday, March 28th, 2021 at 11:59pm CDT (Winnipeg time).

Franklin Bristow, Rasit Eskicioglu 1

COMP 3430 - Operating Systems Winter 2021

General submission requirements

Submissions that violate any of the following will not be evaluated, under any circumstances:

• All solutions must be written in C. No other languages are accepted.

• All solutions must include a working Makefile.

– Forget how to make a Makefile? Never knew how to make a Makefile? Thankfully,

you can go to https://makefiletutorial.com and find some very easy to use basic examples.

– Your Makefile should contain a clean rule. When

make clean

is run from your directory, all the temporary files, including the executable should be removed

(e.g., rm -f my_prog).

• All solutions must be compiled by issuing the command make in the directory containing the

Makefile. No other build commands are acceptable, even if documented in the README.

• All solutions must include a Markdown-formatted README file that minimally describes how to

run your submission.

• All solutions must run to successful completion. Premature termination for any reason (no obvious

output, Segmentation Fault, Bus Error, etc.) is considered to be a solution implementation

that does not run. Code that does not compile is also considered to be a solution

implementation that does not run.

• Programs must produce no errors when compiled with the flags

-Wall -Wpedantic -Wextra -Werror

Note that -Werror prevents your code from being compiled when warnings are present.

If these flags are not in your Makefile, your submission will be treated as though it does not

compile.

If your code does not compile, it will not be graded (you will receive a score of 0).

• Your code must compile and run on a machine on aviary.cs.umanitoba.ca.

• No late submissions will be accepted. The assignment deadline is enforced electronically. Submissions

will not be accepted by e-mail.

Reminder: All submitted code will be evaluated using an automated similarity testing tool, alongside

commonly available online solutions for problems.

Franklin Bristow, Rasit Eskicioglu 2

COMP 3430 - Operating Systems Winter 2021

Question 1 - Simulating Scheduling

In this question, you’ll be writing a simulator that implements different process scheduling policies,

and simulates the behaviour of those scheduling policies on a multi CPU system using threads, where

each “CPU” is one thread.

Policies

Your simulator will implement 3 different scheduling policies:

1. Pure round-robin. A first-come-first-serve queue. This scheduler does not use priority.

2. Shortest time to completion first. This scheduler does not use priority.

3. A multi-level queue, where priority 1 tasks run first, in a round-robin fashion. Then, priority 2

tasks run round-robin, etc. This is similar to the most basic implementation of MLFQ described

in our text.

Tasks

The tasks that will be loaded into your simulation have multiple attributes:

• A name

• A type (which is used for classification for our statistics)

• Priority

• Amount of time to completion

• The odds of this task yielding the CPU due to going to an I/O operation, as a percentage out of

100. When a task starts a timeslice, you should generate a random number to decide if there

will be I/O in the timeslice. If the task will do I/O (the random number is > than the specified

odds), it generates another random number between 0 and the full timeslice time, and run for

that amount of time.

CPUs

Your scheduling policy implementations will be used to evaluate how the different scheduling policies

behave when different numbers of CPUs are running processes.

When running the simulation with 𝑛 “CPUs”, your program should have at least 𝑛+1 threads running:

1 for each “CPU”, plus 1 for the scheduler itself.

Franklin Bristow, Rasit Eskicioglu 3

COMP 3430 - Operating Systems Winter 2021

Implementation

Overall structure

Figure 1: Assignment 3 architecture

1. Scheduling policy determines which task is the next task in the queue of running tasks.

2. The dispatcher notifies all waiting CPUs that a task is available.

3. CPUs get tasks to run from the dispatcher when a task is available and start running (note: “running”

here means that the CPU reduces the remaining time to completion to the task by the

length of the timeslice, or to 0, whichever is larger).

4. CPUs return tasks to the scheduler queue on one of:

• Timeslice elapses, or

• Task does I/O (the amount is calculated by the odds_of_IO attribute of the task. See

below).

CPUs update accounting information on task, e.g., time left for the task.

5. CPUs place tasks in the “done” area along with their stats, when the tasks are complete.

6. When there are no tasks left, the program produces a report and terminates.

Franklin Bristow, Rasit Eskicioglu 4

COMP 3430 - Operating Systems Winter 2021

Your implementation will require several locks, minimally where the CPUs get a task from the dispatcher,

and where the CPUs return the task to the running queue. The level of granularity that you

choose to implement in terms of locking the queue here is your decision.

You’re also going to need to use condition variables to tell CPUs that are not currently working on a

task that a new task is available.

Loading tasks

Tasks are loaded from a file, and are put in the scheduler’s ready queue before the start of the simulation

(in other words, all tasks start at the same time, and all tasks start at time 0).

The configuration file has a space-delimited format:

task_name task_type priority task_length odds_of_IO

There are 4 types of tasks to run, which are indicated by an id:

• id 0 - Short tasks

• id 1 - Medium tasks

• id 2 - Long tasks

• id 3 - I/O tasks

Note that I/O tasks are effectively the same as “Long tasks”, where the only difference is that I/O tasks

have a higher chance of doing an I/O operation (see taskmaker.py) to get an idea of how the tasks

are created).

Here’s an example of a single line that’s generated by taskmaker.py, which represents the properties

for one task:

io_task_1 3 1 10 50

This line can be decoded into a task in your system as:

• task_name: “io_task_1”

• task_type: 3, io task

• priority: 1 (medium)

• task_length: 10

• odds_of_IO: 50%

You can find a file of tasks here. You can (and should!) make your own tasks.txt file with

taskmaker.py.

Franklin Bristow, Rasit Eskicioglu 5

COMP 3430 - Operating Systems Winter 2021

Running

Your program should take two command-line arguments:

1. The number of CPUs in the system you’re simulating, and

2. The scheduling policy that should be used to order tasks.

Some examples:

./a3q1 8 rr # 8 "CPUs" with round-robin scheduling policy

./a3q1 4 stcf # 4 "CPUs" with shortest time to completion first policy

./a3q1 2 mlfq # 2 "CPUs" with the multi-level feedback queue policy

Tracking time

How you choose to track time for tasks is up to you, but One strategy that you can use for tracking

time to completion is to use a global variable tracking how much time has “elapsed”. Basically: as

each processor thread uses up a timeslice for a task, the processor thread should update the global

variable with how much time it “spent running” that task.

So, if a task uses 5 units of time (a complete timeslice, see Notes below), then that processor thread

should update the global time variable by 5. If a task uses only some of its timeslice (it yields because

of an I/O), then the processor thread should update the global time variable by however much time

the task used before it yielded.

When a task finishes (the time remaining for the current task is 0), the processor thread should copy

the “current time” into that task and put it into the done area.

Output

Print the following statistics at the end of the simulation:

• average time from start to completion for each priority

• average time from start to completion for each type

Sample output

Using pure round-robin with 4 CPUs.

Average run time per priority:

Priority 0 average run time: 9999

Franklin Bristow, Rasit Eskicioglu 6

COMP 3430 - Operating Systems Winter 2021

Priority 1 average run time: 8040

Priority 2 average run time: 11187

Average run time per type:

Type 0 average run time: 861

Type 1 average run time: 2476

Type 2 average run time: 16384

Type 3 average run time: 18239

Franklin Bristow, Rasit Eskicioglu 7

COMP 3430 - Operating Systems Winter 2021

Notes

• Time can be integers, you don’t have to use floating point numbers for times.

• Use a constant for the length of the timeslice. Set it to 5.

• This is a very open-ended assignment in terms of implementation. You are permitted to implement

your simulation as you see fit, provided it meets the expectations that are outlined above.

Analysis

Run the scheduling algorithms that you wrote 5 times each with at least two different numbers for

CPUs (e.g., 2 and 8), generating an average and standard deviation all of your collected statistics. You

can make your own set of tasks to do your analysis with.

The statistics should be presented in your README.md as a table, present your results and provide a

written discussion comparing the algorithms. In your response, include answers the following questions:

• Are the distributions generated significantly different?

• How did the algorithms treat the queue differently, and how is that reflected in the data?

• How does the number of “CPU”s affect each scheduling policy?

Franklin Bristow, Rasit Eskicioglu 8

COMP 3430 - Operating Systems Winter 2021

Evaluation

Implementation

5 points are awarded for code quality and design:

Level Description

0 The code is very poor quality (e.g., no comments at all, no functions, poor naming

conventions for variables, etc).

1–3 The code is low quality, while some coding standards are applied, their uses is

inconsistent (e.g., inconsistent use of comments, some functions but functions

might do too much, code is repeated that should be in a function, etc).

4–5 The code is high quality, coding standards are applied consistently throughout the

code base.

10 points are awarded for implementation (5 × 2):

Level Description

0 No attempt is made to answer this question or code does not run or compile.

1–2 The submitted code is substantially incomplete. Many of the requirements for the

assignment are not implemented.

3–4 The submitted code is substantially complete, but some major parts are still missing

(e.g., not all scheduling policies implemented).

5 The submitted code is complete, all major functionality works as expected.

Franklin Bristow, Rasit Eskicioglu 9

COMP 3430 - Operating Systems Winter 2021

Report

Note: If you earn 0 on the implementation for any reason, you will also earn 0 on the report.

Level Criteria

0 No attempt is made to answer this question

1–2 A report is submitted, but is missing substantial parts and provides no meaningful

conclusion about the differences between scheduling policies.

3 – 4 A report is submitted and coherent, but is missing some parts, or does not include

enough data points in the experiment to reasonably draw conclusions about

scheduling policy behaviour.

5 The report is submitted, coherent, and complete. The conclusions about scheduling

policies are consistent with reported statistics.

Submitting your assignment

Submissions will be made using the handin command available on all CS UNIX systems.

If your files are in a folder named my_a3, you would run the command:

handin 3430 a3 my_a3

If you need more information, you can see man handin.

Franklin Bristow, Rasit Eskicioglu 10