Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-07-11
2003-05-13
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S112000, C711S113000, C711S171000, C711S172000, C710S052000, C710S056000
Reexamination Certificate
active
06564292
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data storage in computer systems, and more particularly to optimizing the allocation of sectors for storage of audio and/or video data on magnetic discs.
BACKGROUND OF THE INVENTION
Magnetic discs are commonly used to store programs and data in computer systems, and in some computer-based consumer products. The discs are divided into physical sectors. A sector is a portion of a track on the disc, and represents the minimum physical storage unit on the disc. Sectors are commonly grouped together to form “blocks”. Each block contains an integer number of sectors, and represents the minimum logical storage unit for a disc. Data is read from, or written to, a disc using a whole number of blocks. Block sizes are usually small in order to minimize wastage of memory space in disc blocks that are only partially filled.
When data is written to a disc, the file system normally attempts to allocate the data to blocks in sequential order, so that the writing and reading of the data can be performed efficiently, that is, with minimum movement of the read/write head. However, with subsequent deletion or modification of existing data files and writing of new data files, the blocks available for storage of data may no longer be contiguous. Consequently, a single data file may be stored in sectors in many different portions of the disc. Such fragmentation of data files is a common problem in computer systems.
Computer systems are now commonly used to store and process audio and video information in digital form. The rate at which audio and/or visual information is transferred to/from the disc drive of a computer system affects the system's overall performance. Particularly for audio and video applications, the processing of such audio/video information is time-critical, and sluggish drive performance will result in unacceptable audible and/or visual losses.
To ensure optimal performance, the audio/video information should ideally be written to sequential data sectors to avoid excessive movement of the read/write actuator in the disc drive. However, as mentioned above, repeated writing and deletion of data files will result in fragmentation of data. Consequently, the performance of the disc drive and the audio/video application can be adversely affected by excessive fragmentation of data sectors on the disc and poor allocation of the data file to the fragmented sectors. One common method of reducing file fragmentation in typical file systems used in general purpose operating systems is to use software utilities which reorganize the data files to minimize fragmentation. However, such utility programs provide only a temporary solution, and need to be repeated regularly if optimal performance of the disc drive is to be achieved.
U.S. Pat. No. 5,375,233 discloses a method of more efficient allocation of disc space to data files. In this method, the file system is divided into large blocks which are allocated to large files. Some of the large blocks are subdivided into small blocks which are allocated to small files. However, this system involves the additional step of characterizing each new file as a large file or a small file. Moreover, there may still be wastage due to the use of large size blocks, and read/write inefficiencies due to discontinues disc spaces which inevitably result from repeated deletion, modification and/or creation of files on the disc.
U.S. Pat. No. 5,987,479 teaches a method of allocating block sizes in a disc-based file system depending on the size of the files written to the disc and the operating parameters of the disc drive. In one embodiment, the minimum block size is chosen such that for a given set of files, the largest file is written to consecutive addresses on the disc, that is, within one block, so that fragmentation is reduced below a particular threshold. However, if there is an abnormally large file in the set, this would result in an unduly large block size and consequent inefficient use of disc space.
U.S. Pat. No. 5,987,479 also teaches a method for selecting block size so that fragmentation is reduced below a particular threshold to guarantee that an application will not fail due to file fragmentation. The minimum block size is calculated using application input/output bandwidth requirements, disc transfer rates and seek times. Although the formula for calculating minimum block size taught in the U.S. Pat. No. 5,987,479 reduces the problem of file fragmentation, the formula may not result in optimal block size, particularly for audio and video applications. Moreover, the block size is calculated without reference to the size of any associated buffer.
The present invention provides a solution to this and other problems, and offers other advantages over the prior art.
SUMMARY OF THE INVENTION
One embodiment of the present invention provides a system for optimizing the allocation of sectors in disc drives, particularly for audio and/or video data, by determining the optimal host buffer size required for an audio and/or video application, and then grouping data sectors sequentially in blocks equivalent to the host buffer size.
Another embodiment of the present invention provides computer apparatus having a data storage device in which data is operatively stored in storage elements grouped sequentially into blocks which represent minimum logical storage units, and at least one buffer adapted to receive data from the data storage device for subsequent transfer in a data stream to a respective application, where the size of the blocks is determined to be equal to or slightly greater than the size of the buffer.
The term “computer apparatus” is intended to include not only a computer system, but also a computer-based consumer product, for example, for audio and/or video applications, having a data storage device and associated buffer(s).
Another embodiment of the present invention provides a method of allocation of the storage elements in the data storage device for data storage, the method comprising grouping the storage elements sequentially into blocks which represent the minimum logical storage units, the size of the blocks being equal to or slightly greater than the size of the buffer.
The invention is particularly suitable for audio/video applications. Since the size of each block is equal to, or slightly greater than, the size of the buffer, the buffer can be filled by data obtained from sequential storage elements in a single block. The problem of fragmentation is avoided, thereby reducing the time required for filling the buffer, and avoiding audio/video losses.
In another embodiment, the optimal size of the buffer can be determined from the rate of data transfer from the storage device to the buffer, the rate of data transfer in the data stream from the buffer to the respective application, the number of data streams to be supported, and the worst case data access time for the storage device.
Typically, the data storage device is a magnetic disc such as found in a disc drive of a computer system, and the storage elements are sectors of the disc.
Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description of the embodiments illustrated by those drawings. Such embodiments are provided by way of example, without limiting the scope of the invention.
REFERENCES:
patent: 5375233 (1994-12-01), Kimber et al.
patent: 5465338 (1995-11-01), Clay
patent: 5568650 (1996-10-01), Mori
patent: 5987479 (1999-11-01), Oliver
patent: 6115787 (2000-09-01), Obara
Quak Beng Wee
Wei Loon Ng
Yip Ying Ee
Bragdon Reginald G.
Cesari Kirk A.
Namazi Mehdi
Seagate Technology LLC
LandOfFree
Optimizing allocation of sectors in disc drives does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimizing allocation of sectors in disc drives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing allocation of sectors in disc drives will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3062679