Tues., Nov. 21

Handout: vmstat on ulab amd blade71 (users.cs.umb.edu)

We looked at clock revolutions, #syscalls, #interrupts, #page faults Ulab is a lightly loaded system. blade71 shows more load, but is not seriously overloaded, unless the load was concentrated in a few days.

Paging in practice: UNIX commands vmstat and uptime

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

Handout: hw3 solution discussion, specifically how it executes.

Understanding the hw3 kernel, a multitaskinig kernel

 We see that process 1 gets to do all its output before any other process gets to do any output. It doesn't look like multitasking, but in fact it is. We have discussed this possible behavior before.  What's happening is that process 1 runs first and fills up the queue, then blocks and the scheduler chooses process 2 to run, but the queue is full, so process 2 blocks.  The scheduler then schedules process 3, but again the queue is full, so 3 blocks, and process 0 is scheduled.  A transmit interrupt happens while process 0 is running, causing a call to wakeup in which all 3 user processes are made ready.  The next time process 0 calls schedule, the scheduler finds process 1 is runnable, so chooses it.  And the whole sequence starts over for the next character.

We looked at the log string to confirm that the above story is accurate for system 1.

Modeling Page Replacement Algorithms, Page Faults

Sec. 4.5 Modeling Page replacement algorithms

The page fault rate gives us some info on how paging is doing. If you could run the same work load using two different algorithms and see a higher PF rate with one over the other, then the second would be superior. vmstat –s shows us info on this too:

Belady’s Anomaly, pg. 229. A strange case where adding memory increases the number of page faults, whereas we normally expect the opposite. The explanation is that a very poor page replacement algorithm is in use, FIFO (first in, first out.)

Idea of page reference string: 1, 2, 3, 2, 4 means (virtual) page 1 accessed, then page 2, then page 3, then 2 again, and finally page 4. Recall the idea that demand paging absolutely requires the system to bring in a referenced (virtual) page, as long as it is legitimately part of a process image. We don’t care where it is put in physical memory: all physical pages are the same, so we don’t mention the pfn in use.

FIFO for 3-page memory: 1, 2, 3, 4 would cause page 1, first in, to be dropped to allow 4 in. Sounds OK so far.

But 1, 2, 3, 1, 1, 1, 4 also drops page 1, not so good. A page accessed 4 times is more likely to be needed soon than one accessed only once, like page 3. Anyway, FIFO is not the best algorithm, so strange behavior using it is not too surprising.

Look at Fig. 4-24, pg. 229 to see the details of Belady’s algorithm.

Uses FIFO, a terrible page replacement alg.

Let’s try LRU on the same page reference string that shows Belady’s anomaly with FIFO:

0 1 2 3 0 1 4 0 1 2 3 4

0 1 2 3 0 1 4 0 1 2 3 4

0 1 2 3 0 1 4 0 1 2 3

0 1 2 3 0 1 4 0 1 2

P P P P P P P P P P

Here there are 10 PF’s, compared to 9 with FIFO. Note that the only difference in the P’s is the very last entry, where 4 was found in memory under FIFO but not under LRU. FIFO keeps 4 in memory in spite of its low reference rate just because it showed up last. And then it is “lucky” to have another reference to it that makes it look good.

Even a bad algorithm shines under the right circumstances. So Belady’s anomaly is not so mysterious, but it did have the effect of getting people to figure out what makes an algorithm well-behaved in this sense. This class of well-behaved algorithms are called Stack algorithms, defined on pg. 231, by sets of pages in memory at step r of a page reference string, the sets M(m, r) defined below.

System definition: See Tan., pg. 230, points 1., 2., 3..

Let M(m,r) = the set of pages in memory at step r of a reference string, where m = #pages of memory.

For ex., M(3,2) = {0, 1} in the Belady anomaly case, and also the LRU case above.

But M(3, 11) = {2, 3, 4} in the Belady anomaly case, but M(3, 11) = {1, 2, 3} in the LRU case above, so the reference to page 4 at the end (step r = 12) causes a page fault.

