Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2001-02-28
2004-12-07
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S156000, C711S162000
Reexamination Certificate
active
06829693
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to virtual memory storage systems for mini and mainframe computing systems, and particularly, to a novel system for efficiently freeing up auxiliary storage slots for storing virtual pages.
2. Discussion of the Prior Art
Virtual memory management schemes enable a computer system to present a large address space, larger than the amount of real storage on the system. A virtual memory management scheme consists of a mapping of an address space which provide a means of translating a virtual address of a page into a real address of a frame. A frame is the basic unit by which real storage is managed in a computer system. For example, in z/Architecture a frame consists of 4096 bytes.
Since real storage is a limited resource, when the operating system determines that it has become scarce it may try to write the data on some real frames to auxiliary storage, also called a direct access storage device (DASD) which is cheaper and more plentiful, but much slower to access. This operation is known as paging and involves initiating output device I/O to auxiliary storage. The operating system makes paging decisions at a global level and a local level. At the global level, the operating system determines which address spaces will suffer a potential performance penalty of having their data paged out to auxiliary storage. At the local level, the operating system determines which frames within an address space are good candidates to be paged to auxiliary storage. In general, frames which are least recently used are better candidates to be paged to auxiliary storage since they have a lower likelihood of being referenced in the near future. Computer systems, including z/Architecture, provide facilities to approximate least recently used (LRU) order. Part of the facility is the Referenced bit which is associated with each frame of storage in z/Architecture. The Referenced bit is turned on by the hardware whenever a frame of storage is referenced or changed. A separate bit called the Changed bit is turned on by the hardware whenever a frame is changed. z/Architecture also provides an instruction called Reset Reference Bit Extended (herein referred to a RRBE) which sets the Referenced bit to zero and sets a condition code which provides an indication of whether the frame was changed and/or referenced. The z/OS operating system maintains a data structure, known as the Page Frame Table Entry (or PFTE) which includes data corresponding to a single frame. The aggregate of PFTEs is referred to as the PFT or Page Frame Table. PFTEs corresponding to frames used for a particular address space are placed on a queue. Periodically, this queue of PFTEs is traversed and the RRBE instruction is used to determine whether the frame is referenced; PFTEs corresponding to frames that have been referenced are moved to the back of the queue. This traversal of the PFTE queue is known as Unreferenced Interval Count Update (or UIC Update).
The act of writing real frames in use by an address space to auxiliary storage to replenish the number of available frames is referred to as stealing. When an address space is selected for stealing, steal candidates are selected by traversing the PFTE queue from the front to the back, in least recently used (LRU) order.
As known, a page may exist in the following states:
a first state (1) where a virtual page is not backed in either real storage
20
or auxiliary storage
30
(as illustrated in FIG.
1
); a second state (2) where a virtual page is backed by an unchanged frame
9
that contains zeros (0,0, . . . ) as illustrated in FIG.
2
. Backing refers to a virtual storage concept where a frame or auxiliary “slot” includes the data that a virtual address refers to; a third state (3) where a virtual page
10
exists only in real storage
20
and unchanged as illustrated in
FIG. 3
; a fourth state (4) where the page is backed in real and changed; a fifth state (5) where a virtual page
10
is copied from real storage
20
to auxiliary storage
30
so the frame corresponding to the real storage can be used for other pages as illustrated in
FIG. 4
; a sixth state (6) where a virtual page
10
exists (is backed) only on auxiliary storage
30
as illustrated in
FIG. 5
; a seventh state (7) where a virtual page
10
is needed so a copy of the page is read in (i.e., copied) into real storage
20
from auxiliary storage
30
as illustrated in
FIG. 6
; an eighth state (8) where a virtual page
10
in real storage is unchanged (backed) and matches a copy on the auxiliary storage
30
as illustrated in
FIG. 7
; and, a ninth state (9) where a virtual page
11
in real storage
20
is changed and the copy
10
on the auxiliary storage
30
is no longer valid and usable as illustrated in FIG.
8
.
When data is stored into a page, the page transitions from either initial state, e.g., (1), (2) or (3) to a state (4). The act of writing real frames in use by an address space to auxiliary storage (i.e., stealing) causes the page to transition to a state (5) and when the output I/O completes, the page is transitioned to state (6). When the page is subsequently referenced or changed, it is read into real storage from auxiliary storage which is a state (7). When the input I/O completes, the page is in state (8) and if the page is changed, the page transitions to state (9).
It should be understood that states (8) and (9) differ from the others in that the page is backed by two different units of storage: a real frame and an auxiliary storage slot. In state (8) the real frame and the auxiliary storage slot contain the same data. In this state the frame may be stolen without having to go through the overhead of initiating output I/O to page the data to auxiliary storage since a copy already exists on auxiliary storage. In state (9), however, there is no value in maintaining a down level copy of the data on auxiliary storage and such auxiliary storage slots should be returned to the available pool (the page should transition to state (4)).
It would thus be highly desirable to provide an operating system that may prevent auxiliary storage shortages by periodically freeing auxiliary storage slots that back pages that are also backed in real where the copy in real has been changed from the copy on auxiliary storage (i.e. state 9).
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a means by which an operating system may prevent auxiliary storage shortages by periodically freeing auxiliary storage slots that back pages being read in from auxiliary storage (i.e., state 7).
According to the principles of the invention, there is provided for a computing system implementing a virtual memory system having real memory storage frames for storing virtual pages of data and an auxiliary storage system comprising auxiliary storage slots for storing copies of corresponding virtual pages provided in real storage frames, a system and method for freeing auxiliary storage slots to enable further copying of pages thereto, the method comprising the steps of: a) traversing a queue of page frame table entries indicating presence and location of virtual page data in the real storage system; b) determining from the real storage frame whether a virtual page has been changed in the real storage, and in response, determining whether the page is backed in a corresponding slot in auxiliary storage; c) identifying the auxiliary slot corresponding to the changed frame; and, d) removing the virtual page in said corresponding slot in said auxiliary storage, wherein further room is made available in said auxiliary storage for accommodating storage of other virtual page entries.
Particularly, the invention includes, in addition to normal PFTE table traversal and steal processing, the checking of a condition code of the RRBE (reset referenced bit extended) instruction to determine whether the frame is changed and if so, whether there is an auxiliary storage slot associated with the page that the frame is associated with. If such a
Dyck Greg A.
Morgenstern Harris M.
Sutherland Danny R.
Wang Wendy L.
Elmore Reba I.
Kinnaman, Jr. Esq. William A.
LandOfFree
Auxiliary storage slot scavenger does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Auxiliary storage slot scavenger, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Auxiliary storage slot scavenger will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3313992