Description
1. Problem Description In this homework, we are going to implement a task manager with the following usage: taskMgr [-File ] where the bold words indicate the command name or required entries, square brackets “[ ]” indicate optional arguments, and angle brackets “< >” indicate required arguments. Do not type the square or angle brackets. This taskMgr program should provide the following functionalities: 1. A task manager (a global variable “taskMgr” of class TaskMgr) to supervise various task nodes (class TaskNode). A task node stores the information of the machine that executes the task, which includes the machine name and its accumulated workload. All the task nodes in the task manager should have distinct machine names. 2. A hash (class HashSet) to look up the task node by machine name, and a heap (class MinHeap) to record and dynamically update the minimum task node (i.e. the one with the minimum accumulated load). Please note that the task nodes stored in hash and in heap should be in sync at all times. 3. To properly allocate the number of buckets for the hash and reserve the memory for the heap, there should be a command (TASKInit) to initialize 2 the task manager. In addition, there should be commands to insert new task nodes to and remove existing task node from the task manager (TASKNew and TASKRemove, respectively). Note that both TASKNew and TASKRemove commands can only be evoked after the task manager is initialized (TASKInit). 4. There should be a command (TASKQuery) to query and print the task node(s). 5. There should be a command (TASKAssign) to assign new task(s) with specified workload to the task node(s) of the minimum accumulated load(s). 2. Supported Commands In this homework, you should support these new commands: TASKAssign: Assign load to the minimum task node(s) TASKInit: Initialize task manager TASKNew: Add new task nodes TASKQuery: Query task manager TASKRemove: Remove existing task nodes Please refer to Homework #3 and #4 for the lexicographic notations. 2.1 Command “TASKInit” Usage: TASKInit <(size_t numMachines)> Description: Initialize the task manager “taskMgr”. The option “numMachines” is the approximated number of task machines (i.e. task nodes) that you expect to add later. It will initialize the hash with the getHashSize(nMachines) (note: defined in “util/util.cpp”) number of buckets, and reserve the memory for the heap (i.e. capacity = numMachines). Note that no task nodes will be created or added (i.e. size = 0). They should be added by the TASKNew command. If the global task manager “taskMgr” is initially NOT NULL, it will be deleted and reconstructed. A warning message “Warning: Deleting task manager… ” will be issued in such case. Example: task> taski 100 // initialize with number of approximated task nodes = 100 task> taski // Error: missing number of task nodes task> taski 100 200 // Error: extra argument (200) 3 2.2 Command “TASKNew” Usage: TASKNew <-Random (size_t numMachines) | -Name (string name) (size_t load)> Description: Insert new task nodes to the task manager and print out “Task node inserted: (name, load)” for each newly added one. It can be randomly generated with specified number of machines or manually created with assigned machine name and workload. For random generation, exactly “numMachines” number of task nodes should be created. That is, if a node with duplicated name is generated, it should be discarded and regenerated. On the other hand, the “-Name” option manually creates ONE machine at a time. If the machine name collides with some task node in the task manager, an error message “Error: Task node (name) already exists.” will be issued and no task node will be added. Example: task> taskn –r 10 // randomly generate 10 distinct task nodes task> taskn –n abcde 123 // manually insert the task node (“abcde”, 123) 2.3 Command “TASKRemove” Usage: TASKRemove <-Random (size_t nMachines) | -Name (string name)> Description: Remove task node(s) from the task manager and print out “Task node removed: (name, load)” for each removed one. It can be randomly removed with specified number of machines or manually removed with assigned machine name. For random removal, if the specified number nMachines is equal to or greater than the number of task nodes, then all the task nodes will be removed and warning message will be issued if greater. For each of the random removal, a random number i between 0 and s-1 (s is the number of total task nodes) is first generated and the ith element of the heap will be removed (by MinHeap::delData(i)). That is, there must be one node removed by each random removal call. The corresponding task node in hash should then be removed, too. Note that after each removal, the heap structure should be properly maintained. For manual removal, task node with the specified name in both heap and hash will be removed. If there is no task node with such name, an error message “Error: Task node (name) does not exist.” will be issued. Example: task> taskr –r 10 // randomly remove 10 task nodes task> taskr –n abcde // manually remove the task node with name “abcde” 4 2.4 Command “TASKQuery” Usage: TASKQuery <(string name) | -HAsh | -HEap | -MINimum > Description: Query and print the task node in the task manager. If the machine name is specified, query the node with that name and print it. If there is no such node, print out an error message “Query fails!”. If the option “-HAsh” or “-HEap” is specified, print all task nodes with the order as stored in the hash and heap, respectively. Lastly, the option “-MINimum” will print out the one with the minimum workload. Example: task> taskq abcdefg // query the task node with name = “abcdefg” task> taskq –hash // print out all task nodes with the order as stored in hash task> taskq –min // print out the node with minimum workload 2.5 Command “TASKAssign” Usage: TASKAssign <(size_t load)> [-Repeat (size_t repeats)] Description: Assign the workload to the task node with the minimum accumulated workload. The option “-Repeat (size_t repeats)” specifies how many times the same workload will be repeatedly assigned. Note that every time the workload is assigned, the accumulated workload of the minimum task node will be incremented by “load” and the minimum task node (in the heap) will be updated accordingly. Therefore, it is likely that the repeated workload will be assigned to different task nodes. Example: task> taska –r 100 1000 // assign workload 1000 to the min node for 100 times 3. What you should do? You are encouraged to follow the steps below for this homework assignment: 1. Read the specification carefully and make sure you understand the requirements. 2. Think first how you are going to write the program, assuming you don’t have the reference code. 3. Type “make linux18”, “make linux16” or “make mac” to switch to a proper platform. The default is linux18 platform. 5 4. Play with the reference programs in the “ref” directory to make sure you understand the spec. 5. Implement the TODOs in “myHashSet.h” and “myMinHeap.h” in the “util” package. Write some test programs to test them first. 6. Finish the TODOs in “taskMgr.cpp” for the task manager commands. 7. Test your implementation with the provided testcases. You are also encouraged to create more testcases on your own. 4. Grading We will test your submitted programs with various testcases and compare the outputs with our reference program. Minor differences due to printing alignment, spacing, error message, etc can be tolerated. However, to assist TAs for easier grading work, please try to match your output with ours.
