the following definitions and explanations provide background information pertaining to the technical field of the present invention , and are intended to facilitate the understanding of the present invention without limiting its scope : cache : a temporary storage area for frequently - accessed or recently - accessed data . having certain data stored in cache speeds up the operation of the processor . cache miss : a failure to find requested data in the cache ; consequently , the slower auxiliary memory must be searched . empirically universal : performing as well as a cache system whose tunable parameter is fixed a priori to match a workload with known characteristics and to match a given cache size . hit ratio : the frequency at which a page is found in the cache as opposed to finding the page in the auxiliary memory . miss ratio : the frequency at which pages must be paged into the cache online : requiring no a priori knowledge about the page reference stream or the workload and responding to a changing and evolving workload by observing it . page : uniformly sized objects , items , or block of memory in cache and auxiliary memory . [ 0051 ] fig1 illustrates an exemplary high - level architecture of a computer memory system 100 comprising an adaptive replacement cache policy system 10 that utilizes , a cache 15 and an auxiliary memory 20 . system 10 includes a software programming code or computer program product that is typically embedded within , or installed on a computer . alternatively , system 10 can be saved on a suitable storage medium such as a diskette , a cd , a hard drive , or like devices . the design of system 10 presents a new replacement policy . this replacement policy manages twice the number of pages present in cache 15 ( also referred to herein as dbl ( 2c )). system 10 is derived from a fixed replacement policy that has a tunable parameter . the extrapolation to system 10 transforms the tunable parameter to one that is automatically adjusted by system 10 . the present cache replacement policy dbl ( 2c ) manages and remembers twice the number of pages present in the cache 15 , where c is the number of pages in a typical cache 15 . as seen in fig2 the cache replacement policy dbl ( 2c ) maintains two variable - sized lists l 1 205 and l 2 210 . list l 1 205 contains pages requested only once recently , and establishes the recency aspect of page requests . list l 2 210 contains pages requested at least twice recently , and establishes the frequency aspect of page requests . the pages are sorted in each list from most recently used , mru , to least recently used , lru , as shown by the arrows in list l 1 205 and list l 2 210 . the present cache replacement policy dbl ( 2c ) replaces the lru page in list l 1 205 if list l 1 205 contains exactly c pages ; otherwise , it replaces the lru page in list l 2 210 . the method of operation 300 for the cache replacement policy dbl ( 2c ) is further shown fig3 . the policy attempts to keep both lists l 1 and l 2 to contain roughly c pages . given that a page x is requested at block 302 , the cache replacement policy dbl ( 2c ) first determines at decision block 305 whether input page x exists in list l 1 205 . if so , then page x has recently been seen once , and is moved from the recency list , l 1 205 , to the frequency list , l 2 210 . the cache replacement policy dbl ( 2c ) deletes page x from list l 1 205 at block 310 and moves page x to the top of list l 2 210 at block 315 . page x is now the most recently requested page in list l 2 210 , so it is moved to the top of this list . at block 320 , the cache replacement policy dbl ( 2c ) of system 10 updates the number of pages in each list as shown , where l 1 is the number of pages in list l 1 205 , and l 2 is the number of pages in list l 2 210 . the total number of pages in the cache replacement policy dbl ( 2c ) is still at most 2c , since a page was simply moved from list l 1 205 to list l 2 210 . if at decision block 305 page x was not found in list l 1 205 , the cache replacement policy dbl ( 2c ) determines , at decision block 325 , if page x is in list l 2 210 . if so , page x is now the most recently requested page in list l 2 210 and the cache replacement policy dbl ( 2c ) moves it to the top of the list at block 330 . if page x is in neither list l 1 205 nor list l 2 210 , it is a miss and the cache replacement policy dbl ( 2c ) must decide where to place page x t . the sizes of the two lists can fluctuate , but the cache replacement policy dbl ( 2c ) wishes to maintain , as closely as possible , the same number of pages in list l 1 205 and list l 2 210 , maintaining the balance between recency and frequency . if there are exactly c pages in list l 1 205 at decision block 335 , the cache replacement policy dbl ( 2c ) deletes the least recently used ( lru ) page in list l 1 205 at block 340 , and makes page x the most recently used ( mru ) page in list l 1 205 at block 345 . if the number of pages l 1 in list l 1 205 is determined at decision block 335 to be less than c , the cache replacement policy dbl ( 2c ) determines at decision block 350 if the cache 15 is full , i . e ., whether l 1 + l 2 = 2c . if not , the cache replacement policy dbl ( 2c ) inserts page x as the mru page in list l 1 205 at block 355 , and adds one to l 1 , the number of pages in l 1 205 , at block 360 . if the cache 15 is determined to be full at decision block 350 , the cache replacement policy dbl ( 2c ) deletes the lru page in list l 2 210 at block 365 and subtracts one from l 2 , the number of pages in list l 2 210 . having made room for a new page , the cache replacement policy dbl ( 2c ) then proceeds to blocks 355 and 360 , inserting x as the mru page in l 1 205 and adding one to l 1 , the number of pages in list l 1 205 . pages can only be placed in list l 2 210 , the frequency list , by moving them from list l 1 205 , the recency list . new pages are always added to list l 1 205 . the method 300 of system 10 is based on the following code outline : if ( l1 -& gt ; hit ( page )){ l1 -& gt ; delete ( page ); l2 -& gt ; insert_mru ( page ); } else if ( l2 -& gt ; hit ( page )){ l2 -& gt ; delete ( page ); l2 -& gt ; insert_mru ( page ); } else if ( l1 -& gt ; length ( )== c ){ l1 -& gt ; delete_iru ( ); l1 -& gt ; insert_mru ( page ); } else { if ( l1 -& gt ; length ( ) + l2 -& gt ; length ( )== 2 * c ){ l2 -& gt ; delete_iru ( ); } l1 -& gt ; insert_mru ( page ); } based on the performance of the cache replacement policy dbl ( 2c ) in method 300 of fig3 it can be seen that even though the sizes of the two lists l 1 205 and l 2 210 fluctuate , the following is always true : in addition , the replacement decisions of the cache replacement policy dbl ( 2c ) at blocks 335 and 350 equalize the sizes of two lists . system 10 is based on method 300 shown of fig3 . system 10 contains demand paging policies that track all 2c items that would have been in a cache 15 of size 2c managed by the cache replacement policy dbl ( 2c ), but physically keeps only ( at most ) c of those pages in the cache 15 at any given time . with further reference to fig4 system 10 introduces the concept of a “ dynamic ” or “ sliding ” window 425 . to this end , the window 425 has a capacity c , and divides the list l 1 into two dynamic portions b 1 410 and t 1 405 , and further divides the list l 2 into two dynamic portions b 2 420 and t 2 415 . these dynamic list portions meet the following conditions : 1 . list portions t 1 405 and b 1 410 are disjoint , as are list portions t 2 415 and b 2 420 . 2 . list l 1 205 is comprised of list portions b 1 410 and t 1 405 , as follows : 3 . list l 2 210 is comprised of list portions b 2 420 and t 2 415 , as follows : 4 . if the number of pages l 1 + l 2 in lists l 1 and l 2 is less than c , then the list portions b 1 410 and b 2 420 are empty , as expressed by the following expression : if | l 1 205 |∪| l 2 210 |& lt ; c , then both b 1 410 and b 2 420 are empty . 5 . if the number of pages l 1 + l 2 in lists l 1 and l 2 is greater than , or equal to c , then the list portions t 1 405 and t 2 415 together contain exactly c pages , as expressed by the following then t 1 405 and t 2 415 contain exactly c pages . 6 . either list portion t 1 405 is empty or list portion b 1 410 is empty or the lru page in list portion t 1 405 is more recent than the mru page in list portion b 1 410 . similarly , either list portion t 2 415 is empty or list portion b 2 420 is empty or the lru page in list portion t 2 415 is more recent than the mru page in list portion b 2 420 . in plain words , every page in t 1 is more recent than any page in b 1 and every page in t 2 is more recent than any page in b 2 . 7 . for all traces and at each time , pages in both list portions t 1 405 and t 2 415 are exactly the same pages that are maintained in cache 15 . the foregoing conditions imply that if a page in list portion l 1 205 is kept , then all pages in list portion l 1 205 that are more recent than this page must also be kept in the cache 15 . similarly , if a page in list portion l 2 210 is kept , then all pages in list portion l 2 210 that are more recent than this page must also be kept in the cache 15 . consequently , the cache replacement policy that satisfies the above seven conditions “ skims the top ( or most recent ) few pages ” in list portion l 1 205 and list portion l 2 210 . if a cache 15 managed by the cache replacement policy of system 10 is full , that is if : | t 1 |∪| t 2 |= c , then it follows from the foregoing conditions that , for any trace , on a cache 15 miss only two actions are available to the cache replacement policy : 1 . either replace the lru page in list portion t 1 405 , or 2 . replace the lru page in list portion t 2 415 . the pages in | t 1 |∪| t 2 | are maintained in the cache 15 and a directory ; and are represented by the window 425 . the pages in list portions b 1 410 and b 2 420 are maintained in the directory only and not in the cache . with reference to fig3 the “ c ” most recent pages will always be contained in the cache replacement policy dbl ( 2c ), which , in turn , deletes either the lru item in list l 1 205 ( block 340 ) or the lru item in list l 2 210 ( block 365 ). in the first case , list l 1 205 must contain exactly c items ( block 335 ), while in the latter case , list l 2 210 must contain at least c items ( bock 350 ). hence , the cache replacement policy dbl ( 2c ) does not delete any of the most recently seen c pages , and always contains all pages contained in a lru cache 15 with c items . consequently , there exists a dynamic partition of lists l 1 205 and l 2 210 into list portions t 1 405 , b 1 410 , t 2 415 , and b 2 420 , such that the foregoing conditions are met . the choice of 2c as the size of the cache 15 directory for the cache replacement policy dbl ( 2c ) will now be explained . if the cache replacement policy dbl ( 2c ′) is considered for some positive integer c ′& lt ; c , then the most recent c pages need not always be in the cache replacement policy dbl ( 2c ′). for example , consider the trace for this trace , the hit ratio of lru ( c ) approaches 1 as the size of the trace increases , but the hit ratio of the cache replacement policy dbl ( 2c ′), for any c ′& lt ; c , is zero . the design of the cache replacement policy dbl ( 2c ) can be expanded to a replacement policy frc p ( c ) for fixed replacement cache . this policy frc p ( c ) has a tunable or self - adjusting parameter p , where 0 & lt ; p ≦ c , and satisfies the foregoing seven conditions . in addition , the policy frc p ( c ) satisfies a crucial new condition , namely to keep exactly p pages in the list portion t 1 405 and exactly ( c − p ) pages in the list portion t 2 415 . in other terms , the policy frc p ( c ) attempts to keep exactly the mru p top pages from the list portion l 1 205 and the mru ( c − p ) top pages from the list portion l 2 210 in the cache 15 , wherein p is the target size for the list . 1 . if | t 1 405 |& gt ; p , replace the lru page in list portion t 1 405 . 2 . if | t 1 405 |& lt ; p , replace the lru page in list portion t 2 415 . 3 . if | t 1 405 |= p and the missed page is in list portion b 1 410 , replace the lru page in list portion t 2 415 . similarly , if list portion | t 2 405 |= p and the missed page is in list portion b 2 420 , replace the lru page in list portion t 1 405 . replacement decision 3 above can be optional or it can be varied if desired . system 10 is an adaptive replacement policy based on the design of the replacement policy frc p ( c ). at any time , the behavior of system 10 is described once a certain adaptation parameter pε [ 0 , c ] is known . for a given value of the parameter p , system 10 behaves exactly as the replacement policy frc p ( c ). however , unlike the replacement policy frc p ( c ), system 10 does not use a single fixed value for the parameter p over the entire workload . system 10 continuously adapts and tunes p in response to the observed workload . system 10 dynamically detects , in response to an observed workload , which item to replace at any given time . specifically , on a cache miss , system 10 adaptively decides whether to replace the lru page in list portion t 1 405 or to replace the lru page in list portion t 2 415 , depending on the value of the adaptation parameter p at that time . the adaptation parameter p is the target size for the list portion t 1 405 . a preferred embodiment for dynamically tuning the parameter p is now described . method 500 of system 10 is described by the logic flowchart of fig5 ( fig5 a , 5b , 5 c , 5 d ). at block 502 , a page x is requested from cache 15 . system 10 determines at decision block 504 if page x is in ( t 1 405 ∪ t 2 415 ). if so , then page x is already in cache 15 , a hit has occurred , and at block 506 system 10 moves page x to the top of list portion t 2 415 , the mru position in the frequency list . if however , the result at block 504 is false , system 10 ascertains whether page x is in list portion b 1 410 at block 508 . if so , a miss has occurred in cache 15 and a hit has occurred in the recency directory of system 10 . in response , system 10 updates the value of the adaptation parameter , p , at block 510 , as follows : where | b 2 is the number of pages in the list portion b 2 420 directory and | b 1 | is the number of pages in the list portion b 1 410 directory . system 10 then proceeds to block 512 and moves page x to the top of list portion t 2 415 and places it in cache 15 . page x is now at the mru position in list portion t 2 415 , the list that maintains pages based on frequency . at decision block 514 , system 10 evaluates | t 1 405 |& gt ; p . if the evaluation is true , system 10 moves the lru page of list portion t 1 405 to the top of list portion b 1 410 and removes that lru page from cache 15 at block 516 . the lru page in the recency portion of cache 15 has moved to the mru position in the recency directory . otherwise , if the evaluation at step 514 is false , system 10 moves the lru page of list portion t 2 415 to the top of list portion b 2 420 and removes that lru page from cache 15 at block 518 . in this case , the lru page of the frequency portion of cache 15 has moved to the mru position in the frequency directory . system 10 makes these choices to balance the sizes of list portion l 1 205 and list portion l 2 210 while adapting to meet workload conditions . returning to decision block 508 , if page x is not in b 1 , system 10 continues to decision block 520 ( shown in fig5 b ) to evaluate if page x is in b 2 . if this evaluation is true , a hit has occurred in the frequency directory of system 10 . system 10 proceeds to block 522 and updates the value of the adaptation parameter , p , as follows : where | b 2 | is the number of pages in the list portion b 2 420 directory and | b 1 | is the number of pages in the list portion b 1 410 directory . system 10 then , at block 524 , moves page x to the top of list portion t 2 415 and places it in cache 15 . page x is now at the mru position in list portion t 2 415 , the list that maintains pages based on frequency . system 10 must now decide which page to remove from cache 15 . at decision block 526 , system 10 evaluates | t 1 405 |≧ max { p , 1 }. if the result is true , system 10 moves the lru page of list portion t 1 405 to the top of list portion b 1 410 and removes that lru page from cache 15 at block 528 . otherwise , system 10 moves the lru page of list portion t 2 415 to the top of list portion b 2 420 and removes that lru page from cache 15 at block 530 . if at decision block 520 x is not in b 2 420 , the requested page is not in cache 15 or the directory . more specifically , the requested page is a system miss . system 10 then must determine which page to remove from cache 15 to make room for the requested page . proceeding to fig5 c , system 10 evaluates at decision block 532 | l 1 |= c . if the result is true , system 10 then evaluates at decision block 534 | t 1 |& lt ; c . if the result of the evaluation at block 534 is false , then system 10 deletes the lru page of list portion t 1 405 and removes it from cache 15 , block 536 . system 10 then puts the requested page x at the top of list portion t 1 405 and places it in cache 15 at block 538 . returning to decision block 534 , if the result is true , system 10 proceeds to block 540 and deletes the lru page of list portion b 1 410 . at decision block 542 , system 10 evaluates | t 1 |≧ max { p , 1 }. if the result is false , system 10 moves the lru page of list portion t 2 415 to the top of list portion b 2 420 and removes that lru page from cache 15 at block 544 . system 10 then puts the requested page x at the top of list portion t 1 405 and places it in cache 15 at block 538 . if the result at decision block 542 is true , system 10 moves the lru page of list portion t 1 405 to the top of list portion b 1 410 and removes that lru page from cache 15 at block 546 . system 10 then puts the requested page x at the top of list portion t 1 405 and places it in cache 15 at block 538 . returning now to decision block 532 , if the result is false , system 10 proceeds to decision block 548 and evaluates the following condition : | l 1 205 |& lt ; c and | l 1 205 |+| l 2 210 |≧ c . if the result is false , system 10 puts the requested page x at the top of list portion t 1 405 and places it in cache 15 at block 538 . if , however , the result is true , system 10 proceeds to decision block 550 ( fig5 d ) and evaluates | l 1 |+| l 2 |= 2c . if the result is true , system 10 deletes the lru page of list portion b 2 420 at block 552 . after this the system proceeds to decision block 556 . if the result at decision block 550 is false , system 10 evaluates | t 1 |≧ max { p , 1 } at decision block 556 . if the result is true , system 10 moves the lru page of list portion t 1 405 to the top of list portion b 1 410 , and removes that lru page from cache 15 at block 558 . system 10 then places the requested page x at the top of list portion t 1 405 and places it in cache 15 at block 554 . if the result at decision block 556 is false , system 10 moves the lru page in list portion t 2 415 to the top of list portion b 2 420 and removes that lru page from cache 15 at block 560 . system 10 then places the requested page x at the top of list portion t 1 405 and places it in cache 15 at block 554 . system 10 continually revises the parameter p in response to a page request miss or in response to the location of a hit for page x within list portion t 1 405 , list portion t 2 415 , list portion b 2 410 , or list portion b 2 420 . the response of system 10 to a hit in list portion b 2 410 is to increase the size of t 1 405 . similarly , if there is a hit in list portion b 2 420 , then system 10 increases the size of list portion t 2 415 . consequently , for a hit on list portion b 1 410 system 10 increases p , the target size of list portion t 1 405 ; a hit on list portion b 2 420 decreases p . when system 10 increases p , the size of list portion t 1 405 , the size of list portion t 2 415 ( c − p ) implicitly decreases . the precise magnitude of the revision in p is important . the precise magnitude of revision depends upon the sizes of the list portions b 1 410 and b 2 420 . on a hit in list portion b 1 410 , system 10 increments p by : subject to the cap of c , where | b 2 | is the number of pages in the list portion b 2 420 directory and | b 1 | is the number of pages in the list portion b 1 410 directory ; the minimum revision is by 1 unit . similarly , on a hit in list portion b 2 420 , system 10 decrements p by : subject to the floor of zero , where | b 2 | is the number of pages in the list portion b 2 420 directory and | b 1 | is the number of pages in the list portion b 1 410 directory ; the minimum revision is by 1 unit . if there is a hit in list portion b 1 410 , and list portion b 1 410 is very large compared to list portion b 2 420 , then system 10 increases p very little . however , if list portion b , 410 is small compared to list portion b 2 420 , then system 10 increases p by the ratio | b 2 |/| b 1 |. similarly , if there is a hit in list portion b 2 420 , and list portion b 2 420 is very large compared to list portion b 1 410 , then system 10 increases p very little . however , if list portion b 2 420 is small compared to list portion b 1 410 , then system 10 increases p by the ratio | b 1 |/| b 2 |. in effect , system 10 invests cache 15 resources in the list portion that is receiving the most hits . turning now to fig6 the compound effect of a number of such small increments and decrements to p , induces a “ random walk ” on the parameter p . in effect , the window 425 slides up and down as the sizes of list portions t 1 405 and t 2 415 change in response to the workload . the window 425 is the number of pages in actual cache 15 memory . in illustration a of fig6 the list portions t 1 405 and t 2 415 together contain c pages and list portions b 1 410 and b 2 420 together contain c pages . in illustration b , a hit for page x is received in list portion b 1 410 . system 10 responds by increasing p , which increases the size of list portion t 1 405 while decreasing the size of list portion t 2 415 . window 425 effectively slides down . the distance window 425 moves in fig6 is illustrative of the overall movement and is not based on actual values . in the next illustration c of fig6 one or more hits are received in list portion b 2 420 . system 10 responds by decreasing p , which decreases the size of list portion t 1 405 while increasing the size of t 2 415 . window 425 effectively slides up . continuing with illustration d , another hit is received in list portion b 2 420 , so system 10 responds again by decreasing p and window 425 slides up again . if for example , a fourth hit is received in list portion b 1 410 , system 10 increases p , and window 425 slides down again as shown in illustration c . system 10 responds to the cache 15 workload , adjusting the sizes of list portions t 1 405 and t 2 415 to provide the maximum response to that workload . one feature of the present system 10 is its resistance to scans , long streams of requests for pages not in cache 15 . a page which is new to system 10 , that is , not in l 1 ∪ l 2 , is placed in the mru position of list l 1 205 ( block 538 and 554 of fig5 ). from that position , the new page gradually makes its way to the lru position in list l 1 205 . the new page does not affect list l 2 210 before it is evicted , unless it is requested again . consequently , a long stream of one - time - only reads will pass through list l 1 205 without flushing out potentially important pages in list l 2 210 . in this case , system 10 is scan resistant in that it will only flush out pages in list portion t 1 405 but not in list portion t 2 415 . furthermore , when a scan begins , fewer hits will occur in list portion b 1 410 than in list portion b 2 420 . consequently , system 10 will continually decrease p , increasing list portion t 2 415 at the expense of list portion t 1 405 . this will cause the one - time - only reads to pass through system 10 even faster , accentuating the scan resistance of system 10 . system 10 was tested using the traces of table 1 . otlp is a standard test trace containing references to a codasyl database . traces p 1 through p 14 were collected from workstations to capture disk operations through the use of device filters . page size used for these traces was 512 bytes . the trace concat ( p 1 - p 14 ) was obtained by concatenating the traces p 1 through p 14 . similarly , the trace merge ( p 1 - p 14 ) was obtained by merging the traces p 1 through p 14 using time stamps on each of the requests . concat ( p 1 - p 14 ) and merge ( p 1 - p 14 ) simulated a workload seen by a small storage controller . the trace ds1 was taken off a small database server , and further a trace was captured using an spc1 - like synthetic benchmark . this benchmark contains long sequential scans in addition to random accesses . the page size for the spc1 - like trace was 4 kbytes . table 2 compares the hit ratios of lru , 2q , lru - 2 , lrfu , and lirs policies with those of system 10 for trace p 8 . table 3 compares the hit ratios of lru , 2q , lru - 2 , lrfu , and lirs policies with those of system 10 for trace p 12 . all hit ratios are recorded from the start when the cache is empty and hit ratios are reported in percentages . tunable parameters for lru - 2 , 2q , and lrfu policies were selected offline by trying different parameters and selecting the parameters that provided the best results for different cache sizes . system 10 outperforms the lru policy and performs close to the 2q , lru - 2 , lrfu , and lirs policies even when these policies use the best offline parameters . the same general results continue to hold for all the traces examined . the lru policy is the most widely used cache replacement policy . table 4 and fig7 fig8 and fig9 all illustrate that system 10 outperforms the lru policy . in addition , the performance of system 10 compared to the frc policy shows that system 10 tunes itself as well as frc p with the best offline selection of the parameter p . this result holds for all or most traces , indicating that system 10 is empirically universal . as seen in table 4 , the computational overhead required by system 10 ( when measured in seconds ) is comparable to the lru and 2q policies , while lower than that of the lru - 2 policy and dramatically lower than that of the lrfu policy . table 6 shows an overall comparison of system 10 with all the other replacement techniques discussed thus far . one advantage of system 10 is that it matches or exceeds performance of all other approaches while self - tuning . in addition , system 10 is scan resistant and requires low computational overhead . the notation “ constant ( e )” in table 6 indicates that the corresponding algorithm is constant - time in expected sense only , whereas notation “ constant ” indicates that the corresponding algorithm is constant - time in the worst case . the latter is more desirable than the former . it is to be understood that the specific embodiments of the present invention that have been described are merely illustrative of certain applications of the principle of the present invention . numerous modifications may be made to the system and method for implementation of adaptive replacement cache policy invention described herein without departing from the spirit and scope of the present invention .