CSCE 2014 - Homework 5
Part 1 - Due Date - 11/05/2009 at 11:59 PM
Part 2 - Due Date - 11/09/2009 at 11:59 PM

1. Problem Statement:

Every operating system has a scheduling algorithm that allows multiple programs to run concurrently and share the central processing unit, memory, and other system resources. At the heart of this algorithm is a CPU queue that contains a list of programs that are currently running. This queue is updated as new programs are started and when current programs finish execution. The CPU queue is also updated as each program takes their turn running.

The purpose of this assignment is to implement a simulation of a CPU queue. This will let us see first hand what happens when lots of programs try to execute at one time. To simplify the implementation of this simulation, we will be using an ascii file of user commands. This file will start with an integer count specifying how many commands are in the file. This is followed by count lines with the following format: start_time run_time program_name.

   10 25 A
   13 10 B
   15 45 C
   27 60 D

The example above is a file describing the execution of four programs A, B, C and D. Here, we have program A starting at time 10 and running for 25 CPU seconds. At time 13, program B will start and run for 10 CPU seconds. Similarly, programs C and D will start at times 15 and 27 run for 45 and 60 CPU seconds respectively.

Part 1:

Because it is impossible for two or more programs to run on one CPU at a time, these programs will take turns running on the machine in a round robin fashion. The CPU queue keeps track of the current programs being executed.

To perform an accurate simulation, your program must perform the following tasks:

In order to show your simulation in action, you must invent some way to display the status of the CPU queue over time. You should also output when each program starts and when they terminate. For example, you could output something like this:

   t=10 start A
   t=10 (10,25,A) 
   t=11 (10,24,A) 
   t=12 (10,23,A) 
   t=13 start B
   t=13 (10,22,A) (13,10,B) 
   t=14 (13,10,B) (10,21,A) 
   t=15 start C
   t=15 (10,21,A) (13,9,B) (15,45,C) 
   t=16 (13,9,B) (15,45,C) (10,20,A) 
   t=17 (15,45,C) (10,20,A) (13,8,B) 

Finally, your program should print out when the CPU was the most congested. It is up to you to decide what you mean by congested and to perform this calculation. You can print this out after the simulation output.

Part 2:

To make your simulation more realistic, we will add multiple CPUs to the computer, and introduce the notion of program priority. To do this, extend your program to do the following:

2. Design:

This programming assignment has more design flexibility than many of our previous assignments. You are welcome to use any data structure you want to store the information you read from the the ascii input file. Here is a sample simulation.txt file for your testing.

Your program must use a C++ queue class to store the CPU queue information. You are encouraged to use/modify the queue from the lab8 for this purpose.

Your program must perform the operations listed above to simulate the execution of programs, but you can decide how much should be implemented in the queue class, and how much should be in the main program.

Finally, your must design and implement your own way to display the status of the CPU as the simulation executes. Keep in mind that you need to cut/paste the output into your project report, so interactive displays like "top" uses are probably not appropriate.

3. Implementation:

There is a sample implementation of a Queue class in lab8 that you are welcome to use as part of your solution. This queue stores and retrieves integers, so you will need to extend the queue to store other information.

As always, an incremental implementation is strongly advised. Start with one or two binary operations and make sure they work before going forward with the more complex operations. Once you have the basic program working, you can add the error checking you designed above into the program.

4. Testing:

Test your program to check that it operates correctly for all of the requirements listed above. Also check for the error handling capabilities of the code. Save your testing output in text files for submission on the program due date.

5. Documentation:

When you have completed your C++ program, write a detailed report describing what the objectives were, your design decisions, what you did, and the status of the program. Does it work properly for all test cases? Are there any known problems? Save this report in a separate text file to be submitted electronically.

6. Project Submission:

In this class, we will be using electronic project submission to make sure that all students hand their programming projects and labs on time, and to perform automatic analysis of all programs that are submitted. When you have completed the tasks above go to the class web site to "submit" your documentation, C++ program, and testing files.

The dates on your electronic submission will be used to verify that you met the due date above. All late projects will receive reduced credit (50% off if less than 24 hours late, no credit if more than 24 hours late), so hand in your best effort on the due date.

You should also PRINT a copy of these files and hand them into your teaching assistant in your next lab. Include a title page which has your name and uaid, and attach your hand written design notes from above.