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

7,207,042

10/223954

August 20, 2002

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.

Smith, Joseph A (Phoenix, AZ, US); Larson, Aaron (Shoreview, MN, US)

Honeywell International Inc. (Morristown, NJ, US)

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 wherein overhead time associated with each thread is apportioned into that thread's thread time budget; and enforcing the assigned thread time budget for each of the plurality of threads to thereby operate the computer resource entirely 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. A time-partitioned computer system for assigning processor time consumed by operating system services provided on behalf of an application running in a real-time environment, the system executing the method of claim 2 .

6. 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.

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

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

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

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

11. 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.

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

13. The method of claim 12 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.

14. The method of claim 13 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.

15. 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.

16. A time-partitioned computer system for assigning processor time consumed by operating system services provided on behalf of an application running in a real-time environment, the system executing the method of claim 1 .

17. 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, wherein overhead time associated with each thread is apportioned into that thread's time budget; and enforcing the schedule to execute each of the plurality of threads in the real-time environment such that each thread's usage of processor time does not exceed the thread's time budget.

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

19. The method of claim 18 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. A time-partitioned computer 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 executing the method of claim 17 .

21. 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, wherein overhead time associated with each thread is apportioned into that thread's time budget; 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 to thereby operate the computing resource entirely in real-time.

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

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

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

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

26. The method of claim 21 wherein each tread time budget comprises a thread execution time and a reserved overhead period.

27. The method of claim 26 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.

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

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

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

31. The method of claim 21 wherein the scheduling and enforcing steps operate in real time.

32. The method of claim 21 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.

33. A time-partitioned computer 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 executing the method of claim 21 .

34. A system apportioning access to a computer resource for a computer application, the system comprising a computer-readable storage medium having computer-executable instructions stored thereon, the computer-readable instructions 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 wherein overhead time associated with each thread is apportioned into that thread's thread time budget; and means for enforcing the assigned thread time budget for each of the plurality of threads to thereby operate the computing resource entirely in real time.

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

36. A system apportioning access to a computer resource for a computer application, the system comprising a computer-readable storage medium having computer-executable instructions stored thereon, the computer-readable instructions 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 wherein overhead time associated with each thread is apportioned into that thread's thread time budget; 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 entirely real time.

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

718/104

5339415 August 1994 Strout et al.
5386561 January 1995 Huynh et al.
5812844 September 1998 Jones et al.
6085215 July 2000 Ramakrishnan et al.
6317774 November 2001 Jones et al.
6385638 May 2002 Baker-Harvey
6754690 June 2004 Larson
WO01/20446 March 2001

Schwan, Karsten et al. “Dynamic Scheduling of Hard Real-time Tasks and Real-Time Threads.” IEEE. Aug. 1992. cited by examiner
Jones, Micael B. et al. “CPU Reservations and Time Constraints: Efficient, Predicatable Scheduling of Independent Activities.” ACM. Oct. 1997. cited by examiner
Molano, Anastasio et al. “Real-Time Filesystems.” IEEE. 1997. cited by examiner
Nilsen, Kelvin. “Issues in the Design and Implementation of Real-Time Java.” Jul. 19, 1996. cited by examiner
David B. Stewart and P.K. Khosta; “High-assurance softwre systems are often implemented with the dangerous assumption that timing errors will never occur”; Communications of the ACM; Jan. 1997; vol. 40, No. 1. cited by other
J.M. Andre, A. Kung, P. Robin; “OX: ADA Cyclic Executive for Embedded Applications”; Proceedings of an International Symposium on On-Board Real-time Software: ESTEC; Noordwijk, Nov. 13-15, 1995. cited by other
A. Atlas and A. Bestavros; “Statistical Rate Monotonic Scheduling”; IEEE Computer Soc.; Dec. 2, 1998; pp. 123-132. cited by other
International Search Report; PCT/US00/25543; Sep. 13, 2001; 4 pgs. cited by other
Atlas, Alia et al., “Statistical Rate Monotonic Scheduling,” Proceedings of the 19th IEEE Real-Time Systems Symposium—RTSS '98—Madrid, Dec. 2-4, 1998, IEEE Real-Time Systems Symposium, Los Alamitos, CA: IEEE Computer Soc., US, Dec. 2, 1998, pp. 123-132. cited by other
Andre, J.-M et al., “Ox: ADA Cyclic Executive for Embedded Applications,” International Symposium on On-Board Real-Time Software Isobrts, XX, XX, Jan. 1996, pp. 241-245. cited by other

edspgr.07207042