讲解COMP 3430编程、C++程序调试、c/c++语言编程辅导
- 首页 >> Python编程 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
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