Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-11-05
2002-09-24
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S131000, C711S152000
Reexamination Certificate
active
06457102
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This application relates to the field of computer data storage and more particularly to the field of configuring a cache in a computer data storage system having multiple processors accessing the cache.
2. Description of Related Art
Host processor systems may store and retrieve data using a storage device containing a plurality of host interface units, disk drives, and disk interface units. Such storage devices are provided, for example, by EMC Corporation of Hopkington, Mass. and disclosed in U.S. Pat. No. 5,206,939 to Yanai et al., 5,778,394 to Galtzur et al., U.S. Pat. No. 5,845,147 to Vishlizzky et al., and U.S. Pat. No. 5,857,208 to Ofek. The host systems access the mass storage device through a plurality of channels provided therewith. Host systems provide data and access control information through the channels to the storage device and storage device provides data to the host systems also through the channels. The host systems do not address the disk drives of the storage device directly, but rather, access what appears to be the host systems as a plurality of logical disk units. The logical disk units may or may not correspond to the actual disk drives. Allowing multiple host systems to access the single storage device unit allows the host systems to share data stored therein.
Performance of a storage system may be improved by using a cache. In the case of a disk drive system, the cache may be implemented using a block of semiconductor memory that has a relatively lower data access time than the disk drive. Data that is accessed is advantageously moved from the disk drives to the cache so that the second and subsequent accesses to the data may be made to the cache rather than to the disk drives. Data that has not been accessed recently is removed from the cache to make room for new data. Often such cache accesses are transparent to the host system requesting the data.
One technique for implementing a cache is to store the data in blocks and link each of the blocks together in a doubly linked ring called a logical ring unit (LRU). Each block of the LRU represents a block of data from a logical disk unit. The blocks are placed in the doubly linked ring list in the order in which they are retrieved from the disk. A pointer points to the block that was most recently added to the list. Thus, when a new block is to be added to the cache, the structure of the LRU in combination with the head pointer may be used to determine the oldest block in the LRU that is to be removed to make room for the new block.
A drawback with the LRU mechanism discussed above is that only one process may access and manipulate the ring list at a time since the complexity of the doubly linked ring structure makes it difficult to allow more than one process manipulate to the data structure at any time. One way to enforce this is to use a software lock, which is a conventional semaphore-like mechanism that allows a process exclusive access to the LRU. However, when multiple processors need to use the cache, then this exclusive LRU access policy may become a bottleneck.
SUMMARY OF THE INVENTION
According to the present invention, storing data in a cache memory includes providing a first mechanism for allowing exclusive access to a first portion of the cache memory and providing a second mechanism for allowing exclusive access to a second portion of the cache memory, where exclusive access to the first portion is independent of exclusive access to the second portion. Storing data in a cache memory may also include providing at least a third mechanism for allowing exclusive access to at least a third portion of the cache memory where exclusive access to any one of the portions is independent of exclusive access to any other ones of the portions. The first and second mechanisms may be locks. The locks may be software locks or hardware locks. Allowing exclusive access may also include providing a first data structure in the first portion of the cache memory and providing a second data structure in the second portion of the cache memory, where accessing the first portion includes accessing the first data structure and accessing the second portion includes accessing the second data structure. The data structures may doubly linked ring lists of blocks of data and the blocks may correspond to a track on a disk drive. Allowing exclusive access may also include determining a first cache fall through time for the first portion, determining a second cache fall through time for the second portion, and assigning data to one of the first and second portions according to the first and second cache fall through times. Allowing exclusive access may also include determining a difference between the first and second cache fall through times, wherein assigning data to one of the first and second portions is based on the difference. In response to the difference being less than a predetermined amount, data may be assigned randomly to one of the first and second portions.
According further to the present invention, a cache memory includes a first portion having a first mechanism for allowing exclusive access thereto and a second portion having a second mechanism for allowing exclusive access thereto, where exclusive access to the first portion is independent of exclusive access to the second portion. The first and second mechanisms may be software locks. The first portion may include a first data structure and the second portion may include a second data structure and accessing the first portion may include accessing the first data structure and accessing the second portion may include accessing the second data structure. The data structures may be doubly linked ring lists of blocks of data. Each block of data may correspond to a track on a disk drive. A first cache fall through time for the first portion may be determined, a second cache fail through time for the second portion may be determined, and data may be assigned to one of the first and second portions according to the first and second cache fall through times. A difference between the first and second cache fall through times may be determined and assigning data to one of the first and second portions may be based on the difference. In response to the difference being less than a predetermined amount, data may be assigned randomly to one of the first and second portions.
According further to the present invention, a storage device includes a plurality of disk drives, a plurality of disk interface units, each being coupled to one of the disk drives, a bus that interconnects the disk interface units, and a cache memory, coupled to the bus, the cache memory having a plurality of portions, each being independently controllable by one of the disk interface units. Each of the portions of the cache memory may have a mechanism for controlling exclusive access thereto. Each of the portions may include a data structure and accessing one of the portions may include accessing a corresponding one of the data structures. The data structures may be doubly linked ring lists.
According further to the present invention, a cache memory, includes a plurality of portions and a plurality of locks, each of the locks corresponding to exclusive access to a particular one of the portions, where exclusive access to one of the portions is independent of exclusive access to an other one of the portions. Each of the portions may include a data structure and accessing one of the portions may include accessing the data structure. The data structure may be a doubly linked ring lists of blocks of data. Each block of data may correspond to a track on a disk drive.
REFERENCES:
patent: 4371929 (1983-02-01), Brann et al.
patent: 5206939 (1993-04-01), Yanai et al.
patent: 5778394 (1998-07-01), Galtzur et al.
patent: 5822764 (1998-10-01), Hardage, Jr. et al.
patent: 5845147 (1998-12-01), Vishlitzky et al.
patent: 5857208 (1999-01-01), Ofek
patent: 6115790 (2000-09-01), Schimmel
patent: 6173367 (2001-01-01), Aleksic et al.
patent: 0497543 (1992-08-0
Lambright Daniel
Ofek Yuval
Ofer Adi
Vishlitzky Natan
EMC Corporation
Hutchins, Wheeler & Dittmar
Nguyen Hiep T.
LandOfFree
Cache using multiple LRU's does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cache using multiple LRU's, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache using multiple LRU's will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2882724