Biswajit, a software engineer with Wipro Infotech, Bangladore, India, received his M.S. in computer science and engineering from the Indian Institute of Technology (I.I.T.), Madras. Timothy, a professor in the Department of Computer Science & Engineering at I.I.T., is developing DSP-based computer network products. They can be contacted at [email protected] and [email protected], respectively.
An embedded system is a controller that resides within the system it controls. The control logic is built into the system, which runs throughout the system lifetime. Embedded systems for dedicated applications usually do not require the versatility of the general-purpose microprocessor and often cannot afford the associated cost or overhead. These applications are typically more I/O oriented than CPU intensive. Hence, what they require is a reasonably fast CPU with a simple instruction set, coupled with enhanced I/O capabilities.
Analog Devices' ADSP-21xx series of digital-signal processors (DSPs) fit the requirements of embedded systems very well. They are inexpensive, have a host of features such as a 33-MHz clock, execution of multiple instructions in a single cycle, zero-overhead loop instructions, single-cycle interrupt latency, dual 20-Mbits/sec full-duplex serial ports, and host-interfacing capability. These factors make them suitable contenders for use in various microprocessor-based embedded applications such as control systems, network control and management systems, and device controllers.
In fact, ADSP-21xx processors are being used in Ethernet switches and bridges, laser-printer controllers, and wireless telephones. As DSPs proliferate, the need for better programming platforms for them has grown. To this end, we have developed KeRTESy, a real-time microkernel for embedded systems.
System Design
Many real-time embedded control and management applications are event driven with only a small amount of processing required to handle each event. In such systems, the CPU utilization is usually low while the CPU waits for events to occur. Upon occurrence of an event, the application requires a fast context-switch to the event handler. For such systems, a simple event-driven scheduler that allows tasks to run to completion is an ideal choice. In addition to making fast context-switches possible, such a scheduler also takes much less memory (due to simplified code), which is a valuable resource for embedded systems.
These considerations led us to include the following characteristics in the design of KeRTESy:
- Tasks are statically created at system initialization time to facilitate suitable arrangement of the task table, so as to minimize the scheduler overhead.
- All tasks are event driven.
- At creation time, a task has to specify the event that will cause it to be scheduled. The event may be an interrupt, an alarm (periodic or one-shot), or even an arbitrary C expression becoming nonzero.
Task preemption and resumption require a separate stack for each task and the ability to completely save and restore the processor status. The former increases memory usage compared to a single stack shared by all tasks. The ADSP-21xx processor maintains several internal stacks for keeping processor status, loop counter, and program-counter values. Unfortunately, it does not support manipulation of these stacks. Fully preemptive multitasking would be extremely costly on an ADSP-21xx processor, and since it is not required in many embedded systems, we have opted for a run-to-completion design. A long-running task can be preempted by a higher-priority task, to be restarted (not resumed) only when its next event occurs.
The system timer is used to periodically invoke the scheduler, which checks for the occurrence of events that might warrant the preemption of the currently executing task for a higher-priority task. If no such task is found, control is returned to the interrupted task. A task may yield on its own at any time, in which case the scheduler schedules the highest-priority ready task.
KeRTESy tasks are thread based. A thread differs from a conventional process in that it does not own a separate address space or separate code. It shares address space and code with other threads. A thread has an individual program counter and a stack for storing local variables and calling parameters. Thread-based tasks make context switching easier by minimizing the thread-specific context. The thread-based implementation also suits the flat memory-addressing scheme of ADSP-21xx processors.
Application Programming
Since the kernel is small, the API consists of a compact set of calls dealing mainly with scheduling. On startup, the application uses CreateThread() to create new threads (see Figure 1). This establishes an entry in the thread table, and if needed, sets up the required timers (for PERIODIC/ALARM threads) or the interrupt vector table (for INTERRUPT threads). After creating all the threads and performing other application-specific initialization, the application calls Kernel() as the last step in its main(). This system call never returns. After initializing the system, it calls Scheduler(), which runs in an infinite loop and does the actual thread scheduling.
KeRTESy provides timers for purposes such as timeouts and retransmission of packets. SetAlarm() sets up a timer for the specified duration. A flag argument specifies whether the timer is "one shot" or periodic. If a thread is established as a timer handler, then it is scheduled upon expiration of the timer; otherwise, the expiration of the timer can be explicitly checked by the thread using CheckAlarm(), which returns a nonzero value when the timer has elapsed. A thread can invoke CancelAlarm() to cancel a previously set timer.
A preemptive thread may protect critical section execution using either DisablePreempt() and EnablePreempt() system calls or BeginCS(IMASK) and EndCS() macros. The former calls disable and enable preemption, while the latter accesses disable and enable interrupts represented by IMASK. The latter are more restrictive. If a thread wants to exit before reaching its logical end, it can invoke Yield() to free up the thread's context and transfer control to the scheduler. The thread will be run again when its event next occurs.
All kernel-related defines, typedefs, and the like are included in kertesy.h, which, along with the entire KeRTESy source code, is available electronically; see "Availability," page 3.
An Example Application
To illustrate how you can use KeRTESy, Listing One resents a simple application that maintains the temperature of a device within an adjustable range. One thread periodically samples the input temperature and stores the value in the global variable currTemp. Another thread turns on a heater and lights up an LED when the temperature falls below a preset lower threshold (currTemp<MIN_TEMP). A third thread turns the heater and LED off when the temperature crosses the upper threshold (currTemp
MAX_TEMP). The fourth thread turns the heater off and generates audio-visual alarm signals if and when the temperature crosses a danger limit.
Before invoking the C preprocessor, the KeRTESy preprocessor (called NAP) scans the source file(s) for occurrences of special macros and directives. The macros include those that form part of the CreateThread() system call. To evaluate EXPRESSION events, NAP encapsulates the supplied expression into a function and stores this function in a file that is specified using the special #eventfile directive (defaults to eventdefs.c). Any global variables used in the event expressions must be declared by you in this file for maintaining scope. NAP inserts the event functions below these variable declarations. The code #pragma ident "KeRTESy code below" demarcates declarations of variables from the EXPRESSION function definitions. NAP inserts this line at the end of the file if it did not exist before. The EXPRESSION functions are appended below this line. After processing the original source file, NAP writes the output to a different file. It is this second file that is passed to the C preprocessor and the compiler. This second file has all the special macros substituted, as well as the directive #eventfile filename replaced by #include filename.
Internal Stack Manipulation
We schedule threads by simply calling them as functions from within the scheduler (except INTR threads, which are called as interrupt handlers by the CPU upon generation of the specific interrupt). Since threads share the same address space, separate contexts need not be created for them. ADSP21xx processors have a number of hardware stacks used for loop counters, loop-boundary addresses, status, and program-counter values. Each of these has a fixed size (values pushed beyond the limit are discarded). If a thread is executing a nested-control structure when it either yields or is preempted by the kernel, these stacks may be nonempty, and a future thread might overflow the stack. Therefore, before scheduling a thread, the scheduler clears all four stacks.
Scheduler
We have implemented three variants of the scheduler with different scheduling policies. In the first, the threads are arranged in nonincreasing order of priority in an array called PSTab (see Figure 2). The scheduler always scans from the start of the array until it finds a thread that is ready.
In the second variant, scanning always starts from the highest-priority level, but threads at the same level are scanned in a round-robin fashion, lessening the probability of starving (which is present in the first version). This is achieved by maintaining a linked list of threads at the same priority through an additional field in the thread table (see Figure 3).
In the third variant, the scheduler does a bitmap lookup for scheduling a thread (Figure 4). The bitmap is constructed after all threads are defined, and has more bits set for a thread at a higher-priority than one at a lower priority. Thus, when the bitmap is scanned, a higher priority thread gets more frequent lookups. Here, the concept of priority is not absolute, but only determines the frequency of lookups.
Thread Table
The data structure for the thread table in variant 2 (Figure 3) is presented in Listing Two. The table is an array of MAX_PROCESS entries. Each entry is a structure containing six fields. The first field is the thread priority. The second field stores the nonpreemption duration if the thread is preemptive, 0 otherwise. The third field denotes the type of event that causes the thread to be scheduled. The fourth field, a union, is the event specification: the timer id, the EXPRESSION-function pointer, or the interrupt number. The fifth field is the address of the thread function. The sixth and last field, absent in other scheduler variants, points to the next thread at the same priority level. This pointer gets changed each time the thread is scheduled to maintain a dynamic order among threads at the same priority.
Context Switch
Listing Three presents the complete context-switch code. Preemption involves freeing up the internal stack registers, allocating a new stack frame for local variables, procedure-call parameters, and so on, then making a call to the new thread.
Performance
Memory usage and execution times for critical sections of code form the important performance metrics for real-time embedded systems. KeRTESy uses less than 2000 words of memory or about 6 percent of available on-chip memory on the ADSP-2181, and was written in assembly language. (A word of data memory is two bytes and a word of program memory is three bytes. The context-switch time varies with the number of threads.) On a 33-MHz ADSP-2181, the worst-case context-switch time for scheduler variant 2 is 8.51 microseconds with two threads, 36.33 microseconds with 10 threads, and 67.24 microseconds with 20 threads. The interrupt-handling latency is just one cycle, as the interrupt handler is directly called from the interrupt-vector table upon occurrence of the corresponding interrupt.
Summary
Tasks in many embedded systems are short; hence, event-driven, run-to-completion scheduling is desirable. KeRTESy is a real-time kernel for such systems designed around the ADSP-21xx. It is small and fast, but sufficiently powerful to be useful. It is being used in the development of a remote traffic monitor for Ethernet LANs. The application collects Ethernet packet statistics (such as number of packets and packets with errors) for packets arriving at either of the two ports attached to an ADSP-2181. The statistics are sent to a manager front end upon request, which may then display them in a suitable format.
References
Bortolotti J.F., P. Bernard, and E. Bouchet. "RTMK: A Real-Time Microkernel." Dr. Dobb's Journal, May 1994.
ADSP-2100 Family User's Manual. Norwood, MA: Analog Devices Inc., 1992.
Tanenbaum, A.S. Modern Operating Systems. Englewood Cliffs, NJ: Prentice Hall, 1992.
DDJ
Listing One
/* BEGIN: thermostat.c */#include "kertesy.h"
#eventfile "eventdefs.c"
</p>
typedef enum {PriDanger, PriNormal, PriLow} prilevels;
void Thread1()
{
InPort(HEATER_DATA_PORT, currTemp);
}
void Thread2()
{
OutPort(HEATER_CTRL_PORT, ON);
OutPort(LED_PORT, ON);
}
void Thread3()
{
OutPort(HEATER_CTRL_PORT, OFF);
OutPort(LED_PORT, OFF);
}
void Thread4()
{
OutPort(HEATER_CTRL_PORT, OFF);
OutPort(ALARM_PORT, ON);
}
void main()
{
</p>
/* The first 3 threads have minimal tasks to perform, hence they can
be preempted after small durations. The priority is lowest for
Thread1 because its function is less critical than that of the
others. Threads 2 and 3 have equal priority. Thread 4 has the highest
priority because its function is the most safety-critical. */
</p>
CreateThread(Thread1, PriLow, PREEMPTIVE(2), PERIODIC(10));
CreateThread(Thread2, PriNormal, PREEMPTIVE(3),
EXPRESSION(currTemp <= MIN_TEMP));
CreateThread(Thread3, PriNormal, PREEMPTIVE(3),
EXPRESSION(currTemp >= MAX_TEMP));
CreateThread(Thread4, PriDanger, PREEMPTIVE(0),
EXPRESSION(currTemp >= DANGER_TEMP));
</p>
/* After creating all the threads, call the kernel to schedule. */
Kernel();
}
</p>
/* END: thermostat.c */
Listing Two
typedef union { /* The event type for the thread will Timer, Expression, or */
/* Intr. number */
</p>
u_int timerId; /* for timer type of event */
BOOLEAN (*funcPtr)(); /* for expression event */
u_char intrNo; /* for interrupt handler */
} DescUnionType;
</p>
typedef struct
{
u_char priority; /* priority of the thread */
long preEmptive; /* whether preemptive or not */
u_char descType; /* type of event that schedules this thread */
DescUnionType desc; /* event specification */
void (*psPtr)(); /* pointer to the thread function */
int next; /* pointer to next thread with same priority */
</p>
} PSStructType;
PSStructType psTab[MAX_PROCESS]; /* Thread Table */
Listing Three
!!!!! This code stores the value of non-preemptible duration of the !!!!! thread to be scheduled (readyPid), into the variable
!!!!! preEmptTime. If the thread is non-preemptive, -1 is stored into !!!!! preEmptTime.
mr=readyPidR*psStructSzR (ss);
i1=mr0;
modify(i1,psTabPtrR); !!!!! i1 = (psTab[readyPid]).
i6=i1; !!!!! save i1 to be used later.
m3=PS_PREEMPTL_OFF;
modify(i1,m3);
ay1=dm(i1,m2);
i1=i6;
m3=PS_PREEMPTM_OFF;
modify(i1,m3);
ax1=dm(i1,m2);
af=pass ax1; !!!!! if the thread's preemptive field is 0,
if ne jump SchedulerL18_;
af=pass ay1;
if ne jump SchedulerL18_;
ax1=-1; !!!!! ... then preEmptTime = -1, ...
ay1=-1;
SchedulerL18_:
dm(preEmptTime_)=ax1; !!!!! ... else preEmptTime =
dm(preEmptTime_+1)=ay1; !!!!! the value in the field.
SchedulerL19_:
SchedulerL20_:
!!!!! Disable timer intr. now -- after "currentPid" has been made to
!!!!! store the new thread's Pid, if timer intr. occurs, it will
!!!!! assume that a thread is running, and try to preempt it if it is
!!!!! preemptive. We stop that attempt by disabling timer intr. here.
dis timer;
i1=i6; !!!!! i1 = (psTab[readyPid]) = (psTab[readyPid].pid);
ax1=dm(i1,m2);
dm(currentPid_)=ax1; !!!!! Assign thread's Pid to currentPid;
mr0=dm(currentTime_+1);
dm(currentThreadStartTime_+1)=mr0; !!!!! currentThreadStartTime =
ar=dm(currentTime_); !!!!! currentTime.
dm(currentThreadStartTime_)=ar;
ena timer; & hspace{-3in} !!!!! Enable timer intr. again.
m3=PS_PSPTR_OFF;
i1=i2; !!!!! i2 contains (psTab[readyPid])
modify(i1,m3); !!!!! i1 = (psTab[readyPid].psPtr)
ar=dm(i1,m2);
i6=ar; !!!!! i6 contains pointer to the thread be scheduled.
!!!!! Now empty the internal stack registers.
#define PSE 0x0001 !!!!! PC stack empty
#define CSE 0x0004 !!!!! Counter stack empty
#define SSE 0x0010 !!!!! Status stack empty
#define LSE 0x0040 !!!!! Loop stack empty
!!!!! Empty the status stack until SSE is set
ay0=SSE;
LOOP_STA:
pop sts;
ar=sstat;
ar=ar AND ay0;
if eq jump LOOP_STA;
!!!!! Empty the counter stack until CSE is set
ay0=CSE;
LOOP_CTR:
pop cntr;
ar=sstat;
ar=ar AND ay0;
if eq jump LOOP_CTR;
!!!!! Empty the loop stack until LSE is set
ay0=LSE;
LOOP_LOP:
pop loop;
ar=sstat;
ar=ar AND ay0;
if eq jump LOOP_LOP;
!!!!! Empty the pc stack until PSE is set
ay0=PSE;
LOOP_PC:
ar=toppcstack;
ar=sstat;
ar=ar AND ay0;
if eq jump LOOP_PC;
!!!!! Stacks emptying done, now schedule.
call (i6); !!!!! (*(psTab[readyPid].psPtr))() : SCHEDULE;
Back to Article
DDJ
Copyright © 1997, Dr. Dobb's Journal
