Real-time apparatus and method for minimizing disk fragmentation in a computer system

• US 5,930,828 A
• Filed: 03/26/1997
• Issued: 07/27/1999
• Est. Priority Date: 03/26/1997
• Status: Expired due to Term

• Current Assignee: GQRC Technologies LLC
• Original Assignee: Executive Software International, Inc.
• Inventors: Jensen, Craig Charles, Staffer, Andrew C.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): GOODARZI, NASSER MOAZZAMI
• Application Number:
  US08/824,036
• Time in Patent Office: 853 Days
• Field of Search: 711/170, 707/205, 707/103, 707/206, 707/1, 360/48
• US Class Current: 711/170
• CPC Class Codes: G06F 16/1724 Details of de-fragmentation performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 2206/1004 Defragmentation
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The present invention relates to an apparatus and method for defragmenting a disk drive in a computer system. The defragmentation process, in accordance with the present invention, determines which files have a high degree of fragmentation, where such file extents are to be physically moved on the disk and further determines which portions of such files are to be moved to the selected physical location. More particularly, the defragmentation process selects each file on the disk, checks to see if the file is excluded from processing and, if not, recovers the extent list for the file. If the file is fragmented, the process determines if there is sufficient free space in which to move the file extents to contiguous location on the disk. If such as space exists, the file extents are moved. If the free space is sufficiently fragmented or the disk is substantially full, contiguous files are moved to contiguous locations so as to partially defragment the file. If the file is already contiguous or if there is insufficient free space available to partially defragment the fragmented files, the process of the present invention moves the files or the file extents so as to maximize contiguous free space on the disk. The process then repeats so as to further defragment files that were previously left fragmented. In this manner fragmented files and fragmented free space on the disk are made contiguous. Files are then moved toward the front of the disk where possible. When the fragmentation process is complete, contiguous files tend to be packed toward the front of the disk with defragmented free space tending to be located toward the end of the disk.

Claims

1. In a computer system comprising a processor, an address/data bus coupled to said processor;

a computer readable memory coupled to communicate with said processor, a method performed by said processor for defragmenting a random access storage device where information is stored in files, and where information regarding the location of the files is contained in a master file table stored in a master file zone, the method comprising the steps of;

invoking a first process flow to select a fragmented file having a plurality of non-contiguous extents and moving each extent toward the front of the disk thereby tending to pack files near the beginning of the disk and creating free space toward the end of the disk, said first process flow further comprises the steps of;

identifying a fragmented file having a plurality of non-contiguous extents;

moving the file extents to a contiguous free space on the storage device that is closer to the beginning of the disk than the current file location of the first extent of the fragmented file;

moving the file extents toward the end of the disk if contiguous free space is unavailable closer the beginning of the disk than the current file location of the first extent of the fragmented file so as to at least partially defragment the fragmented file, said step of moving the file extents toward the end of the disk occurring when the contiguous free space is no smaller than the square root of the total number of clusters in the fragmented file so as to at least partially defragment the fragmented file;

invoking a second process flow to select fragmented and contiguous files and moving the files toward the beginning of the disk;

repeating the first and second process flow so as to further minimize file fragmentation and pack contiguous files toward the beginning of the storage device;

invoking a third process flow to move fragmented files and contiguous files from the master file table zone to free space; and

invoking the second process flow to move files toward the beginning of the storage device.

2. The method as recited in claim 1 wherein the processor performed first process flow further comprises the step of moving file extents toward the end of the storage device if the free space is unavailable toward the front of the storage device.

3. The method as recited in claim 1 wherein the processor performed first process flow further comprises the step of selecting files located toward the front of the storage device and proceeding thereafter to select files located toward the end of the storage device.

4. The method as recited in claim 1 wherein the processor performed second process flow further comprises the step of proceeding from the rear of the storage device toward the beginning of the storage device so as to pack files toward the beginning of the storage device into the free space created after the first process flow.

5. The method as recited in claim 1 wherein the processor performed third process flow further comprises the step of searching for free space beginning at the beginning of the storage device and proceeding to the end of the storage device until sufficient contiguous free space is located to move at least one of the fragmented files or at least one of the contiguous files from the master file table zone to the free space.

6. The method as recited in claim 1 wherein the processor performed identifying step further includes the steps of:

recovering the master file table from the random access storage device;

sorting the master file table to align the file records to coincide with the files are stored on the random access storage device

testing each file record to determine whether the corresponding file is contiguous or fragmented;

searching for contiguous free space between the beginning of the disk and the beginning of the master file table zone sufficient to contiguously store substantially all extents of the file corresponding to the current file record; and

moving the file extents to the contiguous free space.

7. The method as recited in claim 1 wherein the processor performed first process flow further comprises the steps of:

searching for free space between the end of the storage device and the middle of the storage device sufficient to store all fragments of the file corresponding to the current file record; and

searching for free space between the end of the storage device and the middle of the storage device sufficient to store at least two of the extents of the file corresponding to the current file record and

