US5021946A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Mostly contiguous file allocation technique involving file extension
Assignee: Modular Computer Systems Inc
•
Filing: 1990-08-22
•
Granted: 1991-06-04
•
Expires: 2010-08-22
Abstract
Abstract A method for selecting the sizes and the ordering of the extents used to construct a file, a segment, or a virtual space of a computer system (file). The general method is defined to be any function, applied to this purpose, that, in general, attaches larger extents to the larger file addresses, and for which the selection of extent sizes is determined only by the address an extent is to reside at in the file, plus any tuning parameters. The method results in files which are mostly contiguous, and that stay mostly contiguous, irrespective of any growth or shrinkage the file may be subjected to during its lifetime. High contiguity improves performance by permitting a compact file representation, and, for disc files, improves performance by permitting larger blocks of data to be moved to or from the disc device, and by minimizing head seeks. The repeat factor, along with the doubling of extent size each time the repeat factor expires, is an important innovation that greatly reduces the internal and external fragmentation normally associated with extent based systems.
Inventors
- 👤 Joseph A. Korty
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 11:23
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9017; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
98 words
A file extension method for data processing files for selecting the sizes and ordering of the extents of a file, each extent including at least one block, wherein the size of an extent starting at a certain file address is an increasing function only of said file address and wherein all extents of the same size are adjacent to each other in the file, the extents being stored at arbitrary locations in a storage device, whereby files are kept contiguous or nearly contiguous as each extent has at least as many blocks as the extent immediately preceeding it.
Claim 2
Dependent Claim
98 words
A file extension method for data processing files for selecting the sizes and ordering of the extents of a file, each extent including at least one block, wherein the size of an extent starting at a certain file address is an increasing function only of said file address and wherein all extents of the same size are adjacent to each other in the file, the extents being stored at arbitrary locations in a storage device, whereby files are kept contiguous or nearly contiguous as each extent has at least as many blocks as the extent immediately preceeding it.
Claim 3
Dependent Claim
37 words
A method as described in claim 1, wherein for each pair of adjacent extents in the file with different sizes, the size of the larger extent is selected to be double the size of the smaller extent.
Claim 4
Dependent Claim
40 words
A method as described in claim 1, wherein for each pair of adjacent extents in the file with different sizes, the size of the larger extent is selected to be a constant multiple of the size of the smaller extent.
Claim 5
Dependent Claim
42 words
A method as described in claim 1, wherein for each pair of adjacent extents in the file with different sizes, the size of the larger extent is selected to be larger than the size of the smaller extent by a constant amount.
Claim 6
Dependent Claim
29 words
A method as described in claim 1, wherein for a sequence of unique extent sizes selected by said method, said sizes are based on a Fibonacci sequence of numbers.
Claim 7
Dependent Claim
33 words
A method as described in claim 1, wherein the number of adjacent extents in the file which are selected to have the same size is a constant greater than or equal to two.
Claim 8
Dependent Claim
39 words
A method as described in claim 1, wherein the number of adjacent extents in the file which are selected to have the same size, said number being called the repeat factor, is a nondecreasing function of the file address.
Claim 9
Dependent Claim
35 words
A method as described in claim 7, wherein the series of said repeat factors internally used by said function form an ascending sequence, such that any two adjacent repeat factors differ by a constant amount.
Claim 10
Dependent Claim
39 words
A method as described in claim 7, wherein the series of said repeat factors internally used by said function form an ascending sequence, such that the ratio of any two adjacent repeat factors is a constant greater than 1.0.
Claim 11
Dependent Claim
29 words
A method as described in claim 7, wherein the series of repeat factors internally used by said function form an ascending sequence based on a Fibanacci sequence of numbers.
Claim 12
Dependent Claim
40 words
A method as described in claim 7, wherein the series of said repeat factors internally used by said function has a finite number of members, and wherein the final member, in order to accomodate arbitrarily large files, is arbitrarily large.
Claim 13
Independent Claim
114 words
A method for storing an extendable data processing file having a series of blocks, comprising: (a) forming the file from a sequence of extents, the first extent of the sequence including the first block of the file and each subsequent extent of the sequence containing at least as many block as the extent immediately preceding said subsequent extent, the number of blocks in the beginning extents being less than in subsequent extents, with at least one extent of the sequence containing more blocks than the extent immediately preceding said at least one extent; and (b) storing the extents at arbitrary locations in a storage device, whereby the files are kept contiguous or mostly contiguous.
Claim 14
Independent Claim
114 words
A method for storing an extendable data processing file having a series of blocks, comprising: (a) forming the file from a sequence of extents, the first extent of the sequence including the first block of the file and each subsequent extent of the sequence containing at least as many block as the extent immediately preceding said subsequent extent, the number of blocks in the beginning extents being less than in subsequent extents, with at least one extent of the sequence containing more blocks than the extent immediately preceding said at least one extent; and (b) storing the extents at arbitrary locations in a storage device, whereby the files are kept contiguous or mostly contiguous.
Claim 15
Dependent Claim
52 words
The method of claim 12, wherein step (a) comprises assigning the first block of the file to the first extent of the sequence, assigning the second block of the file to the second extent of the sequence, and assigning the third block of the file to the third extent of the sequence.
Claim 16
Dependent Claim
46 words
The method of claim 12, wherein step (a) is conducted so that, for each pair of adjacent extents in the sequence, the extents of the pair either contain the same number of blocks or the larger extent of the pair is larger by a constant amount.
Claim 17
Dependent Claim
55 words
The method of claim 13, wherein step (a) further comprises assigning the fourth block of the file to the third extent of the sequence, assigning the fifth and sixth blocks of the file to the fourth extent of the sequence, and assigning the seventh block of the file to the fifth extent of the sequence.
Claim 18
Dependent Claim
24 words
The method of claim 15, wherein step (a) further comprises assigning the eighth, ninth, and tenth blocks of the file to the fifth extent.
Claim 19
Dependent Claim
56 words
The method of claim 12, wherein step (a) is conducted so that, for each pair of adjacent extents in the sequence, the extents of the pair either contain the same number of blocks or the larger extent of the pair contains an integer multiple of the number of blocks in the smaller extent of the pair.
Claim 20
Dependent Claim
10 words
The method of claim 17, wherein the integer is two.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-06-03 | 1994-12-03 | 1995-06-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-06-03 | 1998-12-03 | 1999-06-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-06-03 | 2002-12-03 | 2003-06-04 | $7700.00 | Window Closed / Lapsed |