Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/concurrency/Paper.tex

    rfe3cd36 r287da46  
    33\articletype{RESEARCH ARTICLE}%
    44
    5 \received{XXXXX}
    6 \revised{XXXXX}
    7 \accepted{XXXXX}
     5\received{26 April 2016}
     6\revised{6 June 2016}
     7\accepted{6 June 2016}
    88
    99\raggedbottom
    … …  
    3232\renewcommand{\linenumberfont}{\scriptsize\sffamily}
    3333
    34 \renewcommand{\topfraction}{0.8}                        % float must be greater than X of the page before it is forced onto its own page
    35 \renewcommand{\bottomfraction}{0.8}                     % float must be greater than X of the page before it is forced onto its own page
    36 \renewcommand{\floatpagefraction}{0.8}          % float must be greater than X of the page before it is forced onto its own page
    3734\renewcommand{\textfraction}{0.0}                       % the entire page maybe devoted to floats with no text on the page at all
    3835
    … …  
    135132\makeatother
    136133
    137 \newenvironment{cquote}
    138                {\list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=3pt\parsep=0pt\leftmargin=\parindentlnth\rightmargin\leftmargin}%
    139                 \item\relax}
    140                {\endlist}
    141 
    142 %\newenvironment{cquote}{%
    143 %\list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=3pt\parsep=0pt\leftmargin=\parindentlnth\rightmargin\leftmargin}%
    144 %\item\relax%
    145 %}{%
    146 %\endlist%
    147 %}% cquote
     134\newenvironment{cquote}{%
     135        \list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=3pt\parsep=0pt\leftmargin=\parindentlnth\rightmargin\leftmargin}%
     136        \item\relax
     137}{%
     138        \endlist
     139}% cquote
    148140
    149141% CFA programming language, based on ANSI C (with some gcc additions)
    … …  
    242234\abstract[Summary]{
    243235\CFA is a modern, polymorphic, \emph{non-object-oriented} extension of the C programming language.
    244 This paper discusses the design of the concurrency and parallelism features in \CFA, and its concurrent runtime-system.
     236This paper discusses the design of the concurrency and parallelism features in \CFA, and the concurrent runtime-system.
    245237These features are created from scratch as ISO C lacks concurrency, relying largely on the pthreads library for concurrency.
    246 Coroutines and lightweight (user) threads are introduced into \CFA;
    247 as well, monitors are added as a high-level mechanism for mutual exclusion and synchronization.
    248 A unique contribution of this work is allowing multiple monitors to be safely acquired \emph{simultaneously}.
     238Coroutines and lightweight (user) threads are introduced into the language.
     239In addition, monitors are added as a high-level mechanism for mutual exclusion and synchronization.
     240A unique contribution is allowing multiple monitors to be safely acquired simultaneously.
    249241All features respect the expectations of C programmers, while being fully integrate with the \CFA polymorphic type-system and other language features.
    250 Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming-languages.
     242Finally, experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming-languages.
    251243}%
    252244
    … …  
    279271Concurrency tools handle mutual exclusion and synchronization, while parallelism tools handle performance, cost, and resource utilization.
    280272
    281 The proposed concurrency API is implemented in a dialect of C, called \CFA (pronounced C-for-all).
     273The proposed concurrency API is implemented in a dialect of C, called \CFA.
    282274The paper discusses how the language features are added to the \CFA translator with respect to parsing, semantics, and type checking, and the corresponding high-performance runtime-library to implement the concurrent features.
    283275
    … …  
    289281
    290282\CFA is a non-object-oriented extension of ISO-C, and hence, supports all C paradigms.
     283%It is a non-object-oriented system-language, meaning most of the major abstractions have either no runtime overhead or can be opted out easily.
    291284Like C, the building blocks of \CFA are structures and routines.
    292285Virtually all of the code generated by the \CFA translator respects C memory layouts and calling conventions.
    293 While \CFA is not object oriented, lacking the concept of a receiver (\eg @this@) and nominal inheritance-relationships, C has a notion of objects: ``region of data storage in the execution environment, the contents of which can represent values''~\cite[3.15]{C11}.
    294 While some object-oriented features appear in \CFA, they are independent capabilities, allowing \CFA to adopt them while maintaining a procedural paradigm.
     286While \CFA is not object oriented, lacking the concept of a receiver (\eg @this@) and nominal inheritance-relationships, C does have a notion of objects: ``region of data storage in the execution environment, the contents of which can represent values''~\cite[3.15]{C11}.
     287While some \CFA features are common in object-oriented programming, they are independent capabilities allowing \CFA to adopt them while maintaining a procedural paradigm.
    295288
    296289
    … …  
    345338Object-oriented programming languages only provide implicit qualification for the receiver.
    346339
    347 In detail, the @with@-statement syntax is:
     340In detail, the @with@ statement has the form:
    348341\begin{cfa}
    349342$\emph{with-statement}$:
    … …  
    355348(Enumerations are already opened.)
    356349The object is the implicit qualifier for the open structure-fields.
    357 All expressions in the expression list are opened in parallel within the compound statement, which is different from Pascal, which nests the openings from left to right.
     350All expressions in the expression list are open in parallel within the compound statement, which is different from Pascal, which nests the openings from left to right.
    358351
    359352
    … …  
    361354
    362355\CFA maximizes the ability to reuse names via overloading to aggressively address the naming problem.
    363 Both variables and routines may be overloaded, where selection is based on number and types of returns and arguments (as in Ada~\cite{Ada}).
    364 \newpage
    365 \vspace*{-2\baselineskip}%???
     356Both variables and routines may be overloaded, where selection is based on types, and number of returns (as in Ada~\cite{Ada}) and arguments.
    366357\begin{cquote}
     358\vspace*{-\baselineskip}%???
     359\lstDeleteShortInline@%
    367360\begin{cfa}
    368361// selection based on type
    369362\end{cfa}
    370 \lstDeleteShortInline@%
    371363\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}|@{\hspace{2\parindentlnth}}l@{}}
    372364\begin{cfa}
    … …  
    419411Therefore, overloading eliminates long prefixes and other naming conventions to prevent name clashes.
    420412As seen in Section~\ref{s:Concurrency}, routine @main@ is heavily overloaded.
    421 As another example, variable overloading is useful in the parallel semantics of the @with@ statement for fields with the same name:
     413For example, variable overloading is useful in the parallel semantics of the @with@ statement for fields with the same name:
    422414\begin{cfa}
    423415struct S { int `i`; int j; double m; } s;
    … …  
    472464\lstMakeShortInline@%
    473465\end{cquote}
     466While concurrency does not use operator overloading directly, it provides an introduction for the syntax of constructors.
    474467
    475468
    … …  
    477470
    478471Object lifetime is a challenge in non-managed programming languages.
    479 \CFA responds with \CC-like constructors and destructors, using a different operator-overloading syntax.
     472\CFA responds with \CC-like constructors and destructors:
    480473\begin{cfa}
    481474struct VLA { int len, * data; };                        $\C{// variable length array of integers}$
    … …  
    497490Like \CC, construction is implicit on allocation (stack/heap) and destruction is implicit on deallocation.
    498491The object and all their fields are constructed/destructed.
    499 \CFA also provides @new@ and @delete@ as library routines, which behave like @malloc@ and @free@, in addition to constructing and destructing objects:
     492\CFA also provides @new@ and @delete@, which behave like @malloc@ and @free@, in addition to constructing and destructing objects:
    500493\begin{cfa}
    501494{
    … …  
    525518int i = sum( sa, 5 );                                           $\C{// use S's 0 construction and +}$
    526519\end{cfa}
    527 Type variables can be @otype@ or @dtype@.
    528 @otype@ refers to a \emph{complete type}, \ie, a type with size, alignment, default constructor, copy constructor, destructor, and assignment operator.
    529 @dtype@ refers to an \emph{incomplete type}, \eg, void or a forward-declared type.
    530 The builtin types @zero_t@ and @one_t@ overload constant 0 and 1 for a new types, where both 0 and 1 have special meaning in C.
     520The builtin type @zero_t@ (and @one_t@) overload constant 0 (and 1) for a new types, where both 0 and 1 have special meaning in C.
    531521
    532522\CFA provides \newterm{traits} to name a group of type assertions, where the trait name allows specifying the same set of assertions in multiple locations, preventing repetition mistakes at each routine declaration:
    … …  
    543533\end{cfa}
    544534
     535Assertions can be @otype@ or @dtype@.
     536@otype@ refers to a \emph{complete} object, \ie an object has a size, alignment, default constructor, copy constructor, destructor and an assignment operator.
     537@dtype@ refers to an \emph{incomplete} object, \ie, an object only has a size and alignment.
     538
    545539Using the return type for overload discrimination, it is possible to write a type-safe @alloc@ based on the C @malloc@:
    546540\begin{cfa}
    … …  
    560554In coroutining, the single thread is self-scheduling across the stacks, so execution is deterministic, \ie the execution path from input to output is fixed and predictable.
    561555A \newterm{stackless} coroutine executes on the caller's stack~\cite{Python} but this approach is restrictive, \eg preventing modularization and supporting only iterator/generator-style programming;
    562 a \newterm{stackful} coroutine executes on its own stack, allowing full generality.
    563 Only stackful coroutines are a stepping stone to concurrency.
     556a \newterm{stackfull} coroutine executes on its own stack, allowing full generality.
     557Only stackfull coroutines are a stepping stone to concurrency.
    564558
    565559The transition to concurrency, even for execution with a single thread and multiple stacks, occurs when coroutines also context switch to a \newterm{scheduling oracle}, introducing non-determinism from the coroutine perspective~\cite[\S~3]{Buhr05a}.
    … …  
    567561The resulting execution system now follows a cooperative threading-model, called \newterm{non-preemptive scheduling}.
    568562
    569 Because the scheduler is special, it can either be a stackless or stackful coroutine.
     563Because the scheduler is special, it can either be a stackless or stackfull coroutine.
    570564For stackless, the scheduler performs scheduling on the stack of the current coroutine and switches directly to the next coroutine, so there is one context switch.
    571 For stackful, the current coroutine switches to the scheduler, which performs scheduling, and it then switches to the next coroutine, so there are two context switches.
    572 A stackful scheduler is often used for simplicity and security.
     565For stackfull, the current coroutine switches to the scheduler, which performs scheduling, and it then switches to the next coroutine, so there are two context switches.
     566A stackfull scheduler is often used for simplicity and security, even through there is a slightly higher runtime-cost.
    573567
    574568Regardless of the approach used, a subset of concurrency related challenges start to appear.
    575569For the complete set of concurrency challenges to occur, the missing feature is \newterm{preemption}, where context switching occurs randomly between any two instructions, often based on a timer interrupt, called \newterm{preemptive scheduling}.
    576 While a scheduler introduces uncertainty in the order of execution, preemption introduces uncertainty about where context switches occur.
     570While a scheduler introduces uncertainty in the order of execution, preemption introduces uncertainty where context switches occur.
    577571Interestingly, uncertainty is necessary for the runtime (operating) system to give the illusion of parallelism on a single processor and increase performance on multiple processors.
    578572The reason is that only the runtime has complete knowledge about resources and how to best utilized them.
    … …  
    580574otherwise, it is impossible to write meaningful programs.
    581575Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows.
     576
     577
     578\subsection{\protect\CFA's Thread Building Blocks}
    582579
    583580An important missing feature in C is threading\footnote{While the C11 standard defines a \protect\lstinline@threads.h@ header, it is minimal and defined as optional.
    … …  
    593590
    594591While the focus of this discussion is concurrency and parallelism, it is important to address coroutines, which are a significant building block of a concurrency system (but not concurrent among themselves).
    595 Coroutines are generalized routines allowing execution to be temporarily suspended and later resumed.
     592Coroutines are generalized routines allowing execution to be temporarily suspend and later resumed.
    596593Hence, unlike a normal routine, a coroutine may not terminate when it returns to its caller, allowing it to be restarted with the values and execution location present at the point of suspension.
    597 This capability is accomplished via the coroutine's stack, where suspend/resume context switch among stacks.
     594This capability is accomplish via the coroutine's stack, where suspend/resume context switch among stacks.
    598595Because threading design-challenges are present in coroutines, their design effort is relevant, and this effort can be easily exposed to programmers giving them a useful new programming paradigm because a coroutine handles the class of problems that need to retain state between calls, \eg plugins, device drivers, and finite-state machines.
    599 Therefore, the two fundamental features of the core \CFA coroutine-API are independent call-stacks and @suspend@/@resume@ operations.
     596Therefore, the core \CFA coroutine-API for has two fundamental features: independent call-stacks and @suspend@/@resume@ operations.
    600597
    601598For example, a problem made easier with coroutines is unbounded generators, \eg generating an infinite sequence of Fibonacci numbers
    … …  
    725722Figure~\ref{f:Coroutine3States} creates a @coroutine@ type, @`coroutine` Fib { int fn; }@, which provides communication, @fn@, for the \newterm{coroutine main}, @main@, which runs on the coroutine stack, and possibly multiple interface routines, \eg @next@.
    726723Like the structure in Figure~\ref{f:ExternalState}, the coroutine type allows multiple instances, where instances of this type are passed to the (overloaded) coroutine main.
    727 The coroutine main's stack holds the state for the next generation, @f1@ and @f2@, and the code represents the three states in the Fibonacci formula via the three suspend points, to context switch back to the caller's @resume@.
     724The coroutine main's stack holds the state for the next generation, @f1@ and @f2@, and the code has the three suspend points, representing the three states in the Fibonacci formula, to context switch back to the caller's @resume@.
    728725The interface routine @next@, takes a Fibonacci instance and context switches to it using @resume@;
    729726on restart, the Fibonacci field, @fn@, contains the next value in the sequence, which is returned.
    … …  
    750747\end{quote}
    751748The example takes advantage of resuming a coroutine in the constructor to prime the loops so the first character sent for formatting appears inside the nested loops.
    752 The destructor provides a newline, if formatted text ends with a full line.
    753 Figure~\ref{f:CFmt} shows the C equivalent formatter, where the loops of the coroutine are flattened (linearized) and rechecked on each call because execution location is not retained between calls.
     749The destruction provides a newline, if formatted text ends with a full line.
     750Figure~\ref{f:CFmt} shows the C equivalent formatter, where the loops of the coroutine are flatten (linearized) and rechecked on each call because execution location is not retained between calls.
    754751(Linearized code is the bane of device drivers.)
    755752
    … …  
    764761};
    765762void main( Format & fmt ) with( fmt ) {
    766         for ( ;; ) {
     763        for ( ;; ) {   
    767764                for ( g = 0; g < 5; g += 1 ) {      // group
    768765                        for ( b = 0; b < 4; b += 1 ) { // block
    … …  
    838835The previous examples are \newterm{asymmetric (semi) coroutine}s because one coroutine always calls a resuming routine for another coroutine, and the resumed coroutine always suspends back to its last resumer, similar to call/return for normal routines.
    839836However, @resume@ and @suspend@ context switch among existing stack-frames, rather than create new ones so there is no stack growth.
    840 \newterm{Symmetric (full) coroutine}s have a coroutine call to a resuming routine for another coroutine, and its coroutine main calls another resuming routine, which eventually forms a resuming-call cycle.
     837\newterm{Symmetric (full) coroutine}s have a coroutine call to a resuming routine for another coroutine, and its coroutine main has a call to another resuming routine, which eventually forms a resuming-call cycle.
    841838(The trivial cycle is a coroutine resuming itself.)
    842839This control flow is similar to recursion for normal routines, but again there is no stack growth from the context switch.
    … …  
    929926The call from the consumer to @payment@ introduces the cycle between producer and consumer.
    930927When @payment@ is called, the consumer copies values into the producer's communication variable and a resume is executed.
    931 The context switch restarts the producer at the point where it last context switched, so it continues in @delivery@ after the resume.
     928The context switch restarts the producer at the point where it was last context switched, so it continues in @delivery@ after the resume.
    932929
    933930@delivery@ returns the status value in @prod@'s coroutine main, where the status is printed.
    … …  
    948945\subsection{Coroutine Implementation}
    949946
    950 A significant implementation challenge for coroutines (and threads, see Section~\ref{threads}) is adding extra fields and executing code after/before the coroutine constructor/destructor and coroutine main to create/initialize/de-initialize/destroy extra fields and the stack.
     947A significant implementation challenge for coroutines (and threads, see section \ref{threads}) is adding extra fields and executing code after/before the coroutine constructor/destructor and coroutine main to create/initialize/de-initialize/destroy extra fields and the stack.
    951948There are several solutions to this problem and the chosen option forced the \CFA coroutine design.
    952949
    … …  
    956953\end{cfa}
    957954and the programming language (and possibly its tool set, \eg debugger) may need to understand @baseCoroutine@ because of the stack.
    958 Furthermore, the execution of constructors/destructors is in the wrong order for certain operations.
     955Furthermore, the execution of constructs/destructors is in the wrong order for certain operations.
    959956For example, for threads if the thread is implicitly started, it must start \emph{after} all constructors, because the thread relies on a completely initialized object, but the inherited constructor runs \emph{before} the derived.
    960957
    961 An alternative is composition:
     958An alternatively is composition:
    962959\begin{cfa}
    963960struct mycoroutine {
    … …  
    10071004Users wanting to extend coroutines or build their own for various reasons can only do so in ways offered by the language.
    10081005Furthermore, implementing coroutines without language supports also displays the power of a programming language.
    1009 While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can still be constructed without language support.
    1010 The reserved keyword simply eases use for the common case.
    1011 
    1012 Part of the mechanism to generalize coroutines is using a \CFA trait, which defines a coroutine as anything satisfying the trait @is_coroutine@, and this trait restricts the available set of coroutine-manipulation routines:
     1006While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can still be constructed without using the language support.
     1007The reserved keyword simply eases use for the common cases.
     1008
     1009Part of the mechanism to generalize coroutines is using a \CFA trait, which defines a coroutine as anything satisfying the trait @is_coroutine@, and this trait is used to restrict coroutine-manipulation routines:
    10131010\begin{cfa}
    10141011trait is_coroutine( `dtype` T ) {
    … …  
    10191016forall( `dtype` T | is_coroutine(T) ) void resume( T & );
    10201017\end{cfa}
    1021 The @dtype@ property provides no implicit copying operations and the @is_coroutine@ trait provides no explicit copying operations, so all coroutines must be passed by reference (pointer).
     1018The @dtype@ property of the trait ensures the coroutine descriptor is non-copyable, so all coroutines must be passed by reference (pointer).
    10221019The routine definitions ensures there is a statically-typed @main@ routine that is the starting point (first stack frame) of a coroutine, and a mechanism to get (read) the currently executing coroutine handle.
    10231020The @main@ routine has no return value or additional parameters because the coroutine type allows an arbitrary number of interface routines with corresponding arbitrary typed input/output values versus fixed ones.
     1021The generic routines @suspend@ and @resume@ can be redefined, but any object passed to them is a coroutine since it must satisfy the @is_coroutine@ trait to compile.
    10241022The advantage of this approach is that users can easily create different types of coroutines, \eg changing the memory layout of a coroutine is trivial when implementing the @get_coroutine@ routine, and possibly redefining @suspend@ and @resume@.
    10251023The \CFA keyword @coroutine@ implicitly implements the getter and forward declarations required for implementing the coroutine main:
    … …  
    11521150\begin{cfa}
    11531151int main() {
    1154         MyThread * heapLive;
     1152        MyThread * heapLived;
    11551153        {
    1156                 MyThread blockLive;                                     $\C{// fork block-based thread}$
    1157                 heapLive = `new`( MyThread );           $\C{// fork heap-based thread}$
     1154                MyThread blockLived;                            $\C{// fork block-based thread}$
     1155                heapLived = `new`( MyThread );          $\C{// fork heap-based thread}$
    11581156                ...
    11591157        }                                                                               $\C{// join block-based thread}$
    11601158        ...
    1161         `delete`( heapLive );                                   $\C{// join heap-based thread}$
     1159        `delete`( heapLived );                                  $\C{// join heap-based thread}$
    11621160}
    11631161\end{cfa}
    11641162The heap-based approach allows arbitrary thread-creation topologies, with respect to fork/join-style concurrency.
    11651163
    1166 Figure~\ref{s:ConcurrentMatrixSummation} shows concurrently adding the rows of a matrix and then totalling the subtotals sequentially, after all the row threads have terminated.
     1164Figure~\ref{s:ConcurrentMatrixSummation} shows concurrently adding the rows of a matrix and then totalling the subtotals sequential, after all the row threads have terminated.
    11671165The program uses heap-based threads because each thread needs different constructor values.
    11681166(Python provides a simple iteration mechanism to initialize array elements to different values allowing stack allocation.)
    11691167The allocation/deallocation pattern appears unusual because allocated objects are immediately deallocated without any intervening code.
    11701168However, for threads, the deletion provides implicit synchronization, which is the intervening code.
    1171 While the subtotals are added in linear order rather than completion order, which slightly inhibits concurrency, the computation is restricted by the critical-path thread (\ie the thread that takes the longest), and so any inhibited concurrency is very small as totalling the subtotals is trivial.
     1169While the subtotals are added in linear order rather than completion order, which slight inhibits concurrency, the computation is restricted by the critical-path thread (\ie the thread that takes the longest), and so any inhibited concurrency is very small as totalling the subtotals is trivial.
    11721170
    11731171\begin{figure}
    11741172\begin{cfa}
    1175 `thread` Adder { int * row, cols, & subtotal; } $\C{// communication variables}$
     1173thread Adder {
     1174    int * row, cols, & subtotal;                        $\C{// communication}$
     1175};
    11761176void ?{}( Adder & adder, int row[], int cols, int & subtotal ) {
    11771177    adder.[ row, cols, &subtotal ] = [ row, cols, &subtotal ];
    … …  
    11871187    Adder * adders[rows];
    11881188    for ( int r = 0; r < rows; r += 1 ) {       $\C{// start threads to sum rows}$
    1189                 adders[r] = `new( matrix[r], cols, &subtotals[r] );`
     1189                adders[r] = new( matrix[r], cols, &subtotals[r] );
    11901190    }
    11911191    for ( int r = 0; r < rows; r += 1 ) {       $\C{// wait for threads to finish}$
    1192                 `delete( adders[r] );`                          $\C{// termination join}$
     1192                delete( adders[r] );                            $\C{// termination join}$
    11931193                total += subtotals[r];                          $\C{// total subtotal}$
    11941194    }
    … …  
    12061206To reestablish meaningful execution requires mechanisms to reintroduce determinism, \ie restrict non-determinism, called mutual exclusion and synchronization, where mutual exclusion is an access-control mechanism on data shared by threads, and synchronization is a timing relationship among threads~\cite[\S~4]{Buhr05a}.
    12071207Since many deterministic challenges appear with the use of mutable shared state, some languages/libraries disallow it, \eg Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka~\cite{Akka} (Scala).
    1208 In these paradigms, interaction among concurrent objects is performed by stateless message-passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms closely related to networking concepts, \eg channels~\cite{CSP,Go}.
     1208In these paradigms, interaction among concurrent objects is performed by stateless message-passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms closely relate to networking concepts, \eg channels~\cite{CSP,Go}.
    12091209However, in call/return-based languages, these approaches force a clear distinction, \ie introduce a new programming paradigm between regular and concurrent computation, \eg routine call versus message passing.
    12101210Hence, a programmer must learn and manipulate two sets of design patterns.
    12111211While this distinction can be hidden away in library code, effective use of the library still has to take both paradigms into account.
    1212 In contrast, approaches based on stateful models more closely resemble the standard call/return programming-model, resulting in a single programming paradigm.
     1212In contrast, approaches based on statefull models more closely resemble the standard call/return programming-model, resulting in a single programming paradigm.
    12131213
    12141214At the lowest level, concurrent control is implemented by atomic operations, upon which different kinds of locking mechanisms are constructed, \eg semaphores~\cite{Dijkstra68b}, barriers, and path expressions~\cite{Campbell74}.
    12151215However, for productivity it is always desirable to use the highest-level construct that provides the necessary efficiency~\cite{Hochstein05}.
    12161216A newer approach for restricting non-determinism is transactional memory~\cite{Herlihy93}.
    1217 While this approach is pursued in hardware~\cite{Nakaike15} and system languages, like \CC~\cite{Cpp-Transactions}, the performance and feature set is still too restrictive to be the main concurrency paradigm for system languages, which is why it is rejected as the core paradigm for concurrency in \CFA.
     1217While this approach is pursued in hardware~\cite{Nakaike15} and system languages, like \CC~\cite{Cpp-Transactions}, the performance and feature set is still too restrictive to be the main concurrency paradigm for system languages, which is why it was rejected as the core paradigm for concurrency in \CFA.
    12181218
    12191219One of the most natural, elegant, and efficient mechanisms for mutual exclusion and synchronization for shared-memory systems is the \emph{monitor}.
    … …  
    12441244higher-level mechanisms often simplify usage by adding better coupling between synchronization and data, \eg message passing, or offering a simpler solution to otherwise involved challenges, \eg barrier lock.
    12451245Often synchronization is used to order access to a critical section, \eg ensuring a reader thread is the next kind of thread to enter a critical section.
    1246 If a writer thread is scheduled for next access, but another reader thread acquires the critical section first, that reader \newterm{barged}.
     1246If a writer thread is scheduled for next access, but another reader thread acquires the critical section first, that reader has \newterm{barged}.
    12471247Barging can result in staleness/freshness problems, where a reader barges ahead of a writer and reads temporally stale data, or a writer barges ahead of another writer overwriting data with a fresh value preventing the previous value from ever being read (lost computation).
    12481248Preventing or detecting barging is an involved challenge with low-level locks, which can be made much easier by higher-level constructs.
    … …  
    12501250Algorithms that allow a barger, but divert it until later using current synchronization state (flags), are avoiding the barger;
    12511251algorithms that preclude a barger from entering during synchronization in the critical section prevent barging completely.
    1252 Techniques like baton-passing locks~\cite{Andrews89} between threads instead of unconditionally releasing locks is an example of barging prevention.
     1252Techniques like baton-pass locks~\cite{Andrews89} between threads instead of unconditionally releasing locks is an example of barging prevention.
    12531253
    12541254
    … …  
    12631263Copying a lock is insecure because it is possible to copy an open lock and then use the open copy when the original lock is closed to simultaneously access the shared data.
    12641264Copying a monitor is secure because both the lock and shared data are copies, but copying the shared data is meaningless because it no longer represents a unique entity.
    1265 As for coroutines/tasks, the @dtype@ property provides no implicit copying operations and the @is_monitor@ trait provides no explicit copying operations, so all locks/monitors must be passed by reference (pointer).
     1265As for coroutines/tasks, a non-copyable (@dtype@) trait is used to capture this requirement, so all locks/monitors must be passed by reference (pointer).
    12661266\begin{cfa}
    12671267trait is_monitor( `dtype` T ) {
    … …  
    12751275\label{s:MutexAcquisition}
    12761276
    1277 While correctness implies a monitor's mutual exclusion is acquired and released, there are implementation options about when and where the locking/unlocking occurs.
     1277While correctness implicitly implies a monitor's mutual exclusion is acquired and released, there are implementation options about when and where the locking/unlocking occurs.
    12781278(Much of this discussion also applies to basic locks.)
    12791279For example, a monitor may need to be passed through multiple helper routines before it becomes necessary to acquire the monitor mutual-exclusion.
    … …  
    13011301
    13021302For maximum usability, monitors have \newterm{multi-acquire} semantics allowing a thread to acquire it multiple times without deadlock.
    1303 \begin{cfa}
    1304 monitor M { ... } m;
    1305 void foo( M & mutex m ) { ... }                         $\C{// acquire mutual exclusion}$
    1306 void bar( M & mutex m ) {                                       $\C{// acquire mutual exclusion}$
    1307         ... `foo( m );` ...                                             $\C{// reacquire mutual exclusion}$
    1308 }
    1309 `bar( m );`                                                                     $\C{// nested monitor call}$
    1310 \end{cfa}
    1311 
    1312 The benefit of mandatory monitor qualifiers is self-documentation, but requiring both @mutex@ and \lstinline[morekeywords=nomutex]@nomutex@ for all monitor parameters is redundant.
    1313 Instead, the semantics have one qualifier as the default, and the other required.
    1314 For example, make the safe @mutex@ qualifier the default because assuming \lstinline[morekeywords=nomutex]@nomutex@ may cause subtle errors.
    1315 Alternatively, make the unsafe \lstinline[morekeywords=nomutex]@nomutex@ qualifier the default because it is the \emph{normal} parameter semantics while @mutex@ parameters are rare.
     1303For example, atomically printing the contents of a binary tree:
     1304\begin{cfa}
     1305monitor Tree {
     1306        Tree * left, right;
     1307        // value
     1308};
     1309void print( Tree & mutex tree ) {                       $\C{// prefix traversal}$
     1310        // write value
     1311        print( tree->left );                                    $\C{// multiply acquire monitor lock on each recursion}$
     1312        print( tree->right );
     1313}
     1314\end{cfa}
     1315
     1316Mandatory monitor qualifiers have the benefit of being self-documenting, but requiring both @mutex@ and \lstinline[morekeywords=nomutex]@nomutex@ for all monitor parameter is redundant.
     1317Instead, one of qualifier semantics can be the default, and the other required.
     1318For example, assume the safe @mutex@ qualifier for all monitor parameters because assuming \lstinline[morekeywords=nomutex]@nomutex@ may cause subtle errors.
     1319On the other hand, assuming \lstinline[morekeywords=nomutex]@nomutex@ is the \emph{normal} parameter behaviour, stating explicitly \emph{this parameter is not special}.
    13161320Providing a default qualifier implies knowing whether a parameter is a monitor.
    13171321Since \CFA relies heavily on traits as an abstraction mechanism, the distinction between a type that is a monitor and a type that looks like a monitor can become blurred.
    … …  
    13361340
    13371341To make the issue tractable, \CFA only acquires one monitor per parameter with at most one level of indirection.
    1338 However, there is an ambiguity in the C type-system with respects to arrays.
     1342However, the C type-system has an ambiguity with respects to arrays.
    13391343Is the argument for @f2@ a single object or an array of objects?
    13401344If it is an array, only the first element of the array is acquired, which seems unsafe;
    … …  
    13511355
    13521356For object-oriented monitors, calling a mutex member \emph{implicitly} acquires mutual exclusion of the receiver object, @`rec`.foo(...)@.
    1353 \CFA has no receiver, and hence, must use an explicit mechanism to specify which object acquires mutual exclusion.
     1357\CFA has no receiver, and hence, must use an explicit mechanism to specify which object has mutual exclusion acquired.
    13541358A positive consequence of this design decision is the ability to support multi-monitor routines.
    13551359\begin{cfa}
    … …  
    13621366Having language support for such a feature is therefore a significant asset for \CFA.
    13631367
    1364 The capability to acquire multiple locks before entering a critical section is called \newterm{bulk acquire} (see Section~\ref{s:Implementation} for implementation details).
     1368The capability to acquire multiple locks before entering a critical section is called \newterm{bulk acquire}.
    13651369In the previous example, \CFA guarantees the order of acquisition is consistent across calls to different routines using the same monitors as arguments.
    13661370This consistent ordering means acquiring multiple monitors is safe from deadlock.
    … …  
    13801384
    13811385However, such use leads to lock acquiring order problems resulting in deadlock~\cite{Lister77}, where detecting it requires dynamic tracking of monitor calls, and dealing with it requires rollback semantics~\cite{Dice10}.
    1382 In \CFA, a safety aid is provided by using bulk acquire of all monitors to shared objects, whereas other monitor systems provide no aid.
    1383 While \CFA provides only a partial solution, it handles many useful cases, \eg:
    1384 \begin{cfa}
    1385 monitor BankAccount { ... };
    1386 void deposit( BankAccount & `mutex` b, int deposit );
    1387 void transfer( BankAccount & `mutex` my, BankAccount & `mutex` your, int me2you ) {
    1388         deposit( my, `-`me2you );                               $\C{// debit}$
    1389         deposit( your, me2you );                                $\C{// credit}$
     1386In \CFA, safety is guaranteed by using bulk acquire of all monitors to shared objects, whereas other monitor systems provide no aid.
     1387While \CFA provides only a partial solution, the \CFA partial solution handles many useful cases.
     1388\begin{cfa}
     1389monitor Bank { ... };
     1390void deposit( Bank & `mutex` b, int deposit );
     1391void transfer( Bank & `mutex` mybank, Bank & `mutex` yourbank, int me2you) {
     1392        deposit( mybank, `-`me2you );                   $\C{// debit}$
     1393        deposit( yourbank, me2you );                    $\C{// credit}$
    13901394}
    13911395\end{cfa}
    … …  
    13941398
    13951399
    1396 \subsection{\protect\lstinline@mutex@ statement}
    1397 \label{mutex-stmt}
     1400\subsection{\protect\lstinline|mutex| statement} \label{mutex-stmt}
    13981401
    13991402The monitor call-semantics associate all locking semantics to routines.
    … …  
    14021405\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}}
    14031406\begin{cfa}
    1404 monitor M { ... };
     1407monitor M {};
    14051408void foo( M & mutex m1, M & mutex m2 ) {
    14061409        // critical section
    … …  
    14321435For example, Figure~\ref{f:GenericBoundedBuffer} shows a bounded buffer that may be full/empty so produce/consumer threads must block.
    14331436Leaving the monitor and trying again (busy waiting) is impractical for high-level programming.
    1434 Monitors eliminate busy waiting by providing synchronization to schedule threads needing access to the shared data, where threads block versus spinning.
     1437Monitors eliminate busy waiting by providing internal synchronization to schedule threads needing access to the shared data, where the synchronization is blocking (threads are parked) versus spinning.
    14351438Synchronization is generally achieved with internal~\cite{Hoare74} or external~\cite[\S~2.9.2]{uC++} scheduling, where \newterm{scheduling} defines which thread acquires the critical section next.
    14361439\newterm{Internal scheduling} is characterized by each thread entering the monitor and making an individual decision about proceeding or blocking, while \newterm{external scheduling} is characterized by an entering thread making a decision about proceeding for itself and on behalf of other threads attempting entry.
    … …  
    15221525\end{figure}
    15231526
    1524 Figure~\ref{f:BBExt} shows a \CFA generic bounded-buffer with external scheduling, where producers/consumers detecting a full/empty buffer block and prevent more producers/consumers from entering the monitor until there is a free/empty slot in the buffer.
     1527Figure~\ref{f:BBExt} shows a \CFA generic bounded-buffer with external scheduling, where producers/consumers detecting a full/empty buffer block and prevent more producers/consumers from entering the monitor until the buffer has a free/empty slot.
    15251528External scheduling is controlled by the @waitfor@ statement, which atomically blocks the calling thread, releases the monitor lock, and restricts the routine calls that can next acquire mutual exclusion.
    15261529If the buffer is full, only calls to @remove@ can acquire the buffer, and if the buffer is empty, only calls to @insert@ can acquire the buffer.
    1527 Threads making calls to routines that are currently excluded, block outside of (external to) the monitor on a calling queue, versus blocking on condition queues inside of (internal to) the monitor.
     1530Threads making calls to routines that are currently excluded, block outside (external) of the monitor on a calling queue, versus blocking on condition queues inside (internal) of the monitor.
     1531% External scheduling is more constrained and explicit, which helps programmers reduce the non-deterministic nature of concurrency.
    15281532External scheduling allows users to wait for events from other threads without concern of unrelated events occurring.
    15291533The mechnaism can be done in terms of control flow, \eg Ada @accept@ or \uC @_Accept@, or in terms of data, \eg Go channels.
    … …  
    15421546A thread blocks until an appropriate partner arrives.
    15431547The complexity is exchanging phone numbers in the monitor because of the mutual-exclusion property.
    1544 For signal scheduling, the @exchange@ condition is necessary to block the thread finding the match, while the matcher unblocks to take the opposite number, post its phone number, and unblock the partner.
     1548For signal scheduling, the @exchange@ condition is necessary to block the thread finding the match, while the matcher unblocks to take the oppose number, post its phone number, and unblock the partner.
    15451549For signal-block scheduling, the implicit urgent-queue replaces the explict @exchange@-condition and @signal_block@ puts the finding thread on the urgent condition and unblocks the matcher.
    15461550
    … …  
    15631567                wait( Girls[ccode] );
    15641568                GirlPhNo = phNo;
    1565                 `signal( exchange );`
     1569                `exchange.signal();`
    15661570        } else {
    15671571                GirlPhNo = phNo;
    15681572                `signal( Boys[ccode] );`
    1569                 `wait( exchange );`
     1573                `exchange.wait();`
    15701574        } // if
    15711575        return BoyPhNo;
    … …  
    16421646}
    16431647\end{cfa}
    1644 must have acquired at least the same locks as the waiting thread signalled from the condition queue.
     1648must have acquired monitor locks that are greater than or equal to the number of locks for the waiting thread signalled from the condition queue.
    16451649
    16461650Similarly, for @waitfor( rtn )@, the default semantics is to atomically block the acceptor and release all acquired mutex types in the parameter list, \ie @waitfor( rtn, m1, m2 )@.
    … …  
    16481652@waitfor@ statically verifies the released monitors are the same as the acquired mutex-parameters of the given routine or routine pointer.
    16491653To statically verify the released monitors match with the accepted routine's mutex parameters, the routine (pointer) prototype must be accessible.
    1650 % When an overloaded routine appears in an @waitfor@ statement, calls to any routine with that name are accepted.
    1651 % The rationale is that members with the same name should perform a similar function, and therefore, all should be eligible to accept a call.
    1652 Overloaded routines can be disambiguated using a cast:
     1654
     1655When an overloaded routine appears in an @waitfor@ statement, calls to any routine with that name are accepted.
     1656The rationale is that members with the same name should perform a similar function, and therefore, all should be eligible to accept a call.
     1657As always, overloaded routines can be disambiguated using a cast:
    16531658\begin{cfa}
    16541659void rtn( M & mutex m );
    16551660`int` rtn( M & mutex m );
    1656 waitfor( (`int` (*)( M & mutex ))rtn, m );
    1657 \end{cfa}
    1658 
    1659 The ability to release a subset of acquired monitors can result in a \newterm{nested monitor}~\cite{Lister77} deadlock.
     1661waitfor( (`int` (*)( M & mutex ))rtn, m1, m2 );
     1662\end{cfa}
     1663
     1664Given the ability to release a subset of acquired monitors can result in a \newterm{nested monitor}~\cite{Lister77} deadlock.
    16601665\begin{cfa}
    16611666void foo( M & mutex m1, M & mutex m2 ) {
    … …  
    16681673
    16691674Finally, an important aspect of monitor implementation is barging, \ie can calling threads barge ahead of signalled threads?
    1670 If barging is allowed, synchronization between a signaller and signallee is difficult, often requiring multiple unblock/block cycles (looping around a wait rechecking if a condition is met).
    1671 In fact, signals-as-hints is completely opposite from that proposed by Hoare in the seminal paper on monitors:
     1675If barging is allowed, synchronization between a singller and signallee is difficult, often requiring multiple unblock/block cycles (looping around a wait rechecking if a condition is met).
    16721676\begin{quote}
    16731677However, we decree that a signal operation be followed immediately by resumption of a waiting program, without possibility of an intervening procedure call from yet a third program.
    … …  
    16751679\end{quote}
    16761680\CFA scheduling \emph{precludes} barging, which simplifies synchronization among threads in the monitor and increases correctness.
    1677 Furthermore, \CFA concurrency has no spurious wakeup~\cite[\S~9]{Buhr05a}, which eliminates an implict form of barging.
    16781681For example, there are no loops in either bounded buffer solution in Figure~\ref{f:GenericBoundedBuffer}.
    16791682Supporting barging prevention as well as extending internal scheduling to multiple monitors is the main source of complexity in the design and implementation of \CFA concurrency.
     1683Furthermore, \CFA concurrency has no superious wakeup~\cite[\S~9]{Buhr05a}, which eliminates an implict form of barging.
    16801684
    16811685
    … …  
    17491753
    17501754One scheduling solution is for the signaller to keep ownership of all locks until the last lock is ready to be transferred, because this semantics fits most closely to the behaviour of single-monitor scheduling.
    1751 However, Figure~\ref{f:OtherWaitingThread} shows this solution is complex depending on other waiters, resulting in options when the signaller finishes the inner mutex-statement.
    1752 The signaller can retain @m2@ until completion of the outer mutex statement and pass the locks to waiter W1, or it can pass @m2@ to waiter W2 after completing the inner mutex-statement, while continuing to hold @m1@.
     1755However, Figure~\ref{f:OtherWaitingThread} shows this solution is complex depending on other waiters, resulting is choices when the signaller finishes the inner mutex-statement.
     1756The singaller can retain @m2@ until completion of the outer mutex statement and pass the locks to waiter W1, or it can pass @m2@ to waiter W2 after completing the inner mutex-statement, while continuing to hold @m1@.
    17531757In the latter case, waiter W2 must eventually pass @m2@ to waiter W1, which is complex because W1 may have waited before W2, so W2 is unaware of it.
    17541758Furthermore, there is an execution sequence where the signaller always finds waiter W2, and hence, waiter W1 starves.
    … …  
    17571761Signalled threads are moved to the urgent queue and the waiter at the front defines the set of monitors necessary for it to unblock.
    17581762Partial signalling transfers ownership of monitors to the front waiter.
    1759 When the signaller thread exits or waits in the monitor, the front waiter is unblocked if all its monitors are released.
    1760 The benefit is encapsulating complexity into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
     1763When the signaller thread exits or waits in the monitor the front waiter is unblocked if all its monitors are released.
     1764This solution has the benefit that complexity is encapsulated into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
    17611765
    17621766
    … …  
    17651769
    17661770In an object-oriented programming-language, a class includes an exhaustive list of operations.
    1767 However, new members can be added via static inheritance or dynamic members, \eg JavaScript~\cite{JavaScript}.
     1771However, new members can be added via static inheritance or dynaic members, \eg JavaScript~\cite{JavaScript}.
    17681772Similarly, monitor routines can be added at any time in \CFA, making it less clear for programmers and more difficult to implement.
    17691773\begin{cfa}
    1770 monitor M { ... };
     1774monitor M {};
    17711775void `f`( M & mutex m );
    17721776void g( M & mutex m ) { waitfor( `f` ); }       $\C{// clear which f}$
    … …  
    17741778void h( M & mutex m ) { waitfor( `f` ); }       $\C{// unclear which f}$
    17751779\end{cfa}
    1776 Hence, the cfa-code for entering a monitor looks like:
     1780Hence, the cfa-code for the entering a monitor looks like:
    17771781\begin{cfa}
    17781782if ( $\textrm{\textit{monitor is free}}$ ) $\LstCommentStyle{// \color{red}enter}$
    … …  
    18141818External scheduling, like internal scheduling, becomes significantly more complex for multi-monitor semantics.
    18151819Even in the simplest case, new semantics needs to be established.
    1816 \newpage
    1817 \begin{cfa}
    1818 monitor M { ... };
     1820\begin{cfa}
     1821monitor M {};
    18191822void f( M & mutex m1 );
    18201823void g( M & mutex m1, M & mutex m2 ) {
    … …  
    18261829        waitfor( f, m2 );                                               $\C{\color{red}// wait for call to f with argument m2}$
    18271830\end{cfa}
    1828 Both locks are acquired by routine @g@, so when routine @f@ is called, the lock for monitor @m2@ is passed from @g@ to @f@, while @g@ still holds lock @m1@.
     1831Routine @g@ has acquired both locks, so when routine @f@ is called, the lock for monitor @m2@ is passed from @g@ to @f@, while @g@ still holds lock @m1@.
    18291832This behaviour can be extended to the multi-monitor @waitfor@ statement.
    18301833\begin{cfa}
    1831 monitor M { ... };
     1834monitor M {};
    18321835void f( M & mutex m1, M & mutex m2 );
    18331836void g( M & mutex m1, M & mutex m2 ) {
    … …  
    18361839\end{cfa}
    18371840Again, the set of monitors passed to the @waitfor@ statement must be entirely contained in the set of monitors already acquired by the accepting routine.
    1838 Also, the order of the monitors in a @waitfor@ statement is unimportant.
    1839 
    1840 Figure~\ref{f:UnmatchedMutexSets} shows an example where, for internal and external scheduling with multiple monitors, a signalling or accepting thread must match exactly, \ie partial matching results in waiting.
    1841 For both examples, the set of monitors is disjoint so unblocking is impossible.
    1842 
    1843 \begin{figure}
     1841
     1842Note, for internal and external scheduling with multiple monitors, a signalling or accepting thread must match exactly, \ie partial matching results in waiting.
     1843\begin{cquote}
    18441844\lstDeleteShortInline@%
    18451845\begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
    … …  
    18541854        wait( c );
    18551855}
    1856 g( `m11`, m2 ); // block on wait
     1856g( `m11`, m2 ); // block on accept
    18571857f( `m12`, m2 ); // cannot fulfil
    18581858\end{cfa}
    … …  
    18731873\end{tabular}
    18741874\lstMakeShortInline@%
    1875 \caption{Unmatched \protect\lstinline@mutex@ sets}
    1876 \label{f:UnmatchedMutexSets}
    1877 \end{figure}
     1875\end{cquote}
     1876For both internal and external scheduling, the set of monitors is disjoint so unblocking is impossible.
    18781877
    18791878
    18801879\subsection{Extended \protect\lstinline@waitfor@}
    18811880
    1882 Figure~\ref{f:ExtendedWaitfor} show the extended form of the @waitfor@ statement to conditionally accept one of a group of mutex routines, with a specific action to be performed \emph{after} the mutex routine finishes.
    1883 For a @waitfor@ clause to be executed, its @when@ must be true and an outstanding call to its corresponding member(s) must exist.
    1884 The \emph{conditional-expression} of a @when@ may call a routine, but the routine must not block or context switch.
    1885 If there are multiple acceptable mutex calls, selection occurs top-to-bottom (prioritized) in the @waitfor@ clauses, whereas some programming languages with similar mechanisms accept non-deterministically for this case, \eg Go \lstinline[morekeywords=select]@select@.
    1886 If some accept guards are true and there are no outstanding calls to these members, the acceptor is accept-blocked until a call to one of these members is made.
    1887 If all the accept guards are false, the statement does nothing, unless there is a terminating @else@ clause with a true guard, which is executed instead.
    1888 Hence, the terminating @else@ clause allows a conditional attempt to accept a call without blocking.
    1889 If there is a @timeout@ clause, it provides an upper bound on waiting.
    1890 If both a @timeout@ clause and an @else@ clause are present, the @else@ must be conditional, or the @timeout@ is never triggered.
    1891 In all cases, the statement following is executed \emph{after} a clause is executed to know which of the clauses executed.
    1892 
    1893 \begin{figure}
     1881The extended form of the @waitfor@ statement conditionally accepts one of a group of mutex routines and allows a specific action to be performed \emph{after} the mutex routine finishes.
    18941882\begin{cfa}
    18951883`when` ( $\emph{conditional-expression}$ )      $\C{// optional guard}$
    … …  
    19071895                $\emph{statement}$                                      $\C{// action when no immediate calls}$
    19081896\end{cfa}
    1909 \caption{Extended \protect\lstinline@waitfor@}
    1910 \label{f:ExtendedWaitfor}
    1911 \end{figure}
     1897For a @waitfor@ clause to be executed, its @when@ must be true and an outstanding call to its corresponding member(s) must exist.
     1898The \emph{conditional-expression} of a @when@ may call a routine, but the routine must not block or context switch.
     1899If there are several mutex calls that can be accepted, selection occurs top-to-bottom in the @waitfor@ clauses versus non-deterministically.
     1900If some accept guards are true and there are no outstanding calls to these members, the acceptor is accept-blocked until a call to one of these members is made.
     1901If all the accept guards are false, the statement does nothing, unless there is a terminating @else@ clause with a true guard, which is executed instead.
     1902Hence, the terminating @else@ clause allows a conditional attempt to accept a call without blocking.
     1903If there is a @timeout@ clause, it provides an upper bound on waiting, and can only appear with a conditional @else@, otherwise the timeout cannot be triggered.
     1904In all cases, the statement following is executed \emph{after} a clause is executed to know which of the clauses executed.
    19121905
    19131906Note, a group of conditional @waitfor@ clauses is \emph{not} the same as a group of @if@ statements, e.g.:
    … …  
    19221915\begin{cfa}
    19231916void insert( Buffer(T) & mutex buffer, T elem ) with( buffer ) {
    1924         if ( count == 10 )
     1917        if ( count == BufferSize )
    19251918                waitfor( remove, buffer ) {
    1926                         // insert elem into buffer
     1919                        elements[back] = elem;
     1920                        back = ( back + 1 ) % BufferSize;
     1921                        count += 1;
    19271922                } or `waitfor( ^?{}, buffer )` throw insertFail;
    19281923}
    … …  
    19301925When the buffer is deallocated, the current waiter is unblocked and informed, so it can perform an appropriate action.
    19311926However, the basic @waitfor@ semantics do not support this functionality, since using an object after its destructor is called is undefined.
    1932 Therefore, to make this useful capability work, the semantics for accepting the destructor is the same as @signal@, \ie the call to the destructor is placed on the urgent queue and the acceptor continues execution, which throws an exception to the acceptor and then the caller is unblocked from the urgent queue to deallocate the object.
     1927Therefore, to make this useful capability work, the semantics for accepting the destructor is the same as @signal@, \ie the call to the destructor is placed on the urgent queue and the acceptor continues execution, which throws an exception to the acceptor and then the caller is unbloced from the urgent queue to deallocate the object.
    19331928Accepting the destructor is an idiomatic way to terminate a thread in \CFA.
    19341929
    … …  
    19381933Threads in \CFA are monitors to allow direct communication among threads, \ie threads can have mutex routines that are called by other threads.
    19391934Hence, all monitor features are available when using threads.
    1940 The following shows an example of two threads directly calling each other and accepting calls from each other in a cycle.
     1935Figure~\ref{f:pingpong} shows an example of two threads directly calling each other and accepting calls from each other in a cycle.
     1936Note, both ping/pong threads are globally declared, @pi@/@po@, and hence, start (and possibly complete) before the program main starts.
     1937
     1938\begin{figure}
     1939\lstDeleteShortInline@%
     1940\begin{cquote}
    19411941\begin{cfa}
    19421942thread Ping {} pi;
    … …  
    19461946int main() {}
    19471947\end{cfa}
    1948 \vspace{-0.8\baselineskip}
    1949 \begin{cquote}
    19501948\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}}
    19511949\begin{cfa}
    … …  
    19671965\end{cfa}
    19681966\end{tabular}
     1967\lstMakeShortInline@%
    19691968\end{cquote}
    1970 % \lstMakeShortInline@%
    1971 % \caption{Threads ping/pong using external scheduling}
    1972 % \label{f:pingpong}
    1973 % \end{figure}
    1974 Note, the ping/pong threads are globally declared, @pi@/@po@, and hence, start (and possibly complete) before the program main starts.
    1975 
    1976 
    1977 \subsection{Low-level Locks}
    1978 
    1979 For completeness and efficiency, \CFA provides a standard set of low-level locks: recursive mutex, condition, semaphore, barrier, \etc, and atomic instructions: @fetchAssign@, @fetchAdd@, @testSet@, @compareSet@, \etc.
    1980 
     1969\caption{Threads ping/pong using external scheduling}
     1970\label{f:pingpong}
     1971\end{figure}
    19811972
    19821973\section{Parallelism}
    19831974
    19841975Historically, computer performance was about processor speeds.
    1985 However, with heat dissipation being a direct consequence of speed increase, parallelism is the new source for increased performance~\cite{Sutter05, Sutter05b}.
     1976However, with heat dissipation being a direct consequence of speed increase, parallelism has become the new source for increased performance~\cite{Sutter05, Sutter05b}.
    19861977Now, high-performance applications must care about parallelism, which requires concurrency.
    19871978The lowest-level approach of parallelism is to use \newterm{kernel threads} in combination with semantics like @fork@, @join@, \etc.
    … …  
    20021993\label{s:fibers}
    20031994
    2004 A variant of user thread is \newterm{fibers}, which removes preemption, \eg Go~\cite{Go} @goroutine@s.
    2005 Like functional programming, which removes mutation and its associated problems, removing preemption from concurrency reduces nondeterminism, making race and deadlock errors more difficult to generate.
     1995A variant of user thread is \newterm{fibers}, which removes preemption, \eg Go~\cite{Go}.
     1996Like functional programming, which removes mutation and its associated problems, removing preemption from concurrency reduces nondeterminism, hence race and deadlock errors are more difficult to generate.
    20061997However, preemption is necessary for concurrency that relies on spinning, so there are a class of problems that cannot be programmed without preemption.
    20071998
    … …  
    20092000\subsection{Thread Pools}
    20102001
    2011 In contrast to direct threading is indirect \newterm{thread pools}, where small jobs (work units) are inserted into a work pool for execution.
     2002In contrast to direct threading is indirect \newterm{thread pools}, where small jobs (work units) are insert into a work pool for execution.
    20122003If the jobs are dependent, \ie interact, there is an implicit/explicit dependency graph that ties them together.
    20132004While removing direct concurrency, and hence the amount of context switching, thread pools significantly limit the interaction that can occur among jobs.
    2014 Indeed, jobs should not block because that also blocks the underlying thread, which effectively means the CPU utilization, and therefore throughput, suffers.
     2005Indeed, jobs should not block because that also block the underlying thread, which effectively means the CPU utilization, and therefore throughput, suffers.
    20152006While it is possible to tune the thread pool with sufficient threads, it becomes difficult to obtain high throughput and good core utilization as job interaction increases.
    20162007As well, concurrency errors return, which threads pools are suppose to mitigate.
     2008Intel's TBB library~\cite{TBB} is the gold standard for thread pools.
    20172009
    20182010
    … …  
    20442036The user cluster is created to contain the application user-threads.
    20452037Having all threads execute on the one cluster often maximizes utilization of processors, which minimizes runtime.
    2046 However, because of limitations of the underlying operating system, heterogeneous hardware, or scheduling requirements (real-time), multiple clusters are sometimes necessary.
     2038However, because of limitations of the underlying operating system, heterogeneous hardware, or scheduling requirements (real-time), it is sometimes necessary to have multiple clusters.
    20472039
    20482040
    … …  
    20692061
    20702062\section{Implementation}
    2071 \label{s:Implementation}
    20722063
    20732064Currently, \CFA has fixed-sized stacks, where the stack size can be set at coroutine/thread creation but with no subsequent growth.
    20742065Schemes exist for dynamic stack-growth, such as stack copying and chained stacks.
    2075 However, stack copying requires pointer adjustment to items on the stack, which is impossible without some form of garbage collection.
     2066However, stack copying requires pointer adjustment to items on the stack, which is impossible without some form of garage collection.
    20762067As well, chained stacks require all modules be recompiled to use this feature, which breaks backward compatibility with existing C libraries.
    20772068In the long term, it is likely C libraries will migrate to stack chaining to support concurrency, at only a minimal cost to sequential programs.
    … …  
    20832074This storage is allocated at the base of a thread's stack before blocking, which means programmers must add a small amount of extra space for stacks.
    20842075
    2085 In \CFA, ordering of monitor acquisition relies on memory ordering to prevent deadlock~\cite{Havender68}, because all objects have distinct non-overlapping memory layouts, and mutual-exclusion for a monitor is only defined for its lifetime.
     2076In \CFA, ordering of monitor acquisition relies on memory ordering to prevent deadlock~\cite{Havender68}, because all objects are guaranteed to have distinct non-overlapping memory layouts, and mutual-exclusion for a monitor is only defined for its lifetime.
    20862077When a mutex call is made, pointers to the concerned monitors are aggregated into a variable-length array and sorted.
    2087 This array persists for the entire duration of the mutual exclusion and is used extensively for synchronization operations.
    2088 
    2089 To improve performance and simplicity, context switching occurs inside a routine call, so only callee-saved registers are copied onto the stack and then the stack register is switched;
     2078This array persists for the entire duration of the mutual-exclusion and its ordering reused extensively.
     2079
     2080To improve performance and simplicity, context switching occur inside a routine call, so only callee-saved registers are copied onto the stack and then the stack register is switched;
    20902081the corresponding registers are then restored for the other context.
    20912082Note, the instruction pointer is untouched since the context switch is always inside the same routine.
    … …  
    20942085This method is a 2-step context-switch and provides a clear distinction between user and kernel code, where scheduling and other system operations happen.
    20952086The alternative 1-step context-switch uses the \emph{from} thread's stack to schedule and then context-switches directly to the \emph{to} thread's stack.
    2096 Experimental results (not presented) show the performance of these two approaches is virtually equivalent, because both approaches are dominated by locking to prevent a race condition.
     2087Experimental results (not presented) show the performance difference between these two approaches is virtually equivalent, because the 1-step performance is dominated by a lock instruction to prevent a race condition.
    20972088
    20982089All kernel threads (@pthreads@) created a stack.
    … …  
    21022093
    21032094Finally, an important aspect for a complete threading system is preemption, which introduces extra non-determinism via transparent interleaving, rather than cooperation among threads for proper scheduling and processor fairness from long-running threads.
    2104 Because preemption frequency is usually long (1 millisecond) performance cost is negligible.
     2095Because preemption frequency is usually long, 1 millisecond, performance cost is negligible.
    21052096Preemption is normally handled by setting a count-down timer on each virtual processor.
    21062097When the timer expires, an interrupt is delivered, and the interrupt handler resets the count-down timer, and if the virtual processor is executing in user code, the signal handler performs a user-level context-switch, or if executing in the language runtime-kernel, the preemption is ignored or rolled forward to the point where the runtime kernel context switches back to user code.
    21072098Multiple signal handlers may be pending.
    2108 When control eventually switches back to the signal handler, it returns normally, and execution continues in the interrupted user thread, even though the return from the signal handler may be on a different kernel thread than the one where the signal is delivered.
     2099When control eventually switches back to the signal handler, it returns normally, and execution continues in the interrupted user thread, even though the return from the signal handler may be on a different kernel thread than the one where the signal was delivered.
    21092100The only issue with this approach is that signal masks from one kernel thread may be restored on another as part of returning from the signal handler;
    2110 therefore, the same signal mask is required for all virtual processors in a cluster.
     2101therefore, all virtual processors in a cluster need to have the same signal mask.
    21112102
    21122103However, on current UNIX systems:
    … …  
    21662157\end{cfa}
    21672158The method used to get time is @clock_gettime( CLOCK_REALTIME )@.
    2168 Each benchmark is performed @N@ times, where @N@ varies depending on the benchmark;
    2169 the total time is divided by @N@ to obtain the average time for a benchmark.
     2159Each benchmark is performed @N@ times, where @N@ varies depending on the benchmark, the total time is divided by @N@ to obtain the average time for a benchmark.
    21702160All omitted tests for other languages are functionally identical to the shown \CFA test.
    21712161
    … …  
    22252215\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    22262216\hline
    2227 Kernel Thread   & 333.5 & 332.96        & 4.1 \\
    2228 \CFA Coroutine  & 49            & 48.68 & 0.47    \\
    2229 \CFA Thread             & 105           & 105.57        & 1.37 \\
    2230 \uC Coroutine   & 44            & 44            & 0 \\
    2231 \uC Thread              & 100           & 99.29 & 0.96 \\
    2232 Goroutine               & 145           & 147.25        & 4.15 \\
    2233 Java Thread             & 373.5 & 375.14        & 8.72 \\
     2217Kernel Thread   & 241.5         & 243.86        & 5.08 \\
     2218\CFA Coroutine  & 38            & 38            & 0    \\
     2219\CFA Thread             & 103           & 102.96        & 2.96 \\
     2220\uC Coroutine   & 46            & 45.86         & 0.35 \\
     2221\uC Thread              & 98            & 99.11         & 1.42 \\
     2222Goroutine               & 150           & 149.96        & 3.16 \\
     2223Java Thread             & 289           & 290.68        & 8.72 \\
    22342224\hline
    22352225\end{tabular}
    … …  
    22402230\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
    22412231\begin{cfa}
    2242 monitor M { ... } m1/*, m2, m3, m4*/;
     2232monitor M {} m1/*, m2, m3, m4*/;
    22432233void __attribute__((noinline)) do_call( M & mutex m/*, m2, m3, m4*/ ) {}
    22442234int main() {
    … …  
    22602250\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    22612251\hline
    2262 C routine                                       & 2             & 2             & 0    \\
    2263 FetchAdd + FetchSub                     & 26            & 26            & 0    \\
    2264 Pthreads Mutex Lock                     & 31            & 31.71 & 0.97 \\
    2265 \uC @monitor@ member routine            & 31            & 31            & 0    \\
    2266 \CFA @mutex@ routine, 1 argument        & 46            & 46.68 & 0.93  \\
    2267 \CFA @mutex@ routine, 2 argument        & 84            & 85.36 & 1.99 \\
    2268 \CFA @mutex@ routine, 4 argument        & 158           & 161           & 4.22 \\
    2269 Java synchronized routine               & 27.5  & 29.79 & 2.93  \\
     2252C routine                                                       & 2                     & 2                     & 0    \\
     2253FetchAdd + FetchSub                                     & 26            & 26            & 0    \\
     2254Pthreads Mutex Lock                                     & 31            & 31.86         & 0.99 \\
     2255\uC @monitor@ member routine            & 30            & 30            & 0    \\
     2256\CFA @mutex@ routine, 1 argument        & 41            & 41.57         & 0.9  \\
     2257\CFA @mutex@ routine, 2 argument        & 76            & 76.96         & 1.57 \\
     2258\CFA @mutex@ routine, 4 argument        & 145           & 146.68        & 3.85 \\
     2259Java synchronized routine                       & 27            & 28.57         & 2.6  \\
    22702260\hline
    22712261\end{tabular}
    … …  
    22872277Figure~\ref{f:int-sched} shows the code for \CFA, with results in Table~\ref{tab:int-sched}.
    22882278Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects.
    2289 Java scheduling is significantly greater because the benchmark explicitly creates multiple thread in order to prevent the JIT from making the program sequential, \ie removing all locking.
    22902279
    22912280\begin{figure}
    … …  
    22942283volatile int go = 0;
    22952284condition c;
    2296 monitor M { ... } m;
     2285monitor M {} m;
    22972286void __attribute__((noinline)) do_call( M & mutex a1 ) { signal( c ); }
    22982287thread T {};
    … …  
    23122301}
    23132302\end{cfa}
    2314 \captionof{figure}{\CFA Internal-scheduling benchmark}
     2303\captionof{figure}{\CFA Internal scheduling benchmark}
    23152304\label{f:int-sched}
    23162305
    23172306\centering
    2318 \captionof{table}{Internal-scheduling comparison (nanoseconds)}
     2307\captionof{table}{Internal scheduling comparison (nanoseconds)}
    23192308\label{tab:int-sched}
    23202309\bigskip
    … …  
    23242313\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    23252314\hline
    2326 Pthreads Condition Variable             & 6005  & 5681.43       & 835.45 \\
    2327 \uC @signal@                                    & 324           & 325.54        & 3,02   \\
    2328 \CFA @signal@, 1 @monitor@              & 368.5         & 370.61        & 4.77   \\
    2329 \CFA @signal@, 2 @monitor@              & 467           & 470.5 & 6.79   \\
    2330 \CFA @signal@, 4 @monitor@              & 700.5         & 702.46        & 7.23  \\
    2331 Java @notify@                                   & 15471 & 172511        & 5689 \\
     2315Pthreads Condition Variable             & 5902.5        & 6093.29       & 714.78 \\
     2316\uC @signal@                                    & 322           & 323           & 3.36   \\
     2317\CFA @signal@, 1 @monitor@              & 352.5         & 353.11        & 3.66   \\
     2318\CFA @signal@, 2 @monitor@              & 430           & 430.29        & 8.97   \\
     2319\CFA @signal@, 4 @monitor@              & 594.5         & 606.57        & 18.33  \\
     2320Java @notify@                                   & 13831.5       & 15698.21      & 4782.3 \\
    23322321\hline
    23332322\end{tabular}
    … …  
    23452334\begin{cfa}
    23462335volatile int go = 0;
    2347 monitor M { ... } m;
     2336monitor M {} m;
    23482337thread T {};
    23492338void __attribute__((noinline)) do_call( M & mutex ) {}
    … …  
    23632352}
    23642353\end{cfa}
    2365 \captionof{figure}{\CFA external-scheduling benchmark}
     2354\captionof{figure}{\CFA external scheduling benchmark}
    23662355\label{f:ext-sched}
    23672356
    23682357\centering
    23692358
    2370 \captionof{table}{External-scheduling comparison (nanoseconds)}
     2359\captionof{table}{External scheduling comparison (nanoseconds)}
    23712360\label{tab:ext-sched}
    23722361\bigskip
    … …  
    23752364\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    23762365\hline
    2377 \uC @_Accept@                           & 358           & 359.11        & 2.53  \\
    2378 \CFA @waitfor@, 1 @monitor@     & 359           & 360.93        & 4.07  \\
    2379 \CFA @waitfor@, 2 @monitor@     & 450           & 449.39        & 6.62  \\
    2380 \CFA @waitfor@, 4 @monitor@     & 652           & 655.64        & 7.73 \\
     2366\uC @_Accept@                           & 350           & 350.61        & 3.11  \\
     2367\CFA @waitfor@, 1 @monitor@     & 358.5         & 358.36        & 3.82  \\
     2368\CFA @waitfor@, 2 @monitor@     & 422           & 426.79        & 7.95  \\
     2369\CFA @waitfor@, 4 @monitor@     & 579.5         & 585.46        & 11.25 \\
    23812370\hline
    23822371\end{tabular}
    … …  
    23942383}
    23952384\end{cfa}
    2396 \captionof{figure}{\CFA object-creation benchmark}
     2385\captionof{figure}{\CFA object creation benchmark}
    23972386\label{f:creation}
    23982387
    … …  
    24072396\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} & \multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    24082397\hline
    2409 Pthreads                                & 28091         & 28073.39      & 163.1  \\
    2410 \CFA Coroutine Lazy             & 6                     & 6.07          & 0.26   \\
    2411 \CFA Coroutine Eager    & 520           & 520.61        & 2.04   \\
    2412 \CFA Thread                             & 2032  & 2016.29       & 112.07  \\
    2413 \uC Coroutine                   & 106           & 107.36        & 1.47   \\
    2414 \uC Thread                              & 536.5 & 537.07        & 4.64   \\
    2415 Goroutine                               & 3103  & 3086.29       & 90.25  \\
    2416 Java Thread                             & 103416.5      & 103732.29     & 1137 \\
     2398Pthreads                                & 26996         & 26984.71      & 156.6  \\
     2399\CFA Coroutine Lazy             & 6                     & 5.71          & 0.45   \\
     2400\CFA Coroutine Eager    & 708           & 706.68        & 4.82   \\
     2401\CFA Thread                             & 1173.5        & 1176.18       & 15.18  \\
     2402\uC Coroutine                   & 109           & 107.46        & 1.74   \\
     2403\uC Thread                              & 526           & 530.89        & 9.73   \\
     2404Goroutine                               & 2520.5        & 2530.93       & 61.56  \\
     2405Java Thread                             & 91114.5       & 92272.79      & 961.58 \\
    24172406\hline
    24182407\end{tabular}
    … …  
    24292418\section{Conclusion}
    24302419
    2431 This paper demonstrates a concurrency API that is simple, efficient, and able to build higher-level concurrency features.
     2420This paper demonstrate a concurrency API that is simple, efficient, and able to build higher-level concurrency features.
    24322421The approach provides concurrency based on a preemptive M:N user-level threading-system, executing in clusters, which encapsulate scheduling of work on multiple kernel threads providing parallelism.
    24332422The M:N model is judged to be efficient and provide greater flexibility than a 1:1 threading model.
    … …  
    24502439However, no single scheduler is optimal for all workloads and therefore there is value in being able to change the scheduler for given programs.
    24512440One solution is to offer various tweaking options, allowing the scheduler to be adjusted to the requirements of the workload.
    2452 However, to be truly flexible, a pluggable scheduler is necessary.
     2441However, to be truly flexible, it is necessary to have a pluggable scheduler.
    24532442Currently, the \CFA pluggable scheduler is too simple to handle complex scheduling, \eg quality of service and real-time, where the scheduler must interact with mutex objects to deal with issues like priority inversion.
    24542443
    … …  
    24602449At its core, non-blocking I/O is an operating-system level feature queuing IO operations, \eg network operations, and registering for notifications instead of waiting for requests to complete.
    24612450Current trends use asynchronous programming like callbacks, futures, and/or promises, \eg Node.js~\cite{NodeJs} for JavaScript, Spring MVC~\cite{SpringMVC} for Java, and Django~\cite{Django} for Python.
    2462 However, these solutions lead to code that is hard to create, read and maintain.
     2451However, these solutions lead to code that is hard create, read and maintain.
    24632452A better approach is to tie non-blocking I/O into the concurrency system to provide ease of use with low overhead, \eg thread-per-connection web-services.
    24642453A non-blocking I/O library is currently under development for \CFA.
    … …  
    24672456\label{futur:tools}
    24682457
    2469 While monitors offer flexible and powerful concurrency for \CFA, other concurrency tools are also necessary for a complete multi-paradigm concurrency package.
     2458While monitors offer a flexible and powerful concurrent for \CFA, other concurrency tools are also necessary for a complete multi-paradigm concurrency package.
    24702459Examples of such tools can include futures and promises~\cite{promises}, executors and actors.
    24712460These additional features are useful when monitors offer a level of abstraction that is inadequate for certain tasks.
    2472 As well, new \CFA extensions should make it possible to create a uniform interface for virtually all mutual exclusion, including monitors and low-level locks.
    24732461
    24742462\paragraph{Implicit Threading}
    … …  
    24792467The canonical example of implicit concurrency is concurrent nested @for@ loops, which are amenable to divide and conquer algorithms~\cite{uC++book}.
    24802468The \CFA language features should make it possible to develop a reasonable number of implicit concurrency mechanism to solve basic HPC data-concurrency problems.
    2481 However, implicit concurrency is a restrictive solution with significant limitations, so it can never replace explicit concurrent programming.
     2469However, implicit concurrency is a restrictive solution and has its limitations, so it can never replace explicit concurrent programming.
    24822470
    24832471
Note: See TracChangeset for help on using the changeset viewer.