Operating Systems Lecture Notes

2014 October 28 • Basic Paging

Outline

Demand paging.
No free page frames.
- Page faults, paging candidates.
Demand paging costs.
Reducing costs.
- Smarter page replacement algorithms.

The Whole Process

The whole process address space is loaded for execution.
- Be it one big segment, or lots of little ones.
This is slow and wasteful.
- Non-paged allocation failures.
- Not all code and data needed all the time.
  - Initialization, termination, and error code.
Dynamic loading shows the way: bring it in when you need it.

Demand Paging

Remember the page-table entry validity bit?
- The page-frame entry is valid iff the validity bit is set.
An invalid page-frame entry means the page pn_i is not in primary store.
Accessing a page not in primary store (with an invalid page-table entry) raises a page-fault interrupt.

Page Faults

The OS goes to work when a page-fault interrupt occurs.
1. Get an empty page frame.
2. Read the page into the frame.
3. Set the page-table entry.
4. Restart the process at the instruction causing the fault.
As usual, complications ensue.

Faulting Instructions

The instruction fetch can page fault.
An instruction can page fault when accessing a primary-store operand.
- Up to three page faults for three-operand instructions.
Each access can cause two page faults.

Free Page Frames

Allocating a free page frame requires knowing which page frames are free.
- A page-frame free list
The free list can be a bit map.
- The ith bit is set iff the ith page frame is free.
- Fast, efficient search, compact representation.

Bit-Map Example

Assume 8 Gb (= 2³³ bytes) primary store, 4 kb (= 2¹² bytes) page size.
- 2³³/2¹² = 2²¹ page frames, 2 million or so.
Assume 8 (= 2³) bit units.
- The free-list bit map is 2²¹/2³ = 2¹⁸ bytes, about a quarter-million bytes.
Modern ISAs support instructions that search for 1 bits.

Linked Free List

For reasons that will be clear soon, a bit-mapped free list is inconvenient.
Assume a linked free list instead.
- This list requires four bytes for the list head.
- The free page frames are the links.
As a practical matter, the free list will have to be a page-frame table.
- A bit-mapped free list is a page-frame table with one-bit entries.

Page-Frame Allocation

Allocating a free page frame is easy.
- Unless there aren’t any.
If there are no free page frames, create one:
1. Select an occupied page frame.
2. Eject (page out) the old page.
3. Read in (page in) the new page.
This is page replacement.

Paging Out

The ejected page is written to the swap or paging area on disk.
- A disk partition optimized for page and process image transfer.
- Note the page-space allocation problem.
The page’s page-table entry must be updated.
- Invalidate the entry.
- Indicate where the page is.

Paging In

The incoming page is read from the
- executable image in the file system if new, or
- the swap disk if previously paged out.
- The page-table entry determines which.
Update the page-table entry.
- Validity and location have changed.

Page Replacement

“Free page frames are all alike; every occupied page frame is occupied in its own way.” — Tolstoy.
A page-replacement algorithm is responsible for selecting the page to be sacrificed.
Assume a random page-replacement algorithm.
- A perfectly workable algorithm.
- Ignores available information; effective, but not efficient.

Paging Costs

The paging cost is the extra time it takes.
- The time to
  handle the page fault
  + page out
  + page in
  + instruction restart
  assuming one page fault per instruction.

Page-Fault Rates

The page-fault rate ρ is
ρ = page faults/total storage references
- 0 ≤ ρ ≤ 1.
ρ is the probability that a primary-store access causes a page fault.

Effective Access Time

If
s = time to access primary storage
f = page-fault handling time
then the effective access time (EAT) is
EAT = (1 - ρ)s + ρf
EAT is the expected value of the primary-store access time.

Cost Example.

Handling page faults takes a low 100s of instructions.
Paging I-O takes about 4 msec in each direction.
Instruction restart takes a low 10s of instructions.
Paging I-O time dominates the cost.
A primary-store access takes 200 nsec.

Cost Example..

Let s = 200 nsec, f = 8 msec = 8·10⁶ nsec.

EAT = (1 - ρ)s + ρf

