In this project, you will extend a program that emulates the processing of a series of memory access requests to implement key tasks in processing memory requests, including page replacement. This program takes a sequence of memory access requests as inputs and emulates TLB, page table, and page fault handling to process those requests. You will extend this program in four ways: (1) you will add a mechanism to add and resolve page mappings (i.e., map a page number – for the memory access request – to a physical frame number) for a two-level page table; (2) you will add a mechanism to search the TLB to determine the physical address of a memory request on a TLB hit; (3) you will implement two page replacement schemes (second chance/clock and a 3-bit approximation of”least recently used”); and (4) you will implement a mechanism to deallocate page table memory when a process is terminated.
Using the Program
The program works as follows: type cmpsc473-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 mechanism-number indicates which page replacement algorithm will be applied, where: (0) is for FIFO replacement (code provided); (1) is for the clock (second chance) algorithm; and (2) is for a 3-bit LRU algorithm. We will provide example input files and their expected outputs for each program extension.
NOTE: The paging mechanism that you implement in this project – especially for Tasks 1 and 2 below – is the traditional paging mechanism described in Chapters 18, 19, and 20 of the course textbook . Until you understand those steps, the detailed description for Tasks 1 and 2 below may be hard to follow. Similarly, the page replacement algorithms required for Task 3 are discussed in the book in Chapter 22.
I highly recommend mapping the concept approaches described in the book to the function-level requirements for the programming assignment. If there is a coding task that you cannot map to any conceptual approach, I recommend seeking some help.
The project will consist of the following tasks:
NOTE: For the first two tasks, use the FIFO replacement algorithm (provided) by specifying the mechanism-number of 0. In Task 3, you will add the two other replacement algorithms. For all tasks, each memory request may be made by a different process. Everypage table operation runs in the context of the specific process making the memory request.
- Task 1: The first task in virtual memory management is to allocate physical frames for virtual memory accesses. The basic process of memory management is implemented by the command_loop function. When a program starts, it has no access to physical memory, so the TLB (tlb_resolve_addr) and the page table (pt_resolve_addr) will fail to resolve the virtual address (vaddr) of the memory request. Thus, your first task is to complete an implementation of pt_demand_page to store the physical frame for a virtual page in a two-level page table.
Task Guidance: The first step in allocating a physical frame for a page is to identify the page table entry to start that page-to-frame mapping. The function PAGE_TO_PTENTRY must be completed to translate a page number (from the virtual address of the access, vaddr) to a page table entry. When a process performs an instruction that references a virtual memory address, we need a physical frame to “back”that virtual page being accessed. Thus, the first step is to store a new mapping between the page and the frame in the page table entry.
See the definition of the ptentry_t structure in cmpsc473-p1.h.
In this project, we will use a two-level page table, as described in Section 20.3 of the course textbook. See Figure 20.3 (multi-level version) for the format of the page table in memory. We assume our system uses 32-bit virtual addresses and 4K pages, meaning that: (1) the first (lowest) 12 bits of an address reference the offset within a page and (2) the remaining (highest) 20 bits are the page number.
The two-level page table indexes pages using 10 (higher) bits to index the page directory for the page and 10 (lower) bits of the page number to index the page table to find the specific entry with the page-to-frame mapping. The physical address is then computed as shown.
The first-level is called the page directory and consists of an array of 1024 entries – for 2^10 possible page directory indices. These page directory entries consist of only one field, an 8-byte address to the second-level page table entries for a particular page directory entry. If a page directory entry has a non-null page table page (pte_page) field value, the page table is valid. You need to allocate the memory for each page table page dynamically. It will make yourlife a lot easier if you page-align each page table using posix_memalign. I use this to align the page directory itself, so there is already an example in the code.
Each page table page consists of 1024 entries that are 4 bytes in size. The entries use bit fields to store small values – from 1 bit for “valid”to 20 bits for the “page number.” The data structure definitions for page directory entries (pdentry_t), page table entries (ptentry_t), and physical frames (frame_t), among others, are included in cmpsc473-p1.h. Do not modify the cmpsc473-p1.h file!
- Task Details: I provide you with the code to identify a free physical frame in the function pt_demand_page (so your program runs predictably), so your task is to write the code to setup the page table entry for a new page-to-frame (page table) mapping and compute the resultant physical address for virtual address.
This task has three modest steps. If you find you cannot perform any of the steps please obtain guidance as the subsequent tasks depend on completing this one.
Your task 1(a): The first step is to write the function PAGE_TO_PTENTRY,which maps a virtual page number to its corresponding page table entry for that page and returns the address of the page table entry, allocating page table memory when required. Please use the guidance above to implement this computation.
Your task 1(b): The second step is to initialize the new page-to-frame mappingby updating the page table entry and frame fields in the function pt_alloc_frame with the expected values. You can set the reference (“ref”) and dirty (“dirty”) fields of the page table to FALSE initially, as they will be set later by hw_update_pageref, which emulates how the hardware updates these bits.
Also, please set the “op” field of the page table to OP_READ or OP_WRITE (should be the values passed into that function). Please figure out the semantics of the other page table and frame fields to assign their initial values.
Your task 1(c): The last step is to compute the physical address for a memory address from the virtual address and frame at the line shown in pt_demand_page. The mechanism to do this is described in Chapter 18.
- Task 2: In addition to virtual address translation using page tables, you will also implement virtual-to-physical address resolution for the emulated TLB (tlb_resolve_addr) and for page table hits (pt_resolve_addr).
Your Task 2(a): The TLB is a simple cache (array) of recently used address translations. If a TLB hit is found for a valid entry, the program function tlb_resolve_addr must convert the virtual address (vaddr) to a corresponding physical address (paddr) based on the frame mapped to the page in the TLB.
NOTE: That you need to check for a protection faultfor the TLB hit entry in tlb_resolve_addr. In general, the “op” of a page-to-frame mapping must be “write”(=1) for a write operation to be allowed. See the check in pt_demand_page for an example.
Your Task 2(b): The function pt_resolve_addr must determine whether there is a valid page table entry for the page, and if so, compute the physical address for the frame mapped for the page by the page table. Use the PAGE_TO_PTENTRY function you already wrote in Task 1(a) to simplify this task. NOTE: That you need to check for a protection faultfor the page table lookup as well. See Task 2(a) above.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: firstname.lastname@example.org 微信:itcsdx