Method and system for scheduling I/O operations for processing
An operations scheduler and a method of scheduling I/O operations to be processed by a memory drive are disclosed. The method includes receiving I/O operations, and for each one of them determining an estimated processing time, and an estimated processing period indicative of an estimated deadline. The method also includes determining a scheduled order of I/O operations based on the respective estimated deadlines. The method also includes monitoring an actual processing time for the I/O operations and adjusting a virtual time of the operations scheduler if a given actual processing time is above a given estimated processing time of a given I/O operation.
1. A method of scheduling a plurality of input/output (I/O) operations to be processed by a memory drive, the memory drive being part of a distributed computer system having:
a plurality of I/O sources, the plurality of I/O sources having a first I/O source and a second I/O source, the plurality of I/O sources originating the plurality of I/O operations;
each of the first I/O source and the second I/O source being associated with a respective pre-determined proportion of processing bandwidth of the memory drive for processing I/O operations from each one of the first I/O source and the second I/O source;
an operations scheduler implementing a scheduling algorithm for scheduling the plurality of I/O operations for transmission to the memory drive,
the method executable by the operations scheduler, the method comprising:
receiving (i) at least one I/O operation originated by the first I/O source and (ii) at least one I/O operation originated by the second I/O source;
determining, based on memory drive characteristics, an estimated processing time for (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source;
determining an estimated processing period for each of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source by using (i) the respective estimated processing time and (ii) the respective pre-determined proportion of processing bandwidth of the memory drive,
a respective estimated processing period being indicative of an estimated processing deadline, the estimated processing deadlines expressed in a virtual time of the operations scheduler;
executing the scheduling algorithm to determine a scheduled order of I/O operations based on the respective estimated processing deadlines of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source;
monitoring by the operations scheduler an actual processing time for the processing of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source,
the actual processing time being an actual time taken by the memory drive to process (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source;
in response to the actual processing time being above the estimated processing time for any one of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source, adjusting the virtual time of the operations scheduler.
2. The method of claim 1 , wherein the adjusting the virtual time comprises:
when determining an estimated processing period for an other I/O operation, adding an amount of time to the estimated processing period for the other I/O operation thereby determining an adjusted estimated processing period for the other I/O operation,
the amount of time being a difference between the actual processing time and the estimated processing time for (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source.
3. The method of claim 2 , wherein the adjusted estimated processing period for the other I/O operation is indicative of an adjusted estimated processing deadline for the other I/O operation.
4. The method of claim 1 , wherein the monitoring by the operations scheduler the actual processing time for (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source comprises receiving, from the memory drive, processing confirmations indicative of the actual processing time for (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source.
5. The method of claim 1 , wherein the scheduling algorithm is a real-time type scheduling algorithm.
6. The method of claim 5 , wherein the real-time type scheduling algorithm is an Earliest Deadline First-type (EDF-type) scheduling algorithm.
7. The method of claim 1 , wherein the determining the estimated processing period for each of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source comprises determining a ratio between the respective estimated processing time and the respective pre-determined proportion of processing bandwidth of the memory drive.
8. The method of claim 7 , wherein the estimated processing period for a given one of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source is determined such that the given one of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source is non-suspendably processable within the estimated processing period while respecting the respective pre-determined proportion of processing bandwidth of the memory drive.
9. The method of claim 8 , wherein the given I/O operation is a non-suspendable I/O operation.
10. The method of claim 1 , wherein the determining the estimated processing time for each one of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source is performed by a prediction model emulating operation of the memory drive based on the memory drive characteristics.
11. An operations scheduler for scheduling a plurality of input/output (I/O) operations to be processed by a memory drive, the memory drive being part of a distributed computer system having:
a plurality of I/O sources, the plurality of I/O sources having a first I/O source and a second I/O source, the plurality of I/O sources originating the plurality of I/O operations;
each of the first I/O source and the second I/O source being associated with a respective pre-determined proportion of processing bandwidth of the memory drive for processing I/O operations from each one of the first I/O source and the second I/O source;
the operations scheduler implementing a scheduling algorithm for scheduling the plurality of I/O operations for transmission to the memory drive, the operations scheduler being configured to:
receive (i) at least one I/O operation originated by the first I/O source and (ii) at least one I/O operation originated by the second I/O source;
determine, based on memory drive characteristics, an estimated processing time for (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source;
determine an estimated processing period for each of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source by using (i) the respective estimated processing time and (ii) the respective pre-determined proportion of processing bandwidth of the memory drive,
a respective estimated processing period being indicative of an estimated processing deadline, the estimated processing deadlines expressed in a virtual time of the operations scheduler;
execute the scheduling algorithm to determine a scheduled order of I/O operations based on the respective estimated processing deadlines of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source;
monitor by the operations scheduler an actual processing time for the processing of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source,
the actual processing time being an actual time taken by the memory drive to process (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source;
in response to the actual processing time being above the estimated processing time for any one of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source, adjust the virtual time of the operations scheduler.
12. The operations scheduler of claim 11 , wherein the operations scheduler configured to adjust the virtual time comprises the operations scheduler being configured to:
when determining an estimated processing period for an other I/O operation, add an amount of time to the estimated processing period for the other I/O operation thereby determining an adjusted estimated processing period for the other I/O operation,
the amount of time being a difference between the actual processing time and the estimated processing time for (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source.
13. The operations scheduler of claim 12 , wherein the adjusted estimated processing period for the other I/O operation is indicative of an adjusted estimated processing deadline for the other I/O operation.
14. The operations scheduler of claim 11 , wherein the operations scheduler configured to monitor the actual processing time for (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source comprises the operations scheduler being configured to receive, from the memory drive, processing confirmations indicative of the actual processing time for (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source.
15. The operations scheduler of claim 11 , wherein the scheduling algorithm is a real-time type scheduling algorithm.
16. The operations scheduler of claim 15 , wherein the real-time type scheduling algorithm is an Earliest Deadline First-type (EDF-type) scheduling algorithm.
17. The operations scheduler of claim 11 , wherein the operations scheduler configured to determine the estimated processing period for each of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source comprises the operations scheduler being configured to determine a ratio between the respective estimated processing time and the respective pre-determined proportion of processing bandwidth of the memory drive.
18. The operations scheduler of claim 17 , wherein the estimated processing period for a given one of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source is determined such that the given one of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source is non-suspendably processable within the estimated processing period while respecting the respective pre-determined proportion of processing bandwidth of the memory drive.
19. The operations scheduler of claim 18 , wherein the given I/O operation is a non-suspendable I/O operation.
20. The operations scheduler of claim 11 , wherein the operations scheduler is configured to determine the estimated processing time for each one of (i) the at least one I/O operation originated by the first I/O source and (ii) the at least one I/O operation originated by the second I/O source by using a prediction model emulating operation of the memory drive based on the memory drive characteristics.