|
1 <?xml version="1.0" encoding="utf-8"?> |
|
2 <!-- Copyright (c) 2007-2010 Nokia Corporation and/or its subsidiary(-ies) All rights reserved. --> |
|
3 <!-- This component and the accompanying materials are made available under the terms of the License |
|
4 "Eclipse Public License v1.0" which accompanies this distribution, |
|
5 and is available at the URL "http://www.eclipse.org/legal/epl-v10.html". --> |
|
6 <!-- Initial Contributors: |
|
7 Nokia Corporation - initial contribution. |
|
8 Contributors: |
|
9 --> |
|
10 <!DOCTYPE concept |
|
11 PUBLIC "-//OASIS//DTD DITA Concept//EN" "concept.dtd"> |
|
12 <concept id="GUID-7A50630B-2B44-5D27-AA18-3BEEE1453020" xml:lang="en"><title> The |
|
13 Paging Algorithm Technology Guide</title><shortdesc>Describes the paging algorithm used in demand paging.</shortdesc><prolog><metadata><keywords/></metadata></prolog><conbody> |
|
14 <section id="GUID-0F07152A-5469-463B-8BEE-71170A920B19"><title>Purpose</title> <p>Kernel |
|
15 side developers will sometimes need to know the algorithm used to move data |
|
16 in and out of paged memory. </p> <p><b>Intended |
|
17 Audience:</b> </p> <p>This document is intended to be read by kernel side |
|
18 developers. </p> </section> |
|
19 <section id="GUID-55C2239D-C351-4081-96F8-CAF1538B4BE3"><title>The algorithm</title> <p><b>Terminology</b> </p> <p>Paged memory (virtual addresses and their contents) |
|
20 is called either: </p> <ul> |
|
21 <li id="GUID-8533664E-057B-57EF-8A24-4BA7D3B4EC75"><p>'live', meaning present |
|
22 in the cache of physical RAM, or </p> </li> |
|
23 <li id="GUID-057D65C6-27D2-5BDD-B5CD-081808CCF44D"><p>'dead', meaning stored |
|
24 elsewhere in the backing store. </p> </li> |
|
25 </ul> <p>Physical RAM not being used to hold paged memory is called the free |
|
26 pool. </p> <p>Items of paged memory can be reassigned from 'live' to 'dead' |
|
27 and vice versa. 'Live' items are classed as either 'old' or 'young' for this |
|
28 purpose. </p> <p><b>Paging |
|
29 out memory</b> </p> <p>When more RAM is needed and the pool of free memory |
|
30 is empty then RAM is freed up. This means changing an item of paged memory |
|
31 from live to dead. The process is called paging out and it involves these |
|
32 tasks. </p> <ol id="GUID-20C35CC3-0845-51A8-B3C0-0F542E0570DF"> |
|
33 <li id="GUID-42AC538A-A676-5A7D-9DE3-FDE880E4A508"><p>The oldest virtual page |
|
34 is removed from the cache and physically stored elsewhere </p> </li> |
|
35 <li id="GUID-1FBD9975-97D5-50CA-8A2F-864B688C9AE4"><p>The MMU marks the virtual |
|
36 page as inaccessible. </p> </li> |
|
37 <li id="GUID-F8CDC9C1-C779-5D25-A16C-8BFC4B82B605"><p>The associated page |
|
38 of RAM cache is returned to the free pool. </p> </li> |
|
39 </ol> <p><b>Paging |
|
40 in memory</b> </p> <p>When a program attempts to access dead paged memory, |
|
41 the MMU generates a page fault and the executing thread is diverted to the |
|
42 Symbian platform exception handler. This performs the following |
|
43 tasks. </p> <ol id="GUID-3C52A214-F7FC-55CF-9346-16A4D7E8E37A"> |
|
44 <li id="GUID-B10392F3-D0CA-5C31-8A88-59E151661821"><p>Obtain a page of RAM |
|
45 from the free pool. If the free pool is empty, free up some memory by paging |
|
46 out the oldest live page. </p> </li> |
|
47 <li id="GUID-EA4E0F16-68D2-564D-B46E-5CB4CB515855"><p>Read the contents of |
|
48 the dead paged memory from its actual location (e.g. NAND flash) and write |
|
49 them to the page of RAM. </p> </li> |
|
50 <li id="GUID-5F9C3CEE-5836-5243-B84D-BA7795D0F056"><p>Update the live list |
|
51 described in the next section. </p> </li> |
|
52 <li id="GUID-A2A188F0-87EA-5403-8281-652AC52D41C3"><p>The MMU maps the linear |
|
53 address of the dead paged memory on to the page of RAM. </p> </li> |
|
54 <li id="GUID-F7A50A62-EBAD-50DD-B8F8-DAD42E598D02"><p>Resume program execution. </p> </li> |
|
55 </ol> <p><b>The |
|
56 paging cache</b> </p> <p>The paging cache is only useful if it is used to |
|
57 hold the pages most likely to be required. The paging subsystem provides for |
|
58 this by selecting the oldest pages to be paged out making space for new ones |
|
59 to be paged in. </p> <p>All live pages are stored in a list called the 'live |
|
60 page list'. Live pages are labelled 'young' or 'old' and are stored in two |
|
61 sub-lists, one for each type: the item at the start of the young list is the |
|
62 youngest item and the one at the end of the old list is the oldest item. The |
|
63 MMU makes young pages accessible to programs and old pages inaccessible. However, |
|
64 old pages are different from dead pages because their contents are still held |
|
65 in RAM. </p> <p>The young and old lists are maintained in accordance with |
|
66 these four rules. </p> <ul> |
|
67 <li id="GUID-ACB20E61-3467-56B4-8697-6DD6C79203FA"><p>When a dead page is |
|
68 paged in (made live) it is added to the start of the young list, becoming |
|
69 the youngest item. </p> </li> |
|
70 <li id="GUID-6B56324C-3A75-57C4-90E3-527994DAADFF"><p>When a live page must |
|
71 be paged out (made dead) to free up RAM, the oldest page is selected. </p> </li> |
|
72 <li id="GUID-EB5C43F4-1AC9-541F-8235-4DED9714B6F3"><p>If an old page is accessed |
|
73 by a program a page fault results because old pages are marked inaccessible. |
|
74 The paging system handles the fault by turning the page into a young page |
|
75 ('rejuvenating' it). To compensate, the oldest young page is then turned into |
|
76 an old page ('aging' it). </p> </li> |
|
77 <li id="GUID-366367C8-BBF3-59ED-9122-38112C6EA6FE"><p>Efficient operation |
|
78 requires a stable ratio of young to old pages. If the number of young pages |
|
79 exceeds a specified ratio of old pages, the oldest young page is turned into |
|
80 the youngest old page ('aging' it). </p> </li> |
|
81 </ul> </section> |
|
82 </conbody></concept> |