Real-time programming method

Abstract

The invention is a real-time programming method (RTPM) for use in writing application programs to be executed by virtual machines and a method practiced by a real-time virtual machine (RTVM) while executing an application program written in accordance with a real-time programming method. The invention also includes a method for translating an RTPM programming language into a second programming language, the RTPM programming language being an extended version of the second programming language. The RTPM programming language includes real-time code expressions for specifying real-time execution requirements. The method of translating the real-time code expressions is such that the execution of a second-language translation of a RTPM-language application program complies with the real-time execution requirements on a best-effort basis. The RTPM utilizes a configure method and a negotiate method. The invocation of the configure method in an application program results in the quantification of the needs for one or more resources during execution of the application program by a virtual machine. The invocation of the negotiate method in an application program causes a negotiation to occur between the application program and the virtual machine concerning the allocation of one or more resources to the application program, the resources including CPU time, total memory, and memory allocation rate.

Claims

What is claimed is:

1. A real-time programming method (RTPM) for use in writing application programs to be executed by virtual machines, the RTPM comprising:

utilizing a method selected from the group consisting of a configure method and a negotiate method, the invocation of the configure method in an application program resulting in the quantification of the needs for one or more resources during execution of the application program by a virtual machine, the invocation of the negotiate method in an application program causing a negotiation to occur between the application program and the virtual machine concerning the allocation of one or more resources to the application program, the one or more resources being selected from the group consisting of CPU time, total memory, and memory allocation rate.

2. The RTPM of claim 1 wherein the configure method is selected.

3. The RTPM of claim 2 wherein the quantification pertains to the allocation of CPU time.

4. The RTPM of claim 2 wherein the quantification pertains to the allocation of total memory.

5. The RTPM of claim 2 wherein the quantification pertains to the allocation of memory allocation rate.

6. The RTPM of claim 1 wherein the negotiate method is selected.

7. The RTPM of claim 6 wherein the negotiation pertains to the allocation of CPU time.

8. The RTPM of claim 6 wherein the negotiation pertains to the allocation of total memory.

9. The RTPM of claim 6 wherein the negotiation pertains to the allocation of memory allocation rate.

10. The RTPM of claim 1 further comprising:

utilizing a timed-statement control structure, the control structure consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment, it being anticipated that the specified code segment will execute within the specified increment of time, execution otherwise being aborted.

11. The RTPM of claim 1 further comprising:

utilizing a preemptible-timed-statement control structure, the control structure consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment, it being anticipated that the specified code segment will execute during a plurality of time slices within an execution period, the plurality of time slices adding up to the specified increment of time, execution otherwise being aborted.

12. The RTPM of claim 1 further comprising:

utilizing an aperiodic-timed-statement control structure, the control structure consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment, it being anticipated that the specified code segment will execute in time segments spread over a plurality of execution periods, the time segments in the plurality of execution periods adding up to the specified increment of time, execution otherwise being aborted.

13. The RTPM of claim 1 further comprising:

utilizing an atomic-statement control structure, the control structure consisting of (1) a keyword identifying the structure and (2) a specified code segment, the specified code segment being execution-time analyzable, the control structure requiring that either enough time be assigned to execute the specified code segment or that none be assigned.

14. The RTPM of claim 1 wherein real-time tasks include periodic, sporadic, ongoing, and spontaneous real-time tasks, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the startup( ) and finish( ) methods being execution-time analyzable, the startup( ), work( ), and finish( ) methods being invoked in sequence each time a periodic, sporadic, or spontaneous task is executed, the startup( ) method being invoked exactly once for an ongoing task following which the work( ) method is invoked and suspended repeatedly, the finish( ) method for the ongoing task being invoked only when the corresponding real-time activity terminates.

15. The RTPM of claim 1 further comprising:

utilizing a real-time executive object to provide services in response to requests by the application code, the services being intended to provide information relating to the real-time activities.

16. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

long analyze WCET(String methodName) which returns the worst-case time required to execute the specified method.

17. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

long analyzeEET(String methodName) which returns the expected time required to execute the specified method.

18. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

int codeSize(Object o) which returns the worst-case number of bytes required to represent the object o's instruction and static memory data.

19. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

int dataSize(Object o) which returns the worst-case number of bytes required to represent the data belonging to object o.

20. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

void interpret(String methodName) which provides a suggestion to an underlying run-time system that this method should not be translated to native code but should instead be interpreted each time it is executed.

21. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

int persistentCodeSize(Persistent o) which returns the worst-case number of bytes of non-volatile memory required to represent the object o's instruction and static memory data.

22. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

int persistentDataSize(Persistent o) which returns the worst-case number of bytes of non-volatile memory required to represent the data belonging to object o.

23. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

Object [ ] references(Object o) which returns an array of objects representing all of the memory directly referenced by object o.

24. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

void translate(String methodName) which provides a suggestion to an underlying run-time system that this method should be translated to native code rather than be interpreted each time it is executed.

25. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning time, the requests for service comprising:

long cpuTime( ) which reports the amount of CPU time in increments smaller than one microsecond that has been executed by the current thread.

26. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning time, the requests for service comprising:

void sleep(long increment) and void sleep(int increment) which put the currently executing thread to sleep for a time period specified in increments smaller than one microsecond.

27. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning time, the requests for service comprising:

int timeAccuracy( ) which returns the resolution of the local time measuring device in increments smaller than one microsecond.

28. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning time, the requests for service comprising:

long upTime( ) which returns the time period in increments smaller than one microsecond since system startup.

29. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

boolean addActivity(Activity a) which requests that a new real-time activity be added to an existing workload of activities, the request automatically invoking the configure( ) method for the new activity, the configure( ) method returning a representation of the activity's resource needs and wants, the request then invoking the negotiate( ) method for this and other currently executing activities in order to arrange a mutually agreeable allocation of resources.

30. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

boolean addBiasedActivity(Activity a, float importance, float timeSpaceRatio) which requests that a new real-time activity be added to an existing workload of activities, the new activity being accorded preferential treatment, the request automatically invoking the configure( ) method for the new activity, the configure( ) method returning a representation of the activity's resource needs and wants, the request then invoking the negotiate( ) method for this and other currently executing activities in order to arrange a mutually agreeable allocation of resources.

31. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

void removeActivity(Activity a) which removes an existing real-time activity from the current workload.

32. The RTPM of claim 31 wherein all requests to kill existing real-time tasks are directed to the real-time executive by invoking the removeActivity( ) method.

33. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services to an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

void renegotiate(Activity a, ActivityResource p) which modifies the resource request of real-time activity as specified by p.

34. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

boolean scheduleSpontaneous(Activity a, ActivityResource r, long maxReleaseTime) and boolean scheduleSpontaneous(Activity a, ActivityResource r, int maxReleaseTime) which schedules spontaneous tasks for one-time execution with release sometime between the present and maxReleaseTime with individual task deadlines as described by argument r, a representing a collection of spontaneous tasks and r representing their collective resource requirements.

35. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for atomic segments, an atomic segment being executed either in its entirety or not at all, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the currently executing thread being a supervisor for a real-time task, the requests for service comprising:

void enterAtomic(Object o, AtomicSegmentId asi, int executionTime) and void enterAtomic(Object o, AtomicSegmentId asi, long executionTime) which, if the virtual machine is a multiprocessor system, places the specified task on a wait queue associated with object o's lock if some other task is currently locking access to object o, the specified task remaining on the wait queue until access is granted or until the specified task's current time slice expires, the specified task being suspended if the time slice expires first and enterAtomic( ) restarted if and when the specified task is resumed, the term "suspended" meaning that (1) the specified task is put to sleep until its next scheduled execution time slot if the specified task is an ongoing task, (2) the specified task is put to sleep until its next scheduled time slice if the specified task is a periodic, sporadic or spontaneous task, and it is scheduled to receive additional time slices within its current period, and (3) the execution of the work( ) method for the specified task is aborted and the real-time executive invokes the specified task's finish( ) method if the specified task is a periodic, sporadic, or spontaneous task and it is not scheduled to receive additional time slices within its current period.

36. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for atomic segments, an atomic segment being executed either in its entirety or not at all, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the currently executing thread being a supervisor for a real-time task, the requests for service comprising:

void enterAtomic(Object o, AtomicSegmentId asi, int executionTime) and void enterAtomic(Object o, AtomicSegmentId asi, long executionTime) which suspends the specified task if there is insufficient time in the current time slice to execute the complete atomic statement, the term "suspended" meaning that (1) the specified task is put to sleep until its next scheduled execution time slot if the specified task is an ongoing task, (2) the specified task is put to sleep until its next scheduled time slice if the specified task is a periodic, sporadic or spontaneous task, and it is scheduled to receive additional time slices within its current period, and (3) the execution of the work( ) method for the specified task is aborted and the real-time executive invokes the specified task's finish( ) method if the specified task is a periodic, sporadic, or spontaneous task and it is not scheduled to receive additional time slices within its current period.

37. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for atomic segments, an atomic segment being executed either in its entirety or not at all, the requests for service comprising:

