From: flynn@ACF2.NYU.EDU (Susan Flynn)
Subject: Synchronization Points
Date: 6 Feb 88 22:08:44 GMT [thread overview]
Message-ID: <8802062208.AA08874@acf2.NYU.EDU> (raw)
Recently there has been some discussion on the net about
synchronization points for delays (the points at which a delay
must have expired) and preemptive scheduling (the points at which
a newly executable task must preempt an executing task of lower
priority). (Note that delay synchronization points are not by
themselves sufficient for defining scheduling synchronization points:
in a multiprocessor environment a task running on processor A could
create and activate a task that is of higher priority than a task
running on processor B.)
The LRM says that a delay must cause a task to be suspended for
at least as long as its duration (which seems reasonable). It might
seem desirable to have delay synchronization points defined precisely
by the language, e.g. "a delay must expire after at least the duration
but before <some condition>". The LRM also requires preemptive
scheduling. Again it might seem desirable to have scheduling
synchronization points precisely defined.
There are two types of synchronization points already defined
in the LRM: those pertaining to aborts 9.10 (6) and those pertaining
to shared variables 9.11 (2). Neither of these types of synchronization
points (as far as I can tell) affect when a delay must expire or when
a task must be scheduled (although, they are obvious candidates for
rescheduling a processor).
The LRM states that aborts are to be used only in extremely
severe situations; allowing the completion of an abort to be delayed
until an abort synchronization point appears to be an attempt to reduce
the cost of including abort statements in the language for typical Ada
programs (which will not use aborts). Similarly the LRM states that shared
variables are not meant to be the usual means for tasks to communicate;
allowing local copies of shared variables (which are not declared in a
pragma shared) to be kept between shared variable synchronization points
appears to be an attempt to reduce the cost of including shared variables
in the language for typical Ada programs (which will not use shared
variables).
Why were abort and shared variable synchronization points defined
and scheduling and delay synchronization points not defined? Perhaps
to discourage "quick and dirty" implementations of delays and preemptive
scheduling -- they are integral to real-time programming, whereas aborts
and shared variables are rather obscure language features. More importantly,
were such points defined I do not believe that they could be tested -- in
both cases a task is not currently running (it is either suspended or not
scheduled), and therefore, cannot itself participate in a synchronization
point.
Indeed, what can be meaningfully said about the maximum a task
can be suspended on all architectures? Consider the following potential
requirements:
1) A delay must expire before the next <some type of statement>. With
varying speed CPUs how do I know which <some type of statement> this will
be? (Remember the task that is executing the delay is suspended.)
2) A delay of X seconds must be expired by N*X seconds (where N is not
implementation defined), then very slow CPUs or distributed machines might
never pass validation by virtue of never being able achieve this bound.
(If N were implementation dependent, then it could be made so large as to
be effectively infinite.)
3) A delay of X seconds must expire before the next N statements are
executed (where N is not implementation defined). The comments made
about requirement 2) also apply here. Moreover, if I have a CPU that
executes 2*N statements in X seconds, must I slow down my CPU?
As with delays there seems to be very little that can be said about
when a task becomes executable (or schedulable) in relation to an already
running task. (Note that the task parent that creates a task child will
block awaiting child's activation, so that if child is of higher priority
it will usurp parent's CPU whether a run-until-blocked or a preemptive
scheduling policy is employed.)
In the end, I suspect, that it will be market forces that
dictate these decisions. If I am writing embedded systems software
and I need real-time response, and compiler XXX chooses to never expire
delays and uses a run-until-blocked scheduler, then I will not buy
compiler XXX. (What compiler you do think Simon Tuffs will buy to do
his real-time programming?) Alternatively, if I am writing scientific
code for a distributed machine, then I may not want to incur the
overhead of a preemptive scheduler in a multiprocessor environment
and buy compiler XXX.
Susan Flynn
flynn@acf2.nyu.edu
p.s. Our notes program has been acting up. As far as I can this
never made it off my machine. I apologize if it's a duplicate.
reply other threads:[~1988-02-06 22:08 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox