From bobduff Wed Dec 16 15:52:44 1992 From: bobduff (Bob Duff) To: ada9x-mrt To: iso@ajpo.sei.cmu.edu Subject: LSN-1060 on Low-Level Primitives in the RT Annex !topic LSN on Low-Level Primitives in the RT Annex !key LSN-1060 on Low-Level Primitives in the RT Annex !reference MS-H;MS-13 !from Offer Pazy $Date: 92/12/03 12:48:15 $ $Revision: 1.3 $ !discussion This Language Study Note discusses the issue of introducing low-level primitives in the real-time annex. This LSN is in response to resolution number 3-4 of the ISO/WG9 Salem meeting. INTRODUCTION: ------------- The original need for the proposed primitives came for the US Army/CECOM as a mechanism to provide an alternate low-level functionality for the construction of fast, predictable, and certifiable systems. In the past six months, the idea gained wider support in several meetings (ARTEWG, DR's, WG9 and IRTWA6). After analyzing the requirements and the possible solutions, it was discovered that the utility of such abstractions can be extended beyond the "lean and mean" embedded environments (e.g. the pragma RESTRICTIONS); in fact they can be used in a stand-alone mode together with other language features with a substantial performance boost. The MRT has therefore designed this feature accordingly so it will be suitable in both scenarios. The proposal is made out of three parts: 1) Some kind of asynchronous hold/continue based on a priority-change model. 2) A private semaphore (aka "suspension object") which provides primitive suspend-me/resume capability with support for two-stage suspend, and with semantics expressible using a protected type. 3) A requirement for special recognition of entry-less protected types. These three seem adequate to get full support for suspend/resume and critical-region based programming, with minimal overhead and reasonable semantics. They are also defined in such a way that they use existing 9X semantics with minimal disturbance to the rest of the language rules. These primitives can be used collectively or individually to achieve the desired performance gains. When used with other language features, their semantics and interactions are well-defined. They can also be used (and designed for) with the RESTRICTIONS pragma. Then, they complete the necessary functionality to provide an extremely efficient, simple, and minimal low-level kernel. Below we introduce the three parts of the proposal. Each part starts with the semantic definition followed by a rationale. Note that we include some minor alternatives for the specific capabilities; these are enclosed in [ ]. ASYNCHRONOUS TASK CONTROL ------------------------- The "Suspend_Other" and Resume are expressed in terms of modifying base priorities. The Suspend_Other will be called "Hold" and the resume "Continue". A special constant value (in the System.Any_Priority range) is defined to mark a held task. This value is the lowest value in the system, lower than any conceptual "idle task" (this model is necessary to guarantee the semantics in multi-processor environments). The Hold operation lowers the base priority of the task to this special value, and the Continue operation raises it back to the last base priority the task had (or the initial one). The "Held" state (i.e. "very low" priority) should not be confused with the "Suspended" state as defined in the core, the task is still in an "eligible for execution" state. The rest of the scheduling/queuing semantics are ramifications of these rules. In particular, the rules for computing active priorities are still in effect, which means that if the target task is currently inheriting priorities from other sources (e.g. it is executing a protected action), its active priority does not change, and it continues to execute until it leaves the protected action, at which point it becomes held. This behavior is the behavior we want, and the semantic description is simpler and more consistent this way. In order to avoid dependency on the Dynamic_Priorities package (both if the implementation does not support it, or the user does not need it elsewhere in the program), the Hold/Continue operations are defined in a separate package. The semantics, however, are still defined in terms of changing the base priorities. [The interaction with Set/Get_Priority (where the package Dynamic_Priorities is used) can be defined slightly different. It seems simple and more consistent to let them do the "normal" thing, i.e. Get_Priority of a Held task will return the special value, while Set_Priority of a task with that special value will effectively cause it to be held. If a Set_Priority is called on a Held task with a "normal" value, it will set the base priority, thus causing it to be continued. The only difference then between Hold/Continue and Set_Priority would be that the Hold saves the current base priority which will be restored later by Continue.] In addition, we are proposing an Is_Held boolean query function. Even though the result is not always reliable (inherent races due to asynchrony), it may be useful in some circumstances where other user-mechanisms ensure the stability of the result. The proposed package: package Asynchronous_Task_Control is procedure Hold(T : Task_ID); procedure Continue(T : Task_ID); function Is_Held(T : Task_ID) return Boolean; end Asynchronous_Task_Control; [A possible addition: We have considered adding versions for Hold and Continue with an output boolean parameter Is_Held. The implementation burden is trivial, and the answer is slightly more robust than with the function result. However, it is not clear under which scenarios such an OUT parameter is useful. It is almost certain that in a given program, there is only one "controlling" module, i.e. there won't be more than one entity who is independently holding/continuing other tasks (at least that was not the initial requirement). So this functionality seems redundant since the same information can be stored in the controlling module itself.] RATIONALE: ---------- There seems to be a nice separation between the two cases where dynamic priorities are used and where they are not. When dynamic priorities are not used, tasks' base priorities are not changed after the task is created. It therefore makes sense for the Hold/Continue to restore the task's original priority when it is continued. When dynamic priorities are being used, (we have to remember that we piggyback on the priority model for simplicity of implementation and semantic description), then it makes sense to leave the restoration of continued tasks to the user if the holding is done through Set_Priority(Very_Low). Another alternative that we have considered was to have the "held" state semantically (and implementation-wise) visible. This will mean that when a task is held, that state is being remembered as a boolean value without affecting the base priority value. This approach would have taken us further away from the "held-as-very-low-priority" model, and we would have to define the entire scheduling and queuing behavior in terms of this additional state. Consequently, the implementation would have to do the same. With the current approach, this is not needed. A down-side of this approach is the need to reserve one value in the Any_Priority range for that special use. As for queuing rules, they are all derived from the base/active priorities rules: 1. A task on a queue will have its priority so low as to "never" reach the top of the respective queue as long as there are other tasks on that queue. 2. If a task is in a middle of a protected action, inside a rendezvous, or is inheriting priorities from other sources (e.g. when activated), it will continue to execute until the end of the corresponding region. 3. When a task is caller in a rendezvous, and while waiting for the rendezvous to end, it is being held, the active priority of the acceptor will NOT be recomputed. This is consistent with the fact that the RT annex does not require transitive priority inheritance. 4. If a task is being held when it waits for entry calls (i.e. the entries are already open), one "cycle" of the accept body will execute, but no more, since when the server finishes the accept body, there is a period of time (maybe very short, but still a different state) in which it executes without inheriting priorities. The benefit of avoiding a special case in this case, and simplifying implementation seems to justify this additional "cycle". 5. The same is true if the held task is the only one in a protected entry with an open barrier. The entry body will execute. Regarding (4) and (5) above, we have to remember that the Hold operation is asynchronous with respect to the target task, and there is always an inherent race involved. Since the Hold may be issued just after the accept/entry bodies start, there does not seem to be a testable difference, and the proposed rules do seem to provide a more reliable and consistent behavior. SYNCHRONOUS TASK CONTROL ------------------------ We propose the definition of a suspension object (a private semaphore). This object can be used for "two-stage-suspend" operations and as a simple building block for the implementation of higher-level queues by the user. A suspension object has a boolean state (true, false, and the initial value will be false), operations to change the state and to query it (potentially, see below), and a procedure to suspend the caller until the state is true. This object is assumed to be private to the task declaring it. By private we mean that only the declaring task will suspend on it, other tasks, of course, can call Set_True. We don't actually require that this be true, we just require that the count of callers will never be more than one. Here is a tentative spec: package Synchronous_Task_Control is pragma Pure(Synchronous_Task_Control); type Suspension_Object is limited private; -- Note that this is a (limited) private type, -- so it does not support conditional or timed calls, -- though conditional calls can be simulated using -- Current_State or Set_False with an OUT parameter . procedure Set_True(S : in out Suspension_Object); procedure Set_True(S : in out Suspension_Object; Old_State : out Boolean); procedure Set_False(S : in out Suspension_Object); procedure Set_False(S : in out Suspension_Object; Old_State : out Boolean); function Current_State(S : Suspension_Object) return Boolean; procedure Suspend_Until_True(S : in out Suspension_Object); -- Raises Program_Error if another task is already suspended on -- the suspension object. -- Calling this entry is a bounded error if used from within a -- a protected operation. private . . . -- See rationale end Synchronous_Task_Control; It is a bounded error to call Suspend_Until_True from within a protected action (ideally Program_Error will be raised). A Program_Error will be raised on call to Suspend_Until_True if another task is already suspended on the same object. An implementation requirement is that Set_False and Set_True may be called during any protected action, even one running at an interrupt priority level (these procedures are like protected ones). RATIONALE: ---------- A suspension object would contain little more than a bit and a single TCB pointer. It would *not* contain a queue as that would defeat the purpose of allowing users to implement their own queuing. Also, this avoids having to worry about FIFO vs. priority queuing. Finally, it represents a lowest-common denominator that can almost certainly be implemented easily on top of any kernel. To support "two-stage suspend" a task would call Set_False from some protected action, and then do a Suspend_Until_True after it leaves it. Meanwhile, another task would call Set_True to wake up the suspended task, anytime after the Set_False (including both before and after Suspend_Until_True is called). This technique helps to prevent race conditions since the associated data structures (which control the suspension requests) can be manipulated under the protection of the lock as well as marking the intention to suspend-self. The abstraction of a private semaphore (by requiring the wait-count to be at most 1) fits quite nicely with the traditional Suspend/Resume operations. The object's "bit" corresponds to the task state that is commonly maintained by the kernel. We currently require a Program_Error to be raised if Suspend_Until_True is called and another task is already waiting on the same object. This requirement seems quite straightforward and cheap to implement (checking if the "TCB" field is empty before storing the new one). It also enhances portability. However, such an error is not likely to happen very often in the usage idiom anticipated for this primitives, so instead we may leave it a bounded error, or define that both tasks will be suspended, but only one (the last ?) might be woken up by a subsequent Set_True, with the other suspended until aborted. [An open question is the availability of return values and the Current_State function. All seem quite easy to implement, they don't add distributed overhead, and it seems natural to allow query functions for state that can be set by a user. However, they do add to the apparent "weight" of the package, and it is not clear that these are needed in a likely usage of such a package. Furthermore, Current_State suffers from the obvious race conditions.] This is an implementation model of the package: We use a protected type to define semantics, though it is expected to be implemented directly by the "kernel". Note that the Really_Wait entry and the requeue in Suspend_Until_True are here only to illustrate the check for 'COUNT = 1. package Synchronous_Task_Control is . . . private protected type Suspension_Object is procedure Set_State(New_State: in Boolean; Old_State : out Boolean); entry Wait_Until_True; -- Raises Program_Error if some task is already -- suspended, and otherwise requeues on Really_Wait function Current_State return Boolean; pragma Interrupt_Priority; -- So these can be used -- by interrupt handlers, etc. private entry Really_Wait; -- This one really waits State : Boolean := False; end Suspension_Object; end Synchronous_Task_Control; package body Synchronous_Task_Control is protected body Suspension_Object is procedure Set_State(New_State: in Boolean; Old_State : out Boolean) is begin Old_State := State; State := New_State; end Set_State; entry Wait_Until_True when True is begin if Really_Wait'COUNT > 0 then raise Program_Error; else requeue Really_Wait with abort; end if; end Wait_Until_True; function Current_State return Boolean is begin return State; end Current_State; entry Really_Wait when State = True is begin State := False; end Really_Wait; end Suspension_Object; -- Wrapper subprograms procedure Set_True(S : in out Suspension_Object) is Old_State : Boolean; begin S.Set_State(New_State => True, Old_State => Old_State); end Set_True; . . . procedure Suspend_Until_True(S : in out Suspension_Object) is -- Should Raise Program_Error if the current task holds a lock, -- or if another task is already suspended on the suspension -- object. begin S.Wait_Until_True; end Suspend_Until_True; end Synchronous_Task_Control; CRITICAL REGIONS ---------------- An implementation requirement in the Real-Time Annex will specify that entry-less protected types be recognized specially, and that they perform a lock (ideally a spin-lock) with minimal, documented overhead (metrics will be provided). There should be no overhead associated with checking entry barriers. RATIONALE --------- Entry-less protected types are suitable for simple mutual exclusion, interrupt handlers, use in a passive partition to coordinate active partitions, and in conjunction with Asynchronous_/Synchronous_Task_Control. Without entries, the semantics of such protected types is no more complex than any other traditional primitive used for mutual-exclusion (mutex, locks, critical regions, etc.) which is commonly provided by real-time kernels. Therefore, the same implementation approach may be used and as a result the same performance numbers can be achieved. ------ Output from automsg.perl ------ Mail received from bobduff Unrecognized version number in reference: MS-H;MS-13 **** Message not entered in comment database due to errors ----------- End of output ------------