System for maintaining a buffer pool

RELATED APPLICATIONS

[0001] This application is a Continuation/Divisional of U.S. application Ser. No. 09/595,667 entitled “System for Maintaining Buffer Pool,” by Albert A. Hopeman et al. (filed on Jun. 19, 2000), which is a Continuation-in-Part of U.S. application Ser. No. 08/866,518, entitled “System for Maintaining a Shared Cache in a Multi-Threaded Computer Environment,” by James E. Carey (filed on May 30, 1997) and U.S. application Ser. No. 08/866,619, entitled “Computing Systems for Implementing A Shared Cache,” by James E. Carey (filed on May 30, 1997), the entire teachings of which are incorporated herein by reference.

BACKGROUND

[0002] A multi-threaded large scale computer system, such as a database management system (“DBMS”), supports a number of different users concurrently. In a multi-threaded computer system there is only one execution of the software; that is, only one process. From the one process, a user thread is created for each user. All the user threads share the same process memory space, because they are part of the same process.

[0003] A cache is a storage area operating between a processor and another, slower storage area (such as a disk). Although, other schemes may exist, typical cache memory is evenly divided into a fixed number of finitely sized cache memory blocks, called a page. The cached data includes pages which have stored therein currently executing instructions and currently referenced data. The page stored in each cache memory block is typically controlled and managed through control blocks, there being a correspondence between a control block and a cache memory block. If a user thread references an instruction or data not in memory; then a page fault occurs, which causes the relevant page to be read from disk into the cache. Such an arrangement is typical of cache memory. Problems occur when more pages need to be cached than there are available cache blocks in the cache requiring reclamation of pages.

SUMMARY

[0004] In accordance with a particular embodiment of the invention, a public memory structure is utilized to store data that is shareable between a plurality of users in a multi-threaded computing environment. In contrast to the prior art, a cache memory area on a server is used to store public, shareable data and private, non-shareable data without using locks to negotiate resource ownership. Consequently, there are public and private pages stored in global memory. The private pages are those that are modifiable by a user and the public pages are those that are only readable by one or more users.

[0005] One aspect of the invention is to manage memory on a computer. From the memory there are a plurality of cache memory blocks cooperatively shared by processing threads executing on the computer. These processing threads include user sessions and resource managers.

[0006] The user threads consume page data stored on the cache memory blocks. Each user thread has a public view of unmodified cached pages and can have modified cached pages in a private view. During on-line analytical processing (OLAP), the user threads process the cached pages. For pages that are only read by the user thread, the public view is used to access the necessary cache memory block, which may be read by multiple users. When an analysis requires modifying data, however, access through a public view is inappropriate. Instead, the cache memory block pointed to by the public view is copied to a new cache memory block. The user thread is then assigned a private pointer to the copied pages, and can modify the data in this private view without affecting data viewed by other threads.

[0007] The resource managers ensure that the user threads cooperate to function effectively. In particular, a paging manager interfaces the user threads with the cache memory space to retrieve pages from disk.

[0008] In accordance with one embodiment of the invention, a computer-implemented program manages memory in a computer having a plurality of memory blocks. These memory blocks can be a cache memory area. Data is stored in memory blocks, including a first memory block and a second memory block. First and second user sessions or user threads execute in the computer, with the first user session having a global view of the first memory block data and the second user session having a global view of the first memory block data and a private view of the second memory block data. In a particular, the first and second user sessions are threads in a multi-threaded computer system.

[0009] The user threads can execute resource manager instructions to map data stored in a cache memory block with a location of the cache memory block in the computer. The resource manager also transfers data from a database into a cache memory block and stores generational views of the data. In particular, the data is retrieved from a multi-dimensional database.

[0010] A particular method facilitates simultaneous analysis of data in multiple sessions in a computer. First, data is retrieved from storage into public blocks of a shared memory space. These public blocks store data for global read access by a plurality of user sessions. Second, public blocks of data are selectively copied into private blocks of the shared memory space. Each private block stores data for private read and write access by a single user session. Upon read access to a data item by a user session, the data item is read if present from a private block accessible by the user session. If the data item is not present on a private block accessible by the user session, the data item is read from a public block. Upon write access to a data item by the user session, the data item is written to a private block if present in a private block accessible by the user session. If the private block is not already present, then data is copied from a public to a private block for access by the user session.

