Method and system for storing and retrieving multiple channel sampled data

• US 4,604,687 A
• Filed: 08/11/1983
• Issued: 08/05/1986
• Est. Priority Date: 08/11/1983
• Status: Expired due to Fees

• Current Assignee: Lucasarts Entertainment Company LLC (The Walt Disney Company)
• Original Assignee: Lucasfilm Limited (The Walt Disney Company)
• Inventors: Abbott, Curtis W.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): KRIESS, KEVIN A
• Application Number:
  US06/522,024
• Time in Patent Office: 1,090 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 369/32, 369/33, 369/41, 369/94, 369/56, 369/280, 369/276, 360/78, 360/77, 360/32, 360/13, 360/97, 360/81
• US Class Current: 1/1
• CPC Class Codes: G11B 20/10 Digital recording or reproducing
• CPC Class Codes: G11B 20/1251 for continuous data, e.g. digitised analog information signals, pulse code modulated [PCM] data
• CPC Class Codes: G11B 20/18 Error detection or correction; Testing , e.g. of drop-outs
• CPC Class Codes: G11B 2020/10546 specifically adapted for audio data
• CPC Class Codes: G11B 2020/10592 specifically adapted for recording or reproducing multichannel signals
• CPC Class Codes: G11B 2220/20 Disc-shaped record carriers
• CPC Class Codes: G11B 2220/2508 Magnetic discs
• CPC Class Codes: G11B 2220/65 wherein solid state memory is used for storing indexing information or metadata
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence
• CPC Class Codes: G11B 27/105 of operating discs
• CPC Class Codes: G11B 27/11 by using information not detectable on the record carrier
• CPC Class Codes: G11B 5/012 Recording on, or reproducing or erasing from, magnetic disks G11B17/00, G11B19/00 take precedence

Abstract

A method and system for recording and playing back from a bulk digital data storage medium having unequal access time, such as a rotating magnetic disk, data of a plurality of separate files, such as multi-channel sound information. Blocks of the digital data streams are stored in physically non-sequential scattered positions on a disk. The starting sectors of each recording track of the disk are not made the same but rather at least two different starting sectors are provided on alternating tracks in order to reduce the amount of access time between blocks of data. The blocks of data are read from the disk into a buffer memory in accordance with a disk read head scheduling technique that causes the next block of data with the shortest access time to be transferred unless there is an urgency to maintain balance in the various channels, in which case a block of data for the channel having the least buffered data is transferred next. This general criteria is altered under certain special circumstances, however, in order to take advantage of opportunities to read or write some other block of data without adding any access time, or to make sure that no channel runs out of buffered data. The technique allows the rate of data transfer to and from the disk to be maximized, considering the necessary limitation of buffer memory size and a desire in many cases to do transfers in real time, both reading and writing. The technique is especially advantageous when the data channels require editing by shifting their relative timing, often the case in multi-channel sound recording.

Claims

1. In a random access rotating disk digital data storage system wherein successive blocks of data of at least two data files are recorded in a pattern of a plurality of concentric circular tracks on said disk, each of said plurality of tracks having a plurality of sectors therearound for receiving said data and with one of said sectors at a particular rotational position of each such track designated to receive the beginning of a block of data, an improved method of positioning the recorded blocks of data on said circular tracks in order to reduce rotational latency, comprising the steps of:

recording the successive blocks of data for said at least two data files in physically non-sequential scattered positions in said circular tracks, and

beginning the recording of blocks of data in each of said plurality of tracks at its said beginning sector, the beginning sector of each of said plurality of tracks on said disk being fixed at one of at least two different rotational positions with respect to said disk, wherein the different rotational positions of the beginning sectors are N in number and the beginning sector for substantially any given track is given by (S/N) (cyl. modulo N), where S is the total number of sectors in the given track and "cyl. modulo N" is the remainder resulting from dividing the track number by N.

2. The method according to claim 1 wherein the at least two data files consist of at least two simultaneous channels of digital sound data.

3. In a random access rotating disk digital data storage system wherein successive blocks of digital data of at least two sound channels are recorded in a pattern of concentric circular tracks on said disk, each track having a plurality of sectors therearound for receiving said data and with one of said sectors at a particular rotational position of each track designated to receive the start of a block of data, an improved system for positioning of the recorded blocks of data on said circular tracks in order to reduce rotational latency, comprising:

means receiving said at least two sound channels for simultaneously recording their successive blocks of data in physically non-sequential scattered positions in said circular tracks,

the total different starting sectors of substantially all said tracks being N in number with the starting sector of substantially any given track being given by S/N(cyl. modulo N), where S is the total number of sectors in the given track and "cyl. modulo N" is the remainder resulting from dividing the track number by N.

4. The system according to claim 3 wherein N is equal to two.

5. A method of efficiently transferring, under the control of a central processing unit (CPU), blocks of digital data of a plurality of distinct files in a desired order between (1) a bulk storage memory characterized by having unequal access times to said blocks of data which are recorded in a scattered non-sequential manner, and (2) a random access buffer memory, the buffer memory being connected to simultaneously supply data blocks from the plurality of distinct files therein to another device, comprising the steps of:

developing in the CPU a transfer schedule for blocks of data by a method comprising the steps of;

identifying the locations of certain blocks of data stored in said bulk storage memory that are desired to be transferred into the buffer memory to form simultaneous and time sequential portions of each data file,

determining the number of blocks of data already scheduled to be stored in said buffer memory for each file,

determining from the number of blocks of data already scheduled to be stored in each buffer data file whether the amount of data in such files is balanced enough to avoid running out of data in any one file as the data is transferred to said another device, and

designating an order of the blocks of data to be transferred in either of two ways;

(1) if the amount of data in each buffer file is not balanced enough to avoid running out of data in any one file, data blocks are scheduled for transfer to the buffer files in a manner to increase such balance, or (2) if the amount of data in each buffer file is balanced enough to avoid running out of data in any of said plurality of files, data blocks are scheduled for transfer to the buffer files in an order that minimizes the access time thereto in the bulk storage memory, whereby efficiency of the transfer is maximized, thereby to develop a transfer schedule, and

transferring said certain blocks of data between the bulk storage memory and the buffer memory in accordance with the transfer schedule,

whereby said certain blocks of data are transferred at a high efficiency consistent with maintaining some balance in the number of buffered data blocks in each file.

6. The method according to claim 5,

wherein the step of determining whether balance exists includes the steps of:

determining the reciprocal of the number of blocks of data scheduled to be held in said buffer for each file, and

summing those reciprocals, and

wherein the step of designating an order includes the step of scheduling said certain blocks of data to be accessed either in a manner that substantially maximizes the efficiency of the transfer if said sum is greater than a given threshold or to increase such balance if said sum is less than said threshold.

7. The method according to claim 5 wherein the step of developing a transfer schedule comprises the additional steps of determining before a particular block of data is transferred from the bulk storage memory to the buffer memory whether a blank portion exists in said bulk storage memory into which a block of data can be transferred without any additional access time before transferring therefrom the next scheduled block of data, and if so, scheduling such a transfer into the bulk storage memory in advance of said next scheduled transfer from said bulk storage memory.

8. The method according to claim 5 wherein said data includes digital sound data and each of said files is an independent sound channel.

9. A method of efficiently transferring blocks of digital audio data from a plurality of audio channels betwen a bulk storage memory characterized by having unequal access times to said blocks of data which are recorded in a scattered non-sequential manner, and a random access buffer memory that is connected to a consumer or a source of said multi-channel digital audio data blocks, under the control of a central processing unit (CPU), comprising the steps of:

identifying in the CPU the locations of certain blocks of data stored in said bulk storage memory that are desired to be transferred into the buffer memory to form simultaneous and time sequential portions of each audio channel,

determining the number of blocks of data already stored in said buffer memory for each channel and determining the reciprocal of each such number,

obtaining an indication of urgency by the step of summing said reciprocals, thereby to determine an urgency quantity, and

transferring blocks of data from the bulk storage memory to the buffered memory in a sequence that substantially minimizes the access times between them in said bulk storage memory or in an sequence that substantially equalizes the blocks of data stored in said buffer for each channel, depending upon whether the urgency quantity is respectively less than or greater than a set threshold urgency value,

whereby said certain blocks of data are transferred at a high efficiency consistent with maintaining some balance in the number of buffered data blocks in each channel.

10. The method according to claim 9 wherein the step of obtaining an indication of urgency additionally includes the step of including in the urgency quantity an additional fixed amount if each of a certain number of channels has an amount of buffered data that is less than a predetermined amount.

11. The method according to claim 9 which comprises the additional steps of determining before a particular block of data is transferred from the bulk storage memory to the buffer whether a blank portion exists in said bulk storage memory into which a block of data can be transferred without any additional access time before transferring therefrom the next scheduled block of data, and if so, performing such a transfer into the bulk storage memory before the next scheduled transfer from said bulk storage memory.

12. In a system of efficiently transferring blocks of digital data of a plurality of distinct files between a bulk storage memory characterized by having unequal access times to said blocks of data which are recorded in a scattered non-sequential manner, and a random access buffer memory that is connected to a consumer or a source of said data files, a method of selecting at a particular instant in time the next block of data to be transferred from the bulk storage memory to the buffer, under the control of a central processing unit (CPU) comprising the steps of:

identifying in the CPU the storage locations on said bulk storage media of at least the next one block of data for each of said files to be transferred therefrom into said buffer memory,

determining the number of blocks of data already stored in said buffer memory for each file,

determining a reciprocal of said number of blocks of said data for each of the plurality of files,

obtaining a summation of all said reciprocals, thereby to determine a quantity indicative of the number and balance of the blocks of data in the buffer memory for the plurality of files,

comparing said quantity with a predetermined threshold constant,

selecting one of the identified said next one blocks of data for transfer from the bulk storage memory to the buffer memory according to the following criteria;

(a) the next in order block of data for the file having the least number of buffered blocks if said quantity is greater than said threshold constant, or

(b) the next in order block of data that requires the shortest time to access in said bulk storage memory if said quantity is less than said threshold constant, and

whereby a block of data is selected for transfer in a manner that results in a high transfer efficiency consistent with maintaining some balance in the number of buffered data blocks in each file.

13. The method according to claim 12 which comprises the additional steps of:

determining before the selected one block of data is tranferred from the bulk storage memory to the buffer memory whether a blank portion exists in said bulk storage memory into which a block of data can be transferred without any additional access time before transferring therefrom said selected one block of data, and

if this is found to be the case, performing such a transfer into the bulk storage memory at said blank portion thereof before transferring said selected one block from said media.

14. The method according to claim 12 which comprises the additional step of adjusting said quantity upwards, before the step of comparing said quantity with the threshold constant, if the number of blocks of data in the buffer memory for each of a predetermined number of channels is less than some predetermined low number.

15. The method according to claim 12 wherein the step of selecting the next one block of data for transfer additionally comprises selecting the block of data requiring the least access time even when said quantity is greater than said threshold constant so long as said quantity is only a small amount in excess of said threshold constant and the number of blocks of data in the buffer memory for the file of which this least access time data block is a part is not greatly in excess of the least number of blocks of data in the buffer memory for any file.

16. A system for efficiently transferring, according to a given transfer schedule, blocks of digital data of a plurality of distinct files between a rotating magnetic disk storage device and a random access buffer memory, comprising:

means for identifying the locations of certain blocks of data stored on said disk that are desired to be transferred into the buffer memory to form simultaneous and time sequential portions of each data file,

means for determining the number of blocks of data already stored in said buffer memory for each file,

means responsive to numbers ascertained by said block number determining means for determining whether the amount of data stored in the buffer in each file is enough to avoid running out of data in any one file as the data is simultaneously transferred out of the buffer to a data utilization device,

means responsive to the data amount determining means for designating an order of the blocks of data to be transferred, said designating means including;

means responsive to the amount of data in each buffer file not being balanced enough to avoid running out of data in any one file for scheduling data blocks for transfer to the buffer files in a manner to increase such balance, and

means responsive to the amount of data in each buffer file being balanced enough to avoid running out of data in any one file for scheduling data blocks for transfer to the buffer files in an order that minimizes the access time thereto in the storage device, and

means responsive to the designating means for transferring blocks of data from said disk to the buffered memory in an order scheduled by said designating means,

whereby said certain blocks of data are transferred from said disk at a high efficiency consistent with maintaining some balance in the number of buffered data blocks in each file.

17. The system according to claim 16 wherein said system additionally comprises means receiving blocks of data from said buffer for simultaneously recording successive blocks of data in physically non-sequential scattered positions in a pattern of a plurality of concentric circular tracks on said disk, and means for starting the recording of a block of data in each track at a certain sector thereof, said starting sector of each of the plurality of tracks on the disk being located at at least two different rotational positions therearound.

18. The system according to claim 17 wherein the rotational positions of the beginning sectors are two in number and are located substantially one-hundred-eighty degrees apart.

19. A system for storing and consuming blocks of digital data, comprising:

a magnetic disk storage device characterized by the ability to store digital blocks of data for each of a plurality of data files in scattered physical locations of said device,

a buffer memory characterized by the ability to store at least one block of said data for each of said plurality of files,

means connected to said buffer memory for consuming an unbroken stream of a plurality of blocks of data therein at a predetermined rate in real time simultaneously from each of said plurality of files, and

means connected to said disk storage device and said buffer memory for transferring blocks of data one at a time from the disk storage device to the buffer memory in an order that maintains enough data in said memory for each of said data files as required at any given instant by consuming means,

whereby said consuming means is provided with a sufficient data supply to allow its simultaneous real time consumption of blocks of data from each of said files at said predetermined rate.

20. The system according to claim 19 wherein said digital data includes digitized sound information, and wherein said plurality of data files include a plurality of sound channels.