ECEn 425

The YAK Kernel


The main focus of the ECEn 425 labs is the creation of a fully-functional real-time kernel called YAK. A real-time kernel is a simple operating system that provides basic support to create and execute independent units of computation called tasks. The YAK kernel also provides support for communication between tasks in the form of semaphores and message queues.

Through a series of labs, you will design and implement kernel routines that add to the functionality of the kernel until you have achieved the full functionality described in this document. There are many different ways to implement these routines, but some are much more painful than others. It is highly recommended that you thoroughly consider implementation issues of all routines and all required functionality early in the design phase so that later extensions can be made in a straightforward way without breaking your code.

General Kernel Operation

Real-time applications require both kernel code and application-specific code (also referred to as user code). The kernel provides a library of C routines that can be called as desired by a specific application. To achieve the desired functionality, the user code must call the kernel routines according to prescribed conventions.

Real-time kernels rely on CPU interrupt mechanisms to respond in a timely way to critical events. The ISRs (Interrupt Service Routines), code to which control is automatically transferred when interrupts occur, are part of the kernel. However, they must be modified by the application programmer so that they call the interrupt handler functions that do the actual work associated with each interrupt-causing event. Each ISR and the interrupt handlers it calls therefore constitute a separate runnable entity that is scheduled and dispatched (caused to execute) by hardware, in contrast with tasks which are runnable entities scheduled and dispatched by the kernel. It is vital to understand and differentiate between these two runnable entities. Both may call kernel functions, and the kernel supports communication between interrupt handlers and tasks, but there are significant constraints on the kernel functions that interrupt routines may call.

The YAK kernel supports nested interrupts. You are required to make ISRs and interrupt handlers interruptible by higher priority interrupts. You are advised to consider carefully early in the design phase the implications of implementing nested interrupts.

It is important to note that a mix of C and assembly routines will be required to implement the kernel. In general you should code everything you can in C and use assembly only when you must. Routines that access specific registers (e.g., to save or restore program state) or execute specific instructions (e.g., to enable or disable interrupts) must be written in assembly. One might be tempted to code more in assembly to make it more efficient than compiled C code, but code written in C is much easier to modify and debug, and in the long run, this is much more significant than shaving a bit of run-time overhead. Moreover, the labs for this class will not include any application code in which timing is so critical that compiled C code is inadequate. Since your kernel requires both C and assembly routines, you will need to understand calling and parameter passing conventions used in compiler-generated code so that your C code can call assembly functions and your assembly code can call C functions.

It is the responsibility of the application programmer to partition the work required into tasks, to specify all communication between those tasks, to assign priorities to each task, and to write one or more C functions to represent each task. For maximum flexibility in task scheduling, YAK requires that each task have its own stack space; the responsibility of declaring and sizing the stack belongs to the application programmer and takes place in the user code. A task typically performs work, then delays its execution for a specified period of time or until a particular signal is received indicating it should run again. (The details depend on which kernel routines the task calls.) The kernel manages requested changes in the state or status of each task. Internally the YAK kernel uses a data structure called a task control block (TCB) to keep track of all relevant information for each task.

Because an RTOS is intended to manage time-critical, prioritized code, the kernel must be designed with performance in mind. Think carefully about how you organize the kernel's internal data structures and code so as to avoid unnecessary overhead. Your grade may be adversely affected if your kernel does not meet certain performance requirements.

The Kernel Interface

The kernel consists of C functions, variables, and data structures that are used in combination to provide a variety of services. So that we can readily distinguish kernel code and data from that of the application, names of user-visible YAK routines and variables should begin with YK. Following this convention will keep your kernel reasonably compatible with others and make it easier to debug.

Here is a list of C functions that you must implement in your YAK kernel.

The kernel should also define and maintain the following global variables which are part of the YAK API and can therefore be referenced as desired by the user code.

The correct operation of any application code built on YAK requires strict adherence to a number of conventions. Many of these are mentioned in this document. One worth noting here is that there are significant constraints on the structure of code used to represent tasks in application code. Each task has a corresponding C function (passed as a parameter to YKNewTask) that simply loops forever and never terminates. These C functions are never called in the conventional way, nor will they ever return. (Executing task code that returns from the task function will result in rather strange errors that might be unique to your implementation of the kernel.) If we were to add a YKDeleteTask to our kernel, task code could also end with a call to that function, but the application code we will run this semester will not require this functionality. (It would be pretty easy to add, however.)

Design and Implementation Issues

There are a number of issues you should think through carefully before settling on a specific implementation. The following points are not exhaustive in this respect, but they should serve as a good starting point.

Recommended File Organization

It is strongly recommended that you create a separate directory for each lab that contains all YAK and application files. As you add files or modify the structure in any way, make sure you update your make file. (Not recompiling an old file with a new data structure is a sure-fire way to generate a failure.)

Within each directory, it is highly recommended that you follow certain conventions for file organization. (Do not, for example, just toss everything into a single assembly language file and a single C file!) Your files should reflect the logical distinction between application and kernel. A suggested organization is given below. I've indicated the file names I used in my code to suggest that you adopt consistent and meaningful names that will help you remember where to find the routines and data structures you want.

  My file name File contents
1 lab#_app.c C code for application (# is lab number)
2 myinth.c C code for interrupt handlers
3 myisr.s Assembly code for ISRs
4 clib.s The clib.s file containing library code and the interrupt vector table
5 yaku.h A .h file for kernel code, to be modified by the user. It should include things such as the #define statements for idle task's stack size, the maximum numbers of tasks, semaphores, and message queues, etc.
6 yakk.h A .h file for kernel code, not modified by user. It should include declarations such as the TCB, YKSEM, and YKQ, as well as prototypes for the kernel functions. Global variables shared by kernel and application code should be declared as extern in this file.
7 yakc.c Kernel routines written in C. Global variables used by kernel code or shared by kernel and application code should also be defined in this file.
8 yaks.s Kernel routines written in assembly

If you were developing an application and had purchased YAK off the shelf (a real bargain, to be sure) to build your system around, your application code would go into files 1 and 2. You would need to make slight modifications to system files 3-5 for your application. You would modify the ISR code in file 3 to call your interrupt handlers, you would modify the code in file 4 so the jump table got initialized correctly, and you would modify file 5 to tell the kernel such things as how many tasks your application code creates. (As you design your kernel, you will need to modify these files to make them work with the application code we give you for your labs.) As an application programmer, you would NOT need to modify system files 6-8 in any way since they are application independent. I hope you can see the benefit of organizing files in this way.