The goal of this lab assignment is to extend the LC-3b simulator you wrote in Lab 4 to handle virtual memory. You will augment the existing LC-3b microarchitecture in order to support virtual to physical address translation. You will also provide microarchitectural support for page fault exceptions and change the protection exception from lab #4 to be based on access mode in the PTE.
In Lab 5, the address space of the LC-3b is divided into pages of size 512 bytes. The LC-3b virtual address space has 128 pages, while physical memory has 32 frames. Virtual pages 0-23, which are reserved for the operating system, will be mapped to frames 0-23 and will always be resident in physical memory. Frames 24-31 are available for swapping virtual pages of user programs. There are two modes of operation: supervisor and user. Virtual pages 0-23 cannot be accessed unless the LC-3b is in supervisor mode. Since user programs operate in user mode, they cannot access those pages. Thus the user virtual memory space is 104 pages (pages 24-127).
The input to this new simulator will be:
New shell code.
A modified shell code has been written for you: lc3bsim5.c
This shell code has the capability of loading the page table into memory. You will need to copy and paste the code you wrote for Lab #4 into this new shell code.
Note that a new command line parameter has been added: the pagetable. To run the simulator, type:
lc3bsim5 <micro_code_file> <page table file> <program_file_1> <program_file_2> ...
The first parameter is the microcode file as before. The second parameter is the page table in LC-3b machine language. Note that since the page table is in physical memory, the first line of this file should have a physical address. For all the program files, (including the interrupt and exception handlers) which are in virtual memory, the first line should have a virtual address.
The Page Table
The page table should be placed at the beginning of frame 8 of physical memory. A page table entry (PTE) contains only 9 bits of information, but for convenience, it is represented in a full 16 bit word. Thus one PTE occupies two memory locations. The format of each PTE is as follows:
PFN = PTE[13:9], the page frame number
P = PTE, the protection bit
P=0 -> page can only be accessed in supervisor mode
P=1 -> user has full rights to the page
V = PTE, the valid bit (V=1 for a valid page)
M = PTE, the modified bit (M=1 if page has been written)
R = PTE, the reference bit
R=1 -> page has been referenced since last timer interrupt
R=0 -> otherwise
All other bits are set to zero.
Page Table Access from the Datapath
During the execution of instructions, your microcode will have to convert virtual addresses to physical addresses, as well as modify PTEs when necessary. To make address translation possible, we have added more structures to the datapath. We have added these registers: Page Table Base Register (PTBR) and Virtual Address Register (VA). The PTBR points to the first entry of the page table in physical memory and will be initialized by the shell code to the starting address of the page table file you provided as a command line parameter to the simulator. It's used to access a particular PTE during translation. To put the PTBR register onto the bus, you should assert the GatePTBR signal. The VA register is a temporary register to hold the current address being translated. To put the VA register onto the bus and to write to the VA register from the bus, you should assert the GateVA and LD.VA control signals, respectively.
We will use a simple one-level translation scheme to translate virtual addresses to physical addresses. The high 7 bits of the virtual address (bits[15:9]) specify the page number, and the low 9 bits of the virtual address (bits[8:0]) specify the offset within the page. All 7 bits of the page number will be used during translation. Assume that at the beginning of each address translation phase the virtual address is located in the MAR, and if the operation is a write, a source register holds the data to be written. Address translation consists of the following steps:
To add support for virtual memory, you first need to determine when you need to perform the address translation. Then, you will need to determine how to modify the state diagram so that it supports a "micro-subroutine" written in microcode to translate addresses. You will also need to determine how to return back to the correct state once address translation is complete. For this, you need to augment the microsequencer. You are free to add new control signals, gates, muxes, temporary registers as you wish as long as you fully document your changes.
If the page accessed by a user program is not valid (not in physical memory), then a page fault exception will occur. The exception vector for the page fault exception is x02. You will also write the exception service routine for the page fault. This routine should start at memory location x1400. For the purposes of this assignment, the exception service routine will simply halt the machine. However, don't rely on this. We can test your simulator by replacing your exception routine with our routine which returns from the exception handler using the RTI instruction instead of halting the machine. Upon return from the exception handler, the instruction that caused the exception should be re-executed.
Protection exceptions occur only when the machine is in user mode, and a memory page whose PTE protection bit is set to 0 is accessed. The memory access that causes a protection exception should not be allowed to complete. The exception vector for the protection exception is x04. The exception handler for the protection exception is located starting at x1600. This routine should halt the machine. However, as with the page fault exception, do not assume that the machine will always be halted after a protection exception occurs.
The user program in page 24 should do the following: calculate the
sum of the first 20 bytes stored in memory starting at address
xC000 (notice this is on page 96). This sum should then be stored
as a 16-bit word at xC014. Then the program should jump to the address pointed to by
this sum. Page 96 contains data to be used by the program on page
24. The following numbers should be stored there:
x12, x11, x39, x23, x02, xF6, x12, x23, x56, x89, xBC, xEF, x00, x01, x02, x03, x04, x05, x06, x07.
These should be in the data file for virtual page 96 that you provided as a command line parameter to the simulator and will be loaded into memory when the simulator starts.
The interrupt service routine must traverse the entire page table, clearing the R bits of each PTE. You may assume when writing this code that the start address of the page table is fixed.
The exception handlers you will submit should simply halt the machine.
Initial Page Table Contents
The page table will be initialized upon simulator start-up based on the contents of the page table file you provided as a command line parameter to the simulator. It should look as follows:
Pages 0-23 are in frames 0-23. They are valid and inaccessible by the user.What To Submit Electronically
Page 24 is in frame 25. It is valid and accessible by the user.
Page 96 is in frame 28. It is valid and accessible by the user.
Page 126 is in frame 29. It is valid and accessible by the user. This page contains the user stack.
All other pages are invalid. All invalid PTEs in user space (0x3000-0xFFFF) must be initialized with the protection bit set, i.e. a value of 0x0008. Why?
How to generate the dumpsim file
Dump the memory locations containing the page table entries once before the 300th cycle, once after the ISR is done, and finally after the protection exception halts the execution of the program (you should get a protection exception after the jump). Also, dump memory location x3814 (corresponding to which virtual address?) and the current registers after the protection exception.
Things To Consider
The supervisor stack starts at virtual address 0x3000 (SSP is initialized in the shell code). If the user program uses the user stack, the user stack should start at address 0xFE00 (i.e. that user program should initialize R6 to 0xFE00).