Patent ID: 6871011

Claim:
A method of scheduling a new disk access request, comprising: a. maintaining at least one queue of disk access requests, representing each member in said queue by a data structure that records at least deadline, priority and scheduling time for each member; b. processing a new request for disk access by determining a scheduling time for said new request based on a deadline associated with said new request; c. scanning said queue to locate an insertion point for said new request by comparing the scheduling time and priority of said new request with the scheduling times and priorities of other members in said queue, said insertion point being selected such that the deadlines of members of higher priority than said new request are not violated; d. while scanning said queue in step c, identifying and marking members of lower priority than said new request; e. inserting said new request into said queue at said insertion point if so doing does not violate the deadline of any member of higher priority than said new request; f. if in step d one marked member was identified and if inserting said new request into said queue at said insertion point violates the deadline of any member of higher priority than said new request, then deleting said marked member and repeating steps e and f; g. if in step d at least no marked member was identified and if inserting said new request into said queue at said insertion point violates the deadline of any member of higher priority than said new request, then discard said new request.