Description
Learning outcomes
When you have completed this assignment, you will have learned:
• How to create an implementation of TaskList using a reference-based linked
list.
• How to use reference values including the null value.
• How to debug Java code that makes extensive use of ref-based variables.
Task Scheduling
Problem description
Modern computer operating systems (such as Mac OS X, Linux, and Windows 8) are
designed and constructed around several main concepts. One concept is the task
(sometimes called a process or thread). When you use the Java compiler, it runs as a
task; when you start up a web browser, it runs as a task. There are also many tasks
running “in the background”. In fact, some tasks generate additional tasks in order to
complete some larger, more involved computation. Every task has many properties,
including those known as task priority and task number.
Since an operating system (or OS) is organized around the running of tasks, there
exists a central algorithm that schedules tasks, i.e., it chooses the next task to run
when the current task must halt or pause. Making this choice is relatively easy: the
scheduler simply takes the next available task having the highest priority, and the
task is then given a chance to run on the computer. A task list is a data collection used
to arrange waiting tasks in an order suitable for the OS scheduler. That is:
• When a task is created, it is placed into the task list at a position appropriate
for the task’s priority and arrival time.
Page 2 of 4
• When the OS must choose a task to execute, it takes the one at the head of the
task list.
In this assignment we will not be modifying an existing operating system (!) but we
will play with an implementation of operations needed for a Task List ADT. The data
structure to be used for the implementation is a referenced-based linked list.
Examples
Imagine the following four tasks arrivals (also called four TA events) that occur in the
order shown:
(10, 212)
(12, 100)
(10, 198)
(3, 104)
The first number in each line corresponds to that task’s priority, and the second
number corresponds to the task number. Here our first task has a priority of 10 and a
task number of 212. We want our list organized such that higher priority tasks are
closer to the head, but tasks with the same priority are in order of arrival time (i.e.,
earlier tasks are closer to the head). If the four TA events are the first ones in our
computer, then the resulting task list will be:
{ (12, 100), (10, 212), (10, 198), (3, 104) }
When the scheduler chooses a task for execution (an event denoted as SC) it removes
the first task from the list – in fact, what the scheduler needs most is the task number
of the task at the head of the list. Therefore the next task to be scheduled is:
100
and the task list after the SC event is:
{ (10. 212), (10, 198), (3, 104) }
Sometimes an OS decides a task must deleted before the task has a chance to execute.
This means removing the task from the list (a TD event). Suppose task number 198 is
to be deleted. Once deletion occurs, our resulting task list is:
{ (10, 212), (3, 104) }
Knowing the number of tasks in the task list (or asking for its status, or an ST event)
can be important for other parts of the operating system. Since the number of tasks is
simply the list’s length, we can see there are currently two tasks in the system. If we
add three more TA events:
(10, 85)
(4, 314)
(2, 101)
Page 3 of 4
then the resulting list is:
{ (10, 212), (10, 85), (4, 314), (3, 104), (2, 101) }
and an ST event would result in the following value:
5
Task Scheduling
For this assignment you will complete TaskListLL.java which as this will be your refbased linked-list implementation of the TaskList interface. Your TaskListLL will be
used by code that simulates the TA, TD, SC and ST actions described above. (The
simulator code is contained in A2test.java and used specifically in the last four tests.)
That is, the simulator will use the following completed routines in your
implementation of TaskListLL:
• insert: used by TA
• remove: used by TD
• removeHead: used by SC
• getLength: used by ST
• isEmpty: used by the simulator to control the event loop
The required behavior of these methods is described in TaskList.java.
Several other files are also provided to you:
• TaskList.java: A representation of the data for a Task along with equals() and
compareTo() methods.
• TaskListNode.java: To be used by code within TaskListLL.
• TaskListArray.java: A completed implementation of the TaskList interface but
using an array to store tasks.
• A2test.java: The tester program for this assignment. When run without any
arguments, it used TaskListLL for testing; if at least one argument is provided,
then TaskListArray is used instead.
Here is a run of A2test that uses TaskListArray:
$ javac A2test.java
$ java A2test abc
Testing of ‘TaskList’ class (basic)
Passed test: 1
Passed test: 2
…
Running task simulation 3
Passed test: 39
Running task simulation 4
Passed test: 40
Page 4 of 4
And here a run of A2test that uses TaskListLL as it is distributed with this assignment.
$ java A2test
Testing of ‘TaskList’ class (basic)
ECHO getLength()
Failed test: 1 at line 216
(Note that you should remove all of the “ECHO” println statements in your completed
implementation of TaskListLL.)
As with assignment #1, when we evaluate your work it is the first failed test that will
matter most for us (i.e., we do not cherry-pick tests by ignoring earlier failed tests
while accepting later passing tests). Tests after the first failed test are themselves
considered to have failed.
There are 40 tests and your code is expected to pass them all.
File to submit:
• TaskListLL.java
Grading scheme
Requirement Marks
TaskListLL.java compiles without errors or warnings 2
Code passes the first set of test cases (1 to 16) 2
Code passes the second set of test cases (17 to 22) 3
Code passes the third set of test cases (23 to 28) 4
Code passes the fourth set of test case (29 to 36) 5
Code passes the four simulations (37 to 40) 2
Code uses follows the posted coding conventions on commenting. 2
Total 20
Note: Code submitted must be written using techniques in keeping with the goals of
the assignment. Therefore passing a test is not automatically a guarantee of getting
marks for a test (i.e., your solution must not be written such that it hardcodes results
for specific tests in A2test.java yet would be unable to work with similar tests when
different data is used).
In order to obtain a passing grade for the assignment, you must satisfy at least the
first four requirements by passing all of their test cases.
