Patent US5778392A successfully refreshed from Google Patents.
US5778392A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Opportunistic tile-pulling, vacancy-filling method and apparatus for file-structure reorganization
Assignee: Gen Digital Inc
•
Filing: 1996-04-01
•
Granted: 1998-07-07
•
Expires: 2016-04-01
Abstract
Abstract A storage reorganizing system subdivides a reorganizable storage space into tile areas. Each tile area either contains file data or does not contain file data. The data in a tile area that contains file data is referred to as a tile. A tile area that does not contain file data is referred to as a vacancy. Tiles that are not yet located in their goal positions, as defined by a recorded goal state definition, are opportunistically moved to available vacancies that are the goal positions for such tiles as the vacancies become available. Each tile move leaves behind it a new vacancy. The speed of opportunistic tile moving is optimized by first locating the largest vacancies that are each to be filled with the largest amount of tile data and by first moving tiles to such vacancies. One goal state produces a defragmented set of files. Another goal state produces an intentionally fragmented set of files. A third goal state produces a set of files that are fragmented and whose fragments are tightly interleaved on an access-wise basis so as to enable quick switching between a fragment of a first file and a fragment of a second file.
Inventors
- 👤 Steven Stockman
- 👤 John Blackburn
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 10:22
CPC Classifications
G; G11; G11B; G11B27/00; G11B27/10; G11B27/19; G11B27/28; G11B27/32; G11B27/327; G11B27/329; G06; G06F; G06F16/00; G06F16/10; G06F16/17; G06F16/1724; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0608; G06F3/0628; G06F3/0638; G06F3/0643; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0674; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956
Claims Analysis
Total Claims: 66
Claim 1
Independent Claim
192 words
A method for reorganizing file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing data and where each file is defined by a directory structure as data contained in a directory-specified organization of storage sub-areas, said method comprising the steps of: (a) identifying one or more files or groups of files that are to be reorganized, the identified files or file groups residing in the re-organizable storage space; (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (c) recording as a definition of a goal state, indications of goal locations for each tile in the re-organizable storage space; (d) identifying an already-existing vacancy space within the re-organizable storage space, and if none; creating at least one such vacancy space within the re-organizable storage space and identifying the created vacancy space; and (e) moving (pulling) into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the goal state as the goal location for the moved one or more source tiles.
Claim 2
Independent Claim
192 words
A method for reorganizing file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing data and where each file is defined by a directory structure as data contained in a directory-specified organization of storage sub-areas, said method comprising the steps of: (a) identifying one or more files or groups of files that are to be reorganized, the identified files or file groups residing in the re-organizable storage space; (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (c) recording as a definition of a goal state, indications of goal locations for each tile in the re-organizable storage space; (d) identifying an already-existing vacancy space within the re-organizable storage space, and if none; creating at least one such vacancy space within the re-organizable storage space and identifying the created vacancy space; and (e) moving (pulling) into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the goal state as the goal location for the moved one or more source tiles.
Claim 3
Dependent Claim
35 words
A machine-implemented file data reorganizing method according to claim 1 further comprising the step of: (f) automatically repeating said vacancy identifying step (d) and said tile moving step (e) until the goal state is achieved.
Claim 4
Dependent Claim
27 words
A file data reorganizing method according to claim 1 further comprising the step of: (f) repeating said vacancy identifying step (d) and said tile moving step (e).
Claim 5
Dependent Claim
54 words
A file data reorganizing method according to claim 3 further comprising the step of: (g) upon completion of a move of a last source tile of a given source file to that tile's destination as defined by the goal state, updating the directory structure to reflect the new organization of the re-organized given file.
Claim 6
Dependent Claim
66 words
A file data reorganizing method according to claim 4 further comprising the step of: (h) upon completion of a move of a last source tile to that tile's destination as defined by the goal state, said last move achieving the goal state, updating the directory structure to reflect consequential changes to free space within the re-organizable storage space as a result of the achieved goal state.
Claim 7
Dependent Claim
101 words
A file data reorganizing method according to claim 3 further comprising the steps of: (g.1) for each identified vacancy space and corresponding one or more source tiles that have that identified vacancy space defined as their goal location, generating and recording a respective move request; (g.2) collecting a plurality of move requests; and (g.3) sorting through the collected move requests to identify as a set of adjacency partners those move requests whose servicing either calls for respective reads of data from respective and access-wise adjacent source tiles or calls for respective writes of data to respective and access-wise adjacent vacancy areas.
Claim 8
Dependent Claim
56 words
A file data reorganizing method according to claim 6 wherein for each set of adjacency partners whose servicing calls for respective reads of data from respective and access-wise adjacent source tiles, said method further comprises the step of: (g.4) combining into a unitary data read operation, the data from said respective and access-wise adjacent source tiles.
Claim 9
Dependent Claim
56 words
A file data reorganizing method according to claim 6 wherein for each set of adjacency partners whose servicing calls for respective writes of data to respective and access-wise adjacent vacancy areas, said method further comprises the step of: (g.4) combining into a unitary data write operation, the data filling said respective and access-wise adjacent vacancy areas.
Claim 10
Dependent Claim
114 words
A file data reorganizing method according to claim 1 wherein said step (d) of identifying a vacancy space includes, for the case where there are plural already-existing vacancy spaces, (d.1) identifying a largest one of said plural already-existing vacancy spaces that is to be occupied in accordance with the goal state by a correspondingly largest amount of file data; and wherein said step (e) of moving one or more tiles includes, (e.1) before filling smaller vacancy areas, moving into the identified largest vacancy space the corresponding largest amount of file data that is contained in the one or more source tiles that have said identified largest vacancy space defined as their respective goal location.
Claim 11
Dependent Claim
37 words
A file data reorganizing method according to claim 1 wherein said re-organizable storage space is in a nonvolatile memory device selected from the group consisting of: magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.
Claim 12
Dependent Claim
19 words
A file data reorganizing method according to claim 1 wherein said re-organizable storage space is in a magnetic disk.
Claim 13
Dependent Claim
25 words
A file data reorganizing method according to claim 11 wherein each of said storage sub-area comprises an integral number of one or more disk sectors.
Claim 14
Dependent Claim
41 words
A file data reorganizing method according to claim 1 wherein said re-organizable storage space is in a random access memory device having the capacity to store voluminous amounts of data, said voluminous amounts of data being at least two hundred megabytes.
Claim 15
Dependent Claim
47 words
A file data reorganizing method according to claim 1 wherein said step of recording indications of goal locations for each tile is characterized by: (c.1) a goal state that changes the relative order of two or more tiles with respect to address in said re-organizable storage space.
Claim 16
Independent Claim
167 words
A method for rearranging storage locations of data stored in a re-organizable storage space of a data storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in said storage sub-areas, said method comprising the steps of: (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) providing as a recorded definition of a goal state, pre-recorded indications of goal resting positions for each tile in the storage space of the re-organizable storage means; (c) identifying an already-existing vacancy space within the re-organizable storage space; and (d) moving into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the recorded goal state as the goal resting position for the moved one or more source tiles.
Claim 17
Independent Claim
167 words
A method for rearranging storage locations of data stored in a re-organizable storage space of a data storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in said storage sub-areas, said method comprising the steps of: (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) providing as a recorded definition of a goal state, pre-recorded indications of goal resting positions for each tile in the storage space of the re-organizable storage means; (c) identifying an already-existing vacancy space within the re-organizable storage space; and (d) moving into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the recorded goal state as the goal resting position for the moved one or more source tiles.
Claim 18
Dependent Claim
34 words
A machine-implemented data reorganizing method according to claim 15 further comprising the step of: (e) automatically repeating said vacancy identifying step (c) and said tile moving step (d) until the goal state is achieved.
Claim 19
Dependent Claim
26 words
A data reorganizing method according to claim 15 further comprising the step of: (e) repeating said vacancy identifying step (c) and said tile moving step (d).
Claim 20
Dependent Claim
73 words
A data reorganizing method according to claim 17 further comprising within said step (e) of repeating, (e.1) automatically testing the size of one or more recent tile moves; and (e.2) in cases where the size of the tested one or more recent tile moves falls below a predefined threshold, creating a new vacancy area within said re-organizable storage space even if there are other vacancy areas already available within the re-organizable storage space.
Claim 21
Dependent Claim
82 words
A data reorganizing method according to claim 17 further comprising within said step (e) of repeating, (e.1) automatically testing the degree of fragmentation of current files that are being re-organized by one or more one or more recent tile moves; and (e.2) in cases where the degree of fragmentation of the tested files falls above a predefined threshold, creating a new vacancy area within said re-organizable storage space even if there are other vacancy areas already available within the re-organizable storage space.
Claim 22
Dependent Claim
47 words
A rearranging method according to claim 17 wherein said step of (c) of identifying an already-existing vacancy space further includes: (c.1) creating at least one vacancy space within the re-organizable storage space if none is already-existing and identifying the just-created vacancy space as the already-existing vacancy space.
Claim 23
Dependent Claim
30 words
A rearranging method according to claim 15 wherein said data storage means is selected from the group consisting of: magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.
Claim 24
Dependent Claim
16 words
A rearranging method according to claim 15 wherein said data storage means includes a magnetic disk.
Claim 25
Dependent Claim
23 words
A rearranging method according to claim 22 wherein each of said storage sub-area comprises an integral number of one or more disk sectors.
Claim 26
Dependent Claim
38 words
A rearranging method according to claim 15 wherein said data storage means includes a random access memory device having the capacity to store voluminous amounts of data, said voluminous amounts of data being at least two hundred megabytes.
Claim 27
Dependent Claim
50 words
A rearranging method according to claim 15 wherein said step of providing pre-recorded indications of goal resting positions for each tile includes: (c.1) providing a goal state that changes the relative order of two or more tiles with respect to the addresses of the tiles in said data storage means.
Claim 28
Independent Claim
212 words
A method for defragmenting file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of: (a) identifying one or more files or groups of files that are to be defragmented, the identified files or file groups residing in the re-organizable storage space; (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (c) recording as a definition of a goal state, indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places logically adjacent tiles of each file in access-wise closer adjacency relative to one another than such tiles are in their original state; and (d) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state, where a majority of said tile moves are performed just once for each of the moved tiles.
Claim 29
Independent Claim
212 words
A method for defragmenting file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of: (a) identifying one or more files or groups of files that are to be defragmented, the identified files or file groups residing in the re-organizable storage space; (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (c) recording as a definition of a goal state, indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places logically adjacent tiles of each file in access-wise closer adjacency relative to one another than such tiles are in their original state; and (d) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state, where a majority of said tile moves are performed just once for each of the moved tiles.
Claim 30
Dependent Claim
36 words
A file defragmenting method according to claim 26 wherein said re-organizable storage space is in a nonvolatile memory device selected from the group consisting of: magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.
Claim 31
Independent Claim
186 words
A method for fragmenting file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of: (a) identifying one or more files or groups of files that are to be fragmented, the identified files or file groups residing in the re-organizable storage space; (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (c) recording as a definition of a goal state, indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places logically adjacent tiles of each file in access-wise non-adjacency relative to one another; and (d) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.
Claim 32
Independent Claim
186 words
A method for fragmenting file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of: (a) identifying one or more files or groups of files that are to be fragmented, the identified files or file groups residing in the re-organizable storage space; (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (c) recording as a definition of a goal state, indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places logically adjacent tiles of each file in access-wise non-adjacency relative to one another; and (d) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.
Claim 33
Dependent Claim
35 words
A file data fragmenting method according to claim 28 further comprising the steps of: (e) after moving said tiles, using the identified one or more files to test the speed of a file-accessing application program.
Claim 34
Independent Claim
261 words
A method for increasing fragmentation of file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of: (a) identifying one or more files or groups of files whose degree of fragmentation is to be increased, the identified files or file groups residing in the re-organizable storage space; (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (c) recording as a definition of an original tile state, indications of original resting positions for each tile in the re-organizable storage space; (d) providing as a definition of a recorded goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space, where for each identified file whose degree of fragmentation is to be increased, said goal state places one or more of plural and respective source tiles that are access-wise adjacent to one another in the original tile state to one or more destination tiles that are each access-wise non-adjacent with respect to either one of the source tiles or another, logically-adjacent destination tile; and (e) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.
Claim 35
Independent Claim
261 words
A method for increasing fragmentation of file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of: (a) identifying one or more files or groups of files whose degree of fragmentation is to be increased, the identified files or file groups residing in the re-organizable storage space; (b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (c) recording as a definition of an original tile state, indications of original resting positions for each tile in the re-organizable storage space; (d) providing as a definition of a recorded goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space, where for each identified file whose degree of fragmentation is to be increased, said goal state places one or more of plural and respective source tiles that are access-wise adjacent to one another in the original tile state to one or more destination tiles that are each access-wise non-adjacent with respect to either one of the source tiles or another, logically-adjacent destination tile; and (e) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.
Claim 36
Independent Claim
207 words
A method for interleave-wise fragmenting file data of two or more files, where said file data is stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, where parts of the data of each file are defined as being logically adjacent to one another within the file, and where respective first, second and third parts that respectively belong to at least two different ones of said files are to be interleave-wise accessed one after the other by a predefined program, said method comprising the steps of: (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) providing as a recorded definition of a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places the respective first through third parts in interleaved access-wise adjacency to one another; and (c) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.
Claim 37
Independent Claim
207 words
A method for interleave-wise fragmenting file data of two or more files, where said file data is stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, where parts of the data of each file are defined as being logically adjacent to one another within the file, and where respective first, second and third parts that respectively belong to at least two different ones of said files are to be interleave-wise accessed one after the other by a predefined program, said method comprising the steps of: (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) providing as a recorded definition of a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places the respective first through third parts in interleaved access-wise adjacency to one another; and (c) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.
Claim 38
Dependent Claim
26 words
An interleave-wise fragmenting method according to claim 31 wherein (c.1) a majority of said tile moves are performed just once for each of the moved tiles.
Claim 39
Independent Claim
115 words
A method for rearranging storage locations of data stored in a re-organizable storage space of a data storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, said method comprising the steps of: (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) identifying as a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space; and (c) in accordance with the goal state, opportunistically moving tiles that are not in their goal resting positions to such goal resting positions when such goal resting positions are vacant.
Claim 40
Independent Claim
115 words
A method for rearranging storage locations of data stored in a re-organizable storage space of a data storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, said method comprising the steps of: (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) identifying as a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space; and (c) in accordance with the goal state, opportunistically moving tiles that are not in their goal resting positions to such goal resting positions when such goal resting positions are vacant.
Claim 41
Dependent Claim
130 words
An instructing apparatus for instructing a target data processing system to re-organize storage locations for data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, said instructing apparatus providing instructions for causing said target data processing system to perform the steps of: (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) identifying as a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space; and (c) in accordance with the identified goal state, opportunistically moving tiles that are not in their goal resting positions to such goal resting positions when such goal resting positions are vacant.
Claim 42
Dependent Claim
130 words
An instructing apparatus for instructing a target data processing system to re-organize storage locations for data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, said instructing apparatus providing instructions for causing said target data processing system to perform the steps of: (a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) identifying as a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space; and (c) in accordance with the identified goal state, opportunistically moving tiles that are not in their goal resting positions to such goal resting positions when such goal resting positions are vacant.
Claim 43
Dependent Claim
117 words
An instructing apparatus according to claim 34 further providing instructions for causing said target data processing system to perform the steps of: (d) searching said re-organizable storage space for largest ones of currently available vacancies that are to be filled in accordance with the identified goal state with largest amounts of data; and (c.1) within said step (c) of opportunistically moving tiles, if said searching step (d) results in a finding of one or more largest ones of currently available vacancies, moving those tiles that have the found largest ones of the currently available vacancies as their goal resting positions before moving tiles that have smaller ones of the currently available vacancies as their goal resting positions.
Claim 44
Dependent Claim
76 words
An instructing apparatus according to claim 35 further providing instructions for causing said target data processing system to perform the step of: (e) creating a vacancy within said re-organizable storage space that is a goal resting position for at least one tile not currently in its goal resting position if said searching step (d) fails to find any currently available vacancies that are also goal resting positions for tiles not currently in their goal resting positions.
Claim 45
Dependent Claim
28 words
An instructing apparatus according to claim 34 further providing (d) machine-readable indications defining a goal state that is identifiable by said step (b) as the identified goal state.
Claim 46
Dependent Claim
113 words
An instructing apparatus according to claim 37 further providing (e) machine-readable indications defining an original tile map, the original tile map indicating original positions of tiles and vacancies in the re-organizable storage space prior to the start of reorganization; and (f) instructions for causing said target data processing system to perform the step of: (f.1) after beginning said opportunistic moving of tiles in accordance with a first identified goal state, changing the identification of the goal state to be said original tile map as the identified goal state and continuing with opportunistic moving of tiles in accordance with the re-defined goal state to thereby return the stored data to its original storage organization.
Claim 47
Dependent Claim
86 words
An instructing apparatus according to claim 37 further providing (e) machine-readable indications defining a current tile map, the current tile map indicating essentially current positions of tiles and vacancies in the re-organizable storage space during reorganization; and (f) instructions for causing said target data processing system to perform the step of: (f.1) after beginning said opportunistic moving of tiles, periodically updating said current tile map so that the updated current tile map indicates the most current positions of tiles and vacancies in the re-organizable storage space.
Claim 48
Dependent Claim
117 words
An instructing apparatus according to claim 39 further providing instructions for causing said target data processing system to perform the step of: (g) searching said updated current tile map for largest ones of currently available vacancies that are to be filled in accordance with the goal state with largest amounts of data; and (c.1) within said step (c) of opportunistically moving tiles, if said searching step (d) results in a finding of one or more largest ones of currently available vacancies, moving those tiles that have the found largest ones of the currently available vacancies as their goal resting positions before moving tiles that have smaller ones of the currently available vacancies as their goal resting positions.
Claim 49
Dependent Claim
228 words
A machine system for carrying out data structure reorganization comprising: (a) a primary storage for storing a plurality of files in a file storage space in accordance with a first file storage organization, where the first file storage organization may be represented as a first mapping of tiles of data each in a corresponding tile space of the file storage space; and (b) file storage reorganizing means, operatively coupled to the primary storage, for reorganizing the storage organization of the primary storage such that one or more of the files are stored after the reorganization in the primary storage in accordance with a pre-defined second file storage organization that is different from said first file storage organization, where the pre-defined second file storage organization may be represented as a second mapping of the tiles of data each in a corresponding tile space; and where the file storage reorganizing means includes: (b.1) vacancy locating means for searching through the file storage space of the primary storage looking for a to-be-filled vacant space that is to be ultimately occupied according to the second mapping by a corresponding tile of data; and (b.2) tile moving means, operatively coupled to the vacancy locating means, for moving, in response to the finding of said to-be-filled vacant space, the corresponding tile of data from its currently occupied storage space to the found vacant space.
Claim 50
Dependent Claim
228 words
A machine system for carrying out data structure reorganization comprising: (a) a primary storage for storing a plurality of files in a file storage space in accordance with a first file storage organization, where the first file storage organization may be represented as a first mapping of tiles of data each in a corresponding tile space of the file storage space; and (b) file storage reorganizing means, operatively coupled to the primary storage, for reorganizing the storage organization of the primary storage such that one or more of the files are stored after the reorganization in the primary storage in accordance with a pre-defined second file storage organization that is different from said first file storage organization, where the pre-defined second file storage organization may be represented as a second mapping of the tiles of data each in a corresponding tile space; and where the file storage reorganizing means includes: (b.1) vacancy locating means for searching through the file storage space of the primary storage looking for a to-be-filled vacant space that is to be ultimately occupied according to the second mapping by a corresponding tile of data; and (b.2) tile moving means, operatively coupled to the vacancy locating means, for moving, in response to the finding of said to-be-filled vacant space, the corresponding tile of data from its currently occupied storage space to the found vacant space.
Claim 51
Dependent Claim
129 words
A machine system according to claim 41 wherein said vacancy locating means includes: (b.1a) best vacancy finding means for finding a preferred one or more vacancies among plural vacancies that can be currently filled with corresponding one or more tiles that are not yet in their goal position in accordance with the second file storage organization and outputting identifications of the found one or more vacancies, the preferred one or more vacancies being those currently fillable with the largest amount of tile data in accordance with the second file storage organization; and (b.1b) first-in first-out buffer means, operatively coupled to the best vacancy finding means, for receiving and storing said identifications of the preferred one or more vacancies and for outputting the stored identifications on a first-in first-out basis.
Claim 52
Dependent Claim
55 words
A machine system according to claim 42 wherein said tile moving means includes: (b.2a) move request generating means for generating move requests that request a move of a given tile to a given vacancy; and (b.2b) request sorting means for sorting generated move requests according to access-wise adjacent source tiles or access-wise adjacent destination vacancies.
Claim 53
Dependent Claim
40 words
A machine system according to claim 43 wherein said tile moving means includes: (b.2c) a move buffer for sequentially receiving access-wise adjacent plurality of tiles, for storing the received tiles, and for sequentially outputting data to access-wise adjacent destination vacancies.
Claim 54
Dependent Claim
33 words
A machine system according to claim 41 wherein said primary storage includes a nonvolatile memory device selected from the group consisting of: magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.
Claim 55
Dependent Claim
16 words
A machine system according to claim 45 wherein said primary storage includes a magnetic hard disk.
Claim 56
Dependent Claim
198 words
An instructing apparatus for instructing a target data processing system to re-organize storage locations for data stored in a re-organizable storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, and where the storage means includes a directory structure for defining files of the storage means each as data contained in a respective directory-specified organization of said storage sub-areas and for further defining vacancy spaces each as provided by a respective directory-specified organization of said storage sub-areas, said instructing apparatus providing instructions for causing said target data processing system to perform the steps of: (a) subdividing the data of the re-organizable storage means into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) recognizing as a definition of a goal state, pre-recorded indications of goal locations for tiles in the re-organizable storage space; (c) identifying an already-existing vacancy space within the re-organizable storage means; and (d) opportunistically pulling into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the recognized goal state as the goal location for the moved one or more source tiles.
Claim 57
Dependent Claim
198 words
An instructing apparatus for instructing a target data processing system to re-organize storage locations for data stored in a re-organizable storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, and where the storage means includes a directory structure for defining files of the storage means each as data contained in a respective directory-specified organization of said storage sub-areas and for further defining vacancy spaces each as provided by a respective directory-specified organization of said storage sub-areas, said instructing apparatus providing instructions for causing said target data processing system to perform the steps of: (a) subdividing the data of the re-organizable storage means into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas; (b) recognizing as a definition of a goal state, pre-recorded indications of goal locations for tiles in the re-organizable storage space; (c) identifying an already-existing vacancy space within the re-organizable storage means; and (d) opportunistically pulling into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the recognized goal state as the goal location for the moved one or more source tiles.
Claim 58
Dependent Claim
33 words
An instructing apparatus according to claim 47 wherein said storage means includes a nonvolatile memory device selected from the group consisting of: magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.
Claim 59
Dependent Claim
73 words
An instructing apparatus according to claim 47 further providing instructions for causing said target data processing system to perform the step of: (e) in a case where prior to the execution of said step (d) of opportunistically pulling it is determined that there is no already-existing vacancy space within the re-organizable storage mean, creating such a vacancy space and identifying the created vacancy space for use by said step (d) of opportunistically pulling.
Claim 60
Dependent Claim
61 words
An instructing apparatus according to claim 47 wherein said storage means includes a directory structure that defines logical linkages of said sub-areas as respective files or free spaces and wherein the instructing apparatus further provides instructions for causing said target data processing system to perform the step of: (e) limiting said opportunistic pulling of tiles to tiles associated with pre-identified files.
Claim 61
Dependent Claim
54 words
An instructing apparatus according to claim 50 further providing instructions for causing said target data processing system to perform the step of: (f) updating the directory structure to define the logical linkages of sub-areas for a given file after the goal state for that given file is reached by said opportunistic pulling of tiles.
Claim 62
Dependent Claim
54 words
An instructing apparatus according to claim 50 further providing instructions for causing said target data processing system to perform the step of: (f) updating the directory structure to define the logical linkages of sub-areas for remaining free spaces after the goal state for said pre-identified files is reached by said opportunistic pulling of tiles.
Claim 63
Dependent Claim
15 words
An instructing apparatus according to claim 47 wherein each tile corresponds to one storage sub-area.
Claim 64
Dependent Claim
73 words
An instructing apparatus according to claim 47 wherein said storage means includes a directory structure that defines logical linkages of said sub-areas as respective files or free spaces and wherein the instructing apparatus further provides instructions for causing said target data processing system to perform the step of: (e) generating and recording indications of goal locations for tiles so as to define a goal state that defragments one or more of said files.
Claim 65
Dependent Claim
81 words
An instructing apparatus according to claim 47 wherein said storage means includes a directory structure that defines logical linkages of said sub-areas as respective files or free spaces and wherein the instructing apparatus further provides instructions for causing said target data processing system to perform the step of: (e) generating and recording indications of goal locations for tiles so as to define a goal state that places pre-identified ones of said files in an access-wise fastest portion of said storage means.
Claim 66
Dependent Claim
81 words
An instructing apparatus according to claim 47 wherein said storage means includes a directory structure that defines logical linkages of said sub-areas as respective files or free spaces and wherein the instructing apparatus further provides instructions for causing said target data processing system to perform the step of: (e) generating and recording indications of goal locations for tiles so as to define a goal state that leaves a pre-identified subset of said files in their original organization within said storage means.
References Cited (Backward Citations)
US5481702A
Cited
US5561786A
Cited
US5561785A
Cited
US5623654A
Cited
US5463776A
Cited
US5574907A
Cited
US5604902A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-06 | 2002-01-05 | 2002-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-06 | 2006-01-05 | 2006-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-06 | 2010-01-05 | 2010-07-07 | $7700.00 | Window Closed / Lapsed |