Outline
- Page replacement.
- Paging.
- Page-frame allocation.
Page Replacement
- What happens when a page needs to be brought in from disk and there are
no open page frames?
- A resident page needs to be ejected to free up a page frame.
- The memory manager's page-replacement algorithm determines which
pages to eject.
Random Page Replacement
- Pick a page frame at random and eject the resident page.
- Simple and effective, but not too efficient.
- It may pick a heavily accessed page that will have to be paged in
again soon.
- This leads to excessive paging.
- For better replacement efficienty, take into account page accesses.
Future Page Access
- A page that will never be touched again is the best page to eject.
- Otherwise, eject the page that will remain untouched for the longest
time.
- It won't have to be paged in until sometime far into the future.
Optimal Page Replacement
- Always selecting the longest untouched page results in optimal
(minimal) paging behavior.
- Unfortunately, because optimal page replacement requires knowledge of
the future, it's impossible to implement.
- But maybe there's a good way to guess about future access patterns.
Least Recent Use
- Estimate future behavior from past behavior.
- A page that hasn't been accessed probably won't be accessed.
- Eject the page that has been unaccessed the longest.
- This is known as Least Recently Used (or LRU) replacement.
LRU Selection
- Each page frame has a variable set with the system clock value on each
access.
- When necessary, eject the page in the frame with the smallest clock
value.
LRU Estimation
- LRU replacement works well, but is expensive.
- It requires bits per page frame to keep time, and comparisons to
select the oldest untouched.
- Many LRU estimators needing fewer clock bits (sometimes only one) and
comparisons.
- These are usually still expensive because the clock bits have to be
handled by OS software and not hardware.
Queue LRU Estimating
- The queue is a simple and common LRU estimator.
- A page access brings the page to the head of the queue.
- Unaccessed pages sink to the end of the queue.
- A sampling rate (every nth access) reduces the need to requeue
on every access.
Second-Chance Queuing
- Sampling may cause accessed pages to sink to the end of the queue.
- Assign each page a second-chance bit, initially 0.
- If the end-page second-chance bit is 1, eject it.
- If the end-page second-chance bit is 0, requeue it and set the
second-chance bit to 1.
- The second-chance bit is cleared whenever the page is accessed.
Clock replacement
- Rather than maintain a queue of pages, form them into a ring and use a
pointer to mark the head of the queue.
- A trailing second hand can serve as the second-chance bit scanner,
speeding up the rate at which pages are ejected.
- The angle between the head and second scanner is a parameter of the
algorithm.
Page I-O
- An unmodified page selected for ejection can be overwritten.
- There's another copy of the page on disk.
- If the selected page has been modified (is a dirty page), it must
be written to disk to save the modifications.
- Page-selection algorithms should be biased towards unmodified pages.
Paging Areas
- Dirty pages cannot be written back to the files from which they came.
- There may be several processes using the program, and so more than
one copy of the modified page.
- Modified pages are written to a special file system called the
paging (or sometimes swapping) area.
- The paging area is a special-purpose file system designed to provide
fast page IO.
- Regular files can also be paging areas too, with decreased IO
efficiency.
Page-Frame Allocation
- How many page frames should a process get?
- Local page-frame allocation partitions the page frames among
processes.
- Each process gets a subset of non-shared page frames.
- When each process uses fills its allotment of page frames, paging
begins.
- Local allocation is fair but potentially wasteful; poor allocation
decisions may lead to excessive paging or unused page frames.
Global Allocation
- Global page-frame allocation makes all page frames available to
all processes.
- Each process gloms on to as many page frames as it can.
- Paging begins when all page frames are occupied.
- Global allocation achieves better utilization (fewer unused page
frames), but may cause a form of extreme paging known as thrashing.
Static vs. Dynamic Allocation
- Static page-frame allocation allocates a fixed and unchanging
number of pages at process start.
- Dynamic page-frame allocation allows the number of allocated page
frames to change with process behavior.
Process Working Sets
- An executing process accesses some number of pages within the past
t time units.
- The set of pages recently accessed is the process's working set.
Working Set Bias
- It is useful to bias page selection and page-frame allocation by a
process's working set.
- Allocate (or maintain) enough page frames to cover a process's
working set and a little more.
- Eject pages not in a process's working set.
Working Set Parameters
- The size t of the sample interval is the main working-set
parameter.
- A multiplicative fudge factor for the working set size
a*WorkingSetSize) is another parameter.
Paging Rates
- The paging rate is measured in page-movement per unit time (pages
per second, usually).
- Paging effectiveness is measured relative to page rates.
- If the paging rate is too high, thrashing results.
- If the paging rate is too low, the system is under-utilized.
Paging-Rate Adjustments
- Page rate adjustments can be made by varying the number of processes or
adjusting the working-set parameters (or both).
Swapping
- Swapping moves whole processes to disk.
- Swapping can be used to recover from thrashing.
- Locally thrashing or globally active programs can be swapped out,
removing the offender and freeing up page frames.
- The offender can be swapped (or paged) back in when the system
stabilizes.
This page last modified on 19 November 2004.