kaOS -- A real-time, multithreaded, preemptive OS for the Atmel Mega32 featuring an SD/MMC loader

We have created a real-time, multithreaded, preemptive operating system called kaOS for the Atmel Mega32 microcontroller, which loads and executes programs from a Secure Digital or MMC card.

We wrote this OS and created the SD/MMC card reader as a final project for Cornell's ECE 476 class taught by Professor Bruce Land. Our reason for choosing this particular project is that we were unable to find any OS for the Mega32 that doesn't have to be statically compiled in with a user program. In contrast, kaOS waits for a card to be inserted and a reset button to be pressed, at which point a program is loaded from the card and executed. At any time, a new card with a new program can be inserted and run. Executing a new program doesn't require reprogramming the Atmel processor.

We are two engineering students at Cornell University taking ECE 476: Designing with Microcontrollers (Spring 2005). Both of us are graduating in May and beginning work for Microsoft in August. Nick Clark is an Electrical and Computer Engineering major and Adam Liechty is a Computer Science major.

The design of kaOS was broken up into two major components: the operating system itself and the card reader and program loader.

The card reader is accessed via the Atmel's SPI interface by the program loader, which places the program into flash memory. These programs can be written similar to a standard Atmel Mega32 program, except that it must include the kaos.h header file, which provides an interface to the threading and messaging calls to the OS. The program loader resides in the Mega32's bootloader section of flash. This gives it write access to other portions of flash memory so that it can write executables to program space. Once kaOS loads a program, it creates a thread for it and jumps to its main() method.

The operating system is real-time, multithreaded, and preemptive. It supports creation of up to 8 threads, which can be prioritized. Threads with the same priority are alternately preempted to give both equal processing time. kaOS also supports messaging between threads as a means of inter-thread communication.

While the idea for this project was born out of the lack of a true OS for the Mega32 that dynamically loads programs, we must give some credit to aOS, created by Anssi Ylätalo. In particular, we used his context-switching code to swap processor states when changing threads. Also, portions of our code used to read from SD/MMC cards were adapted from code written by Radig Ulrich. Additional information about SD card communication and the SPI protocol were obtained from SanDisk's SD card manual.

In designing the operating system, we considered various library functions that we could add to increase functionality, such as LCD and keypad drivers, events, and support for multiple programs on a single card with a menu system to choose between them. These features, although useful bells and whistles, were cut from the design because they were extraneous to our core vision of creating a dynamically-loading OS, added unnecessary complexity, and consumed extra flash and RAM, which might be needed for some user programs.

We ran kaOS on an Atmel Mega32 on an STK500 development board, which are available in the lab. In addition, we built a circuit to connect to the SD/MMC card. We connected it to the STK500 with a 10-pin jumper cable to PORTB, which contains the Mega32's SPI interface. We wired the SD card connector's clock, DataIn, and ChipSelect pins to PORTB's pins 7, 5, and 0, respectively, and the DataOut to PORTB pin 6.

The three inputs to the card were each fed through separate step-down circuits to decrease the voltage from the power supply's 5V to the 3.3V required by the card. Likewise, the output from the card was fed through a step-up circuit before going to B.6. The designs of these step-down and step-up circuits were taken from the final project by Peter D'Antonio and Daniel Riiff. To obtain the 3.3 volts needed for the HIGH voltage for the card, we used a simple voltage regulator. We employed the voltage regulator after we found voltage dividers by themselves to be worthless, since the card acts as a load on the 3.3V, drawing some current. With the voltage dividers, the 3.3V was pulled down to 2.6V with the card's load. Our regulator, however, was able to sustain a voltage of about 3.26V with the card's load, which is well within the card's specifications.

We had 3 unused pins on PORTB after connecting to the card reader, so we added a pushbutton with a pull-up resistor and connected it to pin 1. This button is used as a reset, which causes the OS to load the program from an SD/MMC card, if one is inserted, and run it.

The SD connector we used included an ejector, which makes inserting and removing cards easy. Pushing the card into the slot clicks it into place. Pushing it again ejects it with a spring.

