Programming Project: Virtual Memory Solution

$30.00 $24.90

Description

Overview

In this project you will be implementing a virtual memory system. You will be given a simulator that is missing some critical components. In each of the four parts of this assignment, you will implement one of the missing components, and the simulator will be complete once you are finished. The parts are:

  1. Split the Address

  1. Translate the Address

  1. Handle Page Faults

  1. Improve the Page Replacement Algorithm

At the beginning of each part, you will be asked some questions to consider. You do not have to turn in your answers to these questions. They are just there to guide your thought process and give you a check on your understanding before you start implementing it. If you struggle with these questions, you should review the course material and/or visit office hours so that you can understand how to answer these questions before you begin coding.

You will be modifying the pagetable.cpp and pagefault_handler.cpp files in this assignment. As with earlier assignments, the submission script will turn in only these two files and the Makefile; if you modify any other provided files, those modifications will not be submitted. (Modifying the Makefile is allowed, but not required or necessary.) Some TODO comments have been added to these files to indicate the things you’ll need to do. (TODO comments are very useful in programs! However, be sure to remove TODO comments once you have done them. Your completed submission should not have an “TODO”s.)

The simulator code is written in C, but the code you write may be in C or C++. The entire thing will be compiled with the g++ compiler on cs1.seattleu.edu (unless you modify the Makefile to do differently), so it will accept C++ syntax.

To copy the starter code for the assignment to your current directory, run this command:

