JP2002023962A - Disk device and its controlling method - Google Patents

Abstract

(57) [Summary] A disk device itself has a disk access scheduling function based on an access pattern. The disk device includes a pattern determination unit, a schedule mechanism, a disk time sharing mechanism, and a reordering mechanism. The pattern determining unit 46 determines whether the command received from the host is sequential or random, stores the command in the queues 70, 72, 74, 76 of the schedule mechanism 50 separately for the access pattern and the read / write, and stores the command stored in the queue. The command is scheduled to be input to the sequential queue 84 and the random queue 86 of the disk time sharing mechanism 82 in consideration of the access pattern.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a disk device having a reordering function, and more particularly to a disk device for scheduling a command input to a reordering mechanism separately for sequential access and random access.

[0002]

2. Description of the Related Art Conventionally, a disk device known as a hard disk drive has a reordering function (Re-o
rdering function). That is, a disk device having a reordering function has at most one command queue, and performs command reordering in the queue considering only the seek time and the rotation waiting time.

[0003] The reordering function is implemented by a disk device,
This function selects the command that minimizes the positioning time defined by the sum of the seek time and the rotation wait time from the execution wait commands as the next command to be executed. When requesting a command to the disk device, the disk device is notified of a simple task (Simple task) for designating a task to be reordered.

In the case of a command specifying a simple task, the disk device schedules the command in an order that minimizes the positioning time. Thereby, the average processing time at the time of random access is reduced.

Although the reordering function improves the throughput of the disk device in this way, there is a problem that the maximum response time becomes longer. This is because a command that minimizes the positioning time for the next command is selected, and a phenomenon occurs in which a certain command is not scheduled while waiting for a long time.

In order to solve this phenomenon, the disk device has a function of designating an ordered task in addition to a simple task designating that the reordering is good. When a command is requested by designating an ordered task, the disk device completes all commands that have been received and have not been completed, and then schedules the command of the ordered task. In this way, response assurance and priority control are performed.

Further, forcibly placing a command at the head of a queue is realized by a tag attached to the command.

[0008]

On the other hand, there are several access patterns in actual disk drive access. Many applications expect a fast response to random access. On the other hand, for example, an application that handles audio and moving images expects a certain throughput for sequential access.

The command reordering function considers only the seek and rotation wait times. Therefore, when sequential access and random access coexist, there is a problem that, for example, if sequential access is continuous, the response of random access drops. Occurs.

Further, in the case of the sequential access, the response can be made faster by prefetching the data in the cache in advance, but if the prefetch is performed without recognizing the access pattern, a sufficient effect cannot be obtained.

In order to solve such a problem, in a large-scale external storage device in which a large number of disk devices are provided in a disk control mechanism in a RAID configuration, disk access scheduling based on an access pattern is realized by firmware. Have been.

However, it is not cost-effective to connect such a large-scale disk control mechanism in a single disk device as a consumer device that handles a small amount of data. In addition, a typical OS of a current consumer machine does not perform disk input / output scheduling in consideration of such an access pattern.

Therefore, at present, the function of scheduling disk input / output in consideration of the access pattern is left to the application in the consumer machine.
However, the cost of creating an I / O scheduling routine for each application is quite large. Further, when there are a plurality of such applications, there is no guarantee that the scheduling operation will be performed as intended if they are operated simultaneously.

An object of the present invention is to provide a disk device having a disk access scheduling function based on an access pattern in the device itself.

[0015]

FIG. 1 is a diagram illustrating the principle of the present invention. As shown in FIG. 1A, the disk device of the present invention includes a pattern determining unit 46 and a schedule mechanism 50. The pattern determination unit 46 determines an access pattern of a command received from a host device such as a host or a server.

The schedule mechanism 50 has queues 70, 72, 74, and 76 for each access pattern, stores commands in queues corresponding to the access patterns determined by the pattern determination section 46, and performs disk access of the commands stored in the queues. Is scheduled in consideration of the access pattern.

As described above, the disk device of the present invention performs command scheduling based on an access pattern in the device, thereby guaranteeing a constant throughput for sequential access and providing a high-speed response to random access. Realized at low cost. By scheduling the command based on the access pattern by the disk drive alone, there is no need to change the OS or application on the host side.

The pattern determining section 46 sets an access pattern of data to be stored for each area of the disk, and determines the access pattern from a command address. Further, the pattern determining unit 46 may determine the access pattern based on the tag added to the command. Further, the pattern determining unit 46 may monitor the command sequence to find an access pattern, and determine which access pattern each command belongs to.

The pattern discriminating section 46 discriminates a read command and a write command from the host into, for example, sequential access and random access. In response to this, the schedule mechanism 50 includes a sequential read scheduler 60 having a sequential read queue 70, a sequential write scheduler 62 having a sequential write queue 72, a random read scheduler 64 having a random read queue 74, and a random write queue. It has a random write scheduler 66 having a.

Further, according to the present invention, the cache control mechanism 5
2. It has a reordering mechanism 88 and a disk time sharing mechanism 82. The cache control mechanism 52
The write data from the host device and the read data from the disk medium are processed on the cache memory 54. The reordering mechanism 88 queues commands and reorders commands in consideration of seek and rotation waiting time.

The time sharing mechanism 82 has a sequential queue 84 and a random queue 86, stores a command of a corresponding access pattern from the schedule mechanism 50, and the sequential queue 84 and the random queue 86 store commands and compete with each other. , The predetermined allocation time (quantum) τ1,
Scheduling for switching the τ2 in order to input a command to the reordering mechanism 88 is performed.

As described above, the present invention assumes sequential access, sequential write, random read, and random write as access patterns. Of course,
Other patterns can be supported as well.

The cache control mechanism 52 writes the write data according to the write command from the host to the cache memory 54 and terminates normally, and then schedules the write-back of the write data in the cache based on the queued write command. . The read data prefetched into the cache memory 54 is transferred by a cache hit of a read command from the host.

Further, according to the present invention, a disk time sharing mechanism (DTC) 82 for switching a command queued separately for sequential access and random access at an assigned time and inputting the command to a disk medium side.
By keeping the sequential access throughput at a constant value, the response of the random IO is guaranteed.

The following advantages are obtained by performing the two-layer disk access scheduling by the schedule mechanism 50 and the disk time sharing mechanism 82 as described above.

(1) Since sequential accesses of the same pattern are successively input to the reordering mechanism,
The seek time and the rotation wait are reduced, and the throughput and the response are improved as compared with the scheduling using the disk time sharing mechanism alone.

(2) When the sequential read queue of the schedule mechanism becomes empty, a prefetch command is input to the disk time sharing mechanism.
Throughput is improved compared to scheduling using the disk time sharing mechanism alone.

The pattern discriminating section 46 discriminates an access pattern for a read command and stores it in the sequential read queue 70 or the random read queue 74 of the schedule mechanism 50, and discriminates an access pattern for a write command and sends it to the cache control mechanism 52. After the transfer of the write data, the sequential write queue 72 or the random write queue 7
6 is stored.

The cache control mechanism 52 writes the write data to the cache memory 54 when the free space in the cache memory 54 is equal to or more than a predetermined value. Write data after discarding the
4, and if there is no discardable data, a busy response is sent to the host device.

The sequential read scheduler 60
When a command is stored in the sequential read queue 70, a certain amount of commands are input to the sequential queue 84 of the disk time sharing mechanism 82, and when the sequential read queue 70 is empty,
The prefetch processing unit 78 is activated and the subsequent prefetch command is input to the sequential queue 84 of the disk time sharing mechanism 82.

The sequential write scheduler 62
Sends commands to the sequential queue 84 of the disk time sharing mechanism 82 when the commands are stored in the sequential write queue 72.

When a command is stored in the random read queue 74, the random read scheduler 64 sends a certain amount of commands to the random queue 86 of the disk time sharing mechanism 82.

When a command is stored in the random write queue 76, the random write scheduler 66 does not perform scheduling when the free space of the cache memory 54 is equal to or more than a predetermined value, and the free space of the cache memory 54 is less than the predetermined value. , The write-back processing unit 80
Is started, and the write data commands stored in the cache memory 54 whose write data is within a certain range from the address of the oldest command are put together and the disk time sharing mechanism 8 is written from the random write queue 76.
2 is entered into the random queue 86.

The disk time sharing mechanism 82
If the command is stored in one of the sequential queue 84 and the random queue 86 and the other is empty, the allocation time τ1,
Regardless of τ2, commands are continuously input to the reordering mechanism 88 from the queue storing the commands.

Here, the reordering mechanism 88 schedules a plurality of commands so as to minimize the positioning time by designating the simple task, and after completing the command already received by designating the ordered task, reorders the ordered task. Schedule the specified command. In this case, the disk time sharing mechanism 82
Schedules commands stored in the sequential access queue 84 and the random access queue 86 separately for specifying a simple task and specifying an ordered task.

That is, the disk time sharing mechanism 8
Reference numeral 2 denotes a command for reordering commands from the sequential access queue 84 and the random access queue 86.
8, the first command immediately after switching the access pattern is to specify the ordered task, complete the command of the access pattern before switching, schedule the command of the access pattern after switching, and then Commands until the access pattern is switched are specified by a simple task, and a plurality of commands are scheduled so as to minimize the positioning time.

