Compiler-assisted concurrency abstraction for resource-constrained embedded devices

Abstract

The prevailing paradigm in the regime of resource-constrained embedded devices is event-driven programming. An event-driven application consists of a small runtime and a set of event handlers that execute in response to external stimuli. It is often required, though, that the reactive behavior depend not only on the type of the stimulus, but also on program state. Since neither the runtime nor the development tools provide explicit support for defining control flow that involves multiple event handler invocations, event-driven programs are often implemented as explicit state machines. However, this manual management of control flow is a tedious task, which commonly results in ad-hoc and unstructured code that is error-prone and hard to debug. In this work, I introduce TinyVT, a novel programming abstraction that fuses the intuitive linear control flow of thread-based concurrent programs with the memory efficiency and race condition free semantics of event-driven systems. With explicit language support for threads and blocking wait, TinyVT, an extension of the C language, creates a virtual threading abstraction on top of a lightweight event-driven runtime. Unlike traditional threading approaches where multithreading is provided by the operating system kernel or a user-space library, TinyVT's thread abstraction is provided by the language itself. Through source-to-source translation, TinyVT programs, defining conceptually concurrent threads, are automatically mapped to a single-threaded C code, which is efficient in terms of both computational overhead and memory usage. A common drawback of event-driven systems is that the lifetime of a local variable is limited to the execution context of the event handler in which the variable is declared. Consequently, variables that are accessed from multiple event handlers must be global or static, occupying static memory. To overcome this issue, I introduce a compiler-managed memory allocation technique that seamlessly provides C-style scoping and automatic allocation of variables local to a thread, eliminating the need for declaring global variables for information sharing between related actions. Explicit and formal specification of semantics is crucial to any programming language. I provide the operational semantics of TinyVT's language constructs using the Abstract State Machines (ASM) formalism, by building on an existing formal semantics specification of C. Also, to explore the behavior of software modules comprised of multiple threads, I investigate the compositional semantics of TinyVT threads by mapping them to a finite automaton based representation, the semantics of which is given in the Abstract State Machine Language (AsmL).