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

Sec 3.4.6: only need to read the first two paragraphs

Skip 3.4.7

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.

 

 

 

 

 

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.

 

Free list: List of pages the kernel can use when it needs memory. Needs continual replenishment by reclaiming pages.

Reclaim a page: remove a page of memory from a process VA space (or kernel data area), so its PTE P bit goes from 1 to 0. Reclaiming a dirty page: possible, but requires writing the page contents to swap space (a “page out” action).

Page replacement algorithm: decision algorithm for which pages to reclaim to keep the free list in good shape

Page age: time back to the last reference to a page. Mostly a theoretical concept, since current MMU hardware doesn’t track page age, only provides an R/A (Referenced/Accessed) bit.

 

Page Replacement Algorithms

 

Would like to reclaim “old” pages (large page age), since they seem to be less used than others, but MMU doesn’t track page age, just provides R/A bit.

 

Idea: Suppose “old” pages are ones with age > 30 min.

Algorithm: Clear the R bit in a group of pages, come back 30 min later, see which pages still have R=0, reclaim them. 

This is the basic idea of the Clock Algorithm, though it is entirely flexible on the time period.

 

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. The OS can clear the bit at 10:00am and if it’s still off at 11:00, conclude that the page is an hour old.

 

(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 in current Linux because more complicated algorithms (see below) work better using the same A/R bit.

 

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

 

If LRU isn’t excellent, what’s better?  I proposed and proved things about “LRU-K”, a LRU-family algorithm that tracks the last K references—it’s mentioned on the Wikipedia page on Page Replacement Algorithms!

 

Linux: PRFA described (confusingly) on pg 769-771 does use the A bit, and is part of Linux 2.6 and Linux 3.6, the current version (I checked the Linux sources—see links to online Linux kernel sources on the cs644 class web page).  Don’t worry about it in detail for this class, just remember that Linux has a page replacement algorithm that uses the R/A bit. I was interested because it looks like an approximation to LRU-K, not just LRU.

 

Android: Android uses a Linux process for each app execution, with virtual memory and demand paging, and a JVM on top of Linux VA space, but limits memory to (say) 48MB for a Java app. It doesn’t save user memory pages back to persistent storage, however, that is, it runs normally without swap space. Also, Android can throw a process out of memory when it determines that the memory is needed for a higher priority processes.  So an app has to store its own context somewhere to be ready to restart when the user returns to it. The app receives an onPause() event when it gets paused, at which point it should save its state, according to Gargenta, Learning Android, O’Reilly, p. 29.

 

Solaris uses a two-handed clock algorithm, but has responded to the problem of sweeps (at least those caused by file access) by using a priority system to keep balance between file access pages and process image pages.

 

Paging in practice: UNIX/Linux commands vmstat and uptime

You can see how many revolutions of the clock hand have happened on a Solaris system since the last reboot by “vmstat –s”, and how many days uptime by “uptime”.

 

Today: 39 revolutions of clock hand over 1370 days of uptime!  Not much need for pages over what is available through normal process exits, etc.

 

On Linux, vmstat -s shows a lot of stats, but not this one.

The 2-handed clock algorithm is executed by the page daemon, process 2 on “classic” BSD UNIX, now a kernel thread in Solaris and Linux.  But to keep up traditions, the kernel thread appears as process 2 “pageout” on Solaris.  (See it with “ps –ax|head” on ulab.)

Useful small article on vmstat from the Linux Journal.