Patent US3458380A successfully refreshed from Google Patents.
US5390318A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Managing the fetching and replacement of cache entries associated with a file system
Assignee: Hewlett Packard Development Co LP
•
Filing: 1994-05-16
•
Granted: 1995-02-14
•
Expires: 2014-05-16
Abstract
Abstract Information needed by application programs from a secondary storage is cached in a cache memory which is organized in multiple levels, each level having multiple entries, the entries of each level receiving information of a predetermined category, each entry being accessible independently. Links are defined between entries of one level of the cache memory and entries at another level of the cache memory, the links corresponding to information relationships specified by a user of information stored in the secondary storage. In response to a request to a file system from an application for needed information, the needed information is fetched into the cache, and in connection with fetching the needed information, other information is prefetched from the system of files which is not immediately needed. Quotas are established on information which may be fetched from a secondary storage into the cache, the quotas being applicable to file contents within a file and to the number of files within a directory. Upon a request from an application program to open a file, an entry is created in a cache corresponding to the file, the entry including file header information. The file header information is retained in the cache so long as the file remains open, whether or not any file contents of the file remain in cache. The entries of three level of the cache respectively receive directory information, file header information, and file contents information.
Inventors
- 👤 Kadangode K. Ramakrishnan
- 👤 Prabuddha Biswas
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 04:37
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0866; G06F16/00; G06F16/90; G06F16/901; G06F16/9017; G06F16/902; G06F12/0862; G06F12/12; G06F12/121; G06F12/128
Claims Analysis
Total Claims: 67
Claim 1
Independent Claim
115 words
A method for managing the use and re-use of entries of a cache, said entries containing data retrieved from a mass storage into said cache to be thereafter available for use by a computer system, comprising the computer system grouping entries; assigning each entry a priority for storage relative to other entries of the same group; identifying at least a first entry and a second entry belonging to different respective said groups which are related in a system of files in said mass storage; and selecting one of said entries of said cache for re-use according to the priority for storage assigned to said entry and the priority for storage assigned to identified related entries.
Claim 2
Independent Claim
115 words
A method for managing the use and re-use of entries of a cache, said entries containing data retrieved from a mass storage into said cache to be thereafter available for use by a computer system, comprising the computer system grouping entries; assigning each entry a priority for storage relative to other entries of the same group; identifying at least a first entry and a second entry belonging to different respective said groups which are related in a system of files in said mass storage; and selecting one of said entries of said cache for re-use according to the priority for storage assigned to said entry and the priority for storage assigned to identified related entries.
Claim 3
Dependent Claim
17 words
The method of claim 1 further comprising storing pointers in said cache linking said identified related entries.
Claim 4
Dependent Claim
112 words
The method of claim 2 wherein the step of assigning entries priority for storage comprises assigning each said entry a priority for storage relative to other entries within its group by the following steps: when the data contained in a first entry of a first group is used by said computer system, said first entry is assigned the highest priority for storage within the entries of said first group, and when a second entry, which is related by a pointer to said first entry, is assigned the highest priority for storage of a second group, said first entry is assigned the highest priority for storage within the entries of said first group.
Claim 5
Dependent Claim
87 words
The method of claim 3 wherein the step of selecting an entry for re-use comprises selecting one said group of entries that contain data of a type corresponding to the type of data to be stored in the re-used entry, and selecting the entry of the selected group which has the lowest priority for storage, whereby the selected entry has the lowest priority for storage of the selected group and all entries related to the selected entry have the lowest priority for storage of their respective groups.
Claim 6
Dependent Claim
26 words
The method of claim 3 further comprising removing from said cache entries which are not used by said computer system for a given duration of time.
Claim 7
Dependent Claim
17 words
The method of claim 2 wherein re-use of an entry results in re-use of a related entry.
Claim 8
Dependent Claim
125 words
The method of claim 2, further comprising prefetching data into said cache when data required by said computer system is retrieved from said mass storage, said prefetching comprising retrieving said required data into a first entry, placing said first entry into a first group, identifying a second entry in a second group which is related to said first entry, storing a pointer linking said first entry to said second entry, identifying other data in said mass storage which is related to the data contained in said second entry in a similar manner as said required data, retrieving said other data into one or more additional entries, placing said additional entries into said first group, and storing pointers linking said additional entries to said second entry.
Claim 9
Dependent Claim
25 words
The method of claim 7 further comprising limiting the number of additional entries which are prefetched into said cache upon retrieval of said required data.
Claim 10
Dependent Claim
18 words
The method of claim 2 further comprising limiting the number of entries in one group in said cache.
Claim 11
Dependent Claim
25 words
The method of claim 2 further comprising for each group, limiting the number of entries which are related to the same entry in another group.
Claim 12
Independent Claim
140 words
A method for caching information retrieved by application programs from files organized in a file system in mass storage, comprising organizing a cache in at least two levels having multiple cache entries, including an upper level comprising directory entries storing directory file information and representing directories in said file system, and a lower level comprising file header entries storing file header information and representing files in said file system, identifying file header and directory entries related such that the identified directory entry represents the directory containing the file represented by the identified file header entry, and storing pointers in the cache linking the related entries, assigning each entry a priority for storage relative to the other entries in the same level, and managing use and re-use of said cache entries according to the priority for storage assigned to said entries.
Claim 13
Independent Claim
140 words
A method for caching information retrieved by application programs from files organized in a file system in mass storage, comprising organizing a cache in at least two levels having multiple cache entries, including an upper level comprising directory entries storing directory file information and representing directories in said file system, and a lower level comprising file header entries storing file header information and representing files in said file system, identifying file header and directory entries related such that the identified directory entry represents the directory containing the file represented by the identified file header entry, and storing pointers in the cache linking the related entries, assigning each entry a priority for storage relative to the other entries in the same level, and managing use and re-use of said cache entries according to the priority for storage assigned to said entries.
Claim 14
Dependent Claim
71 words
The method of claim 11 wherein said cache includes a third lowest level comprising file contents entries storing file contents information and representing file contents in said file system, and further comprising identifying file contents and file header entries related such that the identified file header entry represents the file containing the file contents represented by the identified file contents entry, and storing pointers in the cache linking the related entries.
Claim 15
Dependent Claim
73 words
The method of claim 12, wherein each cache level may have been new entries added, further comprising adding new entries in a given level of said cache by the steps of searching for an unused entry in said given level, and where an unused entry is located, adding said unused entry to the entries of said given level, or where an unused entry is not located, replacing an entry of said given level.
Claim 16
Dependent Claim
46 words
The method of claim 13 further comprising when an entry is added to a given level, or when the information stored by an entry of a given level is used by an application program, said entry is indicated as the most-recently-used entry of said given level.
Claim 17
Dependent Claim
37 words
The method of claim 14 further comprising when said entry is indicated as the most-recently-used entry of said given level, an entry related to said entry is indicated as the most-recently-used entry of the related entry's level.
Claim 18
Dependent Claim
103 words
The method of claim 15 wherein replacing an entry from a given level comprises selecting the least-recently-used entry in said given level, whereby if the replacing entry is a directory entry, the replaced entry is the entry which contained the directory file of the least-recently-used directory, if the replacing entry is a file header entry, the replaced entry is the entry which contained the header of the least-recently-used file of the least-recently-used directory; or if the replacing entry is a file contents entry, the replaced entry is the entry which contained the least-recently-used file contents of the least-recently-used file of the least-recently-used directory.
Claim 19
Dependent Claim
20 words
The method of claim 16 wherein each said entry contains a replacement value used for selecting an entry for replacement.
Claim 20
Dependent Claim
47 words
The method of claim 17 wherein said replacement value is a time stamp, and when an entry is added or when the information stored in an entry is used by an application program, the replacement value of said entry is updated to a current time stamp value.
Claim 21
Dependent Claim
52 words
The method of claim 18 further comprising when an entry is added to a given level or when the information stored in an entry at a given level is used by an application program, updating the replacement value of a related entry of a higher level to a current time stamp value.
Claim 22
Dependent Claim
68 words
The method of claim 19 wherein replacing a selected entry from a given level comprises selecting the entry of said given level containing the least recent time stamp value, and if said replaced entry is the only entry of said given level which is related to a second entry in a higher level, replacement of said replaced entry entails removal of said second entry from said higher level.
Claim 23
Dependent Claim
127 words
The method of claim 16 wherein the entries of each said level are organized as a list, and when an entry is added to a given level or when the information stored in a given entry at a given level is used by an application program: (1) said added or used entry is moved to an end of said given level's list, (2) an entry of a higher level which is related to said added or used entry is moved to an end of said higher level's list, and (3) one or more entries of a lower level which are related to said added or used entry are moved, as a group and maintaining the ordering within the group, to an end of said lower level's list.
Claim 24
Dependent Claim
149 words
The method of claim 2 further comprising when an entry is added to a given level or when the information stored in a given entry at a given level is used by an application program: (4) one or more entries of said given level which are related to the entry of said higher level which was moved in step (2) are moved, as a group and maintaining the ordering within the group, to a position next to said added or used entry at said end of said given level's list, and (5) one or more groups of entries of said lower level which are related to the entry of said given level which was moved in step (4) are moved, as groups and maintaining the ordering within and between the groups, to positions next to the entries moved in step (3) at said end of said lower level's list.
Claim 25
Dependent Claim
31 words
The method of claim 21 wherein replacing a selected entry from a given level comprises selecting an entry of said given level's list which is at an end opposite said end.
Claim 26
Dependent Claim
116 words
The method of claim 12 further comprising in response to a request from an application program requiring that a directory entry be added to said cache, fetching said directory entry into said cache, and in connection with fetching said directory entry, prefetching into said cache file header entries storing headers of files from the directory represented by said directory entry, and in response to a request from an application program requiring that a file header entry be added to said cache, fetching said file header entry into said cache, and in connection with fetching said file header entry, prefetching into said cache file contents entries storing contents of the file represented by said file header entry.
Claim 27
Dependent Claim
42 words
The method of claim 13 further comprising upon a request from an application program to open a file, determining whether a file header entry storing the header of said file is stored in said cache, and if not adding such an entry.
Claim 28
Dependent Claim
54 words
The method of claim 12 further comprising establishing quotas which limit the number of file header entries which are related to one directory entry, and the number of file contents entries which are related to one file header entry, and managing the use and re-use of entries in said levels to enforce said quotas.
Claim 29
Dependent Claim
59 words
The method of claim 26 wherein said quotas are enforced in accordance with the following step: when a quota will be exceeded by adding a new entry to a given level, an existing entry from said given level which is related to the same entry in a higher level as said new entry is replaced by said new entry.
Claim 30
Dependent Claim
38 words
The method of claim 27 wherein the entry replaced by said new entry is the least-recently-used of the entries of said given level which are related to the same entry in a higher level as said new entry.
Claim 31
Dependent Claim
104 words
The method of claim 28 wherein the entry replaced by said new entry is the least-recently-used of the entries of said given level, whereby if the replacing entry is a directory entry, the replaced entry is the entry which contained the directory file of the least-recently-used directory, if the replacing entry is a file header entry, the replaced entry is the entry which contained the header of the least-recently-used file of the least-recently-used directory; or if the replacing entry is a file contents entry, the replaced entry is the entry which contained the least-recently-used file contents of the least-recently-used file of the least-recently-used directory.
Claim 32
Dependent Claim
19 words
The method of claim 26 further comprising establishing further quotas limiting the total number of entries of each level.
Claim 33
Dependent Claim
44 words
The method of claim 30 wherein said quotas are enforced in accordance with the following step: when a quota described in claim 30 will be exceeded by adding said new entry, an existing entry from said given level is replaced by said new entry.
Claim 34
Dependent Claim
104 words
The method of claim 31 wherein the entry replaced by said new entry is the least-recently-used of the entries of said given level, whereby if the replacing entry is a directory entry, the replaced entry is the entry which contained the directory file of the least-recently-used directory, if the replacing entry is a file header entry, the replaced entry is the entry which contained the header of the least-recently-used file of the least-recently-used directory; or if the replacing entry is a file contents entry, the replaced entry is the entry which contained the least-recently-used file contents of the least-recently-used file of the least-recently-used directory.
Claim 35
Dependent Claim
38 words
The method of claim 30 wherein said quotas are adjusted based on the frequency of use of the entries in said levels, whereby the storage space in said cache that is devoted to each level may be adjusted.
Claim 36
Dependent Claim
27 words
The method of claim 33 wherein said quotas are established such that the directory entry level is less likely to reach its quota than is another level.
Claim 37
Dependent Claim
35 words
The method of claim 34 further comprising said quotas are adjusted based on the number of available unused entries, whereby the storage space in said cache that is devoted to each level may be adjusted.
Claim 38
Dependent Claim
36 words
The method of claim 35 further comprising organizing unused entries into one or more levels corresponding to said higher, lower, and lowest levels, and wherein said quotas are adjusted by reallocating unused entries between said levels.
Claim 39
Dependent Claim
27 words
The method of claim 35 wherein adjustments to said quotas are enforced by removing entries from said cache and placing said entries in said unused entry levels.
Claim 40
Dependent Claim
51 words
The method of claim 11 further comprising in response to a request from an application program requiring that an entry be added to a given level of said cache, fetching said needed entry into said cache, and in connection with fetching said needed entry, prefetching an additional entry into said cache.
Claim 41
Dependent Claim
14 words
The method of claim 38 wherein said additional entry is at said given level.
Claim 42
Dependent Claim
28 words
The method of claim 38 wherein said additional entry is at a level different from said given level, and said additional entry is related to said needed entry.
Claim 43
Dependent Claim
20 words
The method of claim 38 wherein multiple entries are prefetched, the number of entries being limited by a prefetching quota.
Claim 44
Dependent Claim
21 words
The method of claim 41 wherein said prefetching quota is adjusted based on the number of entries available in all levels.
Claim 45
Dependent Claim
49 words
The method of claim 41 further comprising organizing unused entries into one or more levels corresponding to said higher, lower, and lowest levels, and each said level has a prefetching quota, and wherein each level's prefetching quota is adjusted based on the number of entries available in said level.
Claim 46
Dependent Claim
120 words
The method of claim 38 wherein each said entry contains an old age indicator used for selecting entries for removal, and further comprising setting the old age indicator of needed entries when placed in said cache, clearing the old age indicator of prefetched entries when placed in said cache, when an entry is used by an application program, setting the old age indicator of said entry, and periodically removing from said cache all entries having cleared old age indicators, and then clearing the old age indicators of all entries which remain in the cache, whereby prefetched entries which have not been used by an application program in time period after said request may be aged and removed from said cache.
Claim 47
Dependent Claim
28 words
The method of claim 11 further comprising aging and removing from said cache entries which have not been used by an application program over a predetermined time period.
Claim 48
Dependent Claim
60 words
The method of claim 45 wherein each said entry contains a old age indicator, and said aging comprises when an entry is used by an application program, setting the old age indicator of said entry, and periodically removing from said cache all entries having cleared old age indicators, and then clearing the old age indicators of all entries which remain.
Claim 49
Dependent Claim
29 words
The method of claim 13 wherein replacement or removal of an entry from a given level entails removing all entries or lower levels which are related to said entry.
Claim 50
Dependent Claim
50 words
The method of claim 47 wherein if said replaced or removed entry is the only entry of said given level which is related to a second entry in a higher level, replacement or removal of said replaced or removed entry entails removal of said second entry from said higher level.
Claim 51
Dependent Claim
36 words
The method of claim 48 further comprising retaining a file header entry in said cache as long as said file remains open, whether or not any file contents of said file are stored in said cache.
Claim 52
Independent Claim
100 words
A method comprising storing in a cache information describing files and directories of files retrieved by application programs from a file system in which files are organized according to user-defined information relationships among said files and directories, storing in said cache contents of said files in response to a request to said file system from an application program, fetching needed information into a cache, and in connection with fetching said needed information, prefetching other information from said file system which is not immediately needed but is related to said needed information through said user-defined relationships among said files and directories.
Claim 53
Independent Claim
100 words
A method comprising storing in a cache information describing files and directories of files retrieved by application programs from a file system in which files are organized according to user-defined information relationships among said files and directories, storing in said cache contents of said files in response to a request to said file system from an application program, fetching needed information into a cache, and in connection with fetching said needed information, prefetching other information from said file system which is not immediately needed but is related to said needed information through said user-defined relationships among said files and directories.
Claim 54
Dependent Claim
16 words
The method of claim 50 wherein the amount of information prefetched is limited by a quota.
Claim 55
Dependent Claim
13 words
The method of claim 50 wherein said prefetching comprises prefetching headers of files.
Claim 56
Dependent Claim
29 words
The method of claim 50 wherein said needed information is a directory file and said prefetching comprises prefetching headers of files in the directory described by said directory file.
Claim 57
Dependent Claim
30 words
The method of claim 50 wherein said needed information is a file header and said prefetching comprises prefetching headers of files in the same directory as said needed file header.
Claim 58
Dependent Claim
32 words
The method of claim 54 wherein said prefetching comprises fetching the header of files having symbolic file names which match the symbolic file name of the file associated with the needed header.
Claim 59
Dependent Claim
27 words
The method of claim 55 wherein the nature of the similarity between said symbolic file names is determined by the type of application program making said request.
Claim 60
Dependent Claim
28 words
The method of claim 56 wherein said application program is a compiler, and said needed and prefetched files are source and object modules of a program being compiled.
Claim 61
Independent Claim
102 words
A method of a managing a cache of information retrieved by application programs from a file system organized according to user-defined information relationships, said information including file contents as well as file headers describing files and directory files describing directories of files, comprising establishing quotas that set a limit on the amount of information fetched from said mass storage into said cache, said quotas being applicable to the amount of file contents from a given file and the number of file headers from a given directory, and regulating the fetching of information from mass storage into said cache based on said quotas.
Claim 62
Independent Claim
102 words
A method of a managing a cache of information retrieved by application programs from a file system organized according to user-defined information relationships, said information including file contents as well as file headers describing files and directory files describing directories of files, comprising establishing quotas that set a limit on the amount of information fetched from said mass storage into said cache, said quotas being applicable to the amount of file contents from a given file and the number of file headers from a given directory, and regulating the fetching of information from mass storage into said cache based on said quotas.
Claim 63
Dependent Claim
17 words
The method of claim 58 wherein said quotes may be disabled during operation of specified application programs.
Claim 64
Dependent Claim
16 words
The method of claim 59 wherein said quotas are disabled during operation of a backup program.
Claim 65
Independent Claim
109 words
A method for storing in a cache files retrieved from a file system in a computer system, comprising the computer system storing in a cache, information describing files and directories of files retrieved by application programs from a file system, storing in said cache, contents of said files upon a request from an application program to open a file, determining whether an entry storing the header of said file is stored in said cache, and if not creating such an entry, and retaining said entry in said cache so long as said file remains open, whether or not any said contents of said file are stored in said cache.
Claim 66
Independent Claim
109 words
A method for storing in a cache files retrieved from a file system in a computer system, comprising the computer system storing in a cache, information describing files and directories of files retrieved by application programs from a file system, storing in said cache, contents of said files upon a request from an application program to open a file, determining whether an entry storing the header of said file is stored in said cache, and if not creating such an entry, and retaining said entry in said cache so long as said file remains open, whether or not any said contents of said file are stored in said cache.
Claim 67
Dependent Claim
49 words
The method of claim 11 further comprising establishing a quota which limits the number of file header entries in said lower level which are related to one directory entry in said upper level, and managing the use and re-use of entries in said lower level to enforce said quota.
References Cited (Backward Citations)
US3898624A
Cited
US4489378A
Cited
US4928239A
Cited
EP0278472A2
Cited
US5151989A
Cited
EP0284664A2
Cited
US5008820A
Cited
US5134563A
Cited
US5093779A
Cited
JPH01274257A
Cited
EP0352447A2
Cited
US5146578A
Cited
US5133060A
Cited
US5043885A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-02-13 | 1998-08-15 | 1999-02-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-02-13 | 2002-08-15 | 2003-02-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-02-13 | 2006-08-15 | 2007-02-14 | $7700.00 | Window Closed / Lapsed |