Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-02-28
2003-06-03
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S160000, C709S241000, C709S241000
Reexamination Certificate
active
06574718
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 enhancing system performance by eliminating time spent in disabling resources to excessive spin lock times held by processors.
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 IBM's OS/390 system, 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 IBM's OS/390, 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. OS/390 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 OS/390 operating system maintains a data structure, known as the Page Frame Table Entry (or PFTE) that 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 referred to as a pageable frame queue.
FIG. 1
is a conceptual diagram illustrating the use of a data frame space
10
comprising page frame queues in conventional use today. As shown in
FIG. 1
, there is provided a data space of memory, typically comprising two (2) Gigabytes worth of memory where data may be stored. If an address space owns any dataspaces, then a Dataspace Anchor Block (DAB) construct
15
is provided that includes or points to information about all the dataspaces owned by the particular address space. It is understood that a particular “address space” may own many dataspaces. For instance, the DAB
15
is shown in
FIG. 1
as including pointers for linking a data space Pageable Frame Queue (PFQ)
12
comprising all the frames allocated to all the data spaces owned by an address space. This queue
12
may include a queue of allocated frames to back virtual storage for a dataspace, which frames may be stolen (i.e., capable of being migrated by the operating system) to a slower medium such as auxiliary storage if a real storage shortage exits in the system.
As shown in
FIG. 1
, for example, pageable frame queue
12
includes PFTEs
14
associated with frames of a first data space and PFTEs
16
associated with frames of a second data space. It is understood that the queue
12
may comprise PFTEs for pageable frames associated with many user dataspaces. As shown, the queue
12
is a double threaded queue anchored in the Dataspace Anchor Block (DAB)
15
with each PFTEs
14
,
16
of the queue maintaining forward and back pointers for referencing other PFTE in the queue
12
. Queue length for user dataspace queues is only bound by the amount of real storage available.
That is, currently, every address space in OS/390 has a virtual address limit of two (2) Gigabytes. Thus, even if the entire address space was backed in real (main processor storage) only 512K PFTE control blocks (2 Gbytes divided by 4Kbytes, as each frame/page is 4 Kbytes) are needed to be queued to any queue that represents the amount of real storage allocated to a particular address space. As mentioned, an address space may own many dataspaces and all the frames (PFTEs) allocated to all of those dataspaces are queued on a long single queue
12
. Thus, if an address space owned five (5) dataspaces and each dataspace had 2 Gbytes of virtual storage, then if all 5 dataspaces were backed for 2 Gbytes worth of storage for each dataspace, the dataspace frame queue
12
would be 10 Gbytes/4 k=2.5G long. So the more dataspaces an address space owns, the longer the dataspace frame queue
12
anchored from the DAB
15
would be. In the OS/390 architecture, the maximum real (main processor) storage is 2 Gbytes. So for the given example, all five 5 dataspaces could never be backed in real storage at the same time. However, with newer 64-bit architectures (e.g., z/Architecture), the maximum real storage for an OS/390 system is 64 Gbyte (and it will grow in the future). Therefore, in z/Architecture, the potential is that the dataspace queue will grow without a bound.
Referring back to
FIG. 1
, periodically, this pageable frame queue
12
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) in the OS/390 system, for example. UIC update exploits the RRBE (reset reference bit extended instruction) which, besides resetting the reference bit associated with the frame, returns a condition code which indicates whether the frame is referenced and/or changed. In the case where the frame is referenced, the frame's UIC value is set, e.g., to zero, to indicate when the frame was last referenced.
Any such system must periodically process real storage to determine whether the storage has been referenced since the last time it has been processed and if so, make the frame a less desirable steal candidate. Thus, when a UIC update is performed, each PFTE that is in use for a particular address space is processed to determine whether its corresponding frame has been referenced. If the corresponding frame has been referenced, the PFTE is moved to the back of the PFTE queue. Thus, 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.
In the IBM OS/390 the LRU algorithm is implemented by keeping an Unreferenced Interval Count for each in-use frame in the system, and by keeping frames on in-use frame queues ordered by descending UIC. Currently, the UIC update task (LRU task) gets a list of address spaces to process and continues to run until all the frame queues for every address space on the list are processed. The UIC update process runs disable with spin locks held for serialization purposes.
If the LRU update task runs a long time, it may cause other processors in the system to exhibit a condition referred to as Excessive Spin Condition (also called a “spin loop”). This condition results when a processor requests a resource such as a lock that is not available because another processor holds the lock. The processor requesting the lock will continue testi
Sutherland Danny R.
Tzortzatos Elpida
Yocum Peter B.
Kinnaman, Jr. William A.
Scully Scott Murphy & Presser
Takeguchi Kathy
Yoo Do Hyun
LandOfFree
Excessive spin detection and avoidance for systems using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Excessive spin detection and avoidance for systems using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Excessive spin detection and avoidance for systems using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3153050