19770721_Handling_Page_Faults_In_Pilot.pdf part of xerox 19770721 Handling Page Faults In Pilot 19770721_Handling_Page_Faults_In_Pilot.pdf, xerox sdd memos_1977 19770721_Handling_Page_Faults_In

Text preview for : 19770721_Handling_Page_Faults_In_Pilot.pdf part of xerox 19770721 Handling Page Faults In Pilot xerox sdd memos_1977 19770721_Handling_Page_Faults_In_Pilot.pdf

Back to : 19770721_Handling_Page_Fa | Home

Inter-Office Memorandum

To Pilot Group Date July 21, 1977

From Dave Redell Location Palo Alto

Subject Handling page faults in Pilot Organization SOO/SD

XEF.OX SDD ARCHIVES
XEROX I have read and understood
Pages __-------To ---------
Filed on: ..., '1'-, r, ' . ' -
-.' D
., of Pages_ __ Ref 0,' ~.,

Introduction
A previous memo [1] discussed issues immediately surrounding the occurrence of a page
fault and suggested characterizing page faults as I/O-like events, to be serviced by a handler
process. This memo investigates the subsequent processing of page faults; the discussion
emphasizes structural issues, but is implicitly driven by performance considerations.

The main quantitative goals of the proposal are minimization of memory residency. code
complexity. and computational overhead, in roughly that order. The resulting mechanism is
mildly recursive, but termination of the recursion after a single cycle is guaranteed. It would
appear that a similar approach could be used in managing the tables of the file system.

The swapper

The Pilot virtual memory mechanism consists of two layers: the Virtual Memory Manager
and the Swapper [2]. The Swapper consists of three main processes, plus supporting data
structures.
Swapln process: handles page faults using the Active Segment Map and the
PageTransfer level of the File system[3].
SwapOut process: writes pages (esp: deactivated swap units) to the disk in
anticipation of reuse of their pageframes by the Swapln process.
SwapFinish process: handles 1/0 completions as notified by the PageTransfer level,
updating the swapper tables and awakening any faulted processes.
Active Segment Map: The main table of the swap per, mapping (for purposes of this
discussion) virtual page numbers to swap unit descriptions:
SwapUnit: TYPE = RECORO[
file: FileHandle.
fileBase: FilePageNumber
base: PageNumber.
count: PageCount];
Handling page faults in Pilot 2

In handling page faults. the main participants are the Swapln and SwapFinish processes.
wh ich can be sketched as:

Swapln: PROCESS =
BEGIN
faultPage, bufferBase: PageNumber;
faultFilePage: FilePageNumber;
su: SwapUnit;
DO
faultPage +- WaitForPageFault[];
su +- FindActiveSwapUnit [ faultPage ];
faultFilePage +- su.fileBase + (faultPage - su.Base);
bufferBase +- GetBufferPages [ su.count ];
ReadPageSet
[ su.file, su.fileBase, bufferBase, su.count, su.base, faultFilePage];
END LOOP
END;

