Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2002-07-17
2003-04-29
Ellis, Kevin L. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
Reexamination Certificate
active
06557088
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an information processing system for reading data from a large-capacity storage unit through a data buffer and, for example, to a database system for processing a query on a database on a disk unit.
2. Description of the Related Art
The performance of a database system for processing queries on a database file on a disk unit is limited by the data transfer wait time from the disk unit rather than the processing capability of a central processing unit (CPU). Thus, various methods are designed, such as a method of providing a buffer for retaining disk blocks making up a file for decreasing the actual number of input/output times from/to a disk unit and a method of previously reading necessary disk blocks into memory.
FIG. 16
is a chart to show a file access control system shown on “Implementation and performance of integrated application—controlled file caching, prefetching, and disk scheduling,” an article appearing on pages 311 to 343 of issue 4 of vol. 14 of ACM Transactions on Computer Systems published in November 1996, for example
In
FIG. 16
, numerals
4
a
and
4
b
denote query processing tasks, numeral
6
denotes a disk unit for storing a file, numeral
71
denotes a disk input/output control module for performing physical input/output from/to the disk unit, numeral
91
denotes a preread module for reading a block from the disk unit prior to a request issued from the query processing task, and numeral
92
denotes a buffer module for retaining the block read from the disk unit on memory.
FIG. 17
is a timing chart to show a time sequence applied when the query processing task
4
a
executes query processing. In the figure, the horizontal axis represents the time. Numerals
40
a
and
60
represent a data processing sequence of the query processing task
4
a
and a data transfer sequence of the disk unit
6
respectively. Numerals B
1
and B
2
denote numbers of disk blocks and numerals t
21
, t
22
, t
23
, and t
24
denote timings. Numeral
41
a
represents the time taken for the query processing task
4
a
to process one block read into the memory and numeral
61
represents the time taken for the disk unit
6
to transfer one block.
At timing t
21
, the query processing task
4
a
starts execution, notifies the preread module
91
of the accessed disk block order, B
1
, B
2
, . . . , and waits for the first block B
1
to be read. The preread module
91
instructs the disk input/output control module
71
to read the first block B
1
in accordance with the block order indicated from the query processing task
4
a
, and the disk unit
6
starts to transfer the block B
1
. At timing t
22
, the transfer of the block B
1
from the disk unit is complete, the query processing task
4
a
processes the data in the block, the preread module
91
instructs the disk input/output control module
71
to read the second block B
2
, and the disk unit
6
starts to transfer the block B
2
.
At timing t
23
, upon completion of processing the block B
1
, the query processing task
4
a
waits for the second block B
2
to be read. At timing t
24
, the transfer of the block B
2
from the disk unit is complete, the query processing task
4
a
processes the data in the block, and the preread module
91
instructs the disk input/output control module
71
to read the next block. This processing is repeated until completion of processing all blocks in the file.
Thus, using the block access order indicated by the query processing task
4
a
, the preread module
91
can start block read without waiting for a block access request issued from the query processing task
4
a
, so that the wait time of the query processing task
4
a
can be made shorter than the block transfer time
61
of the disk unit
6
with respect to any other block than the first block B
1
.
In the file access system in the related art as described above, the disk block transfer order between the disk unit and the buffer can be changed, but the disk block transfer order between the buffer and the task cannot be changed. Thus, even if two or more tasks make sequential access to the same file at the same time, the disk block accessed at the same time is not necessarily the same. Thus, for a file larger than the buffer capacity, the possibility that the disk block accessed by one task may remain on the buffer until it is accessed by another task is low; the buffering effect cannot be produced.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide an information processing system wherein a buffer can be used efficiently even if a plurality of query processing tasks access a large-capacity database file at the same time.
According to the invention, there is provided an information processing system comprising buffer storage means for temporarily storing a plurality of data pieces read from a storage unit, order determination means for detecting from a processing request for requesting a plurality of data pieces stored on the storage unit, the data piece matching the data stored in the buffer storage means among the data pieces requested in the processing request and determining the read order of the match data piece and the remaining data requested in the processing request so as to read the match data piece preceding the remaining data, and read means for reading the match data piece from the buffer storage means before reading the remaining data into the buffer storage means from the storage unit in accordance with the read order determined by the order determination means.
The storage unit is a disk unit, the read means reads the remaining data into the buffer storage means from the disk unit after reading the match data piece, and the information processing system further includes transmission means for transmitting the remaining data after transmitting the match data piece read by the read means from the buffer storage means.
According to the invention, there is provided an information processing system comprising a disk unit with a storage area divided into a plurality of blocks, buffer storage means for storing a plurality of blocks read from the disk unit, first processing means for accepting a first processing request for requesting a plurality of data pieces stored on the disk unit, detecting a plurality of blocks storing the data pieces requested in the first processing request based on the first processing request, and reading the data in the detected blocks from the buffer storage means, second processing means for accepting a second processing request for requesting a plurality of data pieces stored on the disk unit, detecting a plurality of blocks storing the data pieces requested in the second processing request based on the second processing request, and reading the data in the detected blocks from the buffer storage means, detection means for detecting a block common to the first and second processing requests among the blocks stored in the buffer storage means, and buffer management means, to erase the data contained in the common block detected by the detection means from the buffer storage means, for erasing the data after the data to be erased is read by both the first and second processing means.
The buffer management means comprises preread means for reading the data in the blocks detected by the first processing means and data in a block specified in a read request received from the outside from the disk unit and stores the read data in the buffer storage means, and the detection means specifies a block not common to the blocks related to the first processing request without specifying the common block among the blocks detected by the second processing means and outputs to the preread means as the read request.
The buffer storage means stores the data pieces requested in the first and second processing requests in a first-in first-out shared queue, the preread means stores the data in the common block read from the disk unit in the queue, the first processing means reads the data requested in the fi
Ellis Kevin L.
Mitsubishi Denki & Kabushiki Kaisha
LandOfFree
Information processing system and recording medium recording... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Information processing system and recording medium recording..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information processing system and recording medium recording... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3111473