From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,8eff44ec1bcf8433 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-10-18 13:25:01 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!sn-xit-03!supernews.com!194.159.255.21.MISMATCH!dispose.news.demon.net!news.demon.co.uk!demon!pogner.demon.co.uk!zap!not-for-mail From: Simon Wright Newsgroups: comp.lang.ada Subject: Re: Container reqs Date: 18 Oct 2001 20:42:55 +0100 Organization: Pushface Message-ID: References: <9qctpn$lil$1@news.huji.ac.il> <3BCC01B1.18C18C98@free.fr> <3BCC6CB7.20BAA30D@boeing.com> <3BCD2EC3.3B3C4498@free.fr> NNTP-Posting-Host: localhost X-NNTP-Posting-Host: pogner.demon.co.uk:158.152.70.98 X-Trace: news.demon.co.uk 1003436663 nnrp-10:5512 NO-IDENT pogner.demon.co.uk:158.152.70.98 X-Complaints-To: abuse@demon.net NNTP-Posting-Date: 18 Oct 2001 19:42:56 GMT X-Newsreader: Gnus v5.7/Emacs 20.7 Xref: archiver1.google.com comp.lang.ada:14915 Date: 2001-10-18T19:42:56+00:00 List-Id: Jean-Marc Bourguet writes: > I was probably not clear enough. Tasks savety is not something binary, > it's something for which there is at least five levels. > > 0) the whole library can't be used by two tasks without explicit > synchronisation because there is use of some features (global variables, > COW datastructure build without considering tasking, ...) which make > it totally unfit for that use. > > 1) you can work savely on different objects in different tasks but not > access the same object in different tasks without synchronisation. > > 2) you can savely have read access to one object from different tasks > but modifying accesses must be protected explicitly from other accesses. > > 3) there is a limited set of modifying accesses which can be issued > simultaneously from different tasks. > > 4) whatever you do -- trying to modify the datastructure simultaneously > via iterators from different tasks -- is save. > > From my experience, > * level 4 is useless because you still need synchronisation > for other reasons when its whole generality is needed. Achieving it > has a major performance impact (every operation has to be > protected). > > * level 3 is usefull but the set of modifying access which make sense > depend very much on the application. Your example is probably the > only widely applicable one. Achieving this level has a important > performance impact. > > * level 2 can be achieved with a small performance impact: there is no > need for explicit synchronisation, one need simply to pay attention > to the datastructure used and the way it is accessed. > > I think that one should aim for level 2 because: > - this simplify the library (no need to have tasks save and tasks > unsave > version) > - aiming level 3 whould imply major discussion about the set of > operations > needed with the risks of compromising to level 4. > - I whould probably still encapsulate the ADT in an other > type/package which > export only the operations needed for the application with names > related > to the application. The BCs' design has two sorts of Container, called monolithic and polylithic. The monolithic containers (eg, Queue) are self-contained memory structures, and if I say Queue_2 := Queue_1; I get a deep copy. Polylithic (Grady's word!) containers are implemented as in-memory structures with multiple viewports, for want of a better word, so that if I say List_2 := List_1; I still have only one List; if I say Tail (List_2); then List_2 points one element along from List_1. Very complicated, and the reason I recommend people not to use BC Lists unless they really really need that functionality. The polylithic containers (Lists, Graphs, Binary and Multiway Trees) can't be protected, so they're at your Level 1. The monolithic containers can be protected using BC.Containers.Guarded: generic type Base_Container is new BC.Containers.Container with private; type Semaphore is new BC.Support.Synchronization.Semaphore_Base with private; package BC.Containers.Guarded is which basically adds Seize and Release operations, so that the user has control over where synchronization is applied. This can be applied as an add-in to any style of container (bounded or unbounded with storage allocator). I supply two sorts of Semaphore: -- A Semaphore is like a standard POSIX mutex. type Semaphore is new Semaphore_Base with private; -- A Recursive_Semaphore is like a POSIX recursive mutex; once -- Seized by a task, that task can Seize again; other tasks are -- blocked until the owning task has Released the semaphore as -- many times as it Seized it. type Recursive_Semaphore is new Semaphore_Base with private; If your task happens to die while holding the Semaphore, tough! The other sort of concurrency control, Synchronized, requires a lot more work since one has to wrap the protocol of the class concerned. So far I've done it for Queues and Maps. For Queues, generic type Queue_Base is new Abstract_Queue with private; type Monitor is new BC.Support.Synchronization.Monitor_Base with private; package BC.Containers.Queues.Synchronized is and I supply two sorts of Monitor: -- Single_Monitors allow one task at a time to have access, be it -- for reading or writing. type Single_Monitor is new Monitor_Base with private; -- Multiple_Monitors allow multiple readers; however, when a -- writer owns the monitor it has exclusive access. type Multiple_Monitor is new Monitor_Base with private; Again, this can wrap any style of memory management. (By the way, I should add that this generic doesn't work with ObjectAda 7.2 (free download). I have no idea whether it works with Apex or AdaMulti or .., no complaints received). The normal Queue protocol includes procedure Pop_Value (Q : in out Queue; Elem : out Item); -- Remove and return the item from the front of the queue. which is atomic (and blocking) for the Synchronized queue; I see that for the unsynchronized Queue a call of Pop_Value on an empty queue will in fact raise an exception (but what else can I do?!) What really bugs me is how to provide a multiple reader/single writer Monitor for use with iterators. I fully agree with Jean-Marc that containers are for implementing things, not for inheriting from! -S