This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

The Embedded Machine:Predictable, Portable Real-Time Code∗Thomas A. HenzingerEECS, University of California, [email protected] M. KirschEECS, University of California, [email protected] Embedded Machine is a virtual machine that mediatesin real time the interaction between software processes andphysical processes. It separates the compilation of embed-ded programs into two phases. The first, platform-indepen-dent compiler phase generates E code (code executed bythe Embedded Machine), which supervises the timing —not the scheduling— of application tasks relative to externalevents, such as clock ticks and sensor interrupts. E code isportable and exhibits, given an input behavior, predictable(i.e., deterministic) timing and output behavior. The sec-ond, platform-dependent compiler phase checks the timesafety of the E code, that is, whether platform performance(determined by the hardware) and platform utilization (de-termined by the scheduler of the operating system) enableits timely execution. We have used the Embedded Machineto compile and execute high-performance control applica-tions written in Giotto, such as the flight control system ofan autonomous model helicopter.Categories and Subject DescriptorsD.4.7 [Operating Systems]: Organization and Design—Real-time systems and embedded systemsGeneral TermsLanguagesKeywordsReal Time, Virtual Machine1. INTRODUCTIONWe define a real-time execution model, called the EmbeddedMachine (E machine, for short), which provides a portable∗This research was supported in part by the DARPA SECgrant F33615-C-98-3614, the MARCO GSRC grant 98-DT-660, the AFOSR MURI grant F49620-00-1-0327, and theNSF ITR grant CCR-0085949.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.PLDI’02, June 17-19, 2002, Berlin, Germany.Copyright 2002 ACM 1-58113-463-0/02/0006 ...$5.00.target for the compilation of languages with hard real-timeconstraints, such as Giotto [8]. E code (the code executedby the E machine) has strong theoretical properties, in par-ticular, its timing and behavior are predictable. These ben-efits do not come at undue cost in performance. We havedemonstrated this by using E code to reimplement the flightcontrol system of an autonomous model helicopter [10].From Platform-Centric to Requirements-Centric Real-Time ProgrammingIn embedded systems, there are two time lines. The interac-tion of software processes with physical processes (sensors,actuators, clocks) happens in environment time. Applica-tion requirements are specified in environment time, e.g.,“the actuator is set within 2 clock ticks of a sensor inter-rupt.” On the other hand, the execution of software pro-cesses on a specific platform happens in platform time.Byplatform we mean the combination of hardware and real-time operating system (RTOS). Issues of platform perfor-mance, such as worst-case execution times (WCETs), andplatform utilization, such as distribution and scheduling,must be addressed in terms of CPU time. The art of em-bedded programming is to reconcile the two time lines.The E machine proposes a paradigm shift in real-timeprogramming: it permits the programmer to think exclu-sively in terms of environment time (“reactivity”), and shiftsthe burden of reconciliation with platform time to the com-piler (“schedulability”). This paradigm shift is in line withthe steady move towards higher-level programming abstrac-tions. In fact, the E machine treats platform time as a re-source in the way in which most high-level languages treatmemory: the programmer assumes there is enough of it; thecompiler makes sure there is enough of it (or fails to com-pile); the runtime system throws an exception in case thecompiler was wrong (usually due to incorrect assumptionsabout the platform and possible contingencies).Programming in terms of environment time avoids thetwo central drawbacks of conventional embedded code: non-portability and unpredictability. The former is immedi-ate: conventional embedded code is intrinsically platform-dependent, because it directly or indirectly (say, throughpriorities) refers to platform time; E code is platform-inde-pendent, because it refers only to environment time. Pre-dictability, both in timing and functionality, is a less im-mediate but powerful consequence of programming in termsof environment time. By task we mean a software process(or a fragment thereof) without internal synchronizationpoints [13]. Suppose that the inputs of a task t become315available at time x (say, through a sensor interrupt), and itsoutputs are required at time y (say, as an actuator setting).The programmer and, in turn, the E machine is concernedonly with these two times: at environment time x, the inputsare provided to t and the task is turned over to the platform,namely, the RTOS; at environment time y, the outputs of tare read and given to the actuator. The programmer mayassume that the task has indeed completed at time y;other-wise the compiler (or, as last resort, the runtime system) willcomplain. However, the programmer cannot know exactlywhen in the interval [x, y] the task completes; in fact, shecannot even read the outputs of t “as soon as they becomeavailable,” as this would introduce an instant of platformtime into the program. The strict adherence to environ-ment time allows us to design E code without race condi-tions: for two concurrent tasks, it does not matter whichtask completes first, as long as each task completes beforeits outputs are read.A computation of the E machine is time-safe if each taskcompletes before its outputs are read. Time safety depends,of course, on the platform (performance, distribution, sched-uling). A good compiler ensures time safety; in addition,the runtime system monitors time safety. For E code thatrefers only to environment time, time safety implies environ-ment determinedness. A computation of the E machine isenvironment-determined if the inputs from the environmentprocesses (e.g., the sensor readings) uniquely determine theoutputs of the software processes (e.g., the actuator set-tings). While time safety


View Full Document

UCLA COMSCI 239 - HenzingerKirsch02

Download HenzingerKirsch02
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view HenzingerKirsch02 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view HenzingerKirsch02 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?