Prediction Based Priority Scheduling

Abstract

Systems and methods are provided that schedule task requests within a computing system based upon the history of task requests. The history of task requests can be represented by a historical log that monitors the receipt of high priority task request submissions over time. This historical log in combination with other user defined scheduling rules is used to schedule the task requests. Task requests in the computer system are maintained in a list that can be divided into a hierarchy of queues differentiated by the level of priority associated with the task requests contained within that queue. The user-defined scheduling rules give scheduling priority to the higher priority task requests, and the historical log is used to predict subsequent submissions of high priority task requests so that lower priority task requests that would interfere with the higher priority task requests will be delayed or will not be scheduled for processing.

What is claimed is: 
     
         1 . A method for scheduling task requests, the method comprising:
 maintaining a plurality of queues for receiving a plurality of task requests to be processed within a computing system, the plurality of task request comprising high priority task requests and low priority task requests;   identifying a low priority task request to be scheduled for processing;   using a predictor mechanism to determine a probability that a high priority task request will be received during execution of the low priority task request based on a history of received task requests and a likelihood of receipt of given types of task requests at any given time; and   scheduling the low priority task request based upon the determined probability.   
     
     
         2 . The method of  claim 1 , wherein the step of scheduling the low priority task request comprises immediately processing the low priority task request, postponing processing of the low priority task request for a specified period of time and rejecting processing of the low priority task request. 
     
     
         3 . The method of  claim 1 , wherein the step of maintaining the plurality of queues further comprises maintaining at least two queues, each queue associated with a distinct priority level, wherein the associated priority level of each task request received in any given queue is substantially the same as the distinct priority level of that queue. 
     
     
         4 . The method of  claim 3 , wherein the step of maintaining the list in at least two queues further comprises:
 maintaining a high priority queue for receiving the high priority task requests; and   maintaining a low priority queue for receiving the low priority task requests.   
     
     
         5 . The method of  claim 3 , wherein the step of identifying the low priority task request to be scheduled further comprises identifying an oldest low priority task request in the plurality of queues to be scheduled. 
     
     
         6 . The method of  claim 1 , wherein the plurality of task requests comprises resource requests within the computing system. 
     
     
         7 . The method of  claim 6 , wherein the resource requests comprise memory requests. 
     
     
         8 . A computer-readable medium containing a computer-readable code that when read by a computer causes the computer to perform a method for scheduling task requests, the method comprising:
 maintaining a plurality of queues for receiving a plurality of task requests to be processed within a computing system, the plurality of task request comprising high priority task requests and low priority task requests;   identifying a low priority task request to be scheduled for processing;   using a predictor mechanism to determine a probability that a high priority task request will be received during execution of the low priority task request based on a history of received task requests and a likelihood of receipt of given types of task requests at any given time; and   scheduling the low priority task request based upon the determined probability.   
     
     
         9 . The computer-readable medium of  claim 8 , wherein the step of scheduling the low priority task request comprises immediately processing the low priority task request, postponing processing of the low priority task request for a specified period of time and rejecting processing of the low priority task request. 
     
     
         10 . The computer-readable medium of  claim 8 , wherein the step of maintaining the plurality of queues further comprises maintaining at least two queues, each queue associated with a distinct priority level, wherein the associated priority level of each task request received in any given queue is substantially the same as the distinct priority level of that queue. 
     
     
         11 . The computer-readable medium of  claim 10 , wherein the step of maintaining the list in at least two queues further comprises:
 maintaining a high priority queue for receiving the high priority task requests; and   maintaining a low priority queue for receiving the low priority task requests.   
     
     
         12 . The computer-readable medium of  claim 10 , wherein the step of identifying the low priority task request to be scheduled further comprises identifying an oldest low priority task request in the plurality of queues to be scheduled. 
     
     
         13 . The computer-readable medium of  claim 8 , wherein the plurality of task requests comprises resource requests within the computing system. 
     
     
         14 . The computer-readable medium of  claim 13 , wherein the resource requests comprise memory requests.