Therefore, a sequential access or random access command can be continuously input to the reordering mechanism 88 within one quantum.

The disk time sharing mechanism 82
The unprocessed processing time is predicted at the time of quantum switching, and the next quantum start time T0 is calculated (predicted). Each time a command is accepted or a command is completed, the unprocessed command processing time and the quantum start time T0 are calculated. The remaining time Tr is predicted on the basis of this, and when it is determined that there is a remaining time (Tr> 0), the command of the current quantum is input to the reordering mechanism 88, and when it is determined that there is no remaining time (Tr ≦ 0). Switches to the next quantum.

In order to benefit from reordering, it is necessary to create an environment for requesting as many commands as possible in the disk time sharing mechanism 82. When a simple task is used for this purpose, a plurality of commands are input to the reordering mechanism 88.

The disk time shelling mechanism 8 of the present invention
2 is intended to control the command processing time in a time-sharing manner. Therefore, when a command is input to the reordering mechanism 88, the time required for processing a plurality of input commands is predicted, and the quantum of the next access pattern is estimated. Then, it is necessary to determine whether or not to input a command of the switched access pattern after switching.

Therefore, at the time of quantum switching, the remaining time Tr is calculated by the following equation to determine whether the command currently input to the reordering mechanism 88 is completed within the next quantum and a new command can be input. I do. Remaining time Tr = quantum start time T0 + quantum allocation time τ-unprocessed command processing time-current time Quantum start time T0 = quantum switching time + unprocessed command processing time Unprocessed command processing time = number of unprocessed commands x command average processing Time When the disk time sharing mechanism 82 continuously issues commands of one access pattern to the reordering mechanism 88, the first command immediately after resetting the assigned time designates the ordered task and specifies the ordered task. After the command is completed, the command input after the reset is scheduled, and the command until the next reset is specified by a simple task and the scheduling is performed so as to minimize the positioning time.

Even in the case where the quanta of one access pattern continues as described above, in order to reset the quantum start time to the current time, the first command to the reordering mechanism 88 after resetting the quantum is sent to the ordered task. , It is possible to prevent the response time from being prolonged, which is an adverse effect caused by reordering.

The present invention provides a method for controlling a disk drive that schedules disk access based on an access pattern. In this control method, an access pattern of a command received from a host device such as a host is determined; a read command is input to a queue corresponding to the determined access pattern; a write command transfers write data from a host to a cache. The command is input to the queue corresponding to the access pattern determined from the above; the input of the command from each queue to the disk time sharing mechanism is scheduled at regular time intervals according to the access pattern; , The disk area accessed by the command, the tag attached to the command, or the command string.

In this disk device control method, sequential access and random access are determined as an access pattern of a read command or a write command, and a command is divided into a sequential read queue, a sequential write queue, a random read queue, or a random write queue. Is stored; stored in the sequential queue and the random queue of the time sharing mechanism and competed with each other. In this case, a command is input to the reordering mechanism by sequentially switching the predetermined allocation time (quantum) of each queue.

In the method of controlling a disk drive, when a command is stored in the sequential read queue, a fixed amount of commands is input to the sequential queue of the time sharing mechanism. When the sequential read queue is empty, Subsequent prefetch commands are input to the sequential queue of the time sharing mechanism; if commands are stored in the sequential write queue, all commands are input to the sequential queue of the time sharing mechanism, and the random read queue is input. If a command is stored in the random queue, a certain amount of the command is input to the random queue of the time sharing mechanism; if a command is stored in the random write queue, the free space of the cache memory is equal to or more than a predetermined value. When the free space of the cache memory is less than a predetermined value, the write data stored in the cache memory collects commands having write data within a certain range from the address of the oldest command. The write data in the cache memory is preferentially written back to the disk medium by entering the random queue of the time sharing mechanism; the details of the control method of the disk device other than this are the same as those of the device.

[0046]

FIG. 2 is a block diagram of a hard disk drive to which the present invention is applied. In FIG. 2, the hard disk drive includes a SCSI controller 10, a drive control 12, and a disk enclosure 14. Of course, the interface with the host is not limited to the SCSI controller 10, and an appropriate interface controller can be used.

The SCSI controller 10 has an MCU
(Main control unit) 16, Memory 1 using DRAM or SRAM used as control storage
8. A program memory 20 using a nonvolatile memory such as a flash memory for storing a control program, a hard disk controller (HDC) 22, and a data buffer 24 are provided.

The drive control 12 is provided with a drive interface logic 26, a DSP 28, a read / write LSI 30, a servo demodulator 32, and a servo driver 34.

Further, a head IC 36 is provided in the disk enclosure 14, and a composite head 38-1 to 38 having a write head and a read head is provided for the head IC 36.
-6 is connected.

The composite heads 38-1 to 38-6 are provided for each recording surface of the magnetic disks 40-1 to 40-3.
The magnetic disk 40-1 is moved to an arbitrary track position by driving the rotary actuator by the CM 44. The magnetic disks 40-1 to 40-3 are rotated at a constant speed by a spindle motor 42.

The hard disk controller 22 of the SCSI controller 10 has an access pattern schedule mechanism in the present invention in addition to the formatter and the ECC processing unit.

This access pattern schedule mechanism uses sequential read, sequential write,
Assuming four types of random read and random write, an access pattern is determined when a command is received, the command is stored in a command queue provided for each access pattern, and then command scheduling is performed in consideration of the access pattern.

The hard disk controller 22 is provided with a cache control mechanism. The cache area in the data buffer 24 is used as a cache memory, and write data from the host and read data from the magnetic disk are processed on the cache memory. I do.

The drive interface logic 26 provided in the drive control 12 has a reordering mechanism. This reordering mechanism has a command queue and the hard disk controller 22.
For the commands input from the access pattern schedule mechanism according to the present invention provided in the above, the positioning time defined by the sum of the seek time and the rotation wait time from the commands waiting for execution stored in the command queue is minimized. The command is selected as the next command to be executed, and the reordering process is performed.

FIG. 3 is a block diagram showing a functional configuration of the access pattern schedule mechanism according to the present invention provided in the hard disk drive of FIG.

Referring to FIG. 3, the access pattern scheduling mechanism according to the present invention includes a host interface 4 provided as a function of the hard disk controller 22.
5, a pattern discriminator 46, a schedule mechanism 50, a cache control mechanism 52, a cache memory 54, a disk time sharing mechanism (DTC) 82, and a reordering mechanism 88 provided on the drive interface logic 26 side.

The host interface 45 is, for example, an SCS
It functions as a target for the initiator on the host side in the I interface.

The pattern determining section 46 determines a command pattern for a command received from the host via the host interface 45. In this embodiment, four command patterns (1) sequential read, (2) sequential write, (3) random read, and (4) random write are supported. Of course, patterns other than these four access patterns can be similarly supported.

The pattern discriminating section 46 specifies an access pattern of data to be stored for each area of the magnetic disk in advance, and compares an address when a read command or a write command is received from the host with information for specifying the disk area. This determines the command pattern.

The designation of the disk area for each command pattern can be performed by the user from the host using a command. For example, in the case of SCSI, four access patterns, sequential read, sequential write, and random read, are used for a partition defined by a logical block address LBA0 as a disk area of a magnetic disk medium by a user specification using a vendor unique command. In addition, the correspondence between the partition and the partition for the random write is designated, and this is stored as the disk area designation information 48.

The table information of the partition specified in association with the access pattern is obtained by comparing the address of the command received from the host with the disk area to be accessed because the start address and the end address of the table are known. Is determined, and if the disk area is known, the type of access pattern can be determined from the disk area designation information 48.

The cache control mechanism 52 provided subsequent to the pattern discriminating section 46 has a cache table 5 for managing cache data stored in the cache memory 54.
6 and an LRU management unit 58 that manages the disposal of cache data existing in the cache memory 54.

The cache control mechanism 52 responds to a read command or a write command moved from the host via the host interface 45 and the pattern discriminating unit 46.
By referring to the cache table 52, the cache memory 54
When a cache hit in which the read data is present is determined, the command is normally completed in response to the host using the cache data in the cache memory 54 as the read data.

If there is no read data in the cache memory 54, the result of the determination of the read command by the pattern determining section 46, that is, the read data is processed through the schedule processing by queuing the command to the schedule mechanism 50 according to the sequential read or the random read. To respond.

When the cache control mechanism 52 receives a write command from the host, if there is a free area of a certain value or more in the cache memory 54, the write data from the host is transferred to the cache memory 54 and written. Then, the host is notified of the normal end of the write command.

At the same time, the write command is discriminated by the pattern discriminating section 46 to determine the type of the access pattern, then queued to the schedule mechanism 50 side, and the write data in the cache memory 54 based on the queued write command is written to the magnetic disk. Do the back.

The schedule mechanism 50 divides the four access patterns identified by the pattern identification section 46 into sequential read, sequential write, random read, and random write, and schedules commands in consideration of each access pattern.

For this purpose, the scheduling mechanism 50 is provided with a sequential read scheduler 60, a sequential write scheduler 62, a random read scheduler 64, and a random write scheduler 66. Each of these schedulers 60, 62, 64, 66 has a sequential read queue 70, a sequential write queue 72, a random read queue 7
4 and a random write queue 76 are provided.