[0011] A dedicated collector task can be used to reclaim memory blocks. A list of free memory blocks is stored in the computer. A triggering event is generated based on the amount of free memory blocks in the free list. The triggering event triggers a dedicated collector to reclaim memory blocks to the free list.

[0012] The user sessions and the dedicated collector task can be implemented as processing threads in a multi-threaded computing system. In particular, the computing system can include a plurality of processing units for executing the threads. However, aspects of the invention can also be applied to processes in a multi-process architecture. As such, the term data accessor will be understood to encompass any computing mechanism to access or manipulate data, including threads and processes. By utilizing a dedicated collector thread, any processing penalty encountered during the reclamation process is absorbed by the collector thread. Thus the user session threads continue to operate normally, making the reclaiming of cache memory blocks by the dedicated collector task thread transparent to the user session threads.

[0013] As the number of user session threads concurrently executing in the system increases however, the number of allocatable cache memory blocks stored on the free list decreases. The use of a single dedicated collector task thread can reduce performance of the system because, after requesting a memory block, if the free list is empty, a user session thread must wait until the single dedicated collector task thread reclaims a memory block and stores it on the free list. Also, deadlock can occur if there are no memory blocks on the free list. For example, the single dedicated collector task thread could be waiting for a user session thread to complete after calling the user session thread to perform an action for the single dedicated collector task thread and the user session thread could be waiting for the single dedicated collector task thread to add a memory block to the free list. There is consequently a need for an alternative method for collecting memory blocks for use by multiple user session threads in a multi-threaded computer system.

[0014] In particular, the user thread collector can be a routine executed in the user thread. The collector searches shared memory for a collectable block by, for example, randomly selecting an index to a block in shared memory and determining if the selected block is collectable. Upon determining that a previously selected block is not collectable, the user thread collector can successively select a next index to search and determine if the selected next block is collectable. The next index may be selected by incrementing the previously selected index. The actions of selecting and determining can be repeated until a collectable block is found.

[0015] By allowing each user thread collector to request reclamation of a block for use by the user thread, the user thread does not have to wait for a single dedicated collector thread to reclaim a block. Thus, potential deadlock is avoided. Also, with each user thread collector in a user thread responsible for reclamation of blocks, by randomly selecting an index to a block in shared memory, avoids potential deadlock and the need for a free list of blocks and the associated logic for controlling the free list is no longer required, reducing the memory required in the computer system.

BRIEF DESCRIPTION OF THE DRAWINGS

[0016] The foregoing and other objects, features and advantages of the system for maintaining a buffer pool will be apparent from the following more particular description of particular embodiments, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

[0017]FIG. 1 is a schematic block diagram of an on-line analytical processing system embodying the invention;

[0018]FIG. 2 is a schematic block diagram of a page management system with a dedicated collector thread;

[0019]FIG. 3 illustrates one of the page control blocks used in the embodiments shown in FIG. 1 and FIG. 5;

[0020] FIGS. <b>4</b>A-<b>4</b>B illustrate a flow chart of a collector operation in accordance with the embodiment of the invention with a shared collector shown in FIG. 2;

[0021]FIG. 5 illustrates a plurality of user threads executing in a memory in a computer system with each user thread having a respective user thread collector;

[0022]FIG. 6 is a flow diagram of the steps implemented in the initialization routine shown in FIG. 5;

[0023]FIG. 7 is a flow diagram of the steps to get a page buffer for a user thread implemented in one of the collectors shown in FIG. 4.

DETAILED DESCRIPTION

[0024]FIG. 1 is a schematic block diagram of an on-line analytic processing (OLAP) system embodying the invention. A server <b>1</b> responds to requests from a plurality of client users <b>20</b>₁, <b>20</b>₂, . . . , <b>20</b>_n. To satisfy client requests, the server <b>1</b> retrieves data from a data storage warehouse <b>30</b>, which can include various databases, such as relational databases <b>32</b>, multi-dimensional databases <b>34</b> and temporary databases <b>36</b> stored on disk.

