System and method for robust time partitioning of tasks in a real-time computing environment

• US 20020198925A1
• Filed: 08/20/2002
• Published: 12/26/2002
• Est. Priority Date: 09/16/1999
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Smith, Joe, Larson, Aaron
• Granted Patent: US 7,207,042 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A time-partitioned system for accounting for processor time consumed by operating system services provided on behalf of an application runs in a real-time environment. The time utilized by the operating system is treated as application processing time, rather than viewing the resultant processor time consumed as an operating system overhead. Each application consists of one or more threads. A time budget is assigned to each thread and to each interrupt. The processor time consumed by the operating system when executing on behalf of a thread or interrupt is charged back to the application or interrupt as part of the application'"'"'s time budget. Operating system overheads and processor interrupts are thus accounted for accurately enough to determine a schedule for the applications that is enforceable by the operating system at run time.

Claims

1. A method of apportioning access to a computer resource for a computer application, the method comprising the steps of:

providing the application with a process time budget to use the computer resource;

assigning a portion of the process time budget to each of a plurality of threads according to a thread time budget for each of the threads, wherein each of the threads is associated with the application; and

enforcing the assigned thread time budget for each of the plurality of threads in real time.

2. The method of claim 1 wherein at least one of the threads is an interrupt thread that is assigned according to the occurrence of an interrupt.

3. The method of claim 2 further comprising the step of assigning a periodic time budget to the interrupt thread.

4. The method of claim 3 wherein the periodic time budget comprises a periodic boundary and a replenishment period.

5. The method of claim 1 further comprising the step of scheduling each of the threads according to a period of time associated with the thread to create a schedule for the computing resource.

6. The method of claim 5 further comprising the step of modifying the schedule in real time to accommodate changes in the threads.

7. The method of claim 1 wherein the assigning step comprises apportioning overhead time associated with each of the threads into the thread time budget for each of the threads.

8. The method of claim 1 wherein each thread time budget comprises a thread execution time and a reserved overhead.

9. The method of claim 8 wherein the reserved overhead comprises a first portion of time corresponding to the time consumed by the longest critical section of instructions executed by the operating system during which interrupts are disabled.

10. The method of claim 9 wherein the reserved overhead comprises a second portion of time corresponding to a transitional time used by the processing resource to switch between the threads.

11. The method of claim 5 further comprising the step of releasing the computing resource when one of the plurality of threads terminates.

12. The method of claim 5 wherein the enforcing step comprises denying creation of at least one of the threads when insufficient time for the thread remains in the schedule.

13. The method of claim 1 wherein the enforcing step comprises ensuring that each of the plurality of threads do not consume more time on the computing resource than the thread time budget allows.

14. The method of claim 6 further comprising the step of releasing the computing resource when one of the plurality of threads terminates.

15. The method of claim 6 wherein the enforcing step comprises denying creation of at least one of the threads when insufficient time for the thread remains in the schedule.

17. The system of claim 16 wherein the scheduling step further comprises allocating a second portion of the processor time to process interrupts.

18. The system of claim 17 further comprising pre-empting the execution of the threads to process an interrupt if the duration of time required to process the interrupt does not exceed the second portion of the processor time.

20. The method of claim 19 wherein the assigning step comprises apportioning overhead time associated with each of the threads into the thread time budget for each of the threads.

21. The method of claim 20 further comprising the step of assigning an interrupt time budget to an interrupt process requiring access to the computing resource.

22. The method of claim 21 wherein the scheduling step comprises scheduling the interrupt process to incorporate the interrupt time budget into the schedule.

23. The method of claim 22 wherein the scheduling step further comprises preempting one or more of the plurality of threads to accommodate the interrupt process.

24. The method of claim 19 wherein each thread time budget comprises a thread execution time and a reserved overhead period.

25. The method of claim 24 wherein the reserved overhead period comprises a first portion of time during which interrupts are masked and a second portion of time corresponding to a transitional time used by the processing resource to switch between the threads.

26. The method of claim 25 further comprising the step of modifying the schedule in real time to accommodate changes in the threads.

27. The method of claim 26 wherein the modifying step comprises releasing the computing resource when one of the plurality of threads terminates.

28. The method of claim 27 wherein the scheduling step comprises denying thread creation when insufficient time for the thread remains in the schedule.

29. The method of claim 19 wherein the scheduling and enforcing steps operate in real time.

30. The method of claim 19 wherein the enforcing step comprises ensuring that each of the plurality of threads do not consume more time on the computing resource than the thread time budget allows.

31. A time-partitioned system for assigning processor time consumed by operating system services provided on behalf of an application running in a real-time environment, the system being operable to execute the method of claim 1.

32. A time-partitioned system for assigning processor time consumed by operating system services provided on behalf of an application running in a real-time environment, the system being operable to execute the method of claim 2.

33. A time-partitioned system for accounting for processor time consumed by operating system services provided on behalf of an application running in a real-time environment, the system being operable to execute the method of claim 16.

34. A time-partitioned system for accounting for processor time consumed by operating system services provided on behalf of an application running in a real-time environment, the system being operable to execute the method of claim 19.

36. The system of claim 35 wherein at least one of the threads is an interrupt thread that is assigned according to the occurrence of an interrupt.

38. The system of claim 37 wherein at least one of the threads is an interrupt thread that is assigned according to the occurrence of an interrupt.

16. A method for accounting for processor time consumed by operating system services provided on behalf of an application running in a real-time environment, the method comprising the steps of:

allocating a portion of the processor time to each of a plurality of threads associated with the application to create a time budget for each of the plurality of threads;

scheduling the execution of each of the plurality of threads according to a period of time associated with the thread to create a schedule; and

enforcing the schedule to execute each of the plurality of threads in the real-time environment such that each threads usage of processor time does not exceed the thread'"'"'s time budget.

19. A method of providing access to a computer resource for a plurality of computer applications, the method comprising the steps of:

providing each of the applications with an application time budget to use the computer resource;

assigning a portion of each application time budget to each of a plurality of threads, wherein each of the threads is associated with the application, to create a thread time budget for each of the threads;

scheduling each of the plurality of threads according to a period of time associated with the thread to create a schedule for the computing resource; and

enforcing the schedule for the computing resource.

35. A system apportioning access to a computer resource for a computer application, the system comprising:

means for providing the application with a process time budget to use the computer resource;

means for assigning a portion of the process time budget to each of a plurality of threads according to a thread time budget for each of the threads, wherein each of the threads is associated with the application; and

means for enforcing the assigned thread time budget for each of the plurality of threads for the computing resource in real time.

37. A system apportioning access to a computer resource for a computer application, the system comprising:

a first software module configured to provide the application with a process time budget to use the computer resource;

a second software module configured to assign a portion of the process time budget to each of a plurality of threads according to a thread time budget for each of the threads, wherein each of the threads is associated with the application; and

a third software module configured to enforce the assigned thread time budget for each of the plurality of threads for the computing resource in real time.