辅导案例-COSC 1285-Assignment 1

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
Algorithms and Analysis COSC 1285
Assignment 1: Process Scheduler
Assessment Type Group assignment. Submit online via Canvas→ Assignments
→ Assignment Task 3: Assignment 1 → Assignment 1:
Process Scheduler. Marks awarded for meeting require-
ments as closely as possible. Clarifications/updates may be
made via announcements/relevant discussion forums.
Due Date Week 6, Wednesday 8th April 2020, 11:59pm
Marks 15
1 Objectives
There are three key objectives for this assignment:
• Understand how a real problem can be mapped to various representations and their
operations.
• Use a number of fundamental data structures to implement the runqueue abstract
data type.
• Evaluate and contrast the performance of the data structures with respect to dif-
ferent usage scenarios and input data.
2 Learning Outcomes
This assignment assesses learning outcomes CLO 2, 4 and 5 of the course. Please refer
to the course guide for the relevant learning outcomes: http://www1.rmit.edu.au/
courses/004302
3 Overview
Scheduling is the process of arranging, controlling and optimizing tasks and workloads. In
computing, scheduling concerns about which task is assigned to resources that complete
the task. The task may be virtual computation elements such as threads, processes
or data flows, which are in turn scheduled onto hardware resources such as processors,
network links or expansion cards [2]. Scheduling is an intrinsic part of the execution
model of a computer system. It makes it possible to have computer multitasking with
a single central processing unit (CPU). For more detailed information about scheduling,
please refer to [2].
A process scheduler carries out the scheduling activity in an operating system. It
arranges active processes in a runqueue. The runqueue represents a timeline for the
scheduled processes. For example, the Completely Fair Scheduler (CFS) is a process
scheduler for the 2.6.23 (October 2007) release of the Linux kernel. Schedulers like the
CFS keep track of time (in nanoseconds) a process has executed on processor, called
vruntime. In this assignment, we will implement and analysis CFS types of schedulers
that keep track of vruntime of a process. Processes that has got a small amount of
time are boosted to the front of the runqueue to get the processor, those who got bigger
amount of time are thwarted [1]. When the scheduler is invoked to run a new process: the
process with the lowest vruntime from the runqueue is chosen, and sent for execution,
then
1. If the process simply completes execution, it is removed from the runqueue
2. Otherwise, if it is interrupted for a reason, it is reinserted into the runqueue based
on its new vruntime. If there are multiple processes has the same vruntime, they
follow a First-In-First-Out (FIFO) ordered.
This type of schedulers commonly require efficient data structure implementation of
the runqueue to schedule new process, delete process, track process information and high-
performance code to generate the schedules. Despite the name, the runqueue need not be
implemented in the traditional way, e.g., as an array. In this assignment, we defines the
runqueue as an abstract data type similar to a PriorityQueue and consider the following
two representations:
• The Sequential Representation
• The Tree Representation
We will implement both representations for the runqueue and evaluate how well they
perform when representing some given runqueues and compute the average speed of
various operations.
4 Tasks
The assignment is broken up into a number of tasks, to help you progressively complete
the project.
4.1 Task A: Implement the runqueue representations and its op-
erations (8 marks)
In this task, you will implement the runqueue using linear and tree representations,
respectively. Each representation will be implemented by various data structures. Each
element of the runqueue represents a process to be scheduled, containing a process label,
and its vruntime.
4.1.1 Data Structure Details
In this assignment, each element of the runqueue (i.e., process) will be represented with
an abstract data type Proc that consists of the following information:
• procLabel - a string label of the process, i.e., the unique identifier of a process.
The format of the process label starts with letter P followed by digits, e.g., P1,
P240, P1000, etc.
• vt - vruntime of the process. For the sake of simplicity, we use time units (positive
integers) to represent vruntime in this assignment.
The priority of each element/process is assessed by its vruntime. Process that has a
shorter vruntime should be of higher priority, i.e., should be dequeue/removed before
other processes that have a longer vruntime.
The runqueue can be implemented using a number of data structures. In this assign-
ment, you are to implement the runqueue using the following representations and data
structures:
• Sequential Representation
– using an 1D Ordered Array
– using an Ordered Linked-list
• Tree Representation
– using a Binary Search Tree (BST)
Note that you must program your own implementation, and not use existing libraries
in any kind, e.g. the PriorityQueue, the LinkedList, Set, MultiSet, Tree type of data
structures in java.utils or any other libraries. You must implement your own nodes and
methods to handle the operations. If you use java.utils or other implementation from
libraries, this will be considered as an invalid implementation and attract 0 marks for
that data structure.
4.1.2 Operations Details
Operations to perform on the implemented runqueue abstract data type are specified on
the command line. They are in the following format:
[arguments]
where operation is one of {EN, DE, FP, RP, PT, ST, PA, Q} and arguments is for optional
arguments of some of the operations. The operations take the following form:
• EN – Enqueue: create and add a process (with lable procLabel
and vruntime vt) into the runqueue. There is no output for this operation.
• DE – Dequeue: delete the process with the highest priority (i.e., shortest vruntime)
from the runqueue. Processes that have the same vruntime follow the FIFO order.
If the runqueue is not empty, the output should be the label of the deleted process.
Otherwise, it outputs an empty string.
• FP – Find the process with the given label procLabel in the runqueue.
The output should be true if the search is successful, otherwise false (i.e., the
process does not exist).
3
• RP – Remove the process with the given label procLabel in the run-
queue. The output should be true if successfully deleted, otherwise false (i.e., the
process does not exist).
• PT – Calculate the total vruntime of the preceding processes of the
process labelled as procLabel. Preceding processes are the processes that will be
executed before the given process. If the process with procLabel does not exist in
the runqueue, return -1; otherwise, the output is the calculated total vruntime.
• ST – Calculate the total vruntime of the succeeding processes of the
process labelled as procLabel. Succeeding processes are the processes that will be
executed after the given process. If the process with procLabel does not exist in
the runqueue, return -1; otherwise, the output is the calculated total vruntime.
• PA – Print the labels of all the processes in the runqueue in ascending order of their
vruntime, i.e., the time line. Please refer to the following example for the exact
format of the output. If the runqueue is empty, this operation prints out an empty
string.
• Q – quits the program.
As an example of the operations, consider an initial empty runqueue and the following
list of operations (inputs) and their associated outputs:
[ Int : ]EN P2 2
[ Out : ]
[ Int : ]EN P1 1
[ Out : ]
[ Int : ]EN P3 2
[ Out : ]
[ Int : ]DE
[Out : ] P1
[ Int : ]DE
[Out : ] P2
[ Int : ] FP P2
[ Out : ] f a l s e
[ Int : ]RP P2
[ Out : ] f a l s e
[ Int : ]EN P1 1
[ Out : ]
[ Int : ]EN P2 4
[ Out : ]
[ Int : ]EN P4 4
[ Out : ]
[ Int : ]EN P5 5
[ Out : ]
[ Int : ]PA
[Out : ] P1 P3 P2 P4 P5
[ Int : ]PT P2
4
[ Out : ] 3
[ Int : ] ST P2
[ Out : ] 9
[ Int : ] FP P2
[ Out : ] t rue
[ Int : ]RP P2
[ Out : ] t rue
[ Int : ]PT P2
[ Out:]−1
[ Int : ] ST P2
[ Out:]−1
[ Int : ]PA
[Out : ] P1 P3 P4 P5
4.1.3 Testing Framework
We provide Java skeleton code (see Table 1) to help you get started and test the correct-
ness of your code. You may add your own Java files to your final submission, but please
ensure that they work with the supplied framework (see below).
file description
RunqueueTester.java Code for testing (details see below). No need to
modify this file.
Runqueue.java Interface for Runqueue. All implementations
should implement the Runqueue class defined in
this file. Read the javaDoc of each method care-
fully and do not modify this file.
OrderedArrayRQ.java Code that implements the sequential represen-
tation of runqueue using an 1D ordered array.
Complete the implementation (implement parts la-
belled “Implement me!”).
OrderedLinkedListRQ.java Code that implements the sequential represen-
tation of runqueue using an ordered linked list.
Complete the implementation (implement parts la-
belled “Implement me!”).
BinarySearchTreeRQ.java Code that implements the tree representation of
runqueue using an binary search tree. Complete
the implementation (implement parts labelled “Im-
plement me!”).
Table 1: Table of Java files.
We provide the Java file RunqueueTester.java that helps with automating testing.
Once completed the implementations of the runqueues and compiled the necessary files,
you can test your implementation using the RunqueueTester in either interactive or
non-interactive mode:
5
Interactive mode reads in operation commands from stdin then executes those on the
selected runqueue implementation.
java RunqueueTester
where is one of the implementation, = [array | linkedlist |
tree]
For example:
java RunqueueTester array
The above command executes the RunququeTester with the 1D ordered array im-
plementation of the runqueue in the interactive mode. Please refer to the input
output example in Section 4.1.2
Non-interactive mode reads input files of operations (such as example above). These
are fed into the Java framework which calls your implementations. The outputs
resulting from any print operations are stored. The format of the command call
upon the non-interactive mode is as follows:
java RunqueueTester inputfile_name outputfile_name
For example:
Java RunqueueTester array input.in output.out
The above command executes the RunqueueTester with the 1D ordered array im-
plementation of the runqueue . It reads the commands from input.in and stores
all the output to output.out We provide two pairs of input and expected output
files for your testing and examination.
For our evaluation on the correctness of your implementation, we will use the same
Java file RunqueueTester.java for auto testing, as well as input/expected output files of
the same format as the provided examples. To avoid unexpected failures, please do not
change the RunqueueTester.java file. If you wish to use the java file for your timing
evaluation, make a copy and use the unaltered script to test the correctness of your
implementations, and modify the copy for your timing evaluation.
Notes
• We will run the supplied test file on your implementation on the university’s core
teaching servers. If you develop on your own machines, please ensure your code
compiles and runs on these machines. You don’t want to find out last minute that
your code doesn’t compile on these machines. If your code doesn’t run on these
machines, we unfortunately do not have the resources to debug each one and cannot
award marks for testing.
• All submissions should compile with no warnings on OpenJDK 1.8 - this is the
default javac/java version on the Core teaching servers.
6
4.2 Task B: Evaluate your Data Structures (7 marks)
In this second task, you will evaluate your three implemented structures both theoret-
ically and empirically in terms of their time complexities for the different operations
and different use case scenarios. Scenarios arise from the possible use cases of a process
scheduler.
Write a report on your analysis and evaluation of the different implementations. Con-
sider and recommend in which scenarios each type of implementation would be most
appropriate. The report should be 6 pages or less, in font size 12. See the assessment
rubric (Appendix A) for the criteria we are seeking in the report.
4.2.1 Use Case Scenarios
There are many possibilities, but for this assignment, consider the following scenarios:
• Scenario 1 Growing runqueue (Enqueue). In this scenario, the runqueue is
growing with increasing processes are adding into the runqueue. In this scenario,
you are to evaluate the performance of your implementations in terms of the enqueue
operation (EN).
• Scenario 2 Shrinking runqueue (Dequeue). In this scenario, the runqueue
is shrinking with increasing processes are dequeuing from the runqueue. In this
scenario, you are to evaluate the performance of your implementations in terms of
the dequeue operation (DE).
• Scenario 3 Calculating total vruntime of proceeding processes. In this sce-
nario, assume the runqueue is not changing, but important operation of calculating
total vruntime of proceeding processes of a given process is required. In this sce-
nario, you are to evaluate the performance of your implementations in terms of the
PT operation.
4.2.2 Theoretical Analysis
At first, you are to conduct a theoretical analysis of the performance. Given a runqueue
of size n, report the best case, worse case running time estimate, and the asymptotic
complexity (Big O) of your implementations in terms of the different scenarios outlined
above. You will also need to provide an example scenario and explanation on the each of
the best case and worse case running time estimate, e.g. using an runqueue with a small
number (e.g.,5) of elements/processes. Put the results in the follow format of a table:
7
Theoretical Analysis
Scenarios Best Case Worse Case Big O
Scenario 1 [time estimation]
[example and explanation]
[time estimation]
[example and explanation]
[asymptotic
complexity]
Scenario 2 [time estimation]
[example and explanation]
[time estimation]
[example and explanation]
[asymptotic
complexity]
Scenario 3 [time estimation]
[example and explanation]
[time estimation]
[example and explanation]
[asymptotic
complexity]
4.2.3 Empirical Analysis
Typically, you use real usage data to evaluate your data structures. However, for this
assignment, you will write data generators to enable testing over different scenarios of
interest.
Data Generation
The time performance of the above mentioned scenarios and operations could vary sig-
nificantly depends on the structure and elements/processes of the initial runqueue.
We provide an artificial processes dataset of about 5000 processes, each with a label
(string) and a vruntime (integer number) in a file called “processes.txt”. Each line of this
file stores a process in the format of: label,vruntime
For generating runqueues with different initial structure and elements, you may want
to generate a series of add process operations (EN) to grow the runqueue to the desired
size, by either:
• randomly choosing processes from the file we supplied (‘processes.txt’); or
• writing a process generator to generate a new process. For example, for each pro-
cess, generate a unique string identifier/process label and a random integer (i.e.
vruntime) uniformly sampled within a fixed range, e.g., [1, 100].
Note, whichever method you decide to use, remember to generate runqueues of different
sizes to evaluate on (e.g., 10, 50, 100, 500, ...,1000, 5000). Due to the randomness of the
data, you may wish to generate a significant number of datasets with the same parameters
settings (same size and a scenario) and take the average across a number of runs. In your
analysis, you should evaluate each of your representations and data structures in terms
of the different scenarios outlined above. Hence, we advise you to get started on this part
relatively early.
5 Report Structure
As a guide, the report could contain the following sections:
8
• Theoretical analysis on running time and complexities of the different data structure
implementation as outlined in Section 4.2.2.
• Explain your data generation and experimental setup. Things to include are (brief)
explanations of the generated data you decide to evaluate on, the complexity pa-
rameters you tested on, describe how the scenarios were generated (a paragraph
and perhaps a figure or high level pseudo code suffice), which approach(es) you
decide to use for measuring the timing results.
• Evaluation of the data structures using the generated data. Analyse, compare
and discuss your results across different complexity parameters, representations
and scenarios. Provide your explanation on why you think the results are as you
observed. You may consider using the known theoretical time complexities of the
operations of each data structure to help in your explanation.
• For some particular data structure like Binary Search Tree (BST), you will also
need to suggest possible improvement to reduce running time on different scenarios.
In order to do that, you will need to understand well the complexity of various
operations on a BST, and be able to research beyond.
• Summarise your analysis as recommendations, e.g., “for this certain data scenario
of this parameters setup, I recommend to use this data structure because....”. We
suggest you refer to your previous analysis for help.
5.1 Clarification to Specifications
Please periodically check the assignment FAQ for further clarifications about specifica-
tions. In addition, the lecturer will go through different aspects of the assignment each
week, so even if you cannot make it to the lectures, be sure to check the course material
page on Canvas to see if there are additional notes posted.
6 Team Structure
This assignment is designed to be done in pairs (group of two). If you have difficulty
in finding a partner, post on the discussion forum or contact your lecturer. Any issues
(e.g., work division or workload) that result within the team should be resolved within
the team if possible; if this is not possible, then this should be brought to the attention
of the course coordinators as soon as possible. Marks are awarded to the individual team
members, according to the contributions made towards the final work. Please submit
what percentage each partner made to the assignment (a contribution sheet will be made
available for you to fill in), and submit this sheet in your submission. The contributions
of your group should add up to 100%. If the contribution percentages are not 50-50, the
partner with less than 50% will have their marks reduced. Let student A has contribution
X%, and student B has contribution Y%, and X > Y . The group is given a group mark
of M. Student A will get M for assignment 1, but student B will get MX
Y
.
7 Submission
The final submission will consist of four parts:
9
• Your Java source code of your implementations. Your source code should be
placed into in a flat structure, i.e., all the files should be in the same direc-
tory/folder, and that directory/folder should be named as Assign1-student number>-. Specifically, if your student num-
bers are s12345 and s67890, then all the source code files should be in folder
Assign1-s12345-s67890.
• Your written report for part B in PDF format, called “assign1.pdf”. Place this
pdf within the Java source file directory/folder, e.g., Assign1-s12345-s67890.
• Your data generation code. Create a sub-directory/sub-folder called “generation”
within the Java source file directory/folder. Place your generation code within that
sub-folder. We will not run the code, but will examine their contents.
• Your group’s contribution sheet. See the following ‘Team Structure’ section for
more details. This sheet should also be placed within your Java source file folder.
• Then, the Java source file folder (and files within) should be zipped up and named as
Assign1--.zip. E.g.,
if your student numbers are s12345 and s67890, then your submission file should be
called Assign1-s12345-s67890.zip, and when we unzip that zip file, then all the
submission files should be in the folder Assign1-s12345-s67890.
8 Assessment
The project will be marked out of 15. Late submissions will incur a deduction of 1.5
marks per day, and no submissions will be accepted 5 days beyond the due date.
The assessment in this project will be broken down into two parts. The following
criteria will be considered when allocating marks.
Implementation (8/15):
• You implementation will be assessed on the different implemented data structures,
respectively, and on the number of tests it passes in our automated testing.
• While the emphasis of this project is not programming, we would like you to main-
tain decent coding design, readability and commenting, hence these factors will
contribute towards your marks.
Report (7/15):
The marking sheet in Appendix A outlines the criteria that will be used to guide the
marking of your evaluation report. Use the criteria and the suggested report structure
(Section 4) to inform you of how to write the report.
Late Submission Penalty: Late submissions will incur a 10% penalty on the total
marks of the corresponding assessment task per day or part of day late. Submissions
that are late by 5 days or more are not accepted and will be awarded zero, unless special
consideration has been granted. Granted Special Considerations with new due date set
10
after the results have been released (typically 2 weeks after the deadline) will automat-
ically result in an equivalent assessment in the form of a practical test, assessing the
same knowledge and skills of the assignment (location and time to be arranged by the
coordinator). Please ensure your submission is correct (all files are there, compiles etc),
re-submissions after the due date and time will be considered as late submissions. The
core teaching servers and Canvas can be slow, so please do double check ensure you have
your assignments done and submitted a little before the submission deadline to avoid
submitting late.
Assessment declaration: By submitting this assessment, all the members fo the group
agree to the assessment declaration - https://www.rmit.edu.au/students/student-essentials/
assessment-and-exams/assessment/assessment-declaration
9 Academic integrity and plagiarism (standard warning)
Academic integrity is about honest presentation of your academic work. It means ac-
knowledging the work of others while developing your own insights, knowledge and ideas.
You should take extreme care that you have:
• Acknowledged words, data, diagrams, models, frameworks and/or ideas of others
you have quoted (i.e. directly copied), summarised, paraphrased, discussed or men-
tioned in your assessment through the appropriate referencing methods
• Provided a reference list of the publication details so your reader can locate the
source if necessary. This includes material taken from Internet sites. If you do not
acknowledge the sources of your material, you may be accused of plagiarism because
you have passed off the work and ideas of another person without appropriate
referencing, as if they were your own.
RMIT University treats plagiarism as a very serious offence constituting misconduct.
Plagiarism covers a variety of inappropriate behaviours, including:
• Failure to properly document a source
• Copyright material from the internet or databases
• Collusion between students
For further information on our policies and procedures, please refer to the following:
https://www.rmit.edu.au/students/student-essentials/rights-and-responsibilities/
academic-integrity.
10 Getting Help
There are multiple venues to get help. There are weekly consultation hours (see Canvas
for time and location details). In addition, you are encouraged to discuss any issues you
have with your Tutor or Lab Demonstrator. We will also be posting common questions on
the assignment 1 Q&A section on Canvas and we encourage you to check and participate
in the discussion forum on Canvas. However, please refrain from posting solutions,
particularly as this assignment is focused on algorithmic and data structure design.
11
12
A Marking Guide for the Report
Design of Evaluation Analysis of Results Report Clarity
(Maximum = 1.5 marks) (Maximum = 4 marks) (Maximum = 1.5 marks)
1.5 marks 4 marks 1.5 marks
Data generation is well
designed, systematic and
well explained. All
suggested scenarios, data
structures and a
reasonable range of size of
the runqueue were
evaluated. Each type of
test was run over a
number of runs and results
were averaged.
Analysis is thorough and demon-
strates understanding and critical
analysis. Well-reasoned explana-
tions and comparisons are provided
for all the data structures, scenar-
ios and different input sizes of the
runqueue . All analysis, compar-
isons and conclusions are supported
by empirical evidence and theoreti-
cal complexities. Well reasoned rec-
ommendations are given.
Very clear, well struc-
tured and accessible re-
port, an undergraduate
student can pick up the
report and understand
it with no difficulty.
1 marks 3 marks 1 marks
Data generation is
reasonably designed,
systematic and explained.
There are at least one
obvious missing suggested
scenarios, data structures
or reasonable size of the
runqueue . Each type of
test was run over a
number of runs and results
were averaged.
Analysis is reasonable and demon-
strates good understanding and crit-
ical analysis. Adequate comparisons
and explanations are made and il-
lustrated with most of the suggested
scenarios and input sizes of the run-
queue . Most analysis and compar-
isons are supported by empirical evi-
dence and theoretical analysis. Rea-
sonable recommendations are given.
Clear and structured for
the most part, with a
few unclear minor sec-
tions.
0.5 mark 2 marks 0.5 mark
Data generation is
somewhat adequately
designed, systematic and
explained. There are
several obvious missing
suggested scenarios, data
structures or reasonable
size of the runqueue .
Each type of test may only
have been run once.
Analysis is adequate and demon-
strates some understanding and crit-
ical analysis. Some explanations
and comparisons are given and il-
lustrated with one or two scenarios
and sizes of the runqueue . A por-
tion of analysis and comparisons are
supported by empirical evidence and
theoretical analysis. Adequate rec-
ommendations are given.
Generally clear and well
structured, but there
are notable gaps and/or
unclear sections.
0 marks 1 mark 0 marks
Data generation is poorly
designed, systematic and
explained. There are
many obvious missing
suggested scenarios, data
structures or reasonable
size of the runqueue .
Each type of test has only
have been run once.
Analysis is poor and demonstrates
minimal understanding and critical
analysis. Few explanations or com-
parisons are made and illustrated
with one scenario and size setting.
Little analysis and comparisons are
supported by empirical evidence and
theoretical analysis. Poor or no rec-
ommendations are given.
The report is unclear
on the whole and the
reader has to work hard
to understand.
13
References
[1] Completely fair scheduler. https://en.wikipedia.org/wiki/Completely_Fair_
Scheduler.
[2] Scheduling (computing). https://en.wikipedia.org/wiki/Scheduling_
(computing).
14
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468