cp -r /home/fac/lillethd/cpsc3500/projects/virtual_memory/* ./

(Note the addition of the -r flag compared to earlier assignments. This is to be sure you also copy the subdirectory, which would not get copied with the “recursive” -r flag.)

Compiling and Running

To compile this assignment with the Makefile, just run:

make

To recompile, you can just run that command again. However, if things get weird (for example, if you get strange liner errors), you can try forcing a complete rebuild of all the source code with:

make clean all

The program file generated will be named vm-sim. It takes the name of a memory trace file as an argument, and a few such files are provided for you in the workloads/ directory. For example, to run the simulator with the basic trace file, run:

./vm-sim workloads/basic

The provided trace files are:

  • basic A basic workload that causes no page faults due to eviction (but pages still fault the first time they are accessed, of course!)

  • eviction A workload that causes a lot of evictions and should have many page faults

  • tlb A workload that would cause a lot of TLB hits (except the TLB is not currently implemented in the simulator, so it’s just another generic case for now)

  • everything A workload that provides a bit of everything for a more exhaustive test

There are also several optional command line options that you can play around with, such as changing the memory size and the page size. The defaults are memory size = 16 and page size = 2. To view these options, type:

./vm-sim -h

Part 1 – Split the Address

The virtual address consists of the Virtual Page Number (VPN) and the Offset. You’ll need to separate the virtual address into these two parts. You’ll also need to create a physical address using the Physical Frame Number (PFN) and the Offset.

Conceptual Questions

Consider a machine with the following properties:

  • virtual address size = 16 bits

  • page size = 28 = 256 Bytes (assume memory is byte-addressable)

Answer the following questions, given those properties:

  1. How many bits should the offset be?

  1. How many bits is the Virtual Page Number (VPN)?

  1. What is the Virtual Page Number (VPN) of the virtual address 0xCAFE?

  1. What is the offset, given the virtual address 0xCAFE?

Implementation

Look at the file pagetable.cpp. You will see two functions that split a virtual address and one more that creates a physical address from its components. These functions are:

  • get_vpn

  • get_offset

  • create_paddr

Your job is to fill in the implementations of these three functions. You will want to take advantage of the global variable page_size that the simulator will set to the page size for you (but be sure to only read it – modifying this value could break the simulation!)

Recall the bitwise operators & (bitwise and), | (bitwise or), ^ (bitwise xor), ~ (bitwise not), and the bit shift operators << (left shift) and >> (right shift). You can use a subset of these operators to implement the solution (you won’t need all of them), but you do not have to. The “get” functions can be implemented using only / (integer division) and % (modulo), and the “create” function can be implemented using only * (integer multiplication) and + (integer addition). Either approach to implementing these is perfectly fine for this assignment!

If you want more information about bitwise operators, the Wikipedia article is decent:

https://en.wikipedia.org/wiki/Bitwise_operation

You may also notice that some new types have been introduced here. These types are defined in types.h and help us keep track of which type of thing (a VPN, a PFN, a physical address, a virtual address, etc.) each of our variables is. You will be using the following types, all of which are implemented at 16-bit unsigned integers (although not all 16 bits are actually needed for all of them).

  • vaddr_t a virtual address

  • paddr_t a physical address

  • vpn_t a Virtual Page Number (VPN)

  • pfn_t a Physical Frame Number (PFN)

  • offset_t an offset into a page

Part 2 – Address Translation

The next part is to implement the translate function that takes a virtual address and returns a physical address. (Note that on a real computer, this would be done by the hardware, not the operating system, but we will use software to simulate it.)

Conceptual Questions

Given the following page table:

VPN

PFN

valid

dirty

used

0xDE

0xBE

1 (yes)

0 (no)

0 (no)

0xF0

0xD0

1

1

1

0xBE

0x42

1

0

0

0x42

0x43

0

0

0

0

0

0

Answer the following questions:

  1. What physical address is the virtual address 0xDEAD mapped to?

  1. What physical address is the virtual address 0xF00D mapped to?

  1. Is the virtual address 0x42ED valid?

Implementation

The page table in the simulation is implemented as an array of page table entries. The structure for a page table entry may be found in pagetable.h and is as follows:

typedef struct {

pfn_t pfn;

unsigned char valid;

unsigned char dirty;

unsigned char used;

}

pfn is the Physical Frame Number stored in an entry, and the three bit-flags are represented by unsigned chars that will be assigned either 1 or 0 (other values will not be used).

The Page Table Base Register (PTBR) is represented by the global variable:

pte_t* ptbr;

and it stores page table (array of pte_t) for the currently running process (which is the one generating virtual addresses for translation). The program simulates multiple processes and any time it performs a context switch and dispatches a new process, it will update the ptbr to point to the new current process. You don’t have to do this; it is handled for you, but you should know that the value of ptbr (and therefore the page table it points to) may be different from one call to translate to the next.

Now you can find the translate function in pagetable.cpp and finish the implementation, as instructed by the TODO comment. Remember to check if the page table entry is valid! If it is not, then you’ve found a page fault and should raise a page fault exception (which we will simulate by simply calling the pagefault_handler function).

Part 3 – Handling Page Faults

In the previous step, the “hardware” (simulated by your translate function) raised an exception that calls the page fault handler if it found a page that is not in memory (indicated by an invalid page table entry). However, the page fault handler is incomplete! Now it’s time to move up into the (simulated) operating system code and implement the pagefault_handler function.

Conceptual Questions

  1. If a page fault occurs and there is a free frame in the physical memory, should you choose to evict a frame? When would such a situation occur?

  1. What is thrashing? How would a virtual memory system try to subvert this phenomenon?

Implementation

The pagefault_handler function may be found in pagefault_handler.cpp, and the TODO comment there will help you out a little. The get_free_frame function will find a frame for you to use – it will return the PFN for a free frame, if there is one, and otherwise will choose victim frame to be evicted and return its PFN. (But it only chooses the victim; it does not actually evict it – that is your responsibility, in the page fault handler!)

Also remember that multiple processes are being simulated, so the victim page may not belong to the currently running process! The page table for the currently running process is pointed to by the ptbr. To find the victim page’s owning process (and page table), you need to use the frame table that is stored in the frametable global variable. (Some of this code is provided, but let’s review it anyway…) Each entry in the frame table represents one frame of physical memory and stores the process control block (PCB) of the process using that frame and VPN of that process’s virtual memory that is stored there. The definitions for the frame table and PCB are found in process.h:

typedef struct {

pcb_t* pcb;

vpn_t vpn;

} fte_t;

fte_t* frametable; /* array of frame table entries */

The structure of the PCB is as follows. So you can get the PCB from the frame table, and then get the page table for that process from its PCB.

