6,534
edits
Changes
m
spelling fixes
{{UBC toc}}
This article describes how fractions accounting algorithm used in [[User pages|privvmpages accoutingaccounting]] works.
== Introduction ==
The goal of this algorithm is to calculate the {{H:title|Resident Set Size|RSS}} for each beancounter. This is done by establishing so called many-to-many relation between physical pages and beancounters.
{{Note|the term “page is mapped to beancounter” used in this article means “there exists an <code>mm_struct</code>, the pages is mapped to and this <code>mm_struct</code> belongs to this beancounter”.}}
== Math model ==
As described in the [[User pages|article about user pages]], this algorithm calculates the “fractions” of pages, that are mapped to beancounter, in a tricky manner.
Naturally , if a page is shared between <math>N</math> beancounters , each UB must get <math>\frac {1} {N}</math>-th part of it. This approach is would be the most precise, but also the worst, as adding a page to a new beancounter would require an update on all the beancounters between which the page is already shared. Instead of doing this that, UBC charges parts of page equal to <math>2^{-shift(page, UB)}\,</math>, where <math>shift(page, UB)</math> is calculated so that
<center>
<math>
\sum _{UB} 2^{-shift(page, UB)} = 1\,
</math>
</center>
Such fractions allow to build an O(1) algorithalgorithm, as described below.
== Algorithm description ==
=== Objects ===
The following objects are used in this algoalgorithm:; page Page beancounter (PB): this is a A tie between page and beancounter. This is the PB which holds the value of <math>shift(page, UB)</math>;; pagePage: page is actually a A physical page. In linux Linux kernel each physical page is represented with <code>struct page</code>. What is importaint important is that each page has its associated circular list of PBs and the head PB in this list has a special meaning;; beancounterBeancounter: this is a A known object. To work with this algorithm beancounter has an auxiliary resource called “held pages”.
Page beancounters are stored in a large hash to hasten the lookup of a needed PB.
The next two sections describe the procedures of adding and removing of referencesa reference.
=== Adding a new reference ===
When page is added to UB , one of the following scenarios is possible.:
; There's already a tie between the page an the UB
: In this case just increment the reference count of the tie;
=== Removing an existing reference ===
When the existing reference is removed , the following scenarios are possible.:
; This page was referenced to BC more than once (e.g. by two tasks)
: In this case reference counter is decremented;
; The last reference is removed
: In this case the PB that ties page and UB must give it's its shift back to other PBs and be removed from list. This “giving shift back” procedure may involve three PBs and it is better described in by the code example below.
<pre>
pb = lookup_pb(page, UB);
</pre>
Decrementing the shifts like this means <em>take “take the fraction held by the PB going out and give it to another one; if the fraction held is too large — share it between two PBs</em>PBs”.
{{Note|cases when <code>page.pb_list</code> is becoming empty on adding a reference , or becomes becoming empty on removing references are skipped to simplify the code examples.}}