Method and system for a cache replacement technique with adaptive skipping

A system for adaptively managing pages in a cache memory included within said system having a variable workload comprising:

• a circular buffer comprising said a cache memory;
• a pointer that rotates around said circular buffer;
• a skipping parameter value;
• a bit marker operable for marking each page in said circular buffer with a bit value, wherein a first bit value indicates that said page was not accessed by said system since a last time that said pointer traversed over said page, and a second bit value indicates that said page has been accessed since said last time and said pointer traversed over said page;
• a first controller operable for dynamically controlling a distribution of a number of pages in said cache memory that are marked with said first bit value in response to a variable workload in order to increase a hit ratio of said cache memory;
• and
• a second controller operable for choosing pages to replace by moving said pointer around said circular buffer until a page that is marked with said first bit value is found, wherein while said pointer is moving around said circular buffer, if a page marked with said second bit value is found then remarking said page with bit 0 if since either a movement started or since a last page was marked, a determination is made that said skipping parameter value has been reached.

A system for adaptively managing pages in a cache memory included within said system having a variable workload comprising:

• means for arranging a cache memory included within a system into a circular buffer;
• means for maintaining a pointer that rotates around said circular buffer;
• means for maintaining a skipping parameter value;
• means for maintaining a bit for each page in said circular buffer, wherein a first bit value indicates that said page was not accessed by said system since a last time that said pointer traversed over said page, and a second bit value indicates that said page has been accessed since said last time said pointer traversed over said page;
• means for dynamically controlling a distribution of a number of pages in said cache memory that are marked with bit 0 in response to a variable workload in order to increase a hit ratio of said cache memory;
• and
• means for choosing pages to replace by moving said pointer around said circular buffer until a page that is marked with said first bit value is found, wherein while said pointer is moving around said circular buffer, if a page marked with said second bit value is found then remarking said page with said first bit value if since either a movement started or since a last page was marked, a determination is made that said skipping parameter value has been reached.

A program storage device readable by computer, tangibly embodying a program of instructions executable by said computer to perform a method of adaptively managing pages in a cache memory included within a system having a variable workload, said method comprising:

• arranging a cache memory included within a system into a circular buffer;
• maintaining a pointer that rotates around said circular buffer;
• maintaining a skipping parameter value;
• maintaining a bit for each page in said circular buffer, wherein a first bit value indicates that said page was not accessed by said system since a last time that said pointer traversed over said page, and a second bit value indicates that said page has been accessed since said last time said pointer traversed over said page;
• dynamically controlling a distribution of a number of pages in said cache memory that are marked with said first bit value in response to a variable workload in order to increase a hit ratio of said cache memory;
• and
• choosing pages to replace by moving said pointer around said circular buffer until a page that is marked with said first bit value is found, wherein while said pointer is moving around said circular buffer, if a page marked with said second bit value is found then remarking said page with said first bit value if since either a movement started or since a last page was marked, a determination is made that said skipping value has been reached.

A method of adaptively managing pages in a cache memory included within a circular buffer in a system having a variable workload, said method comprising:

• maintaining a pointer that rotates around said circular buffer;
• maintaining a skipping parameter value;
• assigning a bit value for the pages in the circular buffer, wherein a first bit value indicates that said pages have not been accessed by the system since a previous predetermined time, and wherein a second bit value indicates that said pages have been accessed by the system since a previous predetermined time;
• converting said first bit value to said second bit value for selected pages;
• controlling a distribution of a number of pages in the cache memory that are marked with the first bit value in response to a variable workload in order to increase a hit ratio of the cache memory;
• and
• choosing pages to replace by moving said pointer around said circular buffer until a page that is marked with said first bit value is found, wherein while said pointer is moving around said circular buffer, if a page marked with said second bit value is found then remarking said page with said first bit value if since either a movement started or since a last page was marked, a determination is made that said skipping parameter value has been reached,
• wherein the previous predetermined time includes the previous time said page was assigned said bit value.

A system for adaptively managing pages in a cache memory included within a circular buffer in a system having a variable workload comprising:

• means for maintaining a pointer that rotates around said circular buffer;
• means for maintaining a skipping parameter value;
• means for assigning a bit value for the pages in the circular buffer, wherein a first bit value indicates that said pages have not been accessed by the system since a previous predetermined time, and wherein a second bit value indicates that said pages have been accessed by the system since a previous predetermined time;
• means for converting said first bit value to said second bit value for selected pages;
• means for controlling a distribution of a number of pages in the cache memory that are marked with the first bit value in response to a variable workload in order to increase a hit ratio of the cache memory;
• and
• means for choosing pages to replace by moving said pointer around said circular buffer until a page that is marked with said first bit value is found, wherein while said pointer is moving around said circular buffer, if a page marked with said second bit value is found then remarking said page with said first bit value if since either a movement started or since a last page was marked, a determination is made that said skipping parameter value has been reached,
• wherein the previous predetermined time includes the previous time said page was assigned said bit value.