Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-12-03
2004-10-12
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S170000, C711S173000, C711S202000, C711S205000, C711S206000, C711S207000, C711S208000, C711S209000, C711S211000, C707S793000
Reexamination Certificate
active
06804746
ABSTRACT:
BACKGROUND OF THE INVENTION
With the proliferation of digital audio and video devices, it has become necessary to establish a high speed serial communication mechanism that is capable of allowing efficient and fast transfer of audio/video (A/V) data between devices. IEEE 1394 has so far been a successful candidate for this purpose.
While the transmission of A/V data using industry standard such as IEEE 1394 is well known, the storage of A/V data on modern computing devices is becoming an important issue. Modem computing devices are rapidly moving toward offering various kinds of functionality and features in an integrated manner. For example, a personal computer (PC) nowadays generally contains a myriad of computer programs which offer a variety of functionality, such as word processing programs as well as computer programs which are capable of processing and playing video and audio data. As a result, there is a need to store both A/V data and non-A/V data and both types of data are typically stored on a computer hard disk together.
To store data on the hard disk or other media, a file system is generally required to be in place to organize files and accomplish a number of file-handling tasks such as file creation, deletion, access, save and update. Furthermore, it is preferable and common practice for a file system to have a directory structure which organizes and provides information about all the files stored in the file system. Typically, a file system is capable of storing both A/V and non-A/V data.
A/V data and non-A/V data, however, are fundamentally different in a number of respects. For example, the size of A/V data files is relatively large when compared to the size of non-A/V data files.
In addition, A/V data are typically stored in both large and small files. For example, the A/V data for a movie (in the range of gigabytes) is usually stored in one file and summary information about the movie, such as size of file, length of movie and other relevant information, is stored separately in a descriptor file (in the range of kilobytes) which typically is significantly smaller than the file containing the movie. As a result, handling files of varying sizes in an efficient manner becomes a challenging issue.
Moreover, since A/V data files are generally very large, it is usually not possible to store an entire A/V data file in a temporary storage area such as the random access memory (RAM). Therefore, due to the large size of an A/V data file, efficient random access of A/V data within the A/V data file also presents a problem.
Furthermore, the retrieval and processing of A/V data are subject to relatively stringent time and order-related constraints. Such constraints are necessary to prevent the corruption of A/V data and avoid potential glitches. For example, in order to provide a smooth presentation of video images, A/V data need to be retrieved and processed quickly and continuously in the correct sequential order. Otherwise, the video images might become choppy and incomplete. Hence, it would be desirable to develop and provide a method and system capable of allowing an A/V file system to handle a mix of A/V and non-A/V data in an efficient manner.
In almost every case, many files are stored on the same physical storage media such as a disk. The main problem is how to allocate space to these files so that disk space is utilized efficiently and files can be accessed quickly. A number of allocation methods are well known. For example, in the linked allocation method as shown in
FIG. 1
, each file is a linked list of disk blocks which may be scattered anywhere on the disk. The directory contains a pointer to the first and last blocks of the file and each disk block contains a pointer to the next disk block.
A variation of the linked allocation method is the use of a file-allocation table (FAT) as shown in
FIG. 2. A
section of disk at the beginning of each partition is set aside to contain the FAT. The FAT has one entry for each disk block (or cluster) and is indexed by block number. In other words, each FAT entry corresponds to a unique region on the disk. For a given disk size, the FAT size is fixed. The directory entry contains the block number of the first block of the file. The FAT entry indexed by that block number then contains the block number of the next block in the file. This linked list continues until the last block which has a special end-of-file value as the FAT entry. Unused blocks are typically indicated by a “0” FAT entry value.
This linked allocation method using a FAT has a number of disadvantages. For example, the disk head must move to the start of the partition to read the FAT and find the location of the block in question, then move to the location of the block itself. Therefore, it would be desirable to develop and provide a method and system capable of reducing disk head movement so as to improve data access time.
Furthermore, in a system which contains very large and small files, disk space is wasted since one FAT entry is used even if the file is much smaller than the block or cluster size. In other words, since each FAT entry is mapped to a unique disk block, the space in such disk block is not efficiently utilized if the size of a file is substantially smaller than the size of a disk block. On the other hand, if a disk block is chosen to be small, then the number of FAT entries will proportionally increase, which means there is less room on the disk for data storage. Hence, it would be desirable to develop and provide a method and system capable of allowing an A/V file system to utilize disk space more efficiently.
SUMMARY OF THE INVENTION
The present invention relates to an audio/video file system. More specifically, the present invention is directed to a method and system for optimizing data storage and retrieval by an audio/video system using hierarchical file allocation and other tables.
In an exemplary embodiment, an A/V file system implemented in accordance with the present invention includes two different types of hierarchical file allocation tables (HFATs), a contiguous space table, a track table and a list table.
The two different types of HFATs are a 0th order HFAT and a 1st order HFAT. Each of the two types of HFATs contains a number of entries. Each 0th order HFAT entry corresponds to a specific disk block and each 1st order HFAT entry corresponds to a specific subdivision within a subdivided disk block.
A 0th order HFAT entry is made up of three fields, namely, a type indicator, a 0th order index, and a 1st order index. The type indicator is used indicate whether a 1st order HFAT is referenced by a 0th order HFAT entry. If a 1st order HFAT is referenced by the 0th order HFAT, then the 0th order index is used to locate the disk block which contains the referenced 1st order HFAT. Once the disk block is located, the 1st order index is used to locate a specific 1st order HFAT entry within the 1st order HFAT. The specific 1st order HFAT entry is mapped to a subdivision which contains the next segment of the file.
The contiguous space table is used to store information relating to the location and availability of contiguous spaces or disk blocks. Each record in the contiguous space table includes a HFAT index and an associated quantity indicator. The HFAT index points to the HFAT entry which is mapped to the first of one or more contiguous empty disk blocks. The associated quantity indicator shows the number of contiguous empty disk blocks starting from the disk block which corresponds to the particular HFAT entry referenced by the HFAT index.
The track table contains a number of records. Each record, in turn, contains various track, HMSF and descriptor information.
The list table similarly contains a number of records each containing information about a list such as size and starting location.
Reference to the remaining portions of the specification, including the drawings and claims, will realize other features and advantages of the present invention.
Further features and advantages of the present invention, as well as the struct
Carpenter & Kulas, LLP.
Kulas Charles J.
Sparks Donald
Truong Bao Q.
LandOfFree
Method and system for optimizing data storage and retrieval... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for optimizing data storage and retrieval..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for optimizing data storage and retrieval... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3289058