Further, the sequential read scheduler 6
0 is provided with a prefetch processing unit 78, and the random write scheduler 66 is provided with a write-back processing unit 80.

The schedule mechanism 50 operates at regular intervals.
Operate a sequential read scheduler 60, a sequential write scheduler 62, a random read scheduler 64, and a random write scheduler 66,
The commands of the queues 70, 72, 74, 76 are transferred to the sequential queue 84 or the random access queue 8 provided in the disk time sharing mechanism 82.
6 is performed, and this scheduling takes a process specific to each access pattern.

First, the sequential read scheduler 6
0 indicates that if a command is stored in the sequential read queue 70, a certain amount of the command is input to the sequential queue 84 of the disk time sharing mechanism 82.

When the sequential read queue 70 becomes empty due to the input of this command, the prefetch processing unit 78 is started to transmit the subsequent prefetch command to the sequential queue 8 of the disk time sharing mechanism.
Put into 4.

For this reason, even if the command transfer takes time during the sequential read of the host and the sequential read queue 70 becomes empty, the prefetch processing unit 7
8, a subsequent sequential read command is generated as a prefetch command and input to the sequential queue 84 of the disk time sharing mechanism 82, whereby the drive interface logic 2
6, the sequential read data is prefetched on the cache memory 54 from the sequential read command prefetched via the reordering mechanism 88, and a cache hit of the prefetched data occurs on the cache control mechanism 52 side for the subsequent sequential read command. Thus, the sequential read throughput can be improved.

The sequential write scheduler 62
Sends all commands to the sequential queue 84 of the disk time sharing mechanism 82 when the commands are stored in the sequential write queue 72. The input of the sequential write command into the sequential queue 84 is performed by transferring the sequential write command from the host to the cache memory 54 and scheduling the write back of the write data in the cache memory 54 to the magnetic disk after the host completes the normal write command. Will be done.

As a result, the write-back efficiency of the sequential write data transferred to the cache memory 54 is improved, and the write-back on the cache memory 54 becomes discardable data by the write-back. It is possible to sufficiently secure a free area on the cache memory 54 for data.

When a command is stored in the random read queue 74, the random read scheduler 64 submits a certain amount of commands to the random access queue 86 of the disk time sharing mechanism 82.

Further, the random write scheduler 66
When a command is stored in the random write queue 76, if the free space in the cache memory 54 is equal to or larger than a predetermined value, scheduling is not performed and the cache memory 5
When the free space of No. 4 becomes smaller than the predetermined value, the command having the oldest write data among the commands stored in the random write queue 76 and other commands of the write data within a certain range from the address of the write data are deleted. A scheduling for preferentially writing back is performed.

The disk time sharing mechanism 82
For the commands in the sequential queue 84 and the random access queue 86 which have received the commands scheduled in consideration of the access pattern by the schedule mechanism 50, the predetermined sequential access allocation time τ1 and random access allocation time τ2 are sequentially set. And the command is input to the command queue 92 of the reordering mechanism 88.

When the command is stored in only one of the sequential queue 84 and the random access queue 86, the command is continuously transmitted from the queue storing the command to the reordering mechanism 88 regardless of the allocation times τ1 and τ2. And then throw it in.

This disk time sharing mechanism 82
For the sequential access and the random access, the scheduling is performed by time sharing in which the allocation times τ1 and τ2 are determined, and the throughput is guaranteed for the sequential access, and the response performance is guaranteed for the random access.

Further, the disk time sharing mechanism 82
Schedules the designation of the simple task and the ordered task separately when the command is input to the reordering mechanism 88. That is, when the disk time sharing mechanism 82 sends a command from the sequential queue 84 and the random access queue 86 to the command queue 90 of the reordering mechanism 88, the first command immediately after switching the access queue specifies an ordered task. By the designation of the ordered task, the reordering mechanism 88 completes the command stored two hours ago and then schedules the command after switching.

The disk time sharing mechanism 82
After specifying the command immediately after the queue switching in the ordered task, specify the simple task for the command until the next queue switching, and by specifying this simple task, the reordering mechanism 88 minimizes the positioning time. Schedule the execution order of several commands.

By specifying the ordered task immediately after the switching and the simple task until the next switching, the sequential access or random access command can be reordered within one allotted time.
Can be supplied continuously.

In this case, when a command is input to the reordering mechanism 88, the disk time sharing mechanism 82 estimates the time required for processing the plurality of input commands and switches to the allocation time of the next access pattern. Thereafter, it is determined whether or not to input a command of the switched access pattern. The scheduling of the disk time sharing mechanism 82 will be further clarified in a later description.

FIG. 4 is a flowchart of the access pattern schedule process according to the present invention in FIG.
This is a process activated by the interrupt process.

In FIG. 4, the interrupt is determined in step S1, and when the interrupt is determined, the process proceeds to step S2.
Check if it is a scheduling interrupt. If it is a scheduling interrupt, the process proceeds to step S3, and the scheduling is performed by the schedule mechanism 50 of FIG. 3 in consideration of the access pattern.

If a command acceptance interrupt is determined in step S4, a command acceptance process in step S5 is performed. The command receiving process includes a command receiving process of performing a process for specifying a disk area for each access pattern in the command pattern determining unit 46 of FIG. 3 and a process of receiving a normal write command or a read command.

Further, if it is determined in step S6 that a command end interrupt has occurred, a command end process is performed in step S7. This command end process is to execute an interrupt process in response to the end response of the command which is scheduled by the schedule mechanism 50 of FIG. 3 and input to the disk time sharing mechanism 82 side. Further, in the case of other command interruption, a process corresponding to the other interruption is performed in step S8.

FIG. 5 is a flowchart showing details of the command receiving process in step S5 in FIG. This command accepting process is performed by the command pattern determining unit
6.

First, it is checked in step S1 whether the command is an access pattern association command. In the embodiment shown in FIG. 3, since the user sends a SCSI vendor unique command, for example, as an access pattern association command from the host side to specify a disk area for each access pattern, the access pattern association command is determined. Then, the process proceeds to step S2, where an access area of each pattern is set for sequential and random.

That is, a relationship with, for example, a partition of a magnetic disk medium is set corresponding to four access patterns of sequential read, sequential write, random read, and random write, and this is set to the disk area of the pattern discriminating section 46 in FIG. It is stored as the designation information 48.

If the disk area setting process in step S2 ends normally in step S3, a normal end response is returned to the host in step S4, and subsequent read commands and write commands are set according to the access pattern according to the present invention. Schedule processing can be performed. If the setting of the disk area for each access pattern cannot be performed normally, an abnormal end response is returned to the host in step S5.

On the other hand, if a command other than the access pattern association command is received in step S1, it is a normal read command or write command, and the process proceeds to the normal command processing in step S6.

FIG. 6 is a flowchart showing details of the normal command processing in step S6 of FIG. This normal command process is a command process for a read command and a write command from the host.
A command data block having a format as described above is received and processed.

FIG. 7A shows a read command data block used in SCSI, which is 5-byte command data. A command code "0A" indicating read is stored in the first byte 0, and bytes 1 to 3 are stored. This is a logical block address field, and stores the head address of read data in the logical block address.

Byte 4 is the number of transfer blocks, and the number of logical blocks can be specified up to a maximum of 256 logical data blocks. If the field of the number of logical blocks is 0
In the case of, transfer of 256 logical data blocks is specified,
When it is other than 0, the number of logical data blocks to be transferred is specified.

FIG. 7B shows a write command data block, which is 5 bytes of command data, like the read command data block shown in FIG.
The code "08" of the write command is stored in the "." The next bytes 1 to 3 are a logical block address field, which specifies the start address of the write data in the logical block address field. Byte 4 is the number of transfer blocks, and up to 256 logical data blocks can be specified.

When the transfer block number field is 0, the transfer of write data of 256 logical data blocks is designated, and when the value is other than 0, the number of logical data blocks of write data to be transferred is designated.

The normal command processing of FIG. 6 for receiving such a read command and a write command is as follows. First, it is checked in step S1 whether the command is a read command. If accepting a read command,
The cache memory 54 in the cache control mechanism 52
The process proceeds to step S2 on condition that the read data is a mishit.

In step S2, the pattern discriminating section 46 discriminates whether the pattern of the read command is sequential read or random read, and queues the corresponding access pattern. The command is stored in the queue 70, and if it is a random read read command, it is stored in the random read queue 74 of the random read scheduler 64.

If the received command is a write command in step S1, the flow advances to step S3 to check whether the free space of the cache memory 54 is equal to or more than a predetermined value. If the free space in the cache memory 54 is equal to or more than the predetermined value, the write data is transferred to the cache memory 54 in step S4, and the host normally ends.

Then, the process proceeds to a step S2, wherein the access pattern of the received write command is determined by the pattern discriminating section 46.
In the case of sequential write, the write command is stored in the sequential write queue 72 of the sequential write scheduler, and in the case of random write, the write command is stored in the random write queue 76 of the random write scheduler 66. I do.

