Changeset deda7e6 for doc


Ignore:
Timestamp:
Sep 21, 2023, 10:15:58 PM (2 years ago)
Author:
JiadaL <j82liang@…>
Branches:
master
Children:
62c6cfa
Parents:
c1e66d9 (diff), 5a1ae14 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc
Files:
3 added
9 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/colby_parsons_MMAth/local.bib

    rc1e66d9 rdeda7e6  
    212212    year        = 2023,
    213213}
     214
     215@inproceedings{Harris02,
     216  title={A practical multi-word compare-and-swap operation},
     217  author={Harris, Timothy L and Fraser, Keir and Pratt, Ian A},
     218  booktitle={Distributed Computing: 16th International Conference, DISC 2002 Toulouse, France, October 28--30, 2002 Proceedings 16},
     219  pages={265--279},
     220  year={2002},
     221  organization={Springer}
     222}
     223
     224@misc{kotlin:channel,
     225  author = "Kotlin Documentation",
     226  title = "Channel",
     227  howpublished = {\url{https://kotlinlang.org/api/kotlinx.coroutines/kotlinx-coroutines-core/kotlinx.coroutines.channels/-channel/}},
     228  note = "[Online; accessed 11-September-2023]"
     229}

  • doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex

    rc1e66d9 rdeda7e6  
    11\chapter{Concurrency in \CFA}\label{s:cfa_concurrency}
    22
    3 The groundwork for concurrency in \CFA was laid by Thierry Delisle in his Master's Thesis~\cite{Delisle18}. 
    4 In that work, he introduced generators, coroutines, monitors, and user-level threading. 
    5 Not listed in that work were basic concurrency features needed as building blocks, such as locks, futures, and condition variables, which he also added to \CFA.
     3The groundwork for concurrency in \CFA was laid by Thierry Delisle in his Master's Thesis~\cite{Delisle18}.
     4In that work, he introduced generators, coroutines, monitors, and user-level threading.
     5Not listed in that work were basic concurrency features needed as building blocks, such as locks, futures, and condition variables.
    66
    77\section{Threading Model}\label{s:threading}
    8 \CFA provides user-level threading and supports an $M$:$N$ threading model where $M$ user threads are scheduled on $N$ kernel threads, where both $M$ and $N$ can be explicitly set by the user.
    9 Kernel threads are created by declaring a @processor@ structure.
    10 User-thread types are defined by creating a @thread@ aggregate-type, \ie replace @struct@ with @thread@.
    11 For each thread type a corresponding @main@ routine must be defined, which is where the thread starts running once it is created.
    12 Examples of \CFA  user thread and processor creation are shown in \VRef[Listing]{l:cfa_thd_init}.
    138
     9\CFA provides user-level threading and supports an $M$:$N$ threading model where $M$ user threads are scheduled on $N$ kernel threads and both $M$ and $N$ can be explicitly set by the programmer.
     10Kernel threads are created by declaring processor objects;
     11user threads are created by declaring a thread objects.
     12\VRef[Listing]{l:cfa_thd_init} shows a typical examples of creating a \CFA user-thread type, and then as declaring processor ($N$) and thread objects ($M$).
    1413\begin{cfa}[caption={Example of \CFA user thread and processor creation},label={l:cfa_thd_init}]
    15 @thread@ my_thread {...};                       $\C{// user thread type}$
    16 void @main@( my_thread & this ) {       $\C{// thread start routine}$
     14@thread@ my_thread {                            $\C{// user thread type (like structure)}$
     15        ... // arbitrary number of field declarations
     16};
     17void @main@( @my_thread@ & this ) {     $\C{// thread start routine}$
    1718        sout | "Hello threading world";
    1819}
    19 
    20 int main() {
     20int main() {                                            $\C{// program starts with a processor (kernel thread)}$
    2121        @processor@ p[2];                               $\C{// add 2 processors = 3 total with starting processor}$
    2222        {
    23                 my_thread t[2], * t3 = new();   $\C{// create 3 user threads, running in main routine}$
     23                @my_thread@ t[2], * t3 = new(); $\C{// create 2 stack allocated, 1 dynamic allocated user threads}$
    2424                ... // execute concurrently
    25                 delete( t3 );                           $\C{// wait for thread to end and deallocate}$
    26         } // wait for threads to end and deallocate
    27 }
     25                delete( t3 );                           $\C{// wait for t3 to end and deallocate}$
     26    } // wait for threads t[0] and t[1] to end and deallocate
     27} // deallocate additional kernel threads
    2828\end{cfa}
    29 
    30 When processors are added, they are added alongside the existing processor given to each program.
    31 Thus, for $N$ processors, allocate $N-1$ processors.
    32 A thread is implicitly joined at deallocation, either implicitly at block exit for stack allocation or explicitly at @delete@ for heap allocation.
    33 The thread performing the deallocation must wait for the thread to terminate before the deallocation can occur.
     29A thread type is are defined using the aggregate kind @thread@.
     30For each thread type, a corresponding @main@ routine must be defined, which is where the thread starts running once when a thread object are is created.
     31The @processor@ declaration adds addition kernel threads alongside the existing processor given to each program.
     32Thus, for $N$ processors, allocate $N-1$ processors.
     33A thread is implicitly joined at deallocation, either implicitly at block exit for stack allocation or explicitly at @delete@ for heap allocation.
     34The thread performing the deallocation must wait for the thread to terminate before the deallocation can occur.
    3435A thread terminates by returning from the main routine where it starts.
    3536
    36 \section{Existing Concurrency Features}
     37\section{Existing and New Concurrency Features}
     38
    3739\CFA currently provides a suite of concurrency features including futures, locks, condition variables, generators, coroutines, monitors.
    3840Examples of these features are omitted as most of them are the same as their counterparts in other languages.
    3941It is worthwhile to note that all concurrency features added to \CFA are made to be compatible each other.
    40 The laundry list of features above and the ones introduced in this thesis can be used in the same program without issue.
     42The laundry list of features above and the ones introduced in this thesis can be used in the same program without issue, and the features are designed to interact in meaningful ways.
     43For example, a thread can inteact with a monitor, which can interact with a coroutine, which can interact with a generator.
    4144
    4245Solving concurrent problems requires a diverse toolkit.

  • doc/theses/colby_parsons_MMAth/text/CFA_intro.tex

    rc1e66d9 rdeda7e6  
    99\CFA is a layer over C, is transpiled\footnote{Source to source translator.} to C, and is largely considered to be an extension of C.
    1010Beyond C, it adds productivity features, extended libraries, an advanced type-system, and many control-flow/concurrency constructions.
    11 However, \CFA stays true to the C programming style, with most code revolving around @struct@'s and routines, and respects the same rules as C.
     11However, \CFA stays true to the C programming style, with most code revolving around @struct@s and routines, and respects the same rules as C.
    1212\CFA is not object oriented as it has no notion of @this@ (receiver) and no structures with methods, but supports some object oriented ideas including constructors, destructors, and limited nominal inheritance.
    1313While \CFA is rich with interesting features, only the subset pertinent to this work is discussed here.
    … …  
    1717References in \CFA are a layer of syntactic sugar over pointers to reduce the number of syntactic ref/deref operations needed with pointer usage.
    1818Pointers in \CFA differ from C and \CC in their use of @0p@ instead of C's @NULL@ or \CC's @nullptr@.
     19References can contain 0p in \CFA, which is the equivalent of a null reference.
    1920Examples of references are shown in \VRef[Listing]{l:cfa_ref}.
    2021
    … …  
    6465This feature is also implemented in Pascal~\cite{Pascal}.
    6566It can exist as a stand-alone statement or wrap a routine body to expose aggregate fields.
     67If exposed fields share a name, the type system will attempt to disambiguate them based on type.
     68If the type system is unable to disambiguate the fields then the user must qualify those names to avoid a compilation error.
    6669Examples of the @with@ statement are shown in \VRef[Listing]{l:cfa_with}.
    6770

  • doc/theses/colby_parsons_MMAth/text/actors.tex

    rc1e66d9 rdeda7e6  
    77Actors 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.
    88Hence, actors are in the realm of \gls{impl_concurrency}, where programmers write concurrent code without dealing with explicit thread creation or interaction.
    9 Actor message-passing is similar to channels, but with more abstraction, so there is no shared data to protect, making actors amenable in a distributed environment.
     9Actor message-passing is similar to channels, but with more abstraction, so there is no shared data to protect, making actors amenable to a distributed environment.
    1010Actors are often used for high-performance computing and other data-centric problems, where the ease of use and scalability of an actor system provides an advantage over channels.
    1111
    … …  
    1414
    1515\section{Actor Model}
    16 The \Newterm{actor model} is a concurrent paradigm where computation is broken into units of work called actors, and the data for computation is distributed to actors in the form of messages~\cite{Hewitt73}.
     16The \Newterm{actor model} is a concurrent paradigm where an actor is used as the fundamental building-block for computation, and the data for computation is distributed to actors in the form of messages~\cite{Hewitt73}.
    1717An actor is composed of a \Newterm{mailbox} (message queue) and a set of \Newterm{behaviours} that receive from the mailbox to perform work.
    1818Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors.
    … …  
    2222For example, mutual exclusion and locking are rarely relevant concepts in an actor model, as actors typically only operate on local state.
    2323
    24 An actor does not have a thread.
     24\subsection{Classic Actor System}
     25An implementation of the actor model with a theatre (group) of actors is called an \Newterm{actor system}.
     26Actor systems largely follow the actor model, but can differ in some ways.
     27
     28In an actor system, an actor does not have a thread.
    2529An 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.
    2630The default number of executor threads is often proportional to the number of computer cores to achieve good performance.
    2731An 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{Section~\ref{s:ActorSystem}}.
    2832
    29 \subsection{Classic Actor System}
    30 An implementation of the actor model with a community of actors is called an \Newterm{actor system}.
    31 Actor systems largely follow the actor model, but can differ in some ways.
    3233While the semantics of message \emph{send} is asynchronous, the implementation may be synchronous or a combination.
    33 The default semantics for message \emph{receive} is \gls{fifo}, so an actor receives messages from its mailbox in temporal (arrival) order;
    34 however, messages sent among actors arrive in any order.
     34The default semantics for message \emph{receive} is \gls{fifo}, so an actor receives messages from its mailbox in temporal (arrival) order.
     35% however, messages sent among actors arrive in any order.
    3536Some actor systems provide priority-based mailboxes and/or priority-based message-selection within a mailbox, where custom message dispatchers search among or within a mailbox(es) with a predicate for specific kinds of actors and/or messages.
    36 Some actor systems provide a shared mailbox where multiple actors receive from a common mailbox~\cite{Akka}, which is contrary to the no-sharing design of the basic actor-model (and requires additional locking).
    37 For non-\gls{fifo} service, some notion of fairness (eventual progress) must exist, otherwise messages have a high latency or starve, \ie never received.
    38 Finally, some actor systems provide multiple typed-mailboxes, which then lose the actor-\lstinline{become} mechanism \see{Section~\ref{s:SafetyProductivity}}.
     37Some actor systems provide a shared mailbox where multiple actors receive from a common mailbox~\cite{Akka}, which is contrary to the no-sharing design of the basic actor-model (and may require additional locking).
     38For non-\gls{fifo} service, some notion of fairness (eventual progress) should exist, otherwise messages have a high latency or starve, \ie are never received.
     39% Finally, some actor systems provide multiple typed-mailboxes, which then lose the actor-\lstinline{become} mechanism \see{Section~\ref{s:SafetyProductivity}}.
    3940%While the definition of the actor model provides no restrictions on message ordering, actor systems tend to guarantee that messages sent from a given actor $i$ to actor $j$ arrive at actor $j$ in the order they were sent.
    4041Another way an actor system varies from the model is allowing access to shared global-state.
    … …  
    6061Figure \ref{f:inverted_actor} shows an actor system designed as \Newterm{message-centric}, where a set of messages are scheduled and run on underlying executor threads~\cite{uC++,Nigro21}.
    6162This design is \Newterm{inverted} because actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor.
    62 Now a message send must queries the actor to know which message queue to post the message.
     63Now a message send must query the actor to know which message queue to post the message to.
    6364Again, the simplest design has a single global queue of messages accessed by the executor threads, but this approach has the same contention problem by the executor threads.
    6465Therefore, the messages (mailboxes) are sharded and executor threads schedule each message, which points to its corresponding actor.
    … …  
    176177        @actor | str_msg | int_msg;@                    $\C{// cascade sends}$
    177178        @actor | int_msg;@                                              $\C{// send}$
    178         @actor | finished_msg;@                                 $\C{// send => terminate actor (deallocation deferred)}$
     179        @actor | finished_msg;@                                 $\C{// send => terminate actor (builtin Poison-Pill)}$
    179180        stop_actor_system();                                    $\C{// waits until actors finish}\CRT$
    180181} // deallocate actor, int_msg, str_msg
    … …  
    492493Each executor thread iterates over its own message queues until it finds one with messages.
    493494At 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.
     495Gulping moves the contents of the message queue as a batch rather than removing individual elements.
    494496An example of the queue gulping operation is shown in the right side of Figure \ref{f:gulp}, where an executor thread gulps queue 0 and begins to process it locally.
    495497This step allows the executor thread to process the local queue without any atomics until the next gulp.
    … …  
    523525
    524526Since the copy queue is an array, envelopes are allocated first on the stack and then copied into the copy queue to persist until they are no longer needed.
    525 For many workloads, the copy queues grow in size to facilitate the average number of messages in flight and there are no further dynamic allocations.
     527For many workloads, the copy queues reallocate and grow in size to facilitate the average number of messages in flight and there are no further dynamic allocations.
    526528The downside of this approach is that more storage is allocated than needed, \ie each copy queue is only partially full.
    527529Comparatively, 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.
    … …  
    562564To ensure sequential actor execution and \gls{fifo} message delivery in a message-centric system, stealing requires finding and removing \emph{all} of an actor's messages, and inserting them consecutively in another message queue.
    563565This operation is $O(N)$ with a non-trivial constant.
    564 The only way for work stealing to become practical is to shard each worker's message queue, which also reduces contention, and to steal queues to eliminate queue searching.
     566The only way for work stealing to become practical is to shard each worker's message queue \see{Section~\ref{s:executor}}, which also reduces contention, and to steal queues to eliminate queue searching.
    565567
    566568Given queue stealing, the goal of the presented stealing implementation is to have an essentially zero-contention-cost stealing mechanism.
    … …  
    576578
    577579The outline for lazy-stealing by a thief is: select a victim, scan its queues once, and return immediately if a queue is stolen.
    578 The thief then assumes it normal operation of scanning over its own queues looking for work, where stolen work is placed at the end of the scan.
     580The thief then assumes its normal operation of scanning over its own queues looking for work, where stolen work is placed at the end of the scan.
    579581Hence, only one victim is affected and there is a reasonable delay between stealing events as the thief scans its ready queue looking for its own work before potentially stealing again.
    580582This lazy examination by the thief has a low perturbation cost for victims, while still finding work in a moderately loaded system.
    … …  
    636638% Note that a thief never exceeds its $M$/$N$ worker range because it is always exchanging queues with other workers.
    637639If no appropriate victim mailbox is found, no swap is attempted.
     640Note that since the mailbox checks happen non-atomically, the thieves effectively guess which mailbox is ripe for stealing.
     641The thief may read stale data and can end up stealing an ineligible or empty mailbox.
     642This is not a correctness issue and is addressed in Section~\ref{s:steal_prob}, but the steal will likely not be productive.
     643These unproductive steals are uncommon, but do occur with some frequency, and are a tradeoff that is made to achieve minimal victim contention.
    638644
    639645\item
    … …  
    644650\end{enumerate}
    645651
    646 \subsection{Stealing Problem}
     652\subsection{Stealing Problem}\label{s:steal_prob}
    647653Each queue access (send or gulp) involving any worker (thief or victim) is protected using spinlock @mutex_lock@.
    648654However, to achieve the goal of almost zero contention for the victim, it is necessary that the thief does not acquire any queue spinlocks in the stealing protocol.
    … …  
    703709None of the work-stealing actor-systems examined in this work perform well on the repeat benchmark.
    704710Hence, for all non-pathological cases, the claim is made that this stealing mechanism has a (probabilistically) zero-victim-cost in practice.
     711Future work on the work stealing system could include a backoff mechanism after failed steals to further address the pathological cases.
    705712
    706713\subsection{Queue Pointer Swap}\label{s:swap}
    … …  
    709716The \gls{cas} is a read-modify-write instruction available on most modern architectures.
    710717It atomically compares two memory locations, and if the values are equal, it writes a new value into the first memory location.
    711 A software implementation of \gls{cas} is:
     718A sequential specification of \gls{cas} is:
    712719\begin{cfa}
    713720// assume this routine executes atomically
    … …  
    755762
    756763Either a true memory/memory swap instruction or a \gls{dcas} would provide the ability to atomically swap two memory locations, but unfortunately neither of these instructions are supported on the architectures used in this work.
     764There are lock-free implemetions of DCAS, or more generally K-word CAS (also known as MCAS or CASN)~\cite{Harris02} and LLX/SCX~\cite{Brown14} that can be used to provide the desired atomic swap capability.
     765However, these lock-free implementations were not used as it is advantageous in the work stealing case to let an attempted atomic swap fail instead of retrying.
    757766Hence, a novel atomic swap specific to the actor use case is simulated, called \gls{qpcas}.
     767Note that this swap is \emph{not} lock-free.
    758768The \gls{qpcas} is effectively a \gls{dcas} special cased in a few ways:
    759769\begin{enumerate}
    … …  
    766776\end{cfa}
    767777\item
    768 The values swapped are never null pointers, so a null pointer can be used as an intermediate value during the swap.
     778The values swapped are never null pointers, so a null pointer can be used as an intermediate value during the swap. As such, null is effectively used as a lock for the swap.
    769779\end{enumerate}
    770780Figure~\ref{f:qpcasImpl} shows the \CFA pseudocode for the \gls{qpcas}.
    … …  
    862872The concurrent proof of correctness is shown through the existence of an invariant.
    863873The invariant states when a queue pointer is set to @0p@ by a thief, then the next write to the pointer can only be performed by the same thief.
     874This is effictively a mutual exclusion condition for the later write.
    864875To show that this invariant holds, it is shown that it is true at each step of the swap.
    865876\begin{itemize}
    … …  
    10111022The intuition behind this heuristic is that the slowest worker receives help via work stealing until it becomes a thief, which indicates that it has caught up to the pace of the rest of the workers.
    10121023This heuristic should ideally result in lowered latency for message sends to victim workers that are overloaded with work.
     1024It must be acknowledged that this linear search could cause a lot of cache coherence traffic.
     1025Future work on this heuristic could include introducing a search that has less impact on caching.
    10131026A negative side-effect of this heuristic is that if multiple thieves steal at the same time, they likely steal from the same victim, which increases the chance of contention.
    10141027However, given that workers have multiple queues, often in the tens or hundreds of queues, it is rare for two thieves to attempt stealing from the same queue.
    … …  
    10281041\CFA's actor system comes with a suite of safety and productivity features.
    10291042Most of these features are only present in \CFA's debug mode, and hence, have zero-cost in no-debug mode.
    1030 The suit of features include the following.
     1043The suite of features include the following.
    10311044\begin{itemize}
    10321045\item Static-typed message sends:
    1033 If an actor does not support receiving a given message type, the receive call is rejected at compile time, allowing unsupported messages to never be sent to an actor.
     1046If an actor does not support receiving a given message type, the receive call is rejected at compile time, preventing unsupported messages from being sent to an actor.
    10341047
    10351048\item Detection of message sends to Finished/Destroyed/Deleted actors:
    … …  
    10421055
    10431056\item When an executor is configured, $M >= N$.
    1044 That is, each worker must receive at least one mailbox queue, otherwise the worker spins and never does any work.
     1057That is, each worker must receive at least one mailbox queue, since otherwise a worker cannot receive any work without a queue pull messages from.
    10451058
    10461059\item Detection of unsent messages:
    … …  
    11001113\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=5pt\parsep=5pt\itemsep=0pt}
    11011114\item
    1102 Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets (48 process\-ing units) 2.2GHz, running Linux v5.8.0--59--generic
    1103 \item
    1104 Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units) 2.0 GHz, running Linux v5.8.0--55--generic
     1115Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets (96 process\-ing units), running Linux v5.8.0--59--generic
     1116\item
     1117Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units), running Linux v5.8.0--55--generic
    11051118\end{list}
    11061119
    … …  
    11121125All benchmarks are run 5 times and the median is taken.
    11131126Error bars showing the 95\% confidence intervals appear on each point in the graphs.
     1127The confidence intervals are calculated using bootstrapping to avoid normality assumptions.
    11141128If the confidence bars are small enough, they may be obscured by the data point.
    11151129In this section, \uC is compared to \CFA frequently, as the actor system in \CFA is heavily based off of \uC's actor system.

  • doc/theses/colby_parsons_MMAth/text/channels.tex

    rc1e66d9 rdeda7e6  
    2020Neither Go nor \CFA channels have the restrictions of the early channel-based concurrent systems.
    2121
    22 Other popular languages and libraries that provide channels include C++ Boost~\cite{boost:channel}, Rust~\cite{rust:channel}, Haskell~\cite{haskell:channel}, and OCaml~\cite{ocaml:channel}.
     22Other popular languages and libraries that provide channels include C++ Boost~\cite{boost:channel}, Rust~\cite{rust:channel}, Haskell~\cite{haskell:channel}, OCaml~\cite{ocaml:channel}, and Kotlin~\cite{kotlin:channel}.
    2323Boost channels only support asynchronous (non-blocking) operations, and Rust channels are limited to only having one consumer per channel.
    2424Haskell channels are unbounded in size, and OCaml channels are zero-size.
    2525These restrictions in Haskell and OCaml are likely due to their functional approach, which results in them both using a list as the underlying data structure for their channel.
    2626These languages and libraries are not discussed further, as their channel implementation is not comparable to the bounded-buffer style channels present in Go and \CFA.
     27Kotlin channels are comparable to Go and \CFA, but unfortunately they were not identified as a comparator until after presentation of this thesis and are omitted due to time constraints.
    2728
    2829\section{Producer-Consumer Problem}
    … …  
    3132In the problem, threads interact with a buffer in two ways: producing threads insert values into the buffer and consuming threads remove values from the buffer.
    3233In general, a buffer needs protection to ensure a producer only inserts into a non-full buffer and a consumer only removes from a non-empty buffer (synchronization).
    33 As well, a buffer needs protection from concurrent access by multiple producers or consumers attempting to insert or remove simultaneously (MX).
     34As well, a buffer needs protection from concurrent access by multiple producers or consumers attempting to insert or remove simultaneously, which is often provided by MX.
    3435
    3536\section{Channel Size}\label{s:ChannelSize}
    … …  
    4142Fixed sized (bounded) implies the communication is mostly asynchronous, \ie the producer can proceed up to the buffer size and vice versa for the consumer with respect to removal, at which point the producer/consumer would wait.
    4243\item
    43 Infinite sized (unbounded) implies the communication is asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty.
    44 Since memory is finite, all unbounded buffers are ultimately bounded;
    45 this restriction must be part of its implementation.
     44Infinite sized (unbounded) implies the communication is asymmetrically asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty.
    4645\end{enumerate}
    4746
    … …  
    5049However, like MX, a buffer should ensure every value is eventually removed after some reasonable bounded time (no long-term starvation).
    5150The simplest way to prevent starvation is to implement the buffer as a queue, either with a cyclic array or linked nodes.
     51While \gls{fifo} is not required for producer-consumer problem correctness, it is a desired property in channels as it provides predictable and often relied upon channel ordering behaviour to users.
    5252
    5353\section{First-Come First-Served}
    54 As pointed out, a bounded buffer requires MX among multiple producers or consumers.
     54As pointed out, a bounded buffer implementation often provides MX among multiple producers or consumers.
    5555This MX should be fair among threads, independent of the \gls{fifo} buffer being fair among values.
    5656Fairness among threads is called \gls{fcfs} and was defined by Lamport~\cite[p.~454]{Lamport74}.
    … …  
    6666
    6767\section{Channel Implementation}\label{s:chan_impl}
    68 Currently, only the Go and Erlang programming languages provide user-level threading where the primary communication mechanism is channels.
    69 Both Go and Erlang have user-level threading and preemptive scheduling, and both use channels for communication.
    70 Go provides multiple homogeneous channels; each have a single associated type.
     68The programming languages Go, Kotlin, and Erlang provide user-level threading where the primary communication mechanism is channels.
     69These languages have user-level threading and preemptive scheduling, and both use channels for communication.
     70Go and Kotlin provide multiple homogeneous channels; each have a single associated type.
    7171Erlang, which is closely related to actor systems, provides one heterogeneous channel per thread (mailbox) with a typed receive pattern.
    72 Go encourages users to communicate via channels, but provides them as an optional language feature.
     72Go and Kotlin encourage users to communicate via channels, but provides them as an optional language feature.
    7373On the other hand, Erlang's single heterogeneous channel is a fundamental part of the threading system design; using it is unavoidable.
    74 Similar to Go, \CFA's channels are offered as an optional language feature.
     74Similar to Go and Kotlin, \CFA's channels are offered as an optional language feature.
    7575
    7676While iterating on channel implementation, experiments were conducted that varied the producer-consumer algorithm and lock type used inside the channel.
    … …  
    8383The Go channel implementation utilizes cooperation among threads to achieve good performance~\cite{go:chan}.
    8484This cooperation only occurs when producers or consumers need to block due to the buffer being full or empty.
     85After a producer blocks it must wait for a consumer to signal it and vice versa.
     86The consumer or producer that signals a blocked thread is called the signalling thread.
    8587In these cases, a blocking thread stores their relevant data in a shared location and the signalling thread completes the blocking thread's operation before waking them;
    8688\ie the blocking thread has no work to perform after it unblocks because the signalling threads has done this work.
    … …  
    8890First, each thread interacting with the channel only acquires and releases the internal channel lock once.
    8991As a result, contention on the internal lock is decreased; only entering threads compete for the lock since unblocking threads do not reacquire the lock.
    90 The other advantage of Go's wait-morphing approach is that it eliminates the bottleneck of waiting for signalled threads to run.
     92The other advantage of Go's wait-morphing approach is that it eliminates the need to wait for signalled threads to run.
    9193Note that the property of acquiring/releasing the lock only once can also be achieved with a different form of cooperation, called \Newterm{baton passing}.
    9294Baton passing occurs when one thread acquires a lock but does not release it, and instead signals a thread inside the critical section, conceptually ``passing'' the mutual exclusion from the signalling thread to the signalled thread.
    … …  
    9496the wait-morphing approach has threads cooperate by completing the signalled thread's operation, thus removing a signalled thread's need for mutual exclusion after unblocking.
    9597While baton passing is useful in some algorithms, it results in worse channel performance than the Go approach.
    96 In the baton-passing approach, all threads need to wait for the signalled thread to reach the front of the ready queue, context switch, and run before other operations on the channel can proceed, since the signalled thread holds mutual exclusion;
     98In the baton-passing approach, all threads need to wait for the signalled thread to unblock and run before other operations on the channel can proceed, since the signalled thread holds mutual exclusion;
    9799in the wait-morphing approach, since the operation is completed before the signal, other threads can continue to operate on the channel without waiting for the signalled thread to run.
    98100
    … …  
    154156Thus, improperly handled \gls{toctou} issues with channels often result in deadlocks as threads performing the termination may end up unexpectedly blocking in their attempt to help other threads exit the system.
    155157
     158\subsubsection{Go Channel Close}
    156159Go channels provide a set of tools to help with concurrent shutdown~\cite{go:chan} using a @close@ operation in conjunction with the \Go{select} statement.
    157160The \Go{select} statement is discussed in \ref{s:waituntil}, where \CFA's @waituntil@ statement is compared with the Go \Go{select} statement.
    … …  
    175178Hence, due to Go's asymmetric approach to channel shutdown, separate synchronization between producers and consumers of a channel has to occur during shutdown.
    176179
    177 \paragraph{\CFA channels} have access to an extensive exception handling mechanism~\cite{Beach21}.
     180\subsubsection{\CFA Channel Close}
     181\CFA channels have access to an extensive exception handling mechanism~\cite{Beach21}.
    178182As such \CFA uses an exception-based approach to channel shutdown that is symmetric for both producers and consumers, and supports graceful shutdown.
    179183

  • doc/theses/colby_parsons_MMAth/text/conclusion.tex

    rc1e66d9 rdeda7e6  
    55% ======================================================================
    66
    7 The goal of this thesis was to expand the concurrent support that \CFA offers to fill in gaps and support language users' ability to write safe and efficient concurrent programs.
    8 The presented features achieves this goal, and provides users with the means to write scalable programs in \CFA through multiple avenues.
    9 Additionally, the tools presented include safety and productivity features from deadlock detection, to detection of common programming errors, easy concurrent shutdown, and toggleable performance statistics.
    10 Programmers often have preferences between computing paradigms and concurrency is no exception.
    11 If users prefer the message passing paradigm of concurrency, \CFA now provides message passing utilities in the form of an actor system and channels.
    12 For shared memory concurrency, the mutex statement provides a safe and easy-to-use interface for mutual exclusion.
    13 The @waituntil@ statement aids in writing concurrent programs in both the message passing and shared memory paradigms of concurrency.
    14 Furthermore, no other language provides a synchronous multiplexing tool polymorphic over resources like \CFA's @waituntil@.
    15 This work successfully provides users with familiar concurrent language support, but with additional value added over similar utilities in other popular languages.
     7The goal of this thesis is to expand concurrent support in \CFA to fill in gaps and increase support for writing safe and efficient concurrent programs.
     8The presented features achieve this goal and provide users with the means to write scalable concurrent programs in \CFA through multiple avenues.
     9Additionally, the tools presented provide safety and productivity features including: detection of deadlock and other common concurrency errors, easy concurrent shutdown, and toggleable performance statistics.
    1610
    17 On overview of the contributions in this thesis include the following:
     11For locking, the mutex statement provides a safe and easy-to-use interface for mutual exclusion.
     12If programmers prefer the message-passing paradigm, \CFA now supports it in the form of channels and actors.
     13The @waituntil@ statement simplifies writing concurrent programs in both the message-passing and shared-memory paradigms of concurrency.
     14Finally, no other programming language provides a synchronous multiplexing tool that is polymorphic over resources like \CFA's @waituntil@.
     15This work successfully provides users with familiar concurrent-language support, but with additional value added over similar utilities in other popular languages.
     16
     17On overview of the contributions made in this thesis include the following:
    1818\begin{enumerate}
    19 \item The mutex statement, which provides performant and deadlock-free multiple lock acquisition.
    20 \item Channels with comparable performance to Go, that have safety and productivity features including deadlock detection, and an easy-to-use exception-based channel @close@ routine.
    21 \item An in-memory actor system that achieved the lowest latency message send of systems tested due to the novel copy-queue data structure. The actor system presented has built-in detection of six common actor errors, and it has good performance compared to other systems on all benchmarks.
    22 \item A @waituntil@ statement which tackles the hard problem of allowing a thread to safely synch\-ronously wait for some set of concurrent resources.
     19\item The mutex statement, which provides performant and deadlock-free multi-lock acquisition.
     20\item Channels with comparable performance to Go, which have safety and productivity features including deadlock detection and an easy-to-use exception-based channel @close@ routine.
     21\item An in-memory actor system, which achieves the lowest latency message send of systems tested due to the novel copy-queue data structure.
     22\item As well, the actor system has built-in detection of six common actor errors, with excellent performance compared to other systems across all benchmarks presented in this thesis.
     23\item A @waituntil@ statement, which tackles the hard problem of allowing a thread wait synchronously for an arbitrary set of concurrent resources.
    2324\end{enumerate}
    2425
    25 The features presented are commonly used in conjunction to solve concurrent problems.
    26 The @waituntil@ statement, the @mutex@ statement, and channels will all likely see use in a program where a thread operates as an administrator or server which accepts and distributes work among channels based on some shared state.
    27 The @mutex@ statement sees use across almost all concurrent code in \CFA, since it is used with the stream operator @sout@ to provide thread-safe output.
    28 While not yet implemented, the polymorphic support of the @waituntil@ statement could see use in conjunction with the actor system to enable user threads outside the actor system to wait for work to be done, or for actors to finish.
    29 A user of \CFA does not have to solely subscribe to the message passing or shared memory concurrent paradigm.
    30 As such, channels in \CFA are often used to pass pointers to shared memory that may still need mutual exclusion, requiring the @mutex@ statement to also be used.
     26The added features are now commonly used to solve concurrent problems in \CFA.
     27The @mutex@ statement sees use across almost all concurrent code in \CFA, as it is the simplest mechanism for providing thread-safe input and output.
     28The channels and the @waituntil@ statement see use in programs where a thread operates as a server or administrator, which accepts and distributes work among channels based on some shared state.
     29When implemented, the polymorphic support of the @waituntil@ statement will see use with the actor system to enable user threads outside the actor system to wait for work to be done or for actors to finish.
     30Finally, the new features are often combined, \eg channels pass pointers to shared memory that may still need mutual exclusion, requiring the @mutex@ statement to be used.
    3131
    3232From the novel copy-queue data structure in the actor system and the plethora of user-supporting safety features, all these utilities build upon existing concurrent tooling with value added.
    3333Performance results verify that each new feature is comparable or better than similar features in other programming languages.
    34 All in all, this suite of concurrent tools expands users' ability to easily write safe and performant multi-threaded programs in \CFA.
     34All in all, this suite of concurrent tools expands a \CFA programmer's ability to easily write safe and performant multi-threaded programs.
    3535
    3636\section{Future Work}
    … …  
    4040This thesis only scratches the surface of implicit concurrency by providing an actor system.
    4141There is room for more implicit concurrency tools in \CFA.
    42 User-defined implicit concurrency in the form of annotated loops or recursive concurrent functions exists in many other languages and libraries~\cite{uC++,OpenMP}.
     42User-defined implicit concurrency in the form of annotated loops or recursive concurrent functions exists in other languages and libraries~\cite{uC++,OpenMP}.
    4343Similar implicit concurrency mechanisms could be implemented and expanded on in \CFA.
    4444Additionally, the problem of automatic parallelism of sequential programs via the compiler is an interesting research space that other languages have approached~\cite{wilson94,haskell:parallel} and could be explored in \CFA.
    … …  
    4646\subsection{Advanced Actor Stealing Heuristics}
    4747
    48 In this thesis, two basic victim-selection heuristics are chosen when implementing the work stealing actor system.
    49 Good victim selection is an active area of work stealing research, especially when taking into account NUMA effects and cache locality~\cite{barghi18,wolke17}.
     48In this thesis, two basic victim-selection heuristics are chosen when implementing the work-stealing actor-system.
     49Good victim selection is an active area of work-stealing research, especially when taking into account NUMA effects and cache locality~\cite{barghi18,wolke17}.
    5050The actor system in \CFA is modular and exploration of other victim-selection heuristics for queue stealing in \CFA could be provided by pluggable modules.
    5151Another question in work stealing is: when should a worker thread steal?
    52 Work stealing systems can often be too aggressive when stealing, causing the cost of the steal to be have a negative rather positive effect on performance.
     52Work-stealing systems can often be too aggressive when stealing, causing the cost of the steal to be have a negative rather positive effect on performance.
    5353Given that thief threads often have cycles to spare, there is room for a more nuanced approaches when stealing.
    5454Finally, there is the very difficult problem of blocking and unblocking idle threads for workloads with extreme oscillations in CPU needs.
    … …  
    5656\subsection{Synchronously Multiplexing System Calls}
    5757
    58 There are many tools that try to synchronously wait for or asynchronously check I/O, since improvements in this area pay dividends in many areas of computer science~\cite{linux:select,linux:poll,linux:epoll,linux:iouring}.
     58There are many tools that try to synchronously wait for or asynchronously check I/O.
     59Improvements in this area pay dividends in many areas of I/O based programming~\cite{linux:select,linux:poll,linux:epoll,linux:iouring}.
    5960Research on improving user-space tools to synchronize over I/O and other system calls is an interesting area to explore in the world of concurrent tooling.
    6061Specifically, incorporating I/O into the @waituntil@ to allow a network server to work with multiple kinds of asynchronous I/O interconnects without using tradition event loops.
    … …  
    6970The semantics and safety of these builtins require careful navigation since they require the user to have a deep understanding of concurrent memory-ordering models.
    7071Furthermore, these atomics also often require a user to understand how to fence appropriately to ensure correctness.
    71 All these problems and more could benefit from language support in \CFA.
     72All these problems and more would benefit from language support in \CFA.
    7273Adding good language support for atomics is a difficult problem, which if solved well, would allow for easier and safer writing of low-level concurrent code.
    7374

  • doc/theses/colby_parsons_MMAth/text/intro.tex

    rc1e66d9 rdeda7e6  
    55% ======================================================================
    66
    7 Concurrent programs are the wild west of programming because determinism and simple ordering of program operations go out the window. 
    8 To seize the reins and write performant and safe concurrent code, high-level concurrent-language features are needed. 
    9 Like any other craftsmen, programmers are only as good as their tools, and concurrent tooling and features are no exception. 
     7Concurrent programs are the wild west of programming because determinism and simple ordering of program operations go out the window.
     8To seize the reins and write performant and safe concurrent code, high-level concurrent-language features are needed.
     9Like any other craftsmen, programmers are only as good as their tools, and concurrent tooling and features are no exception.
    1010
    11 This thesis presents a suite of high-level concurrent-language features implemented in the new programming-language \CFA.
    12 These features aim to improve the performance of concurrent programs, aid in writing safe programs, and assist user productivity by improving the ease of concurrent programming.
    13 The groundwork for concurrent features in \CFA was implemented by Thierry Delisle~\cite{Delisle18}, who contributed the threading system, coroutines, monitors and other tools.
    14 This thesis builds on top of that foundation by providing a suite of high-level concurrent features.
    15 The features include a @mutex@ statement, channels, a @waituntil@ statement, and an actor system.
    16 All of these features exist in other programming languages in some shape or form, however this thesis extends the original ideas by improving performance, productivity, and safety.
     11This thesis presents a suite of high-level concurrent-language features implemented in the new programming-language \CFA.
     12These features aim to improve the performance of concurrent programs, aid in writing safe programs, and assist user productivity by improving the ease of concurrent programming.
     13The groundwork for concurrent features in \CFA was designed and implemented by Thierry Delisle~\cite{Delisle18}, who contributed the threading system, coroutines, monitors and other basic concurrency tools.
     14This thesis builds on top of that foundation by providing a suite of high-level concurrent features.
     15The features include a @mutex@ statement, channels, a @waituntil@ statement, and an actor system.
     16All of these features exist in other programming languages in some shape or form;
     17however, this thesis extends the original ideas by improving performance, productivity, and safety.
    1718
    1819\section{The Need For Concurrent Features}
    19 Asking a programmer to write a complex concurrent program without any concurrent language features is asking them to undertake a very difficult task.
    20 They would only be able to rely on the atomicity that their hardware provides and would have to build up from there.
    21 This would be like asking a programmer to write a complex sequential program only in assembly.
    22 Both are doable, but would often be easier and less error prone with higher level tooling.
    2320
    24 Concurrent programming has many pitfalls that are unique and do not show up in sequential code:
     21% Asking a programmer to write a complex concurrent program without any concurrent language features is asking them to undertake a very difficult task.
     22% They would only be able to rely on the atomicity that their hardware provides and would have to build up from there.
     23% This would be like asking a programmer to write a complex sequential program only in assembly.
     24% Both are doable, but would often be easier and less error prone with higher level tooling.
     25
     26Concurrent programming has many unique pitfalls that do not appear in sequential programming:
    2527\begin{enumerate}
    26 \item Deadlock, where threads cyclically wait on resources, blocking them indefinitely.
     28\item Race conditions, where thread orderings can result in arbitrary behaviours, resulting in correctness problems.
    2729\item Livelock, where threads constantly attempt a concurrent operation unsuccessfully, resulting in no progress being made.
    28 \item Race conditions, where thread orderings can result in differing behaviours and correctness of a program execution.
    29 \item Starvation, where threads may be deprived of access to some shared resource due to unfairness and never make progress.
     30\item Starvation, where \emph{some} threads constantly attempt a concurrent operation unsuccessfully, resulting in partial progress being made.
     31\item Deadlock, where some threads wait for an event that cannot occur, blocking them indefinitely, resulting in no progress being made.
    3032\end{enumerate}
    31 Even with the guiding hand of concurrent tools these pitfalls can still catch unwary programmers, but good language support can prevent, detect, and mitigate these problems.
     33Even with the guiding hand of concurrent tools these pitfalls still catch unwary programmers, but good language support helps significantly to prevent, detect, and mitigate these problems.
    3234
    33 \section{A Brief Overview}
     35\section{Thesis Overview}
    3436
    35 The first chapter of this thesis aims to familiarize the reader with the language \CFA.
    36 In this chapter, syntax and features of the \CFA language that appear in this work are discussed The next chapter briefly discusses prior concurrency work in \CFA and how this work builds on top of existing features.
    37 The remaining chapters each introduce a concurrent language feature, discuss prior related work, and present contributions which are then benchmarked against other languages and systems.
    38 The first of these chapters discusses the @mutex@ statement, a language feature that improves ease of use and safety of lock usage.
    39 The @mutex@ statement is compared both in terms of safety and performance with similar tools in \CC and Java.
    40 The following chapter discusses channels, a message passing concurrency primitive that provides an avenue for safe synchronous and asynchronous communication across threads.
    41 Channels in \CFA are compared to Go, which popularized the use of channels in modern concurrent programs.
    42 The following chapter discusses the \CFA actor system.
    43 The \CFA actor system is a close cousin of channels, as it also belongs to the message passing paradigm of concurrency.
    44 However, the actor system provides a great degree of abstraction and ease of scalability, making it useful for a different range of problems than channels.
    45 The actor system in \CFA is compared with a variety of other systems on a suite of benchmarks, where it achieves significant performance gains over other systems due to its design.
    46 The final chapter discusses the \CFA @waituntil@ statement which provides the ability to synchronize while waiting for a resource, such as acquiring a lock, accessing a future, or writing to a channel.
    47 The @waituntil@ statement presented provides greater flexibility and expressibility than similar features in other languages.
    48 All in all, the features presented aim to fill in gaps in the current \CFA concurrent language support, and enable users to write a wider range of complex concurrent programs with ease.
     37Chapter~\ref{s:cfa} of this thesis aims to familiarize the reader with the language \CFA.
     38In this chapter, syntax and features of the \CFA language that appear in this work are discussed.
     39Chapter~\ref{s:cfa_concurrency} briefly discusses prior concurrency work in \CFA, and how the work in this thesis builds on top of the existing framework.
     40Each remaining chapter introduces an additional \CFA concurrent-language feature, which includes discussing prior related work for the feature, extensions over prior features, and uses benchmarks to compare the performance the feature with corresponding or similar features in other languages and systems.
     41
     42Chapter~\ref{s:mutexstmt} discusses the @mutex@ statement, a language feature that provides safe and simple lock usage.
     43The @mutex@ statement is compared both in terms of safety and performance with similar mechanisms in \CC and Java.
     44Chapter~\ref{s:channels} discusses channels, a message passing concurrency primitive that provides for safe synchronous and asynchronous communication among threads.
     45Channels in \CFA are compared to Go's channels, which popularized the use of channels in modern concurrent programs.
     46Chapter~\ref{s:actors} discusses the \CFA actor system.
     47An actor system is a close cousin of channels, as it also belongs to the message passing paradigm of concurrency.
     48However, an actor system provides a greater degree of abstraction and ease of scalability, making it useful for a different range of problems than channels.
     49The actor system in \CFA is compared with a variety of other systems on a suite of benchmarks.
     50Chapter~\ref{s:waituntil} discusses the \CFA @waituntil@ statement, which provides the ability to synchronize while waiting for a resource, such as acquiring a lock, accessing a future, or writing to a channel.
     51The \CFA @waituntil@ statement provides greater flexibility and expressibility than similar features in other languages.
     52All in all, the features presented aim to fill in gaps in the current \CFA concurrent-language support, enabling users to write a wider range of complex concurrent programs with ease.
    4953
    5054\section{Contributions}
    51 This work presents the following contributions:
    52 \begin{enumerate}
    53 \item The @mutex@ statement which:
    54 \begin{itemize}[itemsep=0pt]
    55 \item
    56 provides deadlock-free multiple lock acquisition,
    57 \item
    58 clearly denotes lock acquisition and release,
    59 \item
    60 and has good performance irrespective of lock ordering.
    61 \end{itemize}
    62 \item Channels which:
     55This work presents the following contributions within each of the additional language features:
     56\begin{enumerate}[leftmargin=*]
     57\item The @mutex@ statement that:
     58    \begin{itemize}[itemsep=0pt]
     59    \item
     60    provides deadlock-free multiple lock acquisition,
     61    \item
     62    clearly denotes lock acquisition and release,
     63    \item
     64    and has good performance irrespective of lock ordering.
     65    \end{itemize}
     66\item The channel that:
    6367\begin{itemize}[itemsep=0pt]
    6468    \item
    … …  
    7175    and provides toggle-able statistics for performance tuning.
    7276\end{itemize}
    73 \item An in-memory actor system that:
     77\item The in-memory actor system that:
    7478\begin{itemize}[itemsep=0pt]
    7579    \item
    … …  
    8286    gains performance through static-typed message sends, eliminating the need for dynamic dispatch,
    8387    \item
    84     introduces the copy queue, an array based queue specialized for the actor use case to minimize calls to the memory allocator,
     88    introduces the copy queue, an array-based queue specialized for the actor use-case to minimize calls to the memory allocator,
    8589    \item
    8690    has robust detection of six tricky, but common actor programming errors,
    … …  
    9094    and provides toggle-able statistics for performance tuning.
    9195\end{itemize}
    92 
    93 \item A @waituntil@ statement which:
     96\item The @waituntil@ statement that:
    9497\begin{itemize}[itemsep=0pt]
    9598    \item
    9699    is the only known polymorphic synchronous multiplexing language feature,
    97100    \item
    98     provides greater expressibility of waiting conditions than other languages,
     101    provides greater expressibility for waiting conditions than other languages,
    99102    \item
    100     and achieves comparable performance to similar features in two other languages,
     103    and achieves comparable performance to similar features in two other languages.
    101104\end{itemize}
    102105\end{enumerate}

  • doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex

    rc1e66d9 rdeda7e6  
    8383\end{figure}
    8484
    85 Like Java, \CFA monitors have \Newterm{multi-acquire} semantics so the thread in the monitor may acquire it multiple times without deadlock, allowing recursion and calling of other MX functions.
     85Like Java, \CFA monitors have \Newterm{multi-acquire} (reentrant locking) semantics so the thread in the monitor may acquire it multiple times without deadlock, allowing recursion and calling of other MX functions.
    8686For robustness, \CFA monitors ensure the monitor lock is released regardless of how an acquiring function ends, normal or exceptional, and returning a shared variable is safe via copying before the lock is released.
    8787Monitor objects can be passed through multiple helper functions without acquiring mutual exclusion, until a designated function associated with the object is called.
    … …  
    104104}
    105105\end{cfa}
    106 The \CFA monitor implementation ensures multi-lock acquisition is done in a deadlock-free manner regardless of the number of MX parameters and monitor arguments. It it important to note that \CFA monitors do not attempt to solve the nested monitor problem~\cite{Lister77}.
     106The \CFA monitor implementation ensures multi-lock acquisition is done in a deadlock-free manner regardless of the number of MX parameters and monitor arguments via resource ordering.
     107It it important to note that \CFA monitors do not attempt to solve the nested monitor problem~\cite{Lister77}.
    107108
    108109\section{\lstinline{mutex} statement}
    … …  
    165166In detail, the mutex statement has a clause and statement block, similar to a conditional or loop statement.
    166167The clause accepts any number of lockable objects (like a \CFA MX function prototype), and locks them for the duration of the statement.
    167 The locks are acquired in a deadlock free manner and released regardless of how control-flow exits the statement.
     168The locks are acquired in a deadlock-free manner and released regardless of how control-flow exits the statement.
     169Note that this deadlock-freedom has some limitations \see{\VRef{s:DeadlockAvoidance}}.
    168170The mutex statement provides easy lock usage in the common case of lexically wrapping a CS.
    169171Examples of \CFA mutex statement are shown in \VRef[Listing]{l:cfa_mutex_ex}.
    … …  
    210212Like Java, \CFA introduces a new statement rather than building from existing language features, although \CFA has sufficient language features to mimic \CC RAII locking.
    211213This syntactic choice makes MX explicit rather than implicit via object declarations.
    212 Hence, it is easier for programmers and language tools to identify MX points in a program, \eg scan for all @mutex@ parameters and statements in a body of code.
     214Hence, it is easy for programmers and language tools to identify MX points in a program, \eg scan for all @mutex@ parameters and statements in a body of code; similar scanning can be done with Java's @synchronized@.
    213215Furthermore, concurrent safety is provided across an entire program for the complex operation of acquiring multiple locks in a deadlock-free manner.
    214216Unlike Java, \CFA's mutex statement and \CC's @scoped_lock@ both use parametric polymorphism to allow user defined types to work with this feature.
    … …  
    231233thread$\(_2\)$ : sout | "uvw" | "xyz";
    232234\end{cfa}
    233 any of the outputs can appear, included a segment fault due to I/O buffer corruption:
     235any of the outputs can appear:
    234236\begin{cquote}
    235237\small\tt
    … …  
    260262mutex( sout ) { // acquire stream lock for sout for block duration
    261263        sout | "abc";
    262         mutex( sout ) sout | "uvw" | "xyz"; // OK because sout lock is recursive
     264        sout | "uvw" | "xyz";
    263265        sout | "def";
    264266} // implicitly release sout lock
    265267\end{cfa}
    266 The inner lock acquire is likely to occur through a function call that does a thread-safe print.
    267268
    268269\section{Deadlock Avoidance}\label{s:DeadlockAvoidance}
    … …  
    309310For fewer than 7 locks ($2^3-1$), the sort is unrolled performing the minimum number of compare and swaps for the given number of locks;
    310311for 7 or more locks, insertion sort is used.
    311 Since it is extremely rare to hold more than 6 locks at a time, the algorithm is fast and executes in $O(1)$ time.
    312 Furthermore, lock addresses are unique across program execution, even for dynamically allocated locks, so the algorithm is safe across the entire program execution.
     312It is assumed to be rare to hold more than 6 locks at a time.
     313For 6 or fewer locks the algorithm is fast and executes in $O(1)$ time.
     314Furthermore, lock addresses are unique across program execution, even for dynamically allocated locks, so the algorithm is safe across the entire program execution, as long as lifetimes of objects are appropriately managed.
     315For example, deleting a lock and allocating another one could give the new lock the same address as the deleted one, however deleting a lock in use by another thread is a programming error irrespective of the usage of the @mutex@ statement.
    313316
    314317The downside to the sorting approach is that it is not fully compatible with manual usages of the same locks outside the @mutex@ statement, \ie the lock are acquired without using the @mutex@ statement.
    … …  
    338341\end{cquote}
    339342Comparatively, if the @scoped_lock@ is used and the same locks are acquired elsewhere, there is no concern of the @scoped_lock@ deadlocking, due to its avoidance scheme, but it may livelock.
    340 The convenience and safety of the @mutex@ statement, \ie guaranteed lock release with exceptions, should encourage programmers to always use it for locking, mitigating any deadlock scenario versus combining manual locking with the mutex statement.
     343The convenience and safety of the @mutex@ statement, \ie guaranteed lock release with exceptions, should encourage programmers to always use it for locking, mitigating most deadlock scenarios versus combining manual locking with the mutex statement.
    341344Both \CC and the \CFA do not provide any deadlock guarantees for nested @scoped_lock@s or @mutex@ statements.
    342345To do so would require solving the nested monitor problem~\cite{Lister77}, which currently does not have any practical solutions.
    … …  
    344347\section{Performance}
    345348Given the two multi-acquisition algorithms in \CC and \CFA, each with differing advantages and disadvantages, it interesting to compare their performance.
    346 Comparison with Java is not possible, since it only takes a single lock.
     349Comparison with Java was not conducted, since the synchronized statement only takes a single object and does not provide deadlock avoidance or prevention.
    347350
    348351The comparison starts with a baseline that acquires the locks directly without a mutex statement or @scoped_lock@ in a fixed ordering and then releases them.
    … …  
    356359Each variation is run 11 times on 2, 4, 8, 16, 24, 32 cores and with 2, 4, and 8 locks being acquired.
    357360The median is calculated and is plotted alongside the 95\% confidence intervals for each point.
     361The confidence intervals are calculated using bootstrapping to avoid normality assumptions.
    358362
    359363\begin{figure}
    … …  
    388392}
    389393\end{cfa}
    390 \caption{Deadlock avoidance benchmark pseudocode}
     394\caption{Deadlock avoidance benchmark \CFA pseudocode}
    391395\label{l:deadlock_avoid_pseudo}
    392396\end{figure}
    … …  
    396400% sudo dmidecode -t system
    397401\item
    398 Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units) 2.0 GHz, TSO memory model, running Linux v5.8.0--55--generic, gcc--10 compiler
     402Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units), TSO memory model, running Linux v5.8.0--55--generic, gcc--10 compiler
    399403\item
    400 Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets (48 processing units) 2.2GHz, TSO memory model, running Linux v5.8.0--59--generic, gcc--10 compiler
     404Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets (96 processing units), TSO memory model, running Linux v5.8.0--59--generic, gcc--10 compiler
    401405\end{list}
    402406%The hardware architectures are different in threading (multithreading vs hyper), cache structure (MESI or MESIF), NUMA layout (QPI vs HyperTransport), memory model (TSO vs WO), and energy/thermal mechanisms (turbo-boost).
    … …  
    411415For example, on the AMD machine with 32 threads and 8 locks, the benchmarks would occasionally livelock indefinitely, with no threads making any progress for 3 hours before the experiment was terminated manually.
    412416It is likely that shorter bouts of livelock occurred in many of the experiments, which would explain large confidence intervals for some of the data points in the \CC data.
    413 In Figures~\ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel} there is the counter-intuitive result of the mutex statement performing better than the baseline.
     417In Figures~\ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel} there is the counter-intuitive result of the @mutex@ statement performing better than the baseline.
    414418At 7 locks and above the mutex statement switches from a hard coded sort to insertion sort, which should decrease performance.
    415419The hard coded sort is branch-free and constant-time and was verified to be faster than insertion sort for 6 or fewer locks.
    416 It is likely the increase in throughput compared to baseline is due to the delay spent in the insertion sort, which decreases contention on the locks.
    417 
     420Part of the difference in throughput compared to baseline is due to the delay spent in the insertion sort, which decreases contention on the locks.
     421This was verified to be part of the difference in throughput by experimenting with varying NCS delays in the baseline; however it only comprises a small portion of difference.
     422It is possible that the baseline is slowed down or the @mutex@ is sped up by other factors that are not easily identifiable.
    418423
    419424\begin{figure}

  • doc/theses/colby_parsons_MMAth/text/waituntil.tex

    rc1e66d9 rdeda7e6  
    168168Go's @select@ has the same exclusive-or semantics as the ALT primitive from Occam and associated code blocks for each clause like ALT and Ada.
    169169However, unlike Ada and ALT, Go does not provide guards for the \lstinline[language=go]{case} clauses of the \lstinline[language=go]{select}.
    170 As such, the exponential blowup can be seen comparing Go and \uC in Figure~\label{f:AdaMultiplexing}.
     170As such, the exponential blowup can be seen comparing Go and \uC in Figure~\ref{f:AdaMultiplexing}.
    171171Go also provides a timeout via a channel and a @default@ clause like Ada @else@ for asynchronous multiplexing.
    172172
    … …  
    519519In following example, either channel @C1@ or @C2@ must be satisfied but nothing can be done for at least 1 or 3 seconds after the channel read, respectively.
    520520\begin{cfa}[deletekeywords={timeout}]
    521 waituntil( i << C1 ); and waituntil( timeout( 1`s ) );
    522 or waituntil( i << C2 ); and waituntil( timeout( 3`s ) );
     521waituntil( i << C1 ){} and waituntil( timeout( 1`s ) ){}
     522or waituntil( i << C2 ){} and waituntil( timeout( 3`s ) ){}
    523523\end{cfa}
    524524If only @C2@ is satisfied, \emph{both} timeout code-blocks trigger because 1 second occurs before 3 seconds.
    … …  
    542542Now the unblocked WUT is guaranteed to have a satisfied resource and its code block can safely executed.
    543543The insertion circumvents the channel buffer via the wait-morphing in the \CFA channel implementation \see{Section~\ref{s:chan_impl}}, allowing @waituntil@ channel unblocking to not be special-cased.
     544Note that all channel operations are fair and no preference is given between @waituntil@ and direct channel operations when unblocking.
    544545
    545546Furthermore, if both @and@ and @or@ operators are used, the @or@ operations stop behaving like exclusive-or due to the race among channel operations, \eg:
Note: See TracChangeset for help on using the changeset viewer.