Re: Container reqs

[Simon Wright <simon@pushface.org>]

Jean-Marc Bourguet <jbourguet@free.fr> 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