If the free space in the cache memory 54 is not equal to or more than the predetermined value in step S3, the process proceeds to step S5, where the cache table 5
Check whether there is any discardable data by referring to step 6. If there is discardable data, at step S6 the cache memory 5
After discarding the data from step S4, the process returns to step S3. If the data free space becomes equal to or larger than a predetermined value, the write data is transferred to the cache memory 54 in step S4, and the write command corresponding to the access pattern is transferred in step S2. The data is stored in the sequential write queue 72 or the random write queue 76.

If there is no discardable data in the cache memory 54 in step S5, a busy is notified to the host in step S7, and the process ends.

FIG. 8 is a flowchart showing details of the scheduling process in step S3 of FIG.
This scheduling process is performed by the scheduling mechanism 5 shown in FIG.
0 is a process for scheduling a command stored in a queue corresponding to an access pattern at regular intervals and inputting the command to the queue of the disk time sharing mechanism 82.

Referring to FIG. 8, in the scheduling process executed by interruption every predetermined time, first, in step S1, there are commands in queues 70, 72, 74 and 76 corresponding to the four access patterns provided in the schedule mechanism 50. It is checked whether or not there is no command, and if there is no command, the process is terminated.

According to the type of the access pattern, if the queued command is a sequential read command in step S3, the flow advances to step S4 to execute sequential read scheduling by the sequential read scheduler 60.

If the command queued in step S5 is a sequential write, the flow advances to step S6 to execute sequential write scheduling by the sequential write scheduler 62.

If the queued command is a random read in step S7, the flow advances to step S8, and the random read scheduler 64 executes random read scheduling.

If the queued command is a random write, the flow advances to step S9 to execute random write scheduling by the random write scheduler 66. Each scheduling of the sequential read, the sequential write, the random read, and the random write in the scheduling process is clarified in FIGS. 9, 10, 11, and 12, respectively.

FIG. 9 is a flowchart of the sequential read scheduling in step S4 in FIG.
The sequential read scheduling is executed by the sequential read scheduler 60 in FIG.

First, in step S1, it is checked whether or not the sequential read queue 70 is empty. If the read command is confirmed, the process proceeds to step S2, where a fixed amount of commands are input to the sequential queue 84 of the disk time sharing mechanism 82. .

When the sequential read queue 70 becomes empty in step S3 due to the input of this command, the prefetch processing unit 78 is started in step S4,
A subsequent prefetch command is generated and input to the sequential queue 84 of the disk time sharing mechanism 82, and the process ends.

On the other hand, if the sequential read queue 70 is empty during the sequential read in step S1, the process proceeds to step S5, where the prefetch processing unit 78 generates a subsequent prefetch command and generates the disk time sharing mechanism 82. To the sequential queue 84.

FIG. 10 is a flowchart of the sequential write scheduling in step S6 of FIG. 8, and the sequential write scheduler 62 of FIG.
Done in In this sequential write scheduling, the sequential write queue 72
Are sent to the sequential queue 84 of the disk time sharing mechanism 82.

FIG. 11 is a flowchart of the random read scheduling in step S8 in FIG. 8. The random read scheduler 64 in FIG. 22 transmits a certain amount of commands stored in the random read queue 74 to the disk time sharing mechanism 82. Input to the random queue 86.

FIG. 12 shows the random write scheduling in step S9 in FIG. 8, which is executed by the random write scheduler 66 in FIG. In this random write scheduling, it is checked in step S1 whether the free space of the cache memory 54 is equal to or larger than a certain value.
If the free space is equal to or more than a certain value, scheduling is not performed even if a command is stored in the random write queue 76.

If the free space in the cache memory 54 is not equal to or larger than the predetermined value in step S1, the write-back processing unit 80 writes the write data in the cache memory 54 back to the magnetic disk to generate discard data. Perform priority write-back processing.

That is, in step S 2, among the write data in the cache memory 54 corresponding to the write command stored in the random write queue 76, the write data corresponding to the write data within a certain range from the address of the oldest write command are corresponded. The written write command is sent from the random write queue 76 to the random queue 86 of the disk time sharing mechanism 82 together with the oldest write command, and priority write-back processing for writing old write data back to the disk medium is scheduled.

FIG. 13 is a flowchart of the command end processing in step S7 in FIG. This command end processing is performed by the schedulers 60, 62, 6 corresponding to each access pattern in the schedule mechanism 50 of FIG.
4 and 66 perform processing in cooperation with the cache control mechanism 52.

The command end processing is executed when a normal end notification of a command scheduled by the disk time sharing mechanism 82 to the reordering mechanism 88 is received as a command end interrupt.

First, in step S1, the type of an access pattern of a sequential read, a sequential write, a random read, or a random write is determined for a command for which a command end interrupt has been performed.

If the end command is a sequential read in step S2, the flow advances to step S5 to make a connection request to the host. In step S6, the read data in the cache memory is read as discardable data after the host reads via the cache memory 54 and cached. It is managed on the table 56.

If the end command is a random read in step S3, the flow advances to step S7 to make a connection request to the host. In step S8, the read data transferred on the cache memory 54 is transferred to the host. Thereafter, the read data of the cache memory 54 is managed in the cache table 56 as discardable data.

Further, if it is determined in step S4 that the end command is a sequential write, the write data in the cache memory 54 has been written back in step S9 and can be discarded. I do.

If the end command is a random write, the process returns to the main routine without performing any special end processing.

The write data of the random write which is not subjected to the command end processing is managed by the LRU management unit 58 provided in the cache control mechanism 52. That is, when write data of random write is written to the cache memory 54, the same write data may be repeatedly accessed by the host. Therefore, the write data cannot be discarded at the end of the write command. The LRU management unit 58 manages that the host access of the write data of the random write in the cache memory is not performed, and the write data of the random write can be discarded at the end of the access time sequence by the LRU management. Data.

FIG. 14 is a block diagram of an embodiment of the disk time sharing mechanism (DTC) of FIG.

The disc time sharing mechanism 82
Commands from the schedule mechanism 50 are grouped into a sequential access and a random access, a ratio of time for each group to use the disk device is defined, and a quantum in which each group can continuously use the disk device based on the defined time ratio. (Allocation time) is determined, and when a request is received from a plurality of groups, quantum is sequentially switched between the competing groups to schedule the disk device to be used.

If there is only one group of commands, scheduling is performed so that disk devices can be used continuously for the commands of that group.
The configuration and function of each unit in FIG. 3 for realizing such disk time sharing of the present invention will be described in more detail as follows.

The disk time sharing mechanism 82
It includes control information 92, a command receiving unit 94, a command schedule unit 95, and a command completion processing unit 96. The command schedule unit 95 refers to and updates the control information 92 to perform disk time sharing scheduling.

The control information 92 exemplifies a case where a command is defined by dividing the command into two, a sequential group G1 and a random group G2. The sequential queue 8 for waiting for a schedule corresponds to the groups G1 and G2.
4 and a random queue 86 are provided.

In the sequential queue 84 and the random queue 86 for waiting for the schedule, the commands received by the command receiving unit 94 are divided into a sequential command and a random command and stored in the FIFO constituting the queue.

A sequential queue 85 for waiting for completion and a random queue 87 corresponding to the groups G1 and G2.
Is provided. In the completion waiting queues 85 and 87, the reordering mechanism 8 of the drive interface logic 26 is provided.
After the command has been input to No. 8, commands that have not received a command completion response are queued by being stored in the FIFO constituting the queue.

Further, a sequential quantum 98-1 and a random quantum 98-2 are provided corresponding to the groups G1 and G2. This quantum 98-1,98
-2, the groups G1 and G2 have the reorder link mechanism 8
8, the ratios α1 and α2 of the times in which the respective groups G are used are defined based on the defined ratios α1 and α2.
Quantum τ1 and τ2, which are allocated times for which the reordering mechanism 88 can use the reordering mechanism 88 continuously, are determined and stored.

For example, assuming that the time sharing cycle for performing one time sharing is Tc, the group G1
The quantum τ1, τ2 of G2 is defined by the following equation.

Τ1 = α1 · Tc τ2 = α2 · Tc The appropriate values of the quantum τ1 and τ2 that determine the use of the disk devices of the groups G1 and G2 are determined as follows. First, if the quantum is set too small, it will approach the command processing time of the disk device, and the effect of reordering to select a command so as to minimize the positioning time will be reduced, thus lowering the overall command processing performance.

Conversely, if the quantum value is too large, the average command processing time and the maximum command processing time will be prolonged because the quantum waiting time for switching to another group will increase. For example, if the quantum τ1 and the quantum τ2 are set to one hour, respectively, the quantum τ2 command cannot be executed during the processing of the quantum τ1, so that the quantum τ2 command waits for the quantum τ1 to end for one hour.

According to an experiment conducted by the inventor of the present application, in the case of a disk device having an average command processing time of several ms to 20 ms,
The value of the quantum is desirably several tens ms to several hundreds ms.

Further, the control information 92 includes a current quantum type 100, a current quantum start time 102, and a next command task type 104. In the current quantum type 100, an identifier of a group that is currently using the reordering mechanism 88 is set.

