EE 360N, Spring 2001
Y. N. Patt, Instructor
Onur Mutlu, Kameswar Subramaniam, TAs
Lab Assignment 4; Due May 4, 2001

Introduction

The goal of this lab assignment is to extend the LC-2 simulator from lab 3 to handle virtual memory. You will augment the existing LC-2 microarchitecture with facilities for virtual to physical address translation.

As in Lab 3, the address space of the LC-2 is divided into pages of 512 locations (9 bits). The LC-2 virtual address space will have 128 pages, while physical memory will have 32 frames. Frames 0-7 are reserved for the operating system, and will not be used for this lab. Frames 8-15 hold additional system facilities, i.e. the interrupt handling code, exception handling code, the page table and the stack. Frames 16-31 are available for swapping virtual pages. In addition, there are two modes of operation: kernel and user. Virtual pages 0-15 cannot be accessed unless the LC-2 is in kernel mode. Since user programs operate in user mode, they cannot access those pages. Thus the user virtual memory space is 112 pages (pages 16-127).

The input to this new simulator will be:

1. A file entitled ucode which holds the expanded microcontrol store.
2. A file holding an LC-2 program that gets loaded into physical frame 8 (x1000).

This will be the page table.
3. A file holding a LC-2 user program that gets loaded into virtual page 16 (x2000).
4. A file holding data for the program in page 16. This data will be loaded into page 96 (xC000).
5. A file holding an LC-2 program that gets loaded into virtual page 9 (x1200).

This will be the interrupt service routine.
6. A file holding an LC-2 program that gets loaded into a different address in page 9 (x1300).

This will be the exception handler (followed by the stack)

New shell code A modified shell code has been written for you:

lc2sim4.c

You will need to make similar changes to this shell code as in lab3 to incorporate interrupts & exceptions.

Note that the a new command line parameter has been added: the pagetable. To run the simulator:

a.out <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-2 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 & exception handlers) which are in virtual memory, the first line should have a virtual address.

Specifications

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 page table entry occupies one memory location. The format of each page table entry is as follows:

PFN = PTE[13:9], the page frame number

P = PTE[3], the protection bit
P=0 -> page can only be accessed in kernel mode
P=1 -> user has full rights to the page

V = PTE[2], the valid bit (V=1 for a valid page)

M = PTE[1], the modified bit (M=1 if page has been written)

R = PTE[0], the reference bit
R=1 -> page has been referenced since last timer interrupt
R=0 -> otherwise

All other bits are set to zero.

During the execution of instructions, your microcode will have to convert virtual addresses to physical addresses, as well as modify PTE's when necessary. To make address translation possible, we have added more structures to the datapath. We have added several 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. It's used to access a particular PTE during translation. To read from this register onto the bus, you should assert the GATE_PTBR signal. The VA register is basically a temporary register to hold the current address under translation. To read the VA register onto the bus and to write to the VA register from the bus, you should assert the GATE_VA and LD_VA control signals respectively. There is also a flipflop which holds the current mode of the machine. Two registers called 1 and 3 provide constants needed for modifying PTE's. (These two registers are optional, and you may not use them in your implementation if they aren't required).

Interrupts and Exceptions

You'll have to modify the interrupt and RTI microcode only slightly. When vectoring to the ISR, the mode of the LC-2 should be switched to kernel. Likewise, upon RTI to the user program, the machine goes back to user mode. The timer interrupt service routine implemented in lab 3 must be modified for this lab. Instead of incrementing a counter, the interrupt will clear the reference bits for each entry of the page table, thus enabling a limited LRU replacement scheme for the operating system. Note: the timer will go off only once during program execution - during the 500th cycle.

Two classes of exceptions will exist in your extended LC-2. The first class is protection exception. 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 mode of the LC-2 should be switched to kernel when handling exceptions. The second class of exception is page fault. For either class of exception, the PC is decremented and the machine is halted. On a real machine, of course, page faults will not cause the machine to halt, but rather will cause the current state to be saved and the PC to be loaded with a vector to the operating system's page fault handler. For our purposes, however, it will suffice to decrement the PC and halt.

Translating Addresses

Assume that at the beginning of each address translation phase that 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:

• Save the MAR into a temporary register VA

 
• Load the MAR with the address of the PTE of the current table
MAR[15:7] <- PTBR[15:7]
MAR[6:0] <- VA[15:9]
 
• Read the PTE of the current table into the MDR

 
• Check for a protection exception

 
• Check for a page fault

 
• Set the R bit

 
• If the pending instruction is a write, set the M bit

 
• Write the PTE back to memory

 
• Load the physical address into the MAR
MAR[13:9] <- PFN
MAR[8:0] <- VA[8:0]
 
• If the operation is a write, load the MDR with the source register

What to do for Lab 4

The following extensions must be made to your LC-2 simulator system:

Datapath
There are some minor modifications that need to be made to the datapath. i.e. How you take care of loading values into the MAR
during the translation process. Try to avoid doubling to 128 states.

Microsequencer
You'll need to add logic to detect page faults and protection exceptions. The state diagram must be altered so that any path into a state which uses memory now goes into a microcode routine that does address translation before using the memory. Hint: You will want to implement a micro-subroutine of sorts. The microsequencer must be extended to provide the necessary flow of control.

Microcode
Extra fields for the current LC-2 microinstructions will be required to control the address translation logic (e.g. LD_VA, GATE_VA) and provide control for the microsubroutine and processor mode. In addition, new microcode to do the virtual to physical address translation must be written. A key issue for this lab is when and where to call the address translation routine.

Writing Code
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 user program in page should do the following: sum the first 20 values stored in the memory locations beginning with xC000 (notice this is on page 96). This sum should then be stored 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 16. The following numbers should be stored there:
x0012, x0011, x2F39, x1023, x1002, x00F6, x0912, x0123, x0456, x0789, x0ABC, x0DEF, x0000, x0001, x0002, x0003, x0004, x0005, x0006, x0007.
These should be loaded into page 96 on initialization of the simulator.

Initial Page Table Contents

The page table will be initialized upon simulator start-up. It should look as follows:

Page 0 is in frame 0. It is valid and unaccessible by the user.
Page 8 is in frame 8. It is valid and unaccessible by the user.
Page 9 is in frame 9. It is valid and unaccessible by the user.
Page 16 is in frame 16. It is valid and accessible by the user.
Page 96 is in frame 24. It is valid and accessible by the user.
All other pages are invalid.

1. Adequately documented source code of your simulator called lc2sim4.c.
2. The assembly code for the interrupt service routine, the page table, the exception handler, the page 16 program, and the page 96 data, called int.asm, pagetable.asm, except.asm, add.asm, and data.asm respectively.
3. The machine code for the interrupt service routine, the page table, the exception handler, the page 16 program, and the page 96 data, called int.hex, pagetable.hex, except.hex, and add.hex, and data.hex respectively.
4. The new microcode called ucode.
5. A file called dumpsim. To generate this file, simulate the LC-2 assembly programs by following the instructions in the next section.
6. A text file called readme that explains how you implemented this lab assignment. Describe any new fields you added to the microcode. What changes did you make to the datapath? Include a picture similar to the state machine that shows the new states you added(only show your changes). Describe what occurs at each state. Draw a logic diagram of your new microsequencer.

Things To Consider

The PTBR will contain a physical addresse. The only time you need to update the reference/modified bits for the page 8 PTE is during the interrupt service routine. That is, you only need to update R or M within the context of an address translation for the page 8 PTE.

The stack should start immediately after the exception handler. The address that the stack pointer is initialized to will depend on the length of the exception handler.

How will you return from the address translation to the correct state? An obvious solution would be to have a register which holds the 6-bit return address. A better solution uses a multi-way branch from the final state of the address translation subroutine. You can use COND and the IR register to implement this branch.

Some questions which will help understand this lab:

1. Since the page table is in physical memory, and the PTBR contains a physical address, the ISR needs to access the PTEs using physical addresses. An easy way to do this is to turn off virtual to physical address translation when operating in system mode. This will have the added benefit of reducing the number of cycles taken to execute the ISR.What restriction does turning off virtual to physical address translation place on the ISR code?
2. The stack pointer (R6) in this lab contains a virtual address - why is this feature useful?
3. What should R6 be initialized to?
4. What is the maximum size of the stack in this lab?
5. Note that the interrupt handler, exception handler and the stack are in page 9, and this page is in frame 9 in physical memory. Why are the virtual page number & the physical frame number the same for this page in this lab?
6. What are the values of IAR and MEAR?
7. How will you design the kernel/user mode indicator so that interrupts are allowed to occur during interrupts? In other words, how do you really know when to switch back to user mode after servicing an interrupt?