Nova Patents
EP0805593A2

Storage device control unit and management system

Abstract

The queue inputting part 42 enqueues the arrived "top priority request" to the priority queue so that each request being held in the "priority queue" meets the allowable delay value and the request is processed after other "top priority requests" being held and so that the access position is consecutive. The queue inputting part 42 enqueues the write requests and the "no priority requests" to the write queue and the "no priority queue" respectively one by one. The command output processing part 47, based on state numbers held in the state showing table 46, selects one from the three kinds of queues and the read request or the write request is outputted from the selected queue as a command.

EP0805593A2, drawing sheet 1
Sheet 1 of 50

Term

Term ended

Projected expiry passed 29 April 2017, 9.4 years ago.

  1. Priority
  2. Filed
  3. Published
  4. Projected expiry
  5. Today

67 claims: 14 independent, 53 dependent

  1. 1
    A storage device control unit for controlling write operation or read operation of data on storage devices to be performed, in compliance with write requests or read requests successively arriving from the external, wherein said data is divided into unit blocks of a predetermined size and each of said read requests includes a delay limit value meaning a period which is from the arrival time of the read request to the time when said read operation has to finish, comprising:selecting means for selecting one consecutive empty area or plural consecutive empty areas, where the predetermined number of unit blocks can be written consecutively, corresponding to the amount of data to be written into said storage devices from empty areas of said storage device, write command outputting means for outputting said write request as a write command, order determining means for determining an order of outputting read requests successively arriving from the eternal as read commands, and read command outputting means for outputting the read commands in the order determined by said order determining means, wherein said write command outputting means outputs said write command so that data to be written in said storage devices is written into said empty area selected by said selecting means and said order determining means determines the order of processing each of the read requests successively arriving from the external so that the period for the read operation is not beyond each of said delay limit value and is also shorter than a period for the read operation obtained assuming that read requests is outputted in the order of arrival.
  2. 2
    The storage device control unit in accordance with claim 1, wherein said selecting means selects said consecutive empty areas at random.
  3. 3
    The storage device control unit in accordance with claim 1, wherein, when the number of connected storage devices is "p" (d 1 ,d 2 ,...d p ), said selecting means selects said consecutive empty areas from empty areas of storage devices of which number is "m" ("m" is an integer of 1≦m≦p), and when consecutive empty areas selected from a storage device "d i " ("i" is an integer of 1≦i≦m ) are a i1 ,a i2 ,...a in ("n" is an integer of 2 or more), said write command outputting means outputs said write command so that the unit blocks composing said data are written in such an order as a 11, a 21 ,...a m1 ,a 12 , a 22 ,...a m2 ,...a 1n , a 2n ,...a mn .
  4. 4
    The storage device control unit in accordance with claim 1, wherein said selecting means selects said consecutive empty areas from the empty areas which one storage device has.
  5. 5
    The storage device control unit in accordance with claim 1, wherein said delay limit values are predetermined values stored therein.
  6. 6
    The storage device control unit in accordance with claim 1, wherein said delay limit values are parameters which said read request includes.
  7. 7
    The storage device control unit in accordance with claim 1, further comprising position file managing means for managing positions in which to store each of said unit blocks in said storage devices, wherein said order determining means includes:queue managing means, having a read queue which temporarily holds said read requests in a queue, for managing record positions of unit blocks to be read in compliance with the read requests, position fixing means for fixing a position in said read queue to enqueue an arrived read request to, allowable delay information computing/managing means for computing and then managing an estimated processing period which is estimated to be period for each of said read operations, an expected ending time when the read operation is expected to finish, and an allowable delay value which is obtained by, subtracting the expected ending time from an ending time, obtained by referring to said delay limit values, at which the read operation has to finish, said position fixing means extracts a record position (hereinafter, "a first record position") of a unit block to be read in compliance with a newly-arrived read request from the eternal from said position file managing means, extracts record positions (hereinafter, "second record positions") of unit blocks to be read in compliance with each of the read requests held in said read queue from said queue managing means, temporarily fixing a position in said read queue to which to enqueue said newly-arrived read request based on said first record position and said second record position, said allowable delay information computing/managing means computes the estimated processing period for said newly-arrived read request enqueued to said temporarily fixed position and compares the estimated processing period for said newly-arrived read request with the allowable delay values for each of the read requests behind the read request enqueued to the temporarily-fixed position, and said position fixing means, when said allowable delay information computing/managing means judges that each allowable value is more than said estimated processing period, fixes said temporarily fixed position as a place to enqueue said newly-arrived read request to.
  8. 8
    The storage device control unit in accordance with claim 7, wherein said storage devices have disks for store of said unit blocks, said estimated processing period is computed based on seek time for a head of said storage devices to move between tracks where unit blocks to be read in compliance with the read request and a read request enqueued just ahead of said read request in said read queue are stored, transfer time to transfer the unit block to be read in compliance with said read request from said disks, and predetermined overhead time and rotational latency.
  9. 9
    The storage device control unit in accordance with claim 8, wherein tracks of said disk have respective track numbers, said position file managing means and said queue managing means manage the track numbers corresponding to the positions of the tracks where the unit blocks are stored, and said seek time is computed based on each of said track numbers.
  10. 10
    The storage device control unit in accordance with claim 7, wherein said storage devices have disks for store of said unit blocks, said estimated processing period is computed based on seek time of a head of said storage devices to move between cylinders where unit blocks to be read in compliance with the read request and a read request enqueued just ahead of said read request in said read queue are stored, transfer time to transfer the unit block to be read in compliance with said read request from said disks, and predetermined overhead time and rotational latency.
  11. 11
    The storage device control unit in accordance with claim 10, wherein cylinders of said disk have respective cylinder numbers, said position file managing means and said queue managing means manage said cylinder numbers corresponding to the positions of cylinders where unit blocks are stored, and said seek time is computed based on each of said cylinder numbers.
  12. 12
    The storage device control unit in accordance with claim 10, wherein said transfer time is computed based on packing density in the position where the unit block to be read in compliance with the read request is stored and the rotating speed of said disk.
  13. 13
    The storage device control unit in accordance with claim 8, wherein said overhead time is obtained by subtracting the sum of said mean seek time, said mean rotational latency and said mean transfer time from the average of measured period to read data of the same size as the unit block from said storage device plural times consecutively.
  14. 14
    The storage device control unit in accordance with claim 8, wherein said rotational latency is the mean rotational latency of said disk.
  15. 15
    The storage device control unit in accordance with claim 7, said estimated processing period means the period as a predetermined confidence limit which covers the set of measured periods obtained by reading the data of the same size as the unit block from said storage device plural times consecutively.
  16. 16
    The storage device control unit in accordance with claim 7, wherein said storage devices have disks for store of said unit blocks, said disk have tracks provided with respective ascending or descending numbers from the most inner track of the disk to the most outer track of the disk, said position file managing means manages position files including the track numbers corresponding to the positions where said unit blocks are stored, said queue managing means manages numbers of the tracks where the unit blocks to be read in compliance with read requests enqueued to said read queue are stored, said position fixing means extracts a number (hereinafter, "a first track number") of the track where unit block to be read in compliance with the newly-arrived read request from the external is stored from said position file managing means, extracts numbers (hereinafter, "second track numbers") of the tracks where each unit block to be read in compliance with the respective read requests held in said read queue is stored from said queue managing means, and temporarily fixes a position where the first track number and the second track numbers stand in a row and in an ascending order or a descending order as said temporarily fixed position, and enqueues said newly-arrived read request to said temporarily-fixed position.
  17. 17
    The storage device control unit in accordance with claim 7, wherein said storage devices have disks for store of said unit blocks, said disk have cylinders provided with respective ascending or descending numbers from the most inner track of the disk to the most outer track of the disk, said position file managing means manages position files including cylinder numbers corresponding to the positions where said unit blocks are stored, said queue managing means manages numbers of the cylinders where the unit blocks to be read in compliance with read requests enqueued to said read queue are stored, said position fixing means extracts a number (hereinafter, "a first cylinder number") of the cylinder where unit block to be read in compliance with the newly-arrived read request from the external is stored from said position file managing means, extracts numbers (hereinafter, "second cylinder numbers") of the cylinder where each of the unit block to be read in compliance with the respective read requests held in said read queue is stored from said queue managing means, and temporarily fixes a position where the first cylinder number and the second cylinder numbers stand in a row and in an ascending order or a descending order as said temporarily fixed position, and enqueues said newly-arrived read request to said temporarily-fixed position.
  18. 18
    The storage device control unit in accordance with claim 7, further comprising command operation ending means for receiving the ending time of the read operation performed by said storage device and notifying said allowable delay information computing/managing means of the ending time, wherein said allowable delay information computing/managing means calculates, when the ending time notified by said command operation ending means is different from the expected ending time for said read request managed therein, a time difference between the ending time and the expected ending time, update the expected ending time and the allowable delay value for each of the read requests stored in said read queue based on the calculated time difference.
  19. 19
    A storage device control unit for controlling write operation or read operation of data on storage devices to be performed, in compliance with write requests or read requests successively arriving from the external, wherein each of said read requests includes a delay limit value meaning the maximum value of a period which is from the arrival time of the read request to the time when the read operation finishes, comprising write command outputting means for outputting said write requests as write commands to said storage devices , wherein said write command outputting means outputs said write command so that the write operation of said data is performed within the delay limit value which each of said read requests includes.
  20. 20
    The storage device control unit in accordance with claim 19, further comprising allowable delay information computing/managing means for computing and then managing an estimated processing period which is estimated to be period for each of said read operations and said write operations, an expected ending time when the read or write operation is expected to finish, and an allowable delay value which is obtained by subtracting the expected ending time from an ending time, obtained by referring to said delay limit value, at which the operation has to finish, wherein said write command outputting means outputs said write command when said allowable delay value is more than the estimated processing period for said write request, and said allowable delay information computing/managing means, when the write command is outputted, subtracts the estimated processing period for said write command from each of the allowable delay values for said read requests.
  21. 21
    The storage device control unit in accordance with claim 20, wherein the estimated processing period for said read request shows the processing period as a predetermined confidence limit which covers the set of measured periods obtained by writing the data of the same size as the data written in compliance with said write request into said storage device plural times consecutively.
  22. 22
    The storage device control unit in accordance with claim 21, further comprising command operation ending means for receiving an actual ending time of the write operation performed by said storage device and notifying said allowable delay information computing/managing means of the actual ending time, wherein said allowable delay information computing/managing means calculates, when an actual processing period for the write operation, which is calculated based on the ending time, is different from the estimated processing period which the write request has, a time difference between the processing period and the estimated processing period, update the allowable delay value for each of said read requests based on the calculated time difference.
  23. 23
    The storage device control unit in accordance with claim 19, wherein said delay limit values are predetermined values stored therein.
  24. 24
    The storage device control unit in accordance with claim 19, wherein said delay limit values are parameters which the read requests include.
  25. 25
    A storage device control unit for controlling write operation of data on storage devices to be performed, in compliance with write requests successively arriving from the external, comprising:buffer memory managing/judging means for managing a used capacity of a buffer memory which stores temporarily data to be written into said storage devices and judging whether the used capacity is not less than a predetermined threshold value, and write command outputting means for outputting said write requests to said storage device as write commands, wherein said write command outputting means, when said buffer memory managing/judging means judges that said used capacity is the predetermined threshold value or more, sends a write command so that the data stored temporarily in said buffer memory is written into said storage devices.
  26. 26
    A storage device control unit for controlling write operation of data on storage devices to be performed, in compliance with write requests successively arriving from the external, wherein each of said write requests includes a delay limit value showing the maximum value of a period which is from the arrival time of the read request to the time when said write operation has to finish, comprising write command outputting means for outputting said write request to said storage device as a write command, wherein said write command outputting means, after said delay limit of period has passed since the arrival of said write request, outputs the write command.
  27. 27
    The storage device control unit in accordance with claim 26, wherein said delay limit values are predetermined values stored therein.
  28. 28
    The storage device control unit in accordance with claim 26, wherein said delay limit values are parameters which the write requests include.
  29. 29
    A storage device control unit for controlling write operation or read operation of data on storage devices to be performed, in compliance with write requests or read requests successively arriving from the external, wherein each of said read requests includes a first priority information or a second priority information, and the read request including at least said second priority information includes a delay limit value showing the maximum value of a period which is from the arrival time of the read request to the time when said read operation finishes, comprising read command outputting means for outputting said read requests to said storage devices as a read command, wherein said read command outputting means outputs the read request including said first priority information as the read command within the delay limit value for a read request including said second priority information and with priority to the read request including said second priority information.
  30. 30
    The storage device control unit in accordance with claim 29, wherein said data is divided into unit blocks of a predetermined data size, consecutive empty areas where the predetermined number of unit blocks can be written are selected from the empty areas of said storage device as many as the number which said data needs, the selected consecutive empty areas are stored in the storage devices as a position file to fix a position in which to store said data:and read requests which read said position file from said storage devices include said first priority information.
  31. 31
    The storage device control unit in accordance with claim 29, further comprising:a first read queue which holds read requests including said first priority information in a queue, a second read queue which holds read requests including said second priority information in a queue, and allowable delay information computing/managing means for computing and then managing an estimated processing period which is estimated to be period for each of the read operations performed in compliance with each of said read request, an expected ending time when the read operation is expected to finish, and an allowable delay value which is obtained by subtracting the expected ending time from an ending time, obtained by referring to said delay limit value, at which the read operation has to finish, wherein said read command outputting means, when the estimated processing period for the read request held in said first read queue is less than each of the allowable delay values for the read requests held in the second read queue, outputs the read request located at the head of the queue held in the first read queue as the read command.
  32. 32
    The storage device control unit in accordance with claim 29, further comprising:a read queue which holds the read requests including said first priority information and the second priority information in a queue, position fixing means for determining to enqueue a read request arrived newly from the external to a predetermined position in said read queue , allowable delay information computing/managing means for computing and then managing an estimated processing period which is estimated to be period for the read operation performed in compliance with each read request held in said read queue, an expected ending time when the read operation is expected to finish, and an allowable delay value which is obtained by subtracting the expected ending time from an ending time, obtained by referring to said delay limit value, at which the read operation has to finish, wherein said position fixing means enqueues a read request including the first priority information to said queue so that the read request is outputted as the read command within the delay limit value for the read request, which is being held in the read queue, including the second priority information and with priority to the read request including the second priority information, and said read command outputting means outputs the read requests as the read commands in the order from the head of the queue held in said read queue.
  33. 33
    The storage device control unit in accordance with claim 32, wherein said position fixing means, when the read request including said first priority information has arrived newly, defines the read request including the second priority information which is nearest to the tail of the queue held in said read queue as a sample request and said allowable delay information computing/managing means computes an estimated processing period for a read request including the first priority information, which has been inputted by said position fixing means, when a place just ahead of said sample request is temporarily fixed as a position to enqueue the read request to, and said position fixing means compares estimated processing period for said newly-arrived read request with allowable delay values for said sample request and read requests including the second priority information behind the sample request, when each of said allowable delay values is the estimated processing period or more, fixes finally a position just ahead of said sample request to enqueue said newly-arrived read request to, when at least one of said allowable delay values is less than the estimated processing period, judges whether said sample request is located at the tail of the queue held in said read queue, when said sample request is located at the tail, enqueues said newly-arrived read request to the tail of the queue held in said read queue, and, when said sample request is not located at the tail, defines a read request located just behind the sample request as a new sample request.
  34. 34
    The storage device control unit in accordance with claim 32, wherein said storage devices have disks for store of said unit blocks, said estimated processing period is computed based on seek time of a head for said storage devices to move between tracks or cylinders where unit blocks to be read in compliance with the read request and a read request located just ahead of said read request are stored, transfer time to transfer the unit block to be read in compliance with said read request from said disks, and predetermined overhead time and rotational latency.
  35. 35
    The storage device control unit in accordance with claim 32, wherein said estimated processing period means the period as a predetermined confidence limit which covers the set of measured periods obtained by reading the data of the same size as the unit block from said storage device plural times consecutively.
  36. 36
    The storage device control unit in accordance with claim 29, wherein said read request includes any one of the first to a third priority information and said read request outputting means, when a newly-arrived read request has the third priority information, outputs the newly-arrived read request as the read command after all of the read requests including the first priority information and the second priority information are outputted.
  37. 37
    A storage device control unit for controlling write operation or read operation of data on storage devices to be performed, in compliance with write requests or read requests successively arriving from the external, wherein each of said read requests and said write requests include a delay limit value showing the maximum value of a period which is from the arrival time of the read request and the write request to the time when the read operation and the write operation finish, comprising:a read queue which holds temporarily said read requests in a queue, a write queue which holds temporarily said write requests in a queue, command outputting means for selecting the read queue or the write queue and outputting a read request or a write request located at the head of the queue held in the read queue or the write queue to said storage devices as a read or a write command respectively, allowable delay information computing/managing means for computing and then managing an estimated processing period which is estimated to be period for the operation to be performed in compliance with each arrived read request or each arrived write request, an expected ending time when the operation is expected to finish, and an allowable delay value which is obtained by subtracting the expected ending time from an ending time, obtained by referring to said delay limit value, at which the operation has to finish, buffer memory managing/judging means for managing a used capacity of a buffer memory which stores temporarily data to be written into said storage devices and judging whether the used capacity is not less than a predetermined threshold value, comparing means for comparing the estimated processing period for the write request located at the head of the queue held in said write queue with each minimum value of the allowable delay values for read requests composing the queue held in said read queue, judging means for judging whether the read request and the write request is held in said read queue or said write queue, wherein said command outputting means, when said buffer memory managing/judging means judges that said used capacity is a predetermined threshold value or more, when the allowable delay value for the write request which is managed by said allowable delay information computing/managing means reaches a predetermined constant value, when said judging means judges that the write request and the read request is stored in the write queue and the read queue and said comparing means judges that the estimated processing period for the write request is less than the minimum value of the allowable delay time, when said judging means judges that only the write request is held in the write queue, chooses the write queue, and, when said judging means judges that the write request and the read request is held in the write queue and the read queue and said buffer memory managing/judging means judged that said used capacity is less than the predetermined threshold value and when said judging means judges that only the read request is held in the read queue, chooses the read queue.
  38. 38
    A storage device control unit for controlling write operation or read operation of data on storage devices, in compliance with write requests or read requests successively arriving from the external, wherein said read request includes any one of first to third priority information, read requests including at least said first priority information and said second priority information and said write requests includes a delay limit value meaning the maximum value from the arrival time of the read request and the write request to the time when the read operation and the write operation finish, comprising:a first read queue which holds temporarily read requests including said first priority information and said second priority information in a queue, a second read queue which holds temporarily read requests including said third priority information in a queue, a write queue which holds temporarily said write requests in a queue, position fixing means for fixing a predetermined position in said first read queue to which to enqueue a read request arrived from the external including the first priority information, command outputting means for choosing one from the first read queue, the second read queue and the write queue, and outputting a read request from the head of the queue held in the chosen queue to said storage devices as a read or a write command respectively, allowable delay information computing/managing means for computing and then managing an estimated processing period which is an estimated to be period for the operation to be performed in compliance with each arrived read request or write request, an expected ending time when the operation is expected to finish, and an allowable delay value which is obtained by subtracting the expected ending time from an ending time, obtained by referring to said delay limit value, at which the operation has to finish, buffer memory managing/judging means for managing a used capacity of a buffer memory to store temporarily data to be written into said storage devices and judging whether the used capacity is not less than a predetermined threshold value, comparing means for comparing the estimated processing period for the write request located at the head of the queue held in said write queue with the minimum value of the allowable delay values for read requests composing the queue held in said first read queue, judging means for judging whether the read request or the write request is held in said first read queue, said second read queue or said write queue and whether a read request including the first priority information is held in the first read queue, wherein said position fixing means enqueues the read request including the first priority information to said first read queue so that the read request is outputted as a read command within a delay limit value for the read request, which is being held in said first read queue, including said second priority information and with priority to the read request including the second priority information, and, said command outputting means, when said buffer memory managing/judging means judges that said used capacity is a predetermined threshold value or more, when said buffer memory managing/judging means judges that said used capacity is less than the predetermined threshold value, and the allowable delay value for the write request which is managed by said allowable delay information computing/managing means reaches a predetermined constant value, and when said buffer memory managing/judging means judges that said used capacity is less than the predetermined threshold value, and the allowable delay value for the write request which is managed by said allowable delay information computing/managing means does not reach said predetermined constant value, and further said judging means judges that the read request including the first priority information is not stored, and said comparing means judges that the estimated processing period for the write request is less than the minimum of the allowable delay value, chooses the write queue, when said buffer memory managing/judging means judges that said used capacity is less than the predetermined threshold value, and the allowable delay value for the write request which is managed by said allowable delay information computing/managing means does not reach said predetermined constant value, and further said judging means judges that the read request including said first priority information is stored in said first read queue, when said buffer memory managing/judging means judges that said used capacity is less than the predetermined threshold value, and the allowable delay value for the write request which is managed by said allowable delay information computing/managing means does not reach the predetermined constant value, and further said judging means judges that the read request including said first priority information is not stored in said first read queue, and said comparing means judges that the estimated processing period for the write request is more than the minimum of allowable delay value, and when said judging means judges that the write request is not stored, chooses said first read queue, and, when said judging means judges that the read request is stored in only said second read queue, chooses the second read queue.
  39. 39
    A storage device control unit for controlling write operation or read operation of data on storage devices to be performed, in compliance with write requests or read requests successively arriving from the external, wherein each of said read or write requests includes priority information to set a priority outputted as a command, comprising:a plurality of queues which holds temporarily the said read or write requests in a queue, position fixing means for fixing a predetermined position in a predetermined queue to which to enqueue the read or write request arrived from the external based on said priority information, command outputting means for choosing any one from the plurality of queues and outputting a write or read request located at the head of the queue held in the selected queue to said storage devices as write or read command, and state-number holding means for holding state numbers which decides if said write request should be outputted as the command and said read request should be outputted as the command, wherein said command outputting means selects any one from the plurality of queues based on the state numbers held by said state-number holding means.
  40. 40
    The storage device control unit in accordance with claim 39, wherein each of said read requests and said write requests include a delay limit value showing the maximum value of a period which is from the arrival time of the read request and the write request to the time when the read operation and the write operation finish, and said plural queues are a read queue which holds temporarily said read requests in a queue and a write queue which holds temporarily said write requests in a queue, comprising:allowable delay information computing/managing means for computing and then managing an estimated processing period which is estimated to be period for the operation to be performed in compliance with each arrived read request and each arrived write request, an expected ending time when the operation is expected to finish, and an allowable delay value which is obtained by subtracting the expected ending time from an ending time, obtained by referring to said delay limit value, at which the operation has to finish, buffer memory managing/judging means for managing a used capacity of a buffer memory which stores temporarily data to be written into said storage devices and judging whether the used capacity is not less than a predetermined threshold value, comparing means for comparing the estimated processing period for the write request located at the head of the queue held in said write queue with a minimum value of the allowable delay values for read requests composing the queue held in said read queue, and judging means for judging whether the read request and the write request are held in said read queue and said write queue respectively, wherein said state-number holding means holds: a first state-number showing a case where said buffer memory managing/judging means judges that said used capacity is a predetermined threshold value or more, a second state-number showing a case where the allowable delay value for the write request which is managed by said allowable delay information computing/managing means reaches a predetermined constant value, a third state-number showing a case where said judging means judges that the write request or read request is held in said write or read queue and said comparing means judges that the estimated processing period for the write request is less than the minimum value of the allowable delay time, a forth state-number showing a case where said judging means judges that only the write request is held in said write queue, a fifth state-number showing a case where said judging means judges that the write request and read request are held in said write and read queue and said buffer memory managing/judging means judges that said used capacity is less than the predetermined threshold value, and a sixth state-number showing a case where said judging means judges that only the read request is held in said read queue, said position fixing means enqueues the read request including a first priority information to said read queue so that the read request is outputted as a read command within an allowable delay value for the read request including a second priority information, which has been held in said read queue, and with priority to the read request including the second priority information, said command outputting means selects said write queue when said state-number holding means holds any one of said first to fourth state numbers, and selects said read queue when said state-number holding means holds said fifth or sixth state number.
  41. 41
    The storage device control unit in accordance with claim 39, wherein the said read request includes any one of first to third priority information, each of read requests including at least said first priority information and said second priority information or each of the said write requests includes the delay limit value showing the maximum value of a period which is from the arrival time of the read request and the write request to the time when the read operation and the write operation finish. said plurality of queues are a first read queue which holds temporarily read requests including said first priority information and said second priority information in a queue, a second read queue which holds temporarily read requests including said third priority information in a queue, and a write queue which holds temporarily said write requests in a queue, comprising:allowable delay information computing/managing means for computing and managing an estimated processing period which is the estimated value of the period for the operation to be performed in compliance with each arrived read request or each arrived write request, an expected ending time when the operation is expected to finish, and an allowable delay value which is the value obtained by subtracting the expected ending time from the ending time, obtained by referring to said delay limit value, at which the operation has to finish. buffer memory managing/judging means for managing a used capacity of a buffer memory which stores temporarily data to be write into said storage devices and judging whether the used capacity is not less than a predetermined threshold value, comparing means for comparing the estimated processing period for the write request located at the head of the queue held in said write queue with each of the minimum allowable delay values for read requests composing the queue held in said first read queue, judging means for judging whether the read request or the write request is held in said first read queue, said second read queue or said write queue and whether a read request including the first priority information is held in the first read queue, wherein said position fixing means enqueues the read request including the first priority information to said queue so that the read request is outputted as a read command within a delay limit value for the read request, which is being held in said first read queue, including said second priority information and with priority to the read request including the second priority information, said state-number holding means holds: a first state-number showing a case where said buffer memory managing/judging means judges that said used capacity is a predetermined threshold value or more, a second state-number showing a case where said buffer memory managing/judging means judges that said used capacity is less than the predetermined threshold value, and the allowable delay value for the write request which is managed by said allowable delay information computing/managing means reaches the predetermined constant value, a third state-number showing a case where said buffer memory managing/judging means judges that said used capacity is less than the predetermined threshold value, and the allowable delay value for the write request which is managed by said allowable delay information computing/managing means does not reach the predetermined constant value, and further said judging means judges that the read request including the first priority information is not stored, and said comparing means judges that the estimated processing period for the write request is less than the minimum of the allowable delay value, chooses the write queue, a fourth state-number showing a case where said buffer memory managing/judging means judges that said used capacity is less than the predetermined threshold value, and the allowable delay value for the write request which is managed by said allowable delay information computing/managing means does not reach said predetermined constant value, and further said judging means judges that the read request including said first priority information is stored in said first read queue, a fifth state-number showing a case where said buffer memory managing/judging means judges that said used capacity is less than the predetermined threshold value, and the allowable delay value for the write request which is managed by said allowable delay information computing/managing means does not reach said predetermined constant value, and further said judging means judges that the read request including said first priority information is not stored in said first read queue, and said comparing means judges that the estimated processing period for the write request is more than the minimum of allowable delay value, a sixth state-number showing a case where said judging means judges that the write request is not stored in said write queue, and a seventh state-number showing a case where said judging means judges that the read request is stored only in said second read queue, said command outputting means chooses said write queue when said state-number holding means holds any one of said first to third state numbers, chooses said read queue when said state-number holding means holds said fourth to sixth state number, and chooses said read queue when said state-number holding means holds said seventh state number.
  42. 42
    The storage device control unit in accordance with claim 38, wherein said position fixing means, when a read request including said first priority information has newly arrived from the external, defines a read request which is located at the nearest to the tail of said first read queue and further including the second priority information as a sample request and said allowable delay information computing/managing means computes an estimated processing period for the arrived read request when said position fixing means temporarily fixes a position just ahead of said sample request to which to enqueue the newly arrived read request, and said position fixing means compares the estimated processing period for said newly-arrived read request with the allowable delay values for said sample request and each read requests including the second priority information and located behind the sample request, when each of said allowable delay values is the estimated processing period or more, fixes finally a position just ahead of said sample request to which to enqueue said newly-arrived read request, when at least one of said allowable delay values is less than the estimated processing period, judges whether said sample request is located at the tail of the queue held in said first read queue or not, when said sample request is located at the tail, enqueues said newly-arrived read request at the tail of the queue held in said first read queue, and, when said sample request is not located at the tail, defines a read request located just behind the sample request as a new sample request.
  43. 43
    The storage device control unit in accordance with claim 38, wherein said storage devices have disks for storing said unit blocks, said estimated processing period is computed based on seek time for a head of the storage devices to move between tracks or cylinders where, in said first and second read queue, each of the unit blocks to be read in compliance with the read request and the read request enqueued just ahead of said read request is stored, transfer time to transfer the unit block to be read in compliance with the read request from said disks, and predetermined overhead time and rotational latency.
  44. 44
    The storage device control unit in accordance with claim 38, wherein said estimated processing period means the period as a predetermined confidence limit which covers the set of measured period obtained by reading the data of same size as the unit block from said storage device plural times repetitively, or means the period as a predetermined confidence limit which covers the set of measured periods obtained by writing said data into said storage device plural times repetitively.
  45. 45
    A storage device management system, which applied to a system which distributes data divided into blocks as units for write to a plurality of storage devices, wherein each of said storage devices is provided with a first identifier which is different from that of the other storage devices, comprising:a first managing part which is used to manage at least each of said first identifier, a second managing part which manages an empty area of each of said storage devices with using said address of each empty block into which the block can be written and said first identifier, a destination determining part which creates a combination, with referring to said first and second managing porions, of said first identifier and said address for each of all or part of the storage devices and then rearrange the created combinations, and thereby determines destinations of the data.
  46. 46
    A storage device management system, which applied to a system which distributes data divided into blocks as units for write to a plurality of storage devices divided into predetermined groups, wherein each of said storage devices is provided with a first identifier which is different from that of the other storage devices belonging to the same group, each of said group is provided with a second identifier which is different form that of the other groups, comprising:a first managing part which manages at least each of said first identifier and each of said second identifier, a second managing part which manages an empty area of each of said storage devices with using address of each empty block into which said block can be written and said first and second identifier, a destination determining part which selects all or part of the groups, with referring to said first and second managing parts, and , in the group, selects one storage device for each , at random and so that the same storage device is not selected until all storage devices belonging to the group are selected thoroughly, and creates a combination of said first and second identifiers and said address for each of the selected storage devices and then rearranges the created combinations at random, and thereby determine destinations of the data.
  47. 47
    The storage device management system in accordance with claim 45, wherein at least one of said plurality of storage devices is different from the other storage devices in performance, when said data is distributed to the plurality of storage devices, the rate of the blocks distributed to each storage device is set, based on said performance, as a distribution rate, and said destination determining part selects storage devices for creating combinations according to said distribution rate, creates said combination for each of the selected storage device and further rearranges the created combinations at random.
  48. 48
    The storage device management system in accordance with claim 46, wherein at least one of the storage devices belonging to each of said group is different from the other storage devices belonging to the same group in performance, when said data are distributed to the plurality of storage devices, the rate of the blocks distributed to each storage device belonging to the same group is preset, based on said performance, as a first distribution rate, and when said data are distributed to the plurality of groups, the rate of the blocks distributed to each group is preset, based on the performance of the storage device belonging to the group, as a second distribution rate, and said destination determining part selects groups to be distributed said blocks thereto according to said second distribution rate, selects, as the storage device to create combinations, any one storage device belonging to the selected group according to said first distribution rate, creates said combination for each of the selected storage device and further rearranges the created combinations at random.
  49. 49
    The storage device management system in accordance with claim 47, wherein said distribution rate is beforehand managed therein.
  50. 50
    The storage device management system in accordance with claim 47, wherein said distribution rate is obtained therein based on said performance.
  51. 51
    The storage device management system in accordance with claim 48, wherein said first and/or second distribution rates are beforehand managed therein.
  52. 52
    The storage device management system in accordance with claim 48, wherein said first and/or second distribution rate is obtained therein based on said performance.
  53. 53
    The storage device management system in accordance with claim 52, wherein when said destination determining part repeats the random rearrangement of said created combinations and thereby the number of blocks where the destinations of said data being not determined becomes less than the number of said all or part of storage devices, said destination determining part selects storage devices for creating combinations based on the number of empty blocks which each storage device has and further creates said combination for each of the selected storage devices.
  54. 54
    The storage device management system in accordance with claim 52, wherein when said destination determining part repeats the random rearrangement of said created combinations, said destination determining part rearranges said created combinations at random, both in said determined data destination and in said rearranged combinations, so as not to distribute the data to the same storage device repetitively at the block corresponding to the predetermined number of combinations.
  55. 55
    The storage device management system in accordance with claim 52, wherein when each plural pieces of data which is different in his character from each other is distributed to said plural storage devices, said destination determining part takes out said addresses corresponding to the number of said character and masses the taken-out addresses, and further creates said combinations using the mass of addresses for each selected storage device.
  56. 56
    The storage device management system in accordance with claim 55, wherein said character means band when said data is write into the storage devices, and said destination determining part takes out said addresses of which the number of being determined based on said band.
  57. 57
    A storage device control unit for controlling write operation or read operation of data on storage devices in compliance with requests successively arrived from the external, wherein each of said requests has an access position for said write operation or read operation on said storage device, comprising:queue means for temporarily holding requests, which is not being processed standing in order of process in a queue, request receiving means for receiving a request newly arrived from the external, calculating limited rearrangement time for the arrived request and enqueuing the arrived request to said queue means, position fixing means for fixing a position to which to enqueue the requests received by said request receiving means to the position of said queue means so that a first condition is satisfied, and holding means for calculating and holding weighted time and expected ending time for each of the requests held in said queue means, wherein said limited rearrangement time is determined based on arrival time of the request, and said weighted time for each request held in said queue means is determined based on an access position which the request has and an access position which a request to be processed just ahead of the request has, said expected ending time is obtained by adding said weighted time to said arrival time, further comprising command outputting means for outputting requests held in said queue means in the order of said queue to said storage devices as commands, wherein said position to satisfy' the first condition is so that said expected ending time is not beyond said limited rearrangement time for each arrived request and the sum of said weighted time is the sum of said weighted time or less, assuming that the request received newly by said request receiving means is enqueued to the end of said queue.
  58. 58
    The storage device control unit in accordance with claim 57, wherein said requests are write requests to write data and read requests to read data, said queue means includes a write queue or a read queue to temporarily hold write requests and read requests which are not being processed, said request receiving means calculates the limited ending time for the request arrived newly from the external and enqueues the arrived request, and said command outputting means, when said expected ending time for each of the read requests held in said read queue is not beyond said limited ending time, preferentially outputs the write request held in said write queue as a command.
  59. 59
    The storage device control unit in accordance with claim 58, wherein maximum necessary period from the arrival time of the request to the finish of write operation in compliance with the request on the storage device is preset as maximum processing period, and said holding means changes said weighted time for the write request outputted as said command into said maximum processing period.
  60. 60
    The storage device control unit in accordance with claim 57, wherein the number of commands which can be outputted to said storage devices in a determined period by said command outputting means is preset, said command outputting means outputs commands so as not to exceed the number of said commands.
  61. 61
    The storage device control unit in accordance with claim 57, wherein said storage devices, when said write operation or read operation in compliance with said command finishes, outputs the ending time, further comprising command operation ending means for calculating a time difference between the ending time received from said storage devices and the expected ending time which the request has, the request being held in said holding means and having be processed in the storage device, wherein said holding means recalculates the expected ending time or the limited rearrangement time for each of the requests held in said queue means on the basis of the time difference obtained by said command operation ending means.
  62. 62
    The storage device control unit in accordance with claim 61, wherein said holding means, only when the time difference calculated by said command operation ending means is a predetermined value or more, recalculates said expected ending time or said limited rearrangement time.
  63. 63
    The storage device control unit in accordance with claim 57, wherein said requests are the write requests to write data and the read requests to read data, said queue means includes a write queue and a read queue, said request receiving means further calculates write priority time of the write request arrived newly from the external and enqueues the arrived request, said write queue and said read queue temporarily holds write requests and read requests received by said request receiving means, and said command outputting means, when said write queue holds the write request which reaches said write priority time of the request, preferentially outputs said command from the write queue.
  64. 64
    The storage device control unit in accordance with claim 57, wherein when requests standing connectively in order of process in a queue respectively have consecutive or the same access positions, said position fixing means does not enqueue requests received by said request receiving means between said consecutive requests.
  65. 65
    A process order deciding method for determining which position of a queue requests arriving connectively from the external are enqueued to, the queue being temporarily holding requests in a queue so that the request stands in order of process, wherein each of said requests has an access position on said storage device for said write operation or read operation, comprising:a first step of calculating and holding a weighted time and an expected ending time for each of the requests held in said queue, wherein said weighted time for each request held in said queue means is determined based on an access position which the request has and an access position which a request to be processed just ahead of the request has, and said expected ending time is obtained by adding said weighted time to the arrival time of the request in said queue, a second step of receiving a request arrived newly from the external, calculating limited rearrangement time for the arrived request and enqueuing the arrived request to said queue, wherein said limited rearrangement time is determined based on the arrival time of the request, a third step of enqueuing the requests arrived newly at said second step in a temporarily-determined position to satisfy a first condition and recalculating the weighted time and the expected ending time for each of the requests being held in the queue, and a fourth step of, when the weighted time and the expected ending time recalculated at said third step satisfies a second condition, determining that said newly-arrived request is enqueued to said temporarily-determined position, wherein said first condition is such that the access position which said newly-arrived request has and the access positions which requests located just ahead and/or behind the newly-arrived request have are consecutive access positions or the same access position, and said second condition is such that said expected ending time is not beyond said limited rearrangement time for all of already-arrived requests and the sum of said weighted time is the sum of said weighted time assuming that a request received newly at said first step is enqueued to the end of said queue, or less.
  66. 66
    A process order deciding method for determining which position of a queue requests arrived connectively from the external is enqueued, the queue temporarily holding requests in a queue so that the request stands in order of process, wherein each of said write or read requests has an access position for said write operation or read operation on said storage device and limited rearrangement time obtained by adding the predetermined period which is from the arrival time of the request to the finish time of the operation, weighted time for each request held in said queue is set so as to be determined based on an access position which the request has and an access position which a request to be processed just ahead of the request has, and expected ending time is set so as to be obtained by adding said weighted time to the arrival time of the request, comprising:a first step of receiving a request arrived newly from the external, calculating limited rearrangement time for the arrived request and enqueuing the arrived request to said queue, wherein said limited rearrangement time is determined based on the arrival time, a second step of enqueuing the newly-arrived request at said first step at the end of said queue as a temporarily-determined position and calculating a first sum of the weighted time which each request being held in said queue has, a third step of dequeuing said newly-arrived request from said queue, enqueuing the request in a new temporarily-determined position of said queue, calculating weighted time and expected ending time for each of the requests held in said queue and calculating a second sum of the weighted time, a fourth step of comparing said first sum with said second sum, a fifth step of judging whether the expected ending time for each of the requests obtained at said third step is earlier than a first limited time for each of the requests, a sixth step of fixing a position in said queue to which to enqueue said newly-arrived request as said newly-temporarily-determined position when said first sum is more than said second sum at said fourth step and the expected ending time for each of the requests is earlier than the first limited time for each of the requests at said fifth step.
  67. 67
    A process order deciding method for determining which position of a queue requests connectively arrived from the external are enqueued, the queue temporarily holding requests in a queue so that the request stands in order of process, wherein each of the said write or read requests has an access position on said storage device and limited rearrangement time obtained by adding predetermined time period which is from the arrival time of the request to the finish time of the operation, weighted time for each request held in said queue is set so as to be determined based on an access position which the request has and an access position which a request to be processed just ahead of the request has, and expected ending time obtained by adding said weighted time to the arrival time of the request, comprising:a first step of receiving a request arrived newly from the external, calculating limited rearrangement time for the arrived request and enqueuing the arrived request to said queue, wherein said limited rearrangement time is determined based on said arrival time of the request, a second step of enqueuing the newly-arrived request at said first step in any position of said queue as a temporarily-determined position, calculating weighted time which each request held in said queue has, and calculating and holding a sum of the calculated weighted time, wherein said first step is repeated until said newly-arrived requests are enqueued in all positions in said queue and thereby the sum of said weighted time can be obtained corresponding with the number of requests composing said queue, a second step of selecting the smallest sum from sums of plural of weighed time obtained by repeating said first step, a third step of setting temporarily a temporarily-determined position corresponding to the sum of weighted time selected at said second step for a position to enqueue said newly-arrived request to, a fourth step of calculating and holding said expected ending time for each of said requests composing said queue when said newly-arrived request is enqueued in said position set temporarily at said third step, and a fifth step of finally fixing said position set temporarily at said fourth step as said position to which to enqueue said newly-arrived request when each expected ending time obtained at said fourth step is earlier than the limited rearrangement time.
Independent claims67