typedef struct {

unsigned int pid;

char name[20];

pte_t* pagetable;

} pcb_t;

Finally, you will need to save page data to disk, and load page data from disk into memory frames. The file on disk where pages are stored is referred to as the swap file. The simulator provides a swap file module for you, with two functions that you can call to access the swap file; both are declared in swapfile.h:

void save_page_to_disk (pfn_t pfn, vpn_t vpn, int pid);

  • pfn indicates the data to be saved by indicating the frame containing that data

  • pid indicates the process that the page in that frame belongs to

  • vpn indicates the page of that process’s memory that is in that frame

  • (the pid & vpn identify the saved page so that we are able to specify which page we want to load from disk later)

void load_page_from_disk (pfn_t pfn, vpn_t vpn, int pid);

  • pid indicates the process owning the page that we want to load

  • vpn indicates which page belonging to that process that we want to load

  • pfn indicates which frame in memory we want to load the page data into

You may also need to review your code to make sure the “dirty” bit is being set on pages at the appropriate time, so you know whether you need to save the page or not. (Also remember to set and clear the “valid” bits on pages at the appropriate times.)

Part 4 – Improving Page Replacement

The get_free_frame function implements the page replacement policy by choosing a victim page in memory (unless there is a free frame that it can return instead). However, the current page replacement policy is the “random” policy – not a very good one! In this assignment, you will modify the page replacement policy by implementing the Clock-Sweep Algorithm (also known as the “Second Chance Algorithm”).

In the Clock-Sweep Algorithm, a page is marked as “used” any time it is accessed. When you need to evict a page, you will “sweep” (iterate) through the frame table and check each page’s “used” bit. If the page has the “used” bit set, then just clear the “used” bit and move on to the next entry. However, if you find a page whose “used” bit is clear, then choose that page as the victim. If you reach the end of memory before you find a victim, then just wrap around to the beginning and start over. (So if all the pages are marked as “used” then you will iterate through and clear all of them on the first “sweep”, and then find that the first page is clear after it wraps around, so then you’d choose that page as the victim.) Although the Clock-Sweep Algorithm normally remembers where it left off when it chose the previous victim and continues from there, for this assignment, you may just start from the beginning of memory (i.e., the first frame) each time you run the algorithm.

Conceptual Question

Given the following frame table (which has been condensed to show the page table entries of the pages stored in the frames):

PFN

VPN

valid

dirty

used

0xBE

0xDE

1

0

1

0xD0

0xF0

1

1

1

0x42

0xBE

1

0

0

0x43

0xBC

1

0

0

0xAB

0x42

1

0

1

0x23

0x21

0

0

0

0xC0

0xFE

1

0

1

Answer the following questions:

  1. What is the first page that should be used when we need to allocate a new page?

  1. Assuming we are now using the page that we selected from the previous question, and no other pages have been marked “used” since then, what is the next page we will select?

  1. Again, assuming we are using the pages selected in the previous two questions and that no pages have been marked “used” since then, which page is selected next?

Implementation

Now that you understand how the algorithm works, find the get_free_frame function in pagefault_handler.cpp and change the replacement policy to follow the Clock-Sweep Algorithm. Be sure keep the code that first checks if there is a free frame – we only want to choose a victim if there is no free frame!

Submission

On cs1, go to the directory that contains all your code and run the script:

/home/fac/lillethd/cpsc3500/submit/submit_virtual_memory

This will copy the files pagetable.cpp, pagefault_handler.cpp, and Makefile to a directory where the instructor can access them. Please be sure to keep the same file names or the submission program will not work. (No other files will be submitted, so make sure these are the only ones you modified!)

The submission program will attempt to compile your program using the other provided source code files and your Makefile. Your program must properly compile, or the submission program will reject your program. Programs that fail to compile will not be graded and receive a 0. Only the last assignment submitted before the due date and time will be graded. To resubmit, just run the submission script again, but only your last submission counts and all earlier submissions will be permanently overwritten! Late submissions are not accepted and result in a zero, unless covered by free passes.

The submission script will clearly display a message containing either the word “SUCCESSFUL” or “FAILED” – you should always see exactly one of those words in all caps (never both or neither).