XMK Operating System Overview

Contents

1      Introduction.. 3

1.1        What is XMK?. 3

1.2        What XMK is not?. 3

2      Overview... 3

3      Getting Started with the XMK Scheduler Package.. 5

3.1        Booting your target board.. 5

3.2        Configuring the XMK Scheduler.. 5

3.3        Run time.. 8

4      Getting Started with the APL Package.. 10

4.1        Booting your target board.. 10

4.2        Configuring APL.. 12

4.2.1     Platform Configuration. 12

4.2.2     Application Configuration. 12

5      XMK Scheduler Package in Detail.. 13

5.1        Philosophy.. 13

5.2        Threads. 14

5.2.1     Terminating Dynamic Threads. 14

5.3        Thread Scheduling.. 14

5.3.1     Thread Handles and Thread Priorities. 14

5.4        Interrupts. 15

5.4.1     Stack Memory. 16

5.4.2     Nesting vs. Levels. 16

5.5        Thread Synchronization.. 17

5.6        Mutual Exclusion.. 17

5.7        Priority Inversion.. 18

5.8        Error Handling.. 18

5.9        Porting.. 18

6      APL Package in detail.. 19

6.1        Philosophy.. 19

6.2        OS Abstraction Layer.. 19

6.2.1     Factories. 19

6.3        Hardware Abstraction Layer.. 19

6.4        Porting.. 20

7      Appendix -- Directory Structure.. 21

 

1       Introduction

eXtreme Minimal Kernel (XMK) is a preemptive multithreading operating system for microcontrollers.  XMK was designed from the ground up to be very small with respect to ROM, RAM and CPU processing resources.  The first targeted platforms were 8bit microcontrollers with only 4K to 8K of ROM and 512 bytes of RAM.  XMK has since been scaled up to 16bit and 32bit platforms.  Originally it was only a preemptive scheduler with thread synchronization primitives.  Now it includes such features as mailboxes, memory pools, file descriptors, hardware device drivers, and TCP/IP networking.  Even as XMK has expanded its functionality and scope, it has maintained its extreme minimal philosophy and footprint.  Its minimum configuration[1] is still less than 340 bytes of ROM and 18 bytes of RAM.

 

1.1      What is XMK?

• Small. XMK was specifically designed to run on microcontrollers using on the only onboard ROM and RAM.
• Configurable. The application only includes the kernel services that are needed.
• Scalable. XMK will run on virtually any platform, 8bit, 16bit, and 32bit processors.
• Portable. XMK is written in C with only a small amount of target specific assembler for speed, efficiency, and access to OS related instructions (e.g. trap, interrupt enable/disable).
• Free. The source can be used freely for commercial and proprietary applications (BSD licensing agreement).

1.2      What XMK is not?

• NOT a Board Support Package (BSP). The burden of defining the vector table, C start-up code, booting the board, initializing/configuring RAM, etc. falls on the developer and/or the target's development system.
• NOT a Debug/Run-time environment.  Targets must be loaded and debugged with the tools supplied by their respective development system.
• NOT a C/C++ Run-time Library replacement.  If the C/C++ Run time libraries are needed, they must be provided by the target's development system.

 

2       Overview

The XMK operating system is divided into two packages.  The first package, XMK Scheduler[2], includes only the core scheduler and kernel interfaces.  This package provides the preemptive scheduler, threads, and thread synchronization primitives.  The second package, the Application Programming Layer, is a kernel and platform independent library that provides interfaces such as inter-thread communications, heaps, memory pools, file descriptors, networking, etc.  Figure 1 shows the relationship between the XMK Scheduler and APL packages. 

 

Figure 1 - XMK Scheduler/APL Layering

 