void enterAtomic(Object o, AtomicSegmentId asi, int executionTime) and void enterAtomic(Object o, AtomicSegmentId asi, long executionTime) which sets the value of asi to represent the specified atomic segment and sets appropriate flags within the real-time executive to prohibit other tasks from executing atomic statements that belong to object o if the virtual machine is a multiprocessor system.

38. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for atomic segments, an atomic segment being executed either in its entirety or not at all, the currently executing thread being a supervisor for a real-time task, the requests for service comprising:

void exitAtomic(AtomicSegmentId asi) indicating that the currently executing thread is now leaving the atomic region identified by asi, the request releasing the mutual exclusion constraint on the specified object o that is identified by asi thereby permitting other tasks access to o's atomic segments.

39. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the requests for service comprising:

boolean alarmSet(Alarmid a) which returns true if and only if the alarm represented by argument a has been initialized, the request otherwise returning false;

void clearAlarm(Alarmid a) which removes the specified alarm a from the timeout queue if the corresponding alarm is set.

40. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the currently executing thread being a supervisor for a periodic real-time task, the requests for service comprising:

private void relinquish() which suspends the supervisor until the next time that it is appropriate to trigger its execution.

41. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the requests for service comprising:

void skewClock(long tinc) which adjusts pending alarm times by tinc time increments.

42. The RTPM of claim 41 wherein all exception handlers and finally clauses in VMPM source code that are executed by real-time threads are execution-time analyzable, the RTPM virtual machine constructing a call graph for each real-time thread, the RTPM further comprising:

a byte code analysis method which utilizes the call graph for a real-time thread to identify all of the methods that might be invoked by the real-time thread, the byte code analysis method further comprising:

identifying all of the exception handlers and finally clauses within each of the identified methods;

determining the worst-case execution time for each exception handler and for each finally clause;

inserting an invocation of the real-time executive's skewClock( ) method at each entry into the body of a try statement for the purpose of instructing the real-time executive to abort the execution time at time X-T rather than X where T is the maximum time required to execute one of the try statement's exception handlers added to the time required to execute the try statement's finally clause;

inserting an invocation of the real-time executive's skewClock( ) method at the end of the try statement's body to restore the timeout clock to its original value.

43. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the requests for service comprising:

void startTimed(int timeLimit, Alarmidentity alarmid) and void startTimed(long timeLimit, Alarmidentity alarmid) which causes the real-time executive to suspend the thread if there is insufficient time in the current time slice to execute the complete timed statement, the term "suspended" meaning that (1) the specified task is put to sleep until its next scheduled execution time slot if the specified task is an ongoing task, (2) the specified task is put to sleep until its next scheduled time slice if the specified task is a periodic, sporadic, or spontaneous task, and it is scheduled to receive additional time slices within its current period, and (3) the execution of the work( ) method for the specified task is aborted and the real-time executive invokes the specified task's finish( ) method if the specified task is a periodic, sporadic, or spontaneous task and it is not scheduled to receive additional time slices within its current period.

44. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the requests for service comprising:

void startTimed(int timeLimit, Alarmidentity alarmid) and void startTimed(long timeLimit, Alarmidentity alarmid) which causes the real-time executive to set an alarm which is scheduled to expire in (timeLimit--B CPU-time-increments), B representing the worst-case time required by the task's exception handlers to respond to the timeout exception added to the maximum time spent within the implementation of startTimed( ) between the time at which a first condition is satisfied and the time at which the alarm is set, the first condition being that there is sufficient time in the current time slice to execute the complete timed statement, the alarmID object being updated to reflect the identity of the set alarm at the same time the alarm is set, the real-time executive sending a ThreadDeath exception to this task at the specified alarm time.

45. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the requests for service comprising:

void startTimedPreemptible(int timeLimit, Alarmidentity alarmid) and void startTimedPreemptible(long timeLimit, Alarmidentity alarmid) which cause the real-time executive to suspend the thread if there is insufficient time in the current time period to execute the complete timed statement, the specified task being put to sleep until its next scheduled execution time slot if the specified task is an ongoing task, the real-time executive aborting execution of the work( ) method and invoking the specified task's finish( ) method if the specified task is a periodic, sporadic, or spontaneous task.

46. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the requests for service comprising:

void startTimedPreemptible(int timeLimit, Alarmidentity alarmid) and void startTimedPreemptible(long timeLimit, Alarmidentity alarmid) which cause the real-time executive to set an alarm which is scheduled to expire in (timeLimit--B CPU-time-increments), B representing the worst-case time required by the task's exception handlers to respond to the timeout exception added to the maximum time spent within the implementation of startTimedPreemptible( ) between the time at which a first condition is satisfied and the time at which the alarm is set, the first condition being that there is sufficient time in the current time period to execute the complete timed statement, the alarmID object being updated to reflect the identity of the set alarm at the same time the alarm is set, the real-time executive sending a ThreadDeath exception to this task at the specified alarm time.

47. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the requests for service comprising:

void startTimedAperiodic(int timeLimit, Alarmidentity alarmid) and void startTimedAperiodic(long timeLimit, Alarmidentity alarmid) which prepares for execution of a timed aperiodic statement of duration specified by timeLimit, the real-time executive setting an alarm which is scheduled to expire in (timeLimit--B CPU-time-increments), B representing the worst-case time required by the task's exception handlers to respond to the timeout exception added to the maximum time spent within the implementation of startTimed( ) between the time at which a first condition is satisfied and the time at which the alarm is set, the first condition being that the currently executing task is an ongoing task, the real-time executive aborting the execution of the work( ) method and invoking the task's finish( ) method if the currently executing task is not an ongoing task, the alarmID object being updated to reflect the identity of the alarm at the same time the alarm is set, the real-time executive sending a ThreadDeath exception to this task when the alarm time arrives.

48. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

int allocatableBytes( ) which returns the number of bytes of volatile memory that the currently executing activity has permission to allocate, the request returning a special code if the real-time executive is not able to track the memory usage of activities, each activity's budget being increased as memory is reclaimed by the garbage collector and being decreased as the tasks that comprise the activity allocate memory.

49. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

int allocatablePersistentBytes( ) which returns the number of bytes of non-volatile memory that the currently executing activity has permission to allocate, the request returning a special code if the real-time executive is not able to track the persistent memory usage of activities, each activity's budget being increased as persistent memory is reclaimed by the garbage collector and being decreased as the tasks that comprise the activity allocate persistent memory.

50. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

void doGC(int memSize, int persistentSize) causes the real-time executive to perform garbage collection during what was to have been the task's CPU-time slice until there is enough allocatable memory for the given activity to allow a single object of memSize bytes and a single persistent object of persistentSize bytes to be allocated, the task being suspended until its next scheduled execution if the time slice expires before the requested memory has been obtained.

51. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

void enableMemAllocExceptions( ) informs the real-time executive that a task prefers to receive an OutOfMemoryError exception whenever one of its memory allocation requests cannot immediately be satisfied.

52. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

int largestAllocatable( ) returns the size of the largest contiguous block of memory that the virtual machine promises to be able to allocate at the current time.

53. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

int largestPersistentAllocatable( ) returns the size of the largest contiguous block of persistent memory that the virtual machine promises to be able to allocate at the current time.

54. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

void suppressMemAllocExceptions( ) informs the real-time executive that a task desires to automatically relinquish its scheduled execution time to the garbage collector whenever one of its allocation requests cannot be satisfied, the garbage collector being allowed to execute until such time as the task's time slot expires or until the garbage collector reclaims the memory required to satisfy the allocation request.

55. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for run-time scheduling, the real-time executive dispatching real-time tasks according to agreed-upon real-time schedules, a real-time scheduler waiting for a relinquish( ) invocation to terminate a task's time slot for periodic, sporadic, and spontaneous tasks, the real-time executive automatically suspending a task at the end of its allotted time slot after first waiting for ongoing execution of any atomic segments to be completed for ongoing tasks, an atomic segment being executed either in its entirety or not at all, the requests for service comprising:

void triggerTask(TaskDescriptor taskid) throws FrequencyExcess, TaskNotReady causes the real-time executive to initiate execution of a sporadic task, taskid representing the task to be executed, the real-time executive releasing the task for execution at whatever priority was determined appropriate at resource negotiation time after first verifying that the specified task has not yet exceeded its previously negotiated execution frequency, the real-time executive throwing a FrequencyExcess exception if the task has already used up its execution frequency budget, FrequencyExcess being an exception that is thrown by the real-time executive's triggerTask( ) method whenever an attempt is made to invoke a sporadic task more frequently than was arranged at resource negotiation time, the triggerTask( ) method causes a specified task to be released for execution, the triggerTask( ) throwing a TaskNotReady exception if taskid equals null or represents a task that is not sporadic or belongs to an activity that is no longer running.

56. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including the granting of requests for preferential treatment in allocating resources.

57. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including the allocation of resources to activities in accordance with their importance.

