Patent US5960452A successfully refreshed from Google Patents.
US5960452A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimizing access to multiplexed data streams on a computer system with limited memory
Assignee: Veritas Technologies LLC
•
Filing: 1996-12-23
•
Granted: 1999-09-28
•
Expires: 2016-12-23
Abstract
Abstract A system and method accelerate access time to multiplexed data streams. Data streams are stored in a storage medium (120), and a link allocation table (LAT) (160), which is stored in the storage medium (120), maps blocks of a data stream to sectors of the storage medium (120). The LAT (160) is organized as a set of linked lists, and each data stream is associated with a different linked list in the LAT (160). Each link in a linked list includes the sector location for a different block of the data steam. Traversing the links of the linked list gives the sector location of each subsequent block of data. Each data stream is also associated with a cache memory (140). For each link of a linked list that is traversed, a cache interface (150) writes into an appropriate cache (140) the sector location information stored in the link. When the sector location of a block in a data stream is desired, the cache interface (150) consults the appropriate cache (140) associated with the data stream to determine whether the sector location of the block has been cached. If the information has been cached, the information is retrieved from the cache (140), and the LAT (160) is not used. If the sector location has not been cached, the cache interface (150) determines the last sector location to have been cached, and the appropriated linked list in the LAT (160) is traversed from the entry corresponding to the last sector location cached.
Inventors
- 👤 Darren Chi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:31
CPC Classifications
G; G11; G11B; G11B27/00; G11B27/10; G11B27/19; G11B27/28; G11B27/32; G11B27/327; G11B27/329
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
172 words
A method for determining where in a storage medium a select block of a data stream is located, wherein the method is used in a system including the data stream, the storage medium, a memory device coupled to the storage medium, and a linked list initially stored in the storage medium, wherein the data stream is divided into at least one block, wherein the linked list has a number of links equal to at least the number of blocks in the data stream, and wherein each link of the linked list indicates where in the storage medium a different block of the data stream is located, the method comprising: determining whether the memory device is storing an indication of where in the storage medium the selected block is located; in response to the indication being stored in the memory device, retrieving the indication from the memory device; and in response to the indication not being stored in the memory device, traversing select links of the linked list until the indication is found.
Claim 2
Independent Claim
172 words
A method for determining where in a storage medium a select block of a data stream is located, wherein the method is used in a system including the data stream, the storage medium, a memory device coupled to the storage medium, and a linked list initially stored in the storage medium, wherein the data stream is divided into at least one block, wherein the linked list has a number of links equal to at least the number of blocks in the data stream, and wherein each link of the linked list indicates where in the storage medium a different block of the data stream is located, the method comprising: determining whether the memory device is storing an indication of where in the storage medium the selected block is located; in response to the indication being stored in the memory device, retrieving the indication from the memory device; and in response to the indication not being stored in the memory device, traversing select links of the linked list until the indication is found.
Claim 3
Dependent Claim
28 words
The method of claim 1, wherein an indication of information included in each link of the linked list that has been traversed is stored in the memory device.
Claim 4
Dependent Claim
41 words
The method of claim 2, wherein before the traversing step, the method further comprises the step of: in response to the indication not being stored in the memory device, determining a last link of the linked list to have been traversed.
Claim 5
Dependent Claim
31 words
The method of claim 3, wherein, in response to the indication not being stored in the memory device, the linked list is traversed from a link after the last link traversed.
Claim 6
Dependent Claim
33 words
The method of claim 1, wherein the memory device is a cache having a header and the determining step comprises the step of determining whether the header indicates that the indication is cached.
Claim 7
Independent Claim
207 words
A system for determining where a select block of a data stream is located, wherein the data stream is divided into at least one block, the system comprising: a storage medium, the storage medium storing the data stream; a linked list initially stored in the storage medium and having a number of links equal to at least the number of blocks in the data stream, each link of the link list indicating where in the storage medium a different block of the data stream is located; an interface coupled to the storage medium, the interface configured to traverse at least one link of the link list at a select time to determine where in the storage medium the select block is located; and a memory device coupled to the storage medium and the interface, the memory device storing an indication of information included in each link of the link list that has been traversed, the interface configured to determine whether the memory device is storing an indication of where in the storage medium the select block is located, and, in response to the indication being stored in the memory device, to retrieve the indication from the memory device instead of traversing the link list for the indication.
Claim 8
Independent Claim
207 words
A system for determining where a select block of a data stream is located, wherein the data stream is divided into at least one block, the system comprising: a storage medium, the storage medium storing the data stream; a linked list initially stored in the storage medium and having a number of links equal to at least the number of blocks in the data stream, each link of the link list indicating where in the storage medium a different block of the data stream is located; an interface coupled to the storage medium, the interface configured to traverse at least one link of the link list at a select time to determine where in the storage medium the select block is located; and a memory device coupled to the storage medium and the interface, the memory device storing an indication of information included in each link of the link list that has been traversed, the interface configured to determine whether the memory device is storing an indication of where in the storage medium the select block is located, and, in response to the indication being stored in the memory device, to retrieve the indication from the memory device instead of traversing the link list for the indication.
Claim 9
Dependent Claim
33 words
The system of claim 6, wherein the interface is configured to determine a last link of the link list to have been traversed in response to the memory device not storing the indication.
Claim 10
Dependent Claim
35 words
The system of claim 7, wherein the interface is configured to traverse the linked list from a link after the last link traversed in response to the indication not being stored in the memory device.
Claim 11
Dependent Claim
23 words
A computer program embodied in a tangible medium and capable of being read by a computer for performing the method of claim 1.
Claim 12
Dependent Claim
23 words
A computer program embodied in a tangible medium and capable of being read by a computer for performing the method of claim 4.
Claim 13
Dependent Claim
21 words
The method of claim 4, further comprising storing an indication of information included in each traversed link in the memory device.
References Cited (Backward Citations)
US5247658A
Cited
US5414826A
Cited
US5638506A
Cited
EP0510834A2
Cited
US5652865A
Cited
US5422762A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-27 | 2003-03-29 | 2003-09-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-27 | 2007-03-29 | 2007-09-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-27 | 2011-03-29 | 2011-09-28 | $7700.00 | Window Closed / Lapsed |