[0025] The server <b>1</b> includes at least one central processing unit (CPU) <b>2</b>₁, <b>2</b>₂, . . . , <b>2</b>_p. The CPUs <b>2</b> execute client or user sessions and system management processes to operate on data stored in memory <b>10</b>, which includes an OLAP engine <b>12</b> and a cache memory <b>18</b>. The OLAP engine <b>12</b> includes a kernel <b>13</b>, a paging manager <b>15</b> and a thread manager <b>17</b>. The user sessions can execute paging manager instructions, including page transfer functions (not shown), to manage pages in memory <b>10</b>.

[0026] The user sessions and system management processes can include processing threads managed by the thread manager <b>17</b> in a multi-threaded OLAP engine <b>12</b>. That is, user sessions can accomplish tasks by asynchronously executing processing threads. Embodiments of the system take the form of computer executable instructions embedded in a computer-readable format on a CD-ROM, floppy or hard disk, or another computer-readable distribution medium. These instructions are executed by one or more CPUs <b>2</b>₁, <b>2</b>₂, . . . , <b>2</b>_pto implement the OLAP engine <b>12</b>.

[0027]FIG. 2 is a schematic block diagram of a page management system shown in FIG. 1. The paging manager <b>15</b> receives page requests from the client users <b>20</b>₁, <b>20</b>₂, . . . , <b>20</b>_nand insures that current pages are retrieved from disk <b>30</b> and stored in the shared cache memory <b>18</b>. The cache memory <b>18</b> can be global memory or memory assigned to an on-line analytical processing (“OLAP”) application by a server operating system.

[0028] The paging manager <b>15</b> includes a private memory section <b>40</b>_pand a public memory section <b>40</b>_G. The private section <b>40</b>_Pcan include a plurality of private workspaces <b>4</b>₁, <b>41</b>₂, . . . , <b>41</b>_n. There is one private workspace <b>41</b> for each user session. A private workspace <b>41</b> includes private pagespace views <b>50</b>_a, <b>50</b>_b, . . . , <b>50</b>_z, which record information about writable pagespaces referenced by the current user session.

[0029] The public section <b>40</b>_Gis organized based on open databases. For ease of understanding, the system is illustrated as having one open database. However, it should be understood that there are generally a plurality of open databases being accessed by the client users. For each open database there is a public workspace <b>45</b> in the public memory section <b>40</b>_Ghaving, in general, a plurality of generational pagespace views <b>60</b>_a, <b>60</b>_b, . . . , <b>60</b>_g. Each private pagespace view <b>50</b> is associated with a particular generation of the database. For ease of description, embodiments of the system will be described with reference to a single database having a single generation in memory.

[0030] The cache memory <b>18</b> includes page buffers <b>84</b>₁, <b>84</b>₂, . . . , <b>84</b>_xeach having an associated page control block (“PCB”) <b>82</b>₁, <b>82</b>₂, . . . , <b>82</b>_x. Each free page buffer <b>84</b> holds a page of data read from storage <b>30</b>. In accordance with a particular embodiment, the free page buffers <b>84</b> each store data in blocks of 4K bytes, defined as a page. It should be understood that the page size can be chosen to be either less than or greater than 4K bytes. A page control block <b>82</b> includes data fields used to control and access the associated page buffer <b>84</b>. The cache memory <b>18</b> is shared by the user sessions to store both public and private data.

[0031] It is important to note that there is no physical division between public and private data pages. That is, a particular free page buffer <b>84</b> simply stores a page of data, which can be either public or private data. The public workspace <b>45</b> and the private workspaces <b>41</b>₁, . . . , <b>41</b>_ninclude indexes to the appropriate page control blocks <b>82</b>₁, . . . , <b>82</b>_x.

[0032] As discussed above, pages retrieved from disk <b>30</b> are stored into a page buffer <b>84</b>. To facilitate this function, the paging manager <b>15</b> maintains a list of all page buffers <b>84</b>. For example, a free list pointer <b>92</b> can point to a linked list of page control blocks <b>82</b> associated with free page buffers <b>84</b>. When the paging manager <b>15</b> needs a free buffer, the first page control block on the free list is popped from the top of the linked list, moving the free list pointer to the next page control block in the linked list.

