Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output access regulation
Reexamination Certificate
2002-02-27
2004-10-19
Peikari, B. James (Department: 2186)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output access regulation
C710S040000, C710S041000, C710S042000, C710S043000, C710S044000, C710S054000, C370S395420, C370S395400, C711S136000, C711S160000
Reexamination Certificate
active
06807588
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a method for an operating system to build and maintain sectioned, ordered queues to achieve a reduction in operating costs when traversing these queues and manipulating their queue entries. More particularly, the present invention relates to a more efficient method for an operating system to recover real storage from an address space for potential use in another address space. In this application, the queues that represent the real storage in use by an address space are very long queues.
2. Description of the Related Art
Typically, in operating systems that support multiple virtual address spaces and that have the ability to support more virtual addresses (hereinafter referred to as pages) than can be backed simultaneously by real storage addresses (hereinafter referred to as frames), it is sometimes necessary to reallocate the use of a frame to a different address space. This technique is called paging and allows the operating system to reclaim a subset of the resources of one address space and use that subset for immediate operations in another address space. When the system needs to reference or update a page, a frame is obtained and the dynamic address translation tables for that page are updated using a process called ‘backing’, which indicates that real memory is associated with that page.
This process is described for the IBM OS/390 operating system in such publications as the IBM Redbooks
ABCs of OS/
390
System Programming Volume
1, SG24-5597-00, pages 43-71 (April 2000), and
OS/
390
Version
2
Release
10
Implementation
, SG24-5976-00, pages 9-34 (March 2001), both of which are incorporated herein by reference. Referring to
FIG. 1
, when an instance
10
of the OS/390 operating system (OS) needs frames to back a virtual storage request, it goes to a queue
12
of available frames
14
to satisfy the request. A system resource manager (SRM)
18
checks periodically to ensure that there are a reasonable number of frames on this queue
12
for this purpose. OS instance
10
maintains an in-use frame queue
12
for each separate address space
16
. If the SRM
18
detects a shortage, it uses a least recently used (LRU) algorithm to determine which in-use frames in the system are the best candidates to be reclaimed in order to replenish the supply of available frames. (Using this algorithm, frames that have not recently been referenced are the best candidates to be reclaimed.) This process for reclaiming frames is hereinafter referred to as stealing.
A real storage manager (RSM)
20
identifies how recently a frame has been referenced by maintaining an unreferenced interval count (UIC) value for each frame in use by an address space.
16
In order for the system to more quickly identify which frames are the best candidates to steal, the real storage manager (RSM)
20
maintains the address space frame queues in UIC order, with the least recently referenced frames at the beginning of the queue
12
. Periodically, the RSM
20
performs update processing, which determines whether frames have been referenced, and if so, moves them to the end of the frame queue
12
. Upon completion of the update processing, the least recently referenced frames remain at the beginning of the queue
12
with their UIC values incremented by a constant value and the most recently referenced frames are at the end of the frame queue
12
with their UIC values reset to zero.
The SRM
18
selects the targeted address spaces
16
to steal from, and also indicates a minimum UIC value which a frame to be stolen from any targeted frame queue
12
can have. The SRM
18
also specifies the total number of frames required to satisfy the steal request. The RSM steal processing then attempts to satisfy the SRM's request by traversing the indicated address spaces' frame queues and selecting the frames that meet the SRM's UIC steal criteria. The RSM steal processing also makes one last check to determine whether or not a frame has been recently referenced, and, like the RSM UIC update process, moves any referenced frames to the end of the frame queue
12
with their UIC values reset to zero. If the RSM steal process is unable to fully satisfy the SRM's request, the SRM
18
may elect to create a new steal request with different parameters, and this process may repeat itself until the system's needs for frames is satisfied.
With new advances in hardware design, a larger virtual storage area is made available to address spaces
16
in an operating system. The typical approach of keeping the frame queues associated with an address space
16
in a linear structure may cause system performance degradation when traversing the queues. In a multitasking environment, processing such a queue
12
requires resource serialization which may prevent other processes from being dispatched or may even cause abnormal task termination if the processing of the longer queue
12
exceeds the system's specified time-out intervals. The RSM UIC update and RSM UIC steal processes may no longer perform their functions effectively when traversing or manipulating the frame queues which represent this larger virtual storage area.
SUMMARY OF THE INVENTION
In general, the present invention contemplates a method and apparatus for maintaining a queue in an information handling system, in which there are defined a plurality of queue sections arranged in order from a first queue section to a last queue section. Each of the queue sections contains one or more queue entries arranged in order from a first queue entry to a last queue entry. A weight factor is defined for each queue section and for each queue entry in the queue sections. Each of the queue entries has an effective weight factor formed by combining the weight factor defined for the queue section with the weight factor defined for the queue entry.
The queue entries may correspond to available storage locations, in particular ranges of real storage addresses. The effective weight factor for such a queue entry represents an amount of time the storage location corresponding to the entry has not been referenced.
A new entry is added to the last queue section to indicate a newly available corresponding storage location, while one or more queue entries having at least a predetermined effective weight factor and corresponding to storage locations that have not been referenced in a previous time interval are deleted from the first queue section to indicate that the corresponding storage locations are no longer available.
Periodically, the effective weight factors of the queue entries are updated in accordance with whether the corresponding storage locations have been referenced. This is done by incrementing the effective weight factors of queue entries corresponding to storage locations that have not been referenced in a previous time interval and resetting the effective weight factors of queue entries corresponding to storage locations that have been referenced in a previous time interval. During such updating, the queue entries are maintained in the sections in order of their effective weight factors. Preferably, the individual weight factor defined for each queue entry in the first queue section is updated in accordance with whether the corresponding storage location has been referenced, while only the weight factor defined for each remaining queue section is updated without updating the individual weight factor defined for each queue entry in such remaining queue section. Each queue entry in the first queue section corresponding to a referenced storage location is moved to another section.
Preferably, the number of queue entries in each of the queue sections is maintained within a predetermined permissible range defined for the queue sections, by moving queue entries between queue sections and creating or deleting sections as needed. The weight factors defined for the moved queue entries are adjusted so that their effective weight factors in the new queue sec
Butler Tracy D.
Emmes David B.
Hoang Tri M.
Ndoye Mariama
Sutherland Danny R.
Kinnaman, Jr. William A.
Peikari B. James
LandOfFree
Method and apparatus for maintaining order in a queue by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for maintaining order in a queue by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for maintaining order in a queue by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3306993