Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1995-05-22
2002-05-28
Banankhah, Majid (Department: 2151)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S170000, C709S241000
Reexamination Certificate
active
06397311
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates in general to computers and more particularly the present invention relates to a system and method for defragmenting a file system.
BACKGROUND OF THE INVENTION
As files are created and deleted in a file system such as, for example, a file system created in the UNIX operating system, the files and the free space on the disk space become fragmented. This fragmentation means that an individual file does not reside in a contiguous region of the disk but rather is broken up into many pieces of the disk. When a program tries to access a fragmented file, additional movement of the disk read/write head to another location on the disk is required, resulting in reduced performance.
The defragmentation process rearranges the file segments and free space on the disk so that each file resides in a contiguous region on the disk. There are two common methods for defragmenting a UNIX file system. The first of these methods comprises copying all of the files to another medium, such as a tape drive. After the files are copied, they are then deleted from the file system. A standard utility program may then be run to rebuild the list of free space on the disk. The files are then copied back onto the file system such that each file resides in contiguous regions of the disk space. This method is effective, but has several important drawbacks. If a tape drive is used, the method is cumbersome as it requires a person to be present to handle the tapes if the files in the file system will not all fit on one tape. If a disk is used for the intermediate storage medium, the method is faster and can be automated so that no person's presence is required. However, this is an extremely expensive solution as it requires a large amount of free space on the disk used as the intermediate storage medium.
The second method concentrates on one file at a time and rearranges the disk until that file resides in contiguous regions of the disk. This method does not require an intermediate storage medium such as the previous method, but is itself rather slow because of the extensive data movement required.
Therefore, a need has arisen for a system and method for defragmenting a file system which does not require a separate tape drive or disk for an intermediate storage medium but which efficiently rearranges the file blocks in the file system such that they reside in contiguous regions of the disk space. A further need has arisen for a system and method for defragmenting a file system which is secure in that loss of power during the defragmentation process will not result in loss of data integrity.
SUMMARY OF THE INVENTION
In accordance with the present invention, a method for defragmenting a file system is provided which substantially eliminates or reduces disadvantages associated with prior systems and methods. A first contiguous portion of the file system comprising a first plurality of blocks is read into a storage circuit. The first plurality of blocks is then written into free space within the file system. A second plurality of blocks for contiguous placement in the file system is then read from the file system into the storage circuit. The second plurality of blocks is then written into the first contiguous portion of the file system. These steps are repeated until the entire file system is defragmented.
In accordance with another aspect of the method of the present invention, a block descriptor array is created which contains information identifying the location of each pointer to each block within the file system. This block descriptor array is maintained as blocks containing pointers are moved during the defragmentation process. In this manner, the system and method of the present invention always has access to a map of the entire file system.
In accordance with another aspect of the present invention, an inode cache circuit and an indirect cache circuit are used to store inode blocks and indirect blocks which contain more than one pointer which must be updated during a single cycle during the defragmentation process. In this manner, multiple pointers can be repaired in memory prior to writing the entire inode or indirect block onto the disk. Accordingly, multiple write cycles are saved and the method of the present invention proceeds more quickly.
An important technical advantage of the present invention inheres in the fact that data blocks or indirect blocks are always written to the disk space prior to the alteration of the pointers pointing to those blocks. In this manner, the method of the present invention is secure from possible power failure during the defragmentation process.
REFERENCES:
patent: 4037205 (1977-07-01), Edelberg et al.
patent: 4390945 (1983-06-01), Olsen et al.
patent: 4742447 (1988-05-01), Duvall et al.
patent: 4761737 (1988-08-01), Duvall et al.
patent: 4771375 (1988-09-01), Beglin et al.
patent: 4821185 (1989-04-01), Esposito
patent: 4833604 (1989-05-01), Cheng et al.
patent: 4907151 (1990-03-01), Bartlett
patent: 4959771 (1990-09-01), Ardini, Jr. et al.
patent: 5021946 (1991-06-01), Korty
patent: 5276867 (1994-01-01), Kenley et al.
patent: 5287504 (1994-02-01), Carpenter et al.
patent: 5398142 (1995-03-01), Davy
McDonald et al, Improving File System Performance by Dynamically Restructuring Disk Space, Computers and Comm., 1989 Int'l Phoenix Conf.
Brady W. James
Swayze, Jr. W. Daniel
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
System and method for defragmenting a file system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for defragmenting a file system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for defragmenting a file system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2824366