Re: Ada delay

Re: Ada delay

[cis.ohio-state.edu!news.sei.cmu.edu!firth]

In article <Buq4Mr.D7H@math.uwaterloo.ca> amichail@plg.uwaterloo.ca (Amir Micha
il) writes:

>How is the Ada delay statement implemented?  I suppose it uses a hardware 
>timer coupled with a clock server, but this would mean that the time
>taken for a delay is unbounded (since we have to search an ordered list
>of tasks).

Either a list is ordered or you have to search it, but not both, surely,
else somebody has it in the wrong order.

The usual way is to keep a list of delayed tasks ordered by wake-up time.
You organise the list so that inserting a new task is efficient, and then
set the timer to the wake-up time of the first task.  When the timer goes
off, you pull the first task off the list and stuff it in the ready queue,
reset the timer for the next task, and exit to the scheduler.

For Ada, you need three efficient primitives

. insert in correct place in ordered list

. remove first in list

. remove named task from list (for conditional entry and accept)

Not hard.

Re: Ada delay

[Jorge Luis Diaz-Herrera]

In article <1992Sep17.142643.21378@sei.cmu.edu>, firth@sei.cmu.edu (Robert Firt
h) writes:
|> In article <Buq4Mr.D7H@math.uwaterloo.ca> amichail@plg.uwaterloo.ca (Amir Mi
chail) writes:
|> 
|> >How is the Ada delay statement implemented?  I suppose it uses a hardware 
|> >timer coupled with a clock server, but this would mean that the time
|> >taken for a delay is unbounded (since we have to search an ordered list
|> >of tasks).
|> 
|> Either a list is ordered or you have to search it, but not both, surely,
|> else somebody has it in the wrong order.
|> ...

We implemented (see ref.) simple delays using an ARRAY [1..MaxTasks] of Time.
The task name serves as the array index; the array entry is the task release
time (release time = current time + delaytime.) The array is searched at every
context switch and all tasks whose release time is less than or equal to the
current time are inserted in the corresponding ready queue (priority).  This
is consistent with the LRM which requires delays to be "at least" the
duration specified. Linear search is used since the number of delayed tasks
will probably be small.  In addition to timing through tick counting, using
the timer interrupt trapped, a variation was developed using calls to the
system clock.  This technique while inherently more efficient, can be highly
inaccurate since in our RTK time is updated only upon entry to the dispatcher.

For more information refer to: "ARTK-M2:A Kernel for Ada Tasking Requirements:
an implementation and an Automatic Generator" J.L.Diaz-Herrera et al,
Software Practice and Experience, vol. 22(4) 317-348 (April 1992).

Re: Ada delay

[Bob Kitzberger]

firth@sei.cmu.edu (Robert Firth) writes:

>In article <Buq4Mr.D7H@math.uwaterloo.ca> amichail@plg.uwaterloo.ca (Amir Mich
ail) writes:

>For Ada, you need three efficient primitives
>
>. insert in correct place in ordered list
>
>. remove first in list
>
>. remove named task from list (for conditional entry and accept)
>
>Not hard.