moving the at least two file extents to the contiguous free space.

8. The method as recited in claim 1 wherein the processor performed second process flow further comprises the steps of:

searching the storage device for fragmented files and contiguous files located proximate to the end of the storage drive and proceeding to fragmented files and contiguous files located proximate to the beginning of the storage device;

searching the storage device for contiguous free space of sufficient size between the file'"'"'s current location and the beginning of the disk in which to contiguously store at least two extents of the fragmented files or at least one of the contiguous files; and

moving the at least two extents of the fragmented file or the contiguous file to the contiguous free space.

9. The method as recited in claim 8 wherein the processor performed step of searching for free space excludes free space within the master file zone.

10. The method as recited in claim 1 wherein the processor performed third process flow further comprises the steps of:

locating and selecting one of the fragmented files and contiguous files stored in the master file table zone;

searching for contiguous free space, outside of the master file table zone of sufficient size to at least move either a portion of the selected fragmented file or the selected contiguous file; and

repeating the locating and searching steps until substantially all fragmented files and substantially all contiguous files in the master file table zone have been selected.

11. A computer-usable medium having computer readable program code embodied therein for causing a computer to perform the steps of:

invoking a first process flow where contiguous and non-contiguous files are moved toward the beginning of the storage device so as to pack the files and file extents toward the beginning of the storage device and creating contiguous free space toward the end of the storage device;

invoking a second process flow to move files from the end of the storage device toward the beginning of the storage device, said second process flow tending to defragment file extents, said second process flow further comprising the steps of;

selecting each of the files stored on the storage device beginning with files located near the end of the storage device and proceeding toward files located toward the beginning of the storage device;

searching the storage device for free space of sufficient size between the file'"'"'s current location and the beginning of the disk;

moving the selected file to the free space if the free space is sufficient to locate the entire file in a contiguous locations; and

repeating the selecting, searching and moving steps until the front of the disk is reached;

repeating the first and second process flow so as to further minimize file fragmentation and pack contiguous files toward the beginning of the storage device;

invoking a third process flow to select fragmented files and move each fragment of said files toward the front of the storage device to create free space toward the end of the disk if no space is available toward the front of the storage device to at least partially defragment the file; and

invoking the second process flow to move files toward the beginning of the storage device.

12. The computer-usable medium as recited in claim 11 wherein said computer-readable program code embodied therein causes a computer performing the first process flow to further perform the steps of:

selecting each of files stored on the storage device beginning with files located near the beginning of the storage device and proceeding toward files located toward the end of the storage device;

moving file extents and contiguous files to a location on the storage device that is closer to the beginning of the storage device than the current file location so as to pack the files toward the front of the storage device when sufficient contiguous free space exists between the current file location and the beginning of the storage device;

searching for contiguous free space between the end of the storage device and the beginning of the file;

moving file extents to the contiguous free space so as to make the file extents at least partially contiguous;

moving each of the contiguous files from its respective current location on the storage device to a location closer to the beginning of the storage device if sufficient free space is available; and

searching for contiguous free space between the middle and the end of the storage device and moving file extents, whether contiguous or not, to the contiguous free space.

13. The computer-usable medium as recited in claim 11 wherein said computer-readable program code embodied therein causes a computer performing the third process flow to further perform the steps of:

selecting each of the files stored on the storage device beginning with files located at the beginning of the disk and proceeding toward the end of the storage device;

moving fragmented and contiguous files to a position on the storage device that is closer to the beginning of the disk than the current file location; and

searching the storage device for free space of sufficient size between the file'"'"'s current location and the end of the storage device to at least partially defragment the fragmented files by moving at least a portion of the file extents or the entire file to the free space.

14. In a computer system, a method for defragmenting a disk drive having a plurality of clusters of storage locations arranged in a sequential manner, said drive capable of storing a plurality of files where each of said plurality of files are stored in at least one cluster of the plurality of clusters of storage locations, said method comprising the steps of:

beginning at a first end of said disk drive and proceeding to about the middle of said disk drive, identifying files stored on said disk drive in either one or at least two contiguous clusters, said identifying step further comprising the steps of;

identifying files stored on said disk drive in at least two non-contiguous clusters; and

moving said files stored in said at least two non-contiguous clusters to at least two contiguous clusters proximate to said second end of said disk drive;

determining whether each of said identified file abuts at least one cluster of free space;

moving said identified file to free space proximate to a second end of said disk drive if said the beginning storage location of the identified file abuts at least one cluster of free space;

repeating said identifying, determining and moving steps; and

moving files proximate said second end of said disk toward the beginning of disk drive so as to eliminate clusters of free space between adjacent files stored on said disk drive.

15. The method of claim 14 wherein the identifying step further comprises the steps of:

identifying files stored on said disk drive in at least three non-contiguous clusters; and

moving a portion of the file stored on said disk to free space that is no smaller than the square root of the total number of clusters comprising said identified file.