The real complexity of our design of kaOS is in the software. The biggest software challenge we faced was getting the bootloading to work. All programs on the Atmel have to be contained in flash memory, but only the bootloader can write to flash memory. Thus, we decided to put our OS in the bootloader section of flash. This decision also helped us avoid address conflicts with user programs because the bootloader resides at the highest addresses of flash memory.

We emailed Atmel several times with bootloader questions, asking about the feasibility of some of our ideas. The maximum bootloader size is 2048 instructions. kaOS is too big to fit in this space, so we fixed some functions in high flash addresses next to the bootloader, keeping the functions that program the flash actually in the bootloader.

Card Programmer
The Atmel programs created in our class have been coded and compiled in CodeVision AVR Studio. CodeVision creates .ROM files when it makes a project, which are lists of 16-bit words. These files define what the contents of flash memory should be when the chip is programmed. Rather than programming the MCU, however, we took these .ROM files and used them to program our SD card. We wrote a Win32 programmer and an Atmel programmer, separate from the OS, which programs the contents of a .ROM file to our SD card, also through the circuit we built. The .ROM files consist of hundreds or thousands of lines like the following:

...
003E34:D5EF
003E35:B3BD
003E36:8E9F
...

Each line gives a program address and data value. Our Win32 program parses this file and sends the length of the program followed by its binary contents through the PC's serial port to the STK500. The Atmel program then transfers what it receives on the STK500's serial port to the SD card. Data is simply written to the card sequentially. No file system is used. We considered using FAT16 to organize our data on the cards, but abandoned that feature due to the added complexity of reading FAT16. One additional point we should note is that we initially tried to use the Procyon AVR library to read and write to the SD card, but after experiencing a lot of problems with it realized that it is written for another compiler and is incompatible with CodeVision.

Program Loader
When kaOS boots, it begins waiting for an SD card and a reset signal. At this point, it begins reading the contents of the card into small RAM buffers, which are subsequently transferred to flash. Because RAM is limited, we decided to do some clever repurposing of memory when transitioning between loading a program and executing it under the OS. The buffers used to read data from the card overlap with OS data structures that are not used until after the program is loaded. Since loading and executing never overlap, we can use the same memory for both.

Once the program is loaded (into the lower end of flash opposite kaOS which is in the upper end), kaOS creates and runs a thread that uses the address of the program's main() function as its starting point. User programs can then spawn other threads from their main() function. This is where the operating system takes over.

Operating System
Borrowing some ideas from Anssi Ylätalo's aOS and adding new features of our own, we constructed our preemptive multithreaded operating system. All the code for the OS portion is our own, except for the context switcher which is borrowed from aOS. The following block diagram illustrates the main components of kaOS:

OS Block Diagram

