1 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 different processes such that each process’s needs for resources are satisfied. 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 reasons1, 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 first, 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.
2 Simulation Description and Input Format
Two Java source files 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 file 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 specification. It
1. See the Wikipedia entry at https://en.wikipedia.org/wiki/Nice_(Unix) for details on the origin of the name
1
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 file, 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 file if you want to store it for future use (such as automated comparison using the diff tool).
The program is intended to simulate a fictional 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 reprioritize (‘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 file must meet the exact criteria described in this section or it will be considered invalid for the purposes of testing.
The first 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 file have an ID outside the range, the input is invalid.
Each of the lines after the first 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 file, so you do not have to write any code to interpret the input data (but you should understand the structure of an input file).
2
The add operation has the form