Outline
 - Virtual Memory
 - Project 2
Next week
 - Homework (graded) on virtual memory
 - Bring your questions on project 2

First, we discussed address translation concepts.
Given 4KB page size = 2^12 => need 12 bits to index into the page
32-12 = 20 bits left for page numbers => 2^20 is the size of the address space

We discussed how you would translate a virtual address into a physical address.
You take that virtual pagenum and use is an index into the page table. From 
the page table you will retrieve a physical page number. To generate a 
physical address, you use the offset from the virtual address to index into
the physical page.

"Clock": page replacement algorithm
First, we talked about how you would build a clock queue. Asssume you have
8 physical pages (eg., P0-P7). For each memory page you can keep track of 
whethere the page is free or not. Assume you have a client application that 
will create and access 9 pages (eg., V0-V8). 
main () {
  char *a, *b, *c, *d, *e, *f, *g, *h, *i;
  a = (char *)vm_extend();
  ....
  -- at this point, your pager will create one virtual page for this process.
  Let's call it V0. At some point, your pager would need to associate a 
  physical page with V0, say physical page P0. You will mark page P0 'taken'.
  Say, at this point P1 thru P7 are marked 'free'. Each occupied physical
  page should be on the 'clock queue'. I will write a clock queue as pairs of
  <virtual page, physical page> associations. Now, 
  clock_queue: <V0,P0>
  Where the head pointer points to the first element. 
 
  Assuming that 7 more pages were created and at some point associated with
  other physical pages. As the result, all physical pages would be marked as
  'taken'. Clock queue would have 8 elemenets in it, say:
  clock_quque: <V0,P0>, <V1,P1>, <V2,P2>,.... <V7,P7> 
  The head of the queue still points to the first element.

  Assume that the client application asks of one more page and at some point
  you need to associate the new virtual page with a physical page. However,
  after checking your memory resources (eg., bitmap), you find that no more
  free pages are available and you need to evict one of the pages! This is
  when you need run a clock page replacement algorithm.

evict() {
  bool done = false
  while(! done) // iterate through a clock qeueu
    if the reference bit of the page we are inspecting is 0
      found the victim page
      done = true
      now do things to the page and evict it
    else
      set the reference bit to 0
}  

Remember that dirty and clean pages are treated the same. We only look at
the reference bit.

Next, we went over the infrastructure
First, you start the pager. vm_init() is called.
Then, you start the client. At the pager side, vm_create() and vm_switch() 
is called.
Say, client calls vm_extend(), increases the size of this process valid
address space. Now, the client can do read/write access in the memory that
was returned by a = (char *) vm_extend(). 
eg., you are do a read operation on the page by doing
  cout << a[0];  you can also do vm_syslog(a, 1); 
  to write, you can do a[0] = 'h'.
Then we discussed how some operations will generate page fault, thereby,
invoking vm_fault() at the pager. However, some memory accesses should *not*
generate page faults. We went over examples. When a page fault is not 
generated, the MMU simply translates a suplied virtual address into a physical
address and accesses memory (doing either a read from memory or write into
memory). 

Next, we went over address spaces
vm_create() creates a process which includes creation of an address space 
for that process. We noted that there are always two areas of the address 
space that is always invalid: one below the vm_arena_baseaddr and above the 
top of the arena. On creation even the middle is invalid. A process has its 
own address space. Each process has its own page_table_t (page table that
keeps track of valid virtual-to-physical address translations).
struct page_table_t {
  unsigned int ppage : 30; /*physical page num*/
  unsigned int read_enable : 1 ; /* these are the protection bits that you */
  unsigned int write_enable : 1; /* need to set to generate page faults */
}

You access memory through "pm_physmem" pointer. eg., pm_physmem[0] is looking
into location 0. You don't need to allocate memory for it, infrastructure 
does this for you. However, you are in charge of the content of memory
(initializing, reading from, and writing to that variable).

You access disk through functions disk_read() and disk_write(). Like memory,
you are responsible for content.

Next we looked at data structures:
What do you need to know about a virtual page {
  int resident;
  int dirty;
  int referenced;
  protection bits;
  physical page this virtual page resides if in memory
  disk location 
  ... others? we talked about this in discussion
}

This about when do you need to assign a physical page number to a virtual
page. Think about the example of a page that was created but never used.
We discussed assignment of a disk block. The section 5.4 state: "vm_extend 
should ensure that there are enough valid disk blocks to hold *all* *valid*
virtual pages"..

what do you need to know about the process {
  unsigned int pid;
  page_table_t page_table;
  ... virtual pages...
}

what else?
  - keeping track of available resources: memory pages and disk blocks.
  - clock (per pager) that contains virtual-physical page associations
  (entries in the clock could come from different processes!).

Next, we talked about page faults
Why do they happen: residency and protection
  - access to a non-resident page 
    - pager has to bring non-resident page into memory
    - access is retried
    - retrieve context of memory and finally return return to the user
  - access to protected page
    - eg., write to read-protecte page r=1,w=0

Next, we went over each of the function you need to write
vm_init(num_mpage, num_dblocks)
  setup internal representation of memory and disk. eg., what's free.

vm_create(pid)
  create a new instance of a process
  create a page table so that this process can start doing address translations
  remember that process starts with no valid pages

vm_destroy()
  deallocate resource 
  release memory and disk that this process occupied
  ... 

vm_extend()
  extends the validity of address space by one page
  must ensure there is room on disk
  ....

vm_fault(vaddr, type)
  check if vddr is valid
  residency or protection fault?
    if not resident, make it
       find a free page
       no more free physical pages? evict -> run clock algorithm
       ...
    adjust protection 

vm_switch()
  what to do so that new process can do its address translations?

vm_syslog(vaddr, len)
  think of reading memory starting from vaddr and read 'len' bytes.