CMSC 341 Spring 2006
Project 4
Assigned
| Wednesday, April 19, 2006
|
Due
| 11:59pm, Tuesday, May 2, 2006
|
Updates
| Friday April 21, 2006
The data items in the disk I/O request file will be separated
by whitespace.
Thursday, April 20, 2006
See the note below about the arrival time of
disk I/O requests greater than 50KB.
|
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 of the primary responsibilities of an operating system is to schedule
the use of available resources such as the CPU, printers, network connections,
and disk drives. In this project you will implement
an operating system's disk I/O queue. You will then write a simulation program
to validate your implementation.
Since disk I/O requests are prioritized, a priority
queue is used to implement the disk I/O queue. As is typical, we will use smaller values to indicate higher priority.
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
For this simulation, disk I/O requests will be read from a file and
serviced according to their priority. Your program will output messages
to indicate the activity of the scheduling algorithm.
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
- Put any newly arrived disk I/O requests into the disk I/O queue.
- Perform any necessary aging by raising (decrementing) a disk request's
priority by 2.
- "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.
- 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).
For simulation purposes, we assume that the disk can transfer (a possibly
unrealistic) 50 KB per second. If a disk I/O request is for more than 50 KB,
then the request must be handle as if there were multiple requests.
For example, suppose PID 42 requests 65 KB be transferred from file myData.dat
address 10000 to memory address 5000. When this request
reaches the top of the priority queue, 50KB will be transferred and a "new"
request for the remaining 15KB from file myData.dat
address 10000 + 50K to memory
address 5000 + 50KB will be placed back on the priority queue.
The priority of the "new" request will be the same as the request for
the 65KB transfer.
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.
- 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.
- A new I/O request was placed into the priority queue.
Output the I/O request details.
- Changing a requests priority ("aging" a request).
Your output must include the old priority, the new priority,
and the request details.
- The simulation ends. Output the following information
- The number of I/O requests serviced.
- The average waiting time for all serviced requests (rounded to seconds).
- The details of all requests left unserviced in the disk I/O queue.
Disk I/O Request File
The disk I/O request file contains one disk I/O request per line.
A disk I/O requests consists of the following information in this order.
- Process ID number (PID) - a positive integer
- 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.
- File Name - a string with no spaces.
- Request Type - a string which is either "READ" or "WRITE"
- File Address - a non-negative integer representing the
address in the file to/from which data is transferred.
- Memory Address - a non-negative integer representing the
address in memory to/from which data is transferred
- Size - a positive integer representing the number of bytes to transfer
- Priority - a non-negative integer
You may assume the following about the file
- The file is well formed and contains no errors. No error-checking is required.
- The file is sorted by arrival time, although multiple requests
may have the same arrival time.
- Blank lines may appear anywhere in the file and should be ignored.
- 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
- The first command line parameter is the name of the disk I/O request file
- The second command line parameter is the duration of the simulations in seconds
- The third command line parameter is the interval at which aging should occur in seconds.
- Appropriate C++ design is expected.
Sample Output
This sample output is provided as an example format only.
It is not the result of running any executable and may be inconsistent with itself.
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
Submit any files which you have written or modified -- source code and makefile.
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.