Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2000-03-24
2004-10-05
An, Meng-Al T. (Department: 2126)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C710S040000
Reexamination Certificate
active
06802064
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a control scheme of a request processing device for processing data transfer requests issued to a storage device that requires large mechanical actions such as a media exchanger.
2. Description of the Background Art
In general, data transfer requests issued to a storage device are entered into queues once and then processed in an order according to a scheduling policy specific to that storage device. Policies often used as the scheduling policy of the storage device include FIFO (First In First Out) and SCAN. FIFO is a policy for processing requests in an order of issue times of requests, whereas SCAN is a policy specific to a disk device in which a moving direction of a head is restricted to one direction, and requests are processed in such an order that a request that accesses a closest track in that direction is processed first.
However, in the storage device incorporated within a real time system, there are cases where a deadline is set for a processing of each data transfer request. In such cases, the scheduling policy called EDF (Earliest Deadline First) is often employed. This is a policy in which requests are processed in such an order that a request with the earliest deadline is processed first.
Also, in the case of handling a series of data transfer requests that should be processed periodically, it is possible to employ a policy called RM (Rate Monotonic). Each request sequence to be handled by RM has its unique period, such that one request is issued and processed within one period. RM is a policy in which a plurality of request sequences are handled simultaneously in such an order that a request belonging to a sequence with a shortest period is processed first.
FIFO is used in cases where a response time for a request is important, and SCAN is used in cases where an overall transfer performance is important. On the other hand, EDF or RM is often used in cases where there is a need to guarantee that a processing of each periodic data transfer request will be completed within its period. However, even in such cases, FIFO or SCAN can be used if a special condition that all data transfer requests have an equal period holds.
Here, in the case of using tapes as a storage medium that is a target of data transfer or the case of using a plurality of storage media while exchanging them by a media exchanger, an overhead in the case of random accesses becomes very large. For this reason, the transfer efficiency becomes poor because the overhead time until the start of the data transfer becomes relatively longer than the time required for actually transferring data. In addition, the amount of actions by mechanical parts is large so that there is a need to take the durability of the mechanical parts into consideration.
As a scheme for carrying out the data transfer in the storage device using tapes or a media exchanger, the following schemes have been proposed so far.
(1) A data transfer with deadline is not handled. Namely, the time division multiple access using a policy that can guarantee deadlines such as EDF or RM is abandoned, and a policy that can reduce the number of tape movements or media exchanges such as SCAN is employed.
(2) A data transfer with deadline is not handled in the case of carrying out the time division multiple access that requires media exchanges. Namely, while the data transfer with deadline is to be carried out for some file, a medium that stores this file is left in a drive while this file is in use. However, in this scheme, in order to access a file stored in another medium, it is necessary to wait for the end of the use of the currently used file.
(3) The time division multiple access using a policy that can guarantee deadlines such as EDF or RM is simply carried out. In this scheme, it is possible to handle data transfer with deadline, but the scheduling for reducing the number of tape movements or media exchanges is impossible.
(4) An amount of data transfer is increased in the case of carrying out the time division multiple access using EDF or RM. Since the transfer time and the transfer period become longer in proportion to the data transfer amount, it is possible to relatively reduce the number of tape movements or media exchanges, but the wait time also becomes longer in proportion to the data transfer amount in this scheme.
Note that there also exists a scheme which has a superior random access performance than tapes or a media exchanger and which uses a cache disk in a form of a hard disk whose capacity can be increased beyond that of a memory. In the case of actually carrying out the periodic data transfer using a cache disk, it is customary to use a scheme in which all files with high utilization frequencies are cached into the cache disk and the time division multiple access is permitted only for those files which are entirely cached in the cache disk. As for those files which are not cached in the cache disk, any one of the four schemes described above have to be employed.
As described, according to the conventional schemes, in the case of carrying out the periodic data transfer from the storage device using tapes or a media exchanger, it has been unavoidable to increase the wait time until the periodic data transfer starts when a scheme for reducing the amount of mechanical actions is employed.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a data transfer request processing scheme which is capable of: (a) scheduling the processing order of the data transfer requests such that the amount of mechanical actions can be reduced, by taking the durability of the mechanical parts in consideration, in the case of using storage media that requires a large amount of actions by the mechanical parts at a time of access such as a media exchanger; (b) guaranteeing that a processing of each request will be completed before its deadline in the case of handling data transfer request to be processed periodically; and (c) shortening the wait time until the data transfer starts (i.e., not increasing the amount of transfer data and the period for each request) in the case of handling data transfer requests to be processed periodically.
According to one aspect of the present invention there is provided a method for processing data transfer requests with respect to a storage device that requires mechanical actions in carrying out data transfers, comprising the steps of: classifying data transfer requests with deadlines for completing requested data transfers into first and second classes; scheduling processing of first class data transfer requests that are classified as the first class by the classifying step according to a first scheduling policy in which a completion of data transfers requested by the data transfer requests within the deadlines specified for the data transfer requests is a primary key factor in determining an order of processing, and scheduling processing of second class data transfer requests that are classified as the second class by the classifying step according to a second scheduling policy in which a reduction of amounts of the mechanical actions required in carrying out data transfers requested by the data transfer requests is a primary key factor in determining an order of processing; and processing the data transfer requests according to a scheduling result obtained by the scheduling step so as to control the storage device to carry out data transfers requested by the data transfer requests.
According to another aspect of the present invention there is provided a data transfer request processing device for processing data transfer requests with respect to a storage device that requires mechanical actions in carrying out data transfers, comprising: a classifying unit configured to classify data transfer requests with deadlines for completing requested data transfers into first and second classes; a scheduling unit configured to schedule processing of first class data transfer requests that are classified
Kanai Tatsunori
Yao Hiroshi
An Meng-Al T.
Kabushiki Kaisha Toshiba
Opie George L.
LandOfFree
Data transfer request processing scheme for reducing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data transfer request processing scheme for reducing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data transfer request processing scheme for reducing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3287276