Systems and methods for assigning tasks to derived timers of various resolutions in real-time systems to maximize timer usage

• US 20060064689A1
• Filed: 08/31/2004
• Published: 03/23/2006
• Est. Priority Date: 08/31/2004
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Zhang, Chao
• Granted Patent: US 7,210,053 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

One or more derived timers based on a source timer are provided to accommodate a plurality of periodic tasks while maintaining the high resolution of the source timer. To accommodate a number of periodic tasks, a number of derived timers can be selected utilizing a novel method based on the number of periodic tasks that are most time-critical, the number of tasks that are less time-critical, and the number of tasks that can be performed during the source timer interval. The interval and start time for each derived timer is selected based the source timer and number of the derived timer. After establishing the derived timers, the most time-critical tasks can be assigned to the source timer and the less time-critical tasks arranged amongst the derived timers.

Claims

1. A method of providing timers for a plurality of periodic tasks, comprising:

providing a source timer having a source timer interval;

determining a first number of the plurality of periodic tasks that can be completed during said source timer interval;

classifying a second number of the plurality of periodic tasks as most time-critical;

classifying a third number of the plurality of periodic tasks as less time-critical; and

providing a number of derived timers to be used for said plurality of tasks, wherein providing said number of derived timers includes determining said number to provide as greater than or equal to one less than a first result determined by dividing said third number of less time-critical tasks by a difference between said first number of the plurality of the periodic tasks that can be completed during said source timer interval and said second number of most time-critical tasks.

2. The method of claim 1, further comprising;

determining an interval for each of said derived timers, wherein determining said interval for each of said derived timers includes multiplying said source timer interval by 2ⁿ wherein n is a positive whole number used to individually represent each of said derived timers, said n having a maximum value equal to said number of derived timers and having a minimum value of one.

3. The method of claim 2, wherein:

said number of derived timers includes a first derived timer;

n equals one for said first derived timer; and

said first derived timer has an interval equal to 2 times said source timer interval.

4. The method of claim 2, wherein:

said source timer includes a start time; and

said method further comprises;

determining a start time for each of said derived timers, wherein determining said start time for each of said derived timers includes adding said source timer start time to a second result determined by multiplying said source timer interval by 2<sup>n−

1</sup>.

5. The method of claim 4, wherein:

said number of derived timers includes a first derived timer having a largest interval of said number of derived timers;

said first derived timer includes a first instance having a start time determined by adding said source timer start time to said second result determined by multiplying said source timer interval by 2<sup>n−

1</sup>; and

said first derived timer includes a second instance having a start time equal to said source timer start time.

6. The method of claim 5, further comprising:

assigning said third number of less time-critical tasks to said derived timers.

7. The method of claim 6, wherein:

said step of assigning includes assigning a first selected number of said third number of less time-critical tasks to each of said derived timers except said first derived timer, said first selected number is equal to said difference between said first number of the plurality of the periodic tasks that can be completed during said source timer interval and said second number of most time-critical tasks.

8. The method of claim 7, wherein said step of assigning includes:

assigning a first half of a second selected number of said third number of less time-critical tasks to said first instance of said first derived timer, said second selected number is equal to two times said difference between said first number of the plurality of the periodic tasks that can be completed during said source timer interval and said second number of most time-critical tasks; and

assigning a second half of said second selected number of said third number of less time-critical tasks to said second instance of said first derived timer.

9. The method of claim 8, further comprising:

classifying a subset of said third number of less time-critical tasks as least critical tasks, said second selected number is a number of tasks in said subset of least time-critical tasks.

10. The method of claim 9, wherein:

said step of classifying is performed prior to said steps of assigning a first half and assigning a second half.

11. The method of claim 1, wherein said step of classifying a second number of the plurality of period tasks as most time-critical tasks comprises:

determining which of the plurality of periodic tasks must be completed during said source timer interval; and

classifying those periodic tasks that must be completed during said source timer interval as most time-critical.

12. The method of claim 11, wherein said step of determining which of the plurality of periodic tasks do not have to completed during said source timer interval comprises:

determining which periodic tasks of the plurality have a hard time-limit that is less than said source timer interval.

13. The method of claim 1, wherein said step of classifying a third number of the plurality of periodic tasks as less time-critical comprises:

determining which periodic tasks of the plurality do not have to be completed during said source timer interval; and

classifying those periodic tasks that do not have to be completed during said source timer interval as less time-critical.

14. The method of claim 13, wherein said step of determining which of the plurality of periodic tasks do not have to be completed during said source timer interval comprises:

determining which periodic tasks of the plurality have a hard time-limit that is greater than said source timer interval.

25. The system of claim 1, wherein said second number of less time-critical tasks do not have to be completed during said source timer interval.

26. The system of claim 25, wherein said second number of less time-critical tasks have a hard time-limit that is greater than said source timer interval.

15. A system for time-based task processing, comprising;

a plurality of periodic tasks including a first number of tasks that are most time-critical and a second number of tasks that are less time-critical;

a source timer having a source timer interval, wherein a third number of said plurality of periodic tasks are capable of being completed during said source timer interval; and

a number of derived timers based on said source timer, said number of derived timers is greater than or equal to one less than a first result obtained by dividing said second number of less time-critical tasks by a difference between said third number of said plurality of periodic tasks capable of being completed during said source timer interval and said first number of most time-critical tasks.

16. The system of claim 15, wherein;

