Scheduling storage accesses for rate-guaranteed and non-rate-guaranteed requests
First Claim
1. A system for managing storage accesses for rate guaranteed continuous multimedia data streams and non-rate-guaranteed storage requests, comprising:
- a plurality of rate guaranteed requesters for multimedia data streams;
one or more non-rate-guaranteed requesters;
a disk scheduler, comprising a guaranteed rate queue for queuing storage requests from said rate guaranteed requesters;
a non-rate-guaranteed queue for queuing requests from said non-rate-guaranteed requesters; and
a bandwidth allocator coupled to said guaranteed rate queue and said non-rate-guaranteed queue, and further coupled to a storage system, wherein said bandwidth allocator is configured to allocate bandwidth of the storage system between said guaranteed rate queue and said non-rate-guaranteed queue according to a predetermined ratio.
2 Assignments
0 Petitions
Accused Products
Abstract
A system for managing storage accesses for rate guaranteed continuous multimedia data streams and non-rate-guaranteed storage requests may include a plurality of rate guaranteed requestors for multimedia streams and one or more non-rate guaranteed requesters. A disk scheduler may also be included. The disk scheduler may have a guaranteed rate queue for queuing storage requests from the rate guaranteed requestors and a non-rate-guaranteed queue for queuing requests from the non-rate-guaranteed requestors. The disk scheduler may also include a bandwidth allocator coupled to the guaranteed rate queue and the non-rate-guaranteed queue and further coupled to a storage system. The bandwidth allocator may be configured to allocate bandwidth of the storage system between the guaranteed rate queue and the non-rate-guaranteed queue according to a predetermined ratio. The rate guaranteed requestors may be limited so that an aggregate of maximum stream rates guaranteed for each rate guaranteed requestor does not exceed the portion of the bandwidth allocated to the guaranteed rate queue. Requests may be ordered in the guaranteed rate queue according to a deadline. Requests may be ordered in the non-rate guaranteed queue according to a priority. The system may also include a buffer ring for each multimedia data stream from one of the rate guaranteed requestors.
170 Citations
47 Claims
-
1. A system for managing storage accesses for rate guaranteed continuous multimedia data streams and non-rate-guaranteed storage requests, comprising:
-
a plurality of rate guaranteed requesters for multimedia data streams;
one or more non-rate-guaranteed requesters;
a disk scheduler, comprising a guaranteed rate queue for queuing storage requests from said rate guaranteed requesters;
a non-rate-guaranteed queue for queuing requests from said non-rate-guaranteed requesters; and
a bandwidth allocator coupled to said guaranteed rate queue and said non-rate-guaranteed queue, and further coupled to a storage system, wherein said bandwidth allocator is configured to allocate bandwidth of the storage system between said guaranteed rate queue and said non-rate-guaranteed queue according to a predetermined ratio. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A method for managing storage accesses for rate guaranteed continuous multimedia data streams and non-rate-guaranteed storage requests, the method comprising:
-
allocating a portion of a storage system'"'"'s bandwidth to stream requests from rate guaranteed requesters and allocating the remaining portion of the storage system'"'"'s bandwidth to requests from non-rate-guaranteed requesters;
queuing storage requests from rate guaranteed requesters in a guaranteed rate queue;
queuing storage requests from non-rate-guaranteed requesters in a non-rate-guaranteed queue; and
selecting either the guaranteed rate queue or the a non-rate-guaranteed queue according to the bandwidth allocation to migrate one of the requests to the storage system. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47)
migrating requests from said guaranteed rate and non-rate-guaranteed queues to a seek reorder queue according to the bandwidth allocation; and
reordering the migrated requests in said seek reorder queue according to their physical location within the storage system.
-
-
35. The method as recited in claim 34, further comprising:
-
traversing the seek reorder queue in one direction;
issuing the next request in the seek reorder queue to the storage system; and
reversing the direction of traversal when an end of the seek reorder queue is reached.
-
-
36. The method as recited in claim 24, further comprising repeating said allocating, said queuing storage requests from rate guaranteed requesters, queuing storage requests from non-rate-guaranteed requesters, and said selecting for each of a plurality of storage systems.
-
37. The method as recited in claim 36, further comprising mapping each request from said rate guaranteed requesters and said non-rate-guaranteed requesters to one of the storage systems containing a location of the request.
-
38. The method as recited in claim 37, wherein said mapping comprises:
-
directing requests from said rate guaranteed requesters and said non-rate-guaranteed requesters to the guaranteed rate queue or non-rate-guaranteed queue of the appropriate storage system; and
generating file system requests to the appropriate storage system.
-
-
39. The method as recited in claim 38, wherein said file system requests comprise time-critical file system requests and non-time-critical file system requests.
-
40. The method as recited in claim 39, further comprising:
-
ordering requests in said guaranteed rate queue according to a deadline, wherein the deadline for each request from one of the rate guaranteed requesters indicates a latest time by which that request must be fulfilled to meet a guaranteed maximum stream rate for the corresponding multimedia data stream; and
ordering requests in said non-rate-guaranteed queue according to a priority;
wherein said selecting comprises migrating the request with the highest priority from the non-rate-guaranteed queue.
-
-
41. The method as recited in claim 40, further comprising:
-
sending time-critical file system requests to the guaranteed rate queue with a corresponding deadline; and
sending non-time-critical file system request to the non-rate guaranteed queue with a corresponding priority.
-
-
42. The method as recited in claim 41, further comprising assigning non-time-critical file system requests a higher priority than requests from non-rate-guaranteed requesters.
-
43. The method as recited in claim 24, wherein requests from non-rate-guaranteed requesters include FTP or NFS file transfer requests.
-
44. The method as recited in claim 24, further comprising establishing a buffer ring for each multimedia data stream from one of the rate guaranteed requesters, said buffer ring buffering multimedia stream data between an associated rate-guaranteed requester and the storage system.
-
45. The method as recited in claim 44, further comprising sizing said buffer ring to contain a number of buffers chosen to prevent buffer underrun at a guaranteed maximum stream rate, wherein each buffer is sized to hold one block of multimedia data.
-
46. The method as recited in claim 45, further comprising:
-
consuming the buffers of each buffer ring by the associated rate guaranteed requester one after another in a circular order; and
as each buffer is consumed, issuing a request and a deadline for the just consumed buffer to the guaranteed rate queue, wherein the deadline indicates a time by which the request must be fulfilled to prevent underrun.
-
-
47. The method as recited in claim 46, further comprising calculating each deadline as:
Specification