[0033] In accordance with one embodiment, the user sessions do not directly maintain the cache memory area. Because of the particular use of pagespaces and pointers to denote page ownership, a user session requiring a new page may deadlock with another user session. In such a situation, each user session can be referencing a page that the other user session has chosen to swap from memory. To avoid such a deadlock, a separate dedicated collector thread <b>90</b> can be utilized to manage page removal from the cache memory area.

[0034] To minimize processing delays which can occur when the free list becomes empty, the paging manager <b>15</b> maintains a counter of the number of entries on the free list. Every time a page control block is removed from the free list, the count in compared with a minimum threshold value. If the minimum threshold is met, then the paging manager begins a collecting operation through the dedicated collector thread <b>90</b> to free up additional page buffers. The minimum threshold value can be chosen based on a historical operational profile of the system to maximize the number of page buffers <b>84</b> in use while reducing the chances that there are no free page buffers at any time. For example, the minimum threshold value can be initially chosen to be 10% of the total page buffers. The minimum threshold can also be dynamically adjusted by the paging manager <b>15</b> over time.

[0035]FIG. 3 illustrates one of the page control blocks <b>82</b> shown in FIG. 2. The page control block <b>82</b> is a control structure stored in cache <b>18</b> (FIG. 2). The page control block <b>82</b> includes fields which are used to manage the page buffers <b>84</b> in the cache <b>18</b>. The page control block <b>82</b> includes the following fields: a page address <b>200</b>, an owning page space <b>202</b>, a Most Recently Used (“MRU”) time field <b>204</b>, a PCB lock <b>206</b>, an owner workspace field <b>208</b>, a version control field <b>210</b>, an available field <b>212</b> and an MRU field <b>214</b>.

[0036] The page address field <b>200</b> stores the location of the associated page buffer <b>84</b> in cache <b>18</b>. The owning page space field <b>202</b> identifies whether the page buffer <b>84</b> is local or global. A timestamp is stored in the MRU time field <b>204</b> every time the page buffer <b>84</b> associated with the page control block <b>82</b> is accessed. The PCB lock <b>206</b> is generally obtained before fields in the page control block <b>82</b> are modified. The owner workspace field <b>208</b> stores the address of the owning workspace. The version control field <b>210</b> stores the version of the page control block <b>82</b>. The available field <b>212</b> is a one-bit wide status field, the state of which indicates whether the page buffer <b>84</b> associated with the page control block <b>82</b> is available for use. The MRU field <b>214</b> is one bit wide, the state of which indicates whether the page buffer <b>84</b> associated with the page control block <b>82</b> is on an MRU list.

[0037] FIGS. <b>4</b>A-<b>4</b>B illustrate a flow chart of a collecting operation <b>300</b> in accordance with an embodiment with a dedicated collector thread <b>90</b>, as shown in FIG. 2. The collector operation <b>300</b> is performed by a specialized dedicated collector thread <b>90</b> in a multi-threaded environment. At step <b>305</b>, the operation checks the startup condition. If a startup condition exists, then processing continues to step <b>307</b> where the dedicated collector thread <b>90</b> allocates cache memory from main memory. Processing then jumps to step <b>380</b>.

[0038] If this is not a startup condition, processing continues to step <b>310</b>. At step <b>310</b>, the dedicated collector thread <b>90</b> scans the page control blocks (“PCBs”) for the least-recently-used (LRU) candidate. In particular, the dedicated collector thread <b>90</b> reads the MRU time field <b>204</b> from each page control block <b>82</b>₁, <b>82</b>₂, . . . , <b>82</b>_x. The page control block having the earliest MRU time, is the LRU candidate. At step <b>315</b>, the dedicated collector thread <b>90</b> locks the LRU candidate, thereby setting the PCB lock <b>206</b> in the page control block <b>82</b>. At step <b>320</b>, the dedicated collector thread <b>90</b> rereads the MRU time field <b>204</b> from the LRU candidate page control block. At step <b>325</b>, the dedicated collector thread <b>90</b> compares the original time value with the reread time value to verify that the page has not been more recently used.