The current quantum start time 102 is set to the time T 0 at which the current quantum set in the current quantum type 100 has started. Further, in the next command task type 104, whether the next command request to the reordering mechanism 88 is a simple task or an ordered task is set. This next command task type 10
The simple task or the ordered task set to 4 is performed to make full use of the function of the reordering mechanism 88.

Here, the reordering mechanism 88 selects a command that minimizes the positioning time given by the sum of the seek time and the rotation time from the commands waiting to be executed as the next command to be executed.

When a command is issued to such a reordering mechanism 88, if a simple task is specified, it is notified that the task can be reordered. The reordering mechanism 88 that has received the command specifying the simple task schedules the commands in such an order as to minimize the positioning time.

However, since the reordering mechanism 88 always selects a command that minimizes the positioning time, a phenomenon occurs in which a certain command is not scheduled while waiting for a long time. In order to solve this phenomenon, the reordering mechanism 88 has an ordered task function in addition to the simple task.

When a command is issued with an ordered task specified, the reordering mechanism 88 schedules the ordered task command after completing all of the commands that have been inherited and have not been completed.
Therefore, it is possible to suppress the extension of the maximum response time of the command by mixing the ordered tasks between the simple tasks.

In the disk time sharing mechanism 82 of the present invention, the first command after switching the quantum issues a command to the reordering mechanism 88 by designating the ordered task, and the command before the quantum switching is still executed. Execute the next quantum command after completing the unfinished command. For this reason, a simple task is specified for the second and subsequent commands after switching to quantum.

When there is only one group command, the group is repeated while resetting the quantum in order to continue the schedule. In this case, the first command immediately after resetting the quantum is requested by an ordered task, and after the command that has not been completed in the previous quantum is completed, the command in the reset quantum is scheduled.

As a result, it is possible to prevent an increase in the maximum response time when a plurality of groups of commands compete with each other and when only one group of commands continues.

FIG. 15 shows the command schedule section 9 provided in the disk time sharing mechanism 82 of FIG.
5 is an example of a schedule according to No. 5;

In FIG. 15, regarding the sequential and random groups G1 and G2, when the command is stored in the sequential queue 84 and the random queue 86 of the control information 92, the groups G1 and G2
Each command is scheduled in the order of the groups G1 and G2 according to the quantum τ1 and τ2 determined for each G2, and the commands are issued to the reordering mechanism 88.

For example, during the quantum τ1 from time t0, two commands of the sequential group G1 are scheduled. Quantum switching is performed when the time when the command is completed exceeds the current quantum switching time.
Switch to the next random group quantum τ2. This switching is determined by the following equation. (Current quantum command start time) <(current quantum start time + quantum) (1) That is, if the expression (1) is satisfied, a command of the sequential group G1 corresponding to the current quantum type is issued to the reordering mechanism 88, If not, the quantum is switched to the next quantum of the random group G2.

The quantum τ of the next random group G2
Between two, for example, six commands are scheduled. Further, when the quantum τ2 elapses at time t2,
The sequential group G1 is switched to the quantum τ1 again, and, for example, three commands are scheduled. In the same way, the sequential access command and the random access command are scheduled by switching the quantum holding times τ1 and τ2 in the same manner.

FIG. 16 shows an example of the time sharing process when only the commands of the sequential group continue. In FIG. 16, it is assumed that at time t0, only the commands of the sequential group G1 are arranged in the sequential queue 84 of FIG. 14, and the random queue 86 of the random group G2 is empty.

In this case, after scheduling two sequential commands at the quantum τ1 of the sequential group G1 from the time t0, the quantum τ1 of the same sequential group G1 is restarted by resetting the quantum τ1 at the time t1. For example, schedule three sequential commands.

As described above, when only one group of commands is in a waiting state, the quantum is reset to continuously schedule one group of commands.

Further, in FIG. 16, when the commands of the groups G1 and G2 enter a conflicting state at time t2, switching to the next quantum τ2 is performed. However, there are only three commands of the random group G2 in the quantum τ2, and the time t during the quantum τ2
At 3, three commands are interrupted.

In this case, the sequential group G
Since there is a command in the waiting state at time t1, the time is switched to quantum τ1 at time t3, and the sequential group G1
For example, three commands are scheduled.

In the disk time sharing schedule shown in FIG. 15 and FIG. 16, the command issued to the reordering mechanism 88 is issued by the ordered task immediately after the quantum is switched, and the next and subsequent commands are issued. The command up to the quantum switch is issued by a simple task.

In order to utilize the function of the reordering mechanism 88 in this way, the time until all the commands issued when the quantum is switched is predicted, and the predicted time is within the quantum after the switching. If so, a command is issued after the switch, and if the predicted time exceeds the quantum after the switch, a command is not issued after the switch, and the switch to the next quantum is waited.

In order to benefit from the reordering process, the disk time sharing mechanism 82 sends as many commands as possible to the reordering mechanism 8.
This is to create an environment for issuing to 8.

When using the simple task, the disk time sharing mechanism 82 issues a plurality of commands to the reordering mechanism 88. Since the disk time shelling mechanism 82 aims to control the command processing time in a time-sharing manner, when issuing a command, it estimates the time required to read and write a plurality of issued commands to the disk, and then executes the next quantum operation. It is necessary to determine whether or not to input a command of the quantum type after the switching after the switching.

Therefore, the remaining time τ is determined in order to determine whether the command currently requested at the time of quantum switching is completed in the next quantum and a new command can be input.
Calculate r by the following formula. τr = T0 + τ−Tw−Tnow (2) where T0 is the quantum start time (predicted value) τ is the quantum allocation time Tw is the unprocessed command processing time (predicted value) Tnow is the current time T0 = Ts + Tw (3) , Ts is the quantum start time before switching Tw = N × Ta (4) where N is the number of unprocessed commands Ta is the average processing time of commands for each access type Here, the unprocessed commands are sent to the reordering mechanism 88. A command that has been issued and has not returned a completion response.
In the case of the embodiment of the present invention, the unprocessed commands include a pre-unprocessed command, a pre-pre-processed command, and an all-unprocessed command, and the unprocessed commands of the immediately preceding quantum and the unprocessed commands of the immediately preceding quantum, respectively. Command, and all outstanding commands through quantum.

The quantum start time T0 is also a predicted value, and is predicted when the switching to the current quantum is determined based on the prediction of the remaining time of the previous quantum. At this time, the time Tw required for the reordering mechanism 88 to complete the processing of all the unprocessed commands of the previous quantum is predicted by equation (4), and the end time of the previous quantum, that is, the start time T0 of the current quantum, is calculated. The prediction is made by the equation (3).

The remaining time Tr in the equation (2) is calculated when the disk time sharing mechanism 82 receives a new command or when a command completion response is received from the reordering mechanism 88, and the remaining time Tr is calculated. If Tr> 0, it is determined that there is remaining time, and the command of the current quantum is issued to the reordering mechanism 88. If Tr ≦ 0, it is determined that there is no remaining time, and the quantum is switched.

Here, the average command processing time T of the disk drive used for calculating the remaining time Tr in the above equation (2)
The method of calculating a is, for example, an average value of the last n command processing times. In this case, n may be a finite value of, for example, n = 10, or may be, for example, n = ∞, that is, all commands from the start of the system.

Further, the average value of the command processing time can be calculated by either a method of calculating an average value for each group or a method of calculating an average value of all groups.

On the other hand, when a large amount of data is accessed as in the case of sequential access, the average command processing time Ta is predicted from the amount of data to be accessed and the disk transfer capability because the positioning time is shorter than the data transfer time. In this case, the positioning time depends on the degree of benefit of the reordering process, that is, the number of commands to be reordered at that time, the distribution of addresses of individual commands, and the like. In the case of, the proportion of the positioning time to the processing time is small. In this case, the processing time is predicted to be (average positioning time) + (data transfer time).

For example, when accessing 1 MB of data with a disk drive having a transfer speed of 20 MB / s, an average rotation waiting time of 3 ms, and an average seek time of 5 ms, the transfer time is 52 ms while the average positioning time is 8 ms.
Therefore, the processing time is 60 ms, which is the sum of the two.

FIG. 17 shows an example of prediction of the remaining time at the time of quantum switching. FIG. 17A shows a case where sequential access and random access are alternately switched.
This is an example in which time elapses from (J) to (J).

FIGS. 17A and 17B show an example of predicting the next quantum start time T0 when switching from random access to sequential access. It is assumed that the remaining time of the random access becomes insufficient at the current time Tnow at which the random access is switched. At this time, the completion response of the three commands of the sequential access of the previous quantum and the random access of the current quantum has not been returned, and is being processed.

In this case, as shown in FIG. 17B, the time Tw1 until all the commands being processed are completed is predicted by the equation (4), and the start time T0 of the next sequential access is calculated from the equation (2). decide. The quantum is switched to the sequential access quantum.

FIGS. 17C to 17F show examples in which the remaining time is predicted and it is determined that there is a remaining time. It is assumed that after switching to sequential access in FIG. 17B, the disk time sharing mechanism 82 receives one command of sequential access at the current time Tnow. At this time,
As an unprocessed command for which the completion response of the command issued to the reordering mechanism 88 has not been returned, there is one random access command. That is, the reordering mechanism 88 is processing one random access command of the previous quantum.

