Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1999-04-08
2004-10-19
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S209000, C711S110000, C710S052000
Reexamination Certificate
active
06807615
ABSTRACT:
I. BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates generally to buffers, and in particular to an apparatus and method for creating and maintaining a cyclic or circular buffer.
B. Description of the Prior Art
A buffer is a memory area used for storing information being transferred between two entities. It is often used to decouple concurrently executing software processes so that a process reading from the buffer and a process writing to the buffer may operate at different speeds or on different block sizes of information stored in the buffer. An input pointer is used to identify a location in the buffer to write information.
A cyclic or circular buffer is a special type of buffer that uses a cyclic addressing scheme. Data is input to the buffer at the buffer location pointed to by the input pointer. The input pointer is incremented each time data is input to the buffer. When the input pointer reaches the end of the buffer, it is wrapped around to the beginning of the buffer. Thus, when wraparound occurs, data at the beginning of the buffer starts being overwritten.
A cyclic buffer typically contains blocks of equal size. The size of the buffer is the number of blocks in the buffer. A cyclic buffer is implemented using an input pointer and a cycle number. The input pointer points to the block in the buffer where new input information will be stored, and the cycle number indicates the number of times the input pointer has wrapped around the buffer. Each cycle is referred to as a generation. Thus, if the input pointer has already cycled through the buffer twice, information being added in the next cycle is considered to be third generation information.
Before adding information to the buffer, it is necessary to allocate an appropriate number of blocks to hold the information being input to the buffer. In some cyclic buffer implementations the allocated blocks must be contiguous in the buffer, and therefore cannot be allocated from the bottom and top of the buffer. It is not possible to allocate an area in a cyclic buffer that wraps around the buffer. Thus, if there are N blocks from the input pointer to the end of the cyclic buffer, then an allocation of more than N blocks must start from block number
0
. This is an inefficient use of buffer space.
A cyclic buffer is useful for storing information that must be retrieved quickly. For example cyclic buffers are used to store USENET news articles. See, Fritchie, Scott L., “The Cyclic News Filesystem: Getting INN to Do More with Less,” Proceedings of the Eleventh System Administration Conference (LISA XI) San Diego, Calif., October 1997, pp. 99-111.
A cyclic buffer is also useful for storing information that expires after a relatively brief period of time. If the size of a cyclic buffer is large, information being overwritten may already be expired.
Indexes are often used to locate information stored in a cyclic buffer. An index table for a cyclic buffer is a collection of one or more index entries. Each index entry (or index) comprises a key value identifying particular information and the location of the information in the buffer. To find certain information in the buffer, the index table is first scanned to find an index entry with a key value associated with the desired information. Once an index entry with a proper key is found, the information location in the entry is used to locate the information in the buffer. The index must be modified each time information is added to or deleted from the buffer. For example, the index entry for the deleted information might be removed, or identified as obsolete.
Since information is added into the cyclic buffer contiguously, old information is never updated. Instead, a new copy of the information is written to the cyclic buffer, and the location information of the index that identifies the information is updated to point to the new location. In addition, if the information is overwritten, the index entry for the overwritten information must either be removed, or identified as obsolete. It is preferable to remove the obsolete index to recover the memory space occupied by the index entry. Unfortunately, locating the indexes of information stored in a cyclic buffer that has been overwritten is quite complicated and is also quite time-consuming. Thus, it is preferable to use a method that can identify an obsolete index when it is referenced.
In order to determine whether a buffer block has been overwritten, the location information of an index entry must also contain the cycle number of the cyclic buffer when the buffer block is allocated. When the index is referenced, the cycle number in the index and the current cycle number of the cyclic buffer are then used to determine if the buffer block has been overwritten.
Thus, conventional cyclic buffers require both a cycle number (or generation number) and a block number of a block to determine if the contents of the block have been overwritten. The requirement of both a cycle number and block number, and the algorithms that must be implemented to use them, make a conventional cyclic buffer very cumbersome. There is, therefore, a need for a cyclic buffer that is simpler, requires less space when implemented, and allows blocks to be wrapped around the buffer.
II. SUMMARY OF THE INVENTION
Systems and methods consistent with the present invention maintain and use a cyclic buffer using logical blocks. Logical blocks and physical blocks have the same size. A buffer manager maps logical buffer blocks to physical buffer blocks for storing information to and retrieving information from the buffer.
New data being stored in the buffer is placed in a sequence of contiguous logical blocks. Such a sequence is called a cell. There is an exceptional case when a cell consists of exactly two sequences of contiguous logical blocks, if the first sequence includes the logical block with the highest possible number, and the second sequence includes the logical block with the lowest possible number.
The logical block number of the first logical block of a cell, and the size of the cell in bytes are stored in the index table with information identifying the new data.
The buffer manager accesses the buffer contents by consulting the index to determine the logical blocks associated with desired information, and maps logical block numbers to physical buffer blocks. The logical block numbers allow the buffer manager to simply determine the newness of a logical buffer block, as well as whether the block is obsolete.
Such systems and methods overcome the problems of conventional cyclic buffers described above. Additional advantages of the invention are apparent from the description which follows, and may be learned by practice of the invention. It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.
REFERENCES:
patent: 4482952 (1984-11-01), Akagi
patent: 5109335 (1992-04-01), Watanabe
patent: 5535412 (1996-07-01), Nadehara
patent: 5574944 (1996-11-01), Stager
patent: 5603008 (1997-02-01), Hilton et al.
patent: 5826041 (1998-10-01), Ogus
patent: 5946717 (1999-08-01), Uchibori
patent: 0864967 (1998-09-01), None
patent: WO 88 09014 (1988-11-01), None
“Direct Memory Access for Multiple Requesting Computer Devices,” IBM Technical Disclosure Bulletin, U.S., IBM Corp., New York, vol. 31, No. 11, Apr. 1, 1989, pp. 324-328.
“Concepts for Buffer Storage”, Computer Group News, vol. 2, No. 8, Mar. 1969, pp. 9-13.
Ahmadian Omid
Chawla Rajeev
Radia Sanjay R.
Tsirigotis Panagiotis
Wong Thomas K.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Gossage Glenn
LandOfFree
Apparatus and method for providing a cyclic buffer using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for providing a cyclic buffer using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for providing a cyclic buffer using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3283481