Sign In to Follow Application
View All Documents & Correspondence

"Methods And Apparatus For Controlling Access To A Recording Disk"

Abstract: A method and apparatus for controlling the access to a recording disk which determines a skew so that a rotational delay time at an average distance of movement when a head accesses the recording disk is minimized. The methods and apparatus determine the position of a data block on the recording disk based on at least the determined skew, schedules an order of a plurality of input disk access requests so that an amount of movement of the head becomes small at the time of access with respect to the recording disk by the head, and the head accesses the recording disk based on the result of the scheduling.

Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence

Patent Information

Application #
Filing Date
24 October 1996
Publication Number
35/2007
Publication Type
INA
Invention Field
ELECTRONICS
Status
Email
Parent Application
Patent Number
Legal Status
Grant Date
2008-07-28
Renewal Date

Applicants

SONY CORPORATION
7-35,KITASHINAGAWA 6-CHOME,SHINAGAWA-KU,TOKYO, JAPAN.

Inventors

1. TAKASHI TOTSUKA
C/O SONY CORPORATION 7-35,KITASHINAGAWA 6-CHOME,SHINAGAWA-KU,TOKYO,JAPAN.
2. YASUNOBU KATO
C/O SONY CORPORATION 7-35,KITASHINAGAWA 6-CHOME,SHINAGAWA-KU,TOKYO,JAPAN.
3. NOBORU OYA
C/O SONY CORPORATION 7-35,KITASHINAGAWA 6-CHOME,SHINAGAWA-KU,TOKYO,JAPAN.
4. HIROYUKI SHIOYAA
C/O SONY CORPORATION 7-35,KITASHINAGAWA 6-CHOME,SHINAGAWA-KU,TOKYO,JAPAN.

Specification