= s + ρ(f - s)

= 200 + ρ(8·10⁶ - 200)

≈ 200 + ρ8·10⁶ nsec.
If ρ = 0.001 (1 page fault in 1,000 accesses)
EAT = 200 + 0.001·8·10⁶ nsec ≈ 8 μsec.
a ×40 increase in primary-store access time.

Cost Example...

Suppose you don’t want to pay for more than a 5% reduction.
EAT = 200 + 200(0.05) = 210 nsec.
then

210 = 200 + ρ8·10⁶

ρ = 10/(8·10⁶)

= 0.000 002 625

or about 1 page fault in every 381,000 primary-store accesses.

Low Hanging Fruit

Some pages are unchanged since page-in.
- Read-only (code, constant) pages.
- Read-write pages that haven’t been written.
Unchanged pages don’t have to be paged out.
Add a modified bit to page-table entries.
Initially unset, the modify bit is set on every page write.

Favoring Unchanged Pages

Call the page replacement algorithm a small, constant number of times.
If it returns a page frame with an unmodified page, use that frame.
Otherwise use the last frame returned.
An unchanged-page bias is effective in proportion to the ratio of unchanged to changed pages.
- But it's cheap to implement.
- And disk I-O is so expensive.

Reducing ρ

A page replacement algorithm should select pages to reduce the page-fault rate ρ.
- Have more non-faulting store accesses between successive page faults.
The best page to eject is the page never accessed again.
What's the next best page?

p no: 0 1 2 …

next access: 4,947 15,543 18,056 …

Optimal Page Replacement

The best page-replacement algorithm possible:
- Always eject the page accessed furthest in the future.
- The longest left alone (LLA) page-replacement algorithm.
For example,

Approximating LLA

Unfortunately, LLA has no a priori implementation.
- It does have a posteriori implementations.
- Trace-driven evaluation.
What about good approximations to LLA?

Page Age

Long-residing pages are probably useless and won't be accessed again.
- Pages with initialization code and data.
Eject the longest-residing page.
A queue of allocated (or re-allocated) page frames.
- Newly (re-)allocated page frames at the tail.
- The oldest pages at the head.

FIFO Page Replacement

FIFO page replacement is the age-based approximation to LLA.
For example:

a fifo execution trace

Same page reference sequence as the LLA example.
Twice as many page replacements (6 vs 12).

A Better Age Approximation

Raw age is a bad approximation to LLA.
- It does not account for access patterns.
Eject the page that has been longest unaccessed (read or write).
- The mirror image of LLA.
For example:

LRU Replacement

Least recently used (LRU) page replacement approximates LLA with longest unreferenced.
Finding LRU pages.
- Add a reference-time field to each page-frame table entry.
  - Requires a table search.
- Move each referenced page to the head of the page-frame queue.
  - LRU pages at the tail.

Approximating LRU

Implementing LRU is expensive.
- A requeuing on every page access.
- A table search for ejectable pages.
Hardware usually provides at best partial support.
- A modified bit per page, set on page access.
Need a cheap approximation to LRU.
- Which is an approximation of LLA.

Second-Chance Replacement

Scan the queue starting from the end of the last search.
- If the page is referenced, clear the reference bit, go on to the next page.
- If the page is unreferenced, end the search and replace this page.
- At the end of the queue continue the search at the head.
Second-Chance page replacement.
- Referenced old pages get a second chance.

Page Classes

The modify and reference bits together define four page classes.
- (¬M, ¬R): the best page to eject.
- (¬M, R): a good page to eject.
- (M, ¬R): a fair page to eject.
- (M, R): a poor page to eject.
Modify second-chance to look for a page in the most desirable class.

Summary

Demand paging exploits the opportunities opened up by logical addresses.
- But demand paging is ridiculously expensive.
Page replacement algorithms deal with freeing up page frames.
- Good replacement choices help mitigate paging costs.
The best replacement algorithm is impossible to implement.
- But motivates the search for approximations.

References

Anna Karenina by Leo Tolstoy, Signet Classics, 2005.

This page last modified on 2014 November 1.