Deadline driven disk scheduler method and apparatus with thresholded most urgent request queue scan window

• US 5,787,482 A
• Filed: 07/31/1995
• Issued: 07/28/1998
• Est. Priority Date: 07/31/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Chen, Shenze, Thapar, Manu
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): KIM, HONG CHONG
• Application Number:
  US08/509,074
• Time in Patent Office: 1,093 Days
• Field of Search: 395/439, 395/112, 395/478, 395/151, 395/485, 395/158, 395/826, 395/859, 395/860, 395/607, 395/672, 395/673, 395/874, 348/7
• US Class Current: 711/158
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G11B 27/105 of operating discs
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

A disk control mechanism for controlling the operations of a movable arm disk drive. The disk control mechanism contains a disk access scheduler which accepts disk access requests having a deadline and a disk location. The disk access scheduler further consists of a queue data structure for storing the requests. The queue contains a predefinded window that contains a certain number of requests with deadlines to expire sooner than all other requests. The request that is most soon to expire, the most urgent request, is located at the head of the queue. The disk access scheduler contains logic to determine whether the most urgent request has a deadline to expire sooner than tolerated by a set threshold, and in such cases the disk access scheduler schedules for service the most urgent request prior to any other request, otherwise it scans towards the most urgent request and schedules requests with a disk location between the current arm location and the most urgent request.

Claims

1. A method of controlling a disk drive with a movable arm, wherein said arm at any given point in time has a current location, comprising the steps of:

defining a threshold parameter;

accepting a plurality of disk access requests, each having a prescribed deadline and a disk address, wherein the disk access request with the most urgent deadline is the most urgent request;

storing the disk access requests in a queue having a front, such that the most urgent disk access request is at the front of the queue and such that the queue is sorted according to deadlines;

defining a window in said queue wherein said window contains a certain number of disk access requests in the front of said queue; and

processing requests in said queue by;

determining how much time is left before the deadline of the most urgent request in the queue expires;

if said time is less than the threshold, serve the most urgent request;

otherwise scan from said current arm location towards the disk address of said most urgent request; and

during said scan schedule the first encountered request that is in the scan path and that is in the window.

2. The method of claim 1, wherein said step of determining how much time is left before the deadline of the most urgent request expires comprises comparing the deadline for said most urgent request to the current clock time.

3. The method of claim 1, further comprising the step of defining the size of said window.

4. The method of claim 1, wherein subsequent to being serviced a request is removed from said queue and from said window.

5. A disk control mechanism for controlling the operations of a movable arm disk drive wherein at any given point in time, said movable arm has a current location, comprising:

a disk access scheduler operable to accept disk access requests having a deadline and a disk location, including;

a queue data structure for storing said requests, wherein one request is more urgent than any other request in said queue;

a window in said queue, wherein said window contains a certain number of requests with deadlines to expire sooner than all other requests; and

a logic to determine whether said most urgent request has a deadline to expire sooner than tolerated by a set threshold, and in such cases to service said most urgent request prior to any other request, otherwise to scan towards said most urgent request and to schedule any requests with disk locations between said current arm location and said most urgent request.

6. A data server, for real-time presentation of data stored on said data server, comprising:

at least one central processing unit;

at least one movable arm disk drive for storing data for presentation to customers, said disk drive arm having a current location;

a disk scheduler for each said movable arm disk drive, operable to accept requests for data stored on said disk drive, and to store said requests in a queue data structure such that a given number of requests with deadlines sooner to expire than all other requests are located within a window in said queue; and

wherein said disk schedulers are operable to determine whether a request in said queue that is more urgent than any other request has a deadline to expire prior to a permitted threshold, in such case to schedule to service such request next, otherwise to commence scanning from said disk drive arm'"'"'s current location toward said location of said most urgent request and scheduling for service all requests in said window and encountered during said scanning operation.

7. The data server of claim 6, wherein said threshold and said given number of requests in said window are adjustable parameters of said disk schedulers.