Objectives

• practice modular design;
• get proficient with the ADT Stack, Queue, and Heap/Priority Queue;
• practice developing applications using ADT Stack, or Queue, or Heap/Priority Queue.

This assignment is worth 5% of your final grade.

Problem Description

Your task is to develop a C++ program that simulates a computer job queue (or sometimes called a batch queue).

There are two types of jobs in a computer system: system jobs and user jobs.

When a program starts and waits to be executed, a job is created and is inserted to the job queue for processing. Each job would contain the following information:

• its job type which is either system or user;
• an estimated execution time that is a positive floating point number;
• a user id (in the format of a Linux username) that indicates who started this job; (note: system jobs are usually started by root, but not necessarily so)
• a command name (a string starts with a letter, consists only letters and digits) used to start this job; and
• a resource list (a one line string of printable characters) that describes the resources this job requires (an empty string means that this list is empty).

When the computer is ready to process the next job in the job queue, it always processes system jobs ahead of any user jobs. Among the same typed jobs, the shortest job will be processed first. (Hint: a job's type and its estimated execution time determines the job's priority.)

Your program should interactively accept and handle the following commands:

• submit: to submit a new job request. Your program should ask for the job's time, its estimated execution time, its user id, its command name and a line to describe the resources the job requires. Then your program should insert the job into the job queue.
  Your program can give your job queue a pre-defined capacity. If the job queue is full when a new job request is submitted, the new submission should be denied its service with an explanation.
• execute: to remove the job with the highest priority from the job queue to be executed. To simulate the execution of a job, your program simply displays the job's information. If the job queue is empty when this command is entered, your program should show an appropriate message.
• lottery: to randomly remove a lucky job from the job queue to be executed. This command is designed to give the long and/or user jobs a chance to be executed earlier than its priority warrents.
• quit: to terminate your program. Before the termination, your program should empty the job queue by removing them one by one as a simulation of forcibly killing all uncompleted jobs.

This is an interactive program and it should shutdown only when the command quit is entered.

Your program can safely assume that the user will enter numbers for the estimated execution time. However, the appropriate error checking needs to be done to make sure the numbers fall in the right range.

If the job type entered for a job is neither "system" nor "user", or any other invalid data is entered for the job's information (such as a negative number entered for the estimated execution time), then this job request is discarded with a proper explanation message.

You must design and implement your own Priority Queue ADT for this assignment. And the expected performance of the operations insert and removeMin must be O(logN) where N indicates the number of jobs in your job queue.

Design and Documentation

Your source code file should have the proper documentation, such as the header comment for each file, description of the functionality for each function/method unless the name of the function/method is self-explanatory, and some proper in-line comment to improve the readability of the implementation.

You need to include a README file with your solution. In your README file (Note: do not give it any extension name), there should be following sections:

• Specification: briefly describe the requirements of this application.
• Design: briefly describe the modules in your application design and why you choose your current design.
• Implementation: briefly describe the concrete data structures used in each module. List the advantage and disadvantage of using these data structures. Explain whether there are alternative ways to implement this module.
• Analysis: for each of the command submit, execute and lottery, give a rough analysis about the time efficiency of your implementation.
• Accomplishment: state clearly which parts of the assignment you have completed.
• Testing: list the test cases you have covered to test your program. For each test case, describe the data you used and the result shown by your program. Alternatively, if you used script to capture the sample run of your program, then you only need to describe your test cases and refer to your typescript file for the test run result.
• Know Bugs.
• Note: anything you would like to draw to the attention of the marker.

Create a Makefile to automate the building of your program. Upon typing make, an executable file named pex1 should be generated.

If your program has compile time errors, you lose all the execution correctness marks (which is about 70 percent of the total marks) for this assignment.

Submission

To submit your solution, change working directory to where your solution is located and run the following command:

~liuh/bin/submit 260 Pex1 .

The submit script currently accept Makefile, README, typescript, *.cpp, *.h, src/*.cpp and include/*.h files.

If this command is successfully executed, it should show you a list of the files just got submitted to the instructor's directory. If you submit your assignment more than once, all but the last one will be discarded. Take advantage of this feature, submit early and submit often. Your assignment must be submitted before the due date and time.

You can check what you have submitted for this assignment by running the following command:

~liuh/bin/checksubmit 260 Pex1