FILE SYSTEM HAVING PREDICTABLE REAL-TIME PERFORMANCE

• US 20070067595A1
• Filed: 09/15/2006
• Published: 03/22/2007
• Est. Priority Date: 09/16/2005
• Status: Active Grant

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Ghose, Kanad
• Granted Patent: US 8,046,558 B2
• Time in Patent Office: Days
• US Class Current: 711/167
• CPC Class Codes: G06F 16/1865 Transactional file systems
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0674 Disk device

Abstract

A file system that permits predictable accesses to file data stored on devices that may have a variable access latency dependent on the physical location of the file on the physical storage device. A variety of features that guarantee timely, real-time response to I/O file system requests that specify deadlines or other alternative required quality-of-service parameters. The file system addresses needs to accommodate the file systems of storage devices such as disks that have an access time dependant on the physical location of the data within the storage device. A two-phase, deadline-driven scheduler considers the impact of disk seek time on overall response times. Non real-time file operations may be preempted. Files may be preallocated to help avoid access delay caused by non-contiguity. Disk buffers may also be preallocated to improve real-time file system performance.

Claims

1. A method for managing access to a file storage system having predictable variable latency, comprising:

(a) providing at least one queue of operations, at least a portion of the operations having associated operation time constraints for completion;

(b) receiving at least one request for completion of a new operation within a respective new operation time constraint for completion;

(c) inserting the new operation into the queue of operations, consistent with completion within the respective new operation time constraint; and

(d) for at least one new operation, reordering the queue to defer processing of at least one operation inconsistent with completion of processing of the new operation within the respective new operation time constraint, wherein the at least one operation which is deferred is placed in a queue position consistent with completion within its associated operation time constraint.

2. The method according to claim 1, wherein at least a portion of the operations have no deadline for completion, further comprising the step of:

(e) preempting at least one operation having no deadline for completion by the new operation.

3. The method according to claim 1, wherein at least one operation in the at least one queue has a deadline time constraint.

4. The method according to claim 1, wherein the new operation and at least two operations in the at least one queue each have an associated priority, wherein a priority of a first operation is higher than a priority of a second operation, and wherein a priority of the new operation is intermediate, wherein the second operation is deferred.

5. The method according to claim 1, wherein at least one request for operation is associated with a predictable variable operation time constraints for completion, and at least one operation does not have a predictable variable operation time constraints for completion.

6. The method according to claim 1, wherein at least one request for operation is associated with a preassigned priority, and at least one operation is not associated with a preassigned priority.

7. A method for managing access to a file storage system having predictable variable latency for file system operations, comprising:

(a) providing a queue of operations to be performed, each operation having a predicted variable latency, and at least a portion of the operations having associated operation time constraints for completion;

(b) receiving at least one request for completion of a new operation having a predicted variable latency and an associated new operation time constraint for completion; and

(c) inserting the new operation into the queue of operations, consistent with performing all queued operations having associated time constraints within their respective associated operation time constraints, based on at least available time and predicted variable latencies of the respective operations, and for at least one new operation, deferring at least one operation previously in the queue.

8. The method according to claim 7, wherein at least one operation is associated with a priority, wherein operations having respectively higher priorities are assured completion with respective associated operation time constraints ahead of operations having respectively lower priorities.

9. The method according to claim 7, wherein at least one operation is associated with a deadline, wherein said inserting step ensures that deadlines are met, and that an optimum ordered set of operations are completed within respective operation time constraints in dependence on available time slots, and a respective order sensitive predicted variable latency of respective operations.

10. The method according to claim 7, wherein at least one operation is associated with a deadline, a plurality of operations are associated with respective priorities, wherein said inserting step ensures that deadlines are met, and that an optimum ordered set of operations permits respectively higher priority operations to be completed within deadlines ahead of respectively lower priority operations.

11. The method according to claim 7, wherein at least one request for operation is associated with a predictable variable operation time constraints for completion, and at least one operation does not have a predictable variable operation time constraints for completion.

12. The method according to claim 7, wherein at least one request for operation is associated with a preassigned priority, and at least one operation is not associated with a preassigned priority.

13. A computer readable medium storing program instructions for controlling a processor to perform a method for managing access to a file storage system having predictable variable latency for file system operations, comprising:

(a) providing a queue of operations to be performed, each operation having a predicted variable latency, and at least a portion of the operations having associated operation time constraints for completion;

(b) receiving at least one request for completion of a new operation having a predicted variable latency and an associated new operation time constraint for completion;

(c) for at least one new operation, inserting the new operation into the queue of operations, consistent with performing all queued operations having associated time constraints within their respective associated operation time constraints, based on at least available time and predicted variable latencies of the respective operations, and deferring at least one operation previously in the queue.

14. The method for managing access to a file storage system having predictable variable latency, comprising:

(a) providing at least one scheduling queue of operations, at least a portion of the operations having associated operation time constraints for completion;

(b) receiving at least one request for completion of a new operation within a respective new operation time constraint for completion;

(c) inserting the new operation into the scheduling queue of operations;

(d) reordering the scheduling queue in accordance with a first criterion; and

(e) subsequently reordering the scheduling queue in accordance with a second criterion,

wherein;

for at least one new operation, the reordering the scheduling queue and subsequent reordering of the scheduling queue together defer or preempt processing of at least one operation inconsistent with completion of processing of the new operation within the respective new operation time constraint,

the at least one operation which, if deferred, is placed in a scheduling queue position consistent with completion within its associated operation time constraint,

the scheduling queue ordering in any phase can result in the preemption or deferring of operations previously ordered by the scheduling queue steps of each phase,

the scheduling queue is analyzed to remove dependent operations from a preempted operation, and

requests for operations resulting from the reordering the scheduling queue in accordance with a first criterion can be preempted by said subsequently reordering the scheduling queue in accordance with a second criterion.

15. The method according to claim 14, wherein at least a portion of the operations have no deadline for completion, further comprising the step of preempting at least one operation having no deadline for completion.

16. The method according to claim 14, wherein at least one operation in the at least one queue has a deadline time constraint.

17. The method according to claim 14, wherein the new operation and at least two operations in the at least one queue each have an associated priority, wherein a priority of a first operation is higher than a priority of a second operation, and wherein a priority of the new operation is intermediate, wherein the second operation is deferred or preempted.

18. The method according to claim 14, wherein at least one operation is associated with a predictable variable operation time constraint for completion, and at least one operation does not have a predictable variable operation time constraints for completion.

19. The method according to claim 14, wherein at least one operation is associated with a preassigned priority, and at least one operation is not associated with a preassigned priority.

20. A file storage system having predictable variable latency for file system operations, comprising:

(a) a queue of operations to be performed, each operation having a predicted variable latency, and at least a portion of the operations having associated operation time constraints for completion;

(b) an input for receiving at least one request for completion of a new operation having a predicted variable latency and an associated new operation time constraint for completion;

(c) a scheduler, which inserts the new operation into the queue of operations, consistent with performing all queued operations having associated time constraints within their respective associated operation time constraints, based on at least available time and predicted variable latencies of the respective operations, and for at least one new operation, deferring at least one operation previously in the queue.