Method for scheduling operations called by a task on a real-time or non-real time processor

• US 7,734,833 B2
• Filed: 09/08/2005
• Issued: 06/08/2010
• Est. Priority Date: 09/08/2005
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul Edward
• Primary Examiner(s): Tsai; Henry W. H.
• Assistant Examiner(s): Sun; Michael
• Application Number:
  US11/222,525
• Publication Number:
  US 20070083871A1
• Time in Patent Office: 1,734 Days
• Field of Search: 710/5
• US Class Current: 710/5
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

Provided is a method for scheduling operations called by a task on a real-time or non-real-time processor. Execution durations are provided for operations. A call is received from a task for an operation. A determination is made of a latency requirement for a first processor and of the execution duration of the called operation. The called operation is executed on the first processor in response to determining that the determined execution duration is less than the latency requirement. The called operation is executed on a second processor in response to determining that the determined execution duration is greater than the latency requirement.

Claims

1. A method, comprising:

receiving a call from a real-time task for an operation, wherein said real time task is required to complete within a given time interval;

prior to starting an execution of the operation, determining a latency requirement for a real time processor, said latency requirement defined as a maximum delay within which all tasks assigned to the real time processor are guaranteed to begin execution;

prior to starting the execution of the operation, determining a maximum execution duration of the called operation;

executing the called operation on the real time processor in response to determining that the determined execution duration is less than the latency requirement; and

executing the called operation on a non real time processor in response to determining that the determined execution duration is greater than the latency requirement.

2. The method of claim 1, further comprising:

transferring execution of a task from one processor comprising one of the real time and non-real time processors to another processor comprising one of the real time and non-real time processors by placing the task in a shared queue to be transferred from one processor to another.

3. The method of claim 1, wherein determining the latency requirement comprises:

providing a delay tolerance for each real time task indicating a time within which execution of the task must begin in response to being called; and

determining a minimum delay tolerance for a set of tasks.

4. The method of claim 3, wherein tasks may be of a real time type or a non-real-time type, wherein tasks of the real time type are assigned to the real time processor for execution and wherein tasks of the non-real time type are assigned to the non-real-time processor for execution, wherein the set of tasks for which delay tolerances are provided comprises the real-time type of tasks.

5. The method of claim 4, wherein tasks of the real time type have a higher execution priority over tasks of the non-real time type.

6. The method of claim 4, wherein the real time type of task is deterministic and wherein the non-real time type of tasks is non-deterministic.

7. The method of claim 1, wherein the latency requirement is a maximum delay time during which execution of tasks assigned to the real time processor must begin.

8. The method of claim 1, wherein each real time task is executed on a thread in the operating system, wherein each real time task invokes multiple operations, and wherein the operations invoked by the tasks are members of a set of operations comprising system calls, interrupts and exceptions.

9. The method of claim 1, wherein the latency requirement comprises a first latency requirement associated with the first real time processor and wherein a second latency requirement is associated with a third processor and is greater than the first latency requirement, wherein the task is executing on the first real time processor when the call for operation is received, and wherein the operations further comprise:

determining whether the determined execution duration is less than the second latency requirement in response to determining that the determined execution duration is greater than the first latency requirement; and

executing the called operation on the third real time processor in response to determining that the determined execution duration is greater than the second latency requirement, wherein the called operation is executed on the second real time processor in response to determining that the determined execution duration is greater than both the first and second latency requirements.

10. The method of claim 1, wherein the task is executing on is executing on real time processor, and wherein the operations further comprise:

transferring the task to the non-real time processor to execute the called operations in response to determining that the operation is to be executed on the non-real time processor; and

transferring the task to the real time processor to continue executing the task in response to the non-real time processor completing execution of the called operation.

11. An article of manufacture including code executed to perform operations to schedule tasks between a first processor and a second processor, the operations comprising:

receiving a call from a real-time task for an operation, wherein said real time task is required to complete within a given time interval;

prior to starting an execution of the operation, determining a latency requirement for a real time processor, said latency requirement defined as a maximum delay within which all tasks assigned to the real time processor are guaranteed to begin execution;

prior to starting the execution of the operation, determining a maximum execution duration of the called operation;

executing the called operation on the real time processor in response to determining that the determined execution duration is less than the latency requirement; and

executing the called operation on a non real time processor in response to determining that the determined execution duration is greater than the latency requirement.

12. The article of claim 11, wherein determining the latency requirement comprises:

providing a delay tolerance for each real time task indicating a time within which execution of the task must begin in response to being called; and

determining a minimum delay tolerance for a set of tasks.

13. The article of claim 12, wherein tasks may be of a real time type or a non-real-time type, wherein tasks of the real time type are assigned to the real time processor for execution and wherein tasks of the non-real time type are assigned to the non-real-time processor for execution, wherein the set of tasks for which delay tolerances are provided comprises the real-time type of tasks.

14. The article of claim 13, wherein tasks of the real time type have a higher execution priority over tasks of the non-real time type.

15. The article of claim 13, wherein the real time type of task is deterministic and wherein the non-real time type of tasks is non-deterministic.

16. A system comprising:

a first processor;

a second processor;

a memory; and

an operating system executed in the memory to perform operations, the operations comprising;

receiving a call from a real-time task for an operation, wherein said real time task is required to complete within a given time interval;

prior to execution of the operation, determining a latency requirement for a real time processor, said latency requirement defined as a maximum delay within which all tasks assigned to the real time processor are guaranteed to begin execution;

prior to execution of the operation, determining a maximum execution duration of the called operation;

executing the called operation on the real time processor in response to determining that the determined execution duration is less than the latency requirement; and

executing the called operation on a non real time processor in response to determining that the determined execution duration is greater than the latency requirement.

17. The system of claim 16, wherein the operation for determining the latency requirement further comprise:

providing a delay tolerance for each real time task indicating a time within which execution of the task must begin in response to being called; and

determining a minimum delay tolerance for a set of tasks.

18. The system of claim 17, wherein tasks may be of a real time type or a non-real-time type, wherein tasks of the real time type are assigned to the real time processor for execution and wherein tasks of the non-real time type are assigned to the non-real-time processor for execution, wherein the set of tasks for which delay tolerances are provided comprises the real-time type of tasks.

19. The system of claim 18, wherein tasks of the real time type have a higher execution priority over tasks of the non-real time type.

20. The system of claim 18, wherein the real time type of task is deterministic and wherein the non-real time type of tasks is non-deterministic.