Quick Review of Virtual Memory

         On the address bus, between the CPU and the memory, there is some page translation hardware. For this description, imagine that the CPU produces 32 bit addresses, but the memory component is capable of accepting 36 bit addresses.
         The 32 bit address produced by the CPU is split into two portions, lets say 23 bits + 9 bits. The most significant 23 bits are treated as a page number, which gets translated by the hardware; the least significant 9 bits are an offset within that page, and are not modified, or even seen by the translator.
         The translator contains a large associative memory array: the incoming 23 bit "virtual page number" is instantaneously compared with each of the virtual page numbers already stored in the associative array. If it matches one of them, the 27 bit physical page number together with a few bits of protection information (e.g. Readable, Writable, Executable) that were associated with that virtual page number are output. The protection information is checked against the operation being performed, to see if it is legal, and if it is, the new 27 bit physical page number is recombined with the original 9 bit offset, to produce a 36 bit address that is used to access the memory 
     32 bit Virt Addr
        |||||||
        |||||||
        |||||||          9 bit offset
        |||||\\______________________________________________
        ||||| \______________________________________________\
        |||||                                                \\
        |||||                                                 ||
        |||||  |        Associative Array                     ||
        |||||  |   23 bit    |   27 bit    | Prot|            ||
        |||||  | Virt Pg Num | Phys Pg Num | RWX.|            ||
        |||||  -----------------------------------            ||
        +++++--+   123       |    4672     | ... +------++++++||
        |||||  -----------------------------------      ||||||||
        +++++--+     2       |      10     | ... +------++++++||
        |||||  -----------------------------------      ||||||||
        +++++--+    23       |    8455     | ... +------++++++||
        |||||  -----------------------------------      ||||||||
        +++++--+ 21579       |  287213     | ... +------++++++||
        |||||  -----------------------------------      ||||||||
        +++++--+  4232       |   23872     | ... +------++++++||
        |||||  -----------------------------------      ||||||||
        +++++--+    46       |   21872     | ... +------++++++||
        |||||  -----------------------------------      ||||||||
        +++++--+ 23210       |   12937     | ... +------++++++||
        |||||  -----------------------------------      ||||||||
        +++++--+  2311       |  234521     | ... +------++++++||
               -----------------------------------      ||||||||
                                                        ||||||||
                                                        ||||||||
                                                        ||||||||

                                                      36 bit phys addr
         In the illustration above, if the CPU tries to access memory location number 1055, that is split into VPN=2, Offset=31 (1055 = 2x29+31) The VPN of 2 is compared with all of the VPNs in the associative array, and a match is found on the second row so the PPN of 10, and the associated protection bits are output. If the protection bits indicate that the access is valid, the PPN is recombined with the Offset, to give a physical address of (10x29+31)= 5151, which is the address in memory that is accessed.
         The associative array consists of an incoming 23 bit wide virtual page number bus, whose contents are fed simaultaneously to a large number of comparators. Each of these comparators also receives input from a private 23 bit register. If the number on the bus exactly matches the number in the register, the comparators output is activated. This releases the contents of another private register (of at least 27 bits = physical page number + protection bits + "valid" bit) onto the outgoing 27 bit physical address bus if the valid bit is set to one. Simultaneously, the protection bits are examined by hardware; if they indicate that the current memory access is not permissible, an interrupt is caused and the access is aborted. 
      23 bit VPN
        input
        |||||
        |||||                                                 . . . .
        |||||       --------------          --------------    . . . . 
        |||||       | 23 bit Reg |          | 34 bit reg |    ||||||||
        |||||       ------+-------          ----+---------    ||||||||
        |||||             |                     |             ||||||||
        |||||             |                     |             ||||||||
        |||||        -----+-----            ----+-----        ||||||||
        +++++--------+ Compare +------------+ "gate" +--------++++++++
        |||||        -----------            ----------        ||||||\\
        |||||                                                 |||||| \\
        |||||              (repeated many times)              ||||||  \\
        . . .                                                 ||||||   \\
        . . .                                              27 bit PPN   Protection
                                                             output    bits checked
         If the virtual address had been 2049, that would be an offset of 1 within virtual page 4. VPN=4 does not appear in the associative array, so an interrupt would have been caused. This kind of interrupt is called a page fault.
         A page fault means that a virtual address couldn't be translated by the translation hardware. When one occurs, the operating system searches through its software copy of the current process' Virtual-to-Physical page map. If the required VPN is not present, that means that the process was trying to access unallocated memory, and a fatal run-time error is produced. (If the access was close to the end of the stack, it could be treated as an implicit request for more stack space).
         If the VPN is present, the OS finds from the table where that particular page resides. If it is in memory, the solution is simple (this is a soft page fault): the required VPN->PPN+prot mapping is added to the translation hardware's associative array, and the offending memory access is tried again.
         If the required page has been "paged out", and now resides on disc, the solution is much more complex (and we have a hard page fault). The required page must be read back into memory before the access can succeed. Reading the required page back into memory could necessitate swapping another page back out of memory to make room (if the process' quota is full).

Counting Page Faults

The following program is loaded into memory starting at location 200, and starts to run. How many page faults will occur if we have a maximum allocation of 2 pages of physical memory and use the Least Recently Used page replacement strategy? 
        MOV  1030, R1
        ADD  1042, R1
        MOV   766, R2
        ADD  1066, R2
        ADD  1776, R1
        ADD   901, R2
we will go through the program step by step below. Each memory address will be split into VPN and offset parts, so that when the question gave the instruction "MOV 1030,R1", it appears as "MOV (1030)2/6,R1" to indicate that address 1030 is offset 6 within page 2.
         We'll assume that the page translation hardware is completely empty at the beginning, and that the system is sensible enough to avoid swapping out the page that contains the instructions being executed.          After each instruction appears, we will see what happens, and list the pages that are in the working set when the instruction finishes. 
                MOV (1030)2/6, R1
first page 0 is brought in (the program has to be loaded before it can run, and address 200 is in page 0. Then page 2 is brought in to allow the access. = 2 faults.    Pages now in working set: [0,2] 
               ADD (1042)2/18, R1
page 2 already in. = 0 faults.    Pages now in working set: [0,2] 
                ADD (766)1/254, R1
page 1 brought in (2 paged out) = 1 fault.    Pages now in working set: [0,1] 
                ADD (1066)2/42, R1
page 2 brought in (1 paged out) = 1 fault.    Pages now in working set: [0,2] 
                ADD (1766)3/240, R1
page 3 brought in (2 paged out) = 1 fault.    Pages now in working set: [0,3] 
                ADD (901)1/389, R1
page 1 brought in (3 paged out) = 1 fault.    Pages now in working set: [0,1] Giving a total of 6 page faults.

What if we're allowed 3 pages of physical memory?
Start again... 
                MOV (1030)2/6, R1
first page 0 is brought in (the program has to be loaded before it can run, and address 200 is in page 0. Then page 2 is brought in to allow the access. = 2 faults.    Pages now in working set: [0,2,-] 
               ADD (1042)2/18, R1
page 2 already in. = 0 faults.    Pages now in working set: [0,2,-] 
                ADD (766)1/254, R1
page 1 brought in = 1 fault.    Pages now in working set: [0,2,1] 
                ADD (1066)2/42, R1
page 2 already in = 0 faults.    Pages now in working set: [0,2,1] 
                ADD (1766)3/240, R1
page 3 brought in (1 paged out, because it hasn't been used too recently) = 1 fault.    Pages now in working set: [0,2,3] 
                ADD (901)1/389, R1
page 1 brought back (2 paged out, because it was used least recently) = 1 fault.    Pages now in working set: [0,1,3] Giving a total of 5 page faults.

Now stick with three pages, but use the First In, First Out strategy. 
                MOV (1030)2/6, R1
first page 0 is brought in (the program has to be loaded before it can run, and address 200 is in page 0. Then page 2 is brought in to allow the access. = 2 faults.    Pages now in working set: [0,2,?] 
                ADD (1042)2/18, R1
page 2 already in. = 0 faults.    Pages now in working set: [0,2,?] 
                ADD (766)1/254, R1
page 1 brought in = 0 faults.    Pages now in working set: [0,2,1] 
                ADD (1066)2/42, R1
page 2 already in = 0 faults.    Pages now in working set: [0,2,1] 
                ADD (1766)3/240, R1
page 3 brought in (2 paged out because its been here the longest, except for page 0 which contains the code and is exempt) = 1 fault.    Pages now in working set: [0,1,3] 
                ADD (901)1/389, R1
page 1 already in = 0 fault.    Pages now in working set: [0,1,3] Giving a total of 3 page faults.