Method and apparatus for scheduling tasks

• US 7,500,241 B1
• Filed: 10/10/2003
• Issued: 03/03/2009
• Est. Priority Date: 10/10/2003
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Flockhart, Andrew D., Steiner, Robert C., Roybal, Larry John
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): Kawsar; Abdullah Al
• Application Number:
  US10/683,039
• Time in Patent Office: 1,971 Days
• Field of Search: 718 1-108
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A scheduler system for use in connection with a resource allocation system is provided. According to the present invention, a plurality of queues are provided for scheduling the delivery of tasks or events to a resource. Each of the provided queues may have a different threshold time, allowing the queues to be segmented according to the time values of included tasks. In accordance with an embodiment of the present invention, a primary queue comprising a delta queue is provided for tasks that are to be performed during a first period of time, while one or more secondary scheduler queues are provided for tasks that are scheduled to be performed after the first period of time.

Claims

1. A computerized method for queuing tasks, comprising:

providing a first primary scheduler queue;

selecting a non-zero threshold time for said first primary scheduler queue;

providing a first secondary scheduler queue;

selecting a threshold time for said first secondary scheduler queue, wherein said threshold time for said first secondary scheduler queue is greater than said threshold time for said first primary scheduler queue;

receiving a first task;

determining a scheduled time for said first task, wherein said scheduled time is a time interval;

in response to said scheduled time for said first task not exceeding said threshold time for said first primary scheduler queue, placing said first task in said first primary scheduler queue;

determining whether said scheduled time associated with said first task or a scheduled time associated with another task in said first primary scheduler queue has expired;

in response to said scheduled time associated with said first task or said another task expiring, delivering said first task or said another task to a resource;

receiving a second task;

determining a scheduled time for said second task, wherein said scheduled time is a time interval;

in response to said scheduled time for said second task exceeding said threshold time for said first primary scheduler queue, placing said second task in said first secondary scheduler queue;

storing a record of a time to a next scheduled task stored in said first secondary scheduler queue;

decrementing said scheduled time associated with each of said scheduled tasks stored in said first secondary scheduler queue;

in response to said time to a next scheduled task stored in said first secondary scheduler queue being one of less than or equal to said threshold time for said first primary scheduler queue, scanning said first secondary scheduler queue for at least one task having a scheduled time at least one of less than said threshold time for said first primary scheduler queue and equal to said threshold time for said first primary scheduler queue; and

moving said at least one task having a scheduled time at least one of less than said threshold time for said first primary scheduler queue and equal to said threshold time for said first primary scheduler queue from said first secondary scheduler queue to said first primary scheduler queue.

2. The method of claim 1, further comprising:

providing a second secondary scheduler queue;

receiving a third task;

determining a scheduled time for said third task; and

in response to said scheduled time for said third task exceeding a threshold time for said first secondary scheduler queue, placing said third task in said second secondary scheduler queue.

3. The method of claim 2, wherein said threshold time for said first secondary scheduler queue is less than a threshold time for said second secondary scheduler queue.

4. The method of claim 3, further comprising:

storing a record of a time to a next scheduled task stored in said second secondary scheduler queue;

in response to said time to a next scheduled task stored in said second secondary scheduler queue being one of less than said threshold time for said first secondary scheduler queue and equal to said threshold time for said first secondary scheduler queue, scanning said second secondary scheduler queue for at least one task having a scheduled time at least one of less than said threshold time for said first secondary scheduler queue and equal to said threshold time for said first secondary scheduler queue; and

moving said at least one task to said first secondary scheduler queue.

5. The method of claim 1, further comprising:

identifying in said first primary scheduler queue a task having a scheduled time equal to zero; and

providing said task having a scheduled time equal to zero to a resource.

6. The method of claim 5, further comprising:

providing a second primary scheduler queue; and

selecting a threshold time for said second primary scheduler queue, wherein said threshold time for said second primary scheduler queue is less than a threshold time for said first secondary scheduler queue.

7. The method of claim 1, wherein said first primary scheduler queue comprises a delta queue, and wherein said first secondary scheduler queue comprises a scheduling array.

8. An event scheduler device, comprising:

a processor;

memory, including;

a first primary scheduler queue;

a first secondary scheduler queue, wherein a first received task having a first scheduled time less than a first threshold is placed in said first primary scheduler queue, wherein said first scheduled time is a time interval, wherein said first threshold is greater than zero, wherein a second received task having a second scheduled time greater than said first threshold is placed in said first secondary queue, wherein said scheduled time of said second received task is maintained by a timer, wherein scheduled times of tasks placed in said first secondary queue are periodically decremented, wherein in response to said scheduled time value of said second received task as maintained by said timer dropping below said first threshold time said second received task is moved from said first secondary scheduler queue to said first primary scheduler queue; and

a communication channel, wherein at least one of said first received task and said second received task is delivered to a resource from said first primary scheduler queue using said communication channel in response to at least one of said first scheduled time and said second scheduled time reaching a value of zero.

9. The device of claim 8, further comprising:

a second secondary scheduler queue.

10. The device of claim 8, wherein said first primary scheduler queue is a delta queue, and wherein said first secondary scheduler queue is a scheduling array.

11. The device of claim 8, further comprising:

a resource.

12. A computational component including instructions stored in memory that are executable by a processor for performing a method, the method comprising:

providing a primary queue and a secondary queue;

selecting a non-zero threshold time for said primary queue;

receiving a first task;

determining a scheduled time associated with said first task, wherein said scheduled time associated with said first task is a time interval;

in response to said scheduled time associated with said first task having a value that is less than a threshold time of said primary queue, placing said first task in said first primary queue;

in response to said scheduled time associated with said first task having a value that is greater than a threshold time of said primary queue, placing said first task in said secondary queue;

storing a time equal to a scheduled time of a task stored in said secondary queue having a next time to expire;

decrementing said scheduled time associated with said first task and any other task placed in said secondary queue;

in response to said stored time equaling a first value, scanning said secondary queue for said task having a next time to expire; and

moving said task having a next time to expire to said primary queue.

13. The method of claim 12, wherein said first value is equal to said threshold time of said primary queue.

14. The method of claim 12, wherein said providing a secondary queue further comprises providing a first secondary queue and a second secondary queue, the method further comprising:

selecting a threshold time for said first secondary queue;

selecting a threshold time for said second secondary queue; and

in response to said scheduled time associated with said first task having a value that is greater than a threshold time of said first secondary queue, placing said first task in said second secondary queue.

15. The method of claim 12, further comprising:

receiving an instruction to reschedule said first task;

locating said first task;

associating a new scheduled time with said first task;

in response to said new scheduled time associated with said first task having a value that is less than a threshold time of a said primary queue, placing said first task in said primary queue; and

in response to said new scheduled time associated with said first task having a value that is greater than a threshold time of said primary queue, placing said first task in a secondary queue.

16. A resource allocation system having a processor, comprising:

means for receiving events;

first means for queuing a plurality of events having a time for performing an associated task that is less than a non-zero threshold amount for said first means for queuing;

second means for queuing a plurality of events;

means for determining a time associated with an event, wherein said time associated with an event is a time interval, wherein a received event is placed in one of said first means for queuing and said second means for queuing based on said determined time associated with said event;

means for monitoring a time to expire of a next event in said first means for queuing a plurality of events to expire; and

means for moving an expired event from said first means for queuing to resource means;

means for decrementing said time associated with an event placed in said second means for queuing;

means for monitoring said time associated with a next event in said second means for queuing a plurality of events; and

means for moving an event having a time to expire of less than a first selected value from said second means for queuing to said first means for queuing.