CS444 Class 20 x86 (32 bit) Paging

Handout: MMU Demo

Read Chap. 3 to pg. 194, esp. 189-194, then 3.3.3, TLBs, 3.3.4 multilevel page tables,

3.4 on page replacement algorithms, skipping 3.4.8,

3.6 through pg. 232, Linux pp. 758-762

Added 11/21: Sec 3.4.6: only need to read the first two paragraphs

Skip 3.4.7

Add pg. 887 x86 PTE bits

Sec. 10.4.4 Paging in Linux, to end of pg. 770, so you know PFRA is a clock-like algorithm that uses the page reference bit.

SAPC: See MMU Demo handout. If you missed the class, try out its steps yourself.

The SAPC has 4M of memory set up for use, i.e., one page table, and paging is turned on.  The SAPC’s one page table is at VA 52000 (in the Tutor area.)  We’ll use mdd to display 32-bit quantities nicely (md shows low byte first, mdd shows high byte first):  The 12 bits of the flags show up as the low 3 hex digits, marked ^^^ here, while the top 5 hex digits provide the pfn.

Tutor> mdd 52000

00052000    00000007  00001007  00002007  00003007

            -----^^^  -----^^^  -----^^^  -----^^^

              PTE0      PTE1      PTE2     PTE3

This shows that page 0 (VA 0 to VA fff) is mapped to pfn=0 (PA 0 to PA fff), page 1 (VA 1000 to VA 1fff) is mapped to pfn=1 (PA 1000 to PA 1fff), page 2 is mapped to pfn=2, and so on.  This is the identity mapping. VA = PA for every address, 0 to 0x3ffffff. Paging is turned on, but memory is being used just as if it wasn’t on.

In the demo, we showed the A and D bits in action.  If we do a read on page 0, for example “md 400”, the A bit will go on in PTE0, and if we do a write in page 0, “ms a00 66”, the D bit will go on. 

We were looking at the one page table (PT) for the 4M of memory of the SAPC.  It is located at VA 52000, in the Tutor area of memory.  Recall that we saw that normally for the SAPC, paging is turned on but the mapping is the identity map, so that page 0 of VA space maps to pfn 0, page 1 to pfn 1, and so on.  That means that VA = PA for all addresses on the SAPC, that is addresses 0 – 3fffff.

Demand Paging and the circulation of memory pages.

With demand paging, a program is not “loaded into memory”, but rather only mapped into memory.  PTEs with P=0 are set up for it, except for say one page of stack and possibly one page of code, which are given actual physical memory.

• When another page is referenced by the program, the P=0 in the PTE causes the MMU to initiate a page fault.  In the page fault handler of the kernel, the kernel fills in the page, using a page from its “free list.”  (This often requires reading a page from an executable file while the process is blocked.)  After the page itself is filled in, the kernel fills in the pfn in the PTE and sets P=1.  Then it gets the process to re-execute the instruction that caused the page fault.  More on this later.

• We see that the memory assigned to a process grows incrementally.  The pages of a process “age”.  Page “age” is the length of time since the last reference to the page.

• Old pages of a process are probably not as important to the program as the newer one, and can be removed, i.e., garbage-collected. That’s the underlying idea of “LRU” least-recently-used page replacement algorithm.  The removed pages are put on the free list.  If they are needed later, they can always be paged back in.

• Old pages that have been updated (“dirty”) are paged out to swap space before being “reclaimed”. Swap space is typically on disk (or SSD=solid state disk =flash).

We see that the pages go round and round in the system, spending time on the free list and then in some process image (or possibly in a page table or other kernel object—the kernel uses paging for some of its own data too.)

Tan. mentions the free list on pg. 769, as maintained by the page daemon.

Add this discussion to the reading list.

Page Age in theory and practice: the page reference bit (or A bit for x86).

The idea of page age is important to the understanding of good memory management, but when we look at a PTE, we don’t see a page age field.  All we see is a reference bit, denoted “R” in Chap 3, “A” in x86.  This tells us the page has been referenced since the last time A was set to zero.  This tiny clue is used by several important algorithms in actual use by OSs.

(Aside: However it is not in universal use.  According to Inside Window 2000 (pg. 460), Windows 2000 uses the A bit if it is running on a single processor, but not if it is running on a multiprocessor system.  Each of multiple CPUs has its own TLB, and to make setting A=0 effective, that vpn entry must be flushed from all those TLBs, an operation deemed not worth it.)

First A/R-bit algorithm: Clock algorithm, pg. 205.  Here the hand points to the oldest page in a sense, but not exactly the LRU sense.  It’s just the one that hasn’t been examined by this algorithm for the longest time as it cycled through the rest of the pages.  Although this is a low-cost algorithm, it isn’t in direct use because more complicated algorithms (which we won’t cover) works better using the same A/R bit.

LRU, the touchstone of page replacement algorithms—Sec. 3.4.6

• Can’t be done exactly with current MMUs, because they don’t track page age and the OS is not involved in each page reference, so the kernel doesn’t have the data it needs.
• However, is too expensive for use in OS’s, even if they had hardware page-age information.  Is used in database servers for buffer management. The database server does get involved in buffer memory references (in groups) through “pin buffer” and “unpin buffer” operations.
• Skip the hardware implementations in Tanenbaum—they are all unusable in practice, i.e., just read the first two paragraphs of Sec. 3.4.6.
• Is characterized as “Excellent” on pg. 215, but in fact is not that great. If you read a huge file once, all those pages look new and wipe out older pages in memory.