代写OS中的内存换页算法，代码量虽不大，但是调试非常麻烦。
Aim
By doing this practical work, you will learn how to implement page replacement
algorithms, gain experience in creating and evaluating a simple simulator, and
develop your skills in scientific writing.
Introduction
In class, we have explored a variety of page replacement algorithms for
managing virtual memory.
In this practical, you will evaluate how real applications respond to a
variety of page replacement algorithms. Of course, modifying a real operating
system to use different page replacement algorithms is quite a technical mess,
so we will simulate it instead. You will extend a program that simulates the
behaviour of a memory system using a variety of page replacement algorithms.
Then, you will use memory traces from real applications to evaluate your
algorithms properly. A main outcome of your work will be a report. The report
itself counts for 60% of this assignment, so you should be sure to spend time
thinking about what to measure, and what the significance of your results are.
Memory Traces
We provide you with four large memory traces to use for your evaluation. Each
trace is a real recording of a running program, taken from the SPEC
benchmarks. Real traces are enormously big: billions and billions of memory
accesses. However, a relatively small trace will be more than enough to keep
you busy. Each trace only consists of one million memory accesses taken from
the beginning of each program. Each trace is compressed with gzip, so you will
have to uncompress it with a command like this:
> gunzip –d gcc.trace.gz
Each trace is a series of lines, each listing a hexadecimal memory address
followed by R or W to indicate a read or a write. For example, gcc.trace trace
starts like this:
0041f7a0 R
13f5e2c0 R
05e78900 R
004758a0 R
31348900 W
Simulator Requirements
Your job is to build a simulator that reads a memory trace and simulates the
action of a virtual memory system with a single level page table. Your
simulator should keep track of what pages are loaded into memory. As it
processes each memory event from the trace, it should check to see if the
corresponding page is loaded. If not, it should choose a page to remove from
memory. Of course, if the page to be replaced is dirty, it must be saved to
disk. Finally, the new page is to be loaded into memory from disk, and the
page table is updated. The current simulator fixes the pages and page frames
size to 4 KB (4096 bytes).
This is just a simulation of the page table, so you do not actually need to
read and write data from disk. When a simulated disk read or write must occur,
simply increment a counter to keep track of disk reads and writes,
respectively. You must implement three different page replacement algorithms.
rand replaces a page chosen completely at random. lru always replaces the
least-recently-used page. esc (enhanced second chance) performs the
replacement algorithm described in the textbook section 9.4.5.3.
- The simulator accepts 4 arguments as follows
- the name of the memory trace file to use.
- the number of page frames in the simulated memory.
- the page replacement algorithm to use : rand/lru/esc
- the mode to run: quiet/debug
If the mode is “debug”, the simulator prints out messages displaying the
details of each event in the trace. You may use any format for this output, it
is simply there to help you debug and test your code. If the mode is “quiet”,
then the simulator should run silently with no output until the very end, at
which point it prints out a summary like this:
total memory frames: 12
events in trace: 1002050
total disk reads: 1751
total disk writes: 932
page fault rate: 0.83
Your solution will be run as shown :java Memsim trace1 32 lru debug
In the tarfile provided there is a code skeleton called Memsim.java that reads
the parameters, processes the trace files and for each access it generates a
page read or write request. Your job is to implement the memory management
unit for each replacement policy. You should start thinking how you can keep
track of what pages are loaded, how to find if the page is resident or not,
and how to allocate frames to pages. Some short traces (trace1, trace2 and
trace3) are provided to facilitate testing of your code.
Alternatively, if you prefer to use the C language, there is an equivalent
skeleton of the simulator called memsim.c in the folder.
You simulator code should be saved in an svn directory, and submitted using
the web submission system, by the code deadline.
Report
An important component of this practical is a report describing and evaluating
your work. Your goal is run the simulator to learn as much as you can about
the four memory traces (swim, bzip, gcc and sixpack). For example, how much
memory does each traced program actually need? Which page replacement
algorithm works best when having a low number of frames? Does one algorithm
work best in all situations? What is the size of the working set?
Think carefully about how to run your simulator. Do not choose random input
values. Instead, explore the space of memory sizes intelligently in order to
learn as much as you can about the nature of each memory trace. Your report
should have the following sections:
- Introduction: A section that explains the essential problem of page replacement and briefly summarizes the structure and implementation of your simulator. Do not copy and paste text from this project description. Describe it using your own words.
- Methods: A description of the experiments that you performed. As it is impossible to run your simulator with all possible inputs, so you must think carefully about what measurements you need. Make sure to run your simulator with an excess of memory, a shortage of memory, and memory sizes close to what each process actually needs.
- Results: A description of the results obtained by running your experiments. Present and compare the performance of each algorithm on each memory trace using graphs that show the page fault rate over a range of available memory sizes. In the text, explain what each graph or table shows and point out any interesting or unusual data points.
- Conclusions: Describe what you have learned from the results.
Report length: use enough space to say what needs to be said; a one page
report is probably too short; a six page report is too long. Your report must
be well structured and free of typos and errors. Each group must submit a PDF
file by the due date.
