US6434663B1 — Disk block allocation optimization methodology wi…

Claim 1

Independent Claim 157 words

An apparatus comprising (a) an execution unit for executing programming instructions; and (b) a storage medium coupled to the execution unit and having stored therein a first plurality of programming instructions to be executed by the execution unit for implementing a caching and pre-fetch function of a device driver that selective pre-fetches and caches data stored in disk blocks to facilitate operation with a file system having file clusters with a cluster size greater than an underlying operating system's memory page size, and a second plurality of programming instructions to be executed by the execution unit for implementing a disk block allocation optimization function to generate a new set of disk blocks to reallocate disk blocks for file system clusters accessed by a sequence of file accesses of interest, such that overall access time for these file system clusters will be improved, accounting for the selective pre-fetches and caching to be performed to accommodate said file system.

Claim 2

Independent Claim 157 words

An apparatus comprising (a) an execution unit for executing programming instructions; and (b) a storage medium coupled to the execution unit and having stored therein a first plurality of programming instructions to be executed by the execution unit for implementing a caching and pre-fetch function of a device driver that selective pre-fetches and caches data stored in disk blocks to facilitate operation with a file system having file clusters with a cluster size greater than an underlying operating system's memory page size, and a second plurality of programming instructions to be executed by the execution unit for implementing a disk block allocation optimization function to generate a new set of disk blocks to reallocate disk blocks for file system clusters accessed by a sequence of file accesses of interest, such that overall access time for these file system clusters will be improved, accounting for the selective pre-fetches and caching to be performed to accommodate said file system.

Claim 3

Dependent Claim 92 words

The apparatus as set forth in claim 1 , wherein the disk block allocation optimization function includes first logic for nominally tracing disk block accesses resulted from said sequence of file accesses of interest, without accounting for said selective pre-fetches performed to accommodate said file system, second logic for deducing actual disk block accesses resulted from said sequence of file accesses of interest with said selective pre-fetches being performed to accommodate said file system, and third logic for analyzing the deduced disk block accesses, and generating the new set of disk blocks.

Claim 4

Dependent Claim 32 words

The apparatus as set forth in claim 1 , wherein the second logic includes a simulator for simulating disk block accesses with said selective pre-fetches being performed to accommodate said file system.

Claim 5

Dependent Claim 37 words

The apparatus as set forth in claim 1 , wherein the third logic includes logic for generating a remapping vector mapping the disk blocks of the file system clusters accessed to the new set of disk blocks.

Claim 6

Dependent Claim 45 words

The apparatus as set forth in claim 4 , wherein the data block allocation optimization function further includes fourth logic for relocating data stored in the disk blocks of the file system clusters accessed to the new set of disk blocks using the remapping vector.

Claim 7

Dependent Claim 43 words

The apparatus as set forth in claim 1 , wherein the disk block allocation optimization function is packaged as a standalone utility that can be invoked by a user at will to optimize disk block allocation of any arbitrary sequence of file accesses.

Claim 8

Dependent Claim 49 words

The apparatus as set forth in claim 1 , wherein the disk block allocation optimization function is packaged as an integral part of an application for optimizing disk block allocations for disk blocks of file system clusters accessed by file accesses of the application during start-up of the application.

Claim 9

Dependent Claim 16 words

The apparatus as set forth in claim 1 , wherein the apparatus is a computer system.

Claim 10

Dependent Claim 43 words

The apparatus as set forth in claim 2 , wherein the third logic employs a model to model the actual disk block accesses made against the disk blocks of the file clusters, and a plurality of model pruning criteria to prune the model.

Claim 11

Dependent Claim 58 words

The apparatus as set forth in claim 2 , wherein the first logic is packaged as an integral part of said underlying operating system and the second logic is packaged as a standalone complementary function for optimizing disk block allocations for disk blocks of file system clusters accessed by file accesses of the operating system during start-up/boot time.

Claim 12

Dependent Claim 42 words

The apparatus as set forth in claim 9 , wherein the third logic models the actual disk block accesses using nodes and transition arcs joining the nodes to represent atomic allocation units accessed and access orders of the atomic allocation units accessed.

Claim 13

Dependent Claim 48 words

The apparatus as set forth in claim 11 , wherein the third logic assigns a node to represent each file cluster accessed, a transition arc joining two assigned nodes to represent a successive access relationship between the two represented file clusters, and a weight to each transition arc.

Claim 14

Independent Claim 40 words

