5-ASSIGNMENT 2__Solution

Description

• Assignment Overview: A nice simulator

In a multitasking operating system (such as the operating system on the machine you’re using to read this), CPU time must be divided among a set of di erent processes such that each process’s needs for resources are satis ed. Each process may have an associated priority, and processes with better priorities receive more computation time, while processes with less priority receive less. It can often be useful to deliberately give a process a low priority to run it unobtrusively in the background (and ensure that it does not interfere with other running tasks).

On Unix-like operating systems, a command called nice can be used to start a process with an arbitrary priority, and the command renice can be used to change the priority of a running process. For strange historical reasons¹, the priority of each process is called its nice value, and processes with lower nice values are given more processing time (that is, a ‘high priority’ task has a low ‘nice level’). The apparent logic used by the creators was that the ‘nicer’ a process was, the more likely it would be to let other processes execute rst, so a high ‘nice level’ correlates to low processing priority.

This programming assignment involves implementing a data structure for a simple CPU scheduling simulator. CPU scheduling is a complex topic, and is covered properly in courses like CSC 360 (Operating Systems). The goal of this assignment is to apply the concept of a priority queue to a specialized data structure which implements the operations of the simulator (and therefore requires more functionality than a basic priority queue), and our CPU scheduling simulation will therefore be relatively simple to allow the assignment to focus on the algorithms involved instead of the process model.

In deference to the Unix tradition, our simulator will use ‘nice levels’ to dictate priority, and give preference to tasks with lower nice levels over those with higher nice levels.

• Simulation Description and Input Format

Two Java source les have been provided. The Nice.java program contains a main() method which parses input data, runs the simulation and generates output and the NiceSimulator.java le contains an (unimplemented) data structure for each of the simulated operations. You are expected to implement all of the methods of the NiceSimulator class to conform to this speci cation. It

1. See the Wikipedia entry at https://en.wikipedia.org/wiki/Nice_(Unix) for details on the origin of the name

should not be necessary to modify the Nice.java program at all, but you are welcome to do so, as long as your submitted result has exactly the same output format as the provided Nice.java program.

This section describes the simulator program which reads the input data and calls methods of the NiceSimulator data structure. Note that the entire simulator program described in this section has been provided to you in Nice.java, so you do not need to write code for any of the functionality described in this section. To read about the data structure you are required to implement, you can skip to Section 3. However, you will need to consult this section for information on what constitutes a valid test input.

Once compiled, the simulator can be run with the command

java Nice

Normally, the simulator will read its input from standard input (which defaults to user input). To provide input data from a le, use shell redirection, as in the example below.

java Nice < input_file.txt

Output will be produced to standard output (which defaults to the console). As with input, you can redirect output to a le if you want to store it for future use (such as automated comparison using the diff tool).

The program is intended to simulate a ctional CPU whose time must be divided among a set of tasks. Each task has a unique ID number, which must be a positive integer, an priority value (nice level), which may be any integer (including a negative value), and a time requirement, which must be a positive integer. At each step of the simulator, one task will be selected to run, and its total time requirement will decrease accordingly. Once a task’s time requirement has reached zero, the task is complete and is removed from the system. Eventually, all tasks will be complete and the CPU will be idle.

The input to the simulator program is a set of commands, which may add, remove or repriori-tize (‘renice’) tasks from the set of active tasks. After reading the input, the simulator uses the NiceSimulator data structure to repeatedly simulate single units of CPU time (or ‘timesteps’), during which one of the active tasks will be run (and its total time requirement decremented) until a timestep occurs in which no active jobs are available and the simulated CPU is idle, at which point the simulation ends.

Input is provided in a simple text-based format. Note that an input le must meet the exact criteria described in this section or it will be considered invalid for the purposes of testing.

The rst line of the input is an integer max_tasks, which must be positive. All task ID numbers must be in the range 0 – max_tasks 1 (inclusive). If any tasks in the input le have an ID outside the range, the input is invalid.

Each of the lines after the rst line is a task operation, which may be either add, kill or renice. Note that a valid input must have at least one line (the max_tasks value), but there may be no additional lines (in which case the simulation stops after one step, since there are no tasks to simulate in such cases).

Note that the provided Nice.java program contains all of the code needed to parse and validate the input le, so you do not have to write any code to interpret the input data (but you should understand the structure of an input le).

The add operation has the form

