Queuing architecture including a plurality of queues and associated method for scheduling disk access requests for video content

• US 6,378,036 B2
• Filed: 03/12/1999
• Issued: 04/23/2002
• Est. Priority Date: 03/12/1999
• Status: Expired due to Term

• Current Assignee: Cox Communications Incorporated (Cox Enterprises Incorporated)
• Original Assignee: DIVA Systems Corporation
• Inventors: Taylor, Clement G., Lerman, Jesse S., Chin, Danny, Fredrickson, James
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US09/268,512
• Publication Number:
  US 20010011374A1
• Time in Patent Office: 1,138 Days
• Field of Search: 711/112, 711/113, 711/114, 711/151, 711/158, 711/167, 710/39, 710/40, 710/44, 710/54, 710/52, 710/57, 710/6, 710/5, 710/45, 348/7, 709/103, 725/87, 725/92, 725/94, 725/97
• US Class Current: 711/112
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04N 21/2326 Scheduling disk or memory reading operations

Abstract

A queuing architecture and method for scheduling disk drive access requests in a video server. The queuing architecture employs at least two access request queues for each disk drive within a disk drive array, and a queue selector for selecting the first and second queues. The first queue is for disk access requests by steady-state users requesting new data streams who are currently viewing a program from the video server. The second queue is for all other types of disk access requests, including requests by new users, requests for loading content, disk maintenance, meta-data synchronizing, and the like. Steady-state disk access requests are serviced in order of ascending time deadlines. The queue selector gives highest priority to requests in the first queue, and requests from the second queue are serviced only upon a guarantee that all of the steady-state requests in the first queue will meet their time deadlines in the worst case access times for the disk drives. The second queue may comprise multiple queues to provide a queuing hierarchy including a third queue. Non-steady-state disk access requests are serviced on a first-in-first-out basis. The queue selector establishes priority in response to the location of the data upon a disk in a disk drive, and data may be stored in a disk drive based upon the queuing priority. The selecting and forwarding of the access requests to a disk drive may be performed repeatedly while an internet queue within a disk drive is not full, and there are outstanding access requests for that disk drive.

Claims

1. A queuing architecture for scheduling disk drive access requests in an information server, comprising, for each disk drive associated with said information server:

a first queue for disk access requests from users currently receiving information provided by the information server;

a second queue for all other disk access requests; and

a queue selector for selecting requests from said first and second queues and forwarding said requests to a disk drive associated with the information server.

2. The queuing architecture of claim 1, wherein said information server determines worst-case disk access times for each request and whether requests in said first and second queues can be executed within the time deadlines of the first queue, assuming said worst-case disk access times.

3. The queuing architecture of claim 1, where requests in said first queue each have an associated time deadline.

4. The queuing architecture of claim 1, where requests in said first queue are ordered from front to back by ascending time deadlines.

5. The queuing architecture of claim 1, where said queue selector gives highest priority to requests in said first queue and lower priority to requests in said second queue.

6. The queuing architecture of claim 1, wherein said information server is a video server and said information is a video program.

7. A queuing architecture for scheduling disk drive access requests in an information server, comprising, for each disk drive associated with said information server:

a first queue for disk access requests from users currently receiving information provided by the information server;

a second queue for all disk access requests from users requesting new data streams;

a third queue for all other disk access requests; and

a queue selector for selecting requests from said first, second, and third queues and forwarding said requests to a disk drive associated with the information server.

8. The queuing architecture of claim 7, wherein said information server determines worst-case disk access times for each request, and whether requests in said first and second queues can be executed within the time deadlines of the first queue, assuming said worst-case disk access times.

9. The queuing architecture of claim 7, where requests in said first queue each have an associated time deadline.

10. The queuing architecture of claim 7, where requests in said first queue are ordered from front to back by ascending time deadlines.

11. The queuing architecture of claim 7, where said queue selector gives highest priority to requests in said first queue, a lower priority to requests in said second queue and a lowest priority to requests in said third queue.

12. The queuing architecture of claim 7, where said third queue contains requests for loading content and disk maintenance.

13. The queuing architecture of claim 7, wherein said information server is a video server and said information is a video program.

14. A method of scheduling access requests for a disk drive in an information server, said method comprising the steps of:

(a) providing at least two queues, where a first queue contains steady-state access requests from users being supplied information from the information server and a second queue for all other types of access requests;

(b) selecting an access request from said second queue, if such selection does not cause a steady-state access request to miss a time deadline within which the steady-state access request must be completed to ensure that the information being viewed is not interrupted;

(c) otherwise, selecting one of the steady-state access requests; and

(d) forwarding the selected request to said disk drive.

15. The method of claim 14 wherein the selecting and forwarding steps are performed repeatedly while an internal queue within the disk drive is not full, and there are outstanding access requests for said disk drive.

16. The method of claim 14 further comprising the steps of checking, before forwarding the selected request to said disk drive, if data for the selected request is in a cache, and discarding the selected request if the data is in said cache.

17. The method of claim 14 wherein the steady-state access request selected in step c is the steady-state access request with the earliest time deadline.

18. A method of scheduling access requests for a plurality of disk drives associated with a video server, said method comprising the steps of:

ordering said disk drives by earliest time deadline of steady-state access requests for each of said plurality of disk drives; and

for each of said plurality of disk drives,

providing three queues, where a first queue contains steady state access requests from users being supplied a program from the video server, a second queue contains new programming access requests and a third queue for all other types of access requests;

selecting a next new programming access request, if such selection does not cause any steady-state access request to miss its associated time deadline within which that steady-state access request must be completed, to ensure that the program being viewed is not interrupted;

otherwise, selecting a next other access request, if such selection does not cause any steady-state access request to miss its associated time deadline within which that steady-state access request must be completed, to ensure that the program being viewed is not interrupted;

otherwise, selecting a steady-state access request with the earliest associated time deadline within which that steady-state access request must be completed, to ensure that the program being viewed is not interrupted; and

forwarding the selected request to a disk drive of said plurality of disk drives that is associated with the selected request.

19. The method of claim 18, where the selecting and forwarding steps are performed repeatedly while an internal queue of the disk drive associated with the selected request is not full, and there are outstanding access requests for the disk drive associated with the selected request.

20. A method of scheduling access requests for a plurality of disk drives associated with a video server, said method comprising the steps of:

providing, for each of the disk drives associated with said plurality of disk drives, three queues, where a first queue contains steady-state access requests from users being supplied a program from the video server, a second queue contains new programming access requests and a third queue for all other types of access requests;

determining which of said disk drives has completed a command;

ordering said disk drives that have completed a command by earliest time deadline of steady-state access requests for said disk drives; and

for each of said disk drives that has completed a command,

selecting the next new programming request, if such selection does not cause any steady-state access request to miss its associated time deadline within which that steady-state access request must be completed, to ensure that the program being viewed is not interrupted;

otherwise, selecting a next other type access request, if such selection does not cause any steady-state access request to miss its associated time deadline within which that steady-state access request must be completed, to ensure that the program being viewed is not interrupted;

otherwise, selecting the steady-state access request with the earliest associated time deadline; and

forwarding the selected request to a disk drive of said plurality of disk drives that is associated with the selected request.

21. The method of claim 20, where said method is performed every time one of said disk drives has completed a command.

22. The method of claim 20, where said method is performed within a scheduling interval.