This portable microkernel is based on the Sceptre standard
The authors are electrical engineers and can be contacted at fax number +41 22 784 3452.
Digital-signal processors such as Texas Instruments' 320C30/40, Motorola's 96000, and Analog Devices' ADSP-210x are typically used as dedicated coprocessors--number-crunchers hooked to interrupt vectors, for example. In such configurations, the digital-signal processor (DSP) feeds a general-purpose CPU with "predigested" data so it can take care of housekeeping. Because the inevitable resource duplication is both expensive in cost-sensitive applications and inefficient in design, we needed a way to get rid of the general-purpose microprocessor in interrupt-driven systems we were designing.
With interrupt-driven systems, time is intentionally sacrificed as a safety margin while the CPU waits (via a loop) for the next interrupt. However, the time spent in a background loop with high-performance DSPs is typically 10 to 20 percent of the total CPU time--power that's often more than the total power of the general-purpose CPU. In designing our interrupt-driven system, we decided to utilize this power, instead of resorting to another processor. The only element we lacked was a simple method of scheduling the various low-frequency processes (compared to the interrupt processing) that run on the system. We needed a real-time kernel that would provide a fast context switch (to spend as little time in the kernel as possible), a simple interface to a standard programming language, interruptibility of the kernel to allow high-priority immediate processes hooked to an interrupt, a standardized approach to kernel services, and a high level of portability.
Since we weren't aware of any commercial software that could deliver total control over the interrupt state of the processor (and because a fast interrupt was time critical in our application), we ended up designing RTMK, the real-time kernel presented in this article.
The source code for both DSP and PC implementations of the kernel is provided with this article. Listings One through Three are the PC implementation. Listing One (page 105) is the RTMK.H header file, Listing Two (page 105) is the RTMK.C source file, and Listing Three (page 106) is TEST.C, the test program. The source code for the DSP version (specifically, the TMS320C30) is available electronically; see "Availability," page 3. (Executables for the PC version are also available electronically.) The PC implementation and test programs have been compiled with Borland C 3.1 but should compile as-is with Microsoft C. The DSP version has been compiled with the TI C compiler (Version 4.5) for TMS320C30.
RTMK and the Sceptre Standard
In 1980, several European software houses, tired of waiting for the ideal "real-time" language, proposed a simple but realistic set of commands for a real-time kernel; see "Sceptre," BNI Y (the French computing-standards bureau) September 1982. Our real-time kernel is based on this standard, although it supports only a subset of the original Sceptre commands.
The authors of Sceptre defined a set of primitives that is portable only by its specification. This means that once you've ported the kernel to a new target system, all applications that require specific real-time services are portable to this new target, as well. Services standardized by the Sceptre kernel are listed in Table 1. Note that unlike other kernels, Sceptre events are associated with tasks because events are an elementary mechanism that does not require a system-event queue handled by the kernel. This minimizes the addressing needed to identify which task to schedule and suppresses the need to clock a kernel function at a submultiple frequency of the fastest task to properly schedule the tasks in the system.
Remember that a real-time application is composed of programs under the control of an executive system. Any program execution is achieved through an active agent called a "task/process." The mechanisms that control the execution of these tasks are part of the executive. The executive has to hide specific properties of the target system by turning them into logical properties, interface between different parts of an application (possibly written in different languages), handle communications, and manage hardware resources (files, memory, and so on).
Since most high-level languages already provide parts of this executive as elements of their library, it is only necessary to design the kernel--a set of operations and data structures that can be used through the procedural calling mechanism of a high-level language.
The entities of the Sceptre standard include:
- Tasks/processes. The agent responsible for the execution of a program. A task has a name and attributes. A task context is the minimum set of information necessary for the target processor to execute the task instructions. A stored context is a memory area where the execution context of the task is saved when the task is not currently executing.
- Immediate Tasks. A task ensuring the interface between the real-time application and the environment. Immediate tasks are often handled via the interruption mechanism. In RTMK, the immediate process is the interrupt-service routine.
- Scheduler. A software or hardwired module in charge of handling the CPU power of a set of processors and dispatching it to a set of tasks. Generally, the scheduler of the immediate task is the interrupt mechanism of the processor, while the scheduler of standard (or differed) tasks is part of the kernel.
- Events. The event object stores a signal, which means that a condition became True. In the Sceptre standard, events are associated with specific tasks. This provides an efficient signalling process with low overhead.
- Region. The region object is purely a mark of CPU ownership. Context switches through the scheduler will not occur until a region is exited.
- Queue. The queue is a communication object between tasks that behaves like FIFO memory.
Process Descriptors
In any multitasking kernel, the CPU has to be allocated to different processes, even when they are not finished. During process changes (or "context switches"), we preserve the environment the process was executing in (the "process context"), while reinstating the next scheduled process.
A context switch consists of saving the current context, selecting the process that will get processor time, and restoring the context of this new process. Consequently, the context must contain all the necessary data to maintain the integrity of the CPU and compiled code for the process. The area where all this data is stored is a "process descriptor."
The RTMK PC process descriptor is shown in Example 1. The task priority is handled by the structure's priority and pmask fields. The second item is simply a mask that is precalculated during task definition in order to accelerate the context switches by avoiding unnecessary left shifts at run time. The expected_signals field is a mask. If bit n is set in this mask, then signal n can activate the process. The received_signals is another 32-bit field in which each bit set means that the corresponding signal has been sent to the process. Another element of the context is the microprocessor context that was saved (in the form of a jmp_buf buffer set by the setjump function in the PC implementation).
In the original Sceptre implementation of a real-time application, each process is associated with a set of signals. Each signal can be arrived or not_arrived. The process specifies its own activation condition through these signals.
A process can be in one of the following states:
- Waiting. The process is suspended until one of its signals has arrived.
- Ready. The process has received a signal and will continue execution when the kernel allocates it CPU time.
- In progress. The process is currently running.
In RTMK, we've implemented only the basic services. The signals are sent directly to the task, not (as in many other operating systems) to the kernel. This means RTMK signal handling is much easier and faster, thanks to its Sceptre characteristics.
Process-Handling Services
RTMK provides a number of process-handling services, including:
- osend(PROCESS,SIGNALS). Sets the bits contained in SIGNALS with the corresponding bits in the received_signals field of the processor decriptor and calls the scheduler. When executing, this primitive CPU ownership can be lost if the signals being sent activate a higher-priority task.
- owait(SIGNALS). Sets the process descriptor expected_signals field and calls the scheduler, which usually suspends the process until the notified signals arrive. This service returns the list of received signals. The return value distinguishes between the signals that triggered the process, since two signals can be active at the same time.
- oreset(SIGNALS). Clears the bits corresponding to SIGNALS in the process descriptor arrived_signals field in order to permit another cycle. By clearing these bits just before the next call to the wait service, we can ignore all the events that occurred during the processing (though it is not common practice to do so).
- oarrived_signals(void). Returns the field arrived_signals to the caller.
A process is simply defined by allocating a Process Control Structure (PCS) and calling the create_process function with two arguments: a pointer to the PCS and the address of the process's entry point (again, see Example 2).
An Example
In Example 2, the interrupt handler signals events directly to two processes. Process1 is a short routine that writes a character directly on the PC screen. Process2 is a long process that spends a lot of time in a useless loop and prints dots on the screen through the standard I/O library.
Process1 is activated 200 times when Process2 is activated once. The long calculation times of Process2 demonstrate that the direct screen writes are continuing when Process2 is active, which shows that the CPU has been temporarily reallocated to Process1 during the execution of Process2. The CPU has not been directly stolen by the kernel, but by the interrupt (an "immediate process" in Sceptre terminology) that is sending signals, thus giving control to the kernel.
Performance
Context-switch performance is critical if the time spent in the kernel is to be minimized. We've measured it at 11 ms with a full C version on a Texas Instruments TMS320C30 clocked at 32 MHz. This time drops to 5.5 ms with a scheduler written in assembler. The PC version has not been timed.
Table 1: Sceptre kernel services.
Class Operation Parameters Action
------------------------------------------------------------------------------------------------
Task Handling Start Task Starts the execution of the task.
Stop Task Stops the execution of the task.
Continues Task Resumes the execution of the task.
Terminate Terminates the task that calls this service.
Change Task, Gives task the new priority.
priority priority
State Task Returns task state.
Priority Task Returns the task priority.
Current task Returns the id of currently executing task.
Signaling Send Event,task Sends an event to a task.
Wait Event list Waits until one of the events has arrived.
Arrived Event list True if all the events have arrived.
Clear Event list Resets all events in list to nonarrived state.
Communication Put Element,queue Places the element into the queue.
Get Element,queue Gets the element from the queue.
Empty Queue True if the queue is empty.
Full Queue True if the queue is full.
Mutual- Lock Region Requests exclusive property of the region.
exclusion
Unlock Region Releases the region.
Task States Nonexisting No descriptor associated to task (not created).
Existing A descriptor has been defined for the task.
Nonexecutable Task has descriptor but can't start execution.
Executable Task has descriptor and can start execution.
Not in service Task is executable but execution has not yet
been started or is finished.
In Service Task is executable and has started execution
but has not finished.
Waiting Task is in service and waiting for a condition
to become True to continue execution.
Active Task is in service and not waiting for anything
except a free processor to execute.
Ready Task is active and only waiting for processor.
In Progress Task is active and currently executing on a
processor.
Example 1: RTMK process descriptor (PC version).
typedef unsigned long word32; /* Double Word for 32 process max kernel */
typedef word32 SIGNALS; /* Signal type */
struct PCS {
jmp_buf context; /* CPU Context (registers) */
SIGNALS expected_signals;
SIGNALS received_signals;
word32 pmask;
word32 priority;
};
typedef struct PCS *PROCESS; /* pointer of PROCESS CONTEXT STRUCTURE */
Example 2: Defining a process.
#include "RTMK.H"
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#include <signal.h>
#define IT 0x1C
#define VIDEO_RAM 0xB8000000
PROCESS p1,p2;
int i,j;
char far* p=(char far*)VIDEO_RAM+1;
void interrupt (*old_vector)();
void interrupt clock_it()
{
outp(0x20,0x20);
i+=1;
if(i==200){
i=0;
send(p2,1);
}
else send(p1,1);
}
far process1()
{
while(1) {
p++;
*p++=0x31;
if(p>(char far *)VIDEO_RAM+25*80*2)
p=(char far* )VIDEO_RAM+1;
wait(ANY_SIGNAL);
reset(ALL_SIGNALS);
}
}
far process2()
{static long n;
enable();
while(1) {
printf("process 2:waiting\t");
wait(1);
printf("process 2 :reseting signals\t");
reset(1);
printf("process 2:calculating");
for(j=0;j<60;j+=1){
for(n=0;n<100000;n+=1);
printf(".");
}
printf("calculation terminated ");
}
}
jmp_buf sys_context;
void terminate()
{
longjmp(sys_context,1);
}
void main() {
clrscr();
create_process(&p1,process1);
create_process(&p2,process2);
old_vector=getvect(IT);
disable();
signal(SIGINT,terminate);
setvect(IT,clock_it);
if(!setjmp(sys_context)){
run_kernel();
}
setvect(IT,old_vector);
}
[LISTING ONE]
Copyright © 1994, Dr. Dobb's Journal
/* functions' prototypes */
#include "rtmktype.h" /* declaration of system's types */
#ifndef RTMK_H
#define RTMK_H
void create_process(PROCESS *,void far *);
void send(PROCESS,SIGNALS);
SIGNALS wait(SIGNALS);
SIGNALS reset(SIGNALS);
SIGNALS arrived_signals(void);
SIGNALS process_state(PROCESS);
#define ANY_SIGNAL 0xffffffff
#define ALL_SIGNALS 0xffffffff
int run_kernel(void);
#endif /* RTMK_H */
[LISTING TWO]
/* RTMK.C Real Time Micro Kernel */
#include "RTMKTYPE.h" /* RTMK types' definitions */
#include <dos.h> /* include for context and interrupts management */
#define NULL 0
#define PROCESS_STACK_SIZE 500 /* Stack size for each process */
unsigned _stklen=20; /* minimal stack needed to start the kernel */
/********************* System's variables ****************/
struct PCS pcs_tab[32]; /* Process Context Structure table */
unsigned stack[32*PROCESS_STACK_SIZE]; /* stack table for all the process */
unsigned nbr_process; /* number of process declared */
PROCESS current_process; /* pointer on current process PCS */
word32 ready_process; /* bit map list of ready process */
/************************************************************************/
/* create_process: declares the process where p is the identifier for */
/* the kernel and entry_point is the address of the process's code */
/* the context of the process is initialized. */
/************************************************************************/
void create_process(PROCESS *process_id,void far *entry_point())
{
if (nbr_process<32){ /* 32 is the maximun number of process */
*process_id=pcs_tab+nbr_process;
(pcs_tab[nbr_process].context)->j_ip=FP_OFF(entry_point);
(pcs_tab[nbr_process].context)->j_cs=FP_SEG(entry_point);
(pcs_tab[nbr_process].context)->j_flag=0;
/* reset flag register to disable interrupts */
/* process stack */
(pcs_tab[nbr_process].context)->j_sp=
(unsigned)stack+PROCESS_STACK_SIZE*(32-nbr_process);
(pcs_tab[nbr_process].context)->j_bp=(pcs_tab[nbr_process].context)->j_sp; /* bp=sp (stack) */
(pcs_tab[nbr_process].context)->j_ds=FP_SEG((void far *)stack);
(pcs_tab[nbr_process].context)->j_ss=FP_SEG((void far *)stack);
nbr_process+=1;
}
}
/**************************************************************************/
/* scheduler: the context of the current process is saved and the system */
/* switch to the ready process. If next_process=NULL the higher priority */
/* ready process is searched, else the process is the ready process. */
/**************************************************************************/
void scheduler(PROCESS next_process)
{word32 n,i; /* i and n loop variables */
/* saves the context of current process */
if (setjmp(current_process->context)==0){
if (next_process)
current_process=next_process; /* scheduled is one in next_process */
else { /* determine the next_process */
n=0;
i=0x80000000;
while (!(i&ready_process)) {
n+=1;
i>>=1;
}
current_process=pcs_tab+n; /* scheduled process is elected process */
}
longjmp(current_process->context,1); /* switch to the scheduled process */
}
}
/************************************************************************/
/* SIGNALS MANAGEMENT: send(process,signals_mask), wait(signals_mask), */
/* reset(signals_mask), arrived_signals(), process_state(process) */
/************************************************************************/
/* send: send to process signals that are on (1) in signals_mask */
/************************************************************************/
void send(process,signals_mask)
PROCESS process;
SIGNALS signals_mask;
{
process->received_signals|=signals_mask; /* update arrived signals */
if (process->received_signals&process->expected_signals){
/* if the process is waiting for the signals */
ready_process|=process->pmask; /* put the process ready */
process->expected_signals=0; /* reset expected signals */
if (current_process->priority<process->priority){
/* process's priority level is higher than current_process priority */
scheduler(process); /* switch to process directly */
}
}
}
/**************************************************************************/
/* wait: puts current process in wait for signals_mask return arrived signasl*/
/**************************************************************************/
SIGNALS wait(signals_mask)
SIGNALS signals_mask;
{
if (!(current_process->received_signals&signals_mask)){
/* if signals in signals_mask are not arrived */
/* update expected_signals */
current_process->expected_signals=signals_mask;
ready_process^=current_process->pmask; /* turn process not ready */
scheduler(NULL); /* switch to next process */
}
return (current_process->received_signals); /* returns arrived signals */
}
/************************************************************************/
/* reset: puts signals that are on in signals_mask to zero(not arrived) */
/* returns signals that were arrived */
/************************************************************************/
SIGNALS reset(signals_mask)
SIGNALS signals_mask;
{SIGNALS old_signals;
old_signals=current_process->received_signals; /* saves arrived signals */
/* reset signals_mask */
current_process->received_signals=
current_process->received_signals&~signals_mask;
return (old_signals); /* returns arrived signals before reset */
}
/************************************************************************/
/* arrived_signals: returns arrived signals of the current process */
/************************************************************************/
SIGNALS arrived_signals()
{
return (current_process->received_signals); /* returns arrived signals */
}
/************************************************************************/
/* process_state: returns expected signals of process */
/************************************************************************/
SIGNALS process_state(process)
PROCESS process;
{
return (process->expected_signals); /* returns expected signals */
}
/************************************************************************/
/* run_kernel: initialize the kernel's variables and switch to the */
/* first process, the last loop is the system idle process. */
/************************************************************************/
word32 free_time; /* time not used by process */
int run_kernel()
{int i; /* loop variable */
word32 current_process_mask; /* manage the process mask */
PROCESS pcs_ptr; /* pointer on process contect structure */
disable(); /* disable interrupts */
/* initialization of process context structures */
current_process_mask=0x80000000;
ready_process=0;
for(i=0;i<=nbr_process;i++){ /* for each process initialize pcs */
pcs_ptr=pcs_tab+i; /* point to the pcs in the pcs table */
pcs_ptr->received_signals=0; /* no events arrived */
pcs_ptr->expected_signals=0; /* no events expected */
pcs_ptr->pmask=current_process_mask; /* put the process mask */
pcs_ptr->priority=nbr_process-i; /* set the priority */
/* the process is now ready to take the CPU */
ready_process|=current_process_mask;
/* current_process_mask for the next process */
current_process_mask=current_process_mask>>1;
}
current_process=pcs_tab+nbr_process; /* current process is idle process */
free_time=0; /* reset free_time */
scheduler(pcs_tab); /* switch to the higher priority process */
enable(); /* enable interrupts in idle process */
for(;;) /* loop forever : idle process */
free_time+=1; /* one for each loop */
}
[LISTING THREE]
#include "RTMK.H"
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#include <signal.h>
#define IT 0x1C
#define VIDEO_RAM 0xB8000000
PROCESS p1,p2;
int i,j;
char far* p=(char far*)VIDEO_RAM+1;
void interrupt (*old_vector)();
void interrupt clock_it()
{
outp(0x20,0x20);
i+=1;
if(i==200){
i=0;
send(p2,1);
}
else send(p1,1);
}
far process1()
{
while(1) {
p++;
*p++=0x31;
if(p>(char far *)VIDEO_RAM+25*80*2) p=(char far* )VIDEO_RAM+1;
wait(ANY_SIGNAL);
reset(ALL_SIGNALS);
}
}
far process2()
{static long n;
enable();
while(1) {
printf("process 2:waiting\t");
wait(1);
printf("process 2 :reseting signals\t");
reset(1);
printf("process 2:calculating");
for(j=0;j<60;j+=1){
for(n=0;n<100000;n+=1);
printf(".");
}
printf("calculation terminated ");
}
}
jmp_buf sys_context;
void terminate()
{
longjmp(sys_context,1);
}
void main() {
clrscr();
create_process(&p1,process1);
create_process(&p2,process2);
old_vector=getvect(IT);
disable();
signal(SIGINT,terminate);
setvect(IT,clock_it);
if(!setjmp(sys_context)){
run_kernel();
}
setvect(IT,old_vector);
}