[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-
With my latest suggestion of
c ? priority
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
c ? priority
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
> - 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.
> 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)
> 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.
c ? pri
the channel interface ensures exclusive write. And it can be done when the
processes are active: highly desirable?
> 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
Thanks Gerald. That is very helpful. It gives me much more confidence that
C ? pri
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
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
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