<time> add <task ID> <time requirement>

and adds a task with the ID and time requirement provided immediately before the indicated time step. The time requirement must be a positive (and therefore non-zero) value or the input le will be considered invalid. If a task with the provided ID already exists, then the entire input le is considered invalid (since it is not possible to add a task in such cases).

The kill operation has the form

<time> kill <task ID>

and deletes the task with the provided ID immediately before the indicated time step. If a task with the provided ID does not exist, then the entire input le is considered invalid.

The renice operation has the form

<time> renice <task ID> <new priority>

and changes the priority of the task with the provided ID to the provided priority value immediately before the indicated time step. If a task with the provided ID does not exist, then the entire input le is considered invalid.

For the input le to be valid, the operations in the le must be ordered chronologically (so the operations can be applied in the simulation in the same order they appear in the input le). This implies that the timesteps of the operations in the le must appear in ascending order (so an operation set for time 6 must appear before an operation set for time 10).

• The NiceSimulator data structure

The NiceSimulator data structure contains 8 methods, including a constructor. All 8 methods are empty and must be implemented before the simulator will work. You are permitted to add other methods (or classes) as needed. You are not permitted to change the method signature (name/argument list) or speci cation of any of the 8 provided methods. If you do so, you will receive no marks for the corresponding aspects of the asssignment.

An implementation-level description of each method is given in comments inside the NiceSimulator.java le. None of the methods in NiceSimulator.java may throw any exceptions during normal operation (and adding a throws clause to the method signature is not permitted). A high level description of each method is given below. For full marks, each of the methods must achieve the worst case running time given in the ‘Target Time’ column. However, as for assignment 1, you will receive no marks for running time unless your code is correct, so an asymptotically less-e cient implementation will be worth more marks than a broken (but allegedly ‘fast’) imple-mentation. The parameter n in the running time expressions is de ned to be the number of active tasks (tasks which have at least one unit of time remaining in their requirement), not the maximum number of possible tasks.

Method	Target	Description
	Time
NiceSimulator(maxTasks)		(Constructor) Initialize the data structure for the pro-
		vided maximum number of tasks. The structure may
		assume that no task with an ID outside the range
		[0; maxTasks 1] will ever be used by any operation.
		There are no restrictions on the running time of this
		method.
taskValid(ID)	O(1)	Return true if the provided ID is a valid task (with at
		least one unit of time remaining) and false otherwise.
getPriority(ID)	O(1)	Return the current nice level for the provided task ID.
getRemaining(ID)	O(1)	Return the time remaining for the provided task ID.
add(ID, time)	O(log2 n)	Add a new task with the provided ID and time re-
		quirement. The new task will be assigned a priority of
		0.
kill(ID)	O(log2 n)	Delete the task with the provided ID.
renice(ID,priority)	O(log2 n)	Set the priority of the provided task to the provided
		ID.
simulate()	O(log2 n)	Identify the task t which will run next (see rules be-
		low) and subtract one from the task’s time require-
		ment. If the requirement is decreased to zero, return
		the ID number of task t. Otherwise, return either the
		constant SIMULATE_IDLE (if no task t was found) or
		SIMULATE_NONE_FINISHED (if t was found but still has
		time remaining).

In the simulate() method, the next task t to run is selected by the following rules:

• If no active tasks exist, then no task t can be found.

• Otherwise, if exactly one task has the lowest nice level, that task is selected as t.

• If multiple tasks all have the lowest nice level, then the task with the smallest task ID will be selected as t.

Since this assignment will not be evaluated by demos, you are encouraged to add comments to your code explaining the running time of each operation to ensure that you receive the marks for achieving the targeted running time.

• Sample Input Files

Consider the input le below, which de nes 4 jobs with several di erent execution times. Recall from the previous section that the initial priority of a job is always 0, so to assign a di erent initial priority to a job, it is necessary to use a renice operation before step 0.

			Input File				E ect
32768					Set max		tasks to 32768
0	add	6 3			Add task 6 (with time requirement 3) before timestep 0
0	add	10	4		Add task 10 (with time requirement 4) before timestep 0
0	add	17	5		Add task 17 (with time requirement 5) before timestep 0
0	renice		6	-1	Renice task 6 to nice level			1 before timestep 0
0	renice		10	100	Renice task 10 to nice level 100 before timestep 0
0	renice		17	1	Renice task 17 to nice level 1 before timestep 0
4	add	225 6			Add task 225 (with time requirement 6) before timestep 4
7	kill 225				Terminate task 225 before timestep 7
9	renice		10	-2	Renice task 10 to nice level			2 before timestep 9