each of said derived timers has an interval equal to a second result obtained by multiplying said source timer interval by 2ⁿ wherein n is a positive whole number used to individually represent each of said derived timers, said n having a maximum value equal to said number of derived timers and having a minimum value of one.

17. The system of claim 16, wherein:

said number of derived timers includes a first derived timer;

n equals one for said first derived timer; and

said first derived timer has an interval equal to 2 times said source timer interval.

18. The system of claim 16, wherein:

said source timer includes a start time; and

each of said derived timers has a start time equal to a third result obtained by adding said source timer start time to a fourth result determined by multiplying said source timer interval by 2<sup>n−

1</sup>.

19. The system of claim 18, wherein:

said number of derived timers includes a first derived timer having a largest interval of said number of derived timers;

said first derived timer includes a first instance having a start time determined by adding said source timer start time to said third result; and

said first derived timer includes a second instance having a start time equal to said source timer start time.

20. The system of claim 19, wherein:

a first selected number of said second number of less time-critical tasks is assigned to each of said derived timers except said first derived timer, said first selected number is equal to said difference between said third number of the plurality of the periodic tasks that can be completed during said source timer interval and said first number of most time-critical tasks.

21. The system of claim 20, wherein:

a first half of a second selected number of said second number of less time-critical tasks is assigned to said first instance of said first derived timer, said second selected number is equal to two times said difference between said third number of the plurality of the periodic tasks that can be completed during said source timer interval and said first number of most time-critical tasks; and

assigning a second half of said second selected number of said second number of less time-critical tasks to said second instance of said first derived timer.

22. The system of claim 21, further comprising:

said second selected number of said second number of less time-critical tasks are least time-critical tasks.

23. The system of claim 15, wherein said first number of most time-critical tasks must be completed during said source timer interval.

24. The system of claim 23, wherein said first number of most time-critical tasks have a hard time-limit that is less than said source timer interval.

27. One or more processor readable storage devices having processor readable code embodied on said one or more processor readable storage devices, said processor readable code for programming one or more processors to perform a method comprising:

providing a source timer having a source timer interval;

determining a first number of the plurality of periodic tasks that can be completed during said source timer interval;

classifying a second number of the plurality of periodic tasks as most time-critical;

classifying a third number of the plurality of periodic tasks as less time-critical; and

providing a number of derived timers to be used for said plurality of tasks, wherein providing said number of derived timers includes determining said number to provide as greater than or equal to one less than a first result determined by dividing said third number of less time-critical tasks by a difference between said first number of the plurality of the periodic tasks that can be completed during said source timer interval and said second number of most time-critical tasks.

28. One or more processor readable storage devices according to claim 27, wherein the method further comprises:

determining an interval for each of said derived timers, wherein determining said interval for each of said derived timers includes multiplying said source timer interval by 2ⁿ, wherein n is a positive whole number used to individually represent each of said derived timers, said n having a maximum value equal to said number of derived timers and having a minimum value of one.

29. One or more processor readable storage devices according to claim 28, wherein:

said source timer includes a start time; and

said method further comprises;

determining a start time for each of said derived timers, wherein determining said start time for each of said derived timers includes adding said source timer start time to a second result determined by multiplying said source timer interval by 2<sup>n−

1</sup>.

30. One or more processor readable storage devices according to claim 29, wherein:

said number of derived timers includes a first derived timer having a largest interval of said number of derived timers;

said first derived timer includes a first instance having a start time determined by adding said source timer start time to said second result determined by multiplying said source timer interval by 2<sup>n−

1</sup>; and

said first derived timer includes a second instance having a start time equal to said source timer start time.

31. One or more processor readable storage devices according to claim 30, wherein said method further comprises:

assigning said third number of less time-critical tasks to said derived timers.

32. One or more processor readable storage devices according to claim 31, wherein:

said step of assigning includes assigning a first selected number of said third number of less time-critical tasks to each of said derived timers except said first derived timer, said first selected number is equal to said difference between said first number of the plurality of the periodic tasks that can be completed during said source timer interval and said second number of most time-critical tasks.

33. One or more processor readable storage devices according to claim 32, wherein said step of assigning includes:

assigning a first half of a second selected number of said third number of less time-critical tasks to said first instance of said first derived timer, said second selected number is equal to two times said difference between said first number of the plurality of the periodic tasks that can be completed during said source timer interval and said second number of most time-critical tasks; and

assigning a second half of said second selected number of said third number of less time-critical tasks to said second instance of said first derived timer.

34. One or more processor readable storage devices according to claim 33, wherein said method further comprises:

classifying a subset of said third number of less time-critical tasks as least critical tasks, said second selected number is a number of tasks in said subset of least time-critical tasks.

35. One or more processor readable storage devices according to claim 34, wherein:

said step of classifying is performed prior to said steps of assigning a first half and assigning a second half.

36. One or more processor readable storage devices according to claim 27, wherein said step of classifying a second number of the plurality of period tasks as most time-critical tasks comprises:

determining which of the plurality of periodic tasks must be completed during said source timer interval; and

classifying those periodic tasks that must be completed during said source timer interval as most time-critical.

37. One or more processor readable storage devices according to claim 27, wherein said step of classifying a third number of the plurality of periodic tasks as less time-critical comprises:

determining which periodic tasks of the plurality do not have to be completed during said source timer interval; and

classifying those periodic tasks that do not have to be completed during said source timer interval as less time-critical.