The apparatus as set forth in claims 9 , wherein the model pruning criteria employed by the third logic includes a model pruning criteria of conditionally eliminating a forward rejoining transition arc in accordance with a device characteristic based condition.

Claim 15

Dependent Claim 42 words

The apparatus as set forth in claim 13 , wherein the third logic eliminates a forward rejoining transition arc if the forward rejoining transition arc has an arc length that is shorter than a pre-fetch size of a class of storage device.

Claim 16

Dependent Claim 50 words

The apparatus as set forth in claim 9 , wherein the model pruning criteria employed by the third logic includes a model pruning criteria of conditionally serializing a selected one of a plurality of parallel strings of nodes emanating from a node in accordance with a device characteristic based condition.

Claim 17

Dependent Claim 49 words

The apparatus as set forth in claim 15 , wherein the reallocation optimizer selects a parallel string of nodes emanating from the node to be serialized if the parallel string of nodes has a string length that is shorter than a pre-fetch size of a class of storage device.

Claim 18

Dependent Claim 47 words

The apparatus as set forth in claim 15 , wherein the third logic serializes the selected parallel string of nodes emanating from the node by placing the selected parallel string of nodes in between the node and the longest parallel string of nodes emanating from the node.

Claim 19

Dependent Claim 49 words

The apparatus as set forth in claim 9 , wherein the model pruning criteria employed by the third logic includes a model pruning criteria of conditionally serializing a selected one of a plurality of parallel strings of nodes joining a node in accordance with a device characteristic based condition.

Claim 20

Dependent Claim 48 words

The apparatus as set forth in claim 18 , wherein the third logic selects a parallel string of nodes joining the node to be serialized if the parallel string of nodes has a string length that is shorter than a pre-fetch size of a class of storage device.

Claim 21

Dependent Claim 45 words

The apparatus as set forth in claim 18 , wherein the third logic serializes the selected parallel string of nodes joining the node by placing the selected parallel string of nodes in between the longest parallel string of nodes joining the node and the node.

Claim 22

Dependent Claim 33 words

The apparatus as set forth in claim 9 , wherein the model pruning criteria employed by the third logic includes a model pruning criteria of eliminating a cycle forming backward rejoining transition arc.

Claim 23

Dependent Claim 46 words

The apparatus as set forth in claim 9 , wherein the model pruning criteria employed by the third logic includes a model pruning criteria of eliminating all less probable transition arcs emanating from a node, keeping only the most probable transition arc emanating from the node.

Claim 24

Dependent Claim 44 words

The apparatus as set forth in claim 9 , wherein the model pruning criteria employed by the third logic includes a model pruning criteria of eliminating all less probable transition arcs joining a node, keeping only the most probable transition arc joining the node.

Claim 25

Dependent Claim 129 words

A machine implemented method comprising: nominally tracing disk blocks accesses resulted from a sequence of file accesses of interest, without accounting for selective pre-fetches and caching performed to facilitate operation with a file system having file clusters with a cluster size greater than an underlying operating system's memory page size; deducing actual disk block accesses resulted from said sequence of file accesses of interest accounting for said selective pre-fetches and caching to be performed to accommodate said file system; and analyzing the deduced actual disk block accesses, and generating a new set of disk blocks to reallocate disk blocks for the file system clusters accessed such that overall access time for these file system clusters will be improved, based at least in part on the results of said analysis.

Claim 26

Dependent Claim 129 words

A machine implemented method comprising: nominally tracing disk blocks accesses resulted from a sequence of file accesses of interest, without accounting for selective pre-fetches and caching performed to facilitate operation with a file system having file clusters with a cluster size greater than an underlying operating system's memory page size; deducing actual disk block accesses resulted from said sequence of file accesses of interest accounting for said selective pre-fetches and caching to be performed to accommodate said file system; and analyzing the deduced actual disk block accesses, and generating a new set of disk blocks to reallocate disk blocks for the file system clusters accessed such that overall access time for these file system clusters will be improved, based at least in part on the results of said analysis.

Claim 27

Dependent Claim 30 words

The method as set forth in claim 24 , wherein deducing comprises simulating said nominally traced disk block accesses with said selective pre-fetches being performed to accommodate said file system.

Claim 28

Dependent Claim 34 words

The method as set forth in claim 24 , wherein said generating comprises generating a remapping vector mapping the disk blocks of the file system clusters accessed to the new set of disk blocks.

Claim 29

Dependent Claim 38 words

The method as set forth in claim 26 , wherein said method further comprises relocating data stored in the disk blocks of the file system clusters accessed to the new set of disk blocks using the remapping vector.

