CMPSC 473 - Project #1 - Page Replacement

Due Date: 2/22/16. 100 points

Single person project. Do your own work!

In this project, you will extend a program that emulates the processing of memory accesses. This program takes a sequence of memory accesses as inputs and emulates TLB, page table, and page fault handling to process that request. You will extend this program in four ways: (1) you will add the mechanisms to search the TLB and a simple, linear page table to determine the physical address of a memory request; (2) you will implement page replacement using three schemes (most frequently used, second chance (clock), and enhanced second chance) and (3) you will calculate effective memory-access times and effective (page fault) access times.

The program works as follows: type cse473-p1 input-file output-file mechanism-number at the prompt. The input files will be provided. The output file will contain the results of the processing.

The project will consist of the following tasks:

  1. Download the following tarball Project 1 Code to your CSE account file space. You should have one file p1.tgz.

    There is a Makefile in directory p1, which makes cse473-p1. Add your PSU ID to the Makefile at the variable PSUID (currently XXXXXXXXX). This will ensure that your submission file is named by your PSU ID - please do not change the name of your submission file.

  2. You will need to implement virtual-to-physical address resolution for the emulated TLB (tlb_resolve_addr) and emulated page table (pt_resolve_addr). These functions take a virtual address (vaddr) and return a correspond physical address (paddr). The page table emulation also returns whether the page table contains a valid entry for that virtual address. As these functions are run by the MMU, you will need to include calls to hw_update_pageref in each, which emulates the MMU updating the reference bits in the page table entry for the selected page. See how it is invoked in pt_demand_page.

  3. You will need to implement page replacement when the page table/TLB do not contain a reference to that virtual address. The function pt_demand_page defines the demand paging mechanism (provided), but you will define the supporting page replacements and update the page tables (the TLB updating is provided).

    Page table updates consist of allocating a page table entry the associates a page with a frame (pt_alloc_frame). In this function, a page table entry (ptentry) is associated with a frame and operation (read-only or read-write). The page table bits for the page (valid, and reference) must be updated also (call hw_update_pageref). The .h file defines these bits. If a page is being replaced, we need to invalidate that entry. You will also implement the function (pt_invalidate_mapping) to remove (invalidate) the mapping between a virtual page and a physical frame.

    We will implement three page replacement mechanisms: (0) most frequently used (see slides - cse473-memory in Angel); (1) second-chance (clock, Section 22.8 of the text); and (2) enhanced second-chance (see slides - cse473-memory.ppt in Angel) - use these numbers as the mechanism-number argument to the process. There are two functions that must be implemented for each page replacement mechanism: (1) update, which updates the page replacement data structures when a new page table entry is made valid (allocated); and (2) replace, which performs the page replacement mechanism. The replacement functions must make the same decisions as dictated by the page replacement algorithms.

    See an example implementation of FIFO replacement to give you an idea of how to implement replacement mechanisms.

  4. Finally, when all the memory access requests have been processed, we need to compute some summary information. The two computations that you will need to add to write_results are: (1) effective memory-access time and (2) effective access time relative to page faults. Use the information for tlb_hit_ratio and pf_ratio (page fault) to compute these values. Use 20 nanoseconds for TLB lookup time, 100 nanoseconds for memory access time, and other #defines for overheads in cse473-p1.h.

  5. Please be prepared to answer the following questions regarding the project (e.g., on a future quiz/exam):

    1. When a memory access corresponds to an invalid entry in the page table, it may or may not refer to a legal virtual address in the process's address space. How does the operating system determine this?

    2. What is the page-fault frequency approach? What problem does it address?

    3. What is an example of a workload (sequence of memory accesses) in which most frequently used page replacement would lead to fewer page faults than other page replacement algorithms?

  6. Your submission will consist of a tarball of your code, made from make tar. We will run your code and look for correct solutions to the key parts of the program.

  7. Grading:

Extra notes/explanations/reminders:
  1. To help you better understand what you are supposed to do, we provide a demo executable file project1-demo which implements FIFO algorithm. To run it, first write your own input file in the same directory, then type the command project1-demo input-file output-file in the terminal. We also provide the code to implement FIFO algorithm cse473-p1-fifo.c, note that this code works as a reference, it cannot be compiled alone.

  2. When creating your own input file, please be careful about the virtual address format. The page size is 0x1000 (PAGE_SIZE = 0x1000) and there are at most 64 virtual pages per process (VIRTUAL_PAGES = 64). That is to say, the maximum allowed virtual address is 64 * 0x1000 = 0x40000. Otherwise, a segmentation fault will occur.

  3. In this project, if the accessed page offset is smaller than 0x200, it is write operation, otherwise, it is read operation.

  4. When implementing most frequently used algorithm, you can use the field ct in ptentry to record how many times this page has been referred.

  5. The time metrics such as TLB searching time, page table searching time, page fault overhead, etc, are constants defined in .h file. So you do not need to measure those in your project (since this is only a simulation project, it is meaningless to measure those time metrics). However, you do need to use your recorded tlb_hit_ratio and pf_ratio to calculate effective memory-access time and effective access time in your program.

  6. In functions tlb_resolve_addr and pt_resolve_addr, if there is a hit, do not forget to call hw_update_pageref to update reference bit and (perhaps) dirty bit.

  7. When invalidate a mapping, do not forget to check the dirty bit to determine whether it is necessary to overwrite the disk data (call pt_write_frame), please take section 9.4.1 of Operating System Concepts as a reference.

  8. Although it is not a very difficult project, there are hundreds lines of codes you need to go through. So you may want to start early and ask TAs or instructor for help when you get stuck.

Trent Jaeger