System Time

Location:

St. Louis, MO

Posted:

January 22, 2013

Contact this candidate

Resume:

Formalizing Meta-Programming Techniques to Reconcile Heterogeneous

Scheduling Disciplines in Open Distributed Real-Time Systems

Angelo Corsaro, Chris Gill, and Ron Cytron Douglas C. Schmidt

Department of Computer Science Electrical and Computer Engineering Dept.

Washington University, St. Louis, MO 63130, USA University of California, Irvine, CA 92697, USA

corsaro,cdgill,cytron @cs.wustl.edu abqf2d@r.postjobfree.com

Abstract autonomous vehicles that must collaborate to perform co-

ordinated maneuvers in support of time-critical missions,

In open distributed real-time and embedded (DRE) sys- such as reconnaissance, perimeter defense, and suppres-

sion of enemy air defenses. Likewise, QoS-enabled DOC

tems, different ORB endsystems may use different schedul-

ing disciplines. To ensure appropriate end-to-end applica- middleware will bene t commercial DRE systems, such as

tion behavior in an open architecture, DRE systems must distributed virtual reality applications, distributed multime-

enforce an ordering on activities originating in an endsys- dia collaboration systems, and massively-multiplayer on-

tem and activities that migrate there, based on the relative line persistent-world games.

Key challenges arising in these types of DRE systems in-

importance of these activities. This paper describes the

meta-programming techniques applied in Juno, which ex- volve communicating and enforcing the relative importance

tends Real-time CORBA to enhance the openness of DRE of various competitors (such as threads or operations on

CORBA objects) to ensure appropriate scheduling of sys-

systems with respect to their scheduling disciplines by en-

abling dynamic ordering of priority equivalence classes. tem resources (such as memory, CPU time, and network

We use the forthcoming OMG Real-Time CORBA 2.0: Dy- bandwidth) at a given point in time. Resolving these chal-

namic Scheduling Joint Final Submission (RT-CORBA 2.0 lenges is essential to building DRE systems that are simul-

JFS) to illustrate our techniques. taneously:

1. Open, i.e., system components can connect and inter-

Keywords: Real-Time and Distributed Systems, operate in a exible manner without having to be pre-

CORBA, Dynamic Scheduling, Meta-programming Archi- con gured statically; and

tectures.

2. Dependable, i.e., the system can preserve key end-to-

end QoS properties, such as timeliness and resource

1. Introduction constraints.

For example, mobile autonomous vehicles should be able

Emerging challenges: Distributed object computing to collaborate in a dependable and ef cient manner, despite

(DOC) middleware, such as CORBA, COM+, and Java the heterogeneity of their scheduling disciplines and imple-

RMI, shields developers from many complexities associated mentations. The forthcoming Real-Time CORBA 2.0: Dy-

with developing distributed systems. For example, DOC namic Scheduling Joint Final Submission (RT-CORBA 2.0

middleware allows applications to invoke operations on dis- JFS) [14] addresses some aspects of the challenges outlined

tributed objects without concern for object location, pro- above. For example, the RT-CORBA 2.0 JFS de nes a dis-

gramming language, OS platform, communication proto- tributable thread mechanism that has the following proper-

cols and interconnects, and hardware [7]. The maturation of ties:

DOC middleware speci cations and implementations over It can extend and retract its locus of execution1 to tran-

the past decade have greatly simpli ed the development of sition among ORBs while servicing an operation re-

open distributed systems with complex functional require- quest.

ments.

It contends with other competitors for the use of differ-

More recently, the emergence of quality of ser-

ent resources (such as CPU time, memory, or network

vice (QoS)-enabled DOC middleware, such as Real-

bandwidth) in the various ORBs it traverses through a

time CORBA 1.0 (RT-CORBA 1.0) [13], Real-Time

dynamic call graph.

Java [15], [2] and Distributed Real-time Java [9], will sim-

It contains certain scheduling information carried

plify open distributed real-time and embedded (DRE) sys-

across ORBs embedded in a GIOP service context and

tems with complex QoS requirements, such as stringent la-

tency, jitter, and dependability. For example, future combat 1 The locus of execution of a distributable thread represents the ORBs

systems will involve heterogeneous collections of mobile visited by the thread while servicing a remote method invocation.

1. Mapping of scheduling parameters: The RT-

End System (B)

CORBA 2.0 JFS does not de ne the mapping of scheduling

Running a Rate

Monotonic Scheduler

Computer

parameters when distributable threads pass through ORBs

Workstation

that are con gured with

Minicomputer

Heterogeneous scheduling disciplines or

Satellite dish

Server

Different scheduling parameters for the same schedul-

ing discipline.

For example, during a request s traversal through the dy-

End System (A)

Running an Earliest

namic call graph formed by a distributed thread execution,

Workstation

Deadline First Scheduler

one of the visited ORBs could be con gured using an earli-

est deadline rst (EDF) [12] scheduling discipline. An EDF

End System (C)

scheduler orders competitors according to the propinquity

Competitor Created at End-System (A) Satellite

Running a Generic

Comm. Tower

of their deadlines. Another ORB in the traversal could use

Value Based Scheduler

Competitor Created at End-System (B)

a value-based scheduling discipline [8], where every com-

Competitor Created at End-System (C)

petitor is characterized by a time-dependent function that

describes the value associated with the competitor at a given

Figure 1. DRE Systems with Competitors that

point in time. A value-based scheduler tries to maximize the

Migrate from System to System.

value gained by the system using information this function

provides.

In the RT-CORBA 2.0 JFS, when a distributable thread

used by ORBs visited by a distributable thread to en- traverses endsystems, its corresponding scheduling infor-

sure that the thread is processed at the appropriate pri- mation must be understood at each endsystem. The com-

orities end-to-end. position of scheduling disciplines used along the chain of

endsystems must therefore be semantically coherent, even

if the result is non-optimal. There is no existing standard,

For example, Figure 1 illustrates a representative DRE

however, that speci es how to provide interoperability be-

system in which three endsystems are running three ORBs

tween heterogeneous (but composable) schedulers. This

con gured with three different scheduling disciplines.

omission limits the openness of DRE systems using RT-

Threads are distributed across endsystems as a result of re-

CORBA 2.0 JFS middleware.

mote operation invocations or distributable thread migra-

tion.2 As a result, competitors originating on different 2. Scheduling information propagation: Another

endsystems contend for the same set of resources on each relevant issue that neither the RT-CORBA 1.0 speci cation

ORB endsystem. To adjudicate this competition, some type nor the RT-CORBA 2.0 JFS addresses is whether to update

of scheduling is required. scheduling information propagated on a hop-by-hop basis

RT-CORBA 1.0 speci es a Scheduling Service to relieve through a distributed call graph. Although this issue is not

application programmers of the tedious and error-prone task related directly to interoperability, the solution described in

of con guring scheduling properties on each end-system. this paper to enable interoperability can be used to propa-

This service is an optional part of the RT-CORBA 1.0 gate and update scheduling parameters end-to-end.

speci cation, however, so it may not be available for all

In this paper, we present a solution to the problems out-

RT-CORBA 1.0 ORBs. Moreover, the RT-CORBA 1.0

lined above by

Scheduling Service deals only with priorities, which under-

Formalizing the problem of interoperability in the con-

specify mappings of more complex scheduling properties

text of open DRE systems

(such as deadline) into an ordering of competitor execution

eligibilities. De ning formalisms to express different instances of

The RT-CORBA 2.0 JFS and the RT-CORBA 1.0 spec- the problem precisely and

i cation upon which it builds are the most advanced open

Providing a meta-programming architecture [20] that

standards that address static and dynamic scheduling in the

maps the formalized abstractions to a software archi-

context of open, QoS-enabled middleware for DRE sys-

tecture based on RT-CORBA.

tems. Neither speci cation, however, fully addresses the in-

Figure 1 outlines our solution approach in the context of

teroperability aspect of the challenges outlined above, due

CORBA. As shown in this gure, three endsystems are

to under-speci cation in the areas of:

con gured with three different scheduling disciplines. The

competitors initiated at endsystem (A) are square, those ini-

2 Threads at each endsystem are shown with a different shape, depend-

tiated at endsystem (B) are circular, and those initiated at

ing on the endsystem on which each originated.

endsystem (C) are triangular. To preserve the QoS proper- Schedulers grant competitors access to shared re-

ties requested by the competitors, we apply techniques that sources. The order in which competitors can access

reconcile a resource depends on scheduler disciplines and com-

petitor properties. Scheduling disciplines are formu-

1. The properties used by each scheduler to enforce QoS;

lated in terms of the properties they use to determine

and

the ordering of competitors. These properties can

2. The properties used by each competitor to express its therefore be viewed as an abstraction of the competi-

QoS requirements. tors for the purpose of scheduling. Since we focus

Our techniques enable an open architecture in which com- on dynamic systems, all our schedulers operate on-

petitors can traverse endsystems without concern for how line [4], rather than off-line [16].

QoS requirement are expressed. We also allow each ORB

The remainder of this section presents a formal model

endsystem to schedule competitors including those ini-

for properties, competitors, and schedulers. The advantage

tiated remotely by adapting the competitors properties

of creating a formal model is to enable heterogeneous ORB

for use by the ORB s local scheduler. We use a meta-

endsystems to exchange precise information about the prop-

programming architecture based on a two-level re ective

erties associated with individual competitors and sched-

middleware model [20, 18, 17] to implement the solution

ulers. This information allows each endsystem to transform

presented in this paper.

competitors properties and reconcile them for each ORB

Paper organization: The remainder of this paper is orga-

endsystem s scheduler.

nized as follows: Section 2 de nes a formal model for rec-

onciling heterogeneous scheduling disciplines in open dis-

2.1.1 Properties

tributed real-time systems; Section 3 presents Juno, which

is our meta-programming architecture for enhancing the

De nition 2.1 Let be the Universe of Properties. A

openness of DRE middleware and illustrates brie y how

generic element of is denoted by and is called a prop-

Juno implements the formal model de ned in Section 2;

erty type, or simply a property . Each property is

Section 4 compares our approach with related work; and associated with the following tuple:

Section 5 presents concluding remarks and outlines our fu-

ture research directions.

Where:

2. Terminology and Formalisms

1. is the domain of the property.

2. is the default value for the property.

This section de nes the terminology used throughout the

paper and motivates the assumptions that underly our work. %$

That is, given any property we denote its associated

The formalisms presented in this section are applicable to domain by, and its associated default value by .

any open DRE system. For concreteness, however, we focus

the examples in the context of RT-CORBA 1.0 [13] and the '&

Moreover, given a property we de ne a Tagged

(

RT-CORBA 2.0 JFS [14]. Domain of as:

# @897 5 4 &3 20 &# (

5 6 ) 1 )

2.1. Properties, Competitors, and Schedulers

CBA

