Changeset 739bd7b for doc/theses
- Timestamp:
- Jun 18, 2023, 8:52:01 PM (20 months ago)
- Branches:
- master
- Children:
- df27752
- Parents:
- 7c012e8
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/colby_parsons_MMAth/text/actors.tex
r7c012e8 r739bd7b 21 21 An actor is executed by an underlying \Newterm{executor} (kernel thread-pool) that fairly invokes each actor, where an actor invocation processes one or more messages from its mailbox. 22 22 The default number of executor threads is often proportional to the number of computer cores to achieve good performance. 23 An executor is often tunable with respect to the number of kernel threads and its scheduling algorithm, which optimize for specific actor applications and workloads \see{end of Section~\ref{s:CFAActor Syntax}}.24 25 \s ection{Classic Actor System}23 An executor is often tunable with respect to the number of kernel threads and its scheduling algorithm, which optimize for specific actor applications and workloads \see{end of Section~\ref{s:CFAActor}}. 24 25 \subsection{Classic Actor System} 26 26 An implementation of the actor model with a community of actors is called an actor system. 27 27 Actor systems largely follow the actor model, but can differ in some ways. … … 45 45 \end{figure} 46 46 47 \s ection{\CFA Actors}47 \subsection{\CFA Actor System} 48 48 Figure~\ref{f:standard_actor} shows an actor system designed as \Newterm{actor-centric}, where a set of actors are scheduled and run on underlying executor threads~\cite{CAF,Akka,ProtoActor}. 49 49 The simplest design has a single global queue of actors accessed by the executor threads, but this approach results in high contention as both ends of the queue by the executor threads. … … 92 92 \end{enumerate} 93 93 94 \section{\CFA Actor Syntax}\label{s:CFAActorSyntax}94 \section{\CFA Actor}\label{s:CFAActor} 95 95 \CFA is not an object oriented language and it does not have \gls{rtti}. 96 96 As such, all message sends and receives among actors can only occur using static type-matching, as in Typed-Akka~\cite{AkkaTyped}. … … 146 146 // messages 147 147 struct str_msg { 148 @inline message;@ $\C{// Plan-9 C nominal inheritance}$149 148 char str[12]; 149 @inline message;@ $\C{// Plan-9 C inheritance}$ 150 150 }; 151 151 void ?{}( str_msg & this, char * str ) { strcpy( this.str, str ); } $\C{// constructor}$ 152 152 struct int_msg { 153 @inline message;@ $\C{// Plan-9 C nominal inheritance}$154 153 int i; 154 @inline message;@ $\C{// Plan-9 C inheritance}$ 155 155 }; 156 void ?{}( int_msg & this, int i ) { this.i = i; } $\C{// constructor}$157 156 // behaviours 158 allocation receive( my_actor &, @str_msg & msg@ ) {159 sout | "string message \"" | msg.str | "\"";157 allocation receive( my_actor &, @str_msg & msg@ ) with(msg) { 158 sout | "string message \"" | str | "\""; 160 159 return Nodelete; $\C{// actor not finished}$ 161 160 } 162 allocation receive( my_actor &, @int_msg & msg@ ) {163 sout | "integer message" | msg.i;161 allocation receive( my_actor &, @int_msg & msg@ ) with(msg) { 162 sout | "integer message" | i; 164 163 return Nodelete; $\C{// actor not finished}$ 165 164 } 166 165 int main() { 166 str_msg str_msg{ "Hello World" }; $\C{// constructor call}$ 167 int_msg int_msg{ 42 }; $\C{// constructor call}$ 167 168 start_actor_system(); $\C{// sets up executor}$ 168 169 my_actor actor; $\C{// default constructor call}$ 169 str_msg str_msg{ "Hello World" }; $\C{// constructor call}$ 170 int_msg int_msg{ 42 }; $\C{// constructor call}$ 171 @actor << str_msg << int_msg;@ $\C{// cascade sends}$ 172 @actor << int_msg;@ $\C{// send}$ 173 @actor << finished_msg;@ $\C{// send => terminate actor (deallocation deferred)}$ 170 @actor | str_msg | int_msg;@ $\C{// cascade sends}$ 171 @actor | int_msg;@ $\C{// send}$ 172 @actor | finished_msg;@ $\C{// send => terminate actor (deallocation deferred)}$ 174 173 stop_actor_system(); $\C{// waits until actors finish}\CRT$ 175 174 } // deallocate int_msg, str_msg, actor 176 175 \end{cfa} 177 176 \caption{\CFA Actor Syntax} 178 \label{f:CFAActor Syntax}179 \end{figure} 180 181 Figure~\ref{f:CFAActor Syntax} shows a complete \CFA actor example starting with the actor type @my_actor@ created by defining a @struct@ that inherits from the base @actor@ @struct@ via the @inline@ keyword.182 This inheritance style is the Plan-9 C-style nominalinheritance discussed in Section~\ref{s:Inheritance}.177 \label{f:CFAActor} 178 \end{figure} 179 180 Figure~\ref{f:CFAActor} shows a complete \CFA actor example starting with the actor type @my_actor@ created by defining a @struct@ that inherits from the base @actor@ @struct@ via the @inline@ keyword. 181 This inheritance style is the Plan-9 C-style inheritance discussed in Section~\ref{s:Inheritance}. 183 182 Similarly, the message types @str_msg@ and @int_msg@ are created by defining a @struct@ that inherits from the base @message@ @struct@ via the @inline@ keyword. 184 Both message types have constructors to set the message value. 183 Only @str_msg@ needs a constructor to copy the C string; 184 @int_msg@ is initialized using its \CFA auto-generated constructors. 185 185 There are two matching @receive@ (behaviour) routines that process the corresponding typed messages. 186 The program main begins by calling @start_actor_system@ to start the actor implementation, including executor threads to run the actors. 187 An actor and two messages are created on the stack, and four messages are sent to the actor using operator @<<@. 188 The last message is the builtin @finish_msg@, which returns @Finished@ to an executor thread, which removes the actor from the actor system \see{Section~\ref{s:ActorBehaviours}}. 189 The call to @stop_actor_system@ blocks program main until all actors are finished and removed from the actor system. 190 The program main ends by deleting the actor and messages from the stack. 186 Both @receive@ routines use a @with@ clause so message fields are not qualified and return @Nodelete@ indicating the actor is not finished. 187 Also, all messages are marked with @Nodelete@ as their default allocation state. 188 The program main begins by creating two messages on the stack. 189 Then the executor system is started by calling @start_actor_system@. 190 Now an actor is created on the stack and four messages are sent it using operator @?|?@. 191 The last message is the builtin @finish_msg@, which returns @Finished@ to an executor thread, causing it to removes the actor from the actor system \see{Section~\ref{s:ActorBehaviours}}. 192 The call to @stop_actor_system@ blocks the program main until all actors are finished and removed from the actor system. 193 The program main ends by deleting the actor and two messages from the stack. 191 194 The output for the program is: 192 195 \begin{cfa} … … 237 240 Note, it is safe to construct an actor or message with a status other than @Nodelete@, since the executor only examines the allocation action after a behaviour returns. 238 241 242 \subsection{Actor Envelopes}\label{s:envelope} 243 As stated, each message, regardless of where it is allocated, can be sent to an arbitrary number of actors, and hence, appear on an arbitrary number of message queues. 244 Because a C program manages message lifetime, messages cannot be copied for each send, otherwise who manages the copies. 245 Therefore, it up to the actor program to manage message life-time across receives. 246 However, for a message to appear on multiple message queues, it needs an arbitrary number of link fields. 247 Hence, there is the concept of an envelop, which is dynamically allocated on each send, that wraps a message with any extra implementation fields needed to persist between send and receive. 248 Managing the envelop is straightforward because it is created at the send and deleted after the receive, \ie there is 1:1 relationship for an envelop and a many to one relationship for a message. 249 250 % In actor systems, messages are sent and received by actors. 251 % When a actor receives a message it executes its behaviour that is associated with that message type. 252 % However the unit of work that stores the message, the receiving actor's address, and other pertinent information needs to persist between send and the receive. 253 % Furthermore the unit of work needs to be able to be stored in some fashion, usually in a queue, until it is executed by an actor. 254 % All these requirements are fulfilled by a construct called an envelope. 255 % The envelope wraps up the unit of work and also stores any information needed by data structures such as link fields. 256 257 % One may ask, "Could the link fields and other information be stored in the message?". 258 % This is a good question to ask since messages also need to have a lifetime that persists beyond the work it delivers. 259 % However, if one were to use messages as envelopes then a message would not be able to be sent to multiple actors at a time. 260 % Therefore this approach would just push the allocation into another location, and require the user to dynamically allocate a message for every send, or require careful ordering to allow for message reuse. 261 239 262 \subsection{Actor System}\label{s:ActorSystem} 240 263 The calls to @start_actor_system@, and @stop_actor_system@ mark the start and end of a \CFA actor system. … … 258 281 All actors must be created \emph{after} calling @start_actor_system@ so the executor can keep track of the number of actors that have entered the system but not yet terminated. 259 282 260 % All message sends are done using the left-shift operator, @<<@, similar to the syntax of \CC's stream output.283 % All message sends are done using the vertical-bar operator, @?|?@, similar to the syntax of \CC's stream output. 261 284 % \begin{cfa} 262 % allocation ? <<?( my_actor & receiver, my_msg & msg )285 % allocation ?|?( my_actor & receiver, my_msg & msg ) 263 286 % \end{cfa} 264 287 % Notice this signature is the same as the @receive@ routine, which is no coincidence. 265 % The \CFA compiler generates a @? <<?@ routine definition and forward declaration for each @receive@ routine that has the appropriate signature.288 % The \CFA compiler generates a @?|?@ routine definition and forward declaration for each @receive@ routine that has the appropriate signature. 266 289 % The generated routine packages the message and actor in an \hyperref[s:envelope]{envelope} and adds it to the executor's queues via an executor routine. 267 % As part of packaging the envelope, the @? <<?@ routine sets a routine pointer in the envelope to point to the appropriate receive routine for given actor and message types.290 % As part of packaging the envelope, the @?|?@ routine sets a routine pointer in the envelope to point to the appropriate receive routine for given actor and message types. 268 291 269 292 \subsection{Actor Send}\label{s:ActorSend} 270 All message sends are done using the left-shift operator, @<<@, similar to the syntax of \CC's stream output.293 All message sends are done using the vertical-bar (bit-or) operator, @?|?@, similar to the syntax of the \CFA stream I/O. 271 294 As stated, \CFA does not have named inheritance with RTTI. 272 295 \CFA does have a preliminary form of virtual routines, but it is not mature enough for use in this work. 273 Therefore, there is no mechanism to write a generic @ <<@ routine taking a base actor and message type, and then dynamically selecting the @receive@ routine from the actor argument.296 Therefore, there is no mechanism to write a generic @?|?@ routine taking a base actor and message type, and then dynamically selecting the @receive@ routine from the actor argument. 274 297 (For messages, the Plan-9 inheritance is sufficient because only the inherited fields are needed during the message send.) 275 Hence, programmers must write a matching @<<@ routine for each @receive@ routine, which is awkward and generates a maintenance problem. 276 Therefore, I chose to use a template-like approach, where the compiler generates a matching @<<@ routine for each @receive@ routine it finds with an actor/message type-signature. 277 Then, \CFA uses the type from the left-hand side of an assignment to select the matching receive routine. 298 Hence, programmers must write a matching @?|?@ routine for each @receive@ routine, which is awkward and generates a maintenance problem. 299 Therefore, I chose a template-like approach, where the compiler generates a matching @?|?@ routine for each @receive@ routine it finds with the correct actor/message type-signature. 278 300 (When the \CFA virtual routines mature, it should be possible to seamlessly transition to it from the template approach.) 279 301 280 % Funneling all message sends through a single @allocation ?<<?(actor &, message &)@ routine is not feasible since the type of the actor and message would be erased, making it impossible to acquire a pointer to the correct @receive@. 281 % As such a @?<<?@ routine per @receive@ provides type information needed to write the correct "address" on the envelope. 282 283 % The left-shift operator routines are generated by the compiler. 284 An example of a receive routine and its corresponding generated operator routine is shown in Figure~\ref{f:actor_gen}. 285 Notice the parameter signature of @?<<?@ is the same as the @receive@ routine. 286 A @?<<?@ routine is generated per @receive@ routine with a matching signature. 287 The @?<<?@ routine packages the message and actor in an \hyperref[s:envelope]{envelope} and adds it to the executor's queues via the executor routine @send@. 288 The envelope is conceptually "addressed" to a behaviour, which is stored in the envelope as a function pointer to a @receive@ routine. 289 The @?<<?@ routines ensure that messages are sent to the right address, \ie sent to the right @receive@ routine based on actor and message type. 302 % Funneling all message sends through a single @allocation ?|?(actor &, message &)@ routine is not feasible since the type of the actor and message would be erased, making it impossible to acquire a pointer to the correct @receive@. 303 % As such a @?|?@ routine per @receive@ provides type information needed to write the correct "address" on the envelope. 304 305 Figure~\ref{f:send_gen} shows the generated send routine for the @int_msg@ receive in Figure~\ref{f:CFAActor}. 306 Operator @?|?@ has the same parameter signature as the corresponding @receive@ routine and returns an @actor@ so the operator can be cascaded. 307 The routine sets @rec_fn@ to the matching @receive@ routine using the left-hand type to perform the selection. 308 Then the routine packages the base and derived actor and message and actor, along with the receive routine into an \hyperref[s:envelope]{envelope}. 309 Finally, the envelop is added to the executor queue designated by the actor using the executor routine @send@. 290 310 291 311 \begin{figure} 292 312 \begin{cfa} 293 $\LstCommentStyle{// from Figure~\ref{f:CFAActorSyntax}}$ 294 struct my_actor { inline actor; }; $\C[3.5in]{// actor}$ 295 struct int_msg { inline message; int i; }; $\C{// message}$ 296 void ?{}( int_msg & this, int i ) { this.i = i; } $\C{// constructor}$ 297 allocation receive( @my_actor &, int_msg & msg@ ) { $\C{// receiver}$ 298 sout | "integer message" | msg.i; 299 return Nodelete; 300 } 301 302 // compiler generated operator 303 #define RECEIVER( A, M ) (allocation (*)(actor &, message &))(allocation (*)( A &, M & ))receive 304 my_actor & ?<<?( @my_actor & receiver, int_msg & msg@ ) { 305 send( receiver, (request){ &receiver, &msg, RECEIVER( my_actor, int_msg ) } ); 313 $\LstCommentStyle{// from Figure~\ref{f:CFAActor}}$ 314 struct my_actor { inline actor; }; $\C[3.75in]{// actor}$ 315 struct int_msg { inline message; int i; }; $\C{// message}$ 316 allocation receive( @my_actor &, int_msg & msg@ ) {...} $\C{// receiver}$ 317 318 // compiler generated send operator 319 typedef allocation (*receive_t)( actor &, message & ); 320 actor & ?|?( @my_actor & receiver, int_msg & msg@ ) { 321 allocation (*rec_fn)( my_actor &, int_msg & ) = @receive@; // deduce receive routine 322 request req{ &receiver, (actor *)&receiver, &msg, (message *)&msg, (receive_t)rec_fn }; 323 send( receiver, req ); $\C{// queue message for execution}\CRT$ 306 324 return receiver; 307 325 } 308 326 \end{cfa} 309 327 \caption{Generated Send Operator} 310 \label{f:actor_gen} 328 \label{f:send_gen} 329 \end{figure} 330 331 Figure~\ref{f:ConvenienceMessages} shows three builtin convenience messages and receive routines used to terminate actors, depending on how an actor is allocated: @Delete@, @Destroy@ or @Finished@. 332 For example, in Figure~\ref{f:CFAActor}, the builtin @finished_msg@ message and receive are used to terminate the actor because the actor is allocated on the stack, so no deallocation actions are performed by the executor. 333 334 \begin{figure} 335 \begin{cfa} 336 message __base_msg_finished $@$= { .allocation_ : Finished }; // no auto-gen constructors 337 struct __delete_msg_t { inline message; } delete_msg = __base_msg_finished; 338 struct __destroy_msg_t { inline message; } destroy_msg = __base_msg_finished; 339 struct __finished_msg_t { inline message; } finished_msg = __base_msg_finished; 340 341 allocation receive( actor & this, __delete_msg_t & msg ) { return Delete; } 342 allocation receive( actor & this, __destroy_msg_t & msg ) { return Destroy; } 343 allocation receive( actor & this, __finished_msg_t & msg ) { return Finished; } 344 \end{cfa} 345 \caption{Builtin Convenience Messages} 346 \label{f:ConvenienceMessages} 311 347 \end{figure} 312 348 … … 319 355 The goal is to achieve better performance and scalability for certain kinds of actor applications by reducing executor locking. 320 356 Note, lock-free queues do not help because busy waiting on any atomic instruction is the source of the slowdown whether it is a lock or lock-free. 321 Work steal now becomes queue stealing, where an entire actor/message queue is stolen, which trivially preserves message ordering in a queue \see{Section~\ref{s:steal}}.322 357 323 358 \begin{figure} … … 330 365 331 366 Each executor thread iterates over its own message queues until it finds one with messages. 332 At this point, the executor thread atomically \gls{gulp}s the queue, meaning move the contents of message queue to a local queue of the executor thread using a single atomic instruction. 333 This step allows the executor threads to process the local queue without any atomics until the next gulp, while other executor threads are adding in parallel to the end of one of the message queues. 334 In detail, an executor thread performs a test-and-gulp, non-atomically checking if a queue is non-empty before gulping it. 335 If a test fails during a message add, the worst-case is cycling through all the message queues. 336 However, the gain is minimizing costly lock acquisitions. 367 At this point, the executor thread atomically \gls{gulp}s the queue, meaning it moves the contents of message queue to a local queue of the executor thread using a single atomic instruction. 337 368 An example of the queue gulping operation is shown in the right side of Figure \ref{f:gulp}, where a executor threads gulps queue 0 and begins to process it locally. 338 339 Processing a local queue involves removing a unit of work from the queue and executing it. 369 This step allows an executor thread to process the local queue without any atomics until the next gulp. 370 Other executor threads can continue adding to the ends of executor thread's message queues. 371 In detail, an executor thread performs a test-and-gulp, non-atomically checking if a queue is non-empty, before attempting to gulp it. 372 If an executor misses an non-empty queue due to a race, it eventually finds the queue after cycling through its message queues. 373 This approach minimizes costly lock acquisitions. 374 375 Processing a local queue involves: removing a unit of work from the queue, dereferencing the actor pointed-to by the work-unit, running the actor's behaviour on the work-unit message, examining the returned allocation status from the @receive@ routine for the actor and internal status in the delivered message, and taking the appropriate actions. 340 376 Since all messages to a given actor are in the same queue, this guarantees atomicity across behaviours of that actor since it can only execute on one thread at a time. 341 After running a behaviour, the executor thread examines the returned allocation status from the @receive@ routine for the actor and internal status in the delivered message, and takes the appropriate action. 342 Once all actors have marked themselves as being finished the executor initiates shutdown by inserting a sentinel value into the message queues. 343 Once a executor threads sees a sentinel it stops running. 344 After all executors stop running the actor system shutdown is complete. 345 346 \section{Envelopes}\label{s:envelope} 347 As stated, each message, regardless of where it is allocated, can be sent to an arbitrary number of actors, and hence, appear on an arbitrary number of message queues. 348 Because a C program manages message lifetime, messages cannot be copied for each send, otherwise who manages the copies. 349 Therefore, it up to the actor program to manage message life-time across receives. 350 However, for a message to appear on multiple message queues, it needs an arbitrary number of link fields. 351 Hence, there is the concept of an envelop, which is dynamically allocated on each send, that wraps a message with any extra implementation fields needed to persist between send and receive. 352 Managing the envelop is straightforward because it is created at the send and deleted after the receive, \ie there is 1:1 relationship for an envelop and a many to one relationship for a message. 353 354 % In actor systems, messages are sent and received by actors. 355 % When a actor receives a message it executes its behaviour that is associated with that message type. 356 % However the unit of work that stores the message, the receiving actor's address, and other pertinent information needs to persist between send and the receive. 357 % Furthermore the unit of work needs to be able to be stored in some fashion, usually in a queue, until it is executed by an actor. 358 % All these requirements are fulfilled by a construct called an envelope. 359 % The envelope wraps up the unit of work and also stores any information needed by data structures such as link fields. 360 361 % One may ask, "Could the link fields and other information be stored in the message?". 362 % This is a good question to ask since messages also need to have a lifetime that persists beyond the work it delivers. 363 % However, if one were to use messages as envelopes then a message would not be able to be sent to multiple actors at a time. 364 % Therefore this approach would just push the allocation into another location, and require the user to dynamically allocate a message for every send, or require careful ordering to allow for message reuse. 365 366 Unfortunately, this frequent allocation of envelopes for each send results in heavy contention on the memory allocator. 367 As such, a way to alleviate contention on the memory allocator would result in a performance improvement. 368 Contention is reduced using a novel data structure, called a \Newterm{copy queue}. 377 As each actor is created or terminated by an executor thread, it increments/decrements a global counter. 378 When an executor decrements the counter to zero, it sets a global boolean variable that is checked by each executor thread when it has no work. 379 Once a executor threads sees the flag is set it stops running. 380 After all executors stop, the actor system shutdown is complete. 369 381 370 382 \subsection{Copy Queue}\label{s:copyQueue} 383 Unfortunately, the frequent allocation of envelopes for each send results in heavy contention on the memory allocator. 384 This contention is reduced using a novel data structure, called a \Newterm{copy queue}. 371 385 The copy queue is a thin layer over a dynamically sized array that is designed with the envelope use case in mind. 372 A copy queue supports the typical queue operations of push/pop but in a different way than a typical arraybased queue.373 The copy queue is designed to take advantage of the \gls{gulp}ing pattern. 374 As such, the amortized runtime cost of each push/pop operation for the copy queue is$O(1)$.386 A copy queue supports the typical queue operations of push/pop but in a different way from a typical array-based queue. 387 388 The copy queue is designed to take advantage of the \gls{gulp}ing pattern, giving an amortized runtime cost for each push/pop operation of $O(1)$. 375 389 In contrast, a na\"ive array-based queue often has either push or pop cost $O(n)$ and the other cost $O(1)$ since one of the operations requires shifting the elements of the queue. 376 390 Since the executor threads gulp a queue to operate on it locally, this creates a usage pattern where all elements are popped from the copy queue without any interleaved pushes. … … 384 398 For many workload, the copy queues grow in size to facilitate the average number of messages in flight and there is no further dynamic allocations. 385 399 One downside of this approach that more storage is allocated than needed, \ie each copy queue is only partially full. 386 Comparatively, the individual envelope allocations of a list 400 Comparatively, the individual envelope allocations of a list-based queue mean that the actor system always uses the minimum amount of heap space and cleans up eagerly. 387 401 Additionally, bursty workloads can cause the copy queues to allocate a large amounts of space to accommodate the peaks of the throughput, even if most of that storage is not needed for the rest of the workload's execution. 388 402 … … 390 404 Initially, the memory reclamation na\"ively reclaims one index of the array per \gls{gulp}, if the array size is above a low fixed threshold. 391 405 However, this approach has a problem. 392 The high memory usagewatermark nearly doubled!393 The issue can easily behighlighted with an example.406 The high memory watermark nearly doubled! 407 The issue is highlighted with an example. 394 408 Assume a fixed throughput workload, where a queue never has more than 19 messages at a time. 395 409 If the copy queue starts with a size of 10, it ends up doubling at some point to size 20 to accommodate 19 messages. 396 410 However, after 2 gulps and subsequent reclamations the array size is 18. 397 411 The next time 19 messages are enqueued, the array size is doubled to 36! 398 To avoid this issue a second check is added.399 Each copy queue startedtracking the utilization of its array size.412 To avoid this issue, a second check is added. 413 % Each copy queue starts tracking the utilization of its array size. 400 414 Reclamation only occurs if less than half of the array is utilized. 401 In doing this, the reclamation scheme is able to achieve a lower high-watermark and a lower overall memory utilization compared to the non-reclamation copy queues. 402 However, the use of copy queues still incurs a higher memory cost than list-based queueing. 403 With the inclusion of a memory reclamation scheme the increase in memory usage is reasonable considering the performance gains and is discussed further in Section~\ref{s:actor_perf}. 415 This check achieves a lower total storage and overall memory utilization compared to the non-reclamation copy queues. 416 However, the use of copy queues still incurs a higher memory cost than list-based queueing, but the increase in memory usage is reasonable considering the performance gains \see{Section~\ref{s:actor_perf}}. 404 417 405 418 \section{Work Stealing}\label{s:steal} 406 Work stealing is a scheduling strategy t hat attempts to load balance, and increase resource utilization by having idle threads steal work.407 The re are many parts that make up a work stealing actor scheduler, but the two that will be highlighted in this work are the stealing mechanism and victim selection.408 409 % C_TODO enter citation for langs 419 Work stealing is a scheduling strategy to provide \Newterm{load balance}. 420 The goal is to increase resource utilization by having idle threads steal work from working threads. 421 While there are multiple parts in work-stealing scheduler, the two important components are victim selection and the stealing mechanism. 422 410 423 \subsection{Stealing Mechanism} 411 In this discussion of work stealing the worker being stolen from will be referred to as the \textbf{victim} and the worker stealing work will be called the \textbf{thief}.412 The stealing mechanism presented here differs from existing work stealing actor systems due the inverted actorsystem.413 Other actor systems such as Akka \cite{} and CAF \cite{} have work stealing, but since they use an classic actor system that is actor-centric, stealing work is the act of stealing an actor from a dequeue.414 As an example, in CAF, the sharded actor queue is a set of double 415 When ever an actor is moved to a ready queue, it is inserted into a worker's dequeue.424 In work stealing, the stealing worker is called the \Newterm{thief} and the stolen-from worker is called the \Newterm{victim}. 425 The stealing mechanism presented here differs from existing work-stealing actor-systems because of the message-centric (inverted) actor-system. 426 Other actor systems, such as Akka~\cite{Akka} and CAF~\cite{CAF}, have work stealing, but use an actor-centric system where stealing is dequeuing from a non-empty ready-queue to an empty ready-queue. 427 As an example, in CAF, the sharded actor queue is a set of double-ended queues (dequeues). 428 When an actor has messages, it is inserted into a worker's dequeue (ready queue). 416 429 Workers then consume actors from the dequeue and execute their behaviours. 417 430 To steal work, thieves take one or more actors from a victim's dequeue. 418 This action creates contention on the dequeue, which can slow down the throughput of the victim. 419 The notion of which end of the dequeue is used for stealing, consuming, and inserting is not discussed since it isn't relevant. 420 By the pigeon hole principle there are three dequeue operations (push/victim pop/thief pop) that can occur concurrently and only two ends to a dequeue, so work stealing being present in a dequeue based system will always result in a potential increase in contention on the dequeues. 431 By the pigeon hole principle, there are three dequeue operations (push/victim pop/thief pop) that can occur concurrently and only two ends to a dequeue, so work stealing in a dequeue-based system always results in a potential increase in contention on the dequeues. 432 This contention can slows down the victim's throughput. 433 Note, which end of the dequeue is used for stealing, consuming, and inserting is not discussed since the largest cost is the mutual exclusion and its duration for safely performing the queue operations. 434 435 Work steal now becomes queue stealing, where an entire actor/message queue is stolen, which trivially preserves message ordering in a queue \see{Section~\ref{s:steal}}. 421 436 422 437 % C_TODO: maybe insert stealing diagram 423 438 424 In \CFA, the actor work stealing implementation is unique. 425 While other systems are concerned with stealing actors, the \CFA actor system steals queues. 426 This is a result of \CFA's use of the inverted actor system. 427 The goal of the \CFA actor work stealing mechanism is to have a zero-victim-cost stealing mechanism. 428 This does not means that stealing has no cost. 429 This goal is to ensure that stealing work does not impact the performance of victim workers. 430 This means that thieves can not contend with victims, and that victims should perform no stealing related work unless they become a thief. 431 In theory this goal is not achieved, but results will be presented that show the goal is achieved in practice. 432 In \CFA's actor system workers own a set of sharded queues which they iterate over and gulp. 433 If a worker has iterated over the queues they own twice without finding any work, they try to steal a queue from another worker. 434 Stealing a queue is done wait-free with a few atomic instructions that can only create contention with other stealing workers. 435 To steal a queue a worker does the following: 439 In \CFA, the actor work-stealing implementation is unique because of the message-centric system. 440 In this system, it is impractical to steal actors because an actor's messages are distributed in temporal order along the message queue. 441 To ensure sequential actor execution and FIFO message delivery, actor stealing requires finding and removing all of an actor's messages, and inserting them consecutively in another message queue. 442 This operation is $O(N)$ with a non-trivial constant. 443 The only way for work stealing to become practical is to shard the message queue, which also reduces contention, and steal queues to eliminate queue searching. 444 445 Given queue stealing, the goal is to have a zero-victim-cost stealing mechanism, which does not mean stealing has no cost. 446 It means work stealing does not affect the performance of the victim worker. 447 The implication is that thieves cannot contend with a victim, and that a victim should perform no stealing related work unless it becomes a thief. 448 In theory, this goal is not achievable, but results show the goal is achieved in practice. 449 450 In \CFA's actor system, workers own a set of sharded queues, which they iterate over and gulp. 451 If a worker has iterated over its message queues twice without finding any work, it tries to steal a queue from another worker. 452 Stealing a queue is done wait-free with a few atomic instructions that can only create contention with other stealing workers, not the victim. 453 To steal a queue, a worker does the following: 436 454 \begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt] 437 455 \item 438 The thief chooses a victim .456 The thief chooses a victim, which is trivial because all workers are stored in a shared array. 439 457 440 458 \item 441 459 The thief starts at a random index in the array of the victim's queues and searches for a candidate queue. 442 A candidate queue is any queue that is not empty, is not being stolen by another thief, and is not being processed by the victim. 443 These are not strictly enforced rules. 444 The candidate is identified non-atomically and as such queues that do not satisfy these rules may be stolen. 445 However, steals that do not meet these requirements do not affect correctness so they are allowed and do not constitute failed steals as the queues will still be swapped. 446 447 448 \item 449 Once a candidate queue is chosen, the thief attempts a wait-free swap of the victim's queue and a random on of the thief's queues. 450 This swap can fail. 451 If the swap is successful the thief swaps the two queues. 452 If the swap fails, another thief must have attempted to steal one of the two queues being swapped. 453 Failing to steal is good in this case since stealing a queue that was just swapped would likely result in stealing an empty queue. 460 A candidate queue is any non-empty queue not being processed by the victim and not being stolen by another thief. 461 These rules are not strictly enforced. 462 A candidate is identified non-atomically, and as such, queues that do not satisfy these rules may be stolen. 463 However, steals not meeting the rules do not affect correctness and do not constitute failed steals as the queue is always swapped. 464 465 \item 466 Once a candidate queue is chosen, the thief attempts a wait-free swap of a victim's queue to a random empty thief queue. 467 If the swap successes, the steal is completed. 468 If the swap fails, the victim may have been gulping that message queue or another thief must have attempted to steal the victim's queue. 469 In either case, that message queue is highly likely to be empty. 470 471 \item 472 Once a thief fails or succeeds in stealing a queue, it iterates over its messages queues again because new messages may have arrived during stealing. 473 Stealing is only repeated after two consecutive iterations over its owned queues without finding work. 454 474 \end{enumerate} 455 475 456 Once a thief fails or succeeds in stealing a queue, it goes back to its own set of queues and iterates over them again.457 It will only try to steal again once it has completed two consecutive iterations over its owned queues without finding any work.458 476 The key to the stealing mechanism is that the queues can still be operated on while they are being swapped. 459 This eliminates any contention between thieves and victims. 477 This functionality eliminates any contention among thieves and victims. 478 460 479 The first key to this is that actors and workers maintain two distinct arrays of references to queues. 461 480 Actors will always receive messages via the same queues.
Note: See TracChangeset
for help on using the changeset viewer.