SwapFinish: PROCESS =
BEGIN
page, bufferPage, base: Page Number;
filePage: FilePageNumber;
su: SwapUnit;
op: PageOperation;
DO
[op"filePage,bufferPage,base] +- WaitPageTransferred[];
SELECT op FROM
read =>
BEGIN
su +- FindActiveSwapUnit [ base ];
page +- su.base + (filePage - suJileBase)
MovePageslnRelocatedMemory [ bufferPage, page, 1 ];
(fix up VM tables ... >;
WakeUpFaultedProcesses [ page ]
END;
write =>

ENDCASE
ENDLOOP
END;
Handling page faults in Pilot 3

The swapper as sketched here is quite simple and fast, but this is largely because it assumes
that the descriptions of all existing swap units are present in the resident Active Segment
Map. While this might be feasible in a configuration which made only modest use of the
virtual memory. it would. in general, cramp our style, by making the simple presence of data
in virtual memory intrinsically expensive, whether it was being used or not We are thus
faced with optimizing the tradeoff between two important goals:
Insuring that all page faults can be handled quickly. This suggests simple algorithms
and tables resident in real memory.
Minimizing the cost of retaining large amounts of inactive information in virtual
memory, This implies that the descriptions of such "cold" swap units should
themselves migrate to the disk.

This all suggests some form of caching scheme. The Active Segment Map can serve as a
cache on a more general Segment Map, most of which can reside on disk. (It would also be nice
if, whenever the Active Segment Map is capable of describing the entire working set of the computation, the cost
of the backing Segment Map machinery could atrophy to nearly zero.) There seem to be four general
ways to build such a caching scheme, as determined by two questions:
Is the cache managed by the Swapper, or by the higher level VM Manager?
Is the Segment Map on the disk accessed via the virtual memory (i.e. page faults) or
via direct calls on the File System (i.e reads/writes)?

Note that none of the four approaches rely on the virtual memory to automatically keep the active parts of the
Segment Map in real memory for use by the swap per; instead active swap unit descriptions are always copied
into the Active Segment Map, for two reasons:
- Swap unit descriptions are examples of the kind of small objects which everyone agrees should be
cached explicitly to avoid page breakage.
The Active Segment Map should be a simple, resident table, while the Segment Map is large and should
be optimized for external searching (e.g. a B-tree?): decoupling their representations seems like a good
idea.

The four approaches are thus:
1. Swapper caches entries accessed via reads: This would greatly increase the complexity
of the Swapper. All of the added code would be resident.
2. Swapper caches entries accessed via page faults: This appears to simplify access to the
disk. but actually introduces subtle complexity by making the Swapper fully
recursive.
3. YM Manager caches entries accessed via reads: This pushes the complexity up to the
higher level. which is not intrinsically resident.
4. YM Manager caches entries accessed via page faults: This further simplifies things by
allowing the YM Manager, which already runs in virtual memory, to access the
Segment Map in this way.

It would appear that approach 4 is preferrable, if no other lurking complexities arise. It is
important to note, in this regard, that this approach introduces a new upward dependency of
the Swapper on the VM Manager, When, in the course of handling a page fault, the Swapper
needs a swap unit description which is missing from the Active Segment Map, it notifies a
"Helper" in the YM Manager (in a manner to be described); the Helper then fetches the
description from the Segment Map in virtual memory, which may cause a second round of
page faults. All that is necessary to guarantee that no third round page fault can extend the
series is to make all code and data of the Helper, including the Segment Map, permanently
active (i.e force their swap unit descriptions to reside permanently in the Active Segment
Map.) These appear to be the only remnants of the YM Manager which must remain in real
memory during times when the entire working set fits into the Active Segment Map. Like
the Helper, the rest of the YM Manager can be swapped out when it is not needed. Unlike
Handling page faults in Pilot 4

the Helper. the other parts of the VM Manager have no intrinsic need to be permanently
active.

The Swapper's Helper

The essence of the "Helper" approach is that Swapln. when in need of a missing swap unit
description, "calls for help." It would be nice to do this by having Swapln notify a separate
Helper process of the page fault and then forget the entire affair. This is the simplest way of
insuring that Swapln is ready to process further page faults, including any generated by the
Helper. It does mean that the Helper has inherited the responsibility to insure ultimate
completion of the original page fault episode. As shown below, it can easily do this by
simply referencing the faulted page itself, causing Swapln to effectively reprocess the
original fault.

Helper: PROCESS =
BEGIN
faultPage: PageNumber;
su: Swap Unit;
00
faultPage +- GetCaIlForHelp[];
su +- FindSwapUnit [ faultPage ]; .- may fault on Segment Map
AddActiveSwapUnit [ su ];
[] +- LongPointerToPage [ faultPage ] t; -- will fault on original page
ENDLOOP
END;

Swapln: PROCESS =
BEGIN
faultPage, bufferBase: PageNumber;
faultFilePage: FilePageNumber;
su: Swap Unit;
found: BOOLEAN;
00
faultPage +- WaitForPageFault[];
[found, su] +- FindActiveSwapUnit [ faultPage ];
IF ~ found THEN
CallForHelp [ faultPage ]
ELSE
BEGIN
faultFilePage +- su.fileBase + (faultPage - su.Base);
bufferBase +- GetBufferPages [ su.count ];
ReadPageSet [ su.file, su.fileBase, bufferBase, su.count, sU.base.
faultFi lePage]
END
ENDLOOP
END;

It should be noted that this approach serializes access to the Segment Map via the single
Helper. Thus, although some number of page faults may proceed in parallel (see [1]), only
one at a time may touch the Segment Map. This is probably not important, but if it were,
multiple Helper processes would seem to be an effective solution.

A few details
Handling page faults in Pilot 5

The code sketched above calls several lIseful procedures which were never defined, but whose
general intent should be clear. There are a few of these involving synchronization and
buffering which should be mentioned, however. They are sketched below in terms of
monitors.

Three monitors are defined:

Mpf synchronizes page fault handling with the faulted process(es