File system having predictable real-time performance

A method for managing access to a file storage system, comprising:

• (a) providing a queue of operations to be performed, each operation having a predicted latency, and at least a portion of the operations having associated operation time constraints for performance or relative priority according to a prioritization scheme;
• (b) receiving at least one request for performance of a new operation having a predicted latency and an associated new operation time constraint for performance or relative priority;
• (c) providing a queue of constituent tasks, derived from the queue of operations, the queue of constituent tasks being ordered independently of the queue of operations, at least a portion of the constituent tasks having a required order of completion of processing;
• and
• d) reordering the queue of constituent tasks consistent with the required order of processing and with performing queued constituent tasks having associated time constraints within their respective associated operation time constraints for performance or in accordance with the prioritization scheme, and removing selected constituent tasks from the queue of constituent tasks which are inconsistent with performing the remaining queued constituent tasks having associated time constraints within their respective associated operation time constraints for performance, based on at least available time and predicted latency, wherein said reordering comprises deferring at least one operation previously in the queue to a queue placement after the at least one new operation and after an operation it was previously before.

A method for managing access to a file storage system, comprising:

• (a) providing at least one scheduling queue of operations, at least a portion of the operations having associated operation time constraints for completion or a predetermined relative priority;
• (b) receiving at least one request for completion of a new operation having a respective new operation time constraint for completion or a predetermined relative priority;
• (c) inserting the new operation into the at least one scheduling queue of operations;
• (d) defining at least one low level queue of constituent tasks dependent from operations in the at least one scheduling queue, at least a portion of the constituent tasks having a required order of completion of execution;
• (e) reordering the at least one low level queue in accordance with a first criterion;
• and
• (f) subsequently reordering the at least one low level queue in accordance with a second criterion,
• wherein:
• for at least one new operation, the reordering and subsequent reordering of the at least one low level queue together defer or preempt processing of at least one operation whose dependent constituent tasks pre-reordering placement in the low level queue is inconsistent with completion of processing of the new operation within the respective new operation time constraint, and the required order of execution is obeyed,
• the at least one operation which, if deferred, has its constituent tasks placed in a low level queue position consistent with completion within its associated operation time constraint and in accordance with its relative priority and after completion of at least one operation it was previously before, the consistency being determined based on low level queue order, and the available time,
• the respective low level queue ordering in any phase can result in the preemption or deferring of operations previously ordered by the respective scheduling queue ordering steps of each phase,
• the at least one low level queue is analyzed to remove dependent constituent tasks from a preempted operation, and
• constituent tasks in the low level queue resulting from the reordering of the at least one low level queue in accordance with a first criterion can be preempted by said subsequently reordering of the at least one low level queue in accordance with a second criterion.

A file storage system, comprising:

• (a) a queue of operations to be performed, at least a portion of the operations having associated operation time constraints for completion or a relative priority;
• (b) an input for receiving at least one request for completion of a new operation having an associated new operation time constraint for completion or relative priority;
• (c) a scheduler, which defines an ordering of constituent tasks dependent from the operations in the queue of operations in a low level queue, and inserts constituent tasks dependent from the new operation into the low level queue, and reorders the low level queue, consistent with performing all queued operations having associated time constraints within their respective associated operation time constraints and in accordance with any predetermined prioritization algorithm, and respecting any order dependence of the constituent tasks to avoid violation of order dependency of constituent tasks, based on at least available time, a queue order, and with respect to at least one new operation, either deferring at least one constituent task required for completion of at least one operation previously in the low level queue, after at least one constituent task required for completion of the new operation, and after a constituent task it was previously before, or preempting at least one constituent task in the low level queue which cannot be processed consistent with completion of the new operation within its new operation time constraint for completion and respecting the predetermined prioritization algorithm.

A system for managing access to a file storage system, comprising:

• (a) an interface for communicating with a file storage system;
• and
• (b) an automated control, adapted to:
• (i) maintain at least one high level queue of operations to be performed, and generate entries in at least one low level queue of operations to be performed, the at least one low level queue containing component operations of respective composite operations in the at least high level queue, at least a portion of the operations in the high level queue having associated operation time constraints for completion or relative priorities, and at least a portion of the operations in the at least one high level queue of operations having a processing order completion dependence;
• (ii) receive a request for completion of at least one new high level operation having an associated new operation time constraint for completion or a relative priority;
• and
• (iii) automatically reordering at least the low level queue of operations, consistent with:
• (1) the processing order completion dependence,
• (2) performing all queued operations having associated time constraints within their respective associated operation time constraints, and
• (3) a prioritization scheme dependent on the relative priorities,
• wherein at least one operation in the at least one low level queue prior to the receipt of request for completion of the at least one new high level operation is deferred to a placement after an operation in the at least one low level queue it was previously before, and
• wherein at least one low level queue of operations is analyzed for an inconsistency with the associated time constraints, and in an event of such an inconsistency, at least one high level operation is removed from the at least one high level queue to achieve consistency with the associated time constraints.

A method for operation of an automated system having predictable latency for operations, comprising:

• (a) receiving a plurality of processes to be performed by the system into a first queue, at least a portion of the processes having a respective associated time window within which completion is required;
• (b) determining a set of constituent tasks of the plurality of processes, at least a portion of the constituent tasks having a required relative order of execution;
• (c) placing the set of constituent tasks together into a second queue, wherein constituent tasks of a first process are interspersed with constituent tasks of a second process, while respecting the associated time window within which completion is required and the required relative order of execution;
• (d) receiving an additional process into the first queue, having a respective associated time window within which completion is required;
• (e) determining a set of constituent tasks of the additional process, at least a portion of the constituent tasks having a required relative order of execution;
• (f) if the respective associated time windows within which completion is required for each process can probably be observed, adding the set of constituent tasks of the additional process to the second queue, respecting the required relative order of execution of the constituent tasks of each process, selectively dependent on the predictable latency, wherein a relative order of execution of at least a portion of the constituent tasks of the first and second processes in the second queue is modified to meet the associated time window for completion of the first process, the second process, and the additional process;
• (g) if maintenance of the first process, second process and additional process in the first queue will probably lead to a violation of respective associated time windows within which completion is required for each process, removing at least one process from the first queue, and its respective constituent tasks from the second queue, in dependence on a relative priority for each respective process;
• and
• (h) executing with the automated system the constituent tasks in the order defined by the second queue to thereby complete the processes in the first queue within their respective associated time windows within which completion is required.