Goals

• Practice with objects, template and STL in C++
• Gain familiarity with caching and virtual memory
• Experiment with the fragile type system of C++

Collaboration

For assignments in CIT 5950, you will complete each of them on your own or solo. However, you may discuss high-level ideas with other students, but any viewing, sharing, copying, or dictating of code is forbidden. If you are worried about whether something violates academic integrity, please post on Ed or contact the instructor.

Contents

• Overview
  • Page
  • PageTable
• Instructions
• Suggested Approach
• Hints
• Grading and Testing
  • Compilation
  • Valgrind
  • gtest
  • Submission

Overview

One of the topics we discussed in class so far has been virtual memory. In this assignment, we will be constructing a simplified software implementation of a virtual memory management unit. Note that this is not how virtual memory would actually be implemented at all, this is just a simple model that will be helpful for you to get practice with many of the topics we have discussed in the class so far. In addition, this assignment will give you the opportunity to do some design and do some research on the C++ standard library.

Our simple virtual memory model will have Page Objects and a PageTable object. To represent a page as being loaded into physical memory, we simply say that there is a corresponding page object in our model. If a page is not in memory, then its data is stored entirely on disk in a designated “swap file”. The swap file is structured so that each of the pages have their data ordered sequentially with the page number. For example: the first 0 through Page::PAGE_SIZE - 1 bytes of the file are associated with virtual page number 0. Bytes Page::PAGE_SIZE through (2 * Page::PAGE_SIZE) - 1 are associated with virtual page number 1, etc. To support file I/O, you are to use the C++ fstream class. You are encouraged to look through C++ resources to find useful functions for this. Two possible references are listed below

• cplusplus.com/reference/fstream/fstream
• cppreference.com/w/cpp/io/basic_fstream note that fstream is a typedef of basic_fstream

As a hint, you may find the write() and read() member functions useful, but it is up to you to figure out how to use them and if there are other functions that may be useful.

This assignment is split into two main parts, the Page and the PageTable.

Page

A page object represents a page of data that has been loaded into physical memory. With a page object, a user can utilize the memory in that page for either accessing or storage, as well as getting other information about the page (such as its page number). To support being managed by STL containers in the later portion of the assignment, we must enable copy constructors and the assignment operator on these objects.

More details can be found in Page.h.’ We recommend that you read through this file before you start your implementation.

PageTable

A PageTable object manages various pages and a swap file. The main goal of the PageTable is to implement a page replacement policy (LRU in our case) and limit the number of pages that can be held in memory at once. As a result, there are member functions for discarding a specific page, evicting the least recently used page, flushing a page to disk, and a function that gets a page from disk or memory if it is already in memory.

We do not provide you all the data members you will need to implement the PageTable, and as a result, you will have to decide which will work best for your use case. In particular, there are various STL containers that you may find useful.

More details can be found in PageTable.h. We recommend that you read through this file before you start your implementation.

Instructions

You will find the starter code in Codio, where you will also submit the assignment. Among these files, a few stand out:

• Page.h: Contains the declarations and extensive comments detailing the functions you will have to implement for the Page class.
• Page.cc: Where you will be writing all of your template code for Page.
• PageTemplates.cc: Where you will be writing all of your template code for Page.
• PageTable.h: Contains the declarations and extensive comments detailing the functions you will have to implement for the PageTable. You will have to add data members to the PageTable class.
• PageTable.cc: Where you will be writing all of your code for the PageTable. You will have to implement all of the functions specified in PageTable.h.
• test_page.cc: The tests that we will be using to evaluate your Page.
• test_pagetable.cc: The tests that we will be using to evaluate your PageTable.

We recommend reading all of these files before your start, especially the .h files listed. Note: you are only allowed to modify the following files Page.cc, PageTemplates.cc, Page.h, PageTable.cc, and PageTable.h. This means that your code should work with the other files as they are when initially supplied. Note that you are allowed to modify PageTable.h and Page.h but they still must work with the tests. This means that any modifications you may make would likely be for adding new private data members or new member functions. We even suggest a few private helper methods in the Hints section below. Additionally, you can modify the test files if you like (for debug purposes), but we will be testing your code against un-modified versions of the files.

Suggested Approach

Below we have provided a suggested approach to this homework. Note that you are not required to follow this ordering if you believe another approach would work better for you. Also note that you can gradually check your progress, and run specific tests. Look at the gtest section below for more details on running individual tests.

1. Start by populating Page.cc, PageTemplates.cc and PageTable.cc with “empty” definitions of every member function. Afterwards, make sure that you can compile successfully. This is so that you can test your code as you implement and not all at the end.

