There will be 10 numbers stored contiguously in the computer at location x 7000 . Write a complete LC-3 program, starting at location x3000, that will find the location of the smallest number and swap its location with the number in location x7000. For example, Suppose the following numbers are stored at location x7000:

The LC-3 (Little Computer 3) is an ISA definition for a 16-bit computer. Its architecture includes physical memory mapped I/O via a keyboard and display; TRAPs to the operating system for handling service calls; conditional branches on N, Z, and P condition codes; a subroutine call/return mechanism; a minimal set of operation instructions (ADD, AND, and NOT); and various addressing modes for loads and stores (direct, indirect, Base+offset, PC-relative, and an immediate mode for loading effective addresses). Programs written in LC-3 assembler execute out of a 65536 word memory space. All references to memory, from loading instructions to loading and storing register values, pass through the get Mem Adr() function. The hardware/software function of Project 5 is to translate virtual addresses to physical addresses in a restricted memory space. The following is the default, pass-through, MMU code for all memory references by the LC-3 simulator.

unsigned short int get Mem Adr(int va, int rwFlg)

{

unsigned short int pa;

// Warning: Use of system calls that can cause context switches may result in address translation failure

// You should only need to use gittid() once which has already been called for you below. No other syscalls

// are necessary.

TCB* tcb = get TCB();

int task RPT = tcb [gettid()].RPT;

pa = va;

// turn off virtual addressing for system RAM

if (va < 0x3000) return &memory[va];

return &memory[pa];

} // end get MemAdr

Simple OS, Tasks, and the LC-3 Simulator

We introduce into our simple-os a new task that is an lc3 Task. An lc3 Task is a running LC-3 simulator that executes an LC-3 program loaded into the LC-3 memory. The memory for the LC-3 simulator, however, is a single global array. This single global array for memory means that alllc3 Tasks created by the shell use the same memory for their programs. As all LC-3 programs start at address 0x3000 in LC-3, each task overwrites another tasks LC-3 program when the scheduler swaps task. The LC-3 simulator (lc3 Task) invokes the SWAP command every several LC-3 instruction cycles. This swap invocation means the scheduler is going to be swapping LC-3 tasks before the tasks actually complete execution so over writing another LC-3 task's memory in the LC-3 simulator is not a good thing.

You are going to implement virtual memory for the LC-3 simulator so up to 32 LC-3 tasks can be active in the LC-3 simulator memory without corrupting each others data. To implement the virtual memory, we have routed all accesses to LC-3 memory through a get Mem Adr function that is the MMU for the LC-3 simulator. In essence, we now have a single LC-3 simulator with a single unified global memory array yet we provide multi-tasking in the simulator for up to 32 LC-3 programs running in their own private address space using virtual memory.

We are implementing a two level page table for the virtual memory in this programming task. A two level table relies on referring to two page tables both indexed by separate page numbers to complete an address translation from a virtual to a physical address. The first table is referred to as the root page table or RPT for short. The root page table is a fixed static table that always resides in memory. There is exactly one RPT per LC-3 task. Always.

The memory layout for the LC=3 simulator including the system (kernel) area that is always resident and non-paged (i.e., no virtual address translation).

The two figures try to illustrate the situation. The lower figure below demonstrates the use of the two level page table. The RPT resident in non-virtual memory is first referenced to get the address of the second level user page table or (UPT) for short. The right figure in purple and green illustrates the memory layout more precisely. Anything below the address 0x3000 is considered non-virtual. The address space is not paged. The memory in the region 0x2400 through 0x3000 is reserved for the RPTs for up to thirty-two LC-3 tasks. These tables are again always present in memory and are not paged. Accessing any RPT does not require any type of address translation.

The addresses that reside above 0x3000 require an address translation. The memory area is in the virtual address space of the program. This virtual address space means that a UPT belonging to any given task is accessed using a virtual address. You must use the RPT in the system memory to keep track of the correct physical address for the UPT location. Once you have the physical address of the UPT you can complete the address translation by finding the data frame and combining it with the page offset to arrive at your final absolute physical address.