As the diagram illustrates, each thread has an ID, priority, state, sleep duration (if any), a message box, and its own stack. The stack size is defined by the user program and each thread can be created with a custom-sized stack. This allows for flexibility to use the Mega32's limited RAM effectively. Thus if some threads need large stacks, while others need little stack space, kaOS allows user programs to create threads tailored to these needs. One problem we encountered in creating this OS is that by dynamically loading programs that are compiled separate from the OS, the two executables (OS and user program) could possibly conflict in their allocations of RAM. To prevent this, the header file, kaos.h, fixes a block of memory addresses for use as OS variables. Since all executables run on kaOS must be compiled with kaos.h, this prevents the compiler from breaching kaOS's RAM. kaOS then uses only these RAM addresses to store OS variables when user programs are running (although this is not the case before a program is loaded, as noted in the Program Loader section.

One limitation of kaOS is that user programs cannot currently take advantage of hardware interrupts. The reason is that the interrupt vector table can reside either in the bootloader or at the lower end of flash. Since the OS resides in the bootloader, we need the interrupt vector table to reside there as well. Future work would involve wrapping various interrupts into events that can be registered with parameterized callbacks.

To facilitate inter-thread communication, each thread has its own mailbox. A thread can pass a message to any other thread by calling SendMessage() with a pointer to the destination thread and a void pointer to any type of message structure. The mailboxes are implemented as a queue of messages for each thread as well as a queue of free message structs.

Semaphores are a necessity for synchronization in any OS. kaOS supports creation, waiting and signaling of semaphores as would be expected of an OS. We implemented them as a list of active semaphores and a list of free structs. Each semaphore holds a pointer to the threads waiting on it. When a semaphore is signaled, a waiting thread is removed from this list and reactivated.

The scheduler for kaOS allows priorities between 0 and 255. Higher priority threads always run unless they sleep. Equal-priority threads are swapped back and forth by the scheduler. We used the Mega32's Timer0 to call the scheduler every 10ms and schedule a new thread if necessary. The scheduler keeps all active threads in a queue. Each time the scheduler runs, it finds the highest priority active thread, choosing the least-recently scheduled in case of a tie. It removes it from the queue, schedules it, and places it at the end of the line.

Finally, it was a bit tricky to get kaOS to allow user programs to make OS calls. We accomplished this by including fixed function pointers to the addresses of kaOS functions in the kaOS.h header.

In the end, we were able to successfully accomplish our core objective, which was to create a multithreaded, preemptive operating system that loads program dynamically from a card. We created test programs that verified the concurrency controls on the threads and semaphores and showed that the scheduling, context-switching, and priorities all worked as designed. Our scheduling occurs every 10ms and is very accurate since it is based on timer interrupts. This 10ms granularity means that sleeping threads is only accurate to 10ms intervals, but sleeping is not generally a tremendously accurate feature in most operating systems, so we didn't consider this to be a problem. The operating system and card reader we built are as safe as the Atmel Mega32 and STK500. The card reader is driven by the same power supply as the STK500. While we have found kaOS to work in our tests, it has not been thoroughly tested and should not be used in critical real time situations such as where human or animal health or safety depend on it. However, we believe that kaOS is a big step in demonstrating the possibility of creating an OS that dynamically loads programs, and we have found that once a set of chips is programmed, it is easy to switch execution between various user programs by swapping the card and pressing reset.

At the start of our design of kaOS, we believed that design and implementation would be relatively easy. As we began trying to get bootloaders and card readers to work however, we realized the difficulty of our objectives. Toward the end of the semester we wondered for a while if we would be able to load programs from an SD card, but we were able to get this working in the end. We accomplished all our major objectives and included some minor features that we wanted as well, such as preemptive swapping of same-priority threads. We were unable to complete some features due to time, including implementing a menu system to choose between the programs to run from a card, and creating an event framework with delegates for the OS. If we were to continue with this project, we would increase the ease of use of programming a card. Currently, this requires making a project in CodeVision, obtaining the .ROM file, and using a Win32 program in conjunction with an Atmel program to load the executable onto the card. We would have liked to write a Win32 program that wrote directly to the card through a USB card reader connected to the PC. We would also include bounds checking on the size of the executable, to make sure it does not overwrite parts of the OS when a program loads from the card. Finally, we would implement an event framework to wrap all the interrupts, since kaOS programs currently cannot take advantage of interrupts due to the limitations described earlier.

As noted above, we owe credit to:

Anssi Ylätalo, for design ideas from aOS, and the context-switcher code.

Radig Ulrich, whose code we adapted to read and write to the SD card.

Peter D'Antonio and Daniel Riiff, for the design of our step-up and step-down circuits.

Ethical Considerations
In the design of kaOS, we have adhered to the IEEE code of ethics, examples of which are noted here:

There is no possibility of conflict of interest in creating this project. We offer all our code and circuit design to the public domain.
While we believe the work we have accomplished to be valuable, we have already stated that, due to lack of thorough testing, this operating system should not be used in critical applications.
We have not accepted or even been approached with bribes.
Our novel design of an operating system for the Atmel Mega32 that dynamically loads programs is intended to broaden the scope of what can be done with the Mega32, increase its ease of use, and provide information freely to anyone who wishes to expand on our ideas and designs. We hope that kaOS improves people's understanding of the Mega32 and ways that it can be used.
It is our intention that the ideas produced in creation of this product be used by students and colleagues to further their technological understanding.