In this case, as shown in FIG. 17E, the processing of one random access command is performed by the reordering mechanism 8.
The time Tw2 until completion at step 8 is predicted by equation (4), and FIG.
Using the quantum start time T0 obtained in step 7 (B), the remaining time Tr2 is obtained from equation (2) as shown in FIG. 17 (F). In this case, since Tr2> 0, a sequential access command can be input to the reordering mechanism 88.

FIGS. 17G to 17J show examples in which it is determined that there is no remaining time in the remaining time prediction. It is further assumed that the time further advances, and the disk time sharing mechanism 82 receives one command of the sequential access at the current time Tnow in FIG.

At this time, there is one sequential access command as an unprocessed command for which a completion response of the command issued to the reordering mechanism 88 has not been returned. In other words, one of the current quantum sequential access
The command is being processed.

In this case, as shown in FIG. 17I, one command of the sequential access is transmitted to the ordering mechanism 88.
The time Tw3 to complete on the side is predicted by equation (4), and FIG.
Using the quantum start time T0 obtained in step 7 (B), the remaining time Tr3 is obtained from equation (2) as shown in FIG. 17 (J). In this case, since Tr3 <0, it is determined that there is no remaining time, and switching to the next random access is performed.

FIG. 18 is a flowchart of the control processing by the command schedule unit 95 provided in the disk time sharing mechanism 82 of FIG.

The disk time sharing process by the command schedule unit 95 is executed by the command receiving unit 94.
At the time when the command input from the schedule mechanism 50 in FIG.
The operation is performed in response to a call when the command end is notified to the schedule mechanism 50.

First, as shown in FIG. 15, the disk command schedule mechanism 82 shown in FIG.
In the following, a case will be described in which the quantum τ1 and τ2 are sequentially switched between the conflicting sequential access and random access groups to input a command to the reordering mechanism 88 to perform time sharing.

In step S1, the sequential queue 84 corresponding to the quantum identifier i = 1 set for the current quantum type is checked to determine whether there is a waiting command. If there is a waiting command in the sequential queue 84, the process proceeds to step S2, and it is checked whether there is an uncompleted command in the quantum two months before. Now, assuming that the quantum identifier i = 1 is the first schedule, there is no uncompleted command in the quantum immediately before, so the process proceeds to step S3, and the remaining time Tr is predicted from the equation (2).

Subsequently, at step S4, the remaining time Tr becomes Tr.
It is checked whether or not> 0, and if this condition is satisfied, it is determined that there is a remaining time, and the routine proceeds to step S8. Step S
4 is the current quantum sequential cue 8
4 is input to the command queue 90 of the reordering mechanism 88, and the next command task type information 10
Task 4 is set as a simple task.

Subsequently, the flow returns to step S1, and it is checked whether or not there is a waiting command in the sequential queue 84 of the current quantum.
Steps S3 and S8 are repeated. According to the command schedule in the quantum τ1 of the sequential group G1, Tr ≦ 0 in step S3, and if it is determined that there is no remaining time, the process proceeds to step S5 to determine whether there is a command waiting in the random queue 86 of the random group G2. Check if.

At this time, if there is a command waiting in the random queue 86 of the next group G2, the process proceeds to step S10, switching is made to the quantum τ2 of the next group G2, and the next task is ordered based on the next command task type information 104. Set. At the same time, the quantum current time T0
Is predicted from the equation (3), and the predicted T0 is set as the current quantum start time 102.

As a result, the quantum τ1 of the first sequential group G1 is switched to the quantum τ2 of the next random group G2, and step S1 is performed again.
The command of the next random group G2 accompanying the quantum switching is processed in steps S2, S3, S4, and S8.

At this time, since the next task is set to ordered in step S10, the first command after the quantum switching is input to the reordering mechanism 88 by designation of ordered. When the command has been input, the task of the next command task type information 104 is simply set.

Next, the processing in the case where commands of one group, for example, the sequential group G1 are consecutive as shown in the explanatory diagram of the schedule of FIG. 16 will be described. If the commands of the same sequential group G1 are continuously received, the processing of steps S1 to S4 is repeated at the quantum t1, and the commands of the same group are requested to the disk drive 24-1. If it is determined, the process proceeds to step S5, and it is checked whether or not there is a waiting command in the random queue 86 of the random group G2.

At this time, if there is no waiting command in the random read queue 86 of the random group G2 and it is empty, the flow advances to step S9 to reset the current quantum τ1 and set the next task to ordered, and at the same time, The current quantum time To is predicted and set to the current quantum start time, and the process returns to step S1. In this case, the current quantum type is left as it is.

For this reason, the next quantum after resetting the current quantum holding time τ1 has the same quantum holding time τ1, and when the command of the sequential group G1 continues, the same quantum τ1 is continued.

On the other hand, as shown after time t2 in FIG. 16, commands in group G1 continue from time t0 to t2, quantum .tau.1 continues by reset, and commands in the remaining random group G2 disappear by time t2. If accepted and stored in the random queue 86, the next random group G2 is switched to the quantum τ2.

However, if the random queue 86 of the random group G2 becomes empty in the middle of the quantum τ2 as shown at time t3 in FIG. 16 and it is determined in step S1 that there is no waiting queue, the process proceeds to step S6, where the quantum τ
It is checked whether or not there is a waiting command in the first sequential queue 84.

At this time, if there is a command waiting in the sequential queue 84, the process proceeds to step S7, and it is checked whether there is an uncompleted command in the previous quantum. If not, the process proceeds to step S10, where the quantum τ1 of the sequential group G1 is Switching, setting the next task to ordered, and predicting and setting the quantum start time T0,
By returning to step S1, the first command of the group G1 after switching is input to the reordering mechanism 88 in an ordered manner, and the next command is input by specifying the simple task through the processing of steps S1 to S4 and S8.

As described above, the sequential access command and / or random access command stored in the sequential queue 84 and the random queue 86 are:
The reordering mechanism 88 is sequentially arranged on a schedule according to the ratio of the quantum τ1, τ2 determined for each.
The minimum value can be guaranteed for each of the sequential access throughput and the random access response time.

FIG. 19 shows another embodiment of the access pattern scheduling according to the present invention. This embodiment is characterized in that an access pattern is determined from tag information of a command.

In FIG. 19, this embodiment is similar to the embodiment of FIG. 3 in that the host interface 45,
It comprises a pattern determination unit 46, a schedule mechanism 50, a cache control mechanism 52, a cache memory 54, a disk time sharing mechanism 82, and a reordering mechanism 88.

The pattern discriminating section 46 discriminates the access patterns of sequential read, sequential write, random read and random write based on the tag added to the command from the host. Scheduling.

Although the disk device of the present invention uses SCSI as an interface with the host, in the case of SCSI, the host-side initiator can attach a unique tag (ID) to each command by a queue tag message. .

Therefore, for the sequential read, sequential write, random read, and random write commands supported as access patterns on the host side, a sequential read tag, a sequential write tag, a random read tag, and a random write tag To transfer the command to the disk device of the present invention.

In response to such a command to which a tag designating an access pattern from the host has been added, the pattern discriminating section 46 shown in FIG. The tag information of the sequential read tag, the sequential write tag, the random read tag, and the random write tag is received by the designation, and stored as the tag designation information 106.

If the tag identification information of the command indicating the access pattern is stored in the pattern identification section 46 in this way, the access pattern is identified from the tag added to the command for the command received from the host thereafter. be able to.

FIG. 20 is a flowchart of the command receiving process in the pattern discriminating section 46 of FIG. In this command reception processing, it is checked whether or not the command received from the host in step S1 is an access pattern association command.

If the command is an association command, the flow advances to step S2 to execute sequential read, sequential write,
For each of the random read and the random write, the relationship between the designated tags is stored as the tag designation information 106. After the setting of the tag designation information is completed, the subsequent command reception from the host starts the normal command processing of step S6, and the normal command processing is the same processing as the embodiment of FIG. 3 shown in FIG. is there.

That is, the embodiment of FIG. 19 is similar to that of FIG. 3 except that tag designation information for designating the correspondence between the tag information added to the command shown in FIG. 5 and the access pattern is set.
This is the same as the embodiment.

FIG. 21 is a block diagram of another embodiment of the access pattern scheduling of the present invention for determining an access pattern from a command sequence.

The embodiment of FIG. 21 is the same as the embodiment of FIG. 3 except that the pattern discriminating section 46 stores command string designation information 108 for discriminating an access pattern from a command string received from the host. It is. The command sequence designation information 108 stored in the pattern determination unit 48 is information set by an access pattern association command from the host, for example, a vendor unique command.

The command string designation information 108 is information for judging the address relationship of the command received from the host. For example, for sequential access,
If the transfer block number of the read command data block or the write command data block shown in FIG. 7 is 0 indicating the maximum number of logical blocks 256, it is determined that the access is sequential.

Since the last command of the sequential access cannot be accurately determined only by the number of transfer blocks, the last address of the previous command and the start address of the current command are compared for the addresses of two consecutive commands. Are equal to or less than a predetermined value of, for example, about two blocks, it is determined that the access is sequential.

As described above, the criterion for judging whether or not the access is sequential access with respect to the number of blocks of each command and the address relationship between the preceding and succeeding commands is based on the command sequence designation information 10.
8 is stored in the pattern determination unit 46.