(

Given any we denote the property of the tagged

5 GGE D A

We model an open DRE system as consisting of proper- D A

A HF

element by and its value by .

ties, competitors, and schedulers, which are de ned infor-

mally as follows: I

RT-CORBA3 An example of a property in RT-CORBA

Properties describe QoS attributes, such as a criticality is the deadline of a distributable thread. In this case, the

level, a deadline, or a constraint on jitter. We do not domain of the property is the time, which in RT-CORBA

restrict the domain of the properties, i.e., a property is represented as the integral type TimeBase::TimeT .

can be a function, which allows value and/or quality Other examples of properties in RT-CORBA include criti-

functions to be expressed as properties. cality (which distinguishes classes of real-time competitors)

Competitors denote entities that can contend for com- and the periodicity of activities.

mon system resources. Competitors expose properties

TRP

De nition 2.2 Given a set of n properties, :

that describe their features, such as their importance,

or QoS requirements, such as deadline or worst-case 3 Henceforth,

our use of the term RT-CORBA connotes both static

execution time. and dynamic scheduling capabilities.

cY aD`DD Y 7 V) U

b X W

At any point in time, any competitor has associated with

it the current value of its properties. This value is actually 6 4

We de ne the Compound Property Domain (CPD) as: an element of the Compound Property Domain of, and

0P y wxvT@v )@uit ( 'f C P qP @pf YhgVe U d

s r i F )i i8 f )

w GG

HFE D

will be indicated with .

Figure 2 shows schematically how the relation works.

In this gure, represents the Universe of Competitors,

The compound property domain is a set of sets, each having

tA 6 A 4

is the power-set of the Universe Of Properties, and

size . Each set has exactly one element from each tagged 6 tA 4

represent generic competitors, and and repre-

domain associated with each property in P. Note that the

sent the property sets (contained in ), respectively.

de nition of CPD does not impose any ordering on the prop-

erties. I

RT-CORBA Competitors in RT-CORBA can be

Distributable threads that compete for CPU time on

RT-CORBA The Compound Property Domain can be ORB endsystems

viewed as a generalization of the RT-CORBA 2.0 JFS con-

Events in an event channel [6] that must be delivered

cept of scheduling parameter types. A given scheduling pa-

to consumers that have subscribed for particular events

rameter type (e.g., the EDF scheduling parameters de ned or

in the RT-CORBA 2.0 JFS) is a collection of typed proper-

GIOP requests that compete for network/bus re-

ties, where a type de nes a domain for the property. The

sources.

RT-CORBA 2.0 JFS focuses on the identity of the aggre-

6 4

gate, treating each kind of scheduling parameter as a dif- If competitor is a distributable thread in the context of RT-

ferent type. In our de nition we stress the identity of sin- CORBA, then can be the set of properties containing

gle properties, so each scheduling parameter is treated as a the elements deadline, importance, and laxity. In this case,

HFE D

collection of properties, rather than as a typed aggregate of the would be the value of the deadline, importance,

properties. and laxity at a particular point of time.

2.1.2 Competitors 2.1.3 Schedulers

Let be the Universe of Competitors.4 We assume that each

De nition 2.4 We de ne an Ordering of Classes of Equiv-

e dU

competitor exposes a set of properties, as shown in Figure 2. alence (OCE) over the set of properties as consist-

ing of the following tuple:

pjloanmljhf)

!kig kig

where:

ljg )

pk 1. is an equivalence relation over the CPD of P.

kljg n sF 8 @F q

2. is a total ordering over the set

em pr

tF q

r F

represents the equivalence class to which the element

belongs. Based on this de nition, the OCE provides a par-

tition of equivalence classes over CPD and also provides a

total order of equivalence classes.

Figure 2. Association Between Competitors

and Properties

Note that the ordering of equivalence classes is de ned

over a set of properties. Property ordering therefore has

no effect on the structure of the equivalence classes, nor

on equivalence class ordering. The ordering of equivalence

De nition 2.3 We de ne the following function:

classes depends only on the value and type of properties.

Conversely, due to run-time changes in system con gura-

tion or scheduler operation mode, the ordering of equiva-

6 4

that when given a competitor, maps it to the set lence classes can depend on time. The time dependency of

of properties it exposes. equivalence classes and of their ordering can also occur

when schedulers refer to time-dependent properties, such as

4 In our case, the universe of discourse is those entities that can compete

value functions.

for the use of resources, and are thus subject to scheduling.

De nition 2.5 A Scheduler is an Ordering of Classes of then orders these classes. Also note that the property values

Equivalence (OCE) over a set of properties. The set of prop- associated with competitors can change over time; a poten-

erties on which a scheduler imposes an OCE is called its tial effect of this change is to move a competitor from one

Characteristic Set, which expresses the properties used by a equivalence class to another.

scheduler to impose an ordering on competitors. Of prop- Finally, we assume that all schedulers in DRE systems

erties exposed by a competitor, a scheduler only considers are well-behaved, which means that schedulers on differ-

those in its characteristic set. Given a scheduler, we in- ent ORB endsystems try to enforce real-time QoS over the

dicate its characteristic set with . properties used to characterize the competitors. Speci -

cally, we do not consider pathological cases where sched-

I ulers do not work to improve QoS in at least some dimen-

RT-CORBA Figure 3 shows the characteristic sets the RT-

sion. For example, a rate monotonic scheduler (RMS) [12]

CORBA 2.0 JFS de nes for the least laxity rst (LLF)5,

and an EDF scheduler will use different orderings of op-

EDF, and rate monotonic (RM) scheduling disciplines. If

erations, but they will both work to improve the deadline

LLF EDF RM feasibility of operations they schedule.

2.2. Adapters

Deadline

2.2.1 Core Adapter Concepts

Remaining Deadline

Execution Time

Having formally de ned the terms property, competitor, and

Importance

scheduler, we can now address problems arising when es-

Importance

tablishing an ordering of competitors with sets of properties

that differ from the Characteristic Set of a scheduler. Be-

low, we address the different cases that can arise.

Figure 3. Characteristic Set for Least Laxity

First (LLF), Earliest Deadline First (EFF), and De nition 2.6 Given two set of properties:

Rate Monotonic (RM) Scheduling Disciplines

X U W U

XU WU

then an Adapter from to is a function of the type:

we consider the RT-CORBA 2.0 JFS EDF scheduler, the

t U d G U d 8 @ G ~

properties in the scheduler s characteristic set are the dead-

line and the importance.6 The equivalence classes in this

case are therefore represented by the set containing these Thus, an Adapter is de ned as a function that transforms

two properties. The equivalence classes are ordered so one set of properties into another. The de nition given

G y xy4

that the importance and deadline associated with each above is quite general, i.e., no assumption are made about

equivalence set are ordered. An example of such an order- the mapping performed by an Adapter. In practice, some

ing could be the following expression: Adapters make more sense than others.

6 X Q W X ') W xy4 6 X }n W y4 6 X X y{96 W z W xy4

y I

RT-CORBA Figure 4 depicts a scenario in which three

iff or

endsystems are each running an ORB with a different

scheduling discipline. Two distributable threads, DT and

In this example, the ordering of the importance and deadline

X W

DT are moving across endsystems. DT originated at

are both the ordering of integral values. RT-CORBA 2.0

endsystem A, where it executed an operation on the object

JFS de nes the importance as a long type, and deadline as

X. It migrates from endsystem A to endsystem B after in-

a TimeBase::TimeT type.

voking an operation on object Y. In contrast, DT originated

Based on the de nitions presented above, we can treat

at endsystem B, where it executed an operation on object Z.

any scheduler as an ordering of equivalence classes over a

It migrates from endsystem A to endsystem B after invoking

set of properties used by a scheduler. These properties are

an operation on object Y.

associated with a competitor by the relation . Note that the

Three different schedulers are used by the ORBs in Fig-

scheduler partitions the full Compound Property Domain

ure 4, (endsystem C has a static RM scheduler). As shown

of its characteristics into a series of equivalence classes and

in Figure 3 these schedulers have different Characteristic

5 An LLF scheduler determines the execution eligibility based on laxity,

Sets. As a result, some adaptation will be required when

which is de ned as the difference between the deadline, the current time, a distributable thread crosses a scheduling domain.7 The

and the estimated remaining computation time.

6 In the canonical EDF de nition [12] there is no concept of impor- 7 A scheduling domain is a collection of ORB endsystems using the

tance but in the RT-CORBA 2.0 JFS there is. same scheduling algorithm and properties.

(c)

DT1 DT2

S S

A S

Object X Object Y Object Z

LLF Scheduler EDF Scheduler

Figure 5. The Properties used by a Scheduler

RM Scheduler

are a Subset of Properties Exposed by a Com-

Endsystem A Endsystem B Endsystem C

petitor

Adaptation Point S Scheduling Point Distributable Thread

Figure 4. A Distributable Thread traversing

endsystems that have different Scheduling

A Restriction Adapter drops the properties exposed by a

Disciplines

competitor that do not belong to the scheduler s Charac-

teristic Set.

RT-CORBA For example, if we consider the case shown

claim of this paper is that the proper type of Adapter can W

in Figure 4, a Restriction Adapter could be applied to DT

handle this adaptation. In addition, Figure 4 shows the point immediately before leaving its ORB or when arriving at

at which schedulers are executed, and the place at which endsystem B s ORB. What the Restriction Adapter does

distributable thread property adaptation can occur, i.e., the W

in this case is map the property exposed by DT from a

place at which the right adapter is executed. set containing deadline, importance, and remaining execu-

X W

Figure 4 also shows DT is preempted by DT while ex- tion time, to the set containing just deadline and impor-

ecuting on the endsystem B s ORB. This case shows that the tance. Moreover, a Restriction Adapter implementation

W X

dynamic priority of DT must be higher than that of DT . should also express the property being adapted in a form

W X

In general, DT and DT would be non-comparable unless that can be manipulated ef ciently by the scheduler. This

adaptation is performed to make sure that their properties form is generally scheduler-dependent because properties

can be expressed in a manner comprehensible by endsys- are exposed uniformly by competitors, e.g., a distributable

tem B s ORB scheduler. Such adaptation and reconciliation thread in this context.

of the distributable threads (i.e., competitor) properties can Case 2: Figure 6 shows a scheduler S with a Charac-

be achieved by means of Adapters. 0v

teristic Set and given competitor c with a non-empty

v 96 4

w . To map the properties exposed by the Competi-

2.2.2 Reconciling Properties Through Adapters S

Now that we have de ned our terminology and formal (c)

model, we show how these formalisms can be used to rec-

oncile properties to support interoperability between hetero-

geneous RT-CORBA schedulers. Below, we examine three

relevant cases that can occur and outline a solution for each

of them.

Case 1: Figure 5 shows a scheduler with a non-empty Figure 6. The Properties Exposed by the Com-

6 4

Characteristic Set and given competitor c with petitor are a Subset of Properties used by the

w . To map the properties exposed by the Competitor Scheduler

into the Ordering of Classes of Equivalence created by the

scheduler over we can apply the following Restriction

tor into the ordering of equivalence classes created by the

Adapter :

scheduler over we can use the following Default Exten-

t# U d ` # U d 8 ~

sion Adapter :

U d ` # U d 8 ~ p f

de ned as:

which is de ned as:

D A 8 A { 6 F 4 ~ y a # U d 3F

wv F )

y a # d

6 4 3 2A pt tA F { 6 U F 4 ~ 3

8 D D ) fF A Generalized Adapter contains the adapters described

wv thus far as a special case. We introduce the concept of

a Generalized Adapter to de ne custom adaptation be-

A variation of the Default Extension Adapter is one that

tween property sets, thereby allowing extra exibility and

considers speci c values for extending the given set of prop-

control over how adaptation occurs. While Extension

erties. Using this, we can then de ne the Extension Adapter

and Restriction Adapters can be created dynamically by a

as the tuple:

Meta Adapter (as described in Section 3.1), Generalized

! ~ zf3 f

Adapters must be provided by users or applications.

RT-CORBA For example, consider a case in which a dis-

where:

tributable thread transitions from

4d f 6 ` # U d U

1. is the set of default values. An ORB con gured with a MUF scheduler that uses

d8 ~ f t# d ` #

f YF & 6 F 4 U ~ R y ` # U U

2. the importance property to isolate different classes of

d 3F

Contact this candidate