I want to preface this discussion by saying that you are free to
implement the multiprogramming project in the way that you are most
comfortable with.  You _do not_ have to do it the way I suggest below;
there are many ways to implement the functionality in the project.  If
you want to do it a different way, you _do not_ have to send me email
asking if you can do it differently -- just go ahead and do it.  On
the other hand, if you want to do it differently, do not send me mail
asking me if the way you want to do it works.  You can answer that
question yourself: go ahead and try it.  Your debugging and test cases
will tell you whether it works or not (in other words, I am not your
debugger or test case).

The first step in the multiprogramming project is modifying the
AddrSpace class to support having multiple processes loaded into
memory at the same time.  So let's start by looking at what the
AddrSpace class does already and go from there.

The AddrSpace constructor currently performs the following steps:

1) Look in the executable header to figure out how large of an address
space needs to be created for this process.

2) Create a page table for as many pages are necessary to load the
program into the address space.  The page table is represented as an
array of TranslationEntries (PTEs) indexed by virtual page number.  A
physical page is allocated for each virtual page.

NOTE: This is the only interaction you need to have with
TranslationEntries and the TLB.  Once you get the AddrSpace created
and initialized, the MIPS machine simulator will use the page table to
do all translations.  In other words, don't worry about TLB misses,
etc., the MIPS simulator will take care of it.

3) Zero out the pages allocated for the address space.

4) Load the code and page sections from the executable file for the
program into the pages allocated for the address space.

Now let's see what needs to be changed to support multiprogramming:

-- Executable Header

Nothing needs to be changed here.

-- Creating Page Table

Right now, the page table just grabs physical pages.  So we need to
change it to ask a Memory Manager to allocate physical pages for it.
The Memory Manager will keep track of which physical pages are free
and which are allocated (see below).  The loop in AddrSpace looks
something like:

for () {
  pageTable[i].virtualPage = i;  // this sets the virtual page #
  pageTable[i].physicalPage = i; // this just grabs a physical page
  // initialize flags..

and we want to change it to use the Memory Manager to allocate
physical pages:

for () {
  pageTable[i].virtualPage = i;  // this sets the virtual page #
  pageTable[i].physicalPage = MemoryManager->AllocPage(...) // (see below)
  // initialize flags as before, no need to make changes

At this point, virtual page "i" maps to the physical page returned by
the MemoryManager.

-- Zeroing Out The Address Space

Right now, AddrSpace zeroes out the address space by writing null
bytes directly into physical memory without regard to the mapping of
virtual to physical pages (using the machine->mainMemory variable
directly; see the Q&A below).  With multiprogramming, you can no
longer do this so easily.  Instead, you need to (1) loop through each
virtual page and (2) zero out that page.

for (each virtual page) {
   get a pointer to the physical page by mapping the virtual page
   to the physical page; (see Q&A below)
   zero the physical page using the pointer to it;

-- Loading Code and Data into the Address Space

As with zeroing out the address space, the original version of
AddrSpace loads the code and data directly into physical memory
without regard to page boundaries or page mappings.  You need to
change this so that it pays attention to page boundaries and page
mappings.  So instead of being able to do it in one call, you will
have to do it one page at a time.  In other words, you will read from
the executable file a page a time, and write what you read into the
pages of the address space.

Be sure that you understand what is going on here.  What we're doing
is reading code and data from the executable file into the address
space for this process.  The offset to the code in the executable file
is specified by the "noffH.code.inFileAddr" field of the executable
header.  The size of the code (number of bytes) is specified by
"noffH.code.size".  And the code is supposed to be loaded at virtual
address "noffH.code.virtualAddr".

Since the code and data is specified to be loaded at a virtual
address, you need to translate the virtual address into a physical
address (a pointer inside machine->mainMemory) before you can do this.

For example, let's say you want to read the second page of code from
the executable file into the process' address space.  The executable
file offset for the second code page is "noffH.code.inFileAddr + (2 *
PageSize)".  And this needs to get loaded at virtual address
"noffH.code.virtualAddr + (2 * PageSize)".  And the amount of data
that we'll read from the executable file is "PageSize").  Before we
can actually call ReadAt to do the read, we need to convert the
virtual address into a physical address (into a pointer into
machine->mainMemory).  See the Q&A below.

You need to do this for every page of code and every page of data in
the executable file.  A psuedo-code loop for doing this is:

while (still code (or data) in executable file) {
  file_off = determine current offset into executable file;
  virt_addr = determine the virtual address that the code gets loaded at;
  phys_addr = convert the virt_addr to a physical address (a pointer
              into machine->mainMemory) using your page table;
  size = PageSize;
  executable->ReadAt(phys_addr, size, file_off) 

Note that the virtual addresses where the code and data get loaded
(e.g., noffH.code.virtualAddr) do not necessarily fall on page
boundaries, and that the size of the code and data is not necessarily
a multiple of a page.  This will make your implementation a little
messier than the loop above suggests.

* Handling Errors

Note that you could easily run out of memory, in which case you will
want to return an error.  As described in the project description, you
will want to move most of the code in the AddrSpace constructor into a
new method so that you can return error values.

* Memory Manager

The role of the Memory Manager is to keep track of allocated and free
physical memory pages.  You can use any data structure you want to
implement this.  The project writeup suggests the use of the Table
class, which you can reuse for later parts of the project.  Note that
the Table class is a generic data structure -- it just allocates slots
and fills them with opaque values (void *).  It does a little more
than what the Memory Manager actually requires of it, so don't be
confused if you don't use its full functionality (e.g., storing
pointers).  Since the Table class is generic, it shouldn't know
anything about memory or address spaces or pages, etc.  It just
allocates and frees table slots, and stores pointers into allocated

You define the interface to the Memory Manager (such as the names of
the methods, and their arguments).  You don't have to name it
MemoryManager, and you don't have to have a method named exactly
AllocPage.  There is no one right way to do this.  Just do what works
for you.

* Q&A

Q: How is physical memory represented?

Physical memory is modeled using an array of bytes referenced using
the "machine->mainMemory" variable.  You should think of
machine->mainMemory as being partitioned into "physical pages".  There
are "NumPhysPages" of such pages, and each page has size "PageSize"
(both of these are defined in machine.h).  Hence, the size of
machine->mainMemory is "NumPhysPages * PageSize".

Q: How do I reference a page in "physical memory"?

Pages in physical memory are referenced using offsets into the
"machine->mainMemory" array.  For example, let's say you want to
reference page 3.  Page 3 has a "physical address" of "3 * PageSize",
and therefore begins at machine->mainMemory[3 * PageSize].  To get a
pointer to Page 3, you would take its address: &machine->mainMemory[3
* PageSize].