/* Written 6:47 pm Jun 1, 1992 by stt@inmet.camb.inmet.com in spock:ada9x.mail */ /* ---------- "LSN on Extensible Protected Types" ---------- */ From stt Mon Jun 1 18:46:55 1992 From: stt (Tucker Taft) To: ada9x-mrt@inmet Subject: LSN on Extensible Protected Types !topic LSN on Extensible protected types !key LSN-1030 !reference MS-9.5;4.0 !reference MS-3.4.1;4.0 !from Tucker Taft 92-06-01 !discussion [Note, we are numbering this LSN 1030 to avoid colliding with Art's sequence numbers for non-MRT LSNs] Now that we have pretty much agreed to have OOP in Ada 9X, as well as some kind of special syntax to support fast mutual exclusion (e.g. protected types), it seems appropriate to reopen the question of whether there should be a way to have extensible protected types. In an early Mapping Document we suggested a syntax, but gave no further explanation, and after some thought about implementation concerns, we dropped the idea. Recently, Ted Baker and others have been experimenting with adding concurrency control to abstract data types, and have found that the lack of "tagged" protected types makes the solutions awkward. In particular, one must shift from using a syntax-based non-queued mutual exclusion over to an explicit locking approach, using a protected object as a component. Here is an example of the approach: package Synch_Pkg is -- Define a type to be used as a component, -- and a type to be used as an exclusive handle on -- the component protected type Lock is entry Acquire; procedure Release; private record Locked : Boolean := False; end Lock; type Exclusive_Handle(On_Lock : access Lock) is new System.Controlled with null; procedure Initialize(Handle : in out Exclusive_Handle); procedure Finalize(Handle : in out Exclusive_Handle); end Synch_Pkg; package body Synch_Pkg is protected body Lock is entry Acquire when not Locked is begin Locked := True; end Acquire; procedure Release is begin Locked := False; end Release; end Lock; type Exclusive_Handle(On_Lock : access Lock) is new System.Controlled with null; -- Declare an object of this type -- to acquire a lock; it will be released -- automatically. procedure Initialize(Handle : in out Exclusive_Handle) is begin Handle.On_Lock.Acquire; -- acquire lock during init end Initialize; procedure Finalize(Handle : in out Exclusive_Handle) is begin Handle.On_Lock.Release; -- release lock when exiting end Finalize; end Synch_Pkg; Given the above package, we can embed such a lock in the root type of a tagged class, or we can use a generic to add it to any type. Here is how you could use it with a tagged type: with Synch_Pkg; package Whatever is type Concurrent_Type is tagged record Lock : Synch_Pkg.Lock; -- Other components to be added by extension end record; end Whatever; Now we can extend the root pkg with some components, and define some operations: with Whatever; package Another_Pkg is type Extension is new Whatever.Concurrent_Type with record Some_Component; end record; procedure Some_Operation(X : in out Extension); end Another_Pkg; with Synch_Pkg; package body Another_Pkg is procedure Some_Operation(X : in out Extension) is Handle : Synch_Pkg.Exclusive_Handle(X.Lock'ACCESS); -- X.Lock is now acquired begin X.Some_Component := X.Some_Component + 1; -- X.Lock is released automatically end Some_Operation; end Another_Pkg; Here is how you could add a "lock" to any type with a generic: with Synch_Pkg; generic type Contents_Type is limited private; -- Type to be inside the locked box package Locking_Pkg is type Locked_Box is limited private; -- Type representing the locked box generic with procedure Operation(Contents : in out Contents_Type); procedure Locking_Operation(Box : in out Locked_Box); -- Instantiate this to produce a locking operation private type Locked_Box is record Contents : Contents_Type; Lock : Synch_Pkg.Lock; end record; end Locking_Pkg; package body Locking_Pkg is procedure Locking_Operation(Box : in out Locked_Box) is Handle : Synch_Pkg.Exclusive_Handle(Box.Lock'ACCESS); -- Box.Lock is now acquired begin Operation(Box.Contents); -- Box.Lock is released automatically end Locking_Operation; end Locking_Pkg; We could use a more complex lock if we wanted to, e.g. one that provided both exclusive read/write and shared read/only type access, with two different "Handle" types, one that got the exclusive lock when initialized, the other than got the shared lock when initialized. By using finalization to release the locks, we get automatic release on unhandled exceptions and abort/ATC. Unfortunately, these approaches have some drawbacks: a) They require that each locking operation include the declaration of the local "handle" object. The generic approach ensures that this is always done, but it is a bit clumsy. b) The locking is queued, rather than non-queued. c) There is no protection against priority inversion. d) Getting a shared lock still requires the Lock component to be read/write, so either the Lock would have to be pointed-to, or the object would have to be an IN OUT parameter even when the operation was a read-only operation. e) One locking operation cannot call another such operation, because deadlock would occur when the second operation tried to initialize the exclusive handle. With the generic approach, there is presumably a full set of non-locking operations that operate on the "contents" type, so this is less of a problem. Arguably a more natural approach is to simply make the type a tagged protected type (or the moral equivalent), and then add more protected operations and components as part of type extension. A possible syntax for this would be (upper case = bold): PROTECTED TYPE identifier [discriminant_part] IS [TAGGED | NEW subtype_indication WITH] {protected_operation_declaration} PRIVATE {protected_operation_declaration} RECORD component_list END [protected_simple_name]; We have allowed TAGGED or "NEW subtype_indication WITH" following the "IS." In the case of "NEW subtype_indication WITH" the subtype indication would have to specify a tagged protected type as the parent. By so doing, a single non-queued lock would be used for the components and operations inherited from the parent, as well as the new components and operations defined in the derived type. This seems like a relatively straightforward approach. There are nevertheless some subtle semantic and implemention issues associated with overriding existing entries, or even just adding new ones. The general idea would be that for a tagged protected type, at the end of a protected operation, one would "redispatch" to reevaluate all of the entry barriers. One would *not* be able to optimize barrier evaluation, since in general one operation might be overridden while another might not be. Similarly, a "requeue" would always be a redispatch, meaning that the requeuer could not build in any knowledge of the target entry's barrier. (Note: By "redispatch" we mean that one goes back to the "original" tag of the object, even if some intermediate conversions to ancestor types have occurred implicitly or explicitly as part of calling inherited operations.) Even the number of entries wouldn't be knowable statically when generating the code for a protected operation, because it might be inherited into a type that has more entries. The storage allocation problem for a protected type might also be a little trickier, if a bit-vector approach is used for entry barriers, or an array of entries is used, since one would be adding potentially more components as well as more entries. One possible approach to solving some of these problems is to regenerate the code for *all* of the protected operations, even those that are inherited "as is." However, this does not necessarily solve the problem, since we probably want a redispatch for entry-queue servicing to occur at the end of a protected operation even if it is reached by explicit conversion to a parent type. Here is an example of a possible tagged protected type with an extension, to illustrate some of the conversion and "redispatching" issues. protected type PT1 is tagged -- A simple exclusive lock procedure Release; entry Acquire; private record Locked : Boolean := False; end PT1; protected body PT1 is procedure Release is begin Locked := False; end Release; entry Acquire when not Locked is begin Locked := True; end Acquire; end PT1; protected type PT2 is new PT1 with -- Add operations to support shared locks procedure Release_Shared; entry Acquire_Shared; entry Acquire; -- Override -- inherit Release as is. private record Reader_Count : Natural := 0; end PT2; protected body PT2 is procedure Release_Shared is begin Reader_Count := Reader_Count - 1; end Release_Shared; entry Acquire_Shared when not Locked is begin Reader_Count := Reader_Count + 1; end Acquire_Shared; entry Acquire when not Locked and then Reader_Count = 0 is -- Obviously this is non-optimal; -- A single counter would be better, where < 0 means exclusive, -- and > 0 means shared. But this is an example, remember? begin Locked := True; end Acquire; end PT2; Suppose we have an instance of PT2, and we convert it to PT1 and call Release. We still want both entries of the object to be serviced, even though the operation was called after converting to a type that only had one entry. A more interesting question is what happens if we convert it to PT1 and call the entry Acquire. In this case, does it use the barrier expression and body from PT1.Acquire, or PT2.Acquire? It seems just too weird (and painful to implement if using a bit-vector approach to barrier expressions) to allow it to reach PT1.Acquire. Hence, we could consider the semantics of an entry call to be roughly, add the call to the appropriate queue, and then redispatch to service the queues. In other words, it wouldn't matter whether you converted a tagged protected object to some ancestor type, an entry call would end up the same place, namely the "true" entry based on the original tag of the object. This distinction between subprogram and entry operations is somewhat disconcerting, but from an implementation point of view, it tends to agree with the general approach of "directly" calling protected subprograms, while only indirectly calling entries via the RTS. Similarly, it jibes with the fact that the caller always executes their "own" protected subprograms, whereas entry body execution and barrier evaluation takes place somewhere in the "ether." Finally, it is consistent with calls between protected subprograms, since these bypass the locking completely, and can be totally statically bound, corresponding to calls between primitives of non-protected types. Entries may not call one another directly, and redispatching does seem appropriate for "requeue." We could "punt" on the issue and simply disallow overriding existing entries, but that will only lead the user to asking "why on earth did you put in that restriction?" And of course, for situations where one is just using mutual exclusion and no entries, there is no issue about which barriers to evaluate and which entry bodies to execute. Certainly, in the above example it would be natural to have class-wide operations on PT1'CLASS that call only Acquire and Release, but we certainly want such operations to get our overridden Acquire instead of the original one. All of the above issues seem relatively soluble. The question is whether the benefit of being able to naturally combine the OOP concepts and protected type concepts is sufficient to justify whatever added implementation (and conceptual) complexity is involved. Or, alternatively, is it cheaper to just implement tagged protected types than to take flak about having no good support for concurrent object oriented programming. Note that if barriers were restricted to being boolean variables, then we would have to override protected procedures to make them update additional boolean variables, but we wouldn't have to update entries just to change their barrier. Interesting tradeoff, and probably one that is better left to the designer (since they can choose to use boolean variables instead of expressions if they so desire). By the way, with a "PT2" kind of lock (readers and writers) there is a classic fairness issue that can be partially resolved by disallowing new readers if there are too many writers stacked up. This implies using Acquire'COUNT in the barrier for Acquire_Shared (and perhaps vice-versa). This is a case where it is more difficult to solve this problem without 'COUNT in a barrier, since the writers may all stack up between calls to Acquire_Shared. We welcome comments on these issues! -Tuck ------ Output from automsg.perl ------ Mail received from stt *** Key LSN-1030 given to topic 'LSN on Extensible protected types' ----------- End of output ------------ /* End of text from spock:ada9x.mail */