METHODO AND APPARATUS FOR CONTROLLING ACCECC TO A RECORDING DICKT BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method of controlling the access to a recording disk requiring a high transfer speed and access to discontinuous positions on the disk (random access) and to an apparatus for the same. 2. Description of the Related Art Along with the increase of the speed of computers, disk storage devices which enable high speed, random access have been becoming increasingly important. In recent years, particularly in technology for multimedia, now the focus of so much attention, it is essential to access the motion pictures and audio stored on the disk as digital data at a high speed and from positions on the disk separate from each other. Namely, a high transfer speed and real time property are required for the storage of multimedia data such as motion pictures and audio. The high transfer speed naturally becomes necessary when handling a large amount of motion pictures and audio. Furthermore, the real time property requires that an upper limit of the processing time not be exceeded. For example, the movement becomes awkward unless 30 frames are successively displayed per second at constant intervals in the motion picture. Further, if not able to keep up with the capabilities of the disk and there is insufficient audio data, the sound breaks off and unpleasant noise is generated. In this way, if the data of multimedia are not prepared and used at their respectively specified times, the value of the information drops sharply. Accordingly, in the storage for multimedia, it is important that the upper limit be guaranteed, that is, that the processing can be carried out in that time even in the worst case. Otherwise, even if satisfying the specifications in terms of the average performance, it is possible that the data will be too late at some periods of time. The guarantee of the maximum value of the processing time is referred to as the real time property and is an indispensable function in the multimedia field. In the storage of information for computers, improvement of average performance has been the primary target. The worst value was not always kept low; that is, there was a large variation in storage processing time. This point stands in sharp contrast to storage requirements for multimedia. In addition, in the main fields of application of multimedia, successive access to data at physically separated positions (random access) must be able to be carried out at a high speed. For example, video-on-demand (VOD) is a system allowing a large number of viewers to call up and view the programs they like at the times they like. In order to realize this, it is necessary to process the requests from many viewers in parallel and quickly prepare the data of the parts that the viewers are currently watching. For this reason, it becomes necessary to trace the sources of movies, etc. stored at a variety of locations on the disk at a high speed. Further, in recent years, videos and movies have been edited by using not tapes and films, but disks. With a tape, when inserting a scene of a few seconds into a position near the start of a program of, for example, one hour, to prevent overwriting it is necessary to shift to the rear all of the video after that insertion position and therefore re-record the program. Unlike high speed reproduction of analog audio cassette tapes, such re-recording of video programs requires about one program's worth of time, so the efficiency is poor. With a disk, however, since random access is possible, it is possible to place the insertion portion at another position on the disk, jump once to that position and access the inserted video at the time of reproduction, and then return to the original position and continue the reproduction of the video. Taking this methodology a step further, there is known a technique wherein each scene (cut) of the program is placed at different positions on the disk and track them at a high speed at the time of reproduction so as to make it appear as if a single tape were being reproduced. By doing this, it is possible to switch scenes and change lengths just by changing the order of tracking of the data on the disk, therefore the efficiency of editing is extremely high. This is referred to as non-linear editing. Note that, in this case as well, it is necessary to track physically separated positions on the disk at a high speed. As seen in these examples, in the fields of application of multimedia, it is extremely important to access the data at a high speed while tracking discontinuous positions on the disk (this is referred to as random access), but the time for the movement of the head to the desired cylinder, which is referred to as the seek time, and the time for waiting for the disk to rotate until the start of the data appears in the cylinder, which is referred to as the rotational delay time, are necessary for movement to discontinuous positions. These times are referred to as the overhead of the access. The longer this is compared with the time for actually accessing the data, the longer time it takes for the transfer of data from the disk and therefore the lower the performance. Now, when assuming that the seek time of the disk is Ts and the rotational delay time is Tr, the overhead of the disk access becomes Ts+Tr. When the head of the disk exists in the data and the time for actually accessing the data is Tt, the efficiency compared with a case where there is no jump of the head to a separate position becomes low as shown in the following Equation (1) : Tt/(Tt+Ts+Tr) (1) Namely, in comparison with a case where the data on the disk are sequentially accessed from start to the end, in the case where random access is carried out while tracking the data at separated positions, it is necessary to be aware of the reduction of the performances by that amount. Accordingly, the task with multimedia disks is to suppress the reduction in the performance at the time of a random access while maintaining the real time property (to determine the upper limit of the processing time and guarantee to always operate at a time equal to or shorter than this upper limit). In recent years, research has been conducted regarding the method of guaranteeing the real time property in the access of disks. For example, in D. Anderson, Y. Osawa, and R. Govindan, "A File System for Continuous Media", ACM Transactions on Computer Systems, Vol. 10, No. 4, pp. 311 - 337, 1992 (hereinafter referred to as "Anderson 92"), an attempt is made to improve the performance of a system by optimizing the relationship between the amount of the buffer memory for temporarily storing the data read from the disk and the amount of the data to be read in a single access. When it comes to the overhead of the access of the disk, however, to facilitate the analysis, it assumes that the worst values conceivable both for the seek time and the rotational delay time occur at every random access. Namely, the time when seeking from the innermost circumference to the outermost circumference is adopted as the seek time and the time for waiting for exactly one rotation is adopted as the rotational delay time. Of course, if making this assumption, the estimate of the worst value of the processing time is extremely safe, but such an operation is not conducted every time in actuality and therefore the estimate of the worst value becomes very low in comparison with the performance which can be derived from the disk in actuality and such an estimate has little significance as design data. Further, in V. Rangan and H. Vin, "Efficient Storage Technique for Digital Continuous Multimedia", IEEE Transactions on Knowledge and Data Engineering, Vol. 5, No. 4, pp. 564 - 573, 1993 (hereinafter referred to as "Rangan 93"), it is investigated how, when cutting a video file into a plurality of segments and storing the different segments at different positions, to determine the lengths of the segments and the intervals between segments so as to maintain the real time property. Here too, however, when jumping between segments (at time of random access), it is assumed that the worst overhead is caused every time in the same way as described in "Anderson 92", therefore a similar problem exists. There have also been attempts to keep the worst value lower in comparison with these studies. These enable real time random access to be guaranteed with much higher performances. Each of N. Reddy and J. Wyllie, "Disk Scheduling in a Multimedia I/O System", ACM multimedia 93, pp. 225 - 233, 1993 (hereinafter referred to as "Reddy 93"), J. Gemmel, J. Han, et al., "Delay-Sensitive Multimedia on Disk", IEEE Multimedia 1994, pp. 56 - 67, 1994 (hereinafter referred to as "Gemmel 94"), and M. Chen, D. Kandlur, and P. Yu, "Optimization of the Grouped Sweeping Scheduling (GSS) with Heterogeneous Multimedia Streams", ACM Multimedia 93, pp. 235 - 242, 1993 (hereinafter referred to as "Chen 93"), attempts to suppress the overhead by using a head scheduling algorithm referred to as "SCAN". "Head scheduling" is a method for reducing the seek time by tinkering with the order of the access where it is necessary to access a plurality of positions on the disk. The SCAN algorithm shown in Fig. 1 is an algorithm in which a given plurality of I/O requests (#1, #2, ...) are sorted in the radial direction of the disk and sequentially processed. Reciprocal operation of the head, which will occur if the processing is carried out in the order of arrival of the I/O requests (#1, #2, ...), can be prevented and in turn the respective seek times can be reduced. As the algorithm of the head scheduling, many algorithms are known. These are mentioned in detail in for example H. Deitel, "Operating Systems", Addison Wesley, pp. 360-372, 1990. All of "Reddy 93", "Gemmel 94", and "Chen 93" are predicated on the assumption the use of a SCAN algorithm, therefore are able to suppress the seek time. Accordingly, it is possible to lower the worst value of the overhead and guarantee a higher performance in comparison with "Anderson 92" and "Rangan 93". However, the only thing which the SCAN algorithm can suppress is the seek time. No allusion has yet been made up to now about reduction of the rotational delay time. "Reddy 93" assumes that a special function referred to as a zero latency access mechanism exists in the disk. The zero latency access mechanism is a method in which the data is successively read even from the middle of the data at a point of time when the head reaches the desired track and the leading portion of the data which was not in time is read again when the disk rotates one time and that portion returns. Accordingly, when the disk rotates one time, the desired data can be all reliably read and therefore the total of the rotational delay and the access of data becomes the time of the amount of one rotation at the maximum. However, since few actual disks utilize this mechanism, it may be that the assumption in "Reddy 93" is not realistic. On the other hand, "Gemmel 94" adopts a method of estimating the overhead by always adding the maximum value as a result of considering that the rotational delay is an amount for which control and prediction are impossible. This is safe but there is a lot of waste, which poses a problem. Further, "Chen 93" treats the rotational delay as a negligible correction term, but this is not realistic. For example, in recent high speed disks, the rotation cycle is 8.3 mS, while if the SCAN algorithm is used, the maximum value of the seek time can be suppressed to about 6 ms or less. Therefore the rotational delay is dominant. Further, from the viewpoints of the air resistance and the consumed electric power of the motor and resultant heat generated, it is difficult to expect any epoch-making improvements in the rotational speed from this point onward. The reduction of the rotational delay is the biggest problem which should be solved. It is also pointed out that in the usual file system for computers, the reduction of the rotational delay is important. S. Ng, "Improving Disk Performance Via Latency Reduction", IEEE Transactions on Computers, Vol. 40, No. 1, January 1991, pp. 22 - 30, 1991 (hereinafter referred to as "Ng 91") mentions a method of reducing the average rotational delay time at the time of a read operation by the method of preparing a copy of the data shifted in phase in the rotational direction etc. However, it is difficult to apply this method for multimedia applications which involve a huge amount of data. SUMMARY OF THE INVENTION The present invention was made in consideration with the situations as described above and has as an object thereof to provide a method and apparatus for controlling the access to a recording disk which can realize a high speed random access while maintaining the real time property by suppressing both of the seek time and the rotational delay time. Such a method of controlling the access to a recording disk and an apparatus therefor are preferred as the storage for multimedia data, demand for which has been increasing. In order to solve the problems of the related art mentioned above and achieve the above object, the method for controlling the access to a recording disk of the present invention determines a skew so that a rotational delay time at an average distance of movement when a head accesses the recording disk becomes short; determines the position of a data block on the recording disk based on at least the determined skew; schedules an order of a plurality of input disk access requests so that an amount of movement of the head becomes small at the time of access with respect to the recording disk by the head; and performs the access to the recording disk by the head based on the result of the scheduling. Further, the method of controlling the access to a recording disk of the present invention preferably has the determination of the position of the data block on the recording disk carried out based on a gap indicating an angular difference between the start and the end in the same data block in addition to the skew. Further, the method of controlling the access to a recording disk of the present invention preferably provides data of a plurality of combinations of the skew and the gaps and has the combination data selectively used in accordance with the position on the recording disk. Further, the method of controlling the access to a recording disk of the present invention changes the size of the data block so that the gap is constant over the entire region from the outside to the inside of the recording disk. Further, the method of controlling the access to a recording disk of the present invention preferably determines the skew in accordance with the change of the gap of the data block generated due to a difference of radius of the recording track. Further, the method of controlling the access to a recording disk of the present invention preferably has the scheduling change the order of a plurality of requests for disk access so that they are arranged in order from the nearest one on when the recording head is moved from the current position toward an inner circumference or outer circumference of the recording disk and has the determination of the position of the data block on the recording disk determine the skew and gap so that a difference between a delay time Td(L) given by the following Equation (2) and a seek time Ts(L) near an average seek distance La given by the following Equation (3) becomes sufficiently small in comparison with the rotation cycle: Td(L) = (L-Bc •0 s + 0 g+2 m)/ (2) La=Lt/(N-l) (3) where, L is a seek distance in units of the number of cylinders; Be is a number of data blocks existing in one cylinder; θs is a skew in units of radians; θg is a gap in units of radians;  is a rotational speed (radian/sec) of the disk; Lt is the maximum value of the distance between access positions of the two ends when arranging the access requests in order in units of the number of cylinders; N is the number of accesses to be simultaneously processed; and, m is selected so as to become the smallest within a range where Td(L) exceeds the seek time Ts(L) at the seek distance L. Further, the method of controlling the access to a recording disk of the present invention preferably has the scheduling change the order of a plurality of requests for disk access so that they are arranged in the order of appearance when the head is moved from the current position toward the inner circumference or outer circumference of the recording disk and has the determination of the position of the data block on the recording disk determine the skew and gap so that the delay time Td(L) given by the following Equation (4) is always longer than the seek time Ts(L) and the difference between the delay time Td(L) and the seek time Ts(L) becomes sufficiently small in comparison with the rotation cycle: Td(L) = (L-Bc-0 s+0 g)/ω (4) Further, the method of controlling the access to a recording disk of the present invention preferably has the memory disk divided into first regions used when the head moves from the inner circumference to the outer circumference and second regions used when the head moves from the outer circumference to the inner circumference; has the determination of the position of the data block on the recording disk determine the optimum skew and gap in the respective regions based on the direction of movement of the head; and has the scheduling selectively access only the first and second regions in accordance with the direction of movement of the head. Further, the method of controlling the access to a recording disk of the present invention preferably has the first regions and the second regions on the recording disk divide the disk into a plurality of at least two portions along the radial direction and has both of the first regions and second regions allocated so as to be dispersed from the innermost circumference to the outermost circumference on the disk. The apparatus for controlling the access to a recording disk of the present invention has a skew determining means for determining the skew so that the rotational delay time at the average distance of movement when the head accesses the recording disk becomes short; a data block arranging means for determining the position of a data block on the recording disk based on at least the determined skew; and a scheduling means for scheduling the order of a plurality of input disk access requests so that the amount of movement of the head becomes small at the time of access of the recording disk by the head, wherein the head performs the access to the recording disk by the head based on the results of the scheduling. Further, the apparatus for controlling the access to a recording disk of the present invention preferably has the data block arranging means perform the arrangement based on a gap indicating the angular difference between the start and the end in the same data block in addition to the skew. Further, the apparatus for controlling the access to a recording disk of the present invention preferably has the data block arranging means have data on a plurality of combinations of the skew and the gaps and selectively use the combination data in accordance with the position on the recording disk. Further, the apparatus for controlling the access to a recording disk of the present invention preferably has the data block arranging means change the size of the data block so that the gap is constant over the entire region from the outside to the inside of the recording disk. Further, the apparatus for controlling the access to a recording disk of the present invention preferably has the skew determining means determine the skew in accordance with the change of the gap of the data block generated due to a difference of the radius of the recording track. Further, the apparatus for controlling the access to a recording disk of the present invention preferably has the scheduling means change the order of a plurality of requests for disk access so that they are arranged in order from the nearest one on when the recording head is moved from the current position toward an inner circumference or outer circumference of the recording disk and has the data block arranging means determine the skew and gap so that a difference between a delay time Td(L) given by the following Equation (5) and a seek time Ts(L) near an average seek distance La given by the following Equation (6) becomes sufficiently small in comparison with the rotation cycle: Td(L) = (L-Bc •0s+0g+2mir)/o> (5) La=Lt/(N-l) (6) where, L is a seek distance in units of the number of cylinders; Bc is a number of data blocks existing in one cylinder; 0s is a skew in units of radians; 0g is a gap in units of radians; ω is a rotational speed (radian/sec) of the disk; Lt is the maximum value of the distance between access positions of the two ends when arranging the access requests in order in units of the number of cylinders; N is the number of accesses to be simultaneously processed; and, m is selected so as to become the smallest within a range where Td(L) exceeds the seek time Ts(L) at the seek distance L. Further, the apparatus for controlling the access to a recording disk of the present invention preferably has the scheduling means change the order of a plurality of requests for disk access so that they are arranged in the order of appearance when the head is moved from the current position toward the inner circumference or outer circumference of the recording disk and has the data block arranging means determine the skew and gap so that the delay time Td(L) given by the following Equation (7) is always longer than the seek time Ts(L) and the difference between the delay time Td(L) and the seek time Ts(L) becomes sufficiently small in comparison with the rotation cycle. Td(L) = (L-Bc -0s+0g)/u (7) Further, the apparatus for controlling the access to a recording disk of the present invention preferably has the memory disk divided into first regions used when the head moves from the inner circumference to the outer circumference and second regions used when the head moves from the outer circumference to the inner circumference; has the data block arranging means determine the optimum skew and gap in the respective regions based on the direction of movement of the head; and has the scheduling means selectively access only the first and second regions in accordance with the direction of movement of the head. Further, the apparatus for controlling the access to a recording disk of the present invention preferably has the first regions and the second regions on the recording disk divide the disk into a plurality of at least two portions along the radial direction and has both of the first regions and second regions allocated so as to be dispersed from the innermost circumference to the outermost circumference on the disk. In the method of controlling the access to a recording disk of the present invention and the apparatus therefor, when arranging the data blocks, the blocks are arranged shifted in the circumferential direction (given a skew), therefore control can be carried out so that the start of the desired data does not pass the position of the head during the seek operation. For this reason, it is not necessary to wait for the time until the start of the desired data returns again, both of the seek time and the rotational delay time are suppressed low, and a random access can be realized at a high speed while maintaining the real time property. Further, in the method of controlling the access to a recording disk of the present invention and the apparatus thereof, the skew is changed between the regions used when the head moves from the outer circumference to the inner circumference and the regions used when the head moves from the inner circumference to the outer circumference, whereby the optimum skew can be given irrespective of the direction of movement of the head. The present invention relates to a method of controlling access to a recording disk, comprising the steps of: determining the arrangement of data blocks on the recording disk; scheduling in order of a plurality of disk access requests to minimize an amount of movement of the head when the recording disk is accessed by the head; and accessing the recording disk by the head based on the result of the scheduling, characterized in that the arrangement of data blocks on the recording disk is determined based on at least a determined skew indicating an angular difference in a circumference direction between the starts of adjoining blocks to minimize a rotational delay time which indicates the time for waiting for the recording disk to rotate until the start of the data appears in the cylinder at an average distance of movement when a head accesses the recording disk. The present invention also relates to an apparatus for controlling access to a recording disk, comprising: means for determining the arrangement of data blocks on the recording disk; means for scheduling an order of a plurality of disk access requests to minimize an amount of movement of the head when the recording disk is accessed by the head; and means for accessing the recording disk by the head based on the result of the scheduling characterized in that said determining means determines the arrangement of data blocks on the recording disk based on at least a determined skew indicating an angular difference in circumference direction between the, starts of adjoining blocks to minimize a rotational delay time which indicates the time for waiting for the disk to rotate until the start of the data appears in the cylinder at an average distance of movement when a head accesses the recording disk. BRIEF DESCRIPTION OF DRAWINGS These and other objects and features of the present invention will become more apparent from the following description of the, preferred embodiments given with reference to the attached drawings, in which: Fig. 1 is a diagram for explaining the related art; Fig. 2.is a block diagram of the configuration of an apparatus for controlling the access to a recording disk according to a first embodiment of the present invention; Fig. 3 is a flow chart for explaining the processing in the block allocator shown in Fig. 2; Fig. 4 is a flow chart for explaining the processing in the scheduler shown in Fig. 2; Fig. 5 is a graph showing a relationship between a seek time and seek distance of a drive; Fig. 6 is a diagram for explaining a method of arrangement of blocks on a disk by the block allocator; Fig. 7 is a chart for explaining the content of the block map; Fig. 8 is a view for explaining the content of the processing at step S3 shown in Fig. 3; Fig. 9 is a graph for explaining the content of the processing at step S3 shown in Fig. 3; Fig. 10 is a graph for explaining the overhead in a case where both of the seek and the rotational delay are considered; Figs. 11A, 11B and 11C are views for explaining one example of distribution of accesses on the disk; Fig. 12 is a graph for explaining the overhead in a conventional SCAN algorithm; Fig. 13 is a graph for explaining the relationship between a seek distance L and a delay in a case of using an upward convex function enveloping a sawtooth function; Fig. 14 is a view for explaining the processing in the block allocator of the apparatus for controlling the access to a recording disk according to a second embodiment of the present invention; Fig. 15 is a flow chart for explaining the processing of, the block allocator in the apparatus for controlling the access to a recording disk shown in Fig. 14; and Fig. 16 is a chart for explaining the content of the block map in the apparatus for controlling the access to a recording disk shown in Fig. 13. DESCRIPTION OF THE PREFERRED EMBODIMENTS Below, an explanation will be made of the method of controlling the access to a recording disk according to embodiments of the present invention and an apparatus therefor. First embodiment Figure 2 is a block diagram of a configuration of an apparatus for controlling the access to a recording disk according to the present embodiment. The apparatus for controlling the access to a recording disk according to the present embodiment is realized by operation of software in for example a computer. Each block shown in Fig. 2 represents a main program module or main data structure. A block allocator (arranging means) 1 determines how the data are arranged on a disk 5 based on a given format parameter 10. The disk 5 may be, for example, a magnetic disk, a magneto-optic (MO) disk, or a hard disk (HDD) is used. The format parameter 10 includes the size of a first data block, the average head movement distance La when performing the SCAN schedule, the seek time function Ts(L) of the drive to be used, and the physical format of the disk 5. The average head movement distance La is given by the following Equation (8) from the total number of cylinders Lt of the disk and the number N of the accesses processed by one scan. La=Lt/(N-l) (8) The seek time Ts(L) of the drive is a function of the seek distance L (number of cylinders). The value thereof is determined by the mechanical characteristics of the disk drive used. This example is shown in Fig. 5. How many access requests are processed together by a scan is determined by the nature of the application using this disk, the performance required there, the amount of the buffer memory which can be used, etc. The larger the number N of the access requests to be scanned together, the more improved the random access performance of the disk, but there is a side effect that the response time is increased as the amount of the buffer memory required is increased. These format parameters 10 are determined by a central processing unit (CPU) (not illustrated) having a control program which manages the entire system, and these format parameters 10 are provided to the block allocator 1. In the example in which the present embodiment is utilized for non-linear editing, N = 10 and La = 300 were given to the block allocator 1. Furthermore, the size of the first data block corresponds to one sheet of image data and is about 700 KB (kilobytes) in the case of the CCIR-601 format used in broadcasting stations etc. Of course, this numerical value can be freely set in accordance with the purpose and various requested specifications. The block allocator 1 determines at which position on the disk 5 each block is to be placed based on the given format parameter 10. In this example, one block equals one frame of an image, but of course the fundamental concept is similar even with data obtained by dividing an MPEG or other compressed image into suitable lengths, or even with audio data. The disk 5 can be accessed for every what is normally called a "sector" region. One sector usually has a size of from about 512 B (bytes) to about 4 KB. A doughnut shaped region in which these sectors are arranged in a circle is referred to as a "track". Further, the cylindrical region comprising the group of the same tracks of a superimposed plurality of magnetic media is referred to as a "cylinder". One block of the video and audio data is usually larger than one sector, therefore the block allocator 1 allocates a plurality of sectors for each block. Figure 6 shows a simple example of a case where there is one magnetic medium. The portion indicated by the hatching in Fig. 6, that is, an entire circumference of the track "1", and the sectors »0» to "6" of the track "2" correspond to one block. In this example, since there is only one medium, a "track" and a "cylinder" have the same meaning, but in the case of a disk drive in which there are a plurality of magnetic media, if all parts of the same cylinder are completely used, the blocks are allocated to use the adjoining cylinders. The allocation to the sectors is carried out for all blocks. The result thereof is written on a block map 3, whereupon the role of the block allocator 1 ends. The block allocator 1 designates a position of a sector by the set of the cylinder number, the media number (which sheet of media), and the sector number. However, in a drive of a SCSI (ANSI Small Computer System Interface) specification, which has become the most popular in recent years, serial numbers (local sector numbers, called "logical block addresses" in SCSI, but here referred to as logical sector numbers so as to avoid confusion with the video and audio data blocks) are given to all sectors in the drive and these are used to access the data. For this reason, the correspondence between the logical sector numbers determined by the drive and the physical addresses, that is, the cylinder numbers, media numbers, and sector numbers, is preliminarily stored in a physical address table 7. The block allocator 1 converts the desired physical address to the logical sector number determined by the SCSI referring to the physical address table 7 and enters this on the block map 3. Figure 7 shows an example of a block map. The information corresponding to the block "0" corresponds to the hatching portion of Fig. 6. On the other hand, the scheduler 2 operates as follows. First, the CPU for managing the entire system determines the schedule parameter 20 and provides the schedule parameter 20 to the scheduler 2. The schedule parameter 20 includes a constant N indicating how many access requests are processed together by one scan. When the operator instructs the start of reproduction of a motion picture image recorded on the disk 5, the not illustrated CPU having a suitable control program issues requests for access to the blocks in which the images constituting the motion picture image are stored for every image. These access requests 40 are stored in the access request buffer 4. The scheduler 2 sequentially takes out N number of access requests 40 stored in the access request buffer 4 from the access requests which arrived earlier, finds the positions of the data corresponding to these requests on the disk 5 referring to the block map 3, changes the order of the access requests so that the amount of movement of the head becomes the minimum, and generates an instruction for access to the disk 5. The instruction for the access is made to match the external interface of the disk drive, and therefore is converted to the SCSI protocol by the SCSI device driver 6 and is then transferred to the disk 5. The data read from the disk 5 is stored temporally in the data buffer 8 and further transferred to the video interface of the apparatus. When the operator instructs the recording of data representing motion picture images, the not illustrated CPU having a suitable control program issues requests for access to the block in which the images constituting the motion picture image are stored for every image. These access requests 40 are stored in the access request buffer 4. At the same time, the image data 80 constituting the motion picture are transferred from a video interface (not shown) to the data buffer 8, and such image data 80 is temporally stored in the data buffer 8. The scheduler 2 sequentially takes out N number of access requests 40 stored in the access request buffer 4 from the access requests which arrived earlier. Next the scheduler 2 finds on the disk 5 the position of the data corresponding to these requests, referring to the block map 3. In addition, the scheduler 2 changes the order of the access requests so that the amount of movement of the head becomes the minimum, and generates an instruction for access of the disk 5. The instruction for the access is made to match the external interface of the disk drive, and therefore is converted to the SCSI protocol by the SCSI device driver 6 and is then transferred to the disk 5. Below, a detailed explanation will be made of the operation of the block allocator 1. As the format parameter 10 in Fig. 2, when the size of one block, the average distance of movement of the head La when performing the SCAN schedule, the seek time function Ts(L) of the drive to be used, the physical format of the disk 5 (number of cylinders, number of sectors in one track, and number of media constituting the cylinder) are given, the block allocator 1 determines the position of each block on the disk 5 by the procedures of steps SI to S5 shown in Fig. 3. At step SI, it is calculated how many blocks of the image exist in one cylinder (Bc). The total number of the sectors in one cylinder is obtained by multiplying the number of sectors in the track by the number of the media. When this is divided by the number of sectors necessary for storing one block, Be is found. The gap dg is found at step 82. The gap is the angular difference between the leading sector and the final sector of the block. As an example, in the case of the block indicated by hatching in Fig. 6, the start is the sector "0" of the track "1", and the end is the sector "6" of the track "2", therefore the gap 0g is 5/12ths of the circumference, that is, Sir/6 radian. The skew da is found at step S3 based on the above data. Here, the skew OB means the angular difference in the circumferential direction between heads of adjoining blocks. First, by using the position of the head when the reading of a certain block is ended as the start point, when represented by an equation, the time Td(L) until the t head of the data reaches the same angle in the circumferential direction at the position where the head has moved from the start point by an amount of L cylinders, the following Equation (9) is obtained: Td(L) = (L -Be -0s + 0g+2 -m-ir)/co (9) where, L is the seek distance in units of the numbers of cylinders; Be is the number of blocks existing in one cylinder; da is the skew in units of radians; 0g is the gap in units of radians; ω is the rotational speed (radian/sec) of the disk; and m is any integer where Td(L) becomes positive. Figure 8 explains the meaning of Equation (9) on the disk. In Fig. 8, assume that the access of the block "0" has just been ended. Assume that the head is located in the direction of the angle 70 when seen from the center. Now, when desiring to access the same block "0" again, it is necessary to wait until the disk rotates exactly by the amount of the gap 0g, therefore the delay time of 0g/ω is caused. Further, for the head of the block "n", it is necessary to wait until the disk rotates exactly by the angle of the sum of the gap 6g of the block "0" and n number of blocks worth of skew (n0s) . This takes n0s/ω worth of time. Since the disk is rotating, the start of the data reaches the position at which the head placed at a time obtained by adding a whole multiple of the rotation cycle to the time obtained in this way. When the head moves by n number of blocks, this corresponds to movement of n/Bc cylinders in terms of the number of cylinders, therefore when drawing a graph while plotting the number of cylinders on the abscissa and plotting the delay time until the start is reached on the ordinate, Fig. 9 is obtained. The larger the skew, the larger the inclination of the group of lines. Note that, in the above theory, it was assumed that the position (angle) of the head in the circumferential direction seen from the center was constant irrespective of the distance from the center. In actuality, there exists a case where the position is not correctly constant depending on the mechanism of the head, but the influence thereof is sufficiently small, and therefore it can be usually ignored. As shown in Fig. 9, the time until the start of the block arrives below the head in each cylinder is obtained by the Equation (9). However, since the head must move to the desired cylinder within this time, the delay time becomes the time until the start of the block appears the first time after the seek operation. This is the overhead Td(L) which considers both of the seek and the rotational delay. Figure 10 shows an example of this and Equation 1 shows the definition thereof. The actual overhead (delay time) is indicated by the bold line in Fig. 10. Note that the function of the seek time is indicated by the dotted line. In the fi gure, Trot is one rotation cycle. At step S3-1, the formula of the straight line of m = 0 in Equation 3 and Fig. 9, that is, the formula indicated by the following Equation (10), is found: Td(L) = (L-Bc -0s+0g)/

