[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Dynamic composition constructs

Gerald Hilderink writes:

> A DYN PAR could be a PAR or a PRI PAR on which the parent process can add,
> remove or insert a process at run-time before running the DYN PAR.

Not with static memory allocation surely? Unless we bound the number of 
processes in some strictly checkable way. I doubt that we could do that 
without building a whole new dynamic version of occam in which
we could also pass processes down channels and much more. Pi-(calculus)-in-
the sky?


With my latest suggestion of
PRI PAR
  PRIORITY
    c ? priority
  P0
  P1
  ...
there is no notion of parent process. The channel "c" might even be connected
to one of the [P0,P1,...,PN]. 

I quite like the idea that this should be
PAR
  PRIORITY 
    c ? priority
  P0
  P1
  ...

Maybe PRIORITY should just be PRI to keep in the tradition of 3 letters, and
avoid worrying about nouns/verbs as mentioned by Oyvind. Although a noun seems
ok to me simply as a flag...


> In CTJ the PAR (Parallel), PRI PAR (PriParallel), SEQ (Sequential), ALT
> (Alternative-Guard) and PRI ALT (PriAlternative-Guard) constructs are all
> dynamic constructs. 

That has to be so in a (uncheckable?) dynamic language like Java? :-)


> Without discussing the Java implementation I will try to
> illustrate the idea by the following examples.
> 
> One can add, remove or insert processes by special methods (or by special
> operators):

> - adding process P4:   (P1 || P2 || P3).add(P4)          = (P1 || P2 || P3
> || P4)

> - removing process P2: (P1 || P2 || P3 || P4).remove(P2) = (P1 || P3 || P4)
>   or using index:      (P1 || P2 || P3 || P4).remove(1)  = (P1 || P3 || P4)
> - inserting process P2 before P4 at index 2 (index = [0..2]): (P1 || P3 ||
> P4).insert(P2,2) = (P1 || P3 || P2 || P4)

That's nice. I should have looked at what you have done in CTJ. But we can't
do that in occam for several obvious reasons. 

>
> Example:
> ~~~~~~~~

> For example PROCESS is a process,
> 
> PROCESS =	(P1 |<| P2 |<| P3 |<| P4)
> EXAMPLE =	(PROCESS.remove(P1) ; PROCESS.add(P1) ; PROCESS.remove(P3) ;
> PROCESS.insert(P3,0) ; PROCESS)	(*)
> 
> the result will be shown in steps,
> 
> PROCESS = 	(P2 |<| P3 |<| P4)            (step 1)
> PROCESS = 	(P2 |<| P3 |<| P4 |<| P1)     (step 2)
> PROCESS = 	(P2 |<| P4 |<| P1)            (step 3)
> PROCESS = 	(P3 |<| P2 |<| P4 |<| P1)     (step 4, final result)


> 
> Moving processes is changing priorities:
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Processes could be moved from one location to the other (from a to b) by the
> move(a,b) method.
> 
> PROCESS.move(a,b) =	(p = PROCESS.at(a) ; PROCESS.remove(p) ;
> PROCESS.insert(p, b))
> with a > b.
> 
> PROCESS.move(a,b) =	(p = PROCESS.at(b) ; PROCESS.remove(p) ;
> PROCESS.insert(p, a))
> with a < b.
> 
> PROCESS.move(a,b) =	SKIP
> with a = b.
> 
> The method PROCESS.at(i) returns the process at index i in PROCESS. The
> indexes a and b are positive integer value ([0..>).

 
> Problem when executing these special methods in parallel:
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Executing these special methods in parallel may result in illegal results,
> for example:
> 
> PROCESS =	(P1 |<| P2 |<| P3 |<| P4)
> EXAMPLE =	((PROCESS.insert(P5,1) || PROCESS.insert(P6,1)) ; PROCESS)	(**)
> the result will be
> PROCESS =	(P1 |<| P5 |<| P6 |<| P2 |<| P3 |<| P4)
> or
> PROCESS =	(P1 |<| P6 |<| P5 |<| P2 |<| P3 |<| P4)

This is just the usual concurrent write non-determinism, isn't it?
 
> Solution for Java
> ~~~~~~~~~~~~~~~~~
> The imposed restriction is that only the parent process may invoke these
> methods on PROCESS in sequence where construct (*) is valid and construct
> (**) is invalid.
> 
> The passive process interface for a Java process is
> void run()
> void add(process)
> void remove(process)
> void insert(process, index)
> void move(index_from, index_to)

 
> The parent process can never add, remove, insert or move a process when
> PROCESS is running. The action (PROCESS.add(Px) || PROCESS) is not allowed
> because when PROCESS is running then the parent process is blocked. Other
> processes are *not* allowed to have a reference to PROCESS. By following
> this simple rule makes this technique in Java secure.

In PAR
     PRI
       c ? pri
     P0
     ... 

the channel interface ensures exclusive write. And it can be done when the
processes are active: highly desirable? 
 
> General
> ~~~~~~~
> This technique also applies for the other constructs:
> - PAR construct:     (P1 || P2 || P3).add(P4)   = (P1 || P2 || P3 || P4)
> - SEQ construct:     (P1 ; P2 ; P3).add(P4)     = (P1 ; P2 ; P3 ; P4)
> - ALT construct:     (P1 [] P2 [] P3).add(P4)   = (P1 [] P2 [] P3 [] P4)
> - PRI ALT construct: (P1 [<] P2 [<] P3).add(P4) = (P1 [<] P2 [<] P3 [<] P4)
> 
> PROCESS.insert(p) on a PAR or ALT construct is equal to PROCESS.add(p).
> 
> A nice result of this technique is that processes itself have no priorities.
> One simply manipulates priorities by changing the places of processes in the
> array of processes (referred by their indexes). Indexes do not necessary
> represent the priority number of processes on composition constructs in
> general.

Thanks Gerald. That is very helpful. It gives me much more confidence that
something like

PAR
  PRI
    C ? pri
  P0
  P1
  ... 

is the right approach for occam. 

What experiences do you have with applying your primitives for real time
systems. I know that it is early days, but have any problems shown up
in applications? Do you have any robots running around your labs using these
primitives?

I don't really agree that in your system priorities are not attached to
processes just because they can be moved around a list. But since I think that
we all understand what is happening there is no point is silly discussion
about terminology.

Thanks again.

Adrian
-- 
A E Lawrence, MA., DPhil.  	adrian.lawrence@xxxxxxxxxxxxxx
MicroProcessor Unit, 13, Banbury Road, Oxford. OX2 6NN. UK.                
Voice: (+44)-1865-273274,  Fax: (+44)-1865-273275