You will notice a thin orange section that is not labeled.  This orange section is the Operating System Abstraction Layer defined by the APL package.  The OS Abstraction layer is what provides APL with its kernel independence.  Since APL was original created to support XMK, the implementation of the OS Abstraction layer is simply a mapping of APL names to XMK Scheduler names.  The mapping does not add any code or run time overhead.  While, APL was designed with XMK in mind, it supports other Kernels/RTOSs.  For instance, both Windows and Linux/POSIX are supported as user applications.  This allows applications written to use the APL interfaces to be transparently ported to other operating systems and platforms, thus facilitating the development of applications on a PC workstation before moving to an embedded target. A good example of this is the multi-threaded embedded web server[3] application.  The web server runs under Linux or on an embedded target board without any modification to the application itself.  The executable images require different operating system code and low-level device drivers for each platform, but the application code itself is not modified nor does it use  #ifdef statements to conditionally compile the applicaiton.  Figure 2 shows the APL layering independent of a specific OS.

 

Figure 2 - Formal Layering

 

It is important to note that both packages can be used independently from each other.  The XMK Scheduler package has no dependencies on the APL package.  If you just need a micro-sized preemptive scheduler and nothing else, then forget about APL and just use the XMK Scheduler package.  Also, if you have any existing application that is written for the XMK operating system and you want to move to another RTOS, then keep the APL package, and replace the XMK Scheduler with your new RTOS.  You only need to implement the OS Abstraction layer for the new RTOS.

 

Note on terminology:  XMK is a generic term used to describe the entire XMK operation system, including both the XMK Scheduler and APL packages.  The term XMK is also used for referencing just the XMK Scheduler package.  This is an unfortunate side effect of XMK’s evolution from a simple scheduler to a full featured RTOS.

 

3       Getting Started with the XMK Scheduler Package

The XMK Scheduler is a static scheduler, in that it is statically linked with the application at compile time.  A single executable image is then downloaded to the target.  In addition, the XMK Scheduler assumes a single memory space that is shared by the kernel and the application.  Caution: a way-ward application can corrupt the Scheduler’s memory and crash the system.

 

3.1      Booting your target board

Getting your board up and running is the responsibility the developer.  The XMK Scheduler does not provide any assistance with this stage of the development cycle[4].  Before attempting your first XMK Scheduler application you will need to create a template application that does the following:

• Creates and populates the vector table with the RESET vector and a Timer interrupt.  The timer interrupt will be eventually be used as the system tick for the XMK Scheduler.
• On reset, the boot code configures all of the necessary MCU registers, BUS controller(s), external RAM, peripherals, etc. that are needed for minimum operation of the target board.
• Runs the C start-up code that is responsible for initializing the DATA and BSS segments.  This is very important since the XMK Scheduler assumes that all variables in the BSS segment are initialized to zero on boot-up.
• Verify the period/frequency of your periodic timer interrupt.

 

The complexity of the tempalte application depends on your particular target and your compiler.  Which compiler you use dedicates how you build your vector table, linker scripts, etc.

 

3.2      Configuring the XMK Scheduler

All the major kernel services in the XMK Scheduler are configurable so that the application only includes what it needs and no more.  The configuration the XMK Scheduler is a two-step process.  The first step is done via a global header file: xmkcfg.h.  The following code listing is for the semaphore-with-timeouts test application running on Atmel’s STK501 eval board with an ATmega128 microprocessor.

 

Listing 1 - Example xmkcfg.h

 

There are four steps involved in the configuration.  The content of each step is straight forward and is dictated by the required services, processor platform, and target board.  There are two rules for creating your xmkcfg.h header file.

• Do the steps in the order listed in the example.
• Always include “xmk/config/resovle.h” after selecting the kernel service in step 2.

 

The second step in configuring the XMK Scheduler is to compile and link the services selected in the xmkcfg.h header file.  It is important build only the source directories that corresponded to the compile switches defined in xmkcfg.h.  This is due to the fact that several kernel services have different implementations based on the configuration desired.  The XMK Scheduler provides a mapping of source directories to kernel services.  There are two sets of mapping, one for platform independent kernel services, and the second is for platform specific kernel support.  The current mapping for platform independent services can always be found in file src/xmk/config/services.b.  The current mapping for platform specific support can be found in the files:  src/xmk/config/<mcu-vendor>/pal-<mcu>-<compiler>.b.  Where mcu-vendor, mcu, and compiler define your specific target platform.  Examples of both mappings are listed below.

 

