[EMSOFT’22 Best Paper ] Tinkertoy: Build your own operating systems for IoT devices

The Evolution of IoT: Diverging Application Requirements

The Internet, long the domain of large and/or expensive devices, is now so pervasive that it is possible for tiny devices ranging from fitness trackers to doorbells to be interconnected, forming a bridge between the physical and digital worlds. Unfortunately, general-purpose operating systems, such as Windows and Linux, cannot run on these tiny devices that have limited hardware resources. Instead, they frequently run special-purpose embedded operating systems. However, the range of capabilities of these small devices is immense, and their wildly different application requirements have posed a new challenge in building system software and led to the birth of many different embedded operating systems, such as Contiki and FreeRTOS. We propose an alternative solution to address these heterogeneous requirements. Tinkertoy is a set of components that allows developers to choose the right set and assemble a custom system for their applications. Our assembled system consumes up to four times less memory and has comparable performance to other embedded operating systems.

Building Application-Specific IoT Operating Systems Easily with Tinkertoy

Tinkertoy is composed of ten modules, shown in Figure 2, which can be found in a conventional operating system. However, we provide them as configurable building blocks so that developers can customize the behavior of each module easily. Specifically, some modules are divided into components, so developers can 1) switch one of those components to another prebuilt one, 2) assemble a component from our building blocks or 3) create a new component by providing their own implementation. For example, a scheduler is composed of three components, Policy, Event Handler, and Task Constraints. The policy component manages the ready queue reflecting whether a scheduler is prioritized, so we could replace a FIFO queue with a priority queue to make a prioritized scheduler. The event handler component allows one to define which task events a scheduler can respond to and how it should respond. One can assemble an event handler component from a list of standard event handlers, such as those designed for a preemptive scheduler, or implement a new one that demotes a task on a timer interrupt. Once developers finish customizing each component, they assemble the module back from these components and similarly assemble the kernel from those modules.

Leveraging Programming Language Features to Assemble Efficient and Reasonable Kernels

Our goal is to create flexible building blocks for kernel modules without sacrificing runtime performance while ensuring that these modules can still be reasonably assembled into a kernel. We highlight three C++ language features that we use to make our building blocks highly reusable, easily composable, and reasonably flexible. 

To begin with, we encapsulate some of the standard building blocks as a functor, which is a C++ class that overloads the function call operator and has all the benefits of an ordinary class. Secondly, we exploit C++17’s fold expression to assemble a new building block or a component from existing ones at compile time. For example, one can use the functor Paper Builder in Figure 3 to build a paper from an arbitrary number of sections, each of which is a functor that returns a string. Lastly, we heavily use templates to capture the genericity of kernel modules whose mechanisms are, in fact, independent of other modules. For example, on some systems, a scheduler schedules processes, while on others, it schedules threads, so its design should be agnostic to the object to schedule, but a specific instance of a scheduler should be constrained to schedule objects of a specific type. For example, a priority-based scheduler must know how to reorder tasks by their priority level, so we use C++20’s concepts to require the task type to overload the three-way comparison operator. 

We leverage these C++ features to write concise and efficient code, but we also want to emphasize that C++ is not the only choice. In fact, any languages that provide the right features would be fine. For example, Rust is gaining popularity in system programming, and its type trait mechanism provides functionality similar to C++ concepts.

Achieving Small Memory Footprint and High Performance

We want to know how much effort it takes one to assemble a custom kernel for a particular IoT application and how the memory footprint and runtime performance compare to other popular IoT operating systems, so we built an automatic watering system that requires three different kinds of kernels, 1) a monitor kernel for applications that fetch the soil moisture level, 2) an actuator kernel for applications that controls the water gate, and 3) a gateway kernel for applications that acts as a transparent proxy, translating CoAP messages to HTTP messages and vice versa. We chose these three kernels carefully to reflect first- and second-generation sensor network operating systems, and emerging third-generation systems that run on intelligent IoT devices, and we were able to assemble each of them in less than 200 lines of code. 

We measure the flash and the memory footprint and find that the assembled kernels, on average, consume 4 times less memory than other popular IoT operating systems, because all the data structures and functions in the assembled kernel are designed specifically for a particular application and, therefore there is no unused code at all. We also measure the runtime performance of our gateway kernel by calculating the amount of time it takes the application to translate a single CoAP request message and find that the assembled kernel does not have a performance penalty.

Conclusion

We present Tinkertoy, a collection of components that let you build custom operating systems for tiny IoT devices, but there remain many avenues for future work, such as adding support for multithreaded kernels, providing device drivers, exploiting hardware isolation mechanisms, and synthesizing kernel modules with respect to formal specifications. Once we have more building blocks, we believe that Tinkertoy will be suitable for a richer set of applications, and we hope that you will find it a great platform on which to build exciting next-generation IoT applications.

Authors: Jerry Wang and Margo Seltzer are with the Systopia Lab, Department of Computer Science, University of British Columbia.

Disclaimer: Any views or opinions represented in this blog are personal, belong solely to the blog post authors and do not represent those of ACM SIGBED or its parent organization, ACM.