From: SAHARBAUGH@ROO.FIT.EDU
Newsgroups: comp.lang.ada
Subject: zzz K1 explanation
Date: 17 Aug 92 12:20:00 GMT
Distribution: world
Organization: The Internet

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
(407) 984-1986
(407) 951-4291 (fax)

Newsgroups: comp.lang.ada