Listing 2 – Example Platform Independent Source Directories

 

Listing 3 – Example Platform Specific (H8sa/GCC) Source Directories

 

3.3      Run time

As stated above, the developer is responsible for providing the initial boot-up and target initialization code.  The kernel can be only started after:

1. The C start-up routines have been run.
2. Xmk_initiailize() has been called.
3. And at least one static thread has been created using Xmk_createThread().

Important: the application must leave interrupts disabled during the entire start-up sequence.  The Scheduler will enable interrupts as part of its start sequence when Xmk_start() is called.

 

The code listings below provide a trivial but complete example for creating a multi-threaded application.  The example code is for Atmel’s STK501 eval board with an ATmega128 microprocessor.

Listing 4 - Example Application - main.c

 

Listing 5 - Example Application - xmkcfg.h

 

4       Getting Started with the APL Package

The Application Programming Layer package provides more sophisticated and abstract interfaces than the XMK Scheduler and synchronization primitives.  The reason for this two layer approach is to allow the APL code to be reused on non-XMK platforms.  APL itself is divided into two sections, basic and multi-threaded.  The interfaces and source code in the basic section assume a single threaded model and have few or no dependencies on the actual target platform.  The basic section has no dependencies on the multi-threaded section. The multi-threaded section contains interfaces that aid in multi-threaded programming and/or require the existence of a multithreaded scheduler.  The multi-threaded section is dependent on the basic section. 

 

Note on terminology:  The term APL is used to describe the entire APL package.  It is also sometimes use to describe just the basic section of APL.  The term APLMT refers specifically to the multi-threaded section of APL.

 

4.1      Booting your target board

The APL package is initialized separately from the XMK Scheduler package.  In addition, the APL Basic section is initialized separately from the APL Multi-Threaded section.  The order of initialization is based on who is dependent on whom.  For example, the APL Multi-Thread section is dependent on the APL Basic section and the platform’s kernel; so it can not be initialized till both the APL Basic section and the Kernel have been initialized. The following pseudo code demonstrates two possible and valid start-up sequences. 

Listing 6 - APL Startup Seqeuence#1

Listing 7 - APL Startup Seqeuence#2

 

4.2      Configuring APL

Numerous APL interfaces require configuration and/or setup information at compile time.  This configuration information is divided into two categories.  One is platform configuration.  Platform configuration is information that is dictated by your target platform.  For example, the APL data type AplSize_t needs to large enough to contain an offset that can reference the entire memory space of the processor.  On a MCU that is limited to 64K of total memory, AplSize_t is defined as 16bits.  On other platforms, AplSize_t is defined as 32 bits.  The second category is application configuration.  This allows individual applications to customize the behavior and resources of the interfaces at compile time.

 

4.2.1    Platform Configuration

The platform configuration is done via header files.  Any interface that requires platform information always includes a platform header file.  For example:  The header file for the types interface contains the statement: “#include “platform/types.h”.  It is then the responsibility of the application’s build script to set the header include path correctly so that the appropriate platform/ directory is included.  Note: not all platform header files need to be in the same platform/ directory.  There can be many platform/ directories as long as there is one and only platform header file per interface.  The following example is from the aplmt-itc-large test project running as a POSIX user application.

 

 

4.2.2    Application Configuration

The application configuration is done via preprocessor compile switches and defined values contained in a single header file: aplcfg.h. The application is responsible for the contents of this file.  Typically the aplcfg.h file resided in the project’s root source directory, but it can be located anywhere.  The follow is an example APL configuration file.

Listing 8 - Example aplcfg.h

 

Note: In general, do not include other header files in aplcfg.h.  Almost all of the APL header files are directly or indirectly dependent on the aplcfg.h header file.  Any header file(s) that aplcfg.h is dependent on, so then are the APL header files.

 

5       XMK Scheduler Package in Detail

5.1      Philosophy

The first design requirement is extreme minimal footprint.  All new features and/or interfaces added to the XMK Scheduler are implemented such that they do not increase the ROM and RAM usage of the fundamental scheduler. The goal is that the application does not incur any overhead for services/features it does not use.  On the negative side, the extreme minimal design goal is responsible for the complexity[5] of the scheduler internals.

 

5.2      Threads

The XMK Scheduler provides two types of threads, static and dynamic.  Static threads are threads created before the Scheduler is started and are never terminated[6].  Dynamic threads are threads created only after the Scheduler is running and they can be terminated.  Static and dynamic threads can be used together in the same application.  By default, only static threads are allowed.  Dynamic threads are enabled with the configuration switch:  USE_XMK_EXTENDED_THREADS.

 

5.2.1    Terminating Dynamic Threads

The XMK Scheduler does not provide any method to forcibly terminate or a kill a dynamic thread.  A thread is only deleted and/or terminated with its start() function returns.  This is intentional!  Deleting threads has always been problematic from an application design point of view, because of the resources that need to be released by the dying thread.  If a thread is externally killed, then there is no way to ensure that any resources (memory, semaphores, etc.) it has acquired will be released on its demise.  Threads that voluntarily terminated themselves can ensure[7] that proper clean-up is done before ending.

 

5.3      Thread Scheduling

There are three basic approaches to thread scheduling: cooperative, preemptive, and round-robin. Cooperative scheduling requires that individual threads 'play-nice' and periodically yield control of the CPU to other threads.  Preemptive scheduling forces a thread/context switch whenever there is ready-to-run thread that has higher priority than the currently running thread. Preemptive scheduling requires that all threads be assigned a priority. Round-Robin scheduling is where control of the CPU is time-multiplexed across N threads.  For example, each thread is allowed up to 10msec of run time before the kernel forces a thread/context switch to the next ready-to-run thread.  Round-robin scheduling and preemptive scheduling are often combined together.  The XMK Scheduler currently only supports preemptive scheduling, although there are plans to support round-robin scheduling in the future.

 

5.3.1    Thread Handles and Thread Priorities

The XMK Scheduler requires each thread to have a thread handle and a scheduling priority.  Conceptually thread handles and thread priorities are completely independent of each other.  However, to simplify and to reduce the overall footprint, the XMK Scheduler by default combines the two.  When using the default thread scheduler, a thread's priority is also the thread's handle and can be used interchangeably.  An alternate thread scheduler is available that decouples a thread's handle from the thread's priority (switch: USE_XMK_SCHPRI_SCHEDULER).  The alternate thread scheduler, known as the Priority Scheduler, is more flexible, but costs more in terms of RAM and ROM.  The following table lists the different features of each thread scheduler.

 

 

Note: It is recommended that the application treat thread handles and thread priorities as independent entities even when using the default thread scheduler.  This approach makes the application independent of which thread scheduler is used and facilitates being able to change thread schedulers as the needs of the application change over time.

 

5.4      Interrupts

The XMK Scheduler requires a hook for all interrupt vectors where the corresponding interrupt service routine can cause a thread context change.  If the application has an interrupt that is never associated with a potential context change, then the XMK Scheduler does not need to be aware of the interrupt. The XMK Scheduler hooks into an interrupt vector, by providing the raw interrupt-service routine to allow interaction with the kernel.  The XMK Scheduler ISR stubs in turn calls the application's interrupt-service-routines. The XMK Scheduler ISR stubs are responsible for the mechanics of saving, switching, and restoring thread contexts on entry and exit from interrupts. When the building the vector table, the entries need to reference the XMK Scheduler ISR stubs, not the applications interrupt service routines.

 

Since ISRs are very target specific, the application must create the actual the XMK Scheduler ISR stubs.  XMK makes this step easier by providing template source files for creating both non-nested and nested XMK Scheduler ISR stubs.  These templates files can be found under the src/xmk/platform directory tree.

 

5.4.1    Stack Memory