[0039] If the compared time values do not match, then processing continues to step <b>330</b>. At step <b>330</b>, the dedicated collector thread <b>90</b> unlocks the LRU candidate page control block and processing returns to step <b>310</b> to try again.

[0040] If the time values agree (step <b>325</b>), then the page is confirmed as the least-recently-used page and processing continues to step <b>335</b>. At step <b>335</b>, the owning pagespace field <b>202</b> of the page control block <b>82</b> is checked. If the owning pagespace field <b>202</b> is set, then the page is private data to the user session identified by the owner workspace field <b>208</b> and processing continues to step <b>340</b>. At step <b>340</b>, the dedicated collector thread <b>90</b> causes the page buffer to be written to disk, such as an extended database <b>36</b>. In particular, if an extension file needs to be created, the dedicated collector thread <b>90</b> sends a message to the owner user session to do the file creation. Once the extension file exists, the dedicated collector thread <b>90</b> writes to it itself. Processing then continues to step <b>350</b>. If the data has not been modified (as indicated by a null (i.e., public) owning pagespace field <b>202</b>), then the data is public data for read-only access. In that case, processing jumps to step <b>350</b> without rewriting the data to disk.

[0041] At step <b>350</b>, a check of the owning pagespace field <b>202</b> is again made to see if the field is not null (i.e., private data). If the page is private, processing continues to step <b>355</b>, where the page control block pointer is removed from the private index structure (not shown) by setting the private pointer (not shown) to null. If the page is public, processing instead continues to step <b>357</b> where the page control block pointer is removed from the public index structure (not shown) by setting the public pointer (not shown) to null.

[0042] At step <b>360</b>, the version number of the page stored in the version control field <b>210</b> in the page control block <b>82</b> is incremented. At step <b>365</b>, the page control block is put onto a free list of available page control blocks. At step <b>370</b> the page control block is unlocked to make it available for re-use.

[0043] At step <b>375</b>, the dedicated collector thread <b>90</b> tests the number of page control blocks on the free list. If this number is above a preset maximum threshold, then processing continues to step <b>380</b>. If the maximum threshold has not yet been reached, processing returns to step <b>310</b> to search for additional page control blocks to add to the free list. The maximum threshold value can be chosen to optimize the cache memory <b>18</b> based on past performances. For example, the maximum threshold can initially be twice the minimum threshold and can be dynamically adjusted by the paging manager.

[0044] At step <b>380</b>, the dedicated collector thread <b>90</b> suspends itself. It is awakened again when the number of page control blocks <b>82</b> on the free list is reduced to be below the previously-described minimum threshold level. The dedicated collector thread <b>90</b> can be awakened by a write or read operation from a user session when a page buffer is taken from the free list. Although the triggering event may be generated by a user session, it can be generated at the system level.

[0045] Although the dedicated collector thread <b>90</b> has been described as employing an LRU algorithm, other algorithms may be more particularly suitable. For example, in systems having large caches, the computations required to determine the LRU candidate can be very time consuming. It should be recognized, however, that the function of the dedicated collector thread <b>90</b> is to maintain a buffer of free page slots, even during heavy page faulting, without blocking user threads. To accomplish this function, it is recognized that the candidate page slot does not have to be storing the LRU page.

[0046] In accordance with another preferred embodiment, an “old enough” algorithm is employed to find a reclamation candidate that has not been recently used. Instead of the MRU time field <b>204</b>, the dedicated collector thread <b>90</b> can be read an internal counter field in the page control block <b>82</b>, which can be faster to retrieve than a time field. By, for example, knowing the oldest counter value, the dedicated collector thread <b>90</b> can determine a threshold counter value for those pages that are old enough to be reclaimed. Instead of looping through the entire page pool for the single LRU candidate, the dedicated collector thread <b>90</b> can stop the search when finding the first page having a counter which exceeds the threshold; with the realization that this page is likely to be eventually reclaimed under the LRU algorithm anyway. By using such an “old enough” algorithm, the amount of CPU time required by the dedicated collector thread <b>90</b> can be reduced to a few percent of that required for the LRU algorithm.

[0047] In an OLAP system, most data retrieved from storage is read-only data, which is easier to remove from the cache memory than modified data. Any session, however, can cause data in the cache memory to be privately modified. This data may only be used for a relatively brief period of time, but may tend to stay in the cache memory, using the server's page buffers for a private function. Although that situation is acceptable for short time periods, if left unattended much of the cache memory blocks can be allocated as private memory.

[0048] As the number of user session threads concurrently executing in the system increases however, the number of allocatable cache memory blocks stored on the free list decreases. The use of a single dedicated collector thread <b>90</b> can reduce performance of the system because, after requesting a memory block, if the free list is empty, a user session thread must wait until the single dedicated collector thread <b>90</b> reclaims a memory block and stores it on the free list. To improve performance, the collector function can be distributed amongst the user threads.

[0049]FIG. 5 illustrates another embodiment of the page management system shown in FIG. 1. The dedicated collector thread <b>90</b> in the embodiment described in conjunction with FIG. 2 is replaced by a plurality of user thread collectors <b>114</b><i>a</i>-<i>c</i>. A plurality of user threads <b>112</b><i>a</i>-<i>c </i>execute in the thread manager <b>17</b>, with each user thread <b>112</b><i>a</i>-<i>c </i>having a respective user thread collector <b>114</b><i>a</i>-<i>c</i>. The page management system also includes a cache <b>18</b> and a paging manager <b>15</b>.

[0050] The cache <b>18</b> includes a plurality of page buffers <b>84</b> and a plurality of page control blocks (“PCB”s) <b>82</b>, with each page buffer <b>84</b> having an associated page control block <b>82</b>. The paging manager <b>15</b> includes an initialization routine <b>108</b> and a private workspace <b>41</b> and global or public workspace <b>45</b>. The private workspace <b>41</b> and global workspace <b>45</b> have been described earlier in conjunction with FIG. 2.

[0051] The initialization routine <b>108</b> in the paging manager <b>106</b> allocates page buffers <b>84</b> in cache <b>102</b> and initializes the page control blocks <b>82</b> associated with each page buffer <b>84</b>. Before any of the user threads <b>112</b><i>a</i>-<i>c </i>execute in database management system <b>100</b>, all the page buffers <b>84</b> are free and thus are not assigned to any of the user threads <b>112</b><i>a</i>-<i>c</i>. Executing user threads <b>112</b><i>a</i>-<i>c </i>request page buffers <b>84</b> from the cache <b>18</b>.

[0052] The respective user thread collector <b>114</b><i>a</i>-<i>c </i>in the user thread <b>112</b><i>a</i>-<i>c </i>searches the page control blocks <b>82</b> in the cache <b>18</b> for a free page buffer. If no free page buffer is available, the respective user thread collector <b>114</b><i>a</i>-<i>c </i>searches for a Least Recently Used (“LRU”) page buffer <b>84</b>. Upon finding a LRU page buffer <b>84</b>, the user thread collector <b>114</b><i>a</i>-<i>c </i>obtains the page buffer <b>84</b> for the user thread <b>112</b><i>a</i>-<i>c</i>.

[0053]FIG. 6 is a flow diagram of the steps implemented in the initialization routine shown in FIG. 5. The flow diagram is described in conjunction with FIG. 1 and FIG. 5.

[0054] At step <b>600</b>, the initialization routine <b>108</b> initializes global variables shared by all the user thread collectors <b>114</b><i>a</i>-<i>c</i>. The global timestamp variables include(not shown) and mrudelta (not shown). The global timestamp variables are stored in the global workspace <b>45</b> (FIG. 5). The value stored in Mrudelta is dependent on the maximum number of page buffers. Mrudelta is the interval at which the mruval is incremented.

[0055] Mruval is initialized with a value equal to the maximum number of page buffers <b>84</b> divided by 256. An mrucount count variable is used to calculate the next value for mruval. The mrucount is a variable used to determine the mruval. Mrucount is initialized to 0 and reset to 0 after it reaches 255. If mrucount is less than 255, the current value stored in mruval and mrucount is incremented. Processing continues with step <b>602</b>.

[0056] At step <b>602</b>, the initialization routine <b>108</b> allocates page buffers <b>84</b> and associated page control blocks <b>82</b>. The page buffers <b>84</b> are used by the user threads <b>112</b><i>a</i>-<i>c</i>. Processing continues with step <b>604</b>.

