lunduniversity.lu.se

Computer Science

Faculty of Engineering, LTH

Denna sida på svenska This page in English

Lab4: PintOS Virtual Memory

Introduction

Another key functionality provided by many operating systems is virtual memory. To achieve this in PintOS, you will need to extend page_fault() in src/userprog/exception.c to handle swapping pages in and out of the swap device.

Learning outcomes

After completing this assignment you will have an understanding of how an operating system manages virtual memory using page fault exceptions and dedicated swap.

Assignment

Some of the functionality needed for implementing swapping in PintOS is already available in the sources from the src/vm directory. In particular, swap support is already available via the src/vm/*.[c|h] files. Please study these in detail. If your repository does not contain the src/vm/swap.[c|h] files (were introduced into the public repository recently), make sure you download these two from https://git.cs.lth.se/al7330du/pintos-public and add them to your source tree. You also need to to modify src/Makefile.build to add the newly downloaded files to your build.

In this assignment, you will extend the already existing functionality with the ability of detecting whether a page is present in the memory; if not, locate it on the swap and bring it in to a free frame; if there are no free frames, you should make one by evicting a page according to a policy of your choice. Before proceeding, read Chapter 4: Virtual Memory from the PintOS documentation, except the parts related to Memory Mapped Files. Notice that the repository we provide already includes a lot of functionality mentioned here as design assignment. You will only need to understand how these fit together and implement swapping during the page fault exception, using the provided functions.

The main building directory for this assignment is src/vm/build. To run the tests, run make check in this directory.

In this assignment there are two main additions you should make. First, make sure page_fault() in src/userprog/exception.c handles the case when a page is on the swap. Second, extend the frame_map() in src/vm/frame.c to provide a frame made free for the new page.

Task: Study the sup_page structure from the src/vm directory, swap_in() and swap_free() functions in the same place, and install_page() (again) from src/userprog/process.c. Also check the frame_free() function in src/vm/frame.[c|h], which is needed if you want to handle errors when installing pages. These should allow you to be able to handle page faults with pages on the swap, assuming there are enough free frames.

Task: The swap needs to be initialized and destroyed at the right place in the code, in src/threads/init.c. Add code for this.

Task: Add code to page_fault() which handles the case when the page is on the swap. You may need to add some information in the sup_page structure from src/vm to help you keep track of which page is where on the swap. Add whatever header files needed for this. Don't forget to free the swap space for that page (can only be in one place at a time) and also to update any supplemental page information sup_page about the page you swapped in.

Task: Add code to frame_map() in src/vm/frame.c to handle the case when there are no free frames. Here you will have to choose one page to evict, by using a page replacement algorithm (start with FIFO, but try out others as well if you want to improve performance). Swap that page out if necessary and update related information. Finally, return its physical address - this is where the new page will be swapped in.

When you swap out a page, you need to update the sup_page structure for the thread that allocated the page and record that it no longer resides in the main memory, but in swap. The thread that owns a memory frame is accessible through the struct frame::owner field. To find the page that needs update, you can modify the lookup_page() function such that it accepts this thread as an argument. Feel free to use the printouts in the swap implementation and add your own, in order to get some more information useful for debugging.

Hand-in

  • Motivation for the code added in page_fault, frame_map, and other places.
  • What page replacement policy did you implement and why?
  • The modified PintOS source code that is passing all the make check tests for vm, except the ones related to memory mapped files (not page-merge-mm or those starting with mmap-). Naturally, the tests passed before for the previous labs should still pass!

Hints

  • This assignment does not require you to write any new data structures or assembly code.
  • The estimated time needed to solve this exercise is at most 6h.
  • The approximate size of the code changes is:
src/Makefile.build       |  1 +
src/threads/init.c       |  9 +++++++++
src/userprog/exception.c | 26 ++++++++++++++++++++++++++
src/vm/Make.vars         |  4 ++--
src/vm/frame.c           | 29 +++++++++++++++++++++++++++++
src/vm/sup_page.c        | 11 +++++++++++
src/vm/sup_page.h        |  4 ++++