Claim 30

Dependent Claim 43 words

The method as set forth in claim 24 , wherein said analyzing comprises employing a model to model the actual disk block accesses made against the disk blocks of the file clusters, and a plurality of model pruning criteria to prune the model.

Claim 31

Dependent Claim 42 words

The method as set forth in claim 28 , wherein said analyzing comprises modeling the actual disk block accesses using nodes and transition arcs joining the nodes to represent atomic allocation units accessed and access orders of the atomic allocation units accessed.

Claim 32

Dependent Claim 48 words

The method as set forth in claim 29 , wherein said modeling comprises assigning a node to represent each file cluster accessed, a transition arc joining two assigned nodes to represent a successive access relationship between the two represented file clusters, and a weight to each transition arc.

Claim 33

Dependent Claim 36 words

The method as set forth in claim 28 , wherein the model pruning criteria employed includes a model pruning criteria of conditionally eliminating a forward rejoining transition arc in accordance with a device characteristic based condition.

Claim 34

Dependent Claim 46 words

The apparatus as set forth in claim 28 , wherein the model pruning criteria employed includes a model pruning criteria of conditionally serializing a selected one of a plurality of parallel strings of nodes emanating from a node in accordance with a device characteristic based condition.

Claim 35

Dependent Claim 45 words

The method as set forth in claim 28 , wherein the model pruning criteria employed includes a model pruning criteria of conditionally serializing a selected one of a plurality of parallel strings of nodes joining a node in accordance with a device characteristic based condition.

Claim 36

Dependent Claim 29 words

The method as set forth in claim 28 , wherein the model pruning criteria employed includes a model pruning criteria of eliminating a cycle forming backward rejoining transition arc.

Claim 37

Dependent Claim 42 words

The method as set forth in claim 28 , wherein the model pruning criteria employed includes a model pruning criteria of eliminating all less probable transition arcs emanating from a node, keeping only the most probable transition arc emanating from the node.

Claim 38

Dependent Claim 40 words

The method as set forth in claim 28 , wherein the model pruning criteria employed includes a model pruning criteria of eliminating all less probable transition arcs joining a node, keeping only the most probable transition arc joining the node.

Claim 39

Dependent Claim 143 words

An article of manufacture comprising a recordable medium having recorded thereon a first plurality of programming instructions for programming an apparatus to provide the apparatus with a caching and pre-fetch function of a device driver that selectively pre-fetches and caches data stored in disk blocks to facilitate operation with a file system having file clusters with a cluster size greater than an underlying operating system's memory page size, and a second plurality of programming instructions for programming the apparatus to provide the apparatus with a disk block allocation optimization function to generate a new set of disk blocks to reallocate disk blocks for file system clusters accessed by a sequence of file accesses of interest, such that overall access time for these file system clusters will be improved, accounting for the selective pre-fetches and caching to be performed to accommodate said file system.

Claim 40

Dependent Claim 143 words

An article of manufacture comprising a recordable medium having recorded thereon a first plurality of programming instructions for programming an apparatus to provide the apparatus with a caching and pre-fetch function of a device driver that selectively pre-fetches and caches data stored in disk blocks to facilitate operation with a file system having file clusters with a cluster size greater than an underlying operating system's memory page size, and a second plurality of programming instructions for programming the apparatus to provide the apparatus with a disk block allocation optimization function to generate a new set of disk blocks to reallocate disk blocks for file system clusters accessed by a sequence of file accesses of interest, such that overall access time for these file system clusters will be improved, accounting for the selective pre-fetches and caching to be performed to accommodate said file system.

Claim 41

Dependent Claim 126 words

The article of manufacture of claim 37 , wherein the disk block allocation optimization function includes first logic for nominally tracing disk blocks accesses resulted from said sequence of file accesses of interest, without accounting for said selective pre-fetches performed to accommodate said file system, second logic for deducing actual disk block accesses resulted from said sequence of file accesses of interest with said selective pre-fetches being performed to accommodate said file system and third logic for analyzing the deduced actual disk block accesses, and generating a new set of disk blocks to reallocate disk blocks for the file system clusters accessed such that overall access time for these file system clusters will be improved, based at least in part on the results of said analysis.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2005-08-12	2006-02-11	2006-08-13	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2009-08-12	2010-02-11	2010-08-13	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2013-08-12	2014-02-11	2014-08-13	$7700.00	Window Closed / Lapsed

Disk block allocation optimization methodology with accommodation for file system cluster size greater than operating system memory page size

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag