| COP4610: Operating Systems & Concurrent Programming | up ↑ |
See course calendar.
You are to modify a given virtual memory simulation program. The simulator currently implements a very simple set of policies for virtual memory management (paging). Your modifications will implement a new set of paging/virtual memory management policies, which I hope will be more sophisticated and perform better than those currently implemented.
This scope of this assignment has been reduced from the preliminary draft that I posted earlier. Because of the difficulties some students seemed to have completing the last assignment on time, you are being provided with a simulation program that already includes the memory management and disk subsystems, and only asked to make changes to the memory management portion.
In the earlier version, you were asked to do much more: implement and compare two different sets of policies; implement the disk and memory management subsystems from scratch; make more changes to the process management subsystem; write all the code to keep statistics and output a report. I hope that having a more complete framework and being required to write and debug less code will reduce the amount of effort required, while retaining the educational benefits with respect to virtual memory systems and performance analysis. In a prior on-campus offering of this course all the students managed to complete the originally-scoped project. So, after this reduction in scope there is no reason you should not all be able to complete it on time, if you get started on time. However, please do not underestimate the time it will take to do this project. Because I am providing so much code, you will need to spend more time reading code, which will partially offset the time saved by having less code to write and debug. There will be no time extensions.
We have also switched from the C programming language to C++, in response the apparent preference of the majority of students for working in C++, and relaxed the requirement of prior assignments that the code be portable across Linux and SunOS.
This is a fairly large program. I have done some testing of the provided code, on Darwin, Linux, and SunOS. It passed the tests, but along the way I found quite a few bugs, so it would not be at all surprising if you find a few more. If you find apparent bugs, please report them via the thread "Bugs in provided code" on the Blackboard forum for P5.
The provided code is accessible in two ways this time:
You are not required to learn to use git for this course. However, one student has requested this option, so I am providing it. If you are able to use git you will have a simpler time of incorporating any bug-fixes that we may need to make in the provided code. You will also find it helpful as a configuration-management and back-up tool.
Fetch a copy of ~baker/opsys/assign/P5/P5.tgz and extract the files into a working directory.
Read the README file, as well as the POLICIES, and PARAMETERS files. As explained in the README file the other files comprise a bare-bones simulator written in C++, similar to but more advanced than the one you have been working with for assignments P1-P3 (which was in the C language). The POLICIES file describes than changes you are to make to the program, and the PARAMETERS file describes the existing command-line parameters.
As the POLICIES file explains in more detail, you should choose a set of paging policies, summarized as follows:
Document your choice of policies, by creating a new version of the file POLICIES, that describes clearly the policies that you intend to implement, and keep this up to date as the project evolves.
Modify the code to implement a simulation of your chosen policies, according to the instructions below, in the README file, and the comments in the provided code.
Test and debug your simulation, for Linux. (You are not required to verify that it also run on SunOS for this assignment.)
Experiment with your simulation, comparing the reported performance results against those of the provided version. See if you can obtain better performance by one or more of the summary measures, such as such as lower average page fault frequency, lower idle processor time, shorter average completion time, shorter average waiting time, and shorter overall completion time of the simulation. You may play with the provided parameters to check whether these improvements depend on them.
Write up a report of the results of the step above, and include it in the README file.
Turn in the files that you added or modified, using make deliverables and the submitP5.sh script in the directory you chose to work from. Note this change from previous assignments. Since you may be adding files of your own, you are required to update the Makefile so that it produces a file P5_deliverables.tgz containing the files that you have modified. submitP5.sh will look for a file by that name and submit it.
Inputs and Command Line Arguments: Your program will not have any input files. It will use command-line arguments to specify important parameters, and it will use the interface defined in the file random.h to obtain randomly generated process inter-arrival times, execution times, and page references.
It should be possible for me to modify the implementation of this interface and test your code with different page reference sequences. An example of how this will be done is provided in the code files random_process_1.cc and random_process_2.cc, which the Makefile uses to build program versions sim1 and sim1.
Your program should make use of use the command-line parameters described in the file PARAMETERS in the same way as the provided bare-bones framework. You may add additional parameters, and should document them by updating the file PARAMETERS.
Output: Your program should simulate the execution of the input page reference sequence for the given set of processes, applying one of the two sets of policies you chose. There is a function already provided that will print out a summary report at the end of the simulation. You should not add any code that sends output to stdout. However, it is essential that as you make changes you take care to maintain any statistics that are used to produce the report. I have tried to "rope off" that code, but there remain a few places where you will need to take care.
The program should normally produce only the final report. If you have any execution tracing information (which is useful for debugging) it should go to stderr. All debugging output should be suppressed by default, and only appear if you use the command-line parameters to set the debugging level higher than zero or set one or more of the alphabetic debugging flags described in the file PARAMETERS.
Assumptions: Assume the system has a virtual address space of the size specified by Memory_Model::vmem_pages and a physical memory of the size specified by Memory_Model::real_pages. For simplicity, the simulation deals in whole pages, ignoring the specific addresses within pages, and the size of individual pages. These can be modified by command-line parameters as described in the file PARAMETERS.
The simulation assumes there is only one disk drive, which is simulated by the object Disk1 of class Disk, and that it takes Disk::disk_access_time units of time to read a page from the disk and and equal amount of time to write a page to the disk. This can be modified by command-line parameter as described in the file PARAMETERS.
If there are other assumptions you feel you need to make, either ask me or decide for yourself, but be sure that you document your decision in block comments at the beginning of the main program source file.
Debugging Hints: You will probably encounter segmentation fault and bus error messages when you are working on this program. Those are the error messages Unix typically gives you when you have made an error that causes the program to try to use a bad pointer value or a bad array index value. The easiest way to isolate and correct such errors is using an interactive debugger. There are on-line notes for notes on using gdb to find out where your program dies. Since this program is not multi-threaded you should not run into any special problems.
Take advantage of the debugging machinery already provided in the program, which is controlled by the -debug= and -debug_flags= command-line parameters. Feel free to add your own tracing code, following the same model, and to use other unused debug-flag letters.
Overview of Operation:
Processing a Page Reference Event
The memory manager needs to perform the following for each page reference, as illustrated in the existing code:
Simulating a Disk I/O Request:
The existing code does the following for each disk request:
The disk I/O scheduler does the following:
Processing a Disk Completion Event
Existing Queues:
The simulation already has the following queues, which you will not modify:
To understand the debugging trace output, it helps to know what will normally be in the event queue:
(Yes, that means you should have at most 3 events in the queue at any one time.)
Observe that there is a handy-dandy function that prints the event queue contents, for debugging, and this can be activated by appropriate choice of debugging flags..
Virtual memory and paging systems, including the various policies, are described in Chapter 9 of your text. This should be your starting point and principal reference for this assignment.
Chapter 10 discusses disk storage systems. You should have read it before working on this assignment. However, you will not need much information from there since we are greatly simplifying the disk aspect of the simulation (not taking into account details like location of data on the disk, seek time, rotational latency, caching, etc.)
An introduction to discrete event simulation was given earlier in the term, as part of programming assignment P1. See also the my supplemental notes on discrete event simulation.
As explained above, you are to use the provided code starting point. Read the code and understand the parts you intend to modify, as well as how the fit into the bigger picture, before start the modifications.
Use the submitP5.sh script. As explained above, for this assignment you will need to modify the code in the Makefile for target deliverables so that it creates a file P5_deliverables.tgz containing the files that you have written or modified.
As usual, the the section on Grading Criteria for Programming Assignments in the Study Guide will apply
For this assignment, your program will be evaluated primarily on the correctness of the implementation of the policies you specify. It will also be evaluated on the quality of the code, including the usual criteria, such as clarity, conciseness, efficiency, and internal documentation.
| Criterion | Points |
| Correct implementation of an effective replacement policy, different from the existing FIFO one, with clear explanation in file POLICIES. | 25 |
| Correct implementation of an effective dynamic resident set management policy, different from the existing fixed allocation policy, with clear explanation in file POLICIES. | 25 |
| Correct implementation of an effective dynamic load control policy, in place of the existing fixed multi-programming level, with clear explanation in file POLICIES. | 25 |
| Report of performance experiments, in file README, noting differences against the provided baseline policies in term of performance measures such as average page fault frequency, idle processor time, average completion time, average waiting time, and overall completion time of the simulation. Do your best to explain the observed differences. Score will reflect both the quality of the explanation and the quality of the results. | 20 |
| Appropriate comments and coding style | 5 |
As usual, points may be deducted from any or all of the above, even if a program passes functional tests, if there are defects visible upon examination of the code.
Submissions that come in past the deadline will have 5 points deducted for each day they are late. No submissions will be accepted after grading has started.
| T. P. Baker. |