[0057] At step <b>604</b>, the initialization routine <b>108</b> initializes the MRU time field <b>204</b> in each page control block <b>82</b> by setting the MRU time field <b>204</b> to the current value of mruval. Processing continues with step <b>606</b>.

[0058] At step <b>606</b>, the initialization routine <b>108</b> determines if the last page control block <b>82</b> has been initialized. If so, processing is complete. If not, processing continues with step <b>604</b>.

[0059]FIG. 7 is a flow diagram of the steps for obtaining a page buffer <b>84</b> implemented in each of the user thread collectors <b>114</b><i>a</i>-<i>c </i>shown in FIG. 5. The flow diagram is described in conjunction with FIG. 3 and FIG. 5. A user thread <b>112</b><i>a</i>-<i>c </i>requests a page buffer <b>84</b> by calling its respective user thread collector <b>114</b><i>a</i>-<i>c</i>. Each user thread collector <b>114</b><i>a</i>-<i>c </i>has a local variable called lastcollect (not shown). Lastcollect stores the mruval calculated after the last collection performed by the user thread collector <b>114</b><i>a</i>-<i>c</i>. The value stored in lastcollect is used to determine if a PCB is collectable.

[0060] At step <b>700</b>, a search mechanism in the user thread collector <b>11</b><b>4</b><i>a</i>-<i>c </i>calculates a MinMRUGen value for the user thread collector <b>114</b><i>a</i>-<i>c </i>in the user thread <b>112</b><i>a</i>-<i>c</i>. The MinMRUGen value is calculated by subtracting the value stored in the global variable Mrudelta from the value stored in the local variable lastcollect. The calculated MinMRUGen value is used to determine which of the page buffers <b>84</b> may be reassigned to a user thread <b>112</b><i>a</i>-<i>c</i>. Processing continues with step <b>702</b>.

[0061] At step <b>702</b>, a randomizer in the search mechanism in the user thread collector <b>114</b><i>a</i>-<i>c </i>randomly selects a page control block <b>82</b> from the array of page control blocks. The randomizer randomly selects an index for the array. The index is selected from the set of numbers 1 through the maximum number (x) of page control blocks <b>82</b> in the array of page control blocks <b>84</b>. After selecting a page control block <b>82</b> the user thread collector <b>114</b><i>a</i>-<i>c </i>may obtain exclusive access to the page buffer associated with the page control block <b>82</b> at the selected index by getting the PCB lock <b>206</b> in the page control block <b>82</b>. Processing continues with step <b>704</b>.

[0062] At step <b>704</b>, a determiner in the search mechanism in the user thread collector <b>114</b><i>a</i>-<i>c </i>examines the available field <b>212</b> in the selected page control block <b>82</b>. The state of the available field <b>212</b> indicates whether the selected page control block <b>82</b> is free and can be assigned to the requesting user thread <b>112</b><i>a</i>-<i>c</i>. If the determiner determines from the state of the available field <b>212</b> that the selected page control block <b>82</b> is free, processing continues with step <b>706</b>. If not, processing continues with step <b>706</b>.

[0063] At step <b>706</b>, the determiner in the search mechanism in the user thread collector <b>114</b><i>a</i>-<i>c </i>examines the MRU time field <b>204</b> in the selected page control block <b>82</b>. If the value stored in the MRU time field <b>204</b> is greater than the calculated MinMruGen value, processing continues with step <b>710</b>. If not, processing continues with step <b>708</b>.

[0064] At step <b>708</b>, a sequencer in the search mechanism in the user thread collector <b>114</b><i>a</i>-<i>c </i>selects another page control block <b>82</b>. The sequencer selects the next page control block <b>82</b> by incrementing the PCB array index. The selection of the next page control block <b>82</b> is not limited to incrementing the PCB array index, the next page control block <b>82</b> may also be selected by decrementing the page control block array index or by randomly selecting another array index. Processing continues with step <b>704</b>.

[0065] At step <b>710</b>, the determiner in the user thread collector <b>114</b><i>a</i>-<i>c </i>determines if it has exclusive access to the selected page control block <b>82</b>. If so, processing continues with step <b>714</b>. If not, processing continues with step <b>712</b>.

