EP0463874A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Cache arrangement for file system in digital data processing system
Assignee: Digital Equipment Corp
•
Filing: 1991-06-27
•
Granted: —
•
Expires: 2011-06-27
Abstract
Abstract A method for caching information needed by application programs from a secondary storage in which the cache memory 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. The use and reuse of the cache entries is based on the links. 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. The fetching of information from secondary storage into the cache is regulated based on the quotas. 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
EP
Data Source
google_patents
Last Synchronized
2026-11-06 02:27
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: 61
Claim 1
Independent Claim
106 words
A method for managing the use and reuse of entries of a cache, said entries containing data retrieved from mass storage into said cache to be thereafter available for use by a computer system, comprising grouping entries containing similar types of data; assigning each entry a priority for storage relative to other entries of the same group; identifying at least first and second entries of different said groups which are related in the organization of data in said mass storage; and selecting an entry 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
Dependent Claim
12 words
The method of claim 1 further comprising storing pointers linking related entries.
Claim 3
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 4
Dependent Claim
81 words
The method of claim 3 wherein the step of selecting an entry for re-use comprises selecting one said group of entries according 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 5
Dependent Claim
17 words
The method of claim 2 wherein re-use of an entry results in re-use of a related entry.
Claim 6
Dependent Claim
124 words
The method of claim 2 adapted to prefetch data into said cache when data required by said computer system is retrieved from said mass storage, further 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 7
Dependent Claim
25 words
The method of claim 6 further comprising limiting the number of additional entries which are prefetched into said cache upon retrieval of said required data.
Claim 8
Dependent Claim
18 words
The method of claim 2 further comprising limiting the number of entries in one group in said cache.
Claim 9
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 10
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 11
Independent Claim
138 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 a 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 related file header and directory entries in which the identified directory entry represents the directory containing the file represented by the identified file header entry, and storing pointers linking the related entries, assigning each entry a priority for storage relative to the other entries in the same level, and managing the use and re-use of said cache entries according to the priority for storage assigned to said entries.
Claim 12
Dependent Claim
68 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 related file contents and file header entries in which the identified file header entry represents the file containing the file contents represented by the identified file contents entry, and storing pointers linking the related entries.
Claim 13
Dependent Claim
64 words
The method of claim 12 further comprising adding new entries in a given level of said cache by the steps of searching for an unused entry for 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 a selected entry from said given level.
Claim 14
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 15
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 16
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 17
Dependent Claim
29 words
The method of claim 13 wherein replacement or removal of an entry from a given level entails removing all entries of lower levels which are related to said entry.
Claim 18
Dependent Claim
50 words
The method of claim 17 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 19
Dependent Claim
36 words
The method of claim 18 further comprising retaining a file header entry in said cache so long as said file remains open, whether or not any file contents of said file are stored in said cache.
Claim 20
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 21
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 22
Dependent Claim
47 words
The method of claim 21 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 23
Dependent Claim
52 words
The method of claim 22 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 24
Dependent Claim
68 words
The method of claim 23 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 25
Dependent Claim
130 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 a predetermined 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 a predetermined 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 a predetermined end of said lower level's list.
Claim 26
Dependent Claim
151 words
The method of claim 25 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 predetermined 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 predetermined end of said lower level's list.
Claim 27
Dependent Claim
32 words
The method of claim 25 wherein replacing a selected entry from a given level comprises selecting the entry of said given level's list which is at the end opposite said predetermined end.
Claim 28
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.
Claim 29
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 30
Dependent Claim
59 words
The method of claim 29 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 31
Dependent Claim
38 words
The method of claim 30 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 32
Dependent Claim
19 words
The method of claim 29 further comprising establishing further quotas limiting the total number of entries of each level.
Claim 33
Dependent Claim
44 words
The method of claim 32 wherein said quotas are enforced in accordance with the following step: when a quota described in claim 32 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 33 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
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 36
Dependent Claim
38 words
The method of claim 32 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 37
Dependent Claim
23 words
The method of claim 36 wherein said quotas are established such that the directory entry level is less likely to reach its quota.
Claim 38
Dependent Claim
35 words
The method of claim 37 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 39
Dependent Claim
36 words
The method of claim 38 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 40
Dependent Claim
27 words
The method of claim 38 wherein adjustments to said quotas are enforced by removing entries from said cache and placing said entries in said unused entry levels.
Claim 41
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 42
Dependent Claim
14 words
The method of claim 41 wherein said additional entry is at said given level.
Claim 43
Dependent Claim
28 words
The method of claim 41 wherein said additional entry is at a level different from said given level, and said additional entry is related to said needed entry.
Claim 44
Dependent Claim
20 words
The method of claim 41 wherein multiple entries are prefetched, the number of entries being limited by a prefetching quota.
Claim 45
Dependent Claim
21 words
The method of claim 44 wherein said prefetching quota is adjusted based on the number of entries available in all levels.
Claim 46
Dependent Claim
49 words
The method of claim 44 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 47
Dependent Claim
119 words
The method of claim 41 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, whereby prefetched entries which have not been used by an application program in a predetermined time period after said request may be aged and removed from said cache.
Claim 48
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 49
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 50
Dependent Claim
60 words
The method of claim 49 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 51
Independent Claim
89 words
A method of storing 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 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.
Claim 52
Dependent Claim
16 words
The method of claim 51 wherein the amount of information prefetched is limited by a quota.
Claim 53
Dependent Claim
30 words
The method of claim 51 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 54
Dependent Claim
34 words
The method of claim 53 wherein said prefetching comprises fetching the headers of files having symbolic file names which are similar to the symbolic file name of the file associated with the needed header.
Claim 55
Dependent Claim
27 words
The method of claim 54 wherein the nature of the similarity between said symbolic file names is determined by the type of application program making said request.
Claim 56
Dependent Claim
28 words
The method of claim 55 wherein said application program is a compiler, and said needed and prefetched files are source and object modules of a program being compiled.
Claim 57
Dependent Claim
29 words
The method of claim 51 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 58
Independent Claim
100 words
A method of 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 on the amount of information which may be 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 59
Dependent Claim
17 words
The method of claim 58 wherein said quotas may be disabled during operation of specified application programs.
Claim 60
Dependent Claim
16 words
The method of claim 59 wherein said quotas are disabled during operation of a backup program.
Claim 61
Independent Claim
97 words
A method of storing information retrieved by application programs from a file system in a cache, said information including file contents as well as file headers describing files and directory files describing directories of files, comprising 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 file contents of said file are stored in said cache.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.