NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/lang/ada/2376

Internet Message Format | 1992-08-17 | 10.2 KB

Path: sparky!uunet!sun-barr!ames!agate!ucbvax!ROO.FIT.EDU!SAHARBAUGH
From: [e-mail]
Newsgroups: comp.lang.ada
Subject: zzz K1 explanation
Message-ID: <[e-mail]>
Date: 17 Aug 92 12:20:00 GMT
Sender: [e-mail]
Distribution: world
Organization: The Internet
Lines: 279

K1 - A alternate Ada task scheduler and supporting
tools for hard real-time embedded systems

K1 provides hard deadline Ada task scheduling
(periodic and aperiodic), task performance
monitoring, task overrun detection and supporting
CASE tools.

Features:

An Ada Task can switch itself to being a K1 Task

Periodic K1 Tasks are Scheduled on a Frame/Subframe
Timeline

K1 Task Scheduling can be dynamically altered

K1 Task Timing Performance is measured and reported
to your Ada program

K1 Task Timing Overrun is detected and reported to
your Ada program

K1 Task Priority can be dynamically altered

Precision Delay is provided for use in K1 tasks

Graphical Workstation Tools are provided for
convenience in configuring the K1 Real-Time
Executive and individual K1 Tasks


The K1 Real-Time Executive:

The K1 Real-Time Executive is an integrated part of
the Ada Runtime Environment.  K1 scheduling is
implemented using a frame/subframe model of time.
Periodic K1 tasks are scheduled to run in one,
several or all subframes.  The scheduling of
periodic K1 tasks can be done initially by the
designer, using the Task Generation Tool on the
host workstation.  The scheduling may be altered
dynamically within task bodies.

The K1 Real-Time executive consists of a Scheduler,
a Dispatcher and a Time Overrun Detector.  The
Scheduler builds a K1 task schedule according to
data passed when an Ada task starts as a K1 Task.

The Dispatcher allocates the CPU resource on a
priority basis.  Dispatching occurs at the
beginning of a subframe or when a K1 task
voluntarily gives-up the CPU.  The highest priority
ready-to-run K1 task is dispatched next.  In case
there is more than one ready-to-run K1 task with
highest priority, then Periodic Tasks are chosen
before Aperiodic Tasks.  Periodic tasks which have
not yet had any execution time are chosen before
tasks that have executed previously.  Tasks of
equal rank and priority are chosen in the order
they are queued.

The Dispatcher records K1 task dispatching event
times for the application program to analyze and
act upon.  Performance statistics can be collected.
Misbehaving tasks can be detected before a hard
failure occurs.  In this way an application program
can detect and adjust resource usage of tasks which
overrun their timing allotment.  Task(s) can be
stopped and/or their K1 task priority(s) changed,
etc., as desired.

The Time Overrun Detector, part of the dispatcher,
determines when a task does not complete execution
in its specified number of subframes.  If an
overrun is detected an error routine in the
application program is called.   The error routine
can take corrective action such as stopping a
task(s), changing task(s) priority, etc.

A static Ada task is one declared at compile time.
Any static Ada task may call the runtime to be
scheduled as a K1 task.  The task passes the
following information with the call:

- Task ID and K1 Priority
- Periodic or Aperiodic Scheduling
- If Periodic, which subframe(s) to be scheduled in
- Number of subframes allowed for completion

After scheduling itself, the K1 task is controlled
by the K1 runtime executive until it calls the
runtime to be canceled as a K1 task.  After
canceling itself as a K1 task, the task reverts to
being a conventional Ada task.  The task can
schedule itself as a K1 task and cancel as often as
desired.


Relationship of Conventional Ada Tasks to K1 Tasks:

All K1 tasks begin as conventional Ada tasks.  They
call the K1 Runtime Executive to be scheduled as K1
tasks.  They can call the runtime again to revert
to being conventional Ada tasks.

K1 tasks have a higher priority than all
conventional Ada tasks.  The K1 Real-Time Executive
has a higher priority than the conventional
runtime.  Therefore the highest priority K1 task
has priority over everything except the K1 subframe
clock tick interrupt, the reset button interrupt
and hardware interrupts.

K1 tasks have Ada scope and visibility rules and
therefore data structures can be visible from both
K1 tasks and conventional Ada tasks.  A K1 task can
pass data through such structures.

A K1 Task's priority value determines how it is
dispatched and how the Time Overrun Detector
operates.

Aperiodic tasks can be given any initial or dynamic
priority value from 1 to Pmax.  When its priority
value is less than P2 the Time Overrun Detector
does not monitor the amount of execution time it
consumes.

