+----------+
                              | Project3 |
                              +----------+


For the second part of this project, when you start any process, you
do not allocate any physical pages (in proj2, you calculate the
numpages and got physical pages from the freepage list). Here, you
will simply initialize the page table with an array of
TranslationEntry (TE). Each TE has valid/dirty/vpn/ppn flags and
during initialization, you will need to set valid to false indicating
that the virtual page has no mapped pysical memory at this point of
time.

How to get a physical page?

Same as you did it in project2. But here even if there are no free
pages in the free page list, you still need to get a free page, but
how? You will need to swap a page P (may belong to some other process)
from the physical memory to the swap file. Once you swap P, you can
give P to the process waiting for a physical page and update the TE of
that process. In project3, a program is completely loaded into the
physical memory by a series of page faults and requests for physical
memory. Compare this is with project2 - for example, in proj2, we
allocated eight physical pages for stack right at the beginning. But
here, you will allocate the physical pages for stack only when there
is a fault and the PTE is invalid. So if your program never uses eight
stack pages, you save some memory here!

Which page to swap and how to swap a page?

You can run the clock algorithm to select a physical page to swap
out. Every time, this algorithm simply rotates around the pages in
physical memory using a pointer until it finds a page to swap
out. Once it finds a page, it remembers the pointer position so that
the next time when the algorithm is invoked, it can resume scanning
starting from the next page.

From wikipedia:
http://en.wikipedia.org/wiki/Page_replacement_algorithm#Clock "The
clock algorithm keeps a circular list of pages in memory, with the
"hand" (iterator) pointing to the last examined page frame in the
list. When a page fault occurs and no empty frames exist, then the R
(referenced) bit is inspected at the hand's location. If R is 0, the
new page is put in place of the page the "hand" points to, otherwise
the R bit is cleared. Then, the clock hand is incremented and the
process is repeated until a page is replaced"

Once the clock algo selects a page, before marking that page as free,
you need to clean up the page if needed. What is cleaning up? Read on.

You want to write the contents of the selected page to swapfile to
back that page for later use (swap in). Before you swap out a page
'P', you should ask the question whether it is really necessary to
write the contents of the page to the disk swapfile (using our
familiar filesystem api). Because, for some pages, the contents can be
retrieved from other sources. Which pages are they? Readonly pages or
unmodified pages. If the page you selected 'P' has readonly contents,
then you do not need to back that page because, later when needed, you
can get the contents from the .coff file. If 'P' is a stack page
(which is read/write), then check whether the dirty bit is set - it
indicates whether the content of the page is modified. If modified,
then you need to write P to swap file before marking P as free. Else,
you can simply invalidate the TE (of the process which owns it) and
hand over the physical page (no longer belongs to the process which
owned it).

But, when you decide to swap a page P out, you need to invalidate the
corresponsing TE in the PT of the process which owns P. But given
physical page P, how do you know the process owning it? For this you
need Inverted Page Table which is a datastructure that stores some
meta information for each physical page. At any time, this table knows
who owns each physical page.

A process can "pin" a physical page that it owns. Once a page is
pinned, it means, that page should not be swapped out and it should
stay in the memory until unpinned. While selecting a victim page to
swap out, we need to check whether the page is pinned. So what happens
when there are no free pages available and all the pages are pinned
meaning, we have to swap out a page but we do not have any eligible
pages. So the request for a physical page has to be delayed until
either a physical page becomes free or a page is unpinned.

Swapfile maintenance: 

You will use a single swap file for all processes. The unit of memory
that you will read/write is a page. When you write a page P to
swapfile, you should remember the Swap Page Number (spn) to which you
write to. Later, when P's contents are needed, using spn, you can read
from the contents starting at spn. StubFileSystem's read API which
accepts file cursor position comes handy to read from a particular
position. Like the free page list you maintained for the physical
pages, you can maintain a free page list for the swap file as
well. Whenever a page needs to be swapped out, you can request a page
from this free list. Also remember that, each virtual page can be
associated with only one swap file page and the swap file page can
be used throughout the lifetime of the process. Then how can a virtual
page remember it's corresponding spn? What about TranslationEntry.vpn?
Remember that the page table is already indexed by the virtual page
number. So why store redundant information already in the TranlationEntry
object. Why not use it to store the spn?  You can assume that the swap
file can be grown as needed and write a method to do it. But at the
same time, whenever there is a hole in the swap file, you should
re-use it.

Lazy loading:

Above we have seen how to get a physical pages (even when there are no
free pages!!). Once you get a physical page, how to load the
appropriate content into it? Stop here and compare to project2. In
proj2 we loaded a page only once at the beginning and the page stayed
in the memory throughout the lifetime of the process. But here, you
may need to load the same page multiple times - why? Because, if the
page is evited (can be simply evicted or swapped out and then evicted
if it was a dirty page), then it will not be in the physical memory.

What are the sources of the page content? Can be .coff file or swap
file. Basically when you start the program, you would not have any of
the pages in the swap file so you will load it from the .coff file
(and initialize stack pages to zero). But once the process progresses
and faults on a page (valid bit is false), after getting a free page,
you need to copy the required virtual page content to the free page
obtained. So you need to decide the source - if it is a readonly page,
you know you can get it from the .coff file (you need to know which
section of the coff section to load at the given virtual address). If
not, probably you can look at the TE.vpn to know whether to just fill
zeros (unaffected stack page) or to read the contents from the swap
file (for modified pages which are backed up in the swap file).