PROJECT 3 - VIRTUAL MEMORY

PROJECT 3 - VIRTUAL MEMORY CS 2200 - SYSTEMS AND NETWORKS 
Introduction
In this project, you will be implementing a virtual memory system. You will be given a simulator that manages memory models, is missing some critical components. We will guide you through the implementation
of each of the missing components step-by-step.
Note: In the past we have caught many students for academic violations in the projects involving C
programming. It is easy to copy code from multiple sources. Don’t. Please adhere to the Georgia Tech
Honor Code. Make use of office hours if you are having trouble with understanding concepts or writing
code.
This assignment has six steps:
1. Split the Address [10 points]
2. Translate the Address [20 points]
3. Compute the EMAT [10 points]
4. Handle Page Faults [20 points]
5. Improve Page Replacement [20 points]
6. Add a TLB [20 points]
Each part starts with some theoretical questions. You do not have to submit answers to these questions, as
they are only there to help guide you along. If you are able to answer the questions without much trouble,
you will have an easy time with the code. If you have trouble with the questions, then we strongly suggest
that you take the time to read about the material in the book and/or visit office hours and then answer the
questions.
Once you are able to answer questions about a given concept, we will ask you to implement that concept.
For each section, the given concept is described briefly, and there will be FIXME sections labeled in the
code with greater elaboration as needed. The files you have to fill out for this assignment are located in the
student-src folder. The simulator code can be found in the simulator-src folder. You should not need to
look at any of the simulator code. However, please see Appendix A - The Simulator for more details about
what is in the simulator. It may be useful if you are having trouble figuring out what do to.
Compiling and Running
To recompile the simulator, we have provided you with a Makefile in the top-level directory. You can type
in the command make in the terminal to build the project. When the project is finished building, there will
be an executable in the top level directory called vm-sim. To execute this file, you must provide it with a
references file. Reference files are found in references folder, and it provides four types of reference files:
• basic - A basic reference file that yields no page faults due to eviction.
• eviction - A reference file that should produce a large number of page faults.
• tlb - A reference file that should cause a large number of TLB hits.
• everything - A reference file that provides a bit of everything described above.
For example, if we wanted to run the simulator with the basic file, we would do the following:
$: ./vm-sim references/basic
1
PROJECT 3 - VIRTUAL MEMORY CS 2200 - SYSTEMS AND NETWORKS Spring 2016
There are several other command line options for the simulator that you can play around with, such as
changing the memory size, page size, and the tlb size. The default settings are memory size = 16, page size
= 2, and tlb size = 4. You can change these parameters to see how they affect the memory access time. To
view these options, type:
$: ./vm-sim -h
Step 1 - Split the Address
In modern operating systems, user programs access memory using virtual addresses. The hardware and the
operating system work together to turn this number into a physical address, which can be used to address
into physical memory. The first step of this process is to translate the virtual address into a physical address.
Note that a virtual address consists of two parts: the higher order bits form the Virtual Page Number (VPN),
and the lower order bits form the offset.
Conceptual Questions
On a certain machine, virtual addresses are made up of 16 bits. Each page on this machine has 2
8 addressable locations. Now, answer the following questions:
1. How many bits should the offset be?
2. Recall that the virtual address is split into the Virtual Page Number and the offset. How many bits is
the Virtual Page Number?
3. What is the Virtual Page Number of the virtual address 0xBEEF?
4. What is the offset, given the virtual address 0xBEEF?
Implementation
Look at the file page-splitting.h. You should find two macros that are used by the simulator to split the
address. They are called VADDR PAGENUM and VADDR OFFSET. These macros take a virtual address
and return the page number or offset, respectively. Fix these so that they return the proper VPN and offset.
Here’s a hint: Use the global variable page size to access the size of a page.
Step 2 - Address Translation
Now that we can split the address, we can transform the virtual address into a physical address. This
requires a page table to store the mapping between virtual addresses and physical addresses. In the simulator, a page table is represented as an array filled with the following structure:
typedef struct {
pfn t pfn; /* Physical Frame Number */
unsigned char valid; /* Valid ’bit’ */
unsigned char dirty; /* Dirty ’bit’ */
unsigned char used; /* Used ’bit; */
} pte t;
Notice that the VPN does not appear as part of the page table entry. You will index into the array of the
page table entries using the VPN.
2
PROJECT 3 - VIRTUAL MEMORY CS 2200 - SYSTEMS AND NETWORKS Spring 2016
Conceptual Questions
Most of the address translation deals with reading values from the page table. The table below is similar
to a pte t array that is used in the simulator, although we have reduced the size of the VPN and the PFN
(Physical Frame Number) to simplify the table below. Assume that the page size is the same page size you
determined in the previous part. Assume that any VPNs that do not appear in the table are invalid.
Table 1: Page Table
VPN PFN Valid Dirty Used
0xDE 0xBE YES NO NO
0xF0 0xD0 YES YES YES
0xBE 0x42 YES NO NO
0x42 0x43 NO NO NO
— — NO NO NO
1. What physical address is virtual address 0xDEAD mapped to?
2. What physical address is virtual address 0xF00D mapped to?
3. Is the virtual address 0x42ED valid?
Implementation
After finishing the questions in the previous section, you should have a pretty good idea about how the page
table is used when translating the virtual address into a physical address. Open up the file page-lookup.c.
In this file, you have to modify the function pagetable lookup function. Make sure that you are checking
if the page table entry is valid! If the page table entry is not valid, then you must increment the global
variable count pagefaults and call the pagefault handler function. Keep in mind that the global variable
current pagetable is a pointer to an array of pte t entries, which can be indexed by the VPN. Here is a
hint:
• You do not need to worry about checking the TLB first. This is done for you by the simulator.
• Note that in the questions, you were asked to find the physical address. In the function, you simply
need to find the Physical Frame Number - these are slightly different values!
Step 3 - Computing the EMAT
This section is not necessary for basic operations of the Virtual Memory simulator. Al though labelled
Step 3, I suggest you finish Step 4 before you attempt this section.
Now that we are getting some results from the simulator, we are ready to analyze the output. In this
part, you will complete a function that calculates the Estimated Memory Access Time, or EMAT. This is
computed by calculating the average amount of time it takes for a memory access. Keep in mind that this
metric is influenced by what memory access patterns are processed by your code.
Conceptual Questions
1. Assuming a memory access time of 100 ns, an average disk access time of 10 ms, how long would it
take to access memory ten times if two of those accesses resulted in page faults (these require disk
access to resolve!) and four of the accesses resulted in TLB misses? Remember that accessing the page
table requires two memory accesses.
3
PROJECT 3 - VIRTUAL MEMORY CS 2200 - SYSTEMS AND NETWORKS Spring 2016
2. While accounting for two memory access times for a TLB miss, one memory access for a TLB hit, and
two memory accesses and a disk access for a page fault, what would be the generalized formula for
the average time taken per memory access?
Implementation
Calculating the EMAT by hand every time you run the simulator is quite tedious. Since it is generally
better to make the computer do these kinds of computations for us, this step of the project asks you to fix
the function compute emat found in emat.c. This fucntion takes no parameters, but it has access to the
global statistics matained in statistics.h. Namely, it has access to:
• count pagefaults - The number of page faults that occured.
• count tlbhits - The number of TLB hits that occured.
• count writes - The number of stores and writes that occured.
• count reads - The number of loads and reads that occured.
In your computation, you should utilize the constant values DISK ACCESS TIME and MEMORY ACCESS TIME
which are defined in emat.c. For the purposes of this function, treat a TLB hit as taking no time when
looking up the VPN in the page table.
Step 4 - Handling Page Faults
When the CPU encounters an invalid address in the page table, the OS allocates a page frame for the
requested page by either locating a free frame or by evicting a physical frame that is already in use. After
this occurs, the OS updates the page table to reflect the new mapping, and then continues with the memory
access.
However, what causes page faults to occur? When a program is initially started, none of the virtual addresses are valid. When a given address is used for the first time, the OS will allocate a physical frame to
store the appropriate information. After this occurs for a while, the OS might run out of physical frames to
allocate! In this situation, the page fault handler will have to evict a physical frame. When it does this, it
moves the information stored there to the hard disk and allocates the evicted page to the new process.
Conceptual Questions
1. If a page fault occurs and there is an invalid frame in the physical memory, should you choose to evict
a frame? When would such a situation occur?
2. What is thrashing? How would a virtual memory system try to subvert this phenomenon?
Implementation
Look in page-fault.c to view the partially implemented page fault handler. Follow the comments detailed
in the source file. While working on this part, keep in mind that each process has its own page table. The
data structure current pagetable refers to the page table of the currently running process (which is the
one that is requesting a new page). The page table of the process that owns the victim page can be found in
the victim process control block victim pcb.
4
PROJECT 3 - VIRTUAL MEMORY CS 2200 - SYSTEMS AND NETWORKS Spring 2016
Step 5 - Improving Page Replacement
Up to this point we have not concerned ourselves with what happesn when we have to make more pages
than we have room for in our physical memory. In reality, the virtual memory system uses the hard drive
to make it seem like there is more memory than there really is. Indeed, it is quite slow to load processes
in and out of the disk, however if our page replacement algorithm is performed in an intelligent manner it
will be much more effective than to simply stop the user’s process during execution.
The virtual memory system you have constructed so far uses a randomized page replacement algorithm
that we have provided. You will be implementing a more intelligent system. We will ask you to implement
a page replacement algorithm and observe its effects on the EMAT.
The optimal page replacement algorithm is one that can tell the future! Out of all the physical frames in
memory, our algorithm should evict the page that will not be used for the longest time from when the page
fault happens. Unfortunately, there is no “magical soothsayer” that will allow us to gleam into what is to
pass. However, you will be implementing the Clock-Sweep Algorithm, which takes advantage of temporal
locality in that it assumes that pages that were recently accessed will be used again in the near future. While
this algorithm is not optimal, it is relatively easy to implement and achieves decent performance in practice.
The basic idea of the Clock-Sweep Algorithm is that you first mark a page as “used” whenever it is accessed
or used. When you need to evict a page, you will iterate (Sweep) through the page table, examining each
frame’s “used” bit. If a page is marked “used”, you mark it as “unused”. When you encounter a page that
is not “used” you will select this page to evict. Should you ever reach the end of memory, you should wrap
around and start over at the beginning of the page table array. This means that if all pages are marked as
“used”, the algorithm will unmark all the pages and choose the first page you examined when you iterated
through the page table array Normally, the clock-sweep algorithm remembers the page it left off on, so
that the next time it executes, it continues on from there. Note that for this assignment, you do not have to
implement this feature. If you do, you get brownie (read: not extra credit) points.
Fun fact: Linux developers sometimes refer to the Clock-Sweep Algorithm as the “Second Change Algorithm” because it gives each page that has been used recently a second chance at not being evicted.
Conceptual Questions
Answer the following questions about page replacement, given the following page table. Assume that any
entry not listed is VALID and USED.
Table 2: Page Table
VPN PFN Valid Dirty Used
0xDE 0xBE YES NO YES
0xF0 0xD0 YES YES YES
0xBE 0x42 YES NO NO
0xBC 0x43 YES NO NO
0x42 0xAB YES NO YES
0x21 0x23 NO NO NO
— — YES NO YES
1. What is the first page that should be used when we need to allocate a new page?
2. Assuming that we are now using the page we selected from the previous question and no other pages
have been marked as “used” since then, what is the next page we will select?
3. Again, assuming we are using the pages selected in the previous two questions and that no pages
have been marked as used since then, which page is selected?
5
PROJECT 3 - VIRTUAL MEMORY CS 2200 - SYSTEMS AND NETWORKS Spring 2016
Implementation
Now that you understand how page replacement is supposed to work, open page-replacement.c and
change the replacement algorithm to more intelligently evict pages. Your code should be doing two things:
first, check to see if there is an uninitialized frame. If so, just use that one!(already implemented) If there
are no invalid pages, then perform a Clock-Sweep Algorithm to decide which page you should evict.
Step 6 - Adding a TLB
By now, you might have noticed that accessing memory is very slow. Virtual memory does not help to
curtail this problem, and instead adds to it! In our implementation, we must go to memory twice - once
to translate the virtual address to the physical address and again to access the memory at the translated
location. Virtual memory may even cause us to load in a page from the disk! These costs are unacceptable
for smaller programs that do not take advantage of the virtual memory system.
We cannot eliminate the actual memory access, but we can diminish the page table lookup by adding a
small piece of hardware that keeps a small buffer of past VPN to PFN translations. If we locate a VPN in
this buffer, we can bypass the page table lookup in memory entirely - a great boon! We call this buffer the
Translation Lookaside Buffer. It will provide us an alternative means of performing the lookup during VPN
to PFN translation.
Conceptual Questions
The structure of the TLB is remarkably similar to that of the page table. The biggest difference is the fact
that unlike in the page table, where we use the VPN as an index to an array, the VPN is simply another
entry in the TLB. Note that the TLB is relatively small, and cannot hold many entries. Use the TLB shown
below to answer the questions. This TLB is only capable of holding four entries. Assume that any entry not
explictily present in the page table is invalid.
Table 3: TLB
VPN PFN Valid Dirty Used
0xDE 0xBE YES NO YES
0xF0 0xD0 YES YES YES
0x42 0xAB YES NO YES
0x21 0x23 YES NO NO
1. What address does the virtual address 0xDEAD translate to? Is this translation found in the TLB or
in the Page Table?
2. What address does the virtual address 0xBE21 translate to? Is this translation found in the TLB or the
page table?
3. When we lookup the address 0xBC87, we miss the TLB. This requires us to evict an entry from the
TLB. Which entry would we pick to evict, assuming we use a standard Clock-Sweep Algorithm?
Implementation
Open the tlb-lookup.c file and follow the comments describing what neeeds to be fixed. You may want to
note that you have access to the TLB entries via the tlb array, which is an array of type tlbe t structs and
whose length is tlb size entries. Keep in mind that since there is no relationship between the index in the
TLB and the content stored there, you will have to check every valid entry in the TLB before deciding that
you are unable to find an entry. The structure of each entry is given below:
6
PROJECT 3 - VIRTUAL MEMORY CS 2200 - SYSTEMS AND NETWORKS Spring 2016
typedef struct {
vpn t vpn; /* Virtual Page Number */
pfn t pfn; /* Physical Frame Number */
uint8 t valid; /* Valid ‘bit’ */
uint8 t dirty; /* Dirty ‘bit’ */
uint8 t used; /* Used (recently accessed) ‘bit’ */
} tlbe t;
Deliverables
When you are done with the project, move to the top level directory of your project and run the following:
$: make submit
This will generate a file called p3-submit.tar.gz that contains everything you need to submit for this assignment. Please remember to submit this file on T-Square!
Don’t forget to sign up for a demo slot! We will announce when these
are available. Failure to demo results in a 0!
Precaution: You should always re-download your assignment from TSquare after submitting to ensure that all necessary files were properly
uploaded.
7
PROJECT 3 - VIRTUAL MEMORY CS 2200 - SYSTEMS AND NETWORKS Spring 2016
Appendix A - The Simulator
This section is meant to serve as a reference to the simulator code. Use it if you are interested in knowing
about how the simulator works, or you need to figure out how to use something.
Simulator Files
Simulator files are located in the simulator-src directory. You should not have to modify any of these files.
If you need to look at any of the simulator code, you should really only look at the header files. To help you
understand how the simulator is organised, examine the following list:
• global.h - Provides a definition of three globally accessible values: page size, mem size, and tlb size
• memory.h - Simulates the physical memory found in a computer.
• pagetable.h - Provides an implementation of a page table. You will probably be most interested in
pagetable lookup, which you have to write, and get free frame, which will help you implement the
page fault handler. The struct pte t represents a single page table entry. If you need to get the page
table of the currently executing process, the variable current pagetable will point to the appropriate
array.
• process.h - Provides an implementation for a Process Control Block, as well as various methods for
manipualting processes. You probably won’t need anything in the PCB.
• sim.c - This file includes the main function for the simulator and serves as an entry point into the rest
of the code.
• statistics.h - This file is used to gather and display statistics.
• swapfile.h - Simulates moving and loading pages to and from the disk
• tlb.h - Provides an implementation of the TLB.
• types.h - Provides useful typedefs that allows us to refer to more descriptive types such as vpn t
instead of just int.
• useful.h - Provides useful macros.
8