FIG. 22 is a flowchart of a command accepting process in the pattern determining section 46 of FIG. In this command accepting process, it is checked in step S1 whether the accepting command from the host is an access pattern association command.

If the command is an association command, the flow advances to step S2 to create and store the determination criteria for the sequential command sequence and the random command sequence as command sequence designation information. This command string designation information is a criterion for determining the number of designated blocks of each command and the addresses of consecutive commands.

After the storage of the access pattern designation information based on the command sequence in steps S1 and S2, the normal command processing in step S6 is performed for the subsequently accepted commands. The embodiment of FIG. 21 is the same as the embodiment of FIG. 3 except for the processing of the pattern determining unit 46 shown in the flowchart of the command receiving process of FIG.

Although the above embodiment supports sequential read, sequential write, random read, and random write as access patterns, the same pattern discriminating section 46 and schedule mechanism 50 as to other patterns are used. With the configuration of the disk time sharing mechanism 82, it can be similarly supported.

The present invention is not limited to the above embodiments, but includes appropriate modifications without impairing the objects and advantages thereof. Further, the present invention is not limited by the numerical values shown in the above embodiments. (Supplementary Note) (Supplementary Note 1) A pattern discriminating unit that discriminates an access pattern of a command received from a higher-level device, a queue for each access pattern, and a command stored in a queue corresponding to the access pattern discriminated by the pattern discriminating unit A disk mechanism for scheduling a disk access of a command stored in the queue in consideration of an access pattern.
(1) (Supplementary note 2) In the disk device according to Supplementary note 1, the pattern determination unit sets an access pattern of data to be stored for each area of the disk, and determines the access pattern from a command address. And a disk drive.

(Supplementary Note 3) In the disk device according to Supplementary Note 1, the pattern determination unit determines an access pattern based on a tag added to a command.

(Supplementary Note 4) In the disk device according to Supplementary Note 1, the pattern determination unit monitors a command sequence to find an access pattern, and determines which access pattern each command belongs to. Disk device.

(Supplementary Note 5) In the disk device according to Supplementary Note 1, the pattern discriminating unit discriminates a read command and a write command separately for sequential access and random access, and the schedule mechanism has a sequential read queue. A sequential read scheduler, a sequential write scheduler with a sequential write queue, a random read scheduler with a random read queue, and a random write scheduler with a random write queue. A cache control mechanism that processes read data from a disk medium on a cache memory, and a reordering module that queues commands and reorders commands in consideration of seek and rotation wait time Mechanism, a sequential queue and a random queue, and stores a command of a corresponding access pattern from the scheduling mechanism. When a command is stored in the sequential queue and the random queue and there is a conflict, the queue of each predetermined queue is determined. A disk device comprising: a disk time sharing mechanism for sequentially switching an assigned time (quantum) and inputting a command to the reordering mechanism. (2) (Supplementary note 6) In the disk device according to supplementary note 5, the pattern determination unit determines an access pattern for the read command, stores the read command in a sequential read queue or a random read queue of the schedule mechanism, and writes the read command. After determining the access pattern and transferring the write data to the cache control mechanism, the write data is stored in a sequential write queue or a random write queue of the schedule mechanism, and the cache control mechanism has an empty capacity of a predetermined value or more in the cache memory. If there is, write the write data to the cache memory.If there is no free space equal to or larger than the predetermined value, write the write data to the cache memory after discarding the discardable data in the cache memory. respond A disk device characterized by the above-mentioned. (3) (Supplementary note 7) In the disk device according to supplementary note 5, the sequential read scheduler, when a command is stored in a sequential read queue, sends a fixed amount of the command to the sequential queue of the disk time sharing mechanism. A sequential read queue, and when the sequential read queue is empty, activates a prefetch processing unit and submits a subsequent prefetch command to the sequential queue of the disk time sharing mechanism. (4) (Supplementary note 8) In the disk device according to Supplementary note 5, when a command is stored in a sequential write queue, the sequential write scheduler stores all commands in a sequential queue of the disk time sharing mechanism. A disk drive characterized by being loaded. (5) (Supplementary note 9) In the disk device according to supplementary note 5, when a command is stored in the random read queue, the random read scheduler sends a fixed amount of the command to the random queue of the disk time sharing mechanism. A disk drive characterized in that it is put into a disk drive. (6) (Supplementary Note 10) In the disk device according to Supplementary Note 5, when a command is stored in the random write queue, the random write scheduler may schedule the command when the free space of the cache memory is equal to or more than a predetermined value. When the free space of the cache memory is less than the predetermined value, the write-back processing unit is started, and the write data stored in the cache memory is stored in a certain range from the address of the oldest command. A disk device wherein commands are collectively input from the random write queue to a random queue of the disk time sharing mechanism. (7) (Supplementary Note 11) In the disk device according to Supplementary Note 5, the disk time sharing mechanism stores a command when one of the sequential queue and the random queue stores a command and the other is empty. A disk device for continuously inputting commands from a queue to the reordering mechanism.

(Supplementary Note 12) In the disk device according to Supplementary Note 5, the reordering mechanism schedules a plurality of inputs and outputs so as to minimize the positioning time by designating a simple task, and to execute scheduling by designating an ordered task. After completing the input / output being accepted, schedule the input / output of the second task designation, and when the disk time sharing mechanism inputs a command from the sequential access queue or random access queue to the reordering mechanism, A disk device, wherein the designation of the simple task and the designation of the ordered task are separately scheduled.

(Supplementary note 13) In the disk device according to supplementary note 12, the first command immediately after switching between the sequential access and the random access is switched by specifying the ordered task. After completing the command of the previous access pattern, schedule the command of the access pattern after switching, and then schedule until the switching of the next access pattern is specified by a simple task to minimize the positioning time A disk device characterized by the above-mentioned.

(Supplementary note 14) In the disk device according to supplementary note 13, the disk time sharing mechanism predicts the next quantum start time based on the predicted processing time of the unprocessed command at the time of quantum switching, and accepts the command. Or, for each command completion response, the remaining time is predicted based on the predicted processing time of the unprocessed command at that time and the quantum start time, and when it is determined that there is a remaining time,
A disk device wherein a command of the current quantum is input to the disk device, and if it is determined that there is no remaining time, the disk device is switched to the next quantum.

(Supplementary Note 15) In the disk device according to Supplementary Note 12, the disk time sharing mechanism may include:
When scheduling multiple commands in one access pattern consecutively, the first command immediately after resetting the assigned time specifies the ordered task, completes the command before reset, and then schedules the command after reset A disk device characterized in that a command until a next reset is designated by a simple task and scheduling is performed so as to minimize a positioning time.

(Supplementary Note 16) In the disk device control method, the access pattern of the command received from the host device is determined, the read command is input to the queue corresponding to the determined access pattern, and the write command is transmitted from the host. Write data is transferred to the cache and then entered into the queue corresponding to the determined access pattern, and commands are sent from each queue to the disk time sharing mechanism at regular intervals according to the access pattern. Control method for a disk device. (8) (Supplementary note 17) In the disk device control method according to supplementary note 16, the access pattern of the command received from the higher-level device is determined from a disk area to which the command accesses, a tag attached to the command, or a command sequence. A method of controlling a disk device.

(Supplementary note 18) In the method of controlling a disk device according to supplementary note 16, sequential access and random access are determined as an access pattern of a read command or a write command, and a sequential read queue, a sequential write queue, and a random read queue are determined. Or, the commands are stored in a random write queue, and the commands in each of the queues are scheduled at regular time intervals, and are separately input into a sequential queue and a random queue of a disk time sharing mechanism, and the sequential of the disk time sharing mechanism is stored. When a command is stored in a queue and a random queue and there is contention, a command is input to the reordering mechanism by sequentially switching a predetermined allocation time (quantum) of each queue. Control method for a disk device according to claim. (9) (Supplementary note 19) In the method of controlling a disk device according to Supplementary note 18, when a command is stored in the sequential read queue, a fixed amount of command is input to the sequential queue of the disc time sharing mechanism. When the sequential read queue is empty, a subsequent prefetch command is input to the sequential queue of the disk time sharing mechanism, and when a command is stored in the sequential write queue, all commands are stored in the disk time sharing queue. When a command is stored in the sequential queue of the sharing mechanism, and a command is stored in the random read queue, a certain amount of command is input to the random queue of the disk time sharing mechanism, and a command is further stored in the random write queue. Is stored, the schedule is not performed when the free space of the cache memory is equal to or more than a predetermined value, and when the free space of the cache memory is less than a predetermined value, the write data stored in the cache memory is not stored. Commands having write data in a certain range from the address of the oldest command are put together into a random queue of the disk time sharing mechanism, and write data of the cache memory is preferentially written back to the disk medium. Control method of a disk device to be executed. (10)

[0222]

As described above, according to the present invention, by scheduling a command based on an access pattern in a disk device, a constant throughput is guaranteed for sequential access, that is, sequential read and sequential write. At the same time, it is possible to guarantee a high-speed response to random access, that is, random read or random write, and it is possible to guarantee such a throughput for sequential access and a high-speed response to random access at low cost by a single disk device. it can.