A single stack is used for all interrupt processing.  This interrupt stack is separate from all of the individual thread stacks.  This approach provides significant RAM savings, especially as the number of threads increases.  However, this means that all interrupt processing must be handled by the XMK Scheduler so the interrupt stack can be swapped in and out appropriately. Note:  The requirement of that all interrupt processing be handled by the XMK Scheduler is not an absolute requirement.  The application can choose to bypass the XMK Scheduler's interrupt handlers if it meets the following conditions:

• The application's custom ISRs make no XMK Scheduler calls.
• The application provides sufficient stack space for all application stacks to handle the stack usage of the application's custom ISR routine(s).

 

5.4.2    Nesting vs. Levels

There are two issues with respect to interrupts: The first issue is multiplexing and/or nesting interrupts.  Nesting interrupts occurs when during the executing of an interrupt service routine, interrupts are enabled.  This allows higher priority interrupts to run while deferring the completion of the original interrupt. The second issue is multiple priority levels with respect to enabling/disabling interrupts.  Some processors instead of having a single bit for the global interrupt mask, have multiple bits than can be used to selective disable/enable interrupts based their assigned priority levels.  The XMK Scheduler supports non-nested interrupts, nested interrupts, but not multiple priority interrupt masks[8].  By default, the XMK Scheduler is configured only for non-nested interrupts.  Support for nested interrupts is enabled by the configuration switch: USE_XMK_NESTED_INTERRUPTS.

 

5.5      Thread Synchronization

The XMK Scheduler currently supports two thread synchronization primitives, counting semaphores and thread semaphores.  It is assumed that the reader is familiar with counting and binary semaphores.  Thread semaphores are a specialized form of a binary semaphore.  Listed below are the features of a thread semaphore.

• The same basic wait() and signal() methods of a binary semaphore.
• One and only one thread can wait on the thread semaphore.
• Thread Semaphores are bound to individual threads.  Only the thread that the semaphore is bound-to can call the wait() method.  However, there are no such restrictions on the signal() method.
• Every thread has one Thread Semaphore.
• Thread semaphores can not be used for mutual exclusion.

 

Note: the XMK Scheduler provides signal() methods for both counting and thread semaphores that can be called from the context of an interrupt service routine.

 

5.6      Mutual Exclusion

Concurrently executing threads often share data structures. To protect shared data structures from race conditions and/or corruption, individual thread access to the data should be mutually exclusive.  The following primitives can be used to implement mutual exclusion:

• Semaphores as defined by Dijkstra.
• Mutexes.
• Temporarily disable/enable concurrence.

 

Listed below are the mutual exclusion (MX) primitives provided by the XMK Scheduler:

• Disable/Enable Interrupts.  Disabling interrupts for a short period of time will provide the application with a MX region that protects data shared across threads as well as interrupt service routines.  However, this approach is bit drastic and can have undesired effects on interrupt latencies and/or real-time performance.
• Disable/Enable Context Switching.  Disabling thread switching for a short period of time will provide the application with a MX region that protects data shared across threads only.  While this approach is less drastic the disabling/enabling interrupts, it still impacts the performance of the application by increasing context-switch latencies.
• Counting Semaphores.
• Mutexes.  Currently the Mutex API is implemented as aliases to the Semaphore API.

 

5.7      Priority Inversion

The following is a definition from www.usefulcontent.org:

 

 

The XMK Scheduler does not currently provide any mechanisms for preventing priority inversion.

 

5.8      Error Handling

Rudimentary error handling support is provided, but it is limited to the reporting of fatal errors.  The XMK Scheduler places the burden of handling fatal errors on the application.  This done for the obvious reason that only the application has the knowledge of what to do when a fatal error is encounter.  The XMK Scheduler  efines the method Xmk_fatalError() that is the responsibility of the application to implement.  The semantics of this method are such that the application can use it report fatal errors it encounters, not just the Scheduler.  See the header file src/xmk/thread.h for more details.

 

5.9      Porting

Porting the XMK Scheduler to a new platform is a straight forward process.  However, it does require the porter to be thoroughly familiar with the platform’s interrupt processing model and the compiler’s ABI for the platform (i.e. stack frame layout, volatile registers, etc.).   Note: A given port of the XMK Scheduler is dependent not only the target MCU, but what compiler is used.  A single MCU may have multiple ports.  Listed below is a brief outline of what is required when porting the XMK Scheduler.  More details can be found in the src/xmk/docs directory.