58. The RTPM of claim 15 wherein static objects are declared and initialized in the real-time executive object, the static objects including a defined constant used to represent ongoing tasks wherever the nature of a task must be distinguished by a single integer value, an object that can be thrown by a real-time activity needing to throw a timeout exception in order to avoid allocating a time-out object on the fly, and a defined constant used to represent periodic tasks wherever the nature of a task must be distinguished by a single integer value, a defined constant used to represent a spontaneous task wherever the nature of the task must be distinguished by a single integer value, and a defined constant used to represent a sporadic task wherever the nature of the task must be distinguished by a single integer value.

59. The RTPM of claim 15 wherein the real-time executive maintains an internal representation of the most recently negotiated CPU workload and dispatches tasks at appropriate times in accordance with the most recently negotiated CPU workload.

60. The RTPM of claim 59 wherein the real-time executive dispatches a task at the appropriate time and then trusts the task to invoke the real-time executive's relinquish method at the end of its allotted time slot when the task is a periodic, sporadic, or spontaneous task.

61. The RTPM of claim 59 wherein the real-time executive dispatches a task at the beginning of its time slot and suspends the task at the end of its allotted time slot when the task is ongoing.

62. The RTPM of claim 15 wherein a real-time activity loaded into a virtual machine configures itself by measuring its performance and then negotiating with the real-time executive to determine the levels of service quality that can be achieved, the currently executing application code instantiating the real-time activity into the virtual machine by invoking the real-time executive's addActivity( ) method, the real-time executive responding by invoking the real-time activity's configure( ) method, the real-time executive maintaining at least one ongoing real-time task for purposes of invoking the configure( ) methods of new activities.

