Time Partitioning Webinar Project

A place to coordinate webinar participant questions.

Description

Participants to our recent Time Partitioning webinar have left some questions that we need to answer and get back to them on.

This project page serves as a place to edit and document our responses. At the conclusion of the response review cycle, we'll ask that the responses be transmitted.

This project is related to Deos_Q2_Marketing_Project

Questions

ID	Participant	Done?	Question
Q1	Don Clementi	Yes	How are thread constraints defined?
Q2	Frank Zhang	Yes	Is there a deadlock if Matt (interrupt) has used up his 5 min while other 2 people (threads) are waiting for something to react to the Matt's message?
Q3	Carl Romanik	Yes	Matt or Bill, Does Deos dynamicslly decide the sequencing of threads at the beginning of each period, or is it constant period to period? What parameters does Deos use to base its real time thread sequencing decision(s)?
Q4	Lynn Haney	Yes	Does Deos adjust the priority of threads if they do not have a specified order in which they have to run? (In order to guarantee that a thread will run?)
Q5	Devendra Tripathi	Yes	What is the cost (uS) of switching itself?
Q6	Warren Ballew	Yes	RE slack...how many typical cycles to clear "worst case" backlog? 5?
Q7	Sergio Penna	Yes	When a DEOS thread consumes all of its allotted execution time, is it notified before removed from execution, so it can have a chance to save context for the next activation?
Q8	Sergio Penna	Yes	When a DEOS ISR thread consumes all of its allotted execution time, is it notified before removed from execution, so it can have a chance to save context for the next activation?
Q9	Sergio Penna	Yes	How does an User Mode ISR connect to its kernel counterpart (I'm assuming it must have one)?
Q10	Sergio Penna	Yes	Does DEOS have a "Resource Monitor", such as the one sold by IARSN System Software (www.iasrn.com) named "TaskInfo" for Microsoft Windows or, for old-timers, the MONITOR available for DEC's VMS operating system?

Responses

Q1

Deos threads have the following attributes which are used to constrain their run-time behavior: - Fixed execution budget - Rate at which to execute - Stack size - Optional execution order relative to other threads in the system - Optional use of slack time.

All of these attributes are specified at integration-time, and in XML form.

The process from which a thread is created will also constrain the space partitioning of all threads in that process. These contstraints include: - Access control to physical devices - Access control to memory shared between processes - Access control to run-time created kerenl objects such as semaphores and mutexes. - The maximum number of kernel objects that can be simultaneously created at run-time (processes, threads, semaphores, etc.).

Some of access control is granted at integration-time (in XML form), and some access control is granted at run-time.

For all integration-time specified attributes/constraints, there is workstation tooling to process the various XML files into a binary file referred to as the Deos registry. The Deos registry can subsequently be loaded onto a Deos target for use. Deos supports dynamic linking and individual file loading, so a change to the Deos registry can be made without changing any other aspect of the system.

Q2

If the Matt interrupt thread has consumed its budget for the current period, the Matt interrupt thread will not execute until its next period. In the suggested scenario, two other threads in the system are blocked (say on a Deos Event object), and the normal completion of the Matt interrupt thread would pulse that Event, thereby unblocking the two blocked threads.

In the next period, when the Matt interrupt gets its budget replenished, it will resume execution from where it was preempted by the out-of-budget timer interrupt. At that point, it will pulse the Event and the two waiting threads will resume execution. In this case, there is no deadlock, but there could be a delay in the resuming of the blocked threads.

The root question here is probably "What happens when a thread overruns its budget?" The answer is Deos causes an immediate context switch from out-of-budget to another thread. When the out-of-budget thread gets a replenished budget, it will receive a software exception we call Time Budget Exceeded, or TBE. The default handler for a TBE is to do nothing. In the Matt scenario, the Matt thread would be context switched in with a full budget and continue on to pulse the Event. In Deos, exception handling behavior is configurable at run-time, and users are allowed to implement their own local exception handling functions. Of course, there is a Deos default behavior for all exceptions as well.

If the Matt thread had previously installed a TBE handler, and that handler function cause the Matt thread to restart itself, then the deadlock situation you described could occur, as the Matt thread might not ever have enough budget to actually pulse the Event.

Q3

Unless there is a specific, explicit declaration for the execution order of threads, Deos (RMA) is free to schedule the same-rate (same-priority) threads in any order. Users are encouraged to not care about the scheduling order in all other cases, and to design their software to tolerate sub-period timing jitter, and in cases where that is not possible, to explicitly declare the need for an ordering dependency. By not documenting the algorithm, Deos is free to optimize it over time and not cause your software to break, and more importantly, Deos is free to create and delete threads at run-time which might otherwise perturb the thread ordering.

At integration time, it is possible to define an explicit ordering dependency between same-rate threads (e.g, thread A must run before thread B).

If it becomes important to have sub-period thread activation (i.e., to ensure a thread run at a fixed position within a period), we would recommend associating that thread with an interrupt.

Q4

Rate Monotonic Analysis (RMA) dictates that a thread's scheduling priority and its execution rate are synonymous. Faster threads are higher priority.

When the execution rates in an RMA system are harmonic (which is the case with the Deos scheduler), meaning the length of a period is an even multiple of the next slowest period, processor utilization can be deterministically pushed to 100 percent utilization. Deos requires harmonic rates for this very reason. As such, using very simple logic, Deos can determine at run time if the creation of a process (and its threads), will be schedulable. Once a thread is created, it is known (and guaranteed) that each thread will receive its CPU budget in its period.

So to answer your question, no, thread priorities do not have to be adjusted in order to ensure execution. Guaranteed execution can be determined at integration time using RMA.

Q5

Meaningful context switch times can not be discussed in the absence of real hardware (i.e., the time is hardware dependent). Deos ships with an instrumented version of the Kernel that measures the worst case context switch time (as well as other key time partitioning values) on your hardware. Note: most OSes report their best case context switch times.

Q6

Slack is not something that has to be "cleared". If no thread needs to run and no thread is ready to run (including those that wish to consume slack), then the time simply goes to idle. Due to the two sources of slack time (unused timeline and early completion) it is possible for low rate threads to generate slack time that will then be used by high rate threads. In other words, a low rate thread completes early thereby allowing a higher rate thread (who is waiting on slack) to run again using the newly generate slack time. Also note that, even if idle runs, interrupt threads could cause scheduling and/or slack time consumption/generation.

Q7

When a Deos thread attempts to exceed its budget, Deos will save its context for its next execution. In addition, Deos will "push" a Time Budget Exceeded (TBE) exception onto the offending thread's stack. The TBE handler can be implemented by the thread's software designer, and is typically used to take some action as a result of the thread's attempted over-run. The TBE will run at the beginning of the thread's next activation. Once the TBE completes, the thread will continue execution where it left off (depending upon the behavior of the handler). If the software designer chooses not to install a TBE handler, Deos will provide one by default. This default handler is a "do nothing" (i.e., a NOP). Therefore, the system default behavior is for the thread to "pick up where it left off" during its next activation.

Q8

The answer is the same as a non-ISR thread (see above). However, it is important to note that even ISR threads have a rate or period from the Deos scheduler's perspective that is the system tick period (i.e., the fastest period in the system). Therefore, an ISR thread that exhausts its budget while handling an interrupt (which is not a slack consumer), will be allowed to "pick up where it left off" (see above regarding Time Budget Exceeded exception handlers) during its next activation. Its next activation will be in the next system tick period.

Note that all proprieties of a "normal" thread are shared with an ISR thread (e.g., containing process, period, budget, slack usage, etc.). An ISR thread simply has the additional capability to be scheduled based upon the occurrence of an interrupt (i.e., the Deos API waitUntilNextInterrupt()).

Q9

A User Mode ISR thread does not have a "kernel counterpart". A user mode ISR is simply switched to when its interrupt occurs and is then allowed to consume up to its budgeted amount of execution time. If it completes prior to exhausting its execution time budget, it could potentially be activated again if a subsequent interrupt occurs. This behavior can repeat until the ISR thread's budget has been exhausted. At the beginning of the next system tick, the budget will be replenished, and interrupt handling can then begin anew.

It needs to be noted that since Deos allows users processes to "own" direct access to hardware, there is rarely a need for interrupt handlers to run in kernel mode. The obvious benefit then becomes that low design assurance code can handle their own interrupts, and this interrupt handling code will not need to be certified to the same design assurance level as the kernel.

Q10

Yes, the Deos development tool suite includes a monitor such as you described known as the "Status Monitor". One can use the Status Monitor GUI and/or a telnet connection for scripting purposes.