• The scheduler aids the page selection algorithm by notifying it of
virtual machines that are no longer eligible for dispatching (either
because they have completed or because they are being held suspended
in the eligible list). The scheduler calls the page reset routine
when a virtual machine is dropped from a queue and does not immediately reenter the dispatch list. Under heavy paging loads, it
is the responsibility of the page reset routine to group all
in-storage virtual pages belonging to the virtual machine on an
available (or flush) list for easy selection by the page replacement algorithm.
Requests for real storage fall into two general categories; those that
are requesting space for a page of virtual storage, and those (such as
requests for CP work space) that need page frames for their own use. The former, more general case is discussed first, because the latter case is
a subset of the first.
The main page manager routine, D!KPTRIN, maps a request for a
specific virtual storage address into a page frame of real storage.
This requires that the virtual page be read in and the necessary tables be updated to shOW the proper status of the page frame. D!KPTRIN requires that the caller supply only the virtual address to be translated and any options that apply to the page to be located. Most calls are made via the TRINS macro, which sets up the necessary
parameters, determines whether or not the required page is resident, and
calls D!KPTRIN if it is not. When D!KPTRAN receives control, it first tests to see if the
requested page is resident. This is done via the LRI instruction. If
the page is resident, the routine locks the page if requested and exits
to the caller. If the LRI indicates that the page is unavailable, it is
still possible that the required page is resident. This occurs if the
page frame has been placed on the FREELIST but has not been assigned to
another virtual machine. When the page swap routine removes a page frame from a virtual machine, the unavailable bit is set in the
corresponding page table entry; however, the real main storage index for
the page frame is left unchanged. The page table entry is set to zero
only when the corresponding page is actually assigned to another virtual machine. Thus, if D!KPTRIN finds the page unavailable, a further test
is made on the page table entry to see if the page can be reclaimed. If
the entry is not zero (aside from the unavailable bit), the CORTIBLE entry for the page frame is removed from the FREELIST and the page frame is returned to the calling virtual machine. If the page table entry corresponding to the requested virtual page
is zero, the required page is not in real storage and must be paged in.
However, it is possible that the page is already on its way into .ain
storage. This condition is indicated by a flag in the SWPTIBLE entry for
the virtual page. The D!KPIGIO routine maintains a queue of CPEXBLOKs to
be dispatched when the pending page I/O is complete. The CPEXBLOK for
the page in transit is located and a new CPEXBLOK, representing the
current request, is chained to it.
Before exiting to wait for the paging operation to co.plete, DftKPTRIR checks to see if the deferred return (DEFER option) has been specified.
If it has not, D!KPTRIN returns to the caller. If the DEFER option has
been requested, D!KPTRAN exits to the dispatcher to wait for page I/O co.pletion. When the requested page has been read into real storage, the
list of CPEXBLOKs are unstacked first in first out to satisfy all
requests for the page that arrived while it vas in transit. 1-108 IBM VM/370 System Logic and Problem Deteraination--Volume 1

If a page is not in transit, a page frame of real storage aust be
allocated to fill the request. Before the allocation routine is called,
a test is made to see if the caller wishes the return to his routine or
to be delayed until after the requested page is available. If the DEFEB option is not requested, DMKPTBAN returns to the caller after first
building and stacking a CPEXBLOK that allows processing of the page
request to be continued the next time the dispatcher (DftKDSPCH) is
entered. DMKPTBAN next calls the FBEELIST manager (DMKPTBFB) to obtain the
address of the next available COBTABLE entry. DftKPTBFB aaintains a
first-in-first-out list of the COB TABLE entries for those page fraaes
that are immediately available for assignment. As DMKPTBFB releases
these page frames, a check is made to see if the number of entries on
the FREELIST has fallen below a dynamically aaintained ainiaua value. If
it has, the page selection routine (SELECT) is called to find a suitable
page frame for placement in the FBEELIST. The number aaintained as the
FREEL 1ST threshold has a value equal to the number of users in queue1
plus the number of users in queue2 plus 1.
The FBEELIST is replenished directly by users releasing virtual
storage space. The page-out routine, DftKPGSPO, calls DftKPTBFT to place
released page frames directly on the FBEELIST. However, aost replenishment is done via the page selection routine, SELECT. SELECT is
called by DMKPTBFB when the FBEELIST count falls below the current
minimum, or when a user page is reclaimed fro. the FBEELIST. In either
case, the selection algorithm attempts to find a page to swap to
auxiliary storage. The highest-priority candidates for a swap are those
page frames whose COBTABLE entries appear on the FLUSHLST. SELECT attempts to take a flushed page frame before it takes a page fraae froa an active user. If such a page frame is found, it is checked to see if
it has been changed since page-in •. If it has not, it is placed in the
FBEELIST by DMKPTBFTi otherwise, it is scheduled for a swap-out by dequeuing the COBTABLE entry from the FLUSHLST, constructing a CPEXBLOK for dispatching after I/O completion, and exiting to DMKPAGIO by a GOTO. After the paging I/O is complete, the entry is placed on the FBEELIST via a call to DMKPTBFT. If no pages are found on the FLUSHLST, the selection algoritha
examines each page in real storage, searching for an available page that
does not have its reference bit It begins the search at the first
available page at the high end of real storage and searches by
descending page address. When it reaches the lowest available page
address, it starts again from the top of storage. When a page has been
found, that page address minus one is checkpointed. The next tiae the
selection algoritha is invoked, it starts from the checkpointed address.
As the selection process proceeds, those pages that were not selected
have their reference bits turned off. When the selection algoritha is
operating in this mode, a virtual page must be referenced at least once
per reset cycle (loop around real storage) to avoid selection. Once a page frame has been selected and page-out is scheduled,
control is returned to DMKPTBFB, which then passes control back to DMKPTBAN with the address of the COBTABLE entry that was allocated. In most cases, page-outs are completely overlapped with page-ins.
Approxiaately one half of all page-ins require a corresponding page-out. Once a page frame has been assigned, DMKPTBAN checks to see if a
page-in is required. It usually is, and the DASD address of the virtual
storage page aust be obtained froa the user's swap table entry and the I/O operation scheduled. However, if the page frame bas not yet been
referenced (as indicated by a DASD address of zero), the real aain storage page frame is set to zero, and no page-in is required. After CP Introduction 1-109