Developing Embedded Multi-threaded Applications with CATAPULTS, a Domain-specific Language for Generating Thread Schedulers

Matt Roper

roper@cs.ucdavis.edu

University of California, Davis

Overview

Introduction

Design

Example Scheduler

Implementation

Future Work

Introduction

Embedded control systems generally handle several concurrent tasks

Threads (either cooperative or preemptive) are a popular tool for handling such concurrency

Scheduling algorithm has a significant impact on overall performance of system

The Problem

Problem: thread scheduler not a replaceable component

Highly tuned for the general case, but not for a given application

Built-in means (e.g., priorities) cannot represent all application-level understanding of thread semantics

Thread scheduling should be transparent to the application – explicit scheduling is likely non-portable

Manually hacking schedulers is difficult and error-prone

Solution: CATAPULTS

CATAPULTS: a Domain-Specific Language (DSL) for developing thread schedulers

Scheduling logic is now collected into a single, easily replaceable component instead of spread across several files

Translator for scheduler specification warns about common scheduling mistakes

Scheduler compiler can generate different backend code for different threading libraries

Scheduling Logic

Overview

Introduction

Design

Example Scheduler

Implementation

Future Work

Overview of Scheduler Parts

Per-thread attributes

Global data section

Event and query handlers

Application imported data section

Per-thread imported data section

Design Goals

C/Java-like language chosen for ease of programming by application programmers

CATAPULTS was designed with three primary goals in mind (performance of generated schedulers is an implicit goal):

modularity

error prevention

portability

Modularity

Developing schedulers is hard, partially because scheduling logic is cross-cutting

All actions that manipulate thread data structures must be examined when replacing a scheduler

E.g., modifying the GNU Pth scheduler requires changes to more than 20 files

Non-scheduling functions often make assumptions about scheduling structures or behavior

E.g., all ready threads exist on a single, specific queue

CATAPULTS separates scheduling from other responsibilities of the threading library

Error Prevention

Thread libraries often written in C or assembly

great power, but mistakes in scheduling logic easy

duplicating a reference to a thread on multiple lists (e.g., ready list and suspended list)

losing all references to a thread

scheduling conditions are difficult to reproduce so mistakes are especially hard to track down

Thread Collections

CATAPULTS provides a few simple (but sufficient) container types: stack, queue, pstack, pqueue, and threadref

CATAPULTS helps prevent errors through a simple invariant (but does not guarantee safety)

Invariant: each thread is in exactly one container at a time

Thread Transfers

Special transfer operator (=>) moves threads from one container to another and guarantees invariant

Static analysis attempts to determine whether source container is empty or destination threadref is full to catch mistakes at compile time

Runtime checks are performed on transfers that cannot be verified statically

Portability

Multiple CATAPULTS backends for different threading libraries

Useful for prototyping/simulation of embedded applications

Some minor changes to scheduler specification may be necessary when porting to a more featureful threading library

Verbatim Code

Sometimes functionality is more important than portability

Verbatim code (statements or expressions) allow use of native programming language directly

Useful for making system or library calls that aren't available in CATAPULTS (e.g., rand())

Anything that can be hardcoded directly can be included in a CATAPULTS scheduler

Importing Application Variables

Application variables can be made available to scheduler to help guide scheduling

Primarily used to read application values, although can also be used to modify application variables to alter application behavior

Two types of imports

application global imports

per-thread imports

Importing Application Variables

Tradeoff: tighter coupling, but greater potential performance gains

Imported variables not necessary for all applications

Switching generic schedulers can improve performance

Order of thread creation can be used to determine thread purpose

Overview

Introduction

Design

Example Scheduler

Implementation

Future Work

Example Scheduler

CoW Embedded Webserver

Example Scheduler

Application-specific knowledge can be used to write a more efficient scheduler:

Dynamic C TCP sockets are only updated after a tcp_tick() call drives them

tcp_tick() is only called by the TCP thread in this application

blocked (reading/writing/listening) sockets will make no progress until after the TCP thread has run

Example Scheduler

