A Reflective Implementation of an Actor-based Concurrent Context-Oriented System

A Reflective Implementation of an Actor-based Concurrent Context-Oriented System

• 1.
  A Reflective Implementationof an Actor-based Concurrent Context-Oriented System Souhei Takeno & Takuo Watanabe Department of Computer Science Tokyo Institute of Technology Dec. 8, 2015 ARM 2015 1
• 2.
  About This Work •Introduces a new reflective architecture for actor- based systems, and • Proposes a solution to a synchronization problem in a concurrent context-oriented programming system • Talk outline - Actor-Based Group-Wide Reflective Architecture - COP in Actor-Based Systems - Solution to Asynchronous Context Changing - Preliminary Evaluations 2
• 3.
  The Actor Model Aconcurrent computation model based on asynchronous message passing - Originally invented by 
 C. Hewitt in 1970s and
 developed by G. Agha and
 other researchers in 1980-90s. - Today:
 Erlang, Scala (Akka), Io, etc. • A system is modeled as a collection of actors that communicate with each other only via asynchronous messages. - "Shared Nothing": no shared states, no global clock - Dynamic Topology 3 actormessage
• 4.
  Context-Oriented Programming • Aprogramming paradigm aimed to improve the modularity of context-dependent behaviors - Context • External runtime environment • Internal program state - Layer • A language mechanism describing code fragments for context- dependent behaviors • When the runtime system observes the change of its context, it activate a layer (or a set of layers) that corresponds to the new context. - COP Languages • Context{J, L, S, JS}, EventCJ, ContextErlang, etc. 4
• 5.
  An Actor-Based COPModel • An application is constructed as a group of actors. • A special actor called observer continuously observes the application context. • Upon detecting a change of the context, the observer broadcasts context-changing messages to application actors. 5 observer context changing messages application actors O A B old context new context
• 6.
  Context-Crossing Message (CCM) •Application messages that cross context-borders are sometimes problematic, for example, if they carry context-dependent information. • Two kinds of CCMs: • "New-to-old" CCMs can be resolved by piggybacking context information with application messages • No such local solution for "old-to-new" CCMs 6 O A B O A B (a) old-to-new (b) new-to-old change by piggybacked context info.
• 7.
  Ex: Context-Oriented SensorNetwork • Message type: (Double, Int) - "Average" context: (sum, count) - "Maximum" context: (maximum, node id) 7 + + + + + + + max max max max max max max maximum of the measured values average of the measured values “Average” context “Maximum” context sensor node actor
• 8.
  Ex: Multicore MobileDevice • Consider a mobile device equipped with a shared- memory multicore processor • An application is constructed as a group of fine- grained actors. • "Old-to-new" CCMs may occur even if we use a shared variable to express context. 8 WO A B R R
