Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-09-16
2004-06-22
Sheikh, Ayaz (Department: 2131)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06754690
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer operating systems, and more particularly, to a real-time operating system which schedules multiple threaded application programs or processes.
BACKGROUND OF THE INVENTION
Statement of the Problem
Real-time computer operating systems typically supervise the execution of multiple concurrently executing applications (more precisely, applications which are repetitively scheduled and whose execution is interleaved). These real-time operating systems must provide a means for scheduling the applications. In a ‘hard’ real time operating environment such as an aircraft cockpit, applications monitoring critical functions such as radio communication data and navigation information are typically executed together with applications monitoring other less critical functions. An operating system which supervises these multiple applications must ensure that the applications monitoring the less critical functions do not prevent the higher criticality applications from executing in a timely manner. In such an environment the computer operating system application scheduler must accomplish this by providing some form of time partitioning between the applications.
Presently available operating systems do not accurately account for operating system overheads such as interrupt handling, and are therefore incapable of enforcing timing boundaries between the applications. This lack of capability arises because existing Rate Monotonic Analysis (RMA) and Rate Monotonic Scheduling (RMS) theory and practice fail to account for computer operating system overheads and processor interrupts when determining the feasibility of a proposed schedule.
SUMMARY OF THE INVENTION
Solution
The application scheduling method of the present invention allows integration of critical real-time functions such as avionics display and control, while ensuring that the applications providing these functions are executed in a timely manner. The present scheduling method multiplexes processor (‘CPU’) time amongst multiple application threads. The time utilized by the operating system when executing on behalf of a thread is treated as being application processing time, rather than viewing the resultant processor time consumed as an operating system overhead. A time budget is assigned to each thread. The processor time consumed by the operating system when executing on behalf of a thread is charged back to the corresponding application as part of the application's time budget. The amount of CPU time available to a thread during a given period of its execution is guaranteed by the present method, which efficiently apportions available CPU time by interrupt masking and thread budgeting. Operating system overheads are thus accounted for accurately enough to determine a schedule for the applications which is enforceable by the operating system. Furthermore, the manner in which these overheads are accounted for permits run time creation and deletion of threads via traditional RMA methods.
Existing RMA theory accounts for operating system overheads by specifying a bound on the percent utilization that is expected to be used by the operating system on behalf of the applications running on the operating system. However, in a real-world system, there are three categories of overhead that should actually be accounted for:
1. First, interrupt response and other activities performed by the operating system that result from the passage of time must be accounted for. An example is a response to the periodic system clock ‘tick’ that provides notice of the passage of time to the operating system.
2. Secondly, application-induced overheads resulting from the invocation of operating system services should be accounted for.
3. Finally, the time taken in responding to asynchronous interrupts, e.g., non-periodic I/O such as network interface controller interrupts, needs to be accounted for.
These operating system overheads each require distinct mechanisms to accurately account for their use of processing time in an RMA-based scheme. Category 1 overheads (e.g., periodic system clock interrupt handling), by definition, are strictly a function of time, and thus the standard RMA technique of specifying them as utilization overhead is adequate.
Category 2 overheads (calls to operating system services) are a function of application behavior and cannot, in general, be accounted for in the manner of category 1 overheads. This is because application-induced overheads are not dependent solely on the passage of time; rather, in addition, they depend on the particular activities initiated by the applications. Category 2 overheads can be subdivided into two types:
2A. CPU time consumed by operating system services provided on behalf of an application; and
2B. Blocking time introduced by the effective priority elevation associated with disabling and enabling interrupts associated with a given application.
Overheads associated with category 2A activities are accounted for by the method of the present invention by viewing the time utilized as being application processing time, rather than viewing the resultant CPU time consumed as an operating system overhead. The present method charges this CPU time back to the application as part of the application's time budget.
Overheads associated with category 2B activities can be modeled as a mutex blocking time. Mutex (MUTual EXclusion) services are system functions which permit multiple threads to have synchronized access to application resources. For example, if an application uses multiple threads, and those threads share a common resource such as a data structure, mutexes can be used to ensure that only one thread can access the data structure at a given time.
The method of the present invention models category 2B blocking time by viewing a critical section as a mutex having the following properties:
a) A priority ceiling one greater than the highest actual application priority;
b) a period equivalent to the shortest period in the system being analyzed; and
c) a duration equal to the duration of the time-critical section associated with the longest critical section not part of a category 1 overhead (the period of time when interrupts are disabled).
Overheads associated with category 3 activities cannot, in general, be modeled as a strict utilization of operating system resources by an application. Existing RMA and RMS theory approximates the cost of category 3 overheads by specifying a processing time for each occurrence of the interrupt and a minimum inter-arrival rate for the interrupt, e.g. N interrupts per second, with each interrupt consuming M seconds. The result is a time utilization associated with the interrupt (M*N). Enforcing a schedule directly resulting from such an analysis requires keeping track of the inter-arrival rate of the interrupt, as well as the time consumed by each interrupt response.
One embodiment of the present invention eliminates the need for tracking the interrupt inter-arrival rate by (1) activating a thread in response to an interrupt; (2) associating a time period with the interrupt; and (3) ensuring that during that period the aggregate CPU utilization resulting from handling as many interrupts as necessary does not exceed an allowed value. This aspect of the invention, if implemented, subsumes the category 2B overheads described above. An alternative embodiment provides an interrupt with all of the properties described for a thread in the previous embodiment. In this case, the arrival of an interrupt and the termination of the interrupt handling are treated as a pseudo-thread activation.
Either of these (interrupt thread or pseudo-thread) solutions permits any number of interrupts associated with a specific interrupt to arrive during the associated period and also permits variability in processing time for each individual interrupt, as long as the aggregate used CPU utilization for the period does not exceed the allowed value for that particular interrupt. This method greatly simplifies the enforcement of the app
Honeywell Inc.
LaForgia Christian A.
Sheikh Ayaz
LandOfFree
Method for time partitioned application scheduling in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for time partitioned application scheduling in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for time partitioned application scheduling in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3339391