US5920896A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Reducing operating system start-up/boot time through disk block relocation
Assignee: Intel Corp
•
Filing: 1997-03-21
•
Granted: 1999-07-06
•
Expires: 2017-03-21
Abstract
Abstract A computer system is equipped with an operating system having a tracer driver for generating trace data including disk locations accessed for disk accesses made by various components of the operating system during system startup/boot time. The tracer driver is loaded at an initial phase of system start-up. The computer system is further equipped with a companion disk block relocation driver for generating, if possible, an alternative disk block allocation for a current disk block allocation that will yield improved overall access time for a sequence of disk accesses. In some embodiments, the disk block relocation driver includes logic for tracing the sequence of disk accesses to determine the current disk block allocation, logic for generating the alternative disk block allocation, if possible, using the trace results, and logic for effectuating the alternate disk block allocation, if generated. In one particular embodiment, the logic for generating the alternative disk block allocation employs a random search approach, while in another embodiment, the logic for generating the alternative disk block allocation employs a heuristic approach.
Inventors
- 👤 Knut Grimsrud
- 👤 Rick Coulson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 11:49
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0604; G06F3/0605; G06F11/00; G06F11/30; G06F11/34; G06F11/3466; G06F11/3485; G06F3/0628; G06F3/0629; G06F3/0632; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0674; G11; G11B; G11B27/00; G11B27/02; G11B27/031; G11B27/034; G06F11/3409; G06F11/3419
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
180 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 during system start-up for implementing a plurality of operating system functions, including a tracer function to be loaded at an initial loading phase during system start-up for generating trace data including disk locations accessed and the order the disk locations are accessed for a sequence of disk accesses made to subsequently load one or more of the other operating system functions during said system start-up, and a second plurality of programming instructions to be executed by the execution unit after said system start-up for implementing a disk block relocation utility for analyzing the trace data generated during said system start-up, and generating a new set of disk locations to reallocate the accessed disk locations such that overall access time will be improved, the new set of disk locations being generated in accordance with at least the order the disk locations are accessed.
Claim 2
Independent Claim
180 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 during system start-up for implementing a plurality of operating system functions, including a tracer function to be loaded at an initial loading phase during system start-up for generating trace data including disk locations accessed and the order the disk locations are accessed for a sequence of disk accesses made to subsequently load one or more of the other operating system functions during said system start-up, and a second plurality of programming instructions to be executed by the execution unit after said system start-up for implementing a disk block relocation utility for analyzing the trace data generated during said system start-up, and generating a new set of disk locations to reallocate the accessed disk locations such that overall access time will be improved, the new set of disk locations being generated in accordance with at least the order the disk locations are accessed.
Claim 3
Dependent Claim
29 words
The apparatus as set forth in claim 1, wherein the tracer function logs the access data into a buffer until the disk block relocation utility retrieves the logged data.
Claim 4
Dependent Claim
33 words
The apparatus as set forth in claim 1, wherein the disk block relocation utility includes logic for generating a remapping vector mapping the disk locations accessed to the new set of disk locations.
Claim 5
Dependent Claim
33 words
The apparatus as set forth in claim 3, wherein the disk block relocation utility includes logic for relocating the disk locations accessed to the new set of disk locations using the remapping vector.
Claim 6
Dependent Claim
41 words
The apparatus as set forth in claim 1, wherein the disk block relocation utility includes logic for optimizing a cost function of overall access time which is functionally dependent on disk locations accessed, to generate the new set of disk locations.
Claim 7
Dependent Claim
40 words
The apparatus as set forth in claim 5, wherein the disk block relocation utility includes logic for generating a new set of disk locations, and determining if the generated new set of disk locations yields improvement in overall access time.
Claim 8
Dependent Claim
45 words
The apparatus as set forth in claim 6, wherein the disk block relocation utility includes logic for repeating the generation of an arbitrary set of disk locations, and the determination of whether the generated arbitrary set of disk locations yields improvement on overall access time.
Claim 9
Dependent Claim
24 words
The apparatus as set forth in claim 5, wherein the disk block relocation utility includes logic for coalescing disk blocks of a disk drive.
Claim 10
Dependent Claim
24 words
The apparatus as set forth in claim 5, wherein the disk block relocation utility includes logic for grouping the disk accesses into access runs.
Claim 11
Dependent Claim
31 words
The apparatus as set forth in claim 9, wherein the disk block relocation utility includes logic for generating new disk locations for the disk locations accessed by the various access runs.
Claim 12
Dependent Claim
44 words
The apparatus as set forth in claim 10, wherein the disk block relocation utility includes logic for generating new disk locations from top most portions of a disk region in a top down manner for access runs having run lengths of a particular type.
Claim 13
Dependent Claim
44 words
The apparatus as set forth in claim 10, wherein the disk block relocation utility includes logic for generating new disk locations from bottom most portions of a disk region in a bottom up manner for access runs having run lengths of a particular type.
Claim 14
Dependent Claim
59 words
The apparatus as set forth in claim 10, wherein the disk block relocation utility includes logic for alternatingly generating new disk locations from top most portions of a disk region in a top down manner and from bottom most portions of the disk region in a bottom up manner for access runs having run length of a particular type.
Claim 15
Dependent Claim
38 words
The apparatus as set forth in claim 10, wherein the disk block relocation utility includes logic for generating new disk locations from center portions of a disk region for access runs having run lengths of a particular type.
Claim 16
Dependent Claim
55 words
The apparatus as set forth in claim 14, wherein the disk block relocation utility for generating new disk locations from center portions of a disk region for access runs having run lengths of a particular type, generates the new disk locations factoring into consideration likelihood of occurrence of interrelated access runs of the same type.
Claim 17
Dependent Claim
123 words
A machine implemented method comprising the steps of: a) loading a tracer function incorporated as an integral part of an operating system at an initial phase during system start-up, and using the loaded tracer function to trace a sequence of disk accesses made to subsequently load one or more other operating system functions during said system start-up, and generating trace data for the disk accesses traced including disk locations accessed and the order the disk locations are accessed; b) generating after said system start-up a new set of disk locations that yield improvement on overall access time, over the disk locations accessed, the new set of disk locations being generated in accordance with at least on the order the disk locations are accessed.
Claim 18
Dependent Claim
123 words
A machine implemented method comprising the steps of: a) loading a tracer function incorporated as an integral part of an operating system at an initial phase during system start-up, and using the loaded tracer function to trace a sequence of disk accesses made to subsequently load one or more other operating system functions during said system start-up, and generating trace data for the disk accesses traced including disk locations accessed and the order the disk locations are accessed; b) generating after said system start-up a new set of disk locations that yield improvement on overall access time, over the disk locations accessed, the new set of disk locations being generated in accordance with at least on the order the disk locations are accessed.
Claim 19
Dependent Claim
46 words
The method as set forth in claim 16, wherein the method further includes the step of (c) generating a remapping vector mapping the disk locations accessed to the new set of disk locations, if step (b) was successful in generating the new set of disk locations.
Claim 20
Dependent Claim
39 words
The machine implemented method as set forth in claim 17, wherein the method further includes the step (d) relocating the disk locations accessed to the new set of disk locations using the remapping vector, if step (c) was performed.
Claim 21
Dependent Claim
30 words
The machine implemented method as set forth in claim 16, wherein step (b) includes optimizing a cost function of overall access time which is functionally dependent on disk locations accessed.
Claim 22
Dependent Claim
42 words
The machine implemented method as set forth in claim 19, wherein the cost function optimization of step (b) includes generating a new set of disk locations, and determining if the generated arbitrary set of disk locations yields improvement on overall access time.
Claim 23
Dependent Claim
48 words
The machine implemented method as set forth in claim 20, wherein the cost function optimization of step (b) further includes repeating the generation of an arbitrary set of disk locations, and the determination of whether the generated arbitrary set of disk locations yields improvement on overall access time.
Claim 24
Dependent Claim
22 words
The machine implemented method as set forth in claim 19, wherein step (b) further includes coalescing disk blocks of a disk drive.
Claim 25
Dependent Claim
22 words
The machine implemented method as set forth in claim 19, wherein step (b) further includes grouping the disk accesses into access runs.
Claim 26
Dependent Claim
37 words
The machine implemented method as set forth in claim 23, wherein the generation of new disk locations for the disk locations accessed of step (b) is performed by generating new disk locations for the various access runs.
Claim 27
Dependent Claim
48 words
The machine implemented method as set forth in claim 24, wherein the generation of new disk locations of step (b) includes generating new disk locations from top most portions of a disk region in a top down manner for access runs having run lengths of a particular type.
Claim 28
Dependent Claim
48 words
The machine implemented method as set forth in claim 24, wherein the generation of new disk locations of step (b) includes generating new disk locations from bottom most portions of a disk region in a bottom up manner for access runs having run lengths of a particular type.
Claim 29
Dependent Claim
63 words
The machine implemented method as set forth in claim 24, wherein the generation of new disk locations of step (b) includes alternatingly generating new disk locations from top most portions of a disk region in a top down manner and from bottom most portions of the disk region in a bottom up manner for access runs having run length of a particular type.
Claim 30
Dependent Claim
42 words
The machine implemented method as set forth in claim 24, wherein the generation of new disk locations of step (b) includes generating new disk locations from center portions of a disk region for access runs having run lengths of a particular type.
Claim 31
Dependent Claim
49 words
The machine implemented method as set forth in claim 28, wherein the generation of new disk locations from center portions of a disk region for access runs having run lengths of a particular type, includes factoring into consideration likelihood of occurrence of interrelated access runs of the same type.
Claim 32
Dependent Claim
157 words
A storage medium having stored therein a first plurality of programming instructions to be executed by an execution unit during a system start-up for implementing a plurality of operating system functions, including a tracer function to be loaded at an initial phase of said system start-up for generating trace data including disk locations accessed and the order the disk locations are accessed for a sequence of disk accesses made to subsequently load one or more of other operating system functions during said system start-up, and a second plurality of programming instructions, to be executed by an execution unit after said system start-up, for implementing a disk block relocation utility for analyzing the generated trace data, and generating a new set of disk locations to reallocate the accessed disk locations such that overall access time will be improved, the new set of disk locations being generated in accordance with at least the order the disk locations are accessed.
Claim 33
Dependent Claim
157 words
A storage medium having stored therein a first plurality of programming instructions to be executed by an execution unit during a system start-up for implementing a plurality of operating system functions, including a tracer function to be loaded at an initial phase of said system start-up for generating trace data including disk locations accessed and the order the disk locations are accessed for a sequence of disk accesses made to subsequently load one or more of other operating system functions during said system start-up, and a second plurality of programming instructions, to be executed by an execution unit after said system start-up, for implementing a disk block relocation utility for analyzing the generated trace data, and generating a new set of disk locations to reallocate the accessed disk locations such that overall access time will be improved, the new set of disk locations being generated in accordance with at least the order the disk locations are accessed.
Claim 34
Dependent Claim
42 words
The storage medium as set forth in claim 30, wherein the disk block relocation utility includes logic for optimizing a cost function of overall access time, which is functionally dependent on disk locations accessed, to generate the new set of disk locations.
Claim 35
Dependent Claim
41 words
The storage medium as set forth in claim 31, wherein the disk block relocation utility includes logic for generating a new set of disk locations, and determining if the generated new set of disk locations yields improvement in overall access time.
Claim 36
Dependent Claim
46 words
The storage medium as set forth in claim 32, wherein the disk block relocation utility includes logic for repeating the generation of an arbitrary set of disk locations, and the determination of whether the generated arbitrary set of disk locations yields improvement in overall access time.
Claim 37
Dependent Claim
25 words
The storage medium as set forth in claim 31, wherein the disk block relocation utility includes logic for coalescing disk blocks of a disk drive.
References Cited (Backward Citations)
US5787296A
Cited
US5802593A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-05 | 2003-01-04 | 2003-07-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-05 | 2007-01-04 | 2007-07-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-05 | 2011-01-04 | 2011-07-06 | $7700.00 | Window Closed / Lapsed |