Changes in / [6d18ddb:df27752]

File:

• doc/theses/colby_parsons_MMAth/text/actors.tex (modified) (7 diffs)

doc/theses/colby_parsons_MMAth/text/actors.tex

@@ -7 +7 @@
 % C_TODO: add citations throughout chapter
 Actors are an indirect concurrent feature that abstracts threading away from a programmer, and instead provides \gls{actor}s and messages as building blocks for concurrency, where message passing means there is no shared data to protect, making actors amenable in a distributed environment.
-Actors are another message passing concurrency feature, similar to channels but with more abstraction, and are in the realm of \gls{impl_concurrency}, where programmers write concurrent code without dealing with explicit thread creation or interaction.
+Actors are another message passing concurrency feature, similar to channels but with more abstraction, and are in the realm of \gls{impl_concurrency}, where programmers write concurrent code without dealing with explicit thread create or interaction.
 The study of actors can be broken into two concepts, the \gls{actor_model}, which describes the model of computation and the \gls{actor_system}, which refers to the implementation of the model.
 Before discussing \CFA's actor system in detail, it is important to first describe the actor model, and the classic approach to implementing an actor system.
@@ -244 +244 @@
 Because a C program manages message lifetime, messages cannot be copied for each send, otherwise who manages the copies.
 Therefore, it up to the actor program to manage message life-time across receives.
-However, for a message to appear on multiple message queues, it needs an arbitrary number of associated destination behaviours.
+However, for a message to appear on multiple message queues, it needs an arbitrary number of link fields.
 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.
 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.
@@ -281 +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.
 
+% All message sends are done using the vertical-bar operator, @?|?@, similar to the syntax of \CC's stream output.
+% \begin{cfa}
+% allocation ?|?( my_actor & receiver, my_msg & msg )
+% \end{cfa}
+% Notice this signature is the same as the @receive@ routine, which is no coincidence.
+% The \CFA compiler generates a @?|?@ routine definition and forward declaration for each @receive@ routine that has the appropriate signature.
+% 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.
+% 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.
+
 \subsection{Actor Send}\label{s:ActorSend}
 All message sends are done using the vertical-bar (bit-or) operator, @?|?@, similar to the syntax of the \CFA stream I/O.
-Hence, programmers must write a matching @?|?@ routine for each @receive@ routine, which is awkward and generates a maintenance problem That must be solved.
-The currently supported approach to creating a generic @?|?@ routine requires users to create specific routines for their actor and message types that access the base type.
-Since these routines are not complex, they can be generated using macros that the user can add following their message and actor types.
-This works, but is not much better than asking users to write the @?|?@ routine themselves.
-
 As stated, \CFA does not have named inheritance with RTTI.
 \CFA does have a preliminary form of virtual routines, but it is not mature enough for use in this work.
-Virtuals would provide a clean mechanism to write a single generic @?|?@ routine taking a base actor and message type, and then dynamically selecting the @receive@ routine from the actor argument.
-Note, virtuals are not needed for the send; Plan-9 inheritance is sufficient because only the inherited fields are needed during the message send (only upcasting is needed).
-
-Therefore, a template-like approach was chosen, where the compiler generates a matching @?|?@ routine for each @receive@ routine it finds with the correct actor/message type-signature.
-This approach requires no annotation or additional code to be written by users, thus it resolves the maintenance problem.
+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.
+(For messages, the Plan-9 inheritance is sufficient because only the inherited fields are needed during the message send.)
+Hence, programmers must write a matching @?|?@ routine for each @receive@ routine, which is awkward and generates a maintenance problem.
+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.
 (When the \CFA virtual routines mature, it should be possible to seamlessly transition to it from the template approach.)
+
+% 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@.
+% As such a @?|?@ routine per @receive@ provides type information needed to write the correct "address" on the envelope.
 
 Figure~\ref{f:send_gen} shows the generated send routine for the @int_msg@ receive in Figure~\ref{f:CFAActor}.
@@ -323 +329 @@
 \end{figure}
 
-\subsection{Actor Termination}\label{s:ActorTerm}
-As discussed in Section~\ref{s:ActorSend}, during a message send, the derived type of the actor and message is erased, and then recovered later by calling the receive routine.
-After the receive routine is done, the executor must clean up the actor and message according to their allocation status.
-If the allocation status is @Delete@ or @Destroy@, the appropriate destructor must be called by the executor.
-This poses a problem; the type of the actor or message is not available to the executor, but it needs to call the right destructor!
-This requires down-casting from the base type to derived type, which requires a virtual system.
-Thus, a rudimentary destructor-only virtual system was added to \CFA as part of this work.
-This virtual system is used via Plan-9 inheritance of the @virtual_dtor@ type.
-The @virtual_dtor@ type maintains a pointer to the start of the object, and a pointer to the correct destructor.
-When a type inherits the @virtual_dtor@ type, the compiler adds code to its destructor to make sure that whenever any destructor along inheritance tree is called, the destructor call is intercepted, and restarts at the appropriate destructor for that object.
-
-\begin{figure}
-\begin{cfa}
-struct base_type { inline virtual_dtor; };
-struct intermediate_type { inline base_type; };
-struct derived_type { inline intermediate_type; };
-
-int main() {
-    derived_type d1, d2, d3;
-    intermediate_type & i = d2;
-    base_type & b = d3;
-    ^d1{}; ^i{}; ^b{}; // all of these will call the destructors in the correct order
-}
-
-\end{cfa}
-\caption{\CFA Virtual Destructor}
-\label{f:VirtDtor}
-\end{figure}
-
-This virtual destructor system was built for this work, but is general and can be used in any type in \CFA.
-Actors and messages opt into this system by inheriting the @virtual_dtor@ type, which allows the executor to call the right destructor without knowing the derived actor or message type.
-
 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@.
 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.
@@ -437 +411 @@
 The next time 19 messages are enqueued, the array size is doubled to 36!
 To avoid this issue, a second check is added.
+% Each copy queue starts tracking the utilization of its array size.
 Reclamation only occurs if less than half of the array is utilized.
 This check achieves a lower total storage and overall memory utilization compared to the non-reclamation copy queues.
@@ -650 +625 @@
 
 \subsection{Stealing Guarantees}
+
+% C_TODO insert graphs for each proof
 Given that the stealing operation can potentially fail, it is important to discuss the guarantees provided by the stealing implementation.
 Given a set of $N$ swaps a set of connected directed graphs can be constructed where each vertex is a queue and each edge is a swap directed from a thief queue to a victim queue.
@@ -791 +768 @@
 Since the @Finished@ allocation status is unused for messages, it is used internally to detect if a message has been sent.
 Deallocating a message without sending it could indicate to a user that they are touching freed memory later, or it could point out extra allocations that could be removed.
-\item Detection of messages sent but not received
-As discussed in Section~\ref{s:executor}, once all actors have terminated shutdown is communicated to executor threads via a status flag. Upon termination the executor threads check their queues to see if any contain messages. If they do, an error is reported. Messages being sent but not received means that their allocation action did not occur and their payload was not delivered. Missing the allocation action can lead to memory leaks and missed payloads can cause unpredictable behaviour. Detecting this can indicate a race or logic error in the user's code.
 \end{itemize}