Abstract:
Exemplary embodiments of the present invention disclose a method and system for selecting an eviction location of an item to evict and an insertion location for a new item in a circular buffer. In a step, an exemplary embodiment specifies an insertion location with an insertion pointer. In another step, an exemplary embodiment increments an access count of a first item. In another step, an exemplary embodiment moves an eviction pointer clockwise when specifying an insertion location for the new item and the circular buffer is in eviction mode. In another step, an exemplary embodiment decrements an access count of a second item. In another step, an exemplary embodiment moves the insertion pointer to maintain a constant clockwise distance to the eviction location. In another step, an exemplary embodiment evicts the second item with an access count of zero and inserts the new item counterclockwise to the insertion location.

Description:
FIELD OF THE INVENTION 
     The present invention relates generally to cache replacement algorithms and more specifically to algorithms for selecting an item to delete and a location for a new item in a circular buffer. 
     BACKGROUND 
     Buffers and caches are often used in computing systems to temporarily hold items that are frequently accessed or whose access time may otherwise inhibit performance. Since buffers and caches have limited size, techniques used to efficiently utilize their limited space strongly influence their performance. One type of buffer is a circular buffer implemented in software. A circular buffer is a list of items linked in a circular fashion. Each item in the list is linked to a previous item and a next item, where the first item in the list is the next item with respect to the last item on the list, i.e., the items are linked in a circle. Two algorithms are necessary to operate such a buffer: first, an algorithm to select an item to delete when a new item is to be inserted into a full buffer; second, an algorithm to select a location for the new item. A location from which an item is deleted to make space for a new item and a location to which the new item is inserted may not be the same location. This happens more often in software implemented buffers than those implemented in hardware. The logic that selects these locations is embodied in a replacement algorithm which has a profound effect on the performance of a buffer under various workloads. The performance of a buffer is usually measured by its hit rate, the fraction of accesses to a buffer that find an accessed item in the buffer. The performance of a given replacement algorithm will vary under different circumstances and depends strongly on the access pattern of a program using a buffer. 
     A common replacement algorithm used with a buffer or a cache is least recently used or LRU. When a new item must be added to a full buffer, the LRU algorithm evicts an item from the buffer or a section of the buffer that has not been accessed for the longest period of time compared to that of other items under consideration and the new item replaces the evicted item. Unfortunately, in some buffer configurations and for large buffers, the logic necessary to keep track of a LRU item and the next LRU item, etc. can be significant. 
     SUMMARY 
     Exemplary embodiments of the present invention disclose a method and system for selecting an item to evict and a location for a new item in a circular buffer with a maximum size. In a step, an exemplary embodiment specifies an insertion location with an insertion pointer. In another step, an exemplary embodiment increments an access count of a first item in the circular buffer by one if the first item is accessed and the access count of the first item is less than an access count limit. In another step, an exemplary embodiment enters an eviction mode when the circular buffer contains a plurality of items less than or equal to a maximum size. In another step, an exemplary embodiment specifies a first eviction location with an eviction pointer after the circular buffer enters the eviction mode. In another step, an exemplary embodiment moves the eviction pointer clockwise to a second eviction location when specifying the first insertion location for the new item and the circular buffer is in the eviction mode. In another step, an exemplary embodiment decrements an access count by one of a second item in the second eviction location with an access count greater than zero when the eviction pointer moves to the second eviction location. In another step, an exemplary embodiment moves the insertion pointer to a second insertion location to maintain a constant clockwise distance to the second eviction location when the eviction pointer moves clockwise by one location. In another step, an exemplary embodiment evicts the second item at the second eviction location with an access count of zero when the eviction pointer moves to the second eviction location. In another step, an exemplary embodiment responsive to evicting the second item, inserts the new item in a counterclockwise direction adjacent to the second insertion location specified by the insertion pointer. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         FIG. 1  is a block diagram of a computer executing a data intensive program that utilizes a two handed circular buffer system, in accordance with an embodiment of the present invention. 
         FIG. 2  depicts an example of a two handed circular buffer, in accordance with an embodiment of the present invention. 
         FIG. 3  depicts a flow chart that implements a replacement algorithm for a circular buffer depicted in  FIG. 2 , in accordance with an embodiment of the present invention. 
         FIG. 4  depicts pseudo code that implements a replacement algorithm depicted in  FIG. 3 , in accordance with an embodiment of the present invention. 
         FIG. 5  depicts a block diagram of components of a computing device, in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer-readable medium(s) having computer readable program code/instructions embodied thereon. 
     Any combination of computer-readable media may be utilized. Computer-readable media may be a computer-readable signal medium or a computer-readable storage medium. A computer-readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of a computer-readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer-readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. 
     A computer-readable signal medium may include a propagated data signal with computer-readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer-readable signal medium may be any computer-readable medium that is not a computer-readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device. 
     Program code embodied on a computer-readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing. 
     Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java®, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on a user&#39;s computer, partly on the user&#39;s computer, as a stand-alone software package, partly on the user&#39;s computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user&#39;s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). 
     Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     These computer program instructions may also be stored in a computer-readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer-readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks. 
     The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer-implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     The present invention will now be described in detail with reference to the Figures.  FIG. 1  is a functional block diagram illustrating the operation of a computer executing a data intensive program utilizing a two handed circular buffer system, in accordance with an embodiment of the present invention. 
     In various embodiments of the present invention, computer  101  is computing device that can be a standalone device, a server, a laptop computer, a tablet computer, a netbook computer, a personal computer (PC), or a desktop computer. In another embodiment, computer  101  represents a computing system utilizing clustered computers and components to act as a single pool of seamless resources. In general, computer  101  can be any computing device or a combination of devices capable of running data intensive program  104 . A data intensive program is a program that accesses a large amount of data during an execution of the program. Computer  101  may include internal and external hardware components, as depicted and described in further detail with respect to  FIG. 5 . 
     In an exemplary embodiment shown in  FIG. 1 , two handed circular buffer system  102  in main memory  103  of computer  101  organizes and buffers data accessed by data intensive program  104 . Two handed circular buffer system  102  is termed “two handed” because two pointers (two hands) are used to specify a location for an insertion and a deletion of an item during an operation of two handed circular buffer system  102 . Processor  105  and cache  106  fetch data and instructions from main memory  103  to execute data intensive program  104 . Data and instructions not currently in cache  106  or in main memory  103  are fetched from disk  107 . Two handed circular buffer system  102  includes circular buffer  109  and replacement algorithm  108 . If an item, which includes one or more datums, is needed by data intensive program  104  and the item is not in two handed circular buffer system  102 , replacement algorithm  108  inserts the item into circular buffer  109 . If circular buffer  109  is full, and a new item is to be inserted, replacement algorithm  108  selects an item to delete, deletes the item selected, selects a location to insert the new item and inserts the new item. If circular buffer  109  is not full, and a new item is to be inserted, the new item is inserted and no item is deleted. 
       FIG. 2  shows circular buffer  200  which is an example of circular buffer  109  shown in more detail. Circular buffer  200  contains six items, items  201 ,  202 ,  203 ,  204 ,  205 , and  211 . An item in circular buffer  200  contains a counter that counts a number of accesses to the item. A magnitude of a count in a counter is called an access count. Replacement algorithm  108  specifies a value of an access count limit for data intensive program  104 . A value for the access count limit for data intensive program  104  that results in a best hit ratio for circular buffer  200  is determined through experimentation. If an item in circular buffer  200  is accessed, an access count for the item is incremented by one if the access count is less than the value of the access count limit. For example, if the access count limit is 10 and the count for the item is 7, the access count is incremented by 1 and the access count becomes 8. If the access count limit is 10 and the count for the item is 10 the count for the item is not incremented and the count for the item remains at 10. 
     Each item in circular buffer  200  contains two pointers that emanate from the item. Exemplary embodiments include a next pointer that emanates from each item and points to the next item in a clockwise direction with respect to circular buffer  200 . Exemplary embodiments include a previous pointer that emanates from each item and points to the previous item in a counterclockwise direction with respect to circular buffer  200 . Next pointer  206  emanates from item  201  and points to an adjacent next item, item  202 , in a clockwise direction with respect to circular buffer  109 . Previous pointer  207  emanates from item  201  and points to an adjacent previous item, item  211 , in a counterclockwise direction with respect to circular buffer  200 . 
     Replacement algorithm  108  controls two pointers, eviction point  208  and insertion pointer  209 , whose tails are located in  FIG. 2  at an approximate center of a ring composed of all the items in circular buffer  200 , and whose heads can move clockwise around the perimeter of circular buffer  200  as hands on a clock move. One pointer, insertion pointer  209 , controls an insertion point used to locate a new item that is to be inserted into circular buffer  200 . Another pointer, eviction pointer  208 , is used to search for an item to be evicted when circular buffer  200  is full and a new item is to be inserted into circular buffer  200 . 
     When data intensive program  104  begins execution, circular buffer  200  is initially empty. As data intensive program  104  executes, items are inserted into circular buffer  200  one at a time until the number of items in circular buffer  200  reaches a maximum size that is specified by replacement algorithm  108 . Until circular buffer  200  is full, insertion pointer  209  exists and eviction pointer  208  does not exist. When circular buffer  200  becomes full, eviction pointer  208  is created by replacement algorithm  108  and initially points at an item in circular buffer  200  that is a constant clockwise distance from insertion pointer  209 . The constant clockwise distance is specified by replacement algorithm  108 . For example, in  FIG. 2 , replacement algorithm sets the constant clockwise distance to 2 items in circular buffer  200 . 
     If a new item is to be inserted into circular buffer  200  and circular buffer  200  is not full, the new item is inserted counterclockwise and adjacent to an item pointed to by insertion pointer  209 . For example, in  FIG. 2  the insertion pointer points to item  211 , and a new item is inserted between item  205  and item  211 . 
     A flow chart in  FIG. 3  depicts an operation of replacement algorithm  108 , if a new item is to be inserted into circular buffer  200  and circular buffer  200  is full. In step  301  an access count of an item pointed to by eviction pointer  208  is queried. If the access count is zero the item is evicted in step  302  and the new item is inserted counterclockwise and adjacent to the item pointed to by insertion pointer  209  in step  303 . If the insertion count is not zero (step  301 , no branch), the insertion count is decremented by one in step  304  and eviction pointer  208  moves one item clockwise in step  305  and insertion pointer  209  moves one item clockwise in step  306 . Steps  301 ,  304 ,  305  and  306  are repeated until the eviction pointer points to an item with an access count of zero and then step  302  and step  303  are performed. 
       FIG. 4  shows a pseudo code for an exemplary embodiment of replacement algorithm  108  when an item called item X is accessed (referenced). Code  401  executes if item X is in circular buffer  200  and replacement algorithm  108  terminates execution when code  401  completes. Code  402  executes if item X is not in circular buffer  200  and circular buffer  200  is not full. Code  402  inserts item X counterclockwise and adjacent to the item pointed to by insertion pointer  209  and then terminates execution of replacement algorithm  108 . Code  403  executes if item X is not in circular buffer  200  and circular buffer  200  is full. Code  404 , a code within code  403 , is a loop that moves evection pointer  208  clockwise in circular buffer  200  in search of an item with an access count of zero and concurrently moves insertion pointer  209  to maintain a constant clockwise distance from insertion pointer  209  to eviction pointer  208 . When code  404  finds an item with an access count of zero, code  405  executes, which evicts the item and inserts item X counterclockwise and adjacent to the item pointed to by insertion pointer  209 . Replacement algorithm  108  terminates execution when code  405  completes execution. 
       FIG. 5  depicts a block diagram of components of computer system  101  in accordance with an illustrative embodiment of the present invention. It should be appreciated that  FIG. 5  provides only an illustration of one implementation and does not imply any limitations with regard to the environments in which different embodiments may be implemented. Many modifications to the depicted environment may be made. 
     Computer system  101  includes communications fabric  502 , which provides communications between computer processor(s)  504 , memory  506 , persistent storage  508 , communications unit  510 , and input/output (I/O) interface(s)  512 . Communications fabric  502  can be implemented with any architecture designed for passing data and/or control information between processors (such as microprocessors, communications and network processors, etc.), system memory, peripheral devices, and any other hardware components within a system. For example, communications fabric  502  can be implemented with one or more buses. 
     Memory  506  and persistent storage  508  are computer-readable storage media. In this embodiment, memory  506  includes random access memory (RAM)  514  and cache memory  516 . In general, memory  506  can include any suitable volatile or non-volatile computer-readable storage media. 
     Data intensive program  104  and two handed circular buffer system  102  are stored in persistent storage  508  for execution by one or more of the respective computer processors  504  via one or more memories of memory  506 . In this embodiment, persistent storage  508  includes a magnetic hard disk drive. Alternatively, or in addition to a magnetic hard disk drive, persistent storage  508  can include a solid state hard drive, a semiconductor storage device, read-only memory (ROM), erasable programmable read-only memory (EPROM), flash memory, or any other computer-readable storage media that is capable of storing program instructions or digital information. 
     The media used by persistent storage  508  may also be removable. For example, a removable hard drive may be used for persistent storage  508 . Other examples include optical and magnetic disks, thumb drives, and smart cards that are inserted into a drive for transfer onto another computer-readable storage medium that is also part of persistent storage  508 . 
     Communications unit  510 , in these examples, provides for communications with other data processing systems or devices, including resources of computer system  101 . In these examples, communications unit  510  includes one or more network interface cards. Communications unit  510  may provide communications through the use of either or both physical and wireless communications links. Data intensive program  104  and two handed circular buffer system  102  may be downloaded to persistent storage  508  through communications unit  510 . 
     I/O interface(s)  512  allows for input and output of data with other devices that may be connected to computer system  101 . For example, I/O interface  512  may provide a connection to external devices  518  such as a keyboard, keypad, a touch screen, and/or some other suitable input device. External devices  518  can also include portable computer-readable storage media such as, for example, thumb drives, portable optical or magnetic disks, and memory cards. Software and data used to practice embodiments of the present invention, e.g., Data intensive program  104  and disk health monitor and two handed circular buffer system  102  can be stored on such portable computer-readable storage media and can be loaded onto persistent storage  508  via I/O interface(s)  512 . I/O interface(s)  512  also connect to a display  520 . 
     Display  520  provides a mechanism to display data to a user and may be, for example, a computer monitor. 
     The programs described herein are identified based upon the application for which they are implemented in a specific embodiment of the invention. However, it should be appreciated that any particular program nomenclature herein is used merely for convenience, and thus the invention should not be limited to use solely in any specific application identified and/or implied by such nomenclature. 
     The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions. 
     The forgoing description are example embodiments only, and those skilled in the art understand that a distance between an eviction pointer and an insertion pointer need not be a constant, that an access count may be incremented or decremented by any amount, that an item may be inserted any distance and in a clockwise or counterclockwise direction from an insertion pointer, and that an eviction pointer and an insertion pointer may move by any amount clockwise or counterclockwise.