The +Paging Algorithm Technology Guide

The algorithm

Terminology

Paged memory (virtual addresses and their contents) +is called either:

'live', meaning present +in the cache of physical RAM, or
'dead', meaning stored +elsewhere in the backing store.

Physical RAM not being used to hold paged memory is called the free +pool.

Items of paged memory can be reassigned from 'live' to 'dead' +and vice versa. 'Live' items are classed as either 'old' or 'young' for this +purpose.

Paging +out memory

When more RAM is needed and the pool of free memory +is empty then RAM is freed up. This means changing an item of paged memory +from live to dead. The process is called paging out and it involves these +tasks.

The oldest virtual page +is removed from the cache and physically stored elsewhere
The MMU marks the virtual +page as inaccessible.
The associated page +of RAM cache is returned to the free pool.

Paging +in memory

When a program attempts to access dead paged memory, +the MMU generates a page fault and the executing thread is diverted to the +Symbian platform exception handler. This performs the following +tasks.

Obtain a page of RAM +from the free pool. If the free pool is empty, free up some memory by paging +out the oldest live page.
Read the contents of +the dead paged memory from its actual location (e.g. NAND flash) and write +them to the page of RAM.
Update the live list +described in the next section.
The MMU maps the linear +address of the dead paged memory on to the page of RAM.
Resume program execution.

The +paging cache

The paging cache is only useful if it is used to +hold the pages most likely to be required. The paging subsystem provides for +this by selecting the oldest pages to be paged out making space for new ones +to be paged in.

All live pages are stored in a list called the 'live +page list'. Live pages are labelled 'young' or 'old' and are stored in two +sub-lists, one for each type: the item at the start of the young list is the +youngest item and the one at the end of the old list is the oldest item. The +MMU makes young pages accessible to programs and old pages inaccessible. However, +old pages are different from dead pages because their contents are still held +in RAM.

The young and old lists are maintained in accordance with +these four rules.

When a dead page is +paged in (made live) it is added to the start of the young list, becoming +the youngest item.
When a live page must +be paged out (made dead) to free up RAM, the oldest page is selected.
If an old page is accessed +by a program a page fault results because old pages are marked inaccessible. +The paging system handles the fault by turning the page into a young page +('rejuvenating' it). To compensate, the oldest young page is then turned into +an old page ('aging' it).
Efficient operation +requires a stable ratio of young to old pages. If the number of young pages +exceeds a specified ratio of old pages, the oldest young page is turned into +the youngest old page ('aging' it).