L4Re/departure

Annotated docs/wiki/Paging

465:8523b23738c1
384:1c4421a0046f
23 months ago Paul Boddie file changeset files shortlog Added PageMapper remarks and diagram.
paul@359 1 
= Paging =
paul@359 2 
 
 paul@359      3 
Within filesystem servers, a number of abstractions are combined to support
 
 paul@359      4 
[[FilesystemAccess|access to filesystem content]] through paging: the delivery
 
 paul@465      5 
of content to clients in mapped memory.
 
 paul@465      6 
 
 paul@465      7 
<<TableOfContents(2,3)>>
 
 paul@465      8 
 
 paul@465      9 
== Overview ==
 
 paul@465     10 
 
 paul@465     11 
The general mechanism used to support paging is depicted below.
 
 paul@359     12 
 
 paul@359     13 
######## A graph showing the general paging mechanism
 
 paul@359     14 
 
 paul@359     15 
{{{#!graphviz
 
 paul@359     16 
#format svg
 
 paul@359     17 
#transform notugly
 
 paul@359     18 
digraph paging {
 
 paul@359     19 
  node [fontsize="12.0",fontname="sans-serif",shape=box];
 
 paul@359     20 
  edge [fontsize="12.0",fontname="sans-serif"];
 
 paul@359     21 
  rankdir=LR;
 
 paul@359     22 
 
 paul@359     23 
  subgraph {
 
 paul@359     24 
    rank=same;
 
 paul@359     25 
 
 paul@359     26 
    Pager_note [shape=note,style=filled,fillcolor=gold,label="Provides\nfilesystem\ncontent"];
 
 paul@359     27 
    Pager;
 
 paul@359     28 
 
 paul@359     29 
    Pager_note -> Pager [dir=none,style=dotted];
 
 paul@359     30 
  }
 
 paul@359     31 
 
 paul@359     32 
  subgraph {
 
 paul@359     33 
    rank=same;
 
 paul@359     34 
 
 paul@359     35 
    PageMapper_note [shape=note,style=filled,fillcolor=gold,label="Provides\npopulated\nfile pages"];
 
 paul@359     36 
    PageMapper;
 
 paul@359     37 
 
 paul@359     38 
    PageMapper_note -> PageMapper [dir=none,style=dotted];
 
 paul@359     39 
  }
 
 paul@359     40 
 
 paul@359     41 
  subgraph {
 
 paul@359     42 
    rank=same;
 
 paul@359     43 
 
 paul@359     44 
    Accessor_note [shape=note,style=filled,fillcolor=gold,label="Populates\nfile pages"];
 
 paul@359     45 
    Accessor;
 
 paul@359     46 
 
 paul@359     47 
    Accessor_note -> Accessor [dir=none,style=dotted];
 
 paul@359     48 
  }
 
 paul@359     49 
 
 paul@359     50 
  AccessMap [shape=record,label="<head> AccessMap |
 
 paul@359     51 
                                 { offset-0 |<fp0> flexpage-0 } | ... |
 
 paul@359     52 
                                 { offset-n |<fpn> flexpage-n } | ..."];
 
 paul@359     53 
 
 paul@359     54 
  subgraph {
 
 paul@359     55 
    rank=same;
 
 paul@359     56 
 
 paul@359     57 
    Pages_note [shape=note,style=filled,fillcolor=gold,label="Provides\nmemory\npages"];
 
 paul@359     58 
    Pages;
 
 paul@359     59 
 
 paul@359     60 
    Pages_note -> Pages [dir=none,style=dotted];
 
 paul@359     61 
  }
 
 paul@359     62 
 
 paul@359     63 
  PageQueue [shape=record,label="<head> PageQueue |
 
 paul@359     64 
                                 { owner-0 |<fp0> flexpage-0 } | ... |
 
 paul@359     65 
                                 { owner-N |<fpN> flexpage-N } | <end> ..."];
 
 paul@359     66 
 
 paul@359     67 
  Flexpage_offset_n [shape=record,label="<head> Flexpage |
 
 paul@359     68 
                                         offset | size |<r> region"];
 
 paul@359     69 
 
 paul@359     70 
  subgraph {
 
 paul@359     71 
    rank=same;
 
 paul@359     72 
 
 paul@359     73 
    Memory_note [shape=note,style=filled,fillcolor=gold,label="Allocates\nmemory\nregions"];
 
 paul@359     74 
    Memory;
 
 paul@359     75 
 
 paul@359     76 
    Memory_note -> Memory [dir=none,style=dotted];
 
 paul@359     77 
  }
 
 paul@359     78 
 
 paul@359     79 
  Region;
 
 paul@359     80 
 
 paul@359     81 
  /* Relationships. */
 
 paul@359     82 
 
 paul@359     83 
  PageMapper -> Accessor;
 
 paul@359     84 
  PageMapper -> AccessMap:head;
 
 paul@359     85 
  Pager -> PageMapper -> Pages;
 
 paul@359     86 
  Pages -> Memory;
 
 paul@359     87 
  Pages -> PageQueue:head;
 
 paul@359     88 
  AccessMap:fpn -> Flexpage_offset_n:head;
 
 paul@359     89 
  PageQueue:fpN -> Flexpage_offset_n:head;
 
 paul@359     90 
  Flexpage_offset_n:r -> Region;
 
 paul@359     91 
}
 
 paul@359     92 
}}}
 
 paul@359     93 
 
 paul@359     94 
########
 
 paul@359     95 
 
 paul@384     96 
A [[ServerLibrary#Pager|`Pager`]], being a resource that provides filesystem
 
 paul@384     97 
content to clients for a particular file, requests pages from the
 
 paul@381     98 
`PageMapper`, itself having the role of supplying populated pages of content
 
 paul@381     99 
from the given file. The `PageMapper` relies on the `AccessMap` to discover
 
 paul@381    100 
existing pages for any accessed region of a file, involving the `Pages` object
 
 paul@381    101 
(or page collection) to obtain new memory pages where existing pages are not
 
 paul@381    102 
available or are no longer valid. It also requests the population of such
 
 paul@381    103 
pages through use of the associated `Accessor` for the file concerned.
 
 paul@381    104 
 
 paul@465    105 
== Pagers and Files ==
 
 paul@465    106 
 
 paul@465    107 
Each `PageMapper` is responsible for a particular file, and where multiple
 
 paul@465    108 
`Pager` objects provide access to a file for different clients, these will all
 
 paul@465    109 
share the same `PageMapper` and thus the same `AccessMap` and `Accessor`. The
 
 paul@465    110 
`PageMapper` is initialised when a [[Server Library#Providers|`Provider`]]
 
 paul@465    111 
object is created to represent a file.
 
 paul@465    112 
 
 paul@465    113 
######## A graph showing the relationships between pagers and files
 
 paul@465    114 
 
 paul@465    115 
{{{#!graphviz
 
 paul@465    116 
#format svg
 
 paul@465    117 
#transform notugly
 
 paul@465    118 
digraph pagers_and_files {
 
 paul@465    119 
  node [fontsize="12.0",fontname="sans-serif",shape=box];
 
 paul@465    120 
  edge [fontsize="12.0",fontname="sans-serif"];
 
 paul@465    121 
  rankdir=LR;
 
 paul@465    122 
 
 paul@465    123 
  subgraph {
 
 paul@465    124 
    rank=same;
 
 paul@465    125 
 
 paul@465    126 
    Pager_note12 [shape=note,style=filled,fillcolor=gold,
 
 paul@465    127 
     label="Provides\nfilesystem\ncontent\nfor file #1"];
 
 paul@465    128 
 
 paul@465    129 
    Pager1 [label="Pager"];
 
 paul@465    130 
    Pager2 [label="Pager"];
 
 paul@465    131 
    Pager3 [label="Pager"];
 
 paul@465    132 
 
 paul@465    133 
    Pager_note3 [shape=note,style=filled,fillcolor=gold,
 
 paul@465    134 
     label="Provides\nfilesystem\ncontent\nfor file #2"];
 
 paul@465    135 
 
 paul@465    136 
    Pager_note12 -> Pager1 -> Pager2 [dir=none,style=dotted];
 
 paul@465    137 
    Pager3 -> Pager_note3 [dir=none,style=dotted];
 
 paul@465    138 
  }
 
 paul@465    139 
 
 paul@465    140 
  subgraph {
 
 paul@465    141 
    rank=same;
 
 paul@465    142 
 
 paul@465    143 
    PageMapper1_note [shape=note,style=filled,fillcolor=gold,
 
 paul@465    144 
     label="Provides\npopulated\nfile pages\nfor file #1"];
 
 paul@465    145 
 
 paul@465    146 
    PageMapper1 [label="PageMapper"];
 
 paul@465    147 
    PageMapper2 [label="PageMapper"];
 
 paul@465    148 
 
 paul@465    149 
    PageMapper2_note [shape=note,style=filled,fillcolor=gold,
 
 paul@465    150 
     label="Provides\npopulated\nfile pages\nfor file #2"];
 
 paul@465    151 
 
 paul@465    152 
    PageMapper1_note -> PageMapper1 [dir=none,style=dotted];
 
 paul@465    153 
    PageMapper2 -> PageMapper2_note [dir=none,style=dotted];
 
 paul@465    154 
  }
 
 paul@465    155 
 
 paul@465    156 
  subgraph {
 
 paul@465    157 
    rank=same;
 
 paul@465    158 
 
 paul@465    159 
    AccessMap1_note [shape=note,style=filled,fillcolor=gold,
 
 paul@465    160 
     label="Manages\nfile pages\nfor file #1"];
 
 paul@465    161 
 
 paul@465    162 
    AccessMap1 [label="AccessMap"];
 
 paul@465    163 
    AccessMap2 [label="AccessMap"];
 
 paul@465    164 
 
 paul@465    165 
    AccessMap2_note [shape=note,style=filled,fillcolor=gold,
 
 paul@465    166 
     label="Manages\nfile pages\nfor file #2"];
 
 paul@465    167 
 
 paul@465    168 
    AccessMap1_note -> AccessMap1 [dir=none,style=dotted];
 
 paul@465    169 
    AccessMap2 -> AccessMap2_note [dir=none,style=dotted];
 
 paul@465    170 
  }
 
 paul@465    171 
 
 paul@465    172 
  subgraph {
 
 paul@465    173 
    rank=same;
 
 paul@465    174 
 
 paul@465    175 
    Accessor_note [shape=note,style=filled,fillcolor=gold,label="Populates\nfile pages"];
 
 paul@465    176 
    Accessor;
 
 paul@465    177 
 
 paul@465    178 
    Accessor_note -> Accessor [dir=none,style=dotted];
 
 paul@465    179 
  }
 
 paul@465    180 
 
 paul@465    181 
  /* Relationships. */
 
 paul@465    182 
 
 paul@465    183 
  Pager1 -> PageMapper1;
 
 paul@465    184 
  Pager2 -> PageMapper1;
 
 paul@465    185 
  Pager3 -> PageMapper2;
 
 paul@465    186 
 
 paul@465    187 
  PageMapper1 -> AccessMap1;
 
 paul@465    188 
  PageMapper2 -> AccessMap2;
 
 paul@465    189 
 
 paul@465    190 
  PageMapper1 -> Accessor;
 
 paul@465    191 
  PageMapper2 -> Accessor;
 
 paul@465    192 
}
 
 paul@465    193 
}}}
 
 paul@465    194 
 
 paul@465    195 
########
 
 paul@465    196 
 
 paul@382    197 
== Obtaining and Queuing Pages ==
 
 paul@382    198 
 
 paul@381    199 
The `Pages` object may either obtain new memory pages from a `Memory` object
 
 paul@381    200 
or reclaim (or recycle) existing pages from a `PageQueue`, this recording all
 
 paul@381    201 
pages that have been populated and supplied to clients. Since it may be
 
 paul@381    202 
desirable to limit the number of pages employed to satisfy file access
 
 paul@381    203 
operations, the `PageQueue` provides a kind of lending mechanism: pages are
 
 paul@381    204 
issued to clients and then added to the end of the queue; where no new page
 
 paul@381    205 
can be supplied by a `Memory` object, the issued page at the head of the queue
 
 paul@381    206 
is obtained for recycling; ultimately, an issued page will remain valid for
 
 paul@381    207 
its user (the client accessing its contents) until all pages in front of it in
 
 paul@381    208 
the queue are themselves recycled and it is then removed from the queue for
 
 paul@381    209 
recycling.
 
 paul@381    210 
 
 paul@384    211 
== Satisfying Requests for Pages ==
 
 paul@384    212 
 
 paul@384    213 
The general procedure for satisfying requests for pages is as follows:
 
 paul@384    214 
 
 paul@384    215 
 1. Attempt to find an existing page for the affected file region.
 
 paul@384    216 
 1. With an existing page, attempt to reserve the page for issuing.
 
 paul@384    217 
 1. Without an existing or reserved page, obtain a fresh page for populating.
 
 paul@384    218 
 1. Queue the page for eventual reuse.
 
 paul@384    219 
 
 paul@382    220 
Since many files are likely to be in use, and since a fixed amount of memory
 
 paul@382    221 
may be shared to provide access to file content, the interaction between
 
 paul@382    222 
different `PageMapper` objects, operating on behalf of different files, must
 
 paul@382    223 
be taken into consideration. The following diagram depicts the principal
 
 paul@382    224 
mechanisms involved in securing access to pages so as to provide access to
 
 paul@382    225 
file content.
 
 paul@381    226 
 
 paul@381    227 
######## A graph showing concurrency considerations
 
 paul@381    228 
 
 paul@381    229 
{{{#!graphviz
 
 paul@381    230 
#format svg
 
 paul@381    231 
#transform notugly
 
 paul@381    232 
digraph paging_concurrency {
 
 paul@381    233 
  node [fontsize="12.0",fontname="sans-serif",shape=box];
 
 paul@381    234 
  edge [fontsize="12.0",fontname="sans-serif"];
 
 paul@381    235 
  rankdir=LR;
 
 paul@381    236 
 
 paul@381    237 
  /* First page mapper activities. */
 
 paul@381    238 
 
 paul@381    239 
  subgraph {
 
 paul@384    240 
    rank=same;
 
 paul@381    241 
 
 paul@381    242 
    PageMapper1_note [shape=note,style=filled,fillcolor=gold,label="Find\nflexpage"];
 
 paul@381    243 
    PageMapper1 [label="PageMapper"];
 
 paul@381    244 
 
 paul@384    245 
    Accessor1 [label="Accessor"];
 
 paul@384    246 
 
 paul@381    247 
    PageMapper1_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage"];
 
 paul@381    248 
    PageMapper1_reserve [label="PageMapper"];
 
 paul@381    249 
 
 paul@381    250 
    PageMapper1_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"];
 
 paul@381    251 
    PageMapper1_queue [label="PageMapper"];
 
 paul@381    252 
 
 paul@381    253 
    PageMapper1_note -> PageMapper1 [dir=none,style=dotted];
 
 paul@381    254 
    PageMapper1_reserve_note -> PageMapper1_reserve [dir=none,style=dotted];
 
 paul@381    255 
    PageMapper1_queue_note -> PageMapper1_queue [dir=none,style=dotted];
 
 paul@381    256 
  }
 
 paul@381    257 
 
 paul@381    258 
  /* Access map usage and flexpage acquisition. */
 
 paul@381    259 
 
 paul@381    260 
  subgraph {
 
 paul@381    261 
    rank=same;
 
 paul@381    262 
 
 paul@381    263 
    AccessMap_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ntentatively"];
 
 paul@381    264 
    AccessMap1 [label="AccessMap"];
 
 paul@384    265 
 
 paul@381    266 
    Flexpage1 [label="Flexpage",shape=note,style=dashed];
 
 paul@381    267 
    Flexpage1_note [shape=note,style=filled,fillcolor=gold,label="Needs reservation\nif found\nby mapper"];
 
 paul@382    268 
 
 paul@381    269 
    Flexpage1_reserve [label="Flexpage",shape=note,style=dashed];
 
 paul@381    270 
    Flexpage1_reserved [label="Flexpage",shape=note];
 
 paul@381    271 
    Flexpage1_reserved_note [shape=note,style=filled,fillcolor=gold,label="Claimed if\nstill available"];
 
 paul@382    272 
 
 paul@381    273 
    Flexpage1_queue [label="Flexpage",shape=note];
 
 paul@359    274 
 
 paul@381    275 
    AccessMap_note -> AccessMap1 [dir=none,style=dotted];
 
 paul@381    276 
    Flexpage1_note -> Flexpage1_reserve [dir=none,style=dotted];
 
 paul@381    277 
    Flexpage1_reserved -> Flexpage1_reserved_note [dir=none,style=dotted];
 
 paul@381    278 
 
 paul@381    279 
    Flexpage1_reserve -> Flexpage1_reserved [dir=none,style=invis];
 
 paul@381    280 
  }
 
 paul@381    281 
 
 paul@381    282 
  subgraph {
 
 paul@381    283 
    rank=same;
 
 paul@381    284 
 
 paul@381    285 
    PageQueue_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ndefinitively"];
 
 paul@381    286 
    PageQueue [label="PageQueue"];
 
 paul@381    287 
    Flexpage [shape=note];
 
 paul@381    288 
    Pages [label="Pages"];
 
 paul@382    289 
    Pages_note [shape=note,style=filled,fillcolor=gold,label="Reclaim and\nrecycle\nflexpage"];
 
 paul@381    290 
 
 paul@383    291 
    PageQueue_reserve_note [shape=note,style=filled,fillcolor=gold,label="Provides\nreserved\nflexpage"];
 
 paul@383    292 
    PageQueue_reserve [label="PageQueue"];
 
 paul@381    293 
    Flexpage_reserve [label="Flexpage",shape=note];
 
 paul@381    294 
    Pages_reserve [label="Pages"];
 
 paul@381    295 
    Pages_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage\nif available"];
 
 paul@381    296 
 
 paul@381    297 
    Pages_queue_note [shape=note,style=filled,fillcolor=gold,label="Queues\nissued\nflexpage"];
 
 paul@381    298 
    Pages_queue [label="Pages"];
 
 paul@381    299 
    Flexpage_queued [label="Flexpage",shape=note];
 
 paul@381    300 
    PageQueue_queued [label="PageQueue"];
 
 paul@381    301 
 
 paul@381    302 
    PageQueue_note -> PageQueue [dir=none,style=dotted];
 
 paul@381    303 
    Pages -> Pages_note [dir=none,style=dotted];
 
 paul@383    304 
    PageQueue_reserve_note -> PageQueue_reserve [dir=none,style=dotted];
 
 paul@381    305 
    Pages_reserve -> Pages_reserve_note [dir=none,style=dotted];
 
 paul@381    306 
    Pages_queue_note -> Pages_queue [dir=none,style=dotted];
 
 paul@381    307 
 
 paul@383    308 
    Pages_note -> PageQueue_reserve_note [dir=none,style=invis];
 
 paul@381    309 
    Pages_reserve_note -> Pages_queue_note [dir=none,style=invis];
 
 paul@381    310 
  }
 
 paul@381    311 
 
 paul@381    312 
  subgraph {
 
 paul@381    313 
    rank=same;
 
 paul@381    314 
 
 paul@381    315 
    Flexpage2 [label="Flexpage",shape=note];
 
 paul@381    316 
    Flexpage2_note [shape=note,style=filled,fillcolor=gold,label="Reserved\nwhen obtained"];
 
 paul@381    317 
 
 paul@383    318 
    Flexpage2_reserved [label="Flexpage",shape=note];
 
 paul@383    319 
 
 paul@383    320 
    AccessMap2 [label="AccessMap"];
 
 paul@383    321 
    AccessMap2_note [shape=note,style=filled,fillcolor=gold,label="Records\nreserved\nflexpage"];
 
 paul@383    322 
 
 paul@383    323 
    Flexpage2_queue [label="Flexpage",shape=note];
 
 paul@383    324 
 
 paul@383    325 
    Flexpage2_note -> Flexpage2 [dir=none,style=dotted];
 
 paul@383    326 
    AccessMap2 -> AccessMap2_note [dir=none,style=dotted];
 
 paul@383    327 
 
 paul@383    328 
    Flexpage2 -> Flexpage2_reserved [dir=none,style=invis];
 
 paul@381    329 
  }
 
 paul@381    330 
 
 paul@381    331 
  /* Second page mapper activities. */
 
 paul@381    332 
 
 paul@381    333 
  subgraph {
 
 paul@383    334 
    rank=same;
 
 paul@381    335 
 
 paul@381    336 
    PageMapper2_note [shape=note,style=filled,fillcolor=gold,label="Obtain\nflexpage"];
 
 paul@381    337 
    PageMapper2 [label="PageMapper"];
 
 paul@381    338 
 
 paul@384    339 
    Accessor2 [label="Accessor"];
 
 paul@384    340 
 
 paul@383    341 
    PageMapper2_record_note [shape=note,style=filled,fillcolor=gold,label="Record\nflexpage"];
 
 paul@383    342 
    PageMapper2_record [label="PageMapper"];
 
 paul@383    343 
 
 paul@383    344 
    PageMapper2_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"];
 
 paul@383    345 
    PageMapper2_queue [label="PageMapper"];
 
 paul@383    346 
 
 paul@381    347 
    PageMapper2_note -> PageMapper2 [dir=none,style=dotted];
 
 paul@383    348 
    PageMapper2_record_note -> PageMapper2_record [dir=none,style=dotted];
 
 paul@383    349 
    PageMapper2_queue_note -> PageMapper2_queue [dir=none,style=dotted];
 
 paul@381    350 
  }
 
 paul@381    351 
 
 paul@381    352 
  /* First pager dataflow. */
 
 paul@381    353 
 
 paul@381    354 
  PageMapper1 -> AccessMap1 [label="find"];
 
 paul@381    355 
  AccessMap1 -> Flexpage1 [dir=none];
 
 paul@381    356 
  Flexpage1 -> PageMapper1;
 
 paul@381    357 
 
 paul@381    358 
  PageMapper1_reserve -> Flexpage1_reserve [dir=none];
 
 paul@381    359 
  Flexpage1_reserve -> Pages_reserve [label="reserve"];
 
 paul@381    360 
  Pages_reserve -> Flexpage1_reserved [dir=none];
 
 paul@381    361 
  Flexpage1_reserved -> PageMapper1_reserve;
 
 paul@381    362 
 
 paul@381    363 
  PageMapper1_queue -> Flexpage1_queue [dir=none];
 
 paul@381    364 
  Flexpage1_queue -> Pages_queue [label="queue"];
 
 paul@381    365 
 
 paul@381    366 
  /* Flexpage queuing. */
 
 paul@381    367 
 
 paul@381    368 
  Pages_queue -> Flexpage_queued [dir=none];
 
 paul@381    369 
  Flexpage_queued -> PageQueue_queued;
 
 paul@381    370 
 
 paul@381    371 
  /* Flexpage retrieval from the queue. */
 
 paul@381    372 
 
 paul@381    373 
  PageQueue -> Flexpage [color="red",dir=none];
 
 paul@381    374 
  Flexpage -> Pages [color="red"];
 
 paul@383    375 
 
 paul@383    376 
  PageQueue_reserve -> Flexpage_reserve [dir=none];
 
 paul@381    377 
  Flexpage_reserve -> Pages_reserve;
 
 paul@381    378 
 
 paul@381    379 
  /* Flexpage removal from the access map. */
 
 paul@381    380 
 
 paul@384    381 
  Pages -> AccessMap1 [color="red",label="remove\n(via PageMapper)"];
 
 paul@384    382 
  AccessMap1 -> PageMapper1 [color="red",label="flush"];
 
 paul@384    383 
  PageMapper1 -> Accessor1 [color="red",label="flush"];
 
 paul@381    384 
 
 paul@381    385 
  /* Second pager dataflow. */
 
 paul@381    386 
 
 paul@383    387 
  PageMapper2 -> Pages [color="red",label="flexpage"];
 
 paul@381    388 
  Pages -> Flexpage2 [color="red",dir=none];
 
 paul@381    389 
  Flexpage2 -> PageMapper2 [color="red"];
 
 paul@384    390 
  PageMapper2 -> Accessor2 [label="fill"];
 
 paul@383    391 
 
 paul@383    392 
  PageMapper2_record -> Flexpage2_reserved [dir=none,label="insert"];
 
 paul@383    393 
  Flexpage2_reserved -> AccessMap2;
 
 paul@383    394 
 
 paul@383    395 
  PageMapper2_queue -> Flexpage2_queue [dir=none];
 
 paul@383    396 
  Flexpage2_queue -> Pages_queue [label="queue"];
 
 paul@381    397 
}
 
 paul@381    398 
}}}
 
 paul@381    399 
 
 paul@381    400 
########
 
 paul@382    401 
 
 paul@382    402 
== Reclaiming and Recycling Pages ==
 
 paul@382    403 
 
 paul@382    404 
When a `PageMapper` requests a page from the `Pages` object and when the
 
 paul@382    405 
`Pages` object needs to reclaim such a previously issued page, the page
 
 paul@384    406 
obtained from the head of the queue is removed from the `AccessMap` employed
 
 paul@384    407 
by the `PageMapper` that currently owns it. The "owner" of such a page is
 
 paul@384    408 
employing the page to satisfy requests for content in a region of a particular
 
 paul@384    409 
file. If modified, the page's contents may be flushed to the underlying file
 
 paul@384    410 
when it is removed from the owner. As a consequence of its removal, the
 
 paul@384    411 
`AccessMap` will no longer be able to offer this page to satisfy a request for
 
 paul@384    412 
data in the affected region to its `PageMapper`. A reclaimed page is then
 
 paul@384    413 
returned to the `PageMapper` requiring it, and since the page will no longer
 
 paul@384    414 
reside in the `PageQueue`, it will be exclusively available for that
 
 paul@384    415 
`PageMapper`, being populated with data from the underlying file and then
 
 paul@384    416 
issued to its client.
 
 paul@382    417 
 
 paul@382    418 
== Reserving Available Pages ==
 
 paul@382    419 
 
 paul@382    420 
When an `AccessMap` is able to satisfy a request for a page providing access
 
 paul@382    421 
to a region in a particular file, the `PageMapper` must secure exclusive
 
 paul@382    422 
access to that page. Otherwise, the possibility exists that the page will be
 
 paul@382    423 
reclaimed and recycled concurrently by another `PageMapper`. Thus, the
 
 paul@382    424 
`PageMapper` must request that the page be reserved by the `Pages` object
 
 paul@382    425 
which in turn removes the page from the `PageQueue`. Since no other party can
 
 paul@382    426 
now obtain the page independently, it can be issued safely.
 
 paul@382    427 
 
 paul@382    428 
== Queuing Issued Pages ==
 
 paul@382    429 
 
 paul@382    430 
Once a page has been issued to a client by the `Pager`, regardless of how it
 
 paul@382    431 
was obtained, it must be made available for future reuse. This is achieved by
 
 paul@382    432 
the `PageMapper` requesting the queuing of the page, with it being added to
 
 paul@382    433 
the end of the `PageQueue`.