For a stack algorithm, M(m, r) is always a subset of M(m+1, r), i.e., one more page of physical memory can only cause additional virtual pages to be in memory, not drop any.

For the Belady sequence, M(3, 7) = {0, 1, 4}, but M(4, 7) = {1, 2, 3, 4}, and the first set is not a subset of the second because page 0 is in the first but not the second. Thus FIFO is not a stack algorithm.

LRU is a stack algorithm because for it, M(m, r) = the set of m pages of least page age. Clearly, M(m+1, r) = the set of m+1 pages of least page age, contains M(m,r). Recall the idea of page age = time back to the previous ref to this page. Here time is measured in references in the page reference string.

Full stack display, like Figure 4-25 for an 8-page memory. By showing the full ordering of pages by an algorithm on each step of a reference string, we can deduce the paging behavior (number of page faults) for any size memory. In the case of Figure 4-25, there could be anywhere from m=1 to m=8 pages of physical memory. The P’s there mark page faults for the case of m = 4.

Distance String. Each entry of a distance string is the depth in the full stack that page was pulled from, or infinity if it isn’t yet in the stack. Thus an entry of 4 means the page was at depth 4 in the just-previous stack.

We can show the full stack for the Belady reference string run with LRU, as follows:

0 1 2 3 0 1 4 0 1 2 3 4

0 1 2 3 0 1 4 0 1 2 3 4

0 1 2 3 0 1 4 0 1 2 3

0 1 2 3 0 1 4 0 1 2

0 1 2 3 3 3 4 0 1

2 2 2 3 4 0

Distance: ∞ ∞ ∞ ∞ 4 4 ∞ 3 3 5 5 5

With m = 3 pages of memory, all distances over 3 correspond to page faults. With m=4 pages of memory all distances over 4 correspond to page faults, and so on.

Note: ignore Figure 4-27: it has multiple numeric errors. If you understand the above analysis, that’s plenty on distance strings.

We have noted that OS/paging hardware doesn’t do LRU because it’s too expensive, but database systems use it for their buffering systems. Also that LRU isn’t perfect, and can be “fooled” by sweeps across data. Thus in database systems, a better algorithm would be welcome. I’ve done research on this, so let me show you how my LRU-2 algorithm works.

Optional Material—LRU-2.

This work is joint with 2 others, LRU-2 is LRU-K where K=2, the most useful case.

Ref: With Patrick E. O'Neil and Gerhard Weikum, "The LRU-K Page Replacement Algorithm for Database Disk Buffering", Presented at ACM SIGMOD Conference May 1993, Wash. D.C. and published in its Proceedings, May 1993.

LRU-2 age of a page = time to second-to-last reference.

M(m, r) = set of m-1 pages of least LRU-2 age not including the most recently referenced page, plus the most recently referenced page (which must be there even if it doesn’t qualify by its age.)

M(m+1, r) = set of m pages of least LRU-2 age not including the most recently referenced page, plus most recently referenced page, clearly includes M(m,r), so this is a stack algorithm.

Here’s the same Belady reference string running under LRU-2:

0 1 2 3 0 1 4 0 1 2 3 4

0 1 2 3 0⁴ 1⁴ 4^∞ 0³ 1³ 2⁷ 3 4

0 1 2 3^∞ 0⁵ 1⁵ 1⁶ 0⁴ 1⁴ 1 1

0 1 2^∞ 3^∞ 0⁶ 4^∞ 4^∞ 0⁵ 0 0

0 1^∞ 2^∞ 3^∞ 3^∞ 3^∞ 4^∞ 2 4

2^∞ 2^∞ 2^∞ 3^∞ 4 2

Distance: ∞ ∞ ∞ ∞ 4 4 ∞ 3 2 5 5 5

Here the LRU-2 ages are shown as superscripts. Look at how page 4 drops down past all the pages with finite LRU-2 age on the next tick after its first reference. Also how page 2, when finally re-referenced, drops down past more frequently-referenced pages. This algorithm isn’t “fooled” so easily by once-only referenced pages. This reference string is not at all “normal”, so the only thing to be learned here is how this works.

end of optional material