[0066] At step <b>712</b>, the PCB lock <b>206</b> in the page control block <b>82</b> is obtained so that the user thread collector <b>114</b> has exclusive access to the selected page control block <b>82</b>. Processing continues with step <b>714</b>.

[0067] At step <b>714</b>, an action mechanism in the user thread collector <b>114</b><i>a</i>-<i>c </i>collects the block for use by the user thread <b>112</b>. To collect the block, the action mechanism modifies the contents of the selected page control block <b>82</b> before providing the page control block <b>82</b> to the user thread <b>112</b><i>a</i>-<i>c</i>. The action mechanism modifies the available field <b>212</b> to indicate that the page control block <b>82</b> is no longer available, stores the mruval in the MRU time field <b>204</b> and in lastcollect. Processing continues with step <b>714</b>.

[0068] At step <b>716</b>, the action mechanism provides the modified selected page control block <b>82</b> to the requesting user thread collector <b>114</b><i>a</i>-<i>c</i>. Processing continues with step <b>718</b>.

[0069] At step <b>718</b>, the action mechanism releases the lock. Processing is complete.

[0070] By randomly selecting a page control block <b>82</b> in the PCB array, multiple user thread collectors <b>114</b><i>a</i>-<i>c </i>may obtain page control blocks <b>82</b> for user threads <b>112</b><i>a</i>-<i>c </i>in parallel, thus increasing the speed at which a page control block <b>82</b> can be obtained. As each user thread collector <b>114</b><i>a</i>-<i>c </i>checks first to see if the selected page control block is free by examining the available field <b>212</b>, no free list is required thereby reducing the memory contention bottleneck and reducing the memory required in the paging manager <b>15</b>. Also, overhead for locking is reduced if the PCB lock <b>206</b> is obtained only after determining that a page control block <b>82</b> can be used.

[0071] In an alternative embodiment, a paging management system may include a dedicated collector thread <b>90</b> as described in conjunction with FIG. 2 and a plurality of user thread collectors <b>114</b><i>a</i>-<i>c </i>as described in conjunction with FIG. 5. The dedicated collector thread <b>90</b> maintains a free list of page buffers through a free list pointer <b>92</b> as described in conjunction with FIGS. <b>4</b>A-<b>4</b>B.

[0072] If there are no page buffers <b>84</b> available on the free list (all the page buffers <b>84</b> are assigned to user threads <b>112</b><i>a</i>-<i>c</i>), the respective user thread collector <b>114</b><i>a</i>-<i>c </i>in the user thread <b>112</b><i>a</i>-<i>c </i>searches the page control blocks <b>82</b> in the cache <b>18</b> for a Least Recently Used (“LRU”) page buffer <b>84</b> as described in conjunction with FIG. 6 to obtain a LRU page control block <b>82</b> from the PCB array in cache <b>18</b>. Upon finding a LRU page buffer <b>84</b>, the user thread collector <b>114</b><i>a</i>-<i>c </i>obtains the page buffer <b>84</b> for the user thread <b>112</b><i>a</i>-<i>c. </i>

[0073] In yet another embodiment in which both the dedicated collector thread <b>90</b> and user thread collectors <b>114</b><i>a</i>-<i>c </i>are provided, a method can be provided to select the dedicated collector or the user thread collectors <b>114</b><i>a</i>-<i>c </i>dependent on the environment in which the paging management system is operating. For example, the dedicated collector thread <b>90</b> can be selected for a single-process build environment and the user thread collectors <b>114</b><i>a</i>-<i>c </i>can be selected if there are a large number of concurrent user threads <b>112</b> executing.

[0074] It will be apparent to those of ordinary skill in the art that methods involved in the present system may be embodied in a computer program product that includes a computer usable medium. For example, such a computer usable medium can include a readable memory device, such as a solid state memory, hard drive device, a CD-ROM, a DVD-ROM or a computer diskette, having computer readable program code segments stored thereon. The computer readable medium can also include a communications or transmission medium, such as a bus or communications link, either wired, optical or wireless having program code segments carried thereon as digital or analog data signals.

[0075] While this invention has been particularly shown and described with references to particular embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention encompassed by the appended claims.