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