2. Implement the constructor, destructor, dirty() and pno() member functions for the Page class in Page.cc. Afterwards, you should pass the basic_ctor tests for page.

3. Implement the access() data member function in PageTemplates.cc. Afterwards, you should pass the access tests for page. Note: You may want to read the hints for this function.

4. Implement the store() data member function in PageTemplates.cc. Afterwards, you should pass the store tests for page. Note: You may want to read the hints for this function.

5. Implement the copy constructor and assignment operator in Page.cc. This should get you to a point where you are now passing all Page tests and earning at least 105 points.

6. PageTable is a little more tricky. All of the member functions depend on how you decide to keep track of the pages and how recently they were used. As a result, we recommend that you spend some time reading through the .h files and planning out which data members you will need to complete the PageTable. Please don’t hesitate to ask for help on Piazza with understanding what you are supposed to do! Also note that we are not grading on performance, but we encourage you to try to write efficient code!

NOTE: Just because you pass a test mentioned in one of the steps above doesn’t guarantee that the function is now correct. Other tests may reveal errors that you may have to go back and fix.

Hints

Here are a few hints and tips that you may find useful when approaching this homework.

1. Don’t wait until the end to test. As mentioned in the suggest approach above, you can create “empty” definitions for functions, just enough to compile, so that you can test your other functions.
2. There are many stl containers that will make your life easier for implementing PageTable. In particular, map, unordered_map, list, vector or others may be useful to you. You can find a list of the various STL containers at the following links:
   • cplusplus.com/reference/stl
   • cppreference.com/w/cpp/container
3. Both Page and PageTable will require use of the fstream class. We recommend the member functions read() and write() but it is up to you to figure out how to use them and whether there are other things that may be useful. Some resources on fstream are linked below
   • cplusplus.com/reference/fstream/fstream
   • cppreference.com/w/cpp/io/basic_fstream note that fstream is a typedef of basic_fstream
4. Since we are using uint8_t as a byte to represent page data, we may have to cast from a uint8_t* to a char* to make use of some of the fstream member functions.
5. Constructing the Page Object will require initializing a data member that is a reference. To do this, you MUST use an initializer list to initialize the reference data member.
6. The access() and store() functions may be a little tricky. It is useful to know that you can assume the type you are reading/writing to the page data will be primitives types that support various bit-wise operations (e.g. shifting, bitwise OR, etc.). To get Page::access and Page::store to work, two methods stand out:
   • Since the types are primitives, it is very easy to “bend” the types in code to get the desired behaviour. In particular, one can freely cast from one pointer type to another, and the pointer type decides how the bytes being pointed at is interpreted.
   • Since bitwise operations are supported, one can use things like sizeof() and bitwise operators to “build up” the bytes of the request type.

Grading & Testing

Compilation

We have supplied you with a makefile that can be used for compiling your code into an executable. To do this, open the terminal in codio (this can be done by selecting Tools -> Terminal) and then type in make.

You may need to resolve any compiler warnings and compiler errors that show up. Once all compiler errors have been resolved, if you ls in the terminal, you should be able to see an executable called test_suite. You can then run this by typing in ./test_suite to see the evaluation of your code.

Note that your submission will be partially evaluated on the number of compiler warnings. You should eliminate ALL compiler warnings in your code

Valgrind

We will also test your submission on whether there are any memory errors or memory leaks. We will be using valgrind to do this. To do this, you should try running: valgrind --leak-check=full ./test_suite

If everything is correct, you should see the following towards the bottom of the output:

 ==1620== All heap blocks were freed -- no leaks are possible
 ==1620==
 ==1620== For counts of detected and suppressed errors, rerun with: -v
 ==1620== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

If you do not see something similar to the above in your output, valgrind will have printed out details about where the errors and memory leaks occurred.

Gtest

As with previous homework assignments, you can compile the your implementation by using the make command. This will result in several output files, including an executable called test_suite.

After compiling your solution with make, You can run all of the tests for the homwork by invoking:

./test_suite

You can also run only specific tests by passing command line arguments into test_suite

For example, to only run the Page tests, you can type in:

./test_suite --gtest_filter=Test_Page.*

If you only want to test access from Page, you can type in:

./test_suite --gtest_filter=Test_Page.access

You can specify which tests are run for any of the tests in the assignment. You just need to know the names of the tests, and you can do this by running:

./test_suite --gtest_list_tests

These settings can be helpful for debugging specific parts of the assignment, especially since test_suite can be run with these settings through valgrind and gdb!

Submission:

Please submit your completed Page.cc, PageTemplates.cc, Page.h, PageTable.cc, and PageTable.h to Gradescope