• 9.
  Related Work • COPin Concurrent Settings - ContextErlang [Salvaneschi et al. '12] • Prohibits in-method context-changing • Does not provide solutions to CCMs - CoElektra [Raab '15] • Limiting the changes of contexts to synchronization points • Needs explicit specification of synchronization points • (Global) Synchronization Mechanisms for Actors - Synchronizers [Frølund '96] - Directors [Varela et al. '99] - Transactors [Field et al. '05] - ARC [Ren et al. '06] - Domains [De Koster et al. '12] 9
• 10.
  Contribution • Optimistic CCOPusing Group-Wide Reflection (GWR) - GWR via parallel actor composition [Watanabe, 2013] • Strictly synchronized context changing (= no CCMs) realized by a customized meta-level actors • Preliminary Evaluations using Prototypes in Erlang 10
• 11.
  Group-Wide Reflective Architecture 11 Watanabe'&'Yonezawa,'REX/FOOL''90'(LNCS'#489) a'group'of'objects The$collec(ve$behavior$of$a$group$of$concurrent$ objects$is$represented$as$a$coordinated$ac(ons$ of$a$group$of$meta8objects$(meta8group). The$default$behavior$of$meta8 group$is$proved$to$simulate$the$ behavior$of$base8level$objects. Reflec(ve$behaviors$are$realized$ by$inter8level$messages. Applica(ons:$$ Dynamic$Object$Migra(on,$ Adap(ve$Scheduling,$etc. metaIgroup metaIobjects:' shared'execuNon' engine,'message' router,'etc.
• 12.
  Ad-hoc, Complex Meta-Levels 12 235 Figure3: The Individual and Group Reflective Towers in ABCL/R2 objects at the meta-level, we maintain the tower of metaobjects in the same manner as the individual- based architecture. For coordinated management of system resources such as computational resource, we introduce object groups, whose meta-level representation is a group of meta-level objects that are 409 ., .....I,-'S I ! Mailer ~th:task ...] / L _! t+ / S /%. Task I [~'P- III "'i '"?'T- ' I~ "o i / .~ Evaluator Customersof l" I~'It" "". ,, [ ,,. /^~$~" "" TaskHandler I I~Z:'~I Behavior ~".t~ 0"~" [ ~ t'uo-.] --'~ Actors Ix:~" Figure 1: Actors in TS Definition 1 (Metaeonfiguration) Let C be a configuration orS. A metaconfiguration TC E Fls of C is defined as a pair (7"(TC),T(TC)): .A(tc) = {0, ~s, =,~} u E" u Bs T(TC) = {(u, mo, [:task tt Tm Tk]) I(t,m,k) C T(C)} where E A = {e* 1" e X(O)} Bs = {~ I<m, ~) e x(c)} A task (u, mo, [:task Tt tm tk]) 6 T(TC) is called a meta-task of (t,m,k) E T(C). It represents a task (t,m, k) in the object-level (C). We let Tr denote the recta-task of T. We let u denote the tag of the meta-task, me is the mail address of the task handler actor 0 described below, tt and I'm, called a tag handle and a mail address handle1 (or handles in short), are the metalevel representations of the tag t and the mail address m. A handle may denote another handle: ~Tm is also valid. Let 7-/be the domain of handles. The functionality of t is: T:/+M + 7-/-+~ Recall that 27 and M are the domain of tags and the domain of mail addresses. We write for the inverse function of T- For any x E 27+ M + 7-/and y 6 7-/, ~l"x = x and T~y = y holds. Thus T is a bijection, so 7-/should be an (recursive) infinite domain. Handles will be used as keys in the database actor 6s described below. Tk is the value which has the same structure as k, but every occurrence of mail addresses and handles in k are replaced with their handles. For example, if k is the value [:do ma (foo Tmz)] and ml and m~ are mail addresses, then Tk is [:do Tin1 (foo ~Tm2)]. The metalevel actors in .A(TC) are categorized as follows (see Figure 1). Their precise definition will be given as actual code definitions in Section 2.4. Watanabe & Yonezawa, REX/FOOL '90 (LNCS#489) Matsuoka, Watanabe & Yonezawa, ECOOP '91 Masuhara, Matsuoka, Watanabe & Yonezawa, OOPSLA '92 Hard to customize / reason about
• 13.
  Parallel Composition ofActors (1) • Compose the member in an actor group into a single actor that exhibits the same behavior as the original group. 13 a1 (2, a1) (1, (2, a1)) (2, (2, a1)) (3, a1) a2 (1, a1) a3 (1, a3) actor group boundary ai base address
• 14.
  Parallel Composition ofActors (2) A1 = 〈〈1, m〉, q1, e1, s1〉 A2 = 〈〈2, m〉, q2, e2, s2〉 〈〈1, m〉, k1〉 〈〈2, m〉, k2〉 A1+A2 = 〈m, q, e, s〉 〈〈1, m〉, k1〉 ↦ 〈〈m, (1, k1)〉 〈〈2, m〉, k2〉 ↦ 〈〈m, (2, k2)〉 14 Our language offers a simple group-wide reflection mech- anism based on compositional meta-level actors. This sub- section presents the overview of the actor composition used to construct meta-level actors. We give an intuitive explanation of the composition using a simple example. Let a be the address of a group that as two member actors with addresses (1, a) and (2, a). The initial behavior functions of the actors, named A1 and A2 respectively, are defined as follows. let A1 = { p1 → e1 ; become A′ 1 } let A2 = { p2 → e2 ; become A′ 2 } Note that e1 and e2 do not contain become expressions. By composing A1 and A2, we obtain the behavior function A1+A2 defined as follows. let A1 +A2 = { (1, p1 ) → e1 ; become A′ 1 +A2 | (2, p2 ) → e2 ; become A1 +A′ 2 } The behavior functions A’+B and A+B’ should also be de- fined in similar way. By using this definition, we can replace the entire group (whose members are actors with addresses (1, a) and (2, a)) with a single actor with address a that has A1+A2 as the initial behavior function. Thanks to the message routing mechanism described in the previous subsection, messages that are sent to the addresses (1, a) or (2, a) will be delivered anism based on compositional meta-level actors. This sub- section presents the overview of the actor composition used to construct meta-level actors. We give an intuitive explanation of the composition using a simple example. Let a be the address of a group that as two member actors with addresses (1, a) and (2, a). The initial behavior functions of the actors, named A1 and A2 respectively, are defined as follows. let A1 = { p1 → e1 ; become A′ 1 } let A2 = { p2 → e2 ; become A′ 2 } Note that e1 and e2 do not contain become expressions. By composing A1 and A2, we obtain the behavior function A1+A2 defined as follows. let A1 +A2 = { (1, p1 ) → e1 ; become A′ 1 +A2 | (2, p2 ) → e2 ; become A1 +A′ 2 } The behavior functions A’+B and A+B’ should also be de- fined in similar way. By using this definition, we can replace the entire group (whose members are actors with addresses (1, a) and (2, a)) with a single actor with address a that has A1+A2 as the initial behavior function. Thanks to the message routing mechanism described in the previous subsection, messages that are sent to the addresses (1, a) or (2, a) will be delivered to the composed (replacement) actor. The composed actor
• 15.
  • By applyingthe parallel composition to per-actor meta- level definition, we can acquire a group-wide meta-level. • Group-wide operations can be added to the composed meta-level. Compositional Construction of Group-Wide Meta-level[Watanabe 2013] 15 | [] → become meta1(queue , beh , Dormant , exec1) | _::_ → [self ⇐ Begin]; become meta1(queue , beh , state , exec1) end } Figure 6: A Plain Single Meta-Level Behavior letrec metaG(queue*, beh*, state*, execG) = { (i, Mesg v) → if state*[i] = Dormant then [self ⇐ (i, Begin )]; become metaG(queue*{queue*[i] ++ [v]/i}, beh*, state*{ Active/i}, execG) | (i, Begin) → match queue*[i] with | v::queue ’ → [execG ⇐ (i, Apply(beh*[i], v, self )]; become metaG(queue*{queue ’/i}, beh*, state*, execG) end | (i, End) → match queue*[i] with | [] → become metaG(queue*, beh*, state*{ Dormant/i}, execG) | _::_ → [self ⇐ (i, Begin )]; become metaG(queue*, beh*, state*, execG) end } Figure 7: The Composed Meta-Level Behavior Figure 6 is an example of a default (plain) behavior func- tion for meta-level actors. The argument of the function meta1 is a quadruple of the message queue, the behavior function, the state of the base-level and the address of an actor called execution engine. A meta-level actor governs a single base-level actor. As in ABCL/R, the reception of a message m at the base-level is interpreted as the reception of the message Mesg m at the meta-level. Then the meta-level actor maintains its mes- use so The e x*{v/i its i-t The in [17 execut compo spond such a 3. T Usin ous so collect a poss in the Figu a com messa actor memb keeps A c Ctx c w sage. if c′ i in the inform text o newer the m the op handle simple tent. T the Ti Figu timist tings i contex cation applic old co letrec meta1(queue , beh , state , exec1) = { Mesg v → if state = Dormant then [self ⇐ Begin ]; become meta1(queue ++[v], beh , Active , exec1) | Begin → match queue with | v::queue ’ → [exec1 ⇐ Apply(beh , v, self )]; become meta1(queue ’, beh , state , exec1) end | End → match queue with | [] → become meta1(queue , beh , Dormant , exec1) | _::_ → [self ⇐ Begin ]; become meta1(queue , beh , state , exec1) end } Figure 6: A Plain Single Meta-Level Behavior letrec metaG(queue*, beh*, state*, execG) = { (i, Mesg v) → if state *[i] = Dormant then [self ⇐ (i, Begin )]; become metaG(queue *{ queue *[i] ++ [v]/i}, beh*, state *{ Active/i}, execG) | (i, Begin) → match queue *[i] with | v::queue ’ → [execG ⇐ (i, Apply(beh*[i], v, self )]; become metaG(queue *{queue ’/i}, beh*, explosion of composed behaviors. The trick is that every become invocation in the definition uses the same meta-level definition meta1. Figure 7 shows the result of the composition. To im- plement the behavior of each base-level actor, we need to change the argument of meta1 to the quadruple of collec- tive (indexed) data structures (e.g., arrays or dictionaries) other than the execution engine. In the rest of the paper, we use identifiers end with asterisk (such as queue*, beh* and state*) to denote such collective data structures. We also use some built-in operators regarding these data structures. The expression x*[i] denotes the i-th element of x* and x*{v/i} denotes the data structure same as x* except that its i-th element is replaced by v. The execution engine can be shared within the group as in [17, 8]. In this example, execG is responsible for the execution of all members of the group represented by the composed meta-level actor. This architecture roughly corre- sponds to queue-based concurrent task management systems such as libdispatch1 . 3. TOWARDS CONCURRENT COP Using the composed meta-level actor, we can enjoy vari- ous sorts of group-wide reflective operations that control the collective behaviors of an actor groups. This section presents a possible solution to the synchronization problem described in the Section 1 using group-wide reflection. Figure 8 shows the definition of the behavior function of a composed meta-level actor that can cancel cross-context messages within the group governed by this. The meta-level per-actor meta-level group-wide meta-level
• 16.
  Application: Optimistic CCOP [Watanabe& Takeno 2013] • Assumptions - single observer - contexts are linearly ordered - each message piggybacks the context of its sender • Algorithm - Similar to Timewarp [Jefferson '85] • Better concurrency - cf. pessimistic approach • Implicit - Application programmer doesn't need to take care of context synchronization 16
• 17.
  O A B p q r s t u v O A B p q r s t u vw s’ q’ t’ u’ v’ m n m n -n
• 18.
  O A B p q r s t u v ws’ q’ t’ u’ v’ O A B p r s’ q’ t’ u’ v’ m n -n
• 19.
  Preliminary Evaluations: Ping-Pong •Prototypes in Erlang - Plain: basic actor primitives (send/new/become) - GWR: basic (manually composed) group-wide metalevel - CCOP: an optimistic CCOP on GWR • 1M round-trip messages between two actors 19 Plain GWR CCOP Time (sec) 0.66 3.21 16.03
• 20.
  Preliminary Evaluations: TokenRing • 200k round-trip messages in a ring of 100 actors 20 1 5 10 15 20 25 0 6 12 18 24 Number of Concurrent Messages ExecutionTime(sec) Plain GWR CCOP
• 21.
  Preliminary Evaluations: SensorNetwork • Simulation of a simple sensor network • Sensor Node - has many sensors - computes results using measured values • Benchmark - A master node sends requests to (and receives results from) the sensor nodes along a spanning tree of the network - average turn around time 21 Plain GWR CCOP Time (sec) 14.02 14.41 14.30
• 22.
  Evaluating the RollbackMechanism • A context change in the sensor example • Rollback frequency (200 trials) 22 # of Rollbacks 0 1 2 3 4 5 Freq 80 24 16 41 32 7 Time (sec) Arithmetic 14.30 Harmonic 14.54 A then H 29.00
• 23.
  Summary • Concurrent COPin Actor-Based Systems • Optimistic implementation of CCOP using GWR - A reflective solution to implementing strictly synchronized context-changing in actor-based systems. • Preliminary Evaluations using Prototypes in Erlang • Future Work - Optimizations • context sensitive scheduling policies • application specific undoing/redoing for optimistic CCOP - Loose adaptation to contexts - Language (abstraction) mechanisms for CCOP - Verification 23