• Provide functions for enabling, disabling, and querying the processor’s global interrupt state.  Typically, these map to compiler intrinsic functions.
• Provide methods that perform the actual context switches.  Typically these are implemented in assembler.
• Generate template files for the XMK Scheduler interrupt service routine stubs.  Typically these are done in assembler.
• Perform a stack usage analysis on the platform specific code.  The stack usage is need so the XMK Scheduler can provide the application developer with minimum stack sizes.

 

6       APL Package in detail

6.1      Philosophy

APL has two primary design requirements, platform independence and minimal[9] resource usage.  The first, platform independence, is an absolute requirement.  The second, minimal resource usage, can be compromised when the two design requirements conflict. 

 

6.2      OS Abstraction Layer

The OS Abstraction layer is defined in the multi-threaded section the APL package.  The OS Abstraction Layer is collection of header files that define basic scheduling and kernel methods.  Other APLMT interfaces in turn, depend on the OS Abstraction Layer header files, not any concrete implementation.  It is at link time that the binding between the application code and the platform’s RTOS is made.  The only platform/RTOS specific code in the APL package is the different implementations of the OS Abstraction Layer. 

 

The OS Abstraction Layer contains all of the functionality as the XMK Scheduler package, but presents it in slightly different manner.  Details of the OS Abstraction Layer interfaces can be found in the src/aplmt/os directory.

 

6.2.1    Factories

A major issue when designing platform independent interfaces is how to create resource instances, i.e. how to create threads, semaphores, mutexes, etc.  To create a resource you need to know its how much RAM it needs.  Well, different platforms have different RAM requirements.  APL uses the factory pattern[10] to solve this problem.  Factories allow the application to use a fixed interface for creating a resource while the platform specific details are “hidden” inside the factory.  The factories themselves are platform specific and must be instantiated by the application.  Typically factories are instantiated very earlier in the start-up process so as to localize and/or isolate the platform specific code.  The actual implementation of the factories is part of the OS Abstraction Layer implementation.

 

6.3      Hardware Abstraction Layer

Platform independence involves more than just Scheduler/RTOS independence that is provided by the OS Abstraction Layer.  Accessing special function registers, on board peripherals, external devices, etc. is very platform specific.  APL uses the concept of a Hardware Abstraction Layer, or HAL, to solve this problem.  APL’s Hardware Abstract Layer is a little different from other software packages, in that it is defined on as needed basis.  When a new interface is created and it requires hardware access, then a set of HAL methods are created to support the needs of the new interface.  Another design goal of the HAL is not to put policy functionality into the HAL.  Every effort is made to design HAL methods as simply primitives and move the control logic up a layer.  For example:  APL contains interrupt driven, stream-based, blocking UART drivers.  The driver code for the interrupt routines is platform independent.  This works because of the structure of the HAL and due to that fact that UART semantics are fairly consistent across hardware vendors. 

 

Another side-effect of APL’s HAL design is that for a given interface, not all platforms are supported.  There are no requirements that platforms support all of the various HAL interfaces.  HAL support is a function of the platform’s hardware as well as development time for someone to write the code.

 

6.4      Porting

In theory porting APL is easier than porting the XMK Scheduler package.  This is certainly true when creating a new implementation of the OS Abstraction Layer (no assembly programming is required).  When porting the various HAL interfaces, the developer will need to have intimate knowledge of the hardware being supported.  Listed below is a high level outline of the steps required when porting the OS Abstraction Layer and/or HAL interfaces.  Additional porting details can be found in the src/apl/docs and src/aplmt/docs directories.

• Identify the platform specific requirements of the interface being ported.
• Create the platform header file that the original interface references and/or includes.  Also, you will need to publish the location of this configuration header file so that the application can properly construct its build scripts.
• Provide a correct implementation (this is the hard part).

 

Figure 1 - Source Code Directory Structure