The algorithm is easy -- the 'hard' part is implementing the lower-level
grunge  (myriad target boards, with myriad hardware timers [none worth the
silicon they're made of], mapping to type Duration without loss of
accuracy drift, etc., and making it easy to adapt from target to target 
system).  All of these are important when you want to implement
high-resolution periodic scheduling operations like Delay_Until and periodic
soft interrupts, which developers find out are necessary once they butt 
up against the delay statement's limitations.

Give me a 64-bit monotonic timer, incrementing once per CPU cycle, 
atomic CPU instructions to read the clock and set a single 64-bit
wake-up-time, and a cold Watney's and I'd be a happy Ada delay
implementor.  

	.Bob.
----------------
Bob Kitzberger          VisiCom Laboratories, Inc.
rlk@visicom.com         10052 Mesa Ridge Court, San Diego CA 92121 USA
                        +1 619 457 2111    FAX +1 619 457 0888

Re: Ada delay

[mcsun!uknet!yorkohm!minster!ken]

Amir Michail (amichail@plg.uwaterloo.ca) wrote:
: How is the Ada delay statement implemented?  I suppose it uses a hardware 
: timer coupled with a clock server, but this would mean that the time
: taken for a delay is unbounded (since we have to search an ordered list
: of tasks).  If this is true, then how can one possibly use it for
: realtime scheduling of periodic tasks??

Usually there is a list of tasks waiting on a delay queue, which is
regularly polled by a clock timer (1ms interval, say). Every time this
interrupts the queue is examined for tasks which should now be placed in the
run queue. The time delay isn't unbounded, since there is a maximum length
of the queue. Furthermore, since tasks are periodic they will only need to
be removed from the delay queue once per period. Knowing the period of each
task gives the maximum overheads in a given time interval, and hence a bound
on the overheads.

There are other more sophisticated approaches.

--
Ken Tindell             Internet      : ken@minster.york.ac.uk
Computer Science Dept., Local FTP site: minster.york.ac.uk
York University,        Tel.          : +44-904-433244         
YO1 5DD, UK             Fax.          : +44-904-432708

Re: Ada delay

[Guangxing Li]

_______________________
Amir Michail (amichail@plg.uwaterloo.ca) wrote:
: How is the Ada delay statement implemented?  I suppose it uses a hardware 
: timer coupled with a clock server, but this would mean that the time
: taken for a delay is unbounded (since we have to search an ordered list
: of tasks).  If this is true, then how can one possibly use it for
: realtime scheduling of periodic tasks??

By dynamically updating the delay value, people can still have accurate
periodic tasks, even through the delay statement is not
accurate. 

For example 
      start_time = now;
      for(;;) {
      load();
      next_period_start = start_time + period;
      start_time = next_period_start;
      delay = next_period_start - now;
      Ada_delay(delay);
      }
	  

Re: Ada delay

[Gary Funck]

In article <Buq4Mr.D7H@math.uwaterloo.ca> amichail@plg.uwaterloo.ca (Amir Micha
il) writes:
>How is the Ada delay statement implemented?  I suppose it uses a hardware 
>timer coupled with a clock server, but this would mean that the time
>taken for a delay is unbounded (since we have to search an ordered list
>of tasks).  If this is true, then how can one possibly use it for
>realtime scheduling of periodic tasks??
>

Amir,

Your note brings up a few issues:

- "unbounded" may not be quite correct.  Searching a linear list and
making a task ready to run is linear with respect to the number of
tasks in the delay queue.

- Some implementations use either a timer that is periodic (interrupts
at fixed time intervals) or an "interval timer" that whose time
delta is reprogrammed to the delta of the next task waiting in
the delay queue.  The periodic timer generally has less skew, but
places a consistent and sometimes heavy load on the system, if the
time granularity is small.  Overheads to due to processinmg periodic timer
interrupts can be in the neighborhood of 10-15%, if the time period
is in the neighborhood of 1 KHz, for example.

- The Ada language specifies that a task delay must be *no less than*
than the requested time delay.  An implementation can meet the
letter of law, by processing delay requests, only at language
defined preemption points.  Most "modern" Ada runtimes support
task preemption at arbitrary ppints in the execution of a task;
some older ones only checked when an Ada program performed a
tasking operation, leading to tryly unbounded delays.

- In practice, applications that require tight time synchronization
attach an Ada interrupt entry to an interrupt tied to a periodic
timer, sometimes called the "frame generator".  If the context
switch from interrupt level to task level takes too long, some
applications do the bulk of the periodic processing at interrupt
level, defining an interrupt service routine.  The facilities for
handling events directly at interrupt level are vendor specific.
For example, Verdix has something called "passive interrupt tasks" that give
you the syntax of tasks, and most of the efficiency of interrupt
service routines.  

- Ada 9X includes something called the "real-time annex" to the language
definition that is directed at solving some of the known problems
with using Ada in a real-time environment.
-- 
| Gary Funck  		    gary@intrepid.com  [uunet!uupsi!intrepid!gary]
| Intrepid Technology Inc., Mountain View CA (415) 964-8135
--

Re: Ada delay

[H.Shrikumar{shri@ncst.in}]

In article <1992Sep19.175645.10076@intrepid.com> 
  gary@intrepid.com (Gary Funck) writes:
>For example, Verdix has something called "passive interrupt tasks" that give
>you the syntax of tasks, and most of the efficiency of interrupt
>service routines.  

COuld you post a small description of what this looks like, please ?
SOunds interesting (and similar to something I have).


-- shrikumar ( shri@legato.cs.umass.edu, shri@iucaa.ernet.in )

Re: Ada delay

[John Goodenough]

In article <1992Sep19.175645.10076@intrepid.com>, gary@intrepid.com (Gary Funck
) writes:

|> - The Ada language specifies that a task delay must be *no less than*
|> than the requested time delay.  An implementation can meet the
|> letter of law, by processing delay requests, only at language
|> defined preemption points.  Most "modern" Ada runtimes support
|> task preemption at arbitrary ppints in the execution of a task;
|> some older ones only checked when an Ada program performed a
|> tasking operation, leading to tryly unbounded delays.

The "letter of the law" reads slightly differently these days.  AI-00032,
approved in March 1987, says:

	If an implementation supports more than one priority level, or
	interrupts, then it must also support a preemptive scheduling policy.

In particular, the AI goes on to make clear that if a task is executing when a
task with a higher priority becomes executable because a delay has expired,
execution of the lower priority task must cease immediately so execution of
the higher priority task can continue.  The AI references 9.8(4) and says:

    Expiration of a delay means a task is eligible for execution.  If an
    implementation determines that a delay has expired for a high priority
    task, then that task must be scheduled for execution.  If the physical
    processor and other processing resources needed to execute the higher
    priority task are currently being used by a task of lower priority,
    execution of the lower priority task must be suspended.

    If preemptive scheduling is not feasible in a particular implementation,
    then the implementation should not provide multiple priority levels (see
    AI-00045) or support interrupts.

    (Note: the phrase "could sensibly be executed" [in 9.8(4)] refers to
    situations in which the high priority task can actually make use of the
    processor and other resources being used by the lower priority task.  In
    some distributed processing situations, a high priority task may not be
    able to execute on some processors.  Preemption is only required for
    processing resources the high priority task can use.)

John B. Goodenough					Goodenough@sei.cmu.edu
Software Engineering Institute				412-268-6391