The table below shows the progression of a correct simulator on the input le above. Notice that the operations in the input le are always applied immediately before the provided timestep number and that the input operations do not consume any timesteps to perform. Only the simulate() method actually consumes simulation time.

							Job Status (after current timestep)
Time	Running		Task 6						Task 10					Task 17					Task 225				Notes
Step	Task		Priority		Time				Priority		Time			Priority		Time			Priority		Time
						Left					Left					Left					Left
						Before timestep 0
Add task 6 with time requirement 3
Add task 10 with time requirement 4
Add task 17 with time requirement 5
Renice task 6 to priority -1
Renice task 10 to priority 100
Renice task 17 to priority 1
–	–		1			3			100		4			1		5			–		–		Before timestep 0
0	6		1			2			100		4			1		5			–		–
1	6		1			1			100		4			1		5			–		–
2	6		–			–			100		4			1		5			–		–		Task 6 nished.
3	17		–			–			100		4			1		4			–		–
						Before timestep 4
Add task 225 with time requirement 6
(Note that since task 225 is run next, the requirement immediately drops to 5)
4	225		–			–			100		4			1		4			0		5
5	225		–			–			100		4			1		4			0		4
6	225		–			–			100		4			1		4			0		3
						Before timestep 7
Kill task 225
7	17		–			–			100		4			1		3			–		–
8	17		–			–			100		4			1		2			–		–
						Before timestep 9
Renice task 10 to priority						2
9	10		–			–			2		3			1		2			–		–
10	10		–			–			2		2			1		2			–		–
11	10		–			–			2		1			1		2			–		–
12	10		–			–			–		–			1		2			–		–		Task 10 nished.
13	17		–			–			–		–			1		1			–		–
14	17		–			–			–		–			–		–			–		–		Task 17 nished.
15	–		–			–			–		–			–					–		–		CPU Idle.
							Simulation Ends

A second input le appears below. Notice that the same task ID is used for more than one task: Task 10 is added at timestep 2 and, after it nishes, another task with ID 10 is added at timestep 6. Task IDs may be reused an unlimited number of times within the program, as long as any previous task with the same ID has either nished or been killed.

			Input File			E ect
16384				Set max		tasks to 16384
0	add	100 3		Add task 100 (with time requirement 3) before timestep 0
0	renice		100 1	Renice task 100 to nice level 1 before timestep 0
0	add	2017 4		Add task 2017 (with time requirement 4) before timestep 0
0	renice		2017 2	Renice task 2017 to nice level 2 before timestep 0
2	add	10	3	Add task 10 (with time requirement 3) before timestep 2
2	renice		10 -10	Renice task 10 to nice level			10 before timestep 2
3	renice		2017 -1	Renice task 2017 to nice level			1 before timestep 3
6	add	10	2	Add task 10 (with time requirement 2) before timestep 6

The simulation progression for the input le above is shown below.

			Job Status (after current timestep)
Time	Running	Task 10					Task 100				Task 2017				Notes
Step	Job	Priority			Time		Priority		Time		Priority		Time
					Left				Left				Left
		Before timestep 0
Add task 100 with time requirement 3
Renice task 100 to priority 1
Add task 2017 with time requirement 4
Renice task 2017 to priority 2
–	–	–			–		1		3		2		4		Before timestep 0
0	100	–			–		1		2		2		4
1	100	–			–		1		1		2		4
		Before timestep 2
Add task 10 with time requirement 3
Renice task 10 to priority -10
2	10	10			2		1		1		2		4
		Before timestep 3
Renice task 2017 to priority -1
3	10	10			1		1		1		1		4
4	10	–			–		1		1		1		4		Job 10 nished.
5	2017	–			–		1		1		1		3
		Before timestep 6
Add task 10 with time requirement 2
6	2017	0			2		1		1		1		2
7	2017	0			2		1		1		1		1
8	2017	0			2		1		1		–		–		Job 2017 nished.
9	10	0			1		1		1		–		–
10	10	–			–		1		1		–		–		Job 10 nished.
11	100	–			–		–		–		–		–		Job 100 nished.
12	–	–			–		–		–		–		–		CPU Idle.
			Simulation Ends

• Using Outside Code

You are encouraged to use the features of the Java Standard Library (including any of the data structures it provides) in your code. If you use a standard library data structure, make sure you are aware of the running times of the operations you use, since that will be important for determining the running time of your program.

There should be no need to use large volumes of code from other sources (such as outside libraries or the internet) in this assignment. If you believe that your implementation requires an outside library, talk to your instructor.

If you nd a small snippet of code on the internet that you want to use (for example, in a Stack-

Over ow thread), put a comment in your code indicating the source (including a complete URL).

Remember that using code from an outside source without citation is plagiarism.

You are encouraged to discuss the assignment with your peers, and even to share implementation advice or algorithm ideas. However, you are not permitted to use any code from another CSC 225 student under any circumstances, nor are you permitted to share your code in any way with any other student (or the internet) until after the marking is complete. Sharing your code with others before marking is completed, or using another student’s code for assistance (even if you do not directly copy it) is plagiarism.

• Peer Testing

In addition to your code, you will be expected to include a single test input (in the format described in Section 2) in a text le called test_input.txt. Your test input must meet the following criteria to be considered valid (and any invalid test input will receive zero marks):

• The input must meet all of the conditions in Section 2 to be a valid input.

• The simulation must nish in at least 10 and at most 1000000 timesteps.

• The max_tasks value may be at most 65536.

• The input may contain at most 100000 lines.

After the due date (Sunday, July 2nd, 2017), the results of testing every submitted implementation against every submitted test input will be posted to the Testing Database on conneX. No student numbers will be used in the published data (you will be identi ed by a randomly assigned numerical alias). Your complete test input will also be posted to assist your peers in their testing, but the code for your implementation will not be published (and you are reminded not to share it with any other students until after all marking is complete). Since the output of your program’s testing will be publicly visible, please ensure that your program’s output contains no identifying information.

After the results of peer testing are posted, you will have the opportunity to revise and resubmit your code until Friday, July 7th, 2017. You will not be permitted to resubmit if you did not submit an implementation before the July 2nd deadline (and you will therefore receive a mark of zero). Since all test inputs will be published, you will also not be permitted to resubmit your test input.

For marking purposes, your original and revised submissions will be tested on a set of test inputs created by your instructor (you will not be graded based on the results of peer testing). The 8 marks for program function (see Section 7) will be computed by taking the average of the number of tests passed by your original submission and the number of tests passed by your revised submission.

• Evaluation

Submit all .java les needed to compile your assignment electronically via conneX. Your code must compile and run correctly in the Linux environment in ECS 242. If your code does not compile as submitted, you will receive a mark of zero.

This assignment is worth 7% of your nal grade and will be marked out of 14 with a combination of automated testing and human inspection. This assignment will not be evaluated by interactive demos.

The marks are distributed among the components of the assignment as follows.

Marks

Component

• The requirements in this document are met and the output of the program is correct on a variety of tested inputs.

• Your submitted test input is valid (see Section 6).

• The taskValid, getPriority and getRemaining methods all have worst case O(1) running time.

• The add, kill and renice methods all have worst case O(log₂ n) running time.

• The simulate method has a worst case O(log₂ n) running time.

• All of the required methods of the data structure (except the constructor) have a worst case O(log₂ n) running time.

You are permitted to delete and resubmit your assignment as many times as you want before the due date, but no submissions or resubmissions will be accepted after the due date has passed. You will receive a mark of zero if you have not o cially submitted your assignment (and received a con rmation email) before the due date.

Your data structure must be contained in NiceSimulator.java (and the main simulator program must be contained in Nice.java). You may use additional les if needed by your solution (as long as the program can be invoked from the command line using the syntax in Section 2). Ensure that each submitted le contains a comment with your name and student number.

Ensure that all code les needed to compile and run your code in ECS 242 are submitted. Only the les that you submit through conneX will be marked. The best way to make sure your submission is correct is to download it from conneX after submitting and test it. You are not permitted to revise your submission after the due date, and late submissions will not be accepted, so you should ensure that you have submitted the correct version of your code before the due date. conneX will allow you to change your submission before the due date if you notice a mistake. After submitting your assignment, conneX will automatically send you a con rmation email. If you do not receive such an email, you did not submit the assignment. If you have problems with the submission process, send an email to the instructor before the due date.

9