The Paging Algorithm Technology Guide

Purpose

Kernel side developers will sometimes need to know the algorithm used to move data in and out of paged memory.

Intended Audience:

This document is intended to be read by kernel side developers.

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.

1. The oldest virtual page is removed from the cache and physically stored elsewhere

2. The MMU marks the virtual page as inaccessible.

3. 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.

1. 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.

2. Read the contents of the dead paged memory from its actual location (e.g. NAND flash) and write them to the page of RAM.

3. Update the live list described in the next section.

4. The MMU maps the linear address of the dead paged memory on to the page of RAM.

5. 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).