63. The RTPM of claim 1S wherein the real-time executive includes an interpret() method and a translate( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's interpret( ) method to interpret methods that appear in abstract form, the configure( ) method invoking the real-time executive's translate( ) method to translate methods into native instructions, the default condition being to allow the run-time system to decide for itself whether to interpret or translate particular methods.

64. The RTPM of claim 15 wherein the real-time executive includes an analyze( ) method and each real-time activity includes a configure( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's analyzeWCET( ) method to determine the expected execution time of a method, analyzeWCET( ) returning a first special code if the code is not analyzable or a second special code if the local execution environment lacks the ability to analyze code, the results of the analysis being stored as part of the analyzed method's internal representation.

65. The RTPM of claim 15 wherein the real-time executive includes an analyze( ) method and each real-time activity includes a configure( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's analyzeEET( ) method to determine the worstcase execution time of a method, analyzeEET( ) returning a first special code if the code is not analyzable or a second special code if the local execution environment lacks the ability to analyze code, the results of the analysis being stored as part of the analyzed method's internal representation.

66. The RTPM of claim 15 wherein the real-time executive includes a cpuTime( ) method and each real-time activity includes a configure( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's cpuTime( ) method to measure typical execution times.

67. The RTPM of claim 66 wherein the real-time executive includes a sleep( ) request for putting a currently executing thread to sleep for a specified time period, the configure( ) method inserting a real-time executive's sleep( ) request between each of a plurality of consecutive invocations of the method being measured in order to approximate execution-time cache contention.

68. The RTPM of claim 15 wherein the real-time executive includes a dataSize( ) method and a persistentDataSize( ) method and each real-time activity includes a configure( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's dataSize( ) method and persistentDataSize( ) method to determine the amount of memory required to represent a particular object's data structures, the methods returning a special code if the local environment is unable to determine the memory used to represent the object's data structures.

69. The RTPM of claim 15 wherein the real-time executive includes a codeSize( ) method and persistentCodeSize( ) method and each real-time activity includes a configure( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's codeSize( ) method and persistentCodeSize( ) method to determine the amount of memory required to represent a particular object's instructions, the methods returning a special code if the local environment is unable to determine the memory used to represent the object's instructions.

70. The RTPM of claim 15 wherein each real-time activity includes a configure( ) method, a negotiates method, and a commit() method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the real-time activity responding with a representation of the activity's resource needs and wants, the real-time executive invoking the negotiate( ) method and proposing a budget, the real-time activity responding with "agree" or a proposed budget revision followed by "disagree", the real-time executive having the option of invoking the commit() method in the real-time activity if the response was "agree".

71. The RTPM of claim 70 wherein the proposing-a-budget step allows the real-time executive to propose alternative budgets if particular activities respond with "disagree".

72. The RTPM of claim 15 wherein the real-time executive constructs an activity supervisor object to represent a newly negotiated resource budget for a particular real-time activity, the activity supervisor object maintaining an array of task supervisor objects with one entry for each of the real-time tasks that comprise the real-time activity.

73. The RTPM of claim 72 wherein the real-time executive creates a task supervisor thread to oversee execution of each real-time task, a task supervisor thread being an instance of a task supervisor class.

74. The RTPM of claim 73 wherein the real-time executive creates a periodic task supervisor thread to oversee execution of a periodic, spontaneous, or sporadic task, a periodic task supervisor thread being an instance of a periodic task supervisor class, the periodic task supervisor class being a subclass of the task supervisor class.

75. The RTPM of claim 73 wherein the real-time executive creates a thread supervisor object to oversee execution of an ongoing task, a thread supervisor object being an instance of a thread supervisor class, the thread supervisor class being a subclass of the task supervisor class.

76. The RTPM of claim 15 wherein each real-time activity includes a configure( ) method and a negotiate( ) method, invoking the configure( ) method causing the real-time activity to allocate and initialize an activity resource object to represent the activity's CPU-time and memory needs, the real-time executive subsequently examining the resource requests of all real-time activities in the system and computing budgets for each real-time activity, the real-time executive creating a new activity resource object to represent the budget it is willing to grant to each real-time activity and passing this object as a parameter to the real-time activity's negotiate( ) method, the real-time activity then having an opportunity to accept or reject the proposed budget.

77. The RTPM of claim 15 wherein the real-time executive includes an addActivity( ) method and a scheduleSpontaneous( ) method and each real-time activity includes a configure( ) method, spontaneous activities being in the real-time activities class, spontaneous activities comprising only spontaneous tasks, an application code creating an instance of a spontaneous activity in preparation for subsequent execution, the application code introducing the spontaneous activity to the real-time executive by invoking the addActivity( ) method, the addActivity( ) method refraining from scheduling the workload associated with the spontaneous activity, the real-time executive invoking the spontaneous activity's configure( ) method to enable the activity to analyze its memory and CPU-time requirements, the application code subsequently invoking the real-time executive's scheduleSpontaneous( ) method to request execution of the workload associated with the spontaneous activity.

78. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services to an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

ActivityInventory getBiases( ) which returns an ActivityInventory object that represents all of the activities in the current workload along with the importance and timeSpaceRatio of each, importance being a measure of the importance of an activity, timeSpaceRatio expressing the desired ratio of the fractional scaleback in CPU time to the fractional scaleback in memory space.

79. The RTPM of claim 78 wherein the PersistencyManager implements:

a bootstrap( ) method invoked soon after a virtual machine is restarted in order to reactivate all of the objects which have been stored in persistent memory, the bootstrap( ) method being automatically invoked when the PersistencyManager class is first loaded;

a createShadow(Persistent o) method invoked by the application code to request the PersistencyManager to create a non-volatile shadow copy of the object o;

a deleteShadow(Persistent o) method invoked by the application code to delete shadow object o;

an updateShadow(Persistent o) throws ReferenceNotPersistent method invoked by the application code to request that the modified object o be written to persistent memory, the method guaranteeing that if the virtual machine crashes during the execution of the method, the complete persistent copy of object o will either have its original values or its new values, the PersistencyManager ensuring that if multiple updateShadow( ) invocations appear within a single atomic segment, either all or none of the updateShadow( ) commands are considered to have completed if the system crashes during execution of the atomic segment, an atomic segment being executed either in its entirety or not at all.

80. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services to an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

void biasWorkload(ActivityInventory newBias) which causes the importance and timeSpaceRatio entries for each of the activities that is in both the current workload and in newBias, importance being a measure of the importance of an activity, timeSpaceRatio expressing the desired ratio of the fractional scaleback in CPU time to the fractional scaleback in memory space.

81. The RTPM of claim 80 wherein when power is restored to a virtual machine that contains persistent objects, the bootstrap( ) method comprises:

(a) making consistent those persistent objects that were in an inconsistent state at the time the virtual machine shut down;

(b) creating a heap-memory copy which will be shadowed by the persistent copy for each persistent object in persistent memory;

(c) introducing any of the objects created in (b) which are of type RealTime.Activity to the real-time executive by invoking the addActivity( ) method thereby causing the configuration of the real-time activity followed by negotiation for object resources;

(d) invoking the object's run( ) method for any of the heap objects created in (b) which are Runnable but were not involved in real-time activities.

82. The RTPM of claim 15 further comprising:

utilizing a real-time executive object to provide services to an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

long systemCycleTime( ) which returns the number of time increments required to execute one period of the system's cyclic schedule, systemCycleTime( ) returning a special code if the system is not currently using a cyclic dispatch table.

83. The RTPM of claim 1 further comprising:

utilizing a virtual machine code analysis method at the time of execution of a program to determine the worst-case execution time of a program fragment, a program fragment being represented as a control-flow graph, a program fragment being marked as to whether (1) it has not yet been analyzed, (2) it is currently being analyzed, (3) it has been shown to be unanalyzable, or (4) it has already been analyzed, the byte code analysis method comprising:

aborting the analysis if (2), (3), or (4) is true;

aborting the analysis and marking the fragment's status as (3) if any of the methods invoked within the loop are not final;

identifying all of the loops in the program fragment;

identifying a loop header and footer for each loop, the analysis being aborted and the fragment's status being marked as (3) if a header and footer cannot be found for each loop;

starting with the innermost nested loops and working outward:

identifying all basic induction variables;

identifying the set of constant-initiated induction variables contained in the set of basic induction variables, the analysis being aborted and the fragment's status being marked as (3) if the constant-initiated induction variables set is empty;

identifying the set of iteration-bound induction variables contained in the set of constant-initiated induction variables, the analysis being aborted and the fragment's status being marked as (3) if the iteration-bound induction variables set is empty;

identifying all of the decision points by which control may leave the loop;

identifying the set of obligatory decision points contained in the set of decision points, the analysis being aborted and the fragment's status being marked as (3) if the obligatory decision points set is empty;

identifying the set of obligatory decision points that are based on magnitude comparison of an iteration-bound induction variable with a constant, the analysis being aborted and the fragment's status being marked as (3) if the magnitude-comparison-based obligatory decision points set is empty;

determining the worst-case execution time from the bound for the maximum number of loop iterations given by the obligatory decision point that represents the tightest bound;

calculating the worst-case execution time of the non-iterative loop components as the maximum worst-case execution time for any path from the component's entry point to its exit point, carefully considering pipeline and cache effects.

84. The RTPM of claim 1 wherein the stop( ) method is used to send a ThreadDeath exception to an executing thread when the alarm time is reached, it being arranged to catch this exception and respond appropriately rather than allowing the exception to abort the thread.

85. The RTPM of claim 1 further comprising:

utilizing an activity resource object to represent the memory and CPU time needs of a real-time activity, the activity resource object being an instance of an activity resource class.

86. The RTPM of claim 85 wherein an activity resource object maintains an array of task resource objects, memory being requested and budgeted for the real-time activity, CPU time being budgeted for the individual real-time tasks that comprise a real-time activity.

87. A method practiced by a real-time virtual machine (RTVM) while executing an application program written in accordance with a real-time programming method (RTPM), the RTVM method comprising:

executing a method selected from the group consisting of a configure method and a negotiate method, the execution of the configure method resulting in the quantification of the needs for one or more resources by the application program, the execution of the negotiate method causing a negotiation to occur between the application program and the virtual machine concerning the allocation of one or more resources to the application program, the one or more resources being selected from the group consisting of CPU time, total memory, and memory allocation rate.

88. The RTVM method of claim 87 wherein the configure method is selected.

89. The RTVM method of claim 88 wherein the quantification pertains to the allocation of CPU time.

90. The RTVM method of claim 88 wherein the quantification pertains to the allocation of total memory.

91. The RTVM method of claim 88 wherein the quantification pertains to the allocation of memory allocation rate.

92. The RTVM method of claim 87 wherein the negotiate method is selected.

93. The RTVM of claim 92 wherein the negotiation pertains to the allocation of CPU time.

94. The RTVM method of claim 92 wherein the negotiation pertains to the allocation of total memory.

95. The RTVM method of claim 92 wherein the negotiation pertains to the allocation of memory allocation rate.

96. The RTPM of claim 87 further comprising:

executing a timed-statement with a control structure consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment, it being anticipated that the specified code segment will execute within the specified increment of time, execution otherwise being aborted.

97. The RTVM method of claim 87 further comprising:

executing a preemptible-timed-statement with a control structure consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment, it being anticipated that the specified code segment will execute during a plurality of time slices within an execution period, the plurality of time slices adding up to the specified increment of time, execution otherwise being aborted.

98. The RTVM method of claim 87 further comprising:

executing an aperiodic-timed-statement with a control structure consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment, it being anticipated that the specified code segment will execute in time segments spread over a plurality of execution periods, the time segments in the plurality of execution periods adding up to the specified increment of time, execution otherwise being aborted.

99. The RTVM method of claim 87 further comprising:

executing an atomic-statement with a control structure consisting of (1) a keyword identifying the structure and (2) a specified code segment, the specified code segment being execution-time analyzable, the control structure requiring that either enough time be assigned to execute the specified code segment or that none be assigned.

100. The RTVM method of claim 87 wherein real-time tasks include periodic, sporadic, ongoing, and spontaneous real-time tasks, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the startup( ) and finish( ) methods being execution-time analyzable, the startup( ), work( ), and finish( ) methods being invoked in sequence each time a periodic, sporadic, or spontaneous task is executed, the startup( ) method being invoked exactly once for an ongoing task following which the work( ) method is invoked and suspended repeatedly, the finish( ) method for the ongoing task being invoked only when the corresponding real-time activity terminates.

101. The RTVM method of claim 87 further comprising:

utilizing a real-time executive object to provide services in response to requests by the application code, the services being intended to provide information relating to the real-time activities.

102. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

long analyzeWCET(String methodName) which returns the worst-case time required to execute the specified method.

103. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

long analyzeEET(String methodName) which returns the expected time required to execute the specified method.

104. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

int codeSize(Object o) which returns the worst-case number of bytes required to represent the object o's instruction and static memory data.

105. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

int dataSize(Object o) which returns the worst-case number of bytes required to represent the data belonging to object o.

106. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

void interpret(String methodName) which provides a suggestion to an underlying run-time system that this method should not be translated to native code but should instead be interpreted each time it is executed.

107. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

int persistentCodeSize(Persistent o) which returns the worst-case number of bytes of non-volatile memory required to represent the object o's instruction and static memory data.

108. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

int persistentDataSize(Persistent o) which returns the worst-case number of bytes of non-volatile memory required to represent the data belonging to object o.

109. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

Object [ ] references(Object o) which returns an array of objects representing all of the memory directly referenced by object o.

110. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning the configuration of real-time activities for the purpose of facilitating analysis of execution times and memory requirements, the requests for service comprising:

void translate(String methodName) which provides a suggestion to an underlying run-time system that this method should be translated to native code rather than be interpreted each time it is executed.

111. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning time, the requests for service comprising:

long cpuTime( ) which reports the amount of CPU time in increments smaller than one microsecond that has been executed by the current thread.

112. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning time, the requests for service comprising:

void sleep(long increment) and void sleep(int increment) which put the currently executing thread to sleep for a time period specified in increments smaller than one microsecond.

113. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning time, the requests for service comprising:

int timeAccuracy( ) which returns the resolution of the local time measuring device in increments smaller than one microsecond.

114. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including providing data concerning time, the requests for service comprising:

long upTime( ) which returns the time period in increments smaller than one microsecond since system startup.

115. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

boolean addActivity(Activity a) which requests that a new real-time activity be added to an existing workload of activities, the request automatically invoking the configure( ) method for the new activity, the configure( ) method returning a representation of the activity's resource needs and wants, the request then invoking the negotiate( ) method for this and other currently executing activities in order to arrange a mutually agreeable allocation of resources.

116. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

boolean addBiasedActivity(Activity a, float importance, float timeSpaceRatio) which requests that a new real-time activity be added to an existing workload of activities, the new activity being accorded preferential treatment, the request automatically invoking the configure( ) method for the new activity, the configure( ) method returning a representation of the activity's resource needs and wants, the request then invoking the negotiate( ) method for this and other currently executing activities in order to arrange a mutually agreeable allocation of resources.

117. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

void removeActivity(Activity a) which removes an existing real-time activity from the current workload.

118. The RTVM method of claim 117 wherein all requests to kill existing real-time tasks are directed to the real-time executive by invoking the removeActivity( ) method.

119. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services to an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

void renegotiate(Activity a, ActivityResource p) which modifies the resource request of real-time activity as specified by p.

120. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

boolean scheduleSpontaneous(Activity a, ActivityResource r, long maxReleaseTime) and boolean scheduleSpontaneous(Activity a, ActivityResource r, int maxReleaseTime) which schedules spontaneous tasks for one-time execution with release sometime between the present and maxReleaseTime with individual task deadlines as described by argument r, a representing a collection of spontaneous tasks and r representing their collective resource requirements.

121. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for atomic segments, an atomic segment being executed either in its entirety or not at all, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the currently executing thread being a supervisor for a real-time task, the requests for service comprising:

void enterAtomic(Object o, AtomicSegmentId asi, int executionTime) and void enterAtomic(Object o, AtomicSegmentId asi, long executionTime) which, if the virtual machine is a multiprocessor system, places the specified task on a wait queue associated with object o's lock if some other task is currently locking access to object o, the specified task remaining on the wait queue until access is granted or until the specified task's current time slice expires, the specified task being suspended if the time slice expires first and enterAtomico restarted if and when the specified task is resumed, the term "suspended" meaning that (1) the specified task is put to sleep until its next scheduled execution time slot if the specified task is an ongoing task, (2) the specified task is put to sleep until its next scheduled time slice if the specified task is a periodic, sporadic or spontaneous task, and it is scheduled to receive additional time slices within its current period, and (3) the execution of the work( ) method for the specified task is aborted and the real-time executive invokes the specified task's finish( ) method if the specified task is a periodic, sporadic, or spontaneous task and it is not scheduled to receive additional time slices within its current period.

122. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for atomic segments, an atomic segment being executed either in its entirety or not at all, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the currently executing thread being a supervisor for a real-time task, the requests for service comprising:

void enterAtomic(Object o, AtomicSegmentId asi, int executionTime) and void enterAtomic(Object o, AtomicSegmentId asi, long executionTime) which suspends the specified task if there is insufficient time in the current time slice to execute the complete atomic statement, the term "suspended" meaning that (1) the specified task is put to sleep until its next scheduled execution time slot if the specified task is an ongoing task, (2) the specified task is put to sleep until its next scheduled time slice if the specified task is a periodic, sporadic or spontaneous task, and it is scheduled to receive additional time slices within its current period, and (3) the execution of the work( ) method for the specified task is aborted and the real-time executive invokes the specified task's finish( ) method if the specified task is a periodic, sporadic, or spontaneous task and it is not scheduled to receive additional time slices within its current period.

123. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for atomic segments, an atomic segment being executed either in its entirety or not at all, the requests for service comprising:

void enterAtomic(Object o, AtomicSegmentId asi, int executionTime) and void enterAtomic(Object o, AtomicSegmentId asi, long executionTime) which sets the value of asi to represent the specified atomic segment and sets appropriate flags within the real-time executive to prohibit other tasks from executing atomic statements that belong to object o if the virtual machine is a multiprocessor system.

124. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for atomic segments, an atomic segment being executed either in its entirety or not at all, the currently executing thread being a supervisor for a real-time task, the requests for service comprising:

void exitAtomic(AtomicSegmentId asi) indicating that the currently executing thread is now leaving the atomic region identified by asi, the request releasing the mutual exclusion constraint on the specified object o that is identified by asi thereby permitting other tasks access to o's atomic segments.

125. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the requests for service comprising:

boolean alarmSet(Alarmid a) which returns true if and only if the alarm represented by argument a has been initialized, the request otherwise returning false;

void clearAlarm(Alarmid a) which removes the specified alarm a from the timeout queue if the corresponding alarm is set.

126. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the currently executing thread being a supervisor for a periodic real-time task, the requests for service comprising:

private void relinquish( ) which suspends the supervisor until the next time that it is appropriate to trigger its execution.

127. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the requests for service comprising:

void skewClock(long tinc) which adjusts pending alarm times by tinc time increments.

128. The RTVM method of claim 127 wherein all exception handlers and finally clauses in a virtual machine source code that are executed by real-time threads are execution-time analyzable, the RTVM constructing a call graph for each real-time thread, the RTVM method further comprising:

a byte code analysis method which utilizes the call graph for a real-time thread to identify all of the methods that might be invoked by the real-time thread, the byte code analysis method further comprising:

identifying all of the exception handlers and finally clauses within each of the identified methods;

determining the worst-case execution time for each exception handler and for each finally clause;

inserting an invocation of the real-time executive's skewClock( ) method at each entry into the body of a try statement for the purpose of instructing the real-time executive to abort the execution time at time X-T rather than X where T is the maximum time required to execute one of the try statement's exception handlers added to the time required to execute the try statement's finally clause;

inserting an invocation of the real-time executive's skewClock( ) method at the end of the try statement's body to restore the timeout clock to its original value.

129. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the requests for service comprising:

void startTimed(int timeLimit, Alarmidentity alarmid) and void startTimed(long timeLimit, Alarmidentity alarmid) which causes the real-time executive to suspend the thread if there is insufficient time in the current time slice to execute the complete timed statement, the term "suspended" meaning that (1) the specified task is put to sleep until its next scheduled execution time slot if the specified task is an ongoing task, (2) the specified task is put to sleep until its next scheduled time slice if the specified task is a periodic, sporadic, or spontaneous task, and it is scheduled to receive additional time slices within its current period, and (3) the execution of the work( ) method for the specified task is aborted and the real-time executive invokes the specified task's finish( ) method if the specified task is a periodic, sporadic, or spontaneous task and it is not scheduled to receive additional time slices within its current period.

130. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the requests for service comprising:

void startTimed(int timeLimit, Alarmidentity alarmid) and void startTimed(long timeLimit, Alarmidentity alarmid) which causes the real-time executive to set an alarm which is scheduled to expire in (timeLimit--B CPU-time-increments), B representing the worst-case time required by the task's exception handlers to respond to the timeout exception added to the maximum time spent within the implementation of startTimed( ) between the time at which a first condition is satisfied and the time at which the alarm is set, the first condition being that there is sufficient time in the current time slice to execute the complete timed statement, the alarmID object being updated to reflect the identity of the set alarm at the same time the alarm is set, the real-time executive sending a ThreadDeath exception to this task at the specified alarm time.

131. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the requests for service comprising:

void startTimedPreemptible(int timeLimit, Alarmidentity alarmid) and void startTimedPreemptible(long timeLimit, Alarmidentity alarmid) which cause the real-time executive to suspend the thread if there is insufficient time in the current time slice to execute the complete timed statement, the specified task being put to sleep until its next scheduled execution time slot if the specified task is an ongoing task, the real-time executive aborting execution of the work( ) method and invoking the specified task's finish( ) method if the specified task is a periodic, sporadic, or spontaneous task.

132. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the requests for service comprising:

void startTimedPreemptible(int timeLimit, Alarmidentity alarmid) and void startTimedPreemptible(long timeLimit, Alarmidentity alarmid) which cause the real-time executive to set an alarm which is scheduled to expire in (timeLimit--B CPU-time-increments), B representing the worst-case time required by the task's exception handlers to respond to the timeout exception added to the maximum time spent within the implementation of startTimedPreemptible( ) between the time at which a first condition is satisfied and the time at which the alarm is set, the first condition being that there is sufficient time in the current time slice to execute the complete timed statement, the alarmID object being updated to reflect the identity of the set alarm at the same time the alarm is set, the real-time executive sending a ThreadDeath exception to this task at the specified alarm time.

133. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for timed statements, a timed statement being a statement that is bounded in execution time, the method of execution of a real-time task comprising a startup( ) method, a work( ) method, and a finish( ) method, the requests for service comprising:

void startTimedAperiodic(int timeLimit, Alarmidentity alarmid) and void startTimedAperiodic(long timeLimit, Alarmidentity alarmid) which prepares for execution of a timed aperiodic statement of duration specified by timeLimit, the real-time executive setting an alarm which is scheduled to expire in (timeLimit--B CPU-time-increments), B representing the worst-case time required by the task's exception handlers to respond to the timeout exception added to the maximum time spent within the implementation of startTimed( ) between the time at which a first condition is satisfied and the time at which the alarm is set, the first condition being that the currently executing task is an ongoing task, the real-time executive aborting the execution of the work( ) method and invoking the task's finish( ) method if the currently executing task is not an ongoing task, the alarmID object being updated to reflect the identity of the alarm at the same time the alarm is set, the real-time executive sending a ThreadDeath exception to this task when the alarm time arrives.

134. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

int allocatableBytes( ) which returns the number of bytes of volatile memory that the currently executing activity has permission to allocate, the request returning a special code if the real-time executive is not able to track the memory usage of activities, each activity's budget being increased as memory is reclaimed by the garbage collector and being decreased as the tasks that comprise the activity allocate memory.

135. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

int allocatablePersistentBytes( ) which returns the number of bytes of non-volatile memory that the currently executing activity has permission to allocate, the request returning a special code if the real-time executive is not able to track the persistent memory usage of activities, each activity's budget being increased as persistent memory is reclaimed by the garbage collector and being decreased as the tasks that comprise the activity allocate persistent memory.

136. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

void doGC(int memSize, int persistentSize) causes the real-time executive to perform garbage collection during what was to have been the task's CPU-time slice until there is enough allocatable memory for the given activity to allow a single object of memSize bytes or a single persistent object of persistentSize bytes to be allocated, the task being suspended until its next scheduled execution if the time slice expires before the requested memory has been obtained.

137. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

void enableMemAllocExceptions( ) informs the real-time executive that a task prefers to receive an OutOfMemoryError exception whenever one of its memory allocation requests cannot immediately be satisfied.

138. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

int largestAllocatable( ) returns the size of the largest contiguous block of memory that the virtual machine promises to be able to allocate at the current time.

139. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

int largestPersistentAllocatable( ) returns the size of the largest contiguous block of persistent memory that the virtual machine promises to be able to allocate at the current time.

140. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for dynamic memory management, budgets for each activity's allocation of volatile and non-volatile memory being enforced by the real-time executive, the requests for service comprising:

void suppressMemAllocExceptions( ) informs the real-time executive that a task desires to automatically relinquish its scheduled execution time to the garbage collector whenever one of its allocation requests cannot be satisfied, the garbage collector being allowed to execute until such time as the task's time slot expires or until the garbage collector reclaims the memory required to satisfy the allocation request.

141. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including run-time support for run-time scheduling, the real-time executive dispatching real-time tasks according to agreed-upon real-time schedules, a real-time scheduler waiting for a relinquish( ) invocation to terminate a task's time slot for periodic, sporadic, and spontaneous tasks, the real-time executive automatically suspending a task at the end of its allotted time slot after first waiting for ongoing execution of any atomic segments to be completed for ongoing tasks, an atomic segment being executed either in its entirety or not at all, the requests for service comprising:

void triggerTask(TaskDescriptor taskid) throws FrequencyExcess, TaskNotReady causes the real-time executive to initiate execution of a sporadic task, taskid representing the task to be executed, the real-time executive releasing the task for execution at whatever priority was determined appropriate at resource negotiation time after first verifying that the specified task has not yet exceeded its previously negotiated execution frequency, the real-time executive throwing a FrequencyExcess exception if the task has already used up its execution frequency budget, FrequencyExcess being an exception that is thrown by the real-time executive's triggerTask( ) method whenever an attempt is made to invoke a sporadic task more frequently than was arranged at resource negotiation time, the triggerTask( ) method causes a specified task to be released for execution, the triggerTask( ) throwing a TaskNotReady exception if taskid equals null or represents a task that is not sporadic or belongs to an activity that is no longer running.

142. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including the granting of requests for preferential treatment in allocating resources.

143. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services in response to requests by an application code, the services including the allocation of resources to activities in accordance with their importance.

144. The RTVM method of claim 101 wherein static objects are declared and initialized in the real-time executive object, the static objects including a defined constant used to represent ongoing tasks wherever the nature of a task must be distinguished by a single integer value, an object that can be thrown by a real-time activity needing to throw a timeout exception in order to avoid allocating a timeout object on the fly, and a defined constant used to represent periodic tasks wherever the nature of a task must be distinguished by a single integer value, a defined constant used to represent a spontaneous task wherever the nature of the task must be distinguished by a single integer value, and a defined constant used to represent a sporadic task wherever the nature of the task must be distinguished by a single integer value.

145. The RTVM method of claim 101 wherein the real-time executive maintains an internal representation of the most recently negotiated CPU workload and dispatches tasks at appropriate times in accordance with the most recently negotiated CPU workload.

146. The RTVM method of claim 145 wherein the real-time executive dispatches a task at the appropriate time and then trusts the task to invoke the real-time executive's relinquish method at the end of its allotted time slot when the task is a periodic, sporadic, or spontaneous task.

147. The RTVM method of claim 145 wherein the real-time executive dispatches a task at the beginning of its time slot and suspends the task at the end of its allotted time slot when the task is ongoing.

148. The RTVM method of claim 101 wherein a real-time activity loaded into a virtual machine configures itself by measuring its performance and then negotiating with the real-time executive to determine the levels of service quality that can be achieved, the currently executing application code instantiating the real-time activity into the virtual machine by invoking the real-time executive's addActivity( ) method, the real-time executive responding by invoking the real-time activity's configure( ) method, the real-time executive maintaining at least one ongoing real-time task for purposes of invoking the configure( ) methods of new activities.

149. The RTVM method of claim 101 wherein the real-time executive includes an interpret( ) method and a translate( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's interpret( ) method to suggest that certain methods be interpreted in a byte-code language understood by the RTVM, the configure( ) method invoking the real-time executive's translate( ) method to suggest that other methods be translated into the language of the RTVM execution platform, the default condition being to allow the run-time system to decide for itself whether to interpret or translate particular methods.

150. The RTVM method of claim 101 wherein the real-time executive includes an analyzeWCET( ) method and each real-time activity includes a configure method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's analyzeWCET( ) method to determine the worst-case execution time of a method, analyzeWCET( ) returning a first special code if the code is not analyzable or a second special code if the local execution environment lacks the ability to analyze code, the results of the analysis being stored as part of the analyzed method's internal representation.

151. The RTVM method of claim 101 wherein the real-time executive includes an analyzeEET( ) method and each real-time activity includes a configure( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's analyzeEET( ) method to determine the expected execution time of a method, analyzeEET( ) returning a first special code if the code is not analyzable or a second special code if the local execution environment lacks the ability to analyze code, the results of the analysis being stored as part of the analyzed method's internal representation.

152. The RTVM method of claim 101 wherein the real-time executive includes a cpuTime( ) method and each real-time activity includes a configure( ) method, the real-time executive invoking a real-time activity's configure method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's cpuTime( ) method to measure typical execution times.

153. The RTVM method of claim 152 wherein the real-time executive includes a sleep( ) request for putting a currently executing thread to sleep for a specified time period, the configure( ) method inserting a real-time executive's sleep( ) request between each of a plurality of consecutive invocations of the method being measured in order to approximate execution-time cache contention.

154. The RTVM method of claim 101 wherein the real-time executive includes a dataSize( ) method and a persistentDataSize( ) method and each real-time activity includes a configure( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's dataSize( ) method and persistentDataSize( ) method to determine the amount of memory required to represent a particular object's data structures, the methods returning a special code if the local environment is unable to determine the memory used to represent the object's data structures.

155. The RTVM method of claim 101 wherein the real-time executive includes a codeSize( ) method and persistentCodeSize( ) method and each real-time activity includes a configure( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the configure( ) method invoking the real-time executive's codesize( ) method and persistentCodeSize( ) method to determine the amount of memory required to represent a particular object's instructions, the methods returning a special code if the local environment is unable to determine the memory used to represent the object's instructions.

156. The RTVM method of claim 101 wherein each real-time activity includes a configure( ) method, a negotiate( ) method, and a commit( ) method, the real-time executive invoking a real-time activity's configure( ) method when the real-time activity is added to the system workload, the real-time activity responding with a representation of the activity's resource needs and wants, the real-time executive invoking the negotiate( ) method and proposing a budget, the real-time activity responding with "agree" or a proposed budget revision followed by "disagree", the real-time executive having the option of invoking the commit() method in the real-time activity if the response was "agree".

157. The RTVM method of claim 156 wherein the proposing-a-budget step allows the real-time executive to propose alternative budgets if particular activities respond with "disagree".

158. The RTVM method of claim 101 wherein the real-time executive constructs an activity supervisor object to represent a newly negotiated resource budget for a particular real-time activity, the activity supervisor object maintaining an array of task supervisor objects with one entry for each of the real-time tasks that comprise the real-time activity.

159. The RTVM method of claim 158 wherein the real-time executive creates a task supervisor thread to oversee execution of each real-time task, a task supervisor thread being an instance of a task supervisor class.

160. The RTVM method of claim 159 wherein the real-time executive creates a periodic task supervisor thread to oversee execution of a periodic, spontaneous, or sporadic task, a periodic task supervisor thread being an instance of a periodic task supervisor class, the periodic task supervisor class being a subclass of the task supervisor class.

161. The RTVM method of claim 159 wherein the real-time executive creates a thread supervisor object to oversee execution of an ongoing task, a thread supervisor object being an instance of a thread supervisor class, the thread supervisor class being a subclass of the task supervisor class.

162. The RTVM method of claim 101 wherein each real-time activity includes a configure( ) method and a negotiate( ) method, invoking the configure( ) method causing the real-time activity to allocate and initialize an activity resource object to represent the activity's CPU-time and memory needs, the real-time executive subsequently examining the resource requests of all real-time activities in the system and computing budgets for each real-time activity, the real-time executive creating a new activity resource object to represent the budget it is willing to grant to each real-time activity and passing this object as a parameter to the real-time activity's negotiate( ) method, the real-time activity then having an opportunity to accept or reject the proposed budget.

163. The RTVM method of claim 101 wherein the real-time executive includes an addActivity( ) method and a scheduleSpontaneous( ) method and each real-time activity includes a configure( ) method, spontaneous activities being in the real-time activities class, spontaneous activities comprising only spontaneous tasks, an application code creating an instance of a spontaneous activity in preparation for subsequent execution, the application code introducing the spontaneous activity to the real-time executive by invoking the addActivity( ) method, the addActivity( ) method refraining from scheduling the workload associated with the spontaneous activity, the real-time executive invoking the spontaneous activity's configure( ) method to enable the activity to analyze its memory and CPU-time requirements, the application code subsequently invoking the real-time executive's scheduleSpontaneous( ) method to request execution of the workload associated with the spontaneous activity.

164. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services to an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

ActivityInventory getBiases( ) which returns an ActivityInventory object that represents all of the activities in the current workload along with the importance and timeSpaceRatio of each, importance being a measure of the importance of an activity, timeSpaceRatio expressing the desired ratio of the fractional scaleback in CPU time to the fractional scaleback in memory space.

165. The RTVM method of claim 164 wherein the PersistencyManager implements:

a bootstrap( ) method invoked soon after a virtual machine is restarted in order to reactivate all of the objects which have been stored in persistent memory, the bootstrap( ) method being automatically invoked when the PersistencyManager class is first loaded;

a createShadow(Persistent o) method invoked by the application code to request the PersistencyManager to create a non-volatile shadow copy of the object o;

a deleteShadow(Persistent o) method invoked by the application code to delete shadow object o;

an updateShadow(Persistent o) throws ReferenceNotPersistent method invoked by the application code to request that the modified object o be written to persistent memory, the method guaranteeing that if the virtual machine crashes during the execution of the method, the complete persistent copy of object o will either have its original values or its new values, the PersistencyManager ensuring that if multiple updateShadow( ) invocations appear within a single atomic segment, either all or none of the updateShadow( ) commands are considered to have completed if the system crashes during execution of the atomic segment, an atomic segment being executed either in its entirety or not at all.

166. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services to an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

void biasWorkload(ActivityInventory newBias) which causes the importance and timeSpaceRatio entries for each of the activities that is in both the current workload and in newBias, importance being a measure of the importance of an activity, timeSpaceRatio expressing the desired ratio of the fractional scaleback in CPU time to the fractional scaleback in memory space.

167. The RTVM method of claim 166 wherein when power is restored to a virtual machine that contains persistent objects, the bootstrap( ) method comprises:

(a) making consistent those persistent objects that were in an inconsistent state at the time the virtual machine shut down;

(b) creating a heap-memory copy which will be shadowed by the persistent copy for each persistent object in persistent memory;

(c) introducing any of the objects created in (b) which are of type RealTime.Activity to the real-time executive by invoking the addActivity( ) method thereby causing the configuration of the real-time activity followed by negotiation for object resources;

(d) invoking the object's run( ) method for any of the heap objects created in (b) which are Runnable but were not involved in real-time activities.

168. The RTVM method of claim 101 further comprising:

utilizing a real-time executive object to provide services to an application code, the services including negotiating CPU time and memory resources, the requests for service comprising:

long systemCycleTime( ) which returns the number of time increments required to execute one period of the system's cyclic schedule, systemCycleTime( ) returning a special code if the system is not currently using a cyclic dispatch table.

169. The RTVM method of claim 87 further comprising:

utilizing a virtual machine code analysis method at the time of execution of a program to determine the worst-case execution time of a program fragment, a program fragment being represented as a control-flow graph, a program fragment being marked as to whether (1) it has not yet been analyzed, (2) it is currently being analyzed, (3) it has been shown to be unanalyzable, or (4) it has already been analyzed, the byte code analysis method comprising:

aborting the analysis if (2), (3), or (4) is true;

aborting the analysis and marking the fragment's status as (3) if any of the methods invoked within the loop are not final;

identifying all of the loops in the program fragment;

identifying a loop header and footer for each loop, the analysis being aborted and the fragment's status being marked as (3) if a header and footer cannot be found for each loop;

starting with the innermost nested loops and working outward:

identifying all basic induction variables;

identifying the set of constant-initiated induction variables contained in the set of basic induction variables, the analysis being aborted and the fragment's status being marked as (3) if the constant-initiated induction variables set is empty;

identifying the set of iteration-bound induction variables contained in the set of constant-initiated induction variables, the analysis being aborted and the fragment's status being marked as (3) if the iteration-bound induction variables set is empty;

identifying all of the decision points by which control may leave the loop;

identifying the set of obligatory decision points contained in the set of decision points, the analysis being aborted and the fragment's status being marked as (3) if the obligatory decision points set is empty;

identifying the set of obligatory decision points that are based on magnitude comparison of an iteration-bound induction variable with a constant, the analysis being aborted and the fragment's status being marked as (3) if the magnitude-comparison-based obligatory decision points set is empty;

determining the worst-case execution time from the bound for the maximum number of loop iterations given by the obligatory decision point that represents the tightest bound;

calculating the worst-case execution time of the non-iterative loop components as the maximum worst-case execution time for any path from the component's entry point to its exit point, carefully considering pipeline and cache effects.

170. The RTVM method of claim 87 wherein the stop( ) method is used to send a ThreadDeath exception to an executing thread when the alarm time is reached, it being arranged to catch this exception and respond appropriately rather than allowing the exception to abort the thread.

171. The RTVM method of claim 87 wherein run-time support is provided for the creation and maintenance of persistent objects, persistent objects being objects that continue to live even after the virtual machine has crashed and/or been restarted, a Persistent interface being defined which declares several fields for use by a PersistencyManager.

172. The RTVM method of claim 87 further comprising:

utilizing an activity resource object to represent the memory and CPU time needs of a real-time activity, the activity resource object being an instance of an activity resource class.

173. The RTVM method of claim 172 wherein an activity resource object maintains an array of task resource objects, memory being requested and budgeted for the real-time activity, CPU time being budgeted for the individual real-time tasks that comprise a real-time activity.

174. A method for translating a first programming language into a second programming language, the first programming language being an extended version of the second programming language, the first programming language including real-time code expressions for specifying real-time execution requirements, the method comprising:

translating the real-time code expressions whereby the execution of a second-language translation of a first-language application program complies with the real-time execution requirements on a best-effort basis.

175. The method of claim 174 wherein the first programming language does and the second programming language does not use a timed-statement control structure, the control structure consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment, it being anticipated that the specified code segment will execute within the specified increment of time, execution otherwise being aborted, the method further comprising:

translating the timed-statement control structure of the first programming language into a control structure of the second programming language.

176. The method of claim 174 wherein the first programming language does and the second programming language does not use a preemptible-timed-statement control structure, the control structure consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment, it being anticipated that the specified code segment will execute during a plurality of time slices within an execution period, the plurality of time slices adding up to the specified increment of time, execution otherwise being aborted, the method further comprising:

translating the preemptible-timed-statement control structure of the first programming language into a control structure of the second programming language.

177. The method of claim 174 wherein the first programming language does and the second programming language does not use an aperiodic-timed-statement control structure, the control structure consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment, it being anticipated that the specified code segment will execute in time segments spread over a plurality of execution periods, the time segments in the plurality of execution periods adding up to the specified increment of time, execution otherwise being aborted, the method further comprising:

translating the aperiodic-timed-statement control structure of the first programming language into a control structure of the second programming language.

178. The method of claim 174 wherein the first programming language does and the second programming language does not use an atomic-statement control structure, the control structure consisting of (1) a keyword identifying the structure and (2) a specified code segment, the specified code segment being execution-time analyzable, the control structure requiring that either enough time be assigned to execute the specified code segment or that none be assigned, the method further comprising:

translating the atomic-statement control structure of the first programming language into a control structure of the second programming language.

Description

BACKGROUND OF THE INVENTION

This invention relates generally to computer programming methods pertaining to real-time applications and more specifically to programming methods which enable the development of real-time software that can run on computer systems of different designs.

Java (a trademark of Sun Microsystems, Inc.) is an object-oriented programming language with syntax derived from C and C++. However, Java's designers chose not to pursue full compatibility with C and C++ because they preferred to eliminate from these languages what they considered to be troublesome features. In particular, Java does not support enumerated constants, pointer arithmetic, traditional functions, structures and unions, multiple inheritance, goto statements, operator overloading, and preprocessor directives. In their place, Java requires all constant identifiers, functions (methods), and structures to be encapsulated within class (object) declarations. The purpose of this requirement is to reduce conflicts in the global name space. Java provides standardized support for multiple threads (lightweight tasks) and automatic garbage collection of dynamically-allocated memory. Furthermore, Java fully specifies the behavior of every operator on every type, unlike C and C++ which leave many behaviors to be implementation dependent. These changes were designed to improve software scalability, reduce software development and maintenance costs, and to achieve full portability of Java software. Anecdotal evidence suggests that many former C and C++ programmers have welcomed these language improvements.

One distinguishing characteristics of Java is its execution model. Java programs are first translated into a fully portable standard byte code representation. The byte code is then available for execution on any Java virtual machine. A Java virtual machine is simply any software system that is capable of understanding and executing the standard Java byte code representation. Java virtual machine support is currently available for Apple Macintosh, Microsoft NT, Microsoft Windows 95, Silicon Graphics IRIX, and Sun Solaris. Ports to other environments are currently in progress. To prevent viruses from being introduced into a computer by a foreign Java byte-code program, the Java virtual machine includes a Java byte code analyzer that verifies the byte code does not contain requests that would compromise the local system. By convention, this byte code analyzer is applied to every Java program before it is executed. Byte code analysis is combined with optional run-time restrictions on access to the local file system for even greater security. Current Java implementations use interpreters to execute the byte codes but future high-performance Java systems will have the capability of translating byte codes to native machine code on the fly. In theory, this will allow Java programs to run approximately at the same speed as C++.

Within Sun, development of Java began in April of 1991. Initially, Java was intended to be an implementation language for personal digital assistants. Subsequently, the development effort was retargeted to the needs of set-top boxes, CD-ROM software, and ultimately the World-Wide Web. Most of Java's recent media attention has focused on its use as a medium for portable distribution of software over the Internet. However. both within and outside of Sun, it is well understood that Java is much more than simply a language for adding animations to Web pages. In many embedded real-time applications, for example, the Java byte codes might be represented in system ROMs or might even be pre-translated into native machine code.

Many of the more ambitious "industrial-strength" sorts of applications that Java promises to enable on the Internet have associated real-time constraints. These applications include video conferencing integrated with distributed white boards, virtual reality, voice processing, full-motion video and real-time audio for instruction and entertainment, and distributed video games. More importantly, the next generation Web client will have even more real-time requirements. Future set-top devices will connect home televisions to the Web by way of cable TV networks. Besides all of the capabilities just mentioned, these systems will also support fully interactive television applications.

Java offers important software engineering benefits over C and C++, two of the more popular languages for current implementation of embedded real-time systems. If Java could be extended in ways that would allow it to support the cost-effective creation of portable, reliable real-time applications, the benefits of this programming language would be realized by a much larger audience than just the people who are implementing real-time Web applications. All developers of embedded real-time software could benefit. Some of the near-term applications for which a real-time dialect of Java would be especially well suited include personal digital assistants, real-time digital diagnosis (medical instrumentation, automotive repair, electronics equipment), robotics, weather monitoring and forecasting, emergency and service vehicle dispatch systems, in-vehicle navigation systems, home and business security systems, military surveillance, radar and sonar analysis, air traffic control, and various telephone and Internet packet switching applications.

Java has much to offer developers of embedded real-time systems. High-level abstractions and availability of reusable software components shorten the time-to-market for innovative products. Its virtual machine execution model eliminates the need for complicated cross-compiler development systems, multiple platform version maintenance, and extensive rewriting and retesting each time the software is ported to a new host processor. It is important to recognize that the embedded computing market is quite large. Industry observers have predicted that by the year 2010, there will be ten times as many software programmers writing embedded systems applications as there will be working on software for general purpose computers.

Unlike many existing real-time systems, most of the applications for which a real-time Java is intended are highly dynamic. New real-time workloads arrive continually and must be integrated into the existing workload. This requires dynamic management of memory and on-the-fly schedulability analysis. Price and performance issues are very important, making certain traditional real-time methodologies cost prohibitive. An additional complication is that an application developer is not able to test the software in each environment in which it is expected to run. The same Java byte-code application would have to run within the same real-time constraints on a 50 MHz 486 and on a 300 MHz Digital Alpha. Furthermore, each execution environment is likely to have a different mix of competing applications with which this code must contend for CPU and memory resources. Finally, every Java byte-code program is supposed to run on every Java virtual machine, even a virtual machine that is running as one of many tasks executing on a time-sharing host. Clearly, time-shared virtual machines are not able to offer the same real-time predictability as a specially designed real-time Java virtual machine embedded within a dedicated microprocessor environment. Nevertheless, such systems are able to provide soft-real-time response.

SUMMARY OF THE INVENTION

The invention is a real-time programming method (RTPM) for use in writing application programs to be executed by virtual machines and a method practiced by a real-time virtual machine (RTVM) while executing an application program written in accordance with a real-time programming method. The invention also includes a method for translating an RTPM programming language into a second programming language, the RTPM programming language being an extended version of the second programming language. The RTPM programming language includes real-time code expressions for specifying real-time execution requirements. The method of translating the real-time code expressions is such that the execution of a second-language translation of a RTPM-language application program complies with the real-time execution requirements on a best-effort basis.

The RTPM utilizes a configure method and a negotiate method. The invocation of the configure method in an application program results in the quantification of the needs for one or more resources during execution of the application program by a virtual machine. The invocation of the negotiate method in an application program causes a negotiation to occur between the application program and the virtual machine concerning the allocation of one or more resources to the application program, the resources including CPU time, total memory, and memory allocation rate.

The RTPM utilizes control structures consisting of (1) a keyword identifying the structure, (2) a specified increment of time, and (3) a specified code segment that pertain to timed statements, preemptible timed statements, and aperiodic timed statements. For a timed-statement control structure, it is anticipated that the specified code segment will execute within the specified increment of time, execution otherwise being aborted. For a preemptible-timed-statement control structure, it is anticipated that the specified code segment will execute during a plurality of time slices within an execution period, the plurality of time slices adding up to the specified increment of time, execution otherwise being aborted. For an aperiodic-timed-statement control structure, it is anticipated that the specified code segment will execute in time segments spread over a plurality of execution periods, the time segments in the plurality of execution periods adding up to the specified increment of time, execution otherwise being aborted.

The RTPM also utilizes an atomic-statement control structure. The atomic-statement control structure consisting of (1) a keyword identifying the structure and (2) a specified code segment, the specified code segment being execution-time analyzable, the control structure requiring that either enough time be assigned to execute the specified code segment or that none be assigned.

The real-time tasks handled by the RTPM include periodic, sporadic, ongoing, and spontaneous real-time tasks, the method of execution of a real-time task comprising a startup method, a work method, and a finish method. The startup and finish methods are execution-time analyzable. The startup, work, and finish methods are invoked in sequence each time a periodic, sporadic, or spontaneous task is executed. The startup method is invoked exactly once for an ongoing task following which the work method is invoked and suspended repeatedly. The finish method for the ongoing task is invoked only when the corresponding real-time activity terminates.

The RTPM utilizes a real-time executive object to provide services in response to requests by the application code, the services being intended to provide information relating to the real-time activities.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a code segment that is allowed to execute no longer than 30 .mu.s.

FIG. 2 shows the translation of the FIG. 1 code segment into code for a Java virtual machine.

FIG. 3 shows a code segment which allows a timed statement to span multiple time slices within a particular execution period.

FIG. 4 shows the translation of the FIG. 3 code segment into code for a Java virtual machine.

FIG. 5 shows a code fragment which limits the total CPU time dedicated to a particular activity but allows this CPU time to span multiple periods.

FIG. 6 shows the translation of the FIG. 5 code segment into code for a Java virtual machine.

FIG. 7 shows a code fragment which describes an atomic segment of code.

FIG. 8 shows the translation of the FIG. 7 code segment into code for a Java virtual machine.

FIG. 9 shows a code segment which declares the data structure used to request preferential treatment in the assignment of resources.

FIG. 10 shows a code segment that defines the class of real-time activities.

FIG. 11 shows a code segment that defines the class ActivitySupervisor.

FIG. 12 shows a code segment that identifies the three methods associated with each real-time task.

FIG. 13 shows a code segment that defines the class TaskSupervisor.

FIG. 14 shows a code segment that defines the class PeriodicSupervisor.

FIG. 15 shows a code segment that defines the class ThreadSupervisor.

FIG. 16 shows a code segment that defines the class ActivityResource.

FIG. 17 shows a code segment that defines the class TaskResource.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

The invention is a real-time programming method (RTPM) intended to serve a spectrum of domains ranging from simple multimedia entertainment software for children to highly complex hard-real-time applications critical to the nation's defense systems. The intention is to standardize on this programming notation as a common platform for the development of shared software development tools and reusable software components. Clearly, the rigor with which particular applications need to comply with real-time constraints depends on price/performance issues and risk analyses that are different for each application. The RTPM is such that individual developers can choose to handle these tradeoffs differently.

The RTPM is a superset of virtual machine programming methods (VMPMS) exemplified by "JAVA", a programming language developed by Sun Microsystems, Inc., in that it offers additional syntax and additional time- and memory-related semantics to the VMPM programmer. However, it is a subset in that it forbids certain legal VMPM practices in cases when the use of these practices would interfere with the system's ability to support reliable compliance with real-time requirements.

RTPM programs are implemented by a special preprocessor (RTPMPP) that converts the superset dialect into VMPM code. Alternatively, RTPM programs are implemented by a compiler (RTPMC) that combines the effects of RTPMPP with the effects of a traditional Java compiler. This VMPM code is then translated to VMPM byte codes by an ordinary VMPM compiler. The resulting VMPM byte codes can be executed on a VMPM virtual machine or on a specially designed RTPM virtual machine. On a VMPM virtual machine, the translated RTPM application will make best-effort attempts to comply with the specified real-time requirements. There are a number of reasons why traditional virtual machines are unable to guarantee reliable compliance with real-time constraints. Nevertheless, for applications that are constrained by real-time expectations, executing an RTPM program on a traditional virtual machine offers important benefits over writing code in a VMPM language. In particular:

1. Application programmers are provided with standard notations in which to encode the desired real-time behavior as part of their VMPM source. This contributes to the ease of long-term software maintenance; and

2. Though the execution environment may not be able to satisfy all of the desired real-time constraints, at least the execution environment can be made aware of where it is falling short.

This information can be used by the run-time system and the application code itself to dynamically adjust service quality and load balancing.

For best performance and real-time predictability, it is necessary to run the translated byte codes on a specially designed RTPM virtual machine.

The RTPM languag