[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: Dynamic Priority
What about this?
Design (index free?)
~~~~~~~~~~~~~~~~~~~~
The expression {P0} > {P2,P3} > {P1,P4,P5} can be drawn as a undirected
graph with {P0}, {P2, P3} and {P1, P4, P5} as nodes connected by arcs that
are labelled by ">".
This graph can also be represented by {P0} > ({P2} = {P3}) > ({P1} = {P4} =
{P5}) which can be drawn as an undirected graph with {P1},..,{P5} as nodes
connected by arcs that are labelled by ">" or "=".
This way we could extend our existing data-flow design with priority
relation arcs. I belief that indexes at this level of the conceptual design
can (should) be hidden and can (should) being added later at implementation
level (maybe by the compiler or scheduler). One press on the button and the
PAR will be generated with indexes we do not want to know ... or do we want
to know the indexes?
For example, in {P0} > {P2,P3} > {P1,P4,P5} the indexes
[10,1267,1267,100034,100034,100034] would be valid. I guess the indexes must
be in range of the number of processes (here [0..n-1] with n = 6).
General Ordered Relation
~~~~~~~~~~~~~~~~~~~~~~~~
A priority is a precedence relation between processes in terms of greater
than ">" or equal to "=". The relations ">" or "=" between processes can be
added to the design by some reasons of timing constraints or precedence
constraints. As long as the relation is valid I do not want to know the
indexes. I belief, this is conceptual and that makes reasoning about
precedence relations (or priorities) much simpler.
The compiler or scheduler can do the hard work.
Say, pri(Pi) is the priority of Pi and index(Pi) is the index of Pi in the
PAR construct.
pri(P1) > pri(P2) means that P1 has a higher priority as P2.
Or pri(P1) > pri(P3) is equal to index(P1) < index(P2), which means the
index of P1 is lower than the index of P2.
index(P1) < index(P2) is equal to index(P1) = index(P2) - x, where x > 0 (x
does not always have to be 1). We could generate our priority indexes by
some algorithm. The indexes can be anything that fits the scheduler
implementation as long as the priority relations maintain valid.
PAR and PRI PAR
~~~~~~~~~~~~~~~
Let P1 and P2 be concurrent processes, then
pri(P1) > pri(P2) is
PRI PAR
P1
P2
pri(P1) = pri(P2) is
PAR
P1
P2
pri(P1) > pri(pri(P2) = pri(p3)) is the nested composition
PRI PAR
P1
PAR
P2
P3
The distinct compositions PRI PAR and PAR are very useful in this matter.
However, this may also correspond to
PAR (CHAN OF [x, x+y, x+y]) with x >= 0 and y > 0.
P1
P2
P3
where we need to know x and y.
With our scheduler approach we create a new dispatcher process for each PRI
PAR constructs. The dispatcher manages the ready queue and running queue.
Processes in the PRI PAR construct will be assigned to different ready
queues represented by an 8-bits word. Processes in a PAR construct will be
assigned to the same ready queue of the parent dispatcher. It's simple, fast
and static. Again, the distinct compositions PRI PAR and PAR are very useful
in this matter.
Gerald.
-----Original Message-----
From: Adrian Lawrence
[mailto:adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
Sent: maandag 26 april 1999 21:26
To: occam-com@xxxxxxxxx
Subject: Dynamic Priority
Dynamic Priority
~~~~~~~~~~~~~~~~
Starting from existing occam, we may as well leave PAR as it is.
Although HARD PAR or SOFT PAR or TRANSPARENT PAR or PAR(HARD) may be
needed.
But we can have an optional CHAN parameter in PRI PAR: I think that this
is the more accurate representation.
PRI PAR(CHAN OF something priority)
P0
P1
...
PN
Specifying the POR (Partial Order Relation)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The syntax gives a reference order. My original idea of sending the ordered
image of a bijection as a table of indices is simple, and I hope lightweight
for the sender to prepare, and for the implementation to utilize. It is
pretty much a preprepared lookup table of offsets.
Gerald raises the idea of a more general order relation. Do we need this?
Will it ever be needed? Anyway, one more general possibility is
to have a list of ordered sets:
S0 > S! > S2....
For example {P0} > {P2,P3} > {P1,P4,P5} would correspond to
PRI PAR
P0
PAR
P2
P3
PAR
P1
P4
P5 .
Since each set Si could be represented by a bit list, this could be sent
as bit arrays (packed into INTs I guess, with a restriction of bits_in_word,
in a given set). Of course, if we ever have real BIT arrays as I suggested
a
few years ago, this is another application. :-)
So above would be specified as 00000001,00001100,00110010 in 8-bit words.
No doubt there are many ways to do this, and perhaps we could define
specific
protocols to encode them.
But do we need any of this?
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