A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-03282008-133712


Type of Document Dissertation
Author Sallai, Janos
URN etd-03282008-133712
Title Compiler-assisted concurrency abstraction for resource-constrained embedded devices
Degree PhD
Department Computer Science
Advisory Committee
Advisor Name Title
Janos Sztipanovits Committee Chair
Akos Ledeczi Committee Co-Chair
Miklos Maroti Committee Member
Sandeep Neema Committee Member
Xenofon Koutsoukos Committee Member
Keywords
  • multithreading
  • compilers
  • embedded systems
  • sensor networks
  • event-driven systems
  • Programming languages (Electronic computers)
  • Embedded computer systems -- Programming
  • Sensor networks -- Data processing
Date of Defense 2008-03-26
Availability unrestricted
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).

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  sallai-dissertation.pdf 934.86 Kb 00:04:19 00:02:13 00:01:56 00:00:58 00:00:04

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LITS.