scheduler cow {

thread {

int state; // running, suspended, blocked

int threadclass; // handler, tcp, timeout

int action; // reading, writing, listening, etc.

}

data {

threadref current;

// queues for ready, suspended, reading, writing, listening

queue RQ, SQ, READQ, WRITEQ, LQ;

const int HANDLER = 1, TCP = 2, TIMEOUT = 3;

const int READY = 1, SUSPENDED = 2, BLOCKED = 3;

const int WORKING = 1, LISTENING = 2, READING = 3, WRITING = 4,

CLOSING = 5;

}

Example Scheduler

scheduler cow {

thread {

int state; // running, suspended, blocked

int threadclass; // handler, tcp, timeout

int action; // reading, writing, listening, etc.

}

data {

threadref current;

// queues for ready, suspended, reading, writing, listening

queue RQ, SQ, READQ, WRITEQ, LQ;

const int HANDLER = 1, TCP = 2, TIMEOUT = 3;

const int READY = 1, SUSPENDED = 2, BLOCKED = 3;

const int WORKING = 1, LISTENING = 2, READING = 3, WRITING = 4,

CLOSING = 5;

}

Example Event Handlers

event schedule {

RQ => current;

dispatch current;

}

event switch_out {

threadref iterthr;

// What type of thread just finished running?

if (current.threadclass == TIMEOUT) {

current => RQ;

} else if (current.threadclass == TCP) {

// Just ran the TCP thread, need to see if we have any new

// progress on our threads that were working.

foreach iterthr in READQ {

if ((* sock_bytesready(iterthr->userdata) *) > 0 ||

(* sock_alive(iterthr->userdata) *) == 0 )

iterthr => RQ;

}

// continued on next slide...

Example Scheduler (cont.)

foreach iterthr in WRITEQ {

if ((* sock_tbused(iterthr->userdata) *) == 0 )

iterthr => RQ;

}

foreach iterthr in LQ {

if ((* sock_established(iterthr->userdata) *) != 0 ||

(* sock_alive(iterthr->userdata) *) == 0 )

iterthr => RQ;

}

current => RQ;

} else { // handler thread

if (current.action == READING) current => READQ

else if (current.action == WRITING) current => WRITEQ;

else if (current.action == LISTENING) current => LQ;

else current => RQ;

}

}

Performance Results

4 Handler Thread Case:

8 Handler Thread Case

Performance Discussion

Always provides improvement in 4-handler case, but not in 8-handler case when very busy

part of benefit comes from removing blocked threads (e.g., listening threads) from ready queue consideration; when server is saturated LQ is almost always empty

with more handler threads, it takes longer to get back to the TCP thread; more likely changes will have happened to move threads out of READQ, WRITEQ, etc. and back into RQ

Performance Results (cont.)

Results from weather station example; run until 10,000 calculations are performed

12.6% performance benefit at the expense of 12.7% increase in code size

Overview

Introduction

Design

Example Scheduler

Implementation

Future Work

Current Implementation

Frontend Translator

GNU Pth backend (PC, POSIX)

Dynamic C backend (embedded Rabbit processors)

Frontend Translator

Simple static analysis checks for common errors or potential optimizations:

presence/absence of threads in a container

failure to store event handler parameters

failure of query to return a value or event to produce a side effect

If static analysis of container contents not possible, runtime checks are inserted into generated code

Dynamic C backend (Rabbit)

Generates an entire customized version of cmthread.lib, our custom threading library for Dynamic C

Related Work

Bossa

domain-specific language specifically for Linux kernel schedulers

safety is #1 goal

Linux pluggable CPU scheduler framework

kernel patch to Linux

allows scheduling code to be collected into a single, easily replaceable module

schedulers still written directly in C

Related Work

Bossa

domain-specific language specifically for Linux kernel schedulers

safety is #1 goal

Linux pluggable CPU scheduler framework

kernel patch to Linux

allows scheduling code to be collected into a single, easily replaceable module

schedulers still written directly in C

Overview

Introduction

Example Scheduler

Design

Implementation

Future Work

Soft Realtime Enhancements

Requirements:

builtin time datatype

event failure

Obstacles:

CATAPULTS must estimate scheduler execution time

must also be able to analyze application code and estimate Worst Cost Execution Times (WCET) of tasks to be scheduled

Conclusion

CATAPULTS: A Domain-Specic
Language for developing thread
schedulers

Goals: Modularity, error prevention, and portability

more motivation earlier on

- numbers

- examples

new insights

Make clear that this is for user-level threads on systems that break out user/kernel

Performance goal is implicit

Mention Pth change count earlier to motivate?

Describe what these errors all break, then declare invariant on next slide?

More specific terms? Maybe “data flow?”

a = (* rand() *)

{*

printf(“FOO”);

*}

Read-only vs read-write imports

Size?

Related work on algorithms, or static analysis

2005-05-23T10:31:31