Further, the command scheduling based on the access pattern can be performed by the disk device alone.
The advantage that no change in the OS or application on the host side is required is obtained.

Furthermore, in the present invention, following the command scheduling based on the access pattern, two-layered disk time sharing for switching the allocation time between sequential access and random access and inputting the command to the reordering mechanism. The sequential access of the same pattern is continuously input to the reordering mechanism by the scheduling of
The seek time and the rotation wait can be reduced, and the throughput and the response can be further improved as compared with the scheduling using the disk time sharing alone.

When the sequential read queue is emptied by the scheduling based on the access pattern, a prefetch command is issued to the disk time sharing side, so that the sequential access throughput is higher than that of the disk time sharing alone. Can be further improved.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating the principle of the present invention.

FIG. 2 is a block diagram of a hard disk drive to which the present invention is applied;

FIG. 3 is a block diagram of an embodiment of access pattern scheduling of the present invention.

FIG. 4 is a flowchart of an access pattern scheduling process according to FIG. 3;

FIG. 5 is a flowchart of a command receiving process in FIG. 4;

FIG. 6 is a flowchart of a normal command process in FIG. 5;

FIG. 7 is an explanatory diagram of a format of a read command and a write command.

FIG. 8 is a flowchart of a scheduling process in FIG. 4;

9 is a flowchart of sequential read scheduling in FIG.

FIG. 10 is a flowchart of sequential write scheduling in FIG. 8;

FIG. 11 is a flowchart of random read scheduling in FIG. 8;

FIG. 12 is a flowchart of random write scheduling in FIG. 8;

FIG. 13 is a flowchart of a command end process in FIG. 4;

FIG. 14 shows a disk time sharing mechanism (D
TC) block diagram

15 is an explanatory diagram of scheduling for sequential access and random access in FIG. 14;

FIG. 16 is an explanatory diagram of disk time scheduling when only sequential access is continued in FIG.

FIG. 17 is an explanatory diagram of a process of estimating a remaining time when quantum is switched in FIG. 14;

FIG. 18 is a flowchart of a disk time sharing process of FIG. 14;

FIG. 19 is a block diagram of another embodiment of the access pattern scheduling of the present invention for determining an access pattern from command tag information.

FIG. 20 is a flowchart of a command receiving process in FIG. 19;

FIG. 21 is a block diagram of another embodiment of the access pattern scheduling of the present invention for determining an access pattern from a command sequence.

FIG. 22 is a flowchart of a command receiving process in FIG. 21;

[Explanation of symbols]

 10: SCSI Controller 12: Drive Control 14: Disk Enclosure 16: MCU 18: Memory 20: Program Memory 22: Hard Disk Controller 24: Data Buffer 26: Drive Interface Logic 28: DSP 30: Read / Write LSI 32: Servo Demodulator 34 : Servo driver 36: Head IC 38-1 to 38-6: Composite head 40-1 to 40-3: Disk 42: Spindle motor (SPM) 44: Voice coil motor (VCM) 45: Host interface 46: Pattern discriminator 48: Disk area designation information 50: Schedule mechanism 52: Cache control mechanism 54: Cache memory 56: Cache table 58: LRU management unit 60: Sequential read schedule 62: Sequential write scheduler 64: Random read scheduler 66: Random write scheduler 70: Sequential read queue 72: Sequential write queue 74: Random read queue 76: Random write queue 78: Prefetch processing unit 80: Write back processing unit 82: Disk time Sharing mechanism (DTC) 84: Sequential queue 85: Completion sequential queue 86: Random queue 87: Completion random queue 88: Reordering mechanism 90: Command queue 92: Control information 94: Command reception unit 95: Command schedule Unit 96: Command completion processing unit 98-1, 98-2: Quantum 100: Current quantum type 102: Current quantum start time 104: Next command Disk type 106: Tag designation information 108: Command string designation information

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Kazutaka Ogihara 4-1-1, Kamidadanaka, Nakahara-ku, Kawasaki-shi, Kanagawa Prefecture Inside Fujitsu Limited (72) Inventor Riichiro Take 4-chome, Kamiodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa No. 1 Fujitsu Limited (72) Inventor Masatoshi Tamura 4-1-1 Kamiodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa Prefecture No. 1 Fujitsu Limited (72) Inventor Katsuhiko Nishikawa 4, Kamiodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa 1-1 1-1 Fujitsu Limited (72) Inventor Yuji Hotta 4-1-1 1-1 Kamiodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa F-term within Fujitsu Limited 5B065 BA01 CC08 CH15 5D088 MM06 MM10

Claims (10)

[Claims] A pattern discriminator for discriminating an access pattern of a command received from a host device, a queue for each access pattern, and storing a command in a queue corresponding to the access pattern discriminated by the pattern discriminator; A disk device comprising: a scheduling mechanism for scheduling disk access of a command stored in a queue in consideration of an access pattern. 2. The disk device according to claim 1, wherein the pattern determination unit determines a read command and a write command separately for sequential access and random access, and the schedule mechanism has a sequential read queue. A sequential read scheduler, a sequential write scheduler with a sequential write queue, a random read scheduler with a random read queue, and a random write scheduler with a random write queue, and write data and disk from a higher-level device A cache control mechanism that processes read data from the medium on the cache memory, and a reordering that queues commands and reorders commands in consideration of seek and rotation wait time Structure, has a sequential queue and a random queue, stores a command of a corresponding access pattern from the scheduling mechanism, and stores a command in the sequential queue and the random queue; A disk device comprising: a disk time sharing mechanism for sequentially switching an assigned time (quantum) and inputting a command to the reordering mechanism. 3. The disk device according to claim 2, wherein the pattern determination unit determines an access pattern for the read command, stores the access pattern in a sequential read queue or a random read queue of the schedule mechanism, and stores the read command in a sequential read queue or a random read queue. After determining the access pattern and transferring the write data to the cache control mechanism, the write data is stored in a sequential write queue or a random write queue of the schedule mechanism, and the cache control mechanism has an empty capacity of a predetermined value or more in the cache memory. If there is, write the write data to the cache memory.If there is no free space equal to or larger than the predetermined value, write the write data to the cache memory after discarding the discardable data in the cache memory. Do A disk device characterized by the following. 4. The disk device according to claim 2, wherein the sequential read scheduler stores a certain amount of commands in the sequential queue of the disk time sharing mechanism when the commands are stored in the sequential read queue. A disk drive characterized in that when a sequential read queue is empty, a prefetch processing unit is started and a subsequent prefetch command is input to a sequential queue of the disk time sharing mechanism. 5. The disk device according to claim 2, wherein the sequential write scheduler sends all commands to a sequential queue of the disk time sharing mechanism when a command is stored in a sequential write queue. A disk drive characterized by the following. 6. The disk device according to claim 2, wherein the random read scheduler stores a certain amount of commands in the random queue of the disk time sharing mechanism when a command is stored in the random read queue. A disk drive characterized by being loaded. 7. A disk drive according to claim 2, wherein said random write scheduler schedules when a free space in said cache memory is equal to or more than a predetermined value when a command is stored in a random write queue. When the free space of the cache memory is less than a predetermined value, the write-back processing unit is activated, and the write data stored in the cache memory is stored in the command of the write data within a certain range from the address of the oldest command. A disk device which collectively puts the random write queue from the random write queue into a random queue of the disk time sharing mechanism. 8. A control method for a disk device, wherein an access pattern of a command received from a host device is determined, a read command is input to a queue corresponding to the determined access pattern, and a write command is stored in a cache from a host. After transferring the write data, the write data is input to a queue corresponding to the determined access pattern, and the input of a command from each queue to the disk time sharing mechanism is scheduled at regular intervals according to the access pattern. A method for controlling a disk device. 9. A method for controlling a disk device according to claim 8, wherein a sequential access and a random access are determined as an access pattern of a read command or a write command, and a sequential read queue, a sequential write queue, a random read queue, Alternatively, the commands are stored separately in a random write queue, the commands in each of the queues are scheduled at regular time intervals, and are separately input into a sequential queue and a random queue of the disk time sharing mechanism, and the sequential queue of the disk time sharing mechanism is stored. And when a command is stored in a random queue and there is a conflict, the command is input to the reordering mechanism by sequentially switching the predetermined allocation time (quantum) of each queue. The method of disk device. 10. A control method for a disk device according to claim 9, wherein when a command is stored in said sequential read queue, a certain amount of command is input to a sequential queue of said disk time sharing mechanism. If the sequential read queue is empty, a subsequent prefetch command is input to the sequential queue of the disk time sharing mechanism. If a command is stored in the sequential write queue, all commands are stored in the disk time share. When a command is stored in the sequential queue of the ring mechanism, and a command is stored in the random read queue, a certain amount of command is input to the random queue of the disk time sharing mechanism, and a command is further stored in the random write queue. If it is stored, the schedule is not performed when the free space of the cache memory is equal to or more than a predetermined value, and when the free space of the cache memory is less than the predetermined value, the write data stored in the cache memory is most frequently used. Commands having write data in a certain range from the address of the old command are put together in a random queue of the disk time sharing mechanism, and the write data in the cache memory is preferentially written back to the disk medium. A method for controlling a disk device.