Application-specific User-level

Thread Schedulers

Qualifying Exam

June 1, 2005

Matt Roper

Overview

Introduction

Background

Example Scheduler

Design

Implementation

Proposed Work

Introduction

Threads are a popular model for concurrent applications

large Internet servers (Apache, MySQL, etc.)

medium-sized desktop applications (Mozilla)

small, resource-constrained embedded systems (weather monitoring control 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

Background

Example Scheduler

Design

Implementation

Proposed Work

Multi-threaded Applications

Two kinds of threads:

Kernel-level:

expensive context switches

schedued by OS; no
intra-app scheduling

User-level:

fast context switches

linked against app; possible to change scheduling

less OS bookkeeping; lower resource requirements

Overview

Introduction

Background

Example Scheduler

Design

Implementation

Proposed Work

Overview of Scheduler Parts

Per-thread attributes

Global data section

Event and query handlers

Application imported data section

Per-thread imported data section

Example Scheduler

Weather monitoring station

Several sensors (that run at different speeds)

A display that changes when temperature too high

Perform calculations while sensors and display are idle

Example Thread Attributes

scheduler example {

/*

* No thread-specific data other than thread

* state is required by this scheduler.

*/

thread {

int state; // new, running, suspended, etc.

}

threadimports {

// possible values are thread class constants

// defined in data section

int threadclass default 0;

}

Example Per-Thread Imports

scheduler example {

/*

* No thread-specific data other than thread

* state is required by this scheduler.

*/

thread {

int state; // new, running, suspended, etc.

}

threadimports {

// possible values are thread class constants

// defined in data section

int threadclass default 0;

}

Example Scheduling Data

data {

threadref current; // current thread

threadref next; // next thread (named yield)

stack NQ; // new threads

queue standard_sensors; // sensors

queue slow_sensors; // sensors monitored

// less frequently

threadref display; // display driver

queue calculations; // calculation threads

// Last time various thread types ran

int last_display, last_sensor1, last_sensor2;

const int UNKNOWNCLASS = 0,

SENSOR1CLASS = 1, SENSOR2CLASS = 2,

DISPLAYCLASS = 3, CALCCLASS = 4;

}

imports {

int temperature default 0;

}

Example Application Imports

data {

threadref current; // current thread

threadref next; // next thread (named yield)

stack NQ; // new threads

queue standard_sensors; // sensors

queue slow_sensors; // sensors monitored

// less frequently

threadref display; // display driver

queue calculations; // calculation threads

// Last time various thread types ran

int last_display, last_sensor1, last_sensor2;

const int UNKNOWNCLASS = 0,

SENSOR1CLASS = 1, SENSOR2CLASS = 2,

DISPLAYCLASS = 3, CALCCLASS = 4;

}

imports {

int temperature default 0;

}

Example “schedule” Event Handler

event schedule {

threadref tmp;

// Move new threads to their appropriate containers

// if we know what type of thread they are yet.

foreach tmp in NQ {

if (tmp.threadclass == SENSOR1CLASS)

tmp => standard_sensors;

else if (tmp.threadclass == SENSOR2CLASS)

tmp => slow_sensors;

else if (tmp.threadclass == DISPLAYCLASS)

tmp => display;

else if (tmp.threadclass == CALCCLASS)

tmp => calculations;

}

// Update last run times

last_display++; last_sensor1++; last_sensor2++;

// continued on next slide...

Example Scheduler (cont.)

if (|next| == 1) {	// Note: |x| = # of threads in x

// named yield?

next => current;

} else if (temperature >= 100 && last_display > 10) {

display => current;

last_display = 0;

} else if (last_sensor1 > 3 && |standard_sensors| > 0) {

standard_sensors => current;

last_sensor1 = 0;

} else if (last_sensor2 > 6 && |slow_sensors| > 0) {

slow_sensors => current;

last_sensor2 = 0;

} else {

calculations => current;

}

dispatch current;

}

Overview

Introduction

Background

Example Scheduler

Design

Implementation

Proposed Work

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

Arrays are also available, but are not considered “container”

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

Event parameters always statically checkable

First use of non-parameter container always dynamic, subsequent uses static

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 (as seen in earlier example)

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

Background

Example Scheduler

Design

Implementation

Proposed 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

GNU Pth backend (POSIX)

Pth is modified to load custom schedulers from shared libraries via dlopen()

Applications re-linked against modified copy of Pth

Application chooses scheduler at runtime based on contents of PTH_SCHED environment variable

Dynamic C backend (Rabbit)

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

Performance Results

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

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

Related Work (cont.)

superd

userspace daemon

coarse-grained process selection

goal is fairness between process groups

scheduler activations

OS mechanism that allows better interaction between kernel and user-level threads

intra-application scheduling is handled by user-level threading library

Related Work (cont.)

superd

userspace daemon

coarse-grained process selection

goal is fairness between process groups

scheduler activations

OS mechanism that allows better interaction between kernel and user-level threads

intra-application scheduling is handled by user-level threading library

Overview

Introduction

Background

Example Scheduler

Design

Implementation

Proposed Work

Proposed Work

Distributed threading systems

Enhancements for soft realtime scheduling

CATAPULTS framework metaprogramming

Distributed Threading

Potential advantages of custom schedulers:

assign threads to computing nodes that match their needs

different nodes can easily utilize different schedulers

porting to new hardware may become simpler if thread distribution is handled by scheduler rather than application

CATAPULTS translator can determine an efficient means of sharing scheduling data between nodes based on usage

Distributed CATAPULTS Initial Design

Computing nodes are grouped into “families,” which have a common local scheduling policy

“Distribution specification” describes the scheduler as a whole and incorporates local schedulers of several node families

Node Family Specification

Describes the local scheduling policy of all nodes belonging to the family

Each node family is declared in a separate file to make large schedulers more modular and encourage re-use

Event handler implementations can be omitted in which case a default implementation will be inherited from the distribution specification

Distribution Specification

Similar to existing CATAPULTS schedulers:

Declares collections of nodes – the same type of collections available for threads in a traditional scheduler (stack, queue, etc.)

Declares global variables that are accessible by the scheduler on any node via a DSM model

Provides default behavior of event handlers

Distribution Specification (cont.)

New concepts:

Provides logic to execute when new processing nodes enter the system or when nodes leave the system

Provides logic to decide which processing node should receive a newly created thread (for threading frameworks where this is appropriate)

Target Frameworks

Kaffe JVM – already includes its own internal threading library and uses RMI for distribution

DesCaRTeS – a runtime system for Dynamic C that provides SR-like functionality

Rthreads – can take regular Pthreads applications and make them implicitly distributed

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

CATAPULTS Metaprogramming

Problem: different threading targets have different “features” that require modifications to the CATAPULTS grammar; maintaining several forks of the CATAPULTS language is difficult

Solution: allow CATAPULTS grammar and frontend parser to be auto-generated from a threading specification that lists necessary features

Timeline

Does not include time for writing research papers or maintaining current implementation.

Conclusion

CATAPULTS: A Domain-Specic
Language for developing thread
schedulers

Goals: Modularity, error prevention, and portability

Future Work:

Distributed threading

Soft realtime scheduling

CATAPULTS metaprogramming

more motivation earlier on

- numbers

- examples

new insights

Vague, what kind of mistakes? What kind of warnings?

Kernel thread scheduling is out of our control

Advantages/disadvantages kernel vs user

Real world example

Quantitative motivation

Leak data back?

Size?

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

Compile against modified Pth

Related work on algorithms, or static analysis

2005-05-23T10:31:31