======= LSN004.PrInherit ======= Language Study note on the support for Priority Inheritance Mechanisms Offer Pazy Marchg 25, 1991. Note: This is not a "typical" language study note. It has to do more with the CIFO's RTK, but many issues are similar to the problem we encounter in the language design. I should thanks Ted Baker who has worked with me on some of this issues. Priority Inheritance ---------------------- This interface tries to define a minimal MECHANISM to implement any kind of priority inheritance, whether it be transitive or not, or just the normal Ada83 rendezvous rules. It does not require the kernel to know anything about what POLICY you are actually using, only the USAGE of this interface by the RTS/XRTL will determine that policy. I define a new RTK object called a Priority_Agent. There are four available operations defined for this object type: Create_Agent, Delete_Agent, Associate_With, Dissociate_From. Each such object has only one owner, the creator, (see below for an alternative). Any VP may associate itself with any visible object (it does not make sense for the creating VP to associate itself with its own object, or for a VP to associate itself twice with the same object with no intervening Dissociate). For now, (see more below), Each VP may create any number of such objects. By associating a VP with a Priority_Agent object, the RTK's ACTIVE priority of that VP is added to the set of priorities "contained" in this object. Whenever the RTK's ACTIVE priority of a VP included in the set, is modified, it will be reflected in the set of priorities in all objects of which that VP had associated itself with. (Yes, a VP may associate itself with more than one object at a time). The mechanism says that the RTK's ACTIVE priority of a VP is always the maximum if its own BASE priority, the priority of the locks it is holding, and all the priorities in all the sets of owned agents. The RTS/XRTL can decide when to associate/dissociate VP's from Agent objects, and hence determine the actual policy in effect. with "VP_IDs"; package Priority_Inheritance_Mechanism is -- This is just an example, I don't worry here about the popular issue -- of dangling references vs memory leaks. type Priority_Agent is limited private; -- Each instance of this type will be initialized to Null_Agent. Null_Agent : constant Priority_Agent; procedure Create_Agent (Obj : out Priority_Agent); -- Creates an object, the calling VP is the owner procedure Delete_Agent (Obj : in out Priority_Agent); -- Deletes Obj, and returns Null_Agent in it. procedure Associate_With (Obj : Priority_Agent); -- Or "in out" ? -- Associates the calling VP (and its priority) with Obj procedure Dissociate_From (Obj : Priority_Agent); -- Or "in out" ? -- Dissociates the calling VP (and its priority) from Obj -- Raises XXX if VP is not in the set ? end Priority_Inheritance_Mechanism; There are two points that may be addressed differently: 1. Shall we use Create/Delete, so the object always belongs to the same VP ? Or shall we define a Transfer_Agent_Ownership (Obj : Priority_Agent; To : Vp_ID); ? I think that the trade-offs are clear. 2. Does it make sense for a VP to own more than one Priority_Agent at the same time. It makes the implementation slightly more complex, but it allows a nice allocation of Agents for each resource the VP is holding. Or is it really the VP itself which blocks other VP's (for whatever reason) and conceptually there is only one "set" per VP ? ============================================================================= Priority Inheritance and Protected Records -------------------------------------------- A protected record may want the concept of ownership so that owners of the protected record can inherit the priority of the tasks suspended on the entries of the protected record. This could be implemented by having a general "ownership" type object, which must be a parameter to locking operations which acquire ownership. The finalization for an ownership object will perform the operation which gives up ownership (if not already given up). The ownership object itself will hold a reference to the protected record, a reference to the owning task, and links for chaining on the task owned-object list and the protected record owning-task list. This approach allows the compiler to allocate the storage for linking tasks into ownership lists, as well as provide an automatic clean-up (finalization) if an owning task exits prematurely (so as to release a semaphore, etc.). =============================================================================== Priority Inheritance and the RTK ---------------------------------- There is no support for priority inheritance between VP's. We do believe inheritance to be important, and even mandatory for certain applications, and we hope that users who construct blocking constructs such as semaphores using the RTK consider some form of priority inheritance. Unfortunately the cost of implementing inheritance must be paid in the most time critical parts of the RTK. We do not wish to penalize those systems which do not require inheritance by mandating its inclusion. If priority inheritance is required, several implementation choices are available. Inheritance can be implemented by simply changing VP Base Priorities as needed. This approach can be expensive, as it can introduce extra dispatching points into the system, and tricky book-keeping as well. These problems are aggravated by the need for many-to-one inheritance in Ada tasking, as during task activation or while a completed master task is waiting for its children to terminate. An alternative approach might use a package as follows: with RTK; package RTK_Inheritance is procedure Create_Relationship(Grantor, Receiver: RTK.VP_ID); procedure Destroy_Relationship(Grantor, Receiver: RTK.VP_ID); end RTK_Inheritance; This package allows the RTK to build a graph to describe the inheritance relationships between VP's. Considering each VP as a node in a directed graph, Create_Relationship adds an edge between Grantor and Receiver and Destroy_Relationship deletes it. Such a graph can allow the RTK to perform inheritance by traversing the graph during dispatching, implementing the classic operating system technique of time-slice passing. Extra dispatching points are avoided, and many-to-one inheritance can be supported. For example, here is an implementation of blocking semaphores using this package. with RTK; package Semaphores is type Semaphore is private; procedure Acquire(S: in out Semaphore); procedure Release(S: in out Semaphore); private type Semaphore is record RTK_Lock: RTK.Lock; Q: VP_Q_Type; Is_Locked: Boolean:= FALSE; Owner: RTK.VP_ID; end record; end Semaphores; with RTK; with RTK_Inheritance; package body Semaphores is ...declarations... procedure Acquire(S: in out Semaphore) is begin RTK.Seize_Lock(S.Lock); if not S.Is_Locked then S.Is_Locked:= True; S.Owner:= RTK.Self; else Enqueue(S.Q); RTK_Inheritance.Create_Relationship(RTK.Self, S.Owner); RTK.Suspend_Self(RTK.Self, Suspend_ID); end if; RTK.Release_Lock(S.Lock); end Acquire; procedure Release(S: in out Semaphore) is Waiter: RTK.VP_ID; New_Q: VP_ID_Q_Type; begin RTK.Seize_Lock(S.Lock); if (Is_Empty(S.Q)) then S.Is_Locked:= FALSE; S.Owner:= RTK.Null_VP; else S.Owner:= Dequeue(S.Q); RTK_Inheritance.Destroy_Relationship(S.Owner, RTK.Self); while (not Is_Empty(S.Q)) loop Waiter:= Dequeue(S.Q); Enqueue(New_Q, Waiter); RTK_Inheritance.Destroy_Relationship(Waiter, RTK.Self); RTK_Inheritance.Create_Relationship(Waiter, S.Owner); end loop; S.Q:= New_Q; RTK.Resume(New_Owner, Suspend_ID); end if; RTK.Release_Lock(S.Lock); end Release; end Semaphores;