CMSC 341 Spring 2006
Project 4

Objectives

• To use a priority queue in a simulation
• To learn about operating system scheduling
• To practice using code supplied by another programmer

Background

One problem with priority scheduling algorithms is known as "starvation". If new requests with high priority are continually added to the disk I/O queue a low priority request will wait for a very long time ("starve" for service). The method we will use to combat starvation is "aging" in which the priority of a request waiting for service is raised periodically. The longer the request waits, the higher its priority becomes until eventually it has the highest priority.

Description

A simulation is modeled using a for-loop. For our project, each iteration of the for-loop represents one second of time. The length of the simulation (in seconds) is given by a command line parameter. The aging interval (N) is also given by a command line parameter.

For each iteration of the for-loop, do the following in the order specified

1. Put any newly arrived disk I/O requests into the disk I/O queue.
2. Perform any necessary aging by raising (decrementing) a disk request's priority by 2.
3. "Execute" the top priority I/O request by removing it from the priority queue. If more than one request has the same priority, the request with the earliest arrival time should be used. If more than one request has the same priority and the same arrival time, the request with the smallest size should be used. If more than one request has the same priority, arrival time, and size, choose any of these.
4. If the request "executed" above is more than 50KB, place a "new" disk I/O request onto the priority queue for the remaining data (see below).

The arrival time of the "new" request should also be the same as the request for the 65KB transfer.

Note that (a) the highest possible priority is zero, and (b) aging occurs on a "per-request" basis (i.e. not all request are "aged" at the same time, but rather each request is aged every N seconds it has been waiting).

Your simulation should provide output for each of the following actions.

1. An I/O request was serviced. Your output must include the time the request was serviced, the length of time the request waited for service (service time - arrival time) and all details of the request.
2. A new I/O request was placed into the priority queue. Output the I/O request details.
3. Changing a requests priority ("aging" a request). Your output must include the old priority, the new priority, and the request details.
4. The simulation ends. Output the following information
   1. The number of I/O requests serviced.
   2. The average waiting time for all serviced requests (rounded to seconds).
   3. The details of all requests left unserviced in the disk I/O queue.

Disk I/O Request File

1. Process ID number (PID) - a positive integer
2. Arrival time - a non-negative integer that indicates the time (from the start of the simulation) at which the request should be inserted into the disk I/O queue.
3. File Name - a string with no spaces.
4. Request Type - a string which is either "READ" or "WRITE"
5. File Address - a non-negative integer representing the address in the file to/from which data is transferred.
6. Memory Address - a non-negative integer representing the address in memory to/from which data is transferred
7. Size - a positive integer representing the number of bytes to transfer
8. Priority - a non-negative integer

1. The file is well formed and contains no errors. No error-checking is required.
2. The file is sorted by arrival time, although multiple requests may have the same arrival time.
3. Blank lines may appear anywhere in the file and should be ignored.
4. Lines beginning with '#' are comments and should be ignored.

Other Notes and Requirements

• Mr. Frey's public directory for this project is /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj4
• The author's binary heap code is provided for you in Mr. Frey's public directory. You may modify it as necessary provided that it remains a generic template. It is not necessary to bring the author's code up to our coding standards.
• As noted above, your program will be invoked with command line parameters in this order
  1. The first command line parameter is the name of the disk I/O request file
  2. The second command line parameter is the duration of the simulations in seconds
  3. The third command line parameter is the interval at which aging should occur in seconds.
• Appropriate C++ design is expected.

Sample Output

Proj4 bob.dat 30 5

Starting Simulation
-----------------------
Duration: 30 seconds
Aging Interval: 5 seconds
Data File: bob.dat

Time	Action		Details
------  --------       	--------
   0	New Request	<request details here>
   0    Disk I/O 	Waited 0 seconds; <request details here>
   1	New Request	<request details here>
   1    New Request	<request details here>
   1    Disk I/O	Waited 1 second; <request details here>
   .......

  20    Aged Request	Old Pri: 40; New Pri: 30; <request details here>

End of Simulation
---------------------
Requests not serviced:
	<request details here>
	<request details here>
	<request details here>
		......
Average wait time for all requests serviced: 4 seconds

Files To Be Submitted

Be sure to submit the answers to the project questions (341-Spring06-p4_questions.txt found in Mr. Frey's public directory) in plain text format.

Submit the files using the procedure given to you for your section of the course.
If your makefile is set up correctly, you should be able to execute the command make submit.

Submission Tools
There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/ . One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example:  submitmake cs341 Proj4

This makes the project, and shows you the report from the make utility. It cleans up the directory after making the project (removes .o and ii_files), but leaves the
executable in place.

submitrun <class> <project>

Example:  submitrun cs341 Proj4 <parameter list>

This runs the project, assuming there is an executable (i.e. submitmake was run successfully).

Project grading is described in the Project Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.