z1Introduction toEmbedded SystemsEdward A. Lee & Sanjit SeshiaUC BerkeleyEECS 124Spring 2008Copyright © 2008, Edward A. Lee & Sanjit Seshia, All rights reservedLecture 26: Concurrency Models 3EECS 124, UC Berkeley: 2Model-based designmodels are abstractions of systems:| structural (OO design)| ontological (type systems)| imperative logic (“procedural epistemology”)| functional logic| actor-oriented (“dynamical systems”)All of these have their place…z2EECS 124, UC Berkeley: 3Example: UML static structure diagramsUsed to design object-oriented structure. Can be a model or a meta model(a model of a modeling technique). The above example is a meta model.NamedObjEntity+Entity()+Entity(name : String)+Entity(w : Workspace, name : String)+connectedPorts() : Enumeration+connectionsChanged(p : Port)+getPort(name : String) : Port+getPorts() : Enumeration+linkedRelations() : Enumeration+newPort(name : String) : Port+removeAllPorts()#_addPort(p : Port)#_removePort(p : Port)-_portList : NamedListPort+Port()+Port(w : W orkspace)+Port(container : Entity, name : String)+connectedPorts() : Enumeration+isLinked(r : Relation) : boolean+isOpaque() : boolean+linkedRelations() : Enumeration+link(r : Relation)+numLinks() : int+setContainer(c : Entity)+unlink(r : Relation)+unlinkAll()#_link(r : Relation)-_container : Entity-_relationsList : CrossRefList0..n0..1containeecontainerRelation+Relation()+Relation(name : String)+Relation(w : W orkspace, name : String)+linkedPorts() : Enumeration+linkedPorts(except : Port) : Enumeration+numLinks() : int+unlinkAll()#_checkPort(p : Port)#_getPortList() : CrossRefList-_portList : CrossRefList0..n0..nlinklinkCrossRefList1..11..11..11..1EECS 124, UC Berkeley: 4Example: UML StatechartsStatecharts combine finite state machines with concurrent composition. They are due to David Harel [1987]. The above example models a simple traffic light system, and is due to Reinhard von Hanxleden [2007].z3EECS 124, UC Berkeley: 5Example: Synchronous LanguagesLustre/SCADE, from http://www.esterel-technologies.com/Typical usage pattern:| specify tasks aligned to a master “clock” and subclocks| clock calculus checks for consistency and deadlock| decision logic is given with hierarchical state machines.synchronous signal valuestate machine giving decision logicEECS 124, UC Berkeley: 6Example: Hardware Description Languagesentity latch isport (s,r : in bit;q,nq : out bit);end latch;architecture dataflow of latch isbeginq<=r nor nq;nq<=s nor q;end dataflow;e.g. VHDL:z4EECS 124, UC Berkeley: 7Example: PTIDES: Programming Temporally Integrated Distributed Embedded SystemsDistributed execution under DE semantics, with “model time”and “real time” bound at sensors and actuators.Input time stamps are ≥ real timeInput time stamps are ≥ real timeOutput time stamps are ≤ real timeOutput time stamps are ≤ real timeEECS 124, UC Berkeley: 8Example: Sensor Network LanguagesComponent 1interface usedinterface providedComponent 2interface usedinterface providedcommand invokedcommand implementedevent signaledevent handledTypical usage pattern:| hardware interrupt signals an event.| event handler posts a task.| tasks are executed when machine is idle.| tasks execute atomically w.r.t. one another.| tasks can invoke commands and signal events.| hardware interrupts can interrupt tasks.| exactly one mutex, implemented by disabling interrupts.Command implementers can invoke other commands or post tasks, but do not trigger events.e.g. nesC/TinyOSz5EECS 124, UC Berkeley: 9Example: Network LanguagesClick (Kohler) with a visual syntax in Mescal (Keutzer)push output portpush input portpull output portagnostic output portTypical usage:| queues have push input, pull output.| schedulers have pull input, push output.| thin wrappers for hardware have push output or pull input only.EECS 124, UC Berkeley: 10Example: Dataflow Languagese.g. LabVIEW, Structured dataflow model of computationz6EECS 124, UC Berkeley: 11Example: Continuous-Time Languages Typical usage pattern:| model the continuous dynamics of the physical plant| model the discrete-time controller| code generate the discrete-time controllercontinuous-time signalSimulink + Real-Time WorkshopEECS 124, UC Berkeley: 12Example: Time-Triggered Modelst+10mst+10mstt t+5mst+5msHigher frequency TaskLower frequency task:In time-triggered models (e.g. Giotto, TDL, Simulink/RTW), each actor has a logical execution time (LET). Its actual execution time always appears to have taken the time of the LET.z7EECS 124, UC Berkeley: 13The LET (Logical Execution Time) Programming ModelSoftware Taskread sensor input at time twrite actuator output at time t+d, for specified dExamples: Giotto, TDL, Slide from Tom HenzingerEECS 124, UC Berkeley: 14time t time t+dreal execution on CPUbuffer outputThe LET (Logical Execution Time) Programming ModelSlide from Tom Henzingerz8EECS 124, UC Berkeley: 1550% CPU speedupPortabilitySlide from Tom HenzingerEECS 124, UC Berkeley: 16Task 2Task 1ComposabilitySlide from Tom Henzingerz9EECS 124, UC Berkeley: 17Timing predictability: minimal jitter Function predictability: no race conditions DeterminismSlide from Tom HenzingerEECS 124, UC Berkeley: 18make output available as soon as readyContrast LET with Standard PracticeSlide from Tom Henzingerz10EECS 124, UC Berkeley: 19data raceContrast LET with Standard PracticeSlide from Tom HenzingerEECS 124, UC Berkeley: 20Some efforts get confused:IEC 61499International Electrotechnical Commission(IEC) 61499 is a standard established in 2005 for distributed control systems software engineering for factory automation.The standard is (apparently) inspired by formal composition of state machines, and is intended to facilitate formal verification.Regrettably, the standard essentially fails to give a concurrency model, resulting in radically different behaviors of the same source code from on runtime environments from different vendors, and (worse) highly nondeterministic behaviors on runtimes from any given vendor.See: Ĉengić, G., Ljungkrantz, O. and Åkesson, K., Formal Modeling of Function Block Applications Running in IEC 61499 Execution Runtime. in 11th IEEE International Conference on Emerging Technologies and Factory Automation, (Prague, Czech Republic 2006).z11EECS 124, UC Berkeley: 21There are many ways to view computation and its integration with physical dynamics.Concerns:| timeliness| modularity| composability| reliability|