Browse Prior Art Database

Cyclic Cache

IP.com Disclosure Number: IPCOM000050742D
Original Publication Date: 1982-Dec-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 3 page(s) / 35K

Publishing Venue

IBM

Related People

Minshull, JF: AUTHOR [+2]

Abstract

A working store or cache for a computer has been proposed in European Patent Application No. 43391 in which variable-length segments of data are loaded contiguously in available free space from the lowest available address of the cache towards the high address end. All segments are linked to each other as double-threaded lists in one or other of a number of chains. Access to a particular wanted segment, whose precise location in the cache is unknown, is achieved by means of a search through the associated chain, starting from a segment header located in a predetermined region of additional storage set aside for this purpose. During operation, new data segments are entered into the cache, and existing segments are modified or deleted, as required, by the application being run on the computer.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Cyclic Cache

A working store or cache for a computer has been proposed in European Patent Application No. 43391 in which variable-length segments of data are loaded contiguously in available free space from the lowest available address of the cache towards the high address end. All segments are linked to each other as double-threaded lists in one or other of a number of chains. Access to a particular wanted segment, whose precise location in the cache is unknown, is achieved by means of a search through the associated chain, starting from a segment header located in a predetermined region of additional storage set aside for this purpose. During operation, new data segments are entered into the cache, and existing segments are modified or deleted, as required, by the application being run on the computer. Should additional space be required for new segments, then this is created by drop-out of segments from the cache on a least-recently used (LRU) basis.

Blocks of free space interspersed with data segments within the cache, generated as a result of modification or deletion of data segments, are themselves linked together in a chain. Procedures run at low priority sort the data segments into LRU order, and rearrange data segments and free space blocks so as to merge free space blocks into the general free space region of the cache and restore the contiguity of the data segments. With this design of cache, more-wanted segments tend to migrate towards the low address end of cache and the less-wanted ones, that is, those high on the LRU list for segment drop-out, towards the high address end where they are conveniently placed for deletion, if required, to provide additional free space for new segments. A new segment written into the cache is, by definition, a most-wanted segment. Since new segments are added to the high address end of existing segments, they immediately become embroiled in a migration towards the low address end of the cache. This complication of having to control and monitor movement of more- wanted segments from high to low address and less-wanted segments from low to high address imposes a performance limitation on the cache.

To overcome this difficulty, a cyclic cache, divided into separate low address and high address regions with a moveable free space region between the two, has been devised. The low address region predominantly contains segments to be sorted in LRU order and thereafter to be moved adjacent the existing free space region w...