Documents

Application Documents

# Name Date
1 2301-del-1996-petition-137.pdf 2011-08-21
2 2301-del-1996-gpa.pdf 2011-08-21
3 2301-del-1996-form-6.pdf 2011-08-21
4 2301-del-1996-form-4.pdf 2011-08-21
5 2301-del-1996-form-3.pdf 2011-08-21
6 2301-del-1996-form-2.pdf 2011-08-21
7 2301-del-1996-form-19.pdf 2011-08-21
8 2301-del-1996-form-13.pdf 2011-08-21
9 2301-del-1996-form-1.pdf 2011-08-21
10 2301-del-1996-drawings.pdf 2011-08-21
11 2301-del-1996-description (complete).pdf 2011-08-21
12 2301-del-1996-correspondence-po.pdf 2011-08-21
13 2301-del-1996-correspondence-others.pdf 2011-08-21
14 2301-del-1996-claims.pdf 2011-08-21
15 2301-del-1996-abstract.pdf 2011-08-21

ERegister / Renewals

3rd: 17 Sep 2008

From 24/10/1998 - To 24/10/1999

4th: 17 Sep 2008

From 24/10/1999 - To 24/10/2000

5th: 17 Sep 2008

From 24/10/2000 - To 24/10/2001

6th: 17 Sep 2008

From 24/10/2001 - To 24/10/2002

7th: 17 Sep 2008

From 24/10/2002 - To 24/10/2003

8th: 17 Sep 2008

From 24/10/2003 - To 24/10/2004

9th: 17 Sep 2008

From 24/10/2004 - To 24/10/2005

10th: 17 Sep 2008

From 24/10/2005 - To 24/10/2006

11th: 17 Sep 2008

From 24/10/2006 - To 24/10/2007

12th: 17 Sep 2008

From 24/10/2007 - To 24/10/2008

13th: 17 Sep 2008

From 24/10/2008 - To 24/10/2009