Periodic tasks can be given any initial or dynamic
priority value from P2 to Pmax.  The Time Overrun
Detector always monitors periodic tasks.  If the
periodic task's priority is between P2 and P3 then
the number of subframes specified when the task was
instated is used by the Time Overrun Alarm.  If the
periodic task's priority is between P3 and Pmax
then the Time Overrun Detector checks to see that
the task completed execution in one subframe,
regardless of the number of subframes specified
when scheduled as a K1 task.

A K1 task's execution time behavior is classified
as Deterministic, Bounded Non-Deterministic or Non-
Deterministic.  A task in the priority range of 1
to P2 is treated as Non-Deterministic, no execution
timing checks are performed on it.  A task in the
priority range of P2 to P3 is treated as Bounded
Non-Deterministic, execution is expected to
complete in the number of subframes specified.  A
task in the priority range of P3 to Pmax is treated
as Deterministic, execution is expected to complete
in the subframe in which it started.

As a consequence of this behavior 1) a periodic
task cannot be non-deterministic because it could
try to start again before it had completed its
previous start, 2) the bound of a bounded non-
deterministic task must be less than the number of
subframes before it is scheduled to start again and
3) a deterministic task can be scheduled in one,
several or all subframes because it must finish in
the subframe in which it started.

To assist the real time designer, there are three
K1 tools,

  the runtime configuration tool (RCT),
  the task generation tool (TGT) and
  the task analysis tool (TAT).

The runtime configuration tool can be used to set
up the parameters of the frame/subframe model, set
priority limits, etc.

The  task generation tool can be used to configure
the timing behavior of each K1 task.  The TGT
produces a task template which includes appropriate
data structures and initial values to work with the
runtime.  The designer then uses an editor to
create the algorithm portion of each K1 task.

The runtime parameters are used in compiling the
runtime.  The K1 runtime is linked with the
conventional runtime, converted to s-records and
downloaded to the embedded computer.  The s-records
can be burned into EPROMs and plugged into the
embedded computer

The task analysis tool can be used to monitor
performance of a K1 task or a group of K1 tasks and
compare their performance against requirements.

The K1 Runtime Configuration Tool can be used by
the designer to set the scheduling parameters of
the K1 Real-Time Executive.

The K1 Runtime Configuration Tool allows the frame
rate, number of subframes and the Priority
boundaries P2, P3 and Pmax to be easily set using a
graphical user interface.  The number of frames per
second and the number of subframes per frame are
also chosen using a graphical user interface.  The
frame rate and possible rates for periodic tasks
are automatically shown.

The K1 Real-Time Executive parameter values are
static and cannot be changed dynamically.  If one
or more of these values are changed the Runtime
must be recompiled and re-downloaded.  If the
runtime is in ROM then a new ROM must be loaded and
plugged into the embedded computer.

The K1 Task Generation Tool allows the timing
specification of each K1 task to be easily selected
using a graphical user interface.  Using a mouse,
the designer selects options which determine the
taskUs timing description.

If the task is selected to be periodic then the
designer selects one of the available rates.  Note
that these available rates were determined when the
designer configured the K1 Real-Time Executive
using the Runtime Configuration Tool.

The designer selects the task's behavior
classification, Deterministic, Bounded Non-
Deterministic or Non-Deterministic.  The Task
Generation Tool enforces the rules of the K1 Task
Priority Layout.  A Periodic Task cannot select
Non-Deterministic because there would be no
assurance that it would complete before its next
scheduled periodic execution begins.  The allowable
task priority selection depends on the task's
behavior classification and the Runtime
Configuration parameters.

Alternately, Ada tasks in existing programs can
easily be converted to K1 tasks using a text editor
to insert the K1 calls and data structures.


Validation Considerations:

The validation suite will execute just as it did
before the K1 real-time executive was added into
the runtime environment.  Since the validation
suite does not call K1 to start any tasks as K1
tasks, the K1 real-time executive will be unused.

The validity of this approach is covered by AI-
00850* and the proposed Ada 9X Real-Time annex.
(Ada Interpretations 00850 is available from the
AJPO data base or Integrated Software, Inc.)


Status

K1 has been demonstrated on a Motorola MVME-147,
68030 based single board computer.  The Ada Runtime
Environment including the K1 Real-Time Executive
was burned into EPROM and plugged into the single
board computer.  The demonstration program was
downloaded from a portable PC via a RS232 port.

The K1 tools are currently hosted on a SUN SPARC
workstation with a color monitor.  The Ada compiler
is currently the Verdix VADS 6.0 , 680X0 cross compiler.

K1 is planned to be demonstrated at Tri-Ada, Nov.
16-20 in Orlando, Florida.

For more information contact:

Integrated Software, Inc.
1945 Palm Bay Rd #7
Palm Bay, Florida 32905 USA
[phone]
[phone] (fax)