A Two-level page table for virtual memory management.

x7000 123F x7000 0042

x7001 6534 x7001 6534

x7002 300F x7002 300F

x7003 4005 after the program is run, memory x7003 4005

x7004 3F19

Explanation:

LC-3 Processor:

The LC-3 (Little Computer 3) is an ISA definition for a 16-bit computer. Its architecture includes physical memory mapped I/O via a keyboard and display; TRAPs to the operating system for handling service calls; conditional branches on N, Z, and P condition codes; a subroutine call/return mechanism; a minimal set of operation instructions (ADD, AND, and NOT); and various addressing modes for loads and stores (direct, indirect, Base+offset, PC-relative, and an immediate mode for loading effective addresses). Programs written in LC-3 assembler execute out of a 65536 word memory space. All references to memory, from loading instructions to loading and storing register values, pass through thegetMemAdr() function. The hardware/software function of Project 5 is to translate virtual addresses to physical addresses in a restricted memory space. The following is the default, pass-through, MMU code for all memory references by the LC-3 simulator.

Simple OS, Tasks, and the LC-3 Simulator

We introduce into our simple-os a new task that is an lc3Task. An lc3Task is a running LC-3 simulator that executes an LC-3 program loaded into the LC-3 memory. The memory for the LC-3 simulator, however, is a single global array. This single global array for memory means that alllc3Tasks created by the shell use the same memory for their programs. As all LC-3 programs start at address 0x3000 in LC-3, each task overwrites another tasks LC-3 program when the scheduler swaps task. The LC-3 simulator (lc3Task) invokes the SWAP command every several LC-3 instruction cycles. This swap invocation means the scheduler is going to be swapping LC-3 tasks before the tasks actually complete execution so over writing another LC-3 task's memory in the LC-3 simulator is not a good thing.

You are going to implement virtual memory for the LC-3 simulator so up to 32 LC-3 tasks can be active in the LC-3 simulator memory without corrupting each others data. To implement the virtual memory, we have routed all accesses to LC-3 memory through a getMemAdr function that is the MMU for the LC-3 simulator. In essence, we now have a single LC-3 simulator with a single unified global memory array yet we provide multi-tasking in the simulator for up to 32 LC-3 programs running in their own private address space using virtual memory.

We are implementing a two level page table for the virtual memory in this programming task. A two level table relies on referring to two page tables both indexed by separate page numbers to complete an address translation from a virtual to a physical address. The first table is referred to as the root page table or RPT for short. The root page table is a fixed static table that always resides in memory. There is exactly one RPT per LC-3 task. Always.

The memory layout for the LC=3 simulator including the system (kernel) area that is always resident and non-paged (i.e., no virtual address translation).

The two figures try to illustrate the situation. The lower figure below demonstrates the use of the two level page table. The RPT resident in non-virtual memory is first referenced to get the address of the second level user page table or (UPT) for short. The right figure in purple and green illustrates the memory layout more precisely. Anything below the address 0x3000 is considered non-virtual. The address space is not paged. The memory in the region 0x2400 through 0x3000 is reserved for the RPTs for up to thirty-two LC-3 tasks. These tables are again always present in memory and are not paged. Accessing any RPT does not require any type of address translation.

The addresses that reside above 0x3000 require an address translation. The memory area is in the virtual address space of the program. This virtual address space means that a UPT belonging to any given task is accessed using a virtual address. You must use the RPT in the system memory to keep track of the correct physical address for the UPT location. Once you have the physical address of the UPT you can complete the address translation by finding the data frame and combining it with the page offset to arrive at your final absolute physical address.

This model of having a portion of memory that is not part per se of the virtual address space is not all that unusual. In fact, the lower region of the address space can by thought of as system space where kernel data structures reside. As such, it can be accessed directly without the need for the address translation. Remember, however, that anything above 0x3000 must pass through address translation.

A Two-level page table for virtual memory management.

x7000 123F                                                                            x7000 0042

x7001 6534                                                                            x7001 6534

x7002 300F                                                                            x7002 300F

x7003 4005                after the program is run, memory x7003 4005

x7004 3F19