Ignore:
Timestamp:
Jun 27, 2018, 6:37:47 PM (3 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer
Children:
6d6cf5a
Parents:
203c667
Message:

first complete draft

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/concurrency/Paper.tex

    r203c667 rb199e54  
    2121\renewcommand{\thesubfigure}{(\Alph{subfigure})}
    2222\captionsetup{justification=raggedright,singlelinecheck=false}
    23 \usepackage{siunitx}
    24 \sisetup{binary-units=true}
     23\usepackage{dcolumn}                                            % align decimal points in tables
    2524
    2625\hypersetup{breaklinks=true}
     
    258257An easier approach for programmers is to support higher-level constructs as the basis of concurrency.
    259258Indeed, for highly productive concurrent programming, high-level approaches are much more popular~\cite{Hochstein05}.
    260 Examples of high-level approaches are task (work) based~\cite{TBB}, implicit threading~\cite{OpenMP}, monitors~\cite{Java}, channels~\cite{CSP,Go}, and message passing~\cite{Erlang,MPI}.
     259Examples of high-level approaches are jobs (tasks) based~\cite{TBB}, implicit threading~\cite{OpenMP}, monitors~\cite{Java}, channels~\cite{CSP,Go}, and message passing~\cite{Erlang,MPI}.
    261260
    262261The following terminology is used.
     
    438437\begin{tabular}{@{}ll@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
    439438\begin{cfa}
    440 int ++? (int op);
    441 int ?++ (int op);
    442 int `?+?` (int op1, int op2);
     439int ++?(int op);
     440int ?++(int op);
     441int `?+?`(int op1, int op2);
    443442int ?<=?(int op1, int op2);
    444443int ?=? (int & op1, int op2);
     
    508507\label{s:ParametricPolymorphism}
    509508
    510 The signature feature of \CFA is parametric-polymorphic routines~\cite{} with routines generalized using a @forall@ clause (giving the language its name), which allow separately compiled routines to support generic usage over multiple types.
     509The signature feature of \CFA is parametric-polymorphic routines~\cite{Cforall} with routines generalized using a @forall@ clause (giving the language its name), which allow separately compiled routines to support generic usage over multiple types.
    511510For example, the following sum routine works for any type that supports construction from 0 and addition:
    512511\begin{cfa}
     
    663662\end{lrbox}
    664663
    665 \subfloat[3 States: global variables]{\label{f:GlobalVariables}\usebox\myboxA}
     664\subfloat[3 States: global variables]{\usebox\myboxA}
    666665\qquad
    667 \subfloat[1 State: external variables]{\label{f:ExternalState}\usebox\myboxB}
     666\subfloat[1 State: external variables]{\usebox\myboxB}
    668667\caption{C Fibonacci Implementations}
    669668\label{f:C-fibonacci}
     
    980979symmetric_coroutine<>::yield_type
    981980\end{cfa}
    982 Similarly, the canonical threading paradigm is often based on routine pointers, \eg @pthreads@~\cite{pthreads}, \Csharp~\cite{Csharp}, Go~\cite{Go}, and Scala~\cite{Scala}.
     981Similarly, the canonical threading paradigm is often based on routine pointers, \eg @pthreads@~\cite{Butenhof97}, \Csharp~\cite{Csharp}, Go~\cite{Go}, and Scala~\cite{Scala}.
    983982However, the generic thread-handle (identifier) is limited (few operations), unless it is wrapped in a custom type.
    984983\begin{cfa}
     
    14001399}
    14011400\end{cfa}
    1402 This example shows a trivial solution to the bank-account transfer problem~\cite{BankTransfer}.
     1401This example shows a trivial solution to the bank-account transfer problem.
    14031402Without multi- and bulk acquire, the solution to this problem requires careful engineering.
    14041403
     
    14091408Like Java, \CFA offers an alternative @mutex@ statement to reduce refactoring and naming.
    14101409\begin{cquote}
    1411 \begin{tabular}{@{}c|@{\hspace{\parindentlnth}}c@{}}
    1412 routine call & @mutex@ statement \\
     1410\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}}
    14131411\begin{cfa}
    14141412monitor M {};
     
    14301428
    14311429\end{cfa}
     1430\\
     1431\multicolumn{1}{c}{\textbf{routine call}} & \multicolumn{1}{c}{\lstinline@mutex@ \textbf{statement}}
    14321432\end{tabular}
    14331433\end{cquote}
     
    15721572                wait( Girls[ccode] );
    15731573                GirlPhNo = phNo;
    1574                 exchange.signal();
     1574                `exchange.signal();`
    15751575        } else {
    15761576                GirlPhNo = phNo;
    1577                 signal( Boys[ccode] );
    1578                 exchange.wait();
     1577                `signal( Boys[ccode] );`
     1578                `exchange.wait();`
    15791579        } // if
    15801580        return BoyPhNo;
     
    16021602        } else {
    16031603                GirlPhNo = phNo; // make phone number available
    1604                 signal_block( Boys[ccode] ); // restart boy
     1604                `signal_block( Boys[ccode] );` // restart boy
    16051605
    16061606        } // if
     
    16571657Waitfor statically verifies the released monitors are the same as the acquired mutex-parameters of the given routine or routine pointer.
    16581658To statically verify the released monitors match with the accepted routine's mutex parameters, the routine (pointer) prototype must be accessible.
     1659
     1660When an overloaded routine appears in an @waitfor@ statement, calls to any routine with that name are accepted.
     1661The rationale is that members with the same name should perform a similar function, and therefore, all should be eligible to accept a call.
     1662As always, overloaded routines can be disambiguated using a cast:
     1663\begin{cfa}
     1664void rtn( M & mutex m );
     1665`int` rtn( M & mutex m );
     1666waitfor( (`int` (*)( M & mutex ))rtn, m1, m2 );
     1667\end{cfa}
    16591668
    16601669Given the ability to release a subset of acquired monitors can result in a \newterm{nested monitor}~\cite{Lister77} deadlock.
     
    17591768This 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.
    17601769
    1761 \begin{comment}
    1762 Figure~\ref{f:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
    1763 Because the third thread is signalled when secretly holding @B@, the goal  becomes unreachable.
    1764 Depending on the order of signals (listing \ref{f:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
    1765 
    1766 \paragraph{Case 1: thread $\alpha$ goes first.} In this case, the problem is that monitor @A@ needs to be passed to thread $\beta$ when thread $\alpha$ is done with it.
    1767 \paragraph{Case 2: thread $\beta$ goes first.} In this case, the problem is that monitor @B@ needs to be retained and passed to thread $\alpha$ along with monitor @A@, which can be done directly or possibly using thread $\beta$ as an intermediate.
    1768 \\
    1769 
    1770 Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order.
    1771 However, regardless of the answer, users can move line \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{f:dependency}.
    1772 
    1773 In both cases, the threads need to be able to distinguish, on a per monitor basis, which ones need to be released and which ones need to be transferred, which means knowing when to release a group becomes complex and inefficient (see next section) and therefore effectively precludes this approach.
    1774 
    1775 
    1776 \subsubsection{Dependency graphs}
    1777 
    1778 \begin{figure}
    1779 \begin{multicols}{3}
    1780 Thread $\alpha$
    1781 \begin{cfa}[numbers=left, firstnumber=1]
    1782 acquire A
    1783         acquire A & B
    1784                 wait A & B
    1785         release A & B
    1786 release A
    1787 \end{cfa}
    1788 \columnbreak
    1789 Thread $\gamma$
    1790 \begin{cfa}[numbers=left, firstnumber=6, escapechar=|]
    1791 acquire A
    1792         acquire A & B
    1793                 |\label{line:signal-ab}|signal A & B
    1794         |\label{line:release-ab}|release A & B
    1795         |\label{line:signal-a}|signal A
    1796 |\label{line:release-a}|release A
    1797 \end{cfa}
    1798 \columnbreak
    1799 Thread $\beta$
    1800 \begin{cfa}[numbers=left, firstnumber=12, escapechar=|]
    1801 acquire A
    1802         wait A
    1803 |\label{line:release-aa}|release A
    1804 \end{cfa}
    1805 \end{multicols}
    1806 \begin{cfa}[caption={Pseudo-code for the three thread example.},label={f:dependency}]
    1807 \end{cfa}
    1808 \begin{center}
    1809 \input{dependency}
    1810 \end{center}
    1811 \caption{Dependency graph of the statements in listing \ref{f:dependency}}
    1812 \label{fig:dependency}
    1813 \end{figure}
    1814 
    1815 In listing \ref{f:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
    1816 If ownership of both monitors is transferred to the waiter when the signaller releases @A & B@ and then the waiter transfers back ownership of @A@ back to the signaller when it releases it, then the problem is solved (@B@ is no longer in use at this point).
    1817 Dynamically finding the correct order is therefore the second possible solution.
    1818 The problem is effectively resolving a dependency graph of ownership requirements.
    1819 Here even the simplest of code snippets requires two transfers and has a super-linear complexity.
    1820 This complexity can be seen in listing \ref{f:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.
    1821 Furthermore, the presence of multiple solutions for ownership transfer can cause deadlock problems if a specific solution is not consistently picked; In the same way that multiple lock acquiring order can cause deadlocks.
    1822 \begin{figure}
    1823 \begin{multicols}{2}
    1824 \begin{cfa}
    1825 acquire A
    1826         acquire B
    1827                 acquire C
    1828                         wait A & B & C
    1829                 release C
    1830         release B
    1831 release A
    1832 \end{cfa}
    1833 
    1834 \columnbreak
    1835 
    1836 \begin{cfa}
    1837 acquire A
    1838         acquire B
    1839                 acquire C
    1840                         signal A & B & C
    1841                 release C
    1842         release B
    1843 release A
    1844 \end{cfa}
    1845 \end{multicols}
    1846 \begin{cfa}[caption={Extension to three monitors of listing \ref{f:int-bulk-cfa}},label={f:explosion}]
    1847 \end{cfa}
    1848 \end{figure}
    1849 
    1850 Given the three threads example in listing \ref{f:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (\eg $\alpha1$ must happen before $\alpha2$).
    1851 The extra challenge is that this dependency graph is effectively post-mortem, but the runtime system needs to be able to build and solve these graphs as the dependencies unfold.
    1852 Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one.
    1853 \end{comment}
    1854 
    1855 
    1856 \begin{comment}
    1857 \section{External scheduling} \label{extsched}
    1858 
    1859 \begin{table}
    1860 \begin{tabular}{|c|c|c|}
    1861 Internal Scheduling & External Scheduling & Go\\
    1862 \hline
    1863 \begin{uC++}[tabsize=3]
    1864 _Monitor Semaphore {
    1865         condition c;
    1866         bool inUse;
    1867 public:
    1868         void P() {
    1869                 if(inUse)
    1870                         wait(c);
    1871                 inUse = true;
    1872         }
    1873         void V() {
    1874                 inUse = false;
    1875                 signal(c);
    1876         }
    1877 }
    1878 \end{uC++}&\begin{uC++}[tabsize=3]
    1879 _Monitor Semaphore {
    1880 
    1881         bool inUse;
    1882 public:
    1883         void P() {
    1884                 if(inUse)
    1885                         _Accept(V);
    1886                 inUse = true;
    1887         }
    1888         void V() {
    1889                 inUse = false;
    1890 
    1891         }
    1892 }
    1893 \end{uC++}&\begin{Go}[tabsize=3]
    1894 type MySem struct {
    1895         inUse bool
    1896         c     chan bool
    1897 }
    1898 
    1899 // acquire
    1900 func (s MySem) P() {
    1901         if s.inUse {
    1902                 select {
    1903                 case <-s.c:
    1904                 }
    1905         }
    1906         s.inUse = true
    1907 }
    1908 
    1909 // release
    1910 func (s MySem) V() {
    1911         s.inUse = false
    1912 
    1913         // This actually deadlocks
    1914         // when single thread
    1915         s.c <- false
    1916 }
    1917 \end{Go}
    1918 \end{tabular}
    1919 \caption{Different forms of scheduling.}
    1920 \label{tbl:sched}
    1921 \end{table}
    1922 
    1923 For the @P@ member above using internal scheduling, the call to @wait@ only guarantees that @V@ is the last routine to access the monitor, allowing a third routine, say @isInUse()@, acquire mutual exclusion several times while routine @P@ is waiting.
    1924 On the other hand, external scheduling guarantees that while routine @P@ is waiting, no other routine than @V@ can acquire the monitor.
    1925 \end{comment}
    1926 
    19271770
    19281771\subsection{Loose Object Definitions}
     
    19731816The accepted list is a variable-sized array of accepted routine pointers, so the single instruction bitmask comparison is replaced by dereferencing a pointer followed by a linear search.
    19741817
    1975 \begin{comment}
    1976 \begin{figure}
    1977 \begin{cfa}[caption={Example of nested external scheduling},label={f:nest-ext}]
    1978 monitor M {};
    1979 void foo( M & mutex a ) {}
    1980 void bar( M & mutex b ) {
    1981         // Nested in the waitfor(bar, c) call
    1982         waitfor(foo, b);
    1983 }
    1984 void baz( M & mutex c ) {
    1985         waitfor(bar, c);
    1986 }
    1987 
    1988 \end{cfa}
    1989 \end{figure}
    1990 
    1991 Note that in the right picture, tasks need to always keep track of the monitors associated with mutex routines, and the routine mask needs to have both a routine pointer and a set of monitors, as is discussed in the next section.
    1992 These details are omitted from the picture for the sake of simplicity.
    1993 
    1994 At this point, a decision must be made between flexibility and performance.
    1995 Many design decisions in \CFA achieve both flexibility and performance, for example polymorphic routines add significant flexibility but inlining them means the optimizer can easily remove any runtime cost.
    1996 Here, however, the cost of flexibility cannot be trivially removed.
    1997 In the end, the most flexible approach has been chosen since it allows users to write programs that would otherwise be  hard to write.
    1998 This decision is based on the assumption that writing fast but inflexible locks is closer to a solved problem than writing locks that are as flexible as external scheduling in \CFA.
    1999 \end{comment}
    2000 
    20011818
    20021819\subsection{Multi-Monitor Scheduling}
     
    20091826void f( M & mutex m1 );
    20101827void g( M & mutex m1, M & mutex m2 ) {
    2011         waitfor( f );                                                   $\C{// pass m1 or m2 to f?}$
     1828        waitfor( f );                                                   $\C{\color{red}// pass m1 or m2 to f?}$
    20121829}
    20131830\end{cfa}
    20141831The solution is for the programmer to disambiguate:
    20151832\begin{cfa}
    2016         waitfor( f, m2 );                                               $\C{// wait for call to f with argument m2}$
    2017 \end{cfa}
    2018 Routine @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@).
     1833        waitfor( f, m2 );                                               $\C{\color{red}// wait for call to f with argument m2}$
     1834\end{cfa}
     1835Routine @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@.
    20191836This behaviour can be extended to the multi-monitor @waitfor@ statement.
    20201837\begin{cfa}
     
    20221839void f( M & mutex m1, M & mutex m2 );
    20231840void g( M & mutex m1, M & mutex m2 ) {
    2024         waitfor( f, m1, m2 );                                   $\C{// wait for call to f with arguments m1 and m2}$
     1841        waitfor( f, m1, m2 );                                   $\C{\color{red}// wait for call to f with arguments m1 and m2}$
    20251842}
    20261843\end{cfa}
    20271844Again, the set of monitors passed to the @waitfor@ statement must be entirely contained in the set of monitors already acquired by accepting routine.
    20281845
    2029 An important behaviour to note is when a set of monitors only match partially:
    2030 \begin{cfa}
    2031 mutex struct A {};
    2032 mutex struct B {};
    2033 void g( A & mutex m1, B & mutex m2 ) {
     1846Note, for internal and external scheduling with multiple monitors, a signalling or accepting thread must match exactly, \ie partial matching results in waiting.
     1847\begin{cquote}
     1848\lstDeleteShortInline@%
     1849\begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
     1850\begin{cfa}
     1851monitor M1 {} m11, m12;
     1852monitor M2 {} m2;
     1853condition c;
     1854void f( M1 & mutex m1, M2 & mutex m2 ) {
     1855        signal( c );
     1856}
     1857void g( M1 & mutex m1, M2 & mutex m2 ) {
     1858        wait( c );
     1859}
     1860g( `m11`, m2 ); // block on accept
     1861f( `m12`, m2 ); // cannot fulfil
     1862\end{cfa}
     1863&
     1864\begin{cfa}
     1865monitor M1 {} m11, m12;
     1866monitor M2 {} m2;
     1867
     1868void f( M1 & mutex m1, M2 & mutex m2 ) {
     1869
     1870}
     1871void g( M1 & mutex m1, M2 & mutex m2 ) {
    20341872        waitfor( f, m1, m2 );
    20351873}
    2036 A a1, a2;
    2037 B b;
    2038 void foo() {
    2039         g( a1, b ); // block on accept
    2040 }
    2041 void bar() {
    2042         f( a2, b ); // fulfill cooperation
    2043 }
    2044 \end{cfa}
    2045 While the equivalent can happen when using internal scheduling, the fact that conditions are specific to a set of monitors means that users have to use two different condition variables.
    2046 In both cases, partially matching monitor sets does not wakeup the waiting thread.
    2047 It is also important to note that in the case of external scheduling the order of parameters is irrelevant; @waitfor(f,a,b)@ and @waitfor(f,b,a)@ are indistinguishable waiting condition.
    2048 
    2049 
    2050 \subsection{\protect\lstinline|waitfor| Semantics}
    2051 
    2052 Syntactically, the @waitfor@ statement takes a routine identifier and a set of monitors.
    2053 While the set of monitors can be any list of expressions, the routine name is more restricted because the compiler validates at compile time the validity of the routine type and the parameters used with the @waitfor@ statement.
    2054 It checks that the set of monitors passed in matches the requirements for a routine call.
    2055 Figure~\ref{f:waitfor} shows various usages of the waitfor statement and which are acceptable.
    2056 The choice of the routine type is made ignoring any non-@mutex@ parameter.
    2057 One limitation of the current implementation is that it does not handle overloading, but overloading is possible.
     1874g( `m11`, m2 ); // block on accept
     1875f( `m12`, m2 ); // cannot fulfil
     1876\end{cfa}
     1877\end{tabular}
     1878\lstMakeShortInline@%
     1879\end{cquote}
     1880
     1881
     1882\subsection{Extended \protect\lstinline@waitfor@}
     1883
     1884The 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.
     1885\begin{cfa}
     1886`when` ( $\emph{conditional-expression}$ )      $\C{// optional guard}$
     1887        waitfor( $\emph{mutex-member-name}$ )
     1888                $\emph{statement}$                                      $\C{// action after call}$
     1889`or` `when` ( $\emph{conditional-expression}$ ) $\C{// optional guard}$
     1890        waitfor( $\emph{mutex-member-name}$ )
     1891                $\emph{statement}$                                      $\C{// action after call}$
     1892`or`    ...                                                                     $\C{// list of waitfor clauses}$
     1893`when` ( $\emph{conditional-expression}$ )      $\C{// optional guard}$
     1894        `timeout`                                                               $\C{// optional terminating timeout clause}$
     1895                $\emph{statement}$                                      $\C{// action after timeout}$
     1896`when` ( $\emph{conditional-expression}$ )      $\C{// optional guard}$
     1897        `else`                                                                  $\C{// optional terminating clause}$
     1898                $\emph{statement}$                                      $\C{// action when no immediate calls}$
     1899\end{cfa}
     1900For a @waitfor@ clause to be executed, its @when@ must be true and an outstanding call to its corresponding member(s) must exist.
     1901The \emph{conditional-expression} of a @when@ may call a routine, but the routine must not block or context switch.
     1902If there are several mutex calls that can be accepted, selection occurs top-to-bottom in the @waitfor@ clauses versus non-deterministically.
     1903If 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.
     1904If 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.
     1905Hence, the terminating @else@ clause allows a conditional attempt to accept a call without blocking.
     1906If 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.
     1907In all cases, the statement following is executed \emph{after} a clause is executed to know which of the clauses executed.
     1908
     1909A group of conditional @waitfor@ clauses is \emph{not} the same as a group of @if@ statements, e.g.:
     1910\begin{cfa}
     1911if ( C1 ) waitfor( mem1 );                       when ( C1 ) waitfor( mem1 );
     1912else if ( C2 ) waitfor( mem2 );         or when ( C2 ) waitfor( mem2 );
     1913\end{cfa}
     1914The left example accepts only @mem1@ if @C1@ is true or only @mem2@ if @C2@ is true.
     1915The right example accepts either @mem1@ or @mem2@ if @C1@ and @C2@ are true.
     1916
     1917An interesting use of @waitfor@ is accepting the @mutex@ destructor to know when an object deallocated.
     1918\begin{cfa}
     1919void insert( Buffer(T) & mutex buffer, T elem ) with( buffer ) {
     1920        if ( count == BufferSize )
     1921                waitfor( remove, buffer ) {
     1922                        elements[back] = elem;
     1923                        back = ( back + 1 ) % BufferSize;
     1924                        count += 1;
     1925                } or `waitfor( ^?{}, buffer )` throw insertFail;
     1926}
     1927\end{cfa}
     1928However, the @waitfor@ semantics do not work, since using an object after its destructor is called is undefined.
     1929Therefore, 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 deallocates the object.
     1930Accepting the destructor is an idiomatic way to terminate a thread in \CFA.
     1931
     1932
     1933\subsection{\protect\lstinline@mutex@ Threads}
     1934
     1935Threads in \CFA are monitors, so all monitor features are available when using threads.
     1936Figure~\ref{f:pingpong} shows an example of two threads calling and accepting calls from each other in a cycle.
     1937Note, both ping/pong threads are globally declared, @pi@/@po@, and hence, start (and possibly complete) before the program starts.
     1938
    20581939\begin{figure}
    2059 \begin{cfa}[caption={Various correct and incorrect uses of the waitfor statement},label={f:waitfor}]
    2060 monitor A{};
    2061 monitor B{};
    2062 
    2063 void f1( A & mutex );
    2064 void f2( A & mutex, B & mutex );
    2065 void f3( A & mutex, int );
    2066 void f4( A & mutex, int );
    2067 void f4( A & mutex, double );
    2068 
    2069 void foo( A & mutex a1, A & mutex a2, B & mutex b1, B & b2 ) {
    2070         A * ap = & a1;
    2071         void (*fp)( A & mutex ) = f1;
    2072 
    2073         waitfor(f1, a1);     // Correct : 1 monitor case
    2074         waitfor(f2, a1, b1); // Correct : 2 monitor case
    2075         waitfor(f3, a1);     // Correct : non-mutex arguments are ignored
    2076         waitfor(f1, *ap);    // Correct : expression as argument
    2077 
    2078         waitfor(f1, a1, b1); // Incorrect : Too many mutex arguments
    2079         waitfor(f2, a1);     // Incorrect : Too few mutex arguments
    2080         waitfor(f2, a1, a2); // Incorrect : Mutex arguments don't match
    2081         waitfor(f1, 1);      // Incorrect : 1 not a mutex argument
    2082         waitfor(f9, a1);     // Incorrect : f9 routine does not exist
    2083         waitfor(*fp, a1 );   // Incorrect : fp not an identifier
    2084         waitfor(f4, a1);     // Incorrect : f4 ambiguous
    2085 
    2086         waitfor(f2, a1, b2); // Undefined behaviour : b2 not mutex
    2087 }
    2088 \end{cfa}
     1940\lstDeleteShortInline@%
     1941\begin{cquote}
     1942\begin{cfa}
     1943thread Ping {} pi;
     1944thread Pong {} po;
     1945void ping( Ping & mutex ) {}
     1946void pong( Pong & mutex ) {}
     1947int main() {}
     1948\end{cfa}
     1949\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}}
     1950\begin{cfa}
     1951void main( Ping & pi ) {
     1952        for ( int i = 0; i < 10; i += 1 ) {
     1953                `waitfor( ping, pi );`
     1954                `pong( po );`
     1955        }
     1956}
     1957\end{cfa}
     1958&
     1959\begin{cfa}
     1960void main( Pong & po ) {
     1961        for ( int i = 0; i < 10; i += 1 ) {
     1962                `ping( pi );`
     1963                `waitfor( pong, po );`
     1964        }
     1965}
     1966\end{cfa}
     1967\end{tabular}
     1968\lstMakeShortInline@%
     1969\end{cquote}
     1970\caption{Threads ping/pong using external scheduling}
     1971\label{f:pingpong}
    20891972\end{figure}
    20901973
    2091 Finally, for added flexibility, \CFA supports constructing a complex @waitfor@ statement using the @or@, @timeout@ and @else@.
    2092 Indeed, multiple @waitfor@ clauses can be chained together using @or@; this chain forms a single statement that uses baton pass to any routine that fits one of the routine+monitor set passed in.
    2093 To enable users to tell which accepted routine executed, @waitfor@s are followed by a statement (including the null statement @;@) or a compound statement, which is executed after the clause is triggered.
    2094 A @waitfor@ chain can also be followed by a @timeout@, to signify an upper bound on the wait, or an @else@, to signify that the call should be non-blocking, which checks for a matching routine call already arrived and otherwise continues.
    2095 Any and all of these clauses can be preceded by a @when@ condition to dynamically toggle the accept clauses on or off based on some current state.
    2096 Figure~\ref{f:waitfor2} demonstrates several complex masks and some incorrect ones.
     1974\section{Parallelism}
     1975
     1976Historically, computer performance was about processor speeds.
     1977However, with heat dissipation being a direct consequence of speed increase, parallelism has become the new source for increased performance~\cite{Sutter05, Sutter05b}.
     1978Now, high-performance applications must care about parallelism, which requires concurrency.
     1979The lowest-level approach of parallelism is to use \newterm{kernel threads} in combination with semantics like @fork@, @join@, \etc.
     1980However, kernel threads are better as an implementation tool because of complexity and high cost.
     1981Therefore, different abstractions are layered onto kernel threads to simplify them.
     1982
     1983
     1984\subsection{User Threads with Preemption}
     1985
     1986A direct improvement on kernel threads is user threads, \eg Erlang~\cite{Erlang} and \uC~\cite{uC++book}.
     1987This approach provides an interface that matches the language paradigms, more control over concurrency in the language runtime, and an abstract (and portable) interface to the underlying kernel threads across operating systems.
     1988In many cases, user threads can be used on a much larger scale (100,000 threads).
     1989Like kernel threads, user threads support preemption, which maximizes nondeterminism, but introduces concurrency errors: race, livelock, starvation, and deadlock.
     1990\CFA adopts user-threads as they represent the truest realization of concurrency and can build the following approaches and more, \eg actors~\cite{Actors}.
     1991
     1992
     1993\subsection{User Threads without Preemption (Fiber)}
     1994\label{s:fibers}
     1995
     1996A variant of user thread is \newterm{fibers}, which removes preemption, \eg Go~\cite{Go}.
     1997Like 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.
     1998However, preemption is necessary for concurrency that relies on spinning, so there are a class of problems that cannot be programmed without preemption.
     1999
     2000
     2001\subsection{Thread Pools}
     2002
     2003In contrast to direct threading is indirect \newterm{thread pools}, where small jobs (work units) are insert into a work pool for execution.
     2004If the jobs are dependent, \ie interact, there is an implicit/explicit dependency graph that ties them together.
     2005While removing direct concurrency, and hence the amount of context switching, thread pools significantly limit the interaction that can occur among jobs.
     2006Indeed, jobs should not block because that also block the underlying thread, which effectively means the CPU utilization, and therefore throughput, suffers.
     2007While 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.
     2008As well, concurrency errors return, which threads pools are suppose to mitigate.
     2009The gold standard for thread pool is Intel's TBB library~\cite{TBB}.
     2010
     2011
     2012\section{\protect\CFA Runtime Structure}
     2013
     2014Figure~\ref{f:RunTimeStructure} illustrates the runtime structure of a \CFA program.
     2015In addition to the new kinds of objects introduced by \CFA, there are two more runtime entities used to control parallel execution.
     2016An executing thread is illustrated by its containment in a processor.
    20972017
    20982018\begin{figure}
    2099 \lstset{language=CFA,deletedelim=**[is][]{`}{`}}
    2100 \begin{cfa}
    2101 monitor A{};
    2102 
    2103 void f1( A & mutex );
    2104 void f2( A & mutex );
    2105 
    2106 void foo( A & mutex a, bool b, int t ) {
    2107         waitfor(f1, a);                                                 $\C{// Correct : blocking case}$
    2108 
    2109         waitfor(f1, a) {                                                $\C{// Correct : block with statement}$
    2110                 sout | "f1" | endl;
    2111         }
    2112         waitfor(f1, a) {                                                $\C{// Correct : block waiting for f1 or f2}$
    2113                 sout | "f1" | endl;
    2114         } or waitfor(f2, a) {
    2115                 sout | "f2" | endl;
    2116         }
    2117         waitfor(f1, a); or else;                                $\C{// Correct : non-blocking case}$
    2118 
    2119         waitfor(f1, a) {                                                $\C{// Correct : non-blocking case}$
    2120                 sout | "blocked" | endl;
    2121         } or else {
    2122                 sout | "didn't block" | endl;
    2123         }
    2124         waitfor(f1, a) {                                                $\C{// Correct : block at most 10 seconds}$
    2125                 sout | "blocked" | endl;
    2126         } or timeout( 10`s) {
    2127                 sout | "didn't block" | endl;
    2128         }
    2129         // Correct : block only if b == true if b == false, don't even make the call
    2130         when(b) waitfor(f1, a);
    2131 
    2132         // Correct : block only if b == true if b == false, make non-blocking call
    2133         waitfor(f1, a); or when(!b) else;
    2134 
    2135         // Correct : block only of t > 1
    2136         waitfor(f1, a); or when(t > 1) timeout(t); or else;
    2137 
    2138         // Incorrect : timeout clause is dead code
    2139         waitfor(f1, a); or timeout(t); or else;
    2140 
    2141         // Incorrect : order must be waitfor [or waitfor... [or timeout] [or else]]
    2142         timeout(t); or waitfor(f1, a); or else;
    2143 }
    2144 \end{cfa}
    2145 \caption{Correct and incorrect uses of the or, else, and timeout clause around a waitfor statement}
    2146 \label{f:waitfor2}
     2019\centering
     2020\input{RunTimeStructure}
     2021\caption{\CFA Runtime Structure}
     2022\label{f:RunTimeStructure}
    21472023\end{figure}
    21482024
    21492025
    2150 \subsection{Waiting For The Destructor}
    2151 
    2152 An interesting use for the @waitfor@ statement is destructor semantics.
    2153 Indeed, the @waitfor@ statement can accept any @mutex@ routine, which includes the destructor (see section \ref{data}).
    2154 However, with the semantics discussed until now, waiting for the destructor does not make any sense, since using an object after its destructor is called is undefined behaviour.
    2155 The simplest approach is to disallow @waitfor@ on a destructor.
    2156 However, a more expressive approach is to flip ordering of execution when waiting for the destructor, meaning that waiting for the destructor allows the destructor to run after the current @mutex@ routine, similarly to how a condition is signalled.
    2157 \begin{figure}
    2158 \begin{cfa}[caption={Example of an executor which executes action in series until the destructor is called.},label={f:dtor-order}]
    2159 monitor Executer {};
    2160 struct  Action;
    2161 
    2162 void ^?{}   (Executer & mutex this);
    2163 void execute(Executer & mutex this, const Action & );
    2164 void run    (Executer & mutex this) {
    2165         while(true) {
    2166                    waitfor(execute, this);
    2167                 or waitfor(^?{}   , this) {
    2168                         break;
    2169                 }
    2170         }
    2171 }
    2172 \end{cfa}
    2173 \end{figure}
    2174 For example, listing \ref{f:dtor-order} shows an example of an executor with an infinite loop, which waits for the destructor to break out of this loop.
    2175 Switching the semantic meaning introduces an idiomatic way to terminate a task and/or wait for its termination via destruction.
    2176 
    2177 
    2178 \section{Parallelism}
    2179 
    2180 Historically, computer performance was about processor speeds and instruction counts.
    2181 However, with heat dissipation being a direct consequence of speed increase, parallelism has become the new source for increased performance~\cite{Sutter05, Sutter05b}.
    2182 In this decade, it is no longer reasonable to create a high-performance application without caring about parallelism.
    2183 Indeed, parallelism is an important aspect of performance and more specifically throughput and hardware utilization.
    2184 The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like @fork@, @join@, \etc.
    2185 However, since these have significant costs and limitations, \textbf{kthread} are now mostly used as an implementation tool rather than a user oriented one.
    2186 There are several alternatives to solve these issues that all have strengths and weaknesses.
    2187 While there are many variations of the presented paradigms, most of these variations do not actually change the guarantees or the semantics, they simply move costs in order to achieve better performance for certain workloads.
    2188 
    2189 
    2190 \section{Paradigms}
    2191 
    2192 
    2193 \subsection{User-Level Threads}
    2194 
    2195 A direct improvement on the \textbf{kthread} approach is to use \textbf{uthread}.
    2196 These threads offer most of the same features that the operating system already provides but can be used on a much larger scale.
    2197 This approach is the most powerful solution as it allows all the features of multithreading, while removing several of the more expensive costs of kernel threads.
    2198 The downside is that almost none of the low-level threading problems are hidden; users still have to think about data races, deadlocks and synchronization issues.
    2199 These issues can be somewhat alleviated by a concurrency toolkit with strong guarantees, but the parallelism toolkit offers very little to reduce complexity in itself.
    2200 
    2201 Examples of languages that support \textbf{uthread} are Erlang~\cite{Erlang} and \uC~\cite{uC++book}.
    2202 
    2203 
    2204 \subsection{Fibers : User-Level Threads Without Preemption} \label{fibers}
    2205 
    2206 A popular variant of \textbf{uthread} is what is often referred to as \textbf{fiber}.
    2207 However, \textbf{fiber} do not present meaningful semantic differences with \textbf{uthread}.
    2208 The significant difference between \textbf{uthread} and \textbf{fiber} is the lack of \textbf{preemption} in the latter.
    2209 Advocates of \textbf{fiber} list their high performance and ease of implementation as major strengths, but the performance difference between \textbf{uthread} and \textbf{fiber} is controversial, and the ease of implementation, while true, is a weak argument in the context of language design.
    2210 Therefore this proposal largely ignores fibers.
    2211 
    2212 An example of a language that uses fibers is Go~\cite{Go}
    2213 
    2214 
    2215 \subsection{Jobs and Thread Pools}
    2216 
    2217 An approach on the opposite end of the spectrum is to base parallelism on \textbf{pool}.
    2218 Indeed, \textbf{pool} offer limited flexibility but at the benefit of a simpler user interface.
    2219 In \textbf{pool} based systems, users express parallelism as units of work, called jobs, and a dependency graph (either explicit or implicit) that ties them together.
    2220 This approach means users need not worry about concurrency but significantly limit the interaction that can occur among jobs.
    2221 Indeed, any \textbf{job} that blocks also block the underlying worker, which effectively means the CPU utilization, and therefore throughput, suffers noticeably.
    2222 It can be argued that a solution to this problem is to use more workers than available cores.
    2223 However, unless the number of jobs and the number of workers are comparable, having a significant number of blocked jobs always results in idles cores.
    2224 
    2225 The gold standard of this implementation is Intel's TBB library~\cite{TBB}.
    2226 
    2227 
    2228 \subsection{Paradigm Performance}
    2229 
    2230 While the choice between the three paradigms listed above may have significant performance implications, it is difficult to pin down the performance implications of choosing a model at the language level.
    2231 Indeed, in many situations one of these paradigms may show better performance but it all strongly depends on the workload.
    2232 Having a large amount of mostly independent units of work to execute almost guarantees equivalent performance across paradigms and that the \textbf{pool}-based system has the best efficiency thanks to the lower memory overhead (\ie no thread stack per job).
    2233 However, interactions among jobs can easily exacerbate contention.
    2234 User-level threads allow fine-grain context switching, which results in better resource utilization, but a context switch is more expensive and the extra control means users need to tweak more variables to get the desired performance.
    2235 Finally, if the units of uninterrupted work are large, enough the paradigm choice is largely amortized by the actual work done.
    2236 
    2237 
    2238 \section{The \protect\CFA\ Kernel : Processors, Clusters and Threads}\label{kernel}
    2239 
    2240 A \textbf{cfacluster} is a group of \textbf{kthread} executed in isolation. \textbf{uthread} are scheduled on the \textbf{kthread} of a given \textbf{cfacluster}, allowing organization between \textbf{uthread} and \textbf{kthread}.
    2241 It is important that \textbf{kthread} belonging to a same \textbf{cfacluster} have homogeneous settings, otherwise migrating a \textbf{uthread} from one \textbf{kthread} to the other can cause issues.
    2242 A \textbf{cfacluster} also offers a pluggable scheduler that can optimize the workload generated by the \textbf{uthread}.
    2243 
    2244 \textbf{cfacluster} have not been fully implemented in the context of this paper.
    2245 Currently \CFA only supports one \textbf{cfacluster}, the initial one.
    2246 
    2247 
    2248 \subsection{Future Work: Machine Setup}\label{machine}
    2249 
    2250 While this was not done in the context of this paper, another important aspect of clusters is affinity.
    2251 While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heterogeneous setups.
    2252 For example, a system using \textbf{numa} configurations may benefit from users being able to tie clusters and/or kernel threads to certain CPU cores.
    2253 OS support for CPU affinity is now common~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which means it is both possible and desirable for \CFA to offer an abstraction mechanism for portable CPU affinity.
    2254 
    2255 
    2256 \subsection{Paradigms}\label{cfaparadigms}
    2257 
    2258 Given these building blocks, it is possible to reproduce all three of the popular paradigms.
    2259 Indeed, \textbf{uthread} is the default paradigm in \CFA.
    2260 However, disabling \textbf{preemption} on a cluster means threads effectively become fibers.
    2261 Since several \textbf{cfacluster} with different scheduling policy can coexist in the same application, this allows \textbf{fiber} and \textbf{uthread} to coexist in the runtime of an application.
    2262 Finally, it is possible to build executors for thread pools from \textbf{uthread} or \textbf{fiber}, which includes specialized jobs like actors~\cite{Actors}.
    2263 
    2264 
    2265 \section{Behind the Scenes}
    2266 
    2267 There are several challenges specific to \CFA when implementing concurrency.
    2268 These challenges are a direct result of bulk acquire and loose object definitions.
    2269 These two constraints are the root cause of most design decisions in the implementation.
    2270 Furthermore, to avoid contention from dynamically allocating memory in a concurrent environment, the internal-scheduling design is (almost) entirely free of mallocs.
    2271 This approach avoids the chicken and egg problem~\cite{Chicken} of having a memory allocator that relies on the threading system and a threading system that relies on the runtime.
    2272 This extra goal means that memory management is a constant concern in the design of the system.
    2273 
    2274 The main memory concern for concurrency is queues.
    2275 All blocking operations are made by parking threads onto queues and all queues are designed with intrusive nodes, where each node has pre-allocated link fields for chaining, to avoid the need for memory allocation.
    2276 Since several concurrency operations can use an unbound amount of memory (depending on bulk acquire), statically defining information in the intrusive fields of threads is insufficient.The only way to use a variable amount of memory without requiring memory allocation is to pre-allocate large buffers of memory eagerly and store the information in these buffers.
    2277 Conveniently, the call stack fits that description and is easy to use, which is why it is used heavily in the implementation of internal scheduling, particularly variable-length arrays.
    2278 Since stack allocation is based on scopes, the first step of the implementation is to identify the scopes that are available to store the information, and which of these can have a variable-length array.
    2279 The threads and the condition both have a fixed amount of memory, while @mutex@ routines and blocking calls allow for an unbound amount, within the stack size.
    2280 
    2281 Note that since the major contributions of this paper are extending monitor semantics to bulk acquire and loose object definitions, any challenges that are not resulting of these characteristics of \CFA are considered as solved problems and therefore not discussed.
    2282 
    2283 
    2284 \section{Mutex Routines}
    2285 
    2286 The first step towards the monitor implementation is simple @mutex@ routines.
    2287 In the single monitor case, mutual-exclusion is done using the entry/exit procedure in listing \ref{f:entry1}.
    2288 The entry/exit procedures do not have to be extended to support multiple monitors.
    2289 Indeed it is sufficient to enter/leave monitors one-by-one as long as the order is correct to prevent deadlock~\cite{Havender68}.
    2290 In \CFA, ordering of monitor acquisition relies on memory ordering.
    2291 This approach is sufficient because all objects are guaranteed to have distinct non-overlapping memory layouts and mutual-exclusion for a monitor is only defined for its lifetime, meaning that destroying a monitor while it is acquired is undefined behaviour.
    2292 When a mutex call is made, the concerned monitors are aggregated into a variable-length pointer array and sorted based on pointer values.
     2026\subsection{Cluster}
     2027\label{s:RuntimeStructureCluster}
     2028
     2029A \newterm{cluster} is a collection of threads and virtual processors (abstraction a kernel thread) that execute the threads (like a virtual machine).
     2030The purpose of a cluster is to control the amount of parallelism that is possible among threads, plus scheduling and other execution defaults.
     2031The default cluster-scheduler is single-queue multi-server, which provides automatic load-balancing of threads on processors.
     2032However, the scheduler is pluggable, supporting alternative schedulers.
     2033If several clusters exist, both threads and virtual processors, can be explicitly migrated from one cluster to another.
     2034No automatic load balancing among clusters is performed by \CFA.
     2035
     2036When a \CFA program begins execution, it creates two clusters: system and user.
     2037The system cluster contains a processor that does not execute user threads.
     2038Instead, the system cluster handles system-related operations, such as catching errors that occur on the user clusters, printing appropriate error information, and shutting down \CFA.
     2039A user cluster is created to contain the user threads.
     2040Having all threads execute on the one cluster often maximizes utilization of processors, which minimizes runtime.
     2041However, because of limitations of the underlying operating system, special hardware, or scheduling requirements (real-time), it is sometimes necessary to have multiple clusters.
     2042
     2043
     2044\subsection{Virtual Processor}
     2045\label{s:RuntimeStructureProcessor}
     2046
     2047A virtual processor is implemented by a kernel thread (\eg UNIX process), which is subsequently scheduled for execution on a hardware processor by the underlying operating system.
     2048Programs may use more virtual processors than hardware processors.
     2049On a multiprocessor, kernel threads are distributed across the hardware processors resulting in virtual processors executing in parallel.
     2050(It is possible to use affinity to lock a virtual processor onto a particular hardware processor~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which is used when caching issues occur or for heterogeneous hardware processor.)
     2051The \CFA runtime attempts to block unused processors and unblock processors as the system load increases;
     2052balancing the workload with processors is difficult.
     2053Preemption occurs on virtual processors rather than user threads, via operating-system interrupts.
     2054Thus virtual processors execute user threads, where preemption frequency applies to a virtual processor, so preemption occurs randomly across the executed user threads.
     2055Turning off preemption transforms user threads into fibers.
     2056
     2057
     2058\subsection{Debug Kernel}
     2059
     2060There are two versions of the \CFA runtime kernel: debug and non-debug.
     2061The debugging version has many runtime checks and internal assertions, \eg stack (non-writable) guard page, and checks for stack overflow whenever context switches occur among coroutines and threads, which catches most stack overflows.
     2062After a program is debugged, the non-debugging version can be used to decrease space and increase performance.
     2063
     2064
     2065\section{Implementation}
     2066
     2067Currently, \CFA has fixed-sized stacks, where the stack size can be set at coroutine/thread creation but with no subsequent growth.
     2068Schemes exist for dynamic stack-growth, such as stack copying and chained stacks.
     2069However, stack copying requires pointer adjustment to items on the stack, which is impossible without some form of garage collection.
     2070As well, chained stacks require all modules be recompiled to use this feature, which breaks backward compatibility with existing C libraries.
     2071In the long term, it is likely C libraries will migrate to stack chaining to support concurrency, at only a minimal cost to sequential programs.
     2072Nevertheless, experience teaching \uC~\cite{CS343} shows fixed-sized stacks are rarely an issue in the most concurrent programs.
     2073
     2074A primary implementation challenge is avoiding contention from dynamically allocating memory because of bulk acquire, \eg the internal-scheduling design is (almost) free of allocations.
     2075All blocking operations are made by parking threads onto queues, therefore all queues are designed with intrusive nodes, where each node has preallocated link fields for chaining.
     2076Furthermore, several bulk-acquire operations need a variable amount of memory.
     2077This 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.
     2078
     2079In \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.
     2080When a mutex call is made, pointers to the concerned monitors are aggregated into a variable-length array and sorted.
    22932081This array persists for the entire duration of the mutual-exclusion and its ordering reused extensively.
    2294 \begin{figure}
    2295 \begin{multicols}{2}
    2296 Entry
    2297 \begin{cfa}
    2298 if monitor is free
    2299         enter
    2300 elif already own the monitor
    2301         continue
    2302 else
    2303         block
    2304 increment recursions
    2305 \end{cfa}
    2306 \columnbreak
    2307 Exit
    2308 \begin{cfa}
    2309 decrement recursion
    2310 if recursion == 0
    2311         if entry queue not empty
    2312                 wake-up thread
    2313 \end{cfa}
    2314 \end{multicols}
    2315 \begin{cfa}[caption={Initial entry and exit routine for monitors},label={f:entry1}]
    2316 \end{cfa}
    2317 \end{figure}
    2318 
    2319 
    2320 \subsection{Details: Interaction with polymorphism}
    2321 
    2322 Depending on the choice of semantics for when monitor locks are acquired, interaction between monitors and \CFA's concept of polymorphism can be more complex to support.
    2323 However, it is shown that entry-point locking solves most of the issues.
    2324 
    2325 First of all, interaction between @otype@ polymorphism (see Section~\ref{s:ParametricPolymorphism}) and monitors is impossible since monitors do not support copying.
    2326 Therefore, the main question is how to support @dtype@ polymorphism.
    2327 It is important to present the difference between the two acquiring options: \textbf{callsite-locking} and entry-point locking, \ie acquiring the monitors before making a mutex routine-call or as the first operation of the mutex routine-call.
    2328 For example:
    2329 \begin{table}
    2330 \begin{center}
    2331 \begin{tabular}{|c|c|c|}
    2332 Mutex & \textbf{callsite-locking} & \textbf{entry-point-locking} \\
    2333 call & cfa-code & cfa-code \\
    2334 \hline
    2335 \begin{cfa}[tabsize=3]
    2336 void foo(monitor& mutex a){
    2337 
    2338         // Do Work
    2339         //...
    2340 
    2341 }
    2342 
    2343 void main() {
    2344         monitor a;
    2345 
    2346         foo(a);
    2347 
    2348 }
    2349 \end{cfa} & \begin{cfa}[tabsize=3]
    2350 foo(& a) {
    2351 
    2352         // Do Work
    2353         //...
    2354 
    2355 }
    2356 
    2357 main() {
    2358         monitor a;
    2359         acquire(a);
    2360         foo(a);
    2361         release(a);
    2362 }
    2363 \end{cfa} & \begin{cfa}[tabsize=3]
    2364 foo(& a) {
    2365         acquire(a);
    2366         // Do Work
    2367         //...
    2368         release(a);
    2369 }
    2370 
    2371 main() {
    2372         monitor a;
    2373 
    2374         foo(a);
    2375 
    2376 }
    2377 \end{cfa}
    2378 \end{tabular}
    2379 \end{center}
    2380 \caption{Call-site vs entry-point locking for mutex calls}
    2381 \label{tbl:locking-site}
    2382 \end{table}
    2383 
    2384 Note the @mutex@ keyword relies on the type system, which means that in cases where a generic monitor-routine is desired, writing the mutex routine is possible with the proper trait, \eg:
    2385 \begin{cfa}
    2386 // Incorrect: T may not be monitor
    2387 forall(dtype T)
    2388 void foo(T * mutex t);
    2389 
    2390 // Correct: this routine only works on monitors (any monitor)
    2391 forall(dtype T | is_monitor(T))
    2392 void bar(T * mutex t));
    2393 \end{cfa}
    2394 
    2395 Both entry point and \textbf{callsite-locking} are feasible implementations.
    2396 The current \CFA implementation uses entry-point locking because it requires less work when using \textbf{raii}, effectively transferring the burden of implementation to object construction/destruction.
    2397 It is harder to use \textbf{raii} for call-site locking, as it does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, \ie the routine body.
    2398 For example, the monitor call can appear in the middle of an expression.
    2399 Furthermore, entry-point locking requires less code generation since any useful routine is called multiple times but there is only one entry point for many call sites.
    2400 
    2401 
    2402 \section{Threading} \label{impl:thread}
    2403 
    2404 Figure \ref{fig:system1} shows a high-level picture if the \CFA runtime system in regards to concurrency.
    2405 Each component of the picture is explained in detail in the flowing sections.
    2406 
    2407 \begin{figure}
    2408 \begin{center}
    2409 {\resizebox{\textwidth}{!}{\input{system.pstex_t}}}
    2410 \end{center}
    2411 \caption{Overview of the entire system}
    2412 \label{fig:system1}
    2413 \end{figure}
    2414 
    2415 
    2416 \subsection{Processors}
    2417 
    2418 Parallelism in \CFA is built around using processors to specify how much parallelism is desired. \CFA processors are object wrappers around kernel threads, specifically @pthread@s in the current implementation of \CFA.
    2419 Indeed, any parallelism must go through operating-system libraries.
    2420 However, \textbf{uthread} are still the main source of concurrency, processors are simply the underlying source of parallelism.
    2421 Indeed, processor \textbf{kthread} simply fetch a \textbf{uthread} from the scheduler and run it; they are effectively executers for user-threads.
    2422 The main benefit of this approach is that it offers a well-defined boundary between kernel code and user code, for example, kernel thread quiescing, scheduling and interrupt handling.
    2423 Processors internally use coroutines to take advantage of the existing context-switching semantics.
    2424 
    2425 
    2426 \subsection{Stack Management}
    2427 
    2428 One of the challenges of this system is to reduce the footprint as much as possible.
    2429 Specifically, all @pthread@s created also have a stack created with them, which should be used as much as possible.
    2430 Normally, coroutines also create their own stack to run on, however, in the case of the coroutines used for processors, these coroutines run directly on the \textbf{kthread} stack, effectively stealing the processor stack.
    2431 The exception to this rule is the Main Processor, \ie the initial \textbf{kthread} that is given to any program.
    2432 In order to respect C user expectations, the stack of the initial kernel thread, the main stack of the program, is used by the main user thread rather than the main processor, which can grow very large.
    2433 
    2434 
    2435 \subsection{Context Switching}
    2436 
    2437 As mentioned in section \ref{coroutine}, coroutines are a stepping stone for implementing threading, because they share the same mechanism for context-switching between different stacks.
    2438 To improve performance and simplicity, context-switching is implemented using the following assumption: all context-switches happen inside a specific routine call.
    2439 This assumption means that the context-switch only has to copy the callee-saved registers onto the stack and then switch the stack registers with the ones of the target coroutine/thread.
    2440 Note that the instruction pointer can be left untouched since the context-switch is always inside the same routine
    2441 Threads, however, do not context-switch between each other directly.
    2442 They context-switch to the scheduler.
    2443 This method is called a 2-step context-switch and has the advantage of having a clear distinction between user code and the kernel where scheduling and other system operations happen.
    2444 Obviously, this doubles the context-switch cost because threads must context-switch to an intermediate stack.
    2445 The alternative 1-step context-switch uses the stack of the ``from'' thread to schedule and then context-switches directly to the ``to'' thread.
    2446 However, the performance of the 2-step context-switch is still superior to a @pthread_yield@ (see section \ref{results}).
    2447 Additionally, for users in need for optimal performance, it is important to note that having a 2-step context-switch as the default does not prevent \CFA from offering a 1-step context-switch (akin to the Microsoft @SwitchToFiber@~\cite{switchToWindows} routine).
    2448 This option is not currently present in \CFA, but the changes required to add it are strictly additive.
    2449 
    2450 
    2451 \subsection{Preemption} \label{preemption}
    2452 
    2453 Finally, an important aspect for any complete threading system is preemption.
    2454 As mentioned in section \ref{basics}, preemption introduces an extra degree of uncertainty, which enables users to have multiple threads interleave transparently, rather than having to cooperate among threads for proper scheduling and CPU distribution.
    2455 Indeed, preemption is desirable because it adds a degree of isolation among threads.
    2456 In a fully cooperative system, any thread that runs a long loop can starve other threads, while in a preemptive system, starvation can still occur but it does not rely on every thread having to yield or block on a regular basis, which reduces significantly a programmer burden.
    2457 Obviously, preemption is not optimal for every workload.
    2458 However any preemptive system can become a cooperative system by making the time slices extremely large.
    2459 Therefore, \CFA uses a preemptive threading system.
    2460 
    2461 Preemption in \CFA\footnote{Note that the implementation of preemption is strongly tied with the underlying threading system.
    2462 For this reason, only the Linux implementation is cover, \CFA does not run on Windows at the time of writting} is based on kernel timers, which are used to run a discrete-event simulation.
    2463 Every processor keeps track of the current time and registers an expiration time with the preemption system.
    2464 When the preemption system receives a change in preemption, it inserts the time in a sorted order and sets a kernel timer for the closest one, effectively stepping through preemption events on each signal sent by the timer.
    2465 These timers use the Linux signal {\tt SIGALRM}, which is delivered to the process rather than the kernel-thread.
    2466 This results in an implementation problem, because when delivering signals to a process, the kernel can deliver the signal to any kernel thread for which the signal is not blocked, \ie:
     2082
     2083To 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;
     2084the corresponding registers are then restored for the other context.
     2085Note, the instruction pointer is untouched since the context switch is always inside the same routine.
     2086Unlike coroutines, threads do not context switch among each other;
     2087they context switch to the cluster scheduler.
     2088This method is a 2-step context-switch and provides a clear distinction between user and kernel code, where scheduling and other system operations happen.
     2089The 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.
     2090Experimental results (not shown) show the performance difference between these two approaches is virtually equivalent, because the 1-step performance is dominated by locking instructions to prevent a race condition.
     2091
     2092All kernel threads (@pthreads@) created a stack.
     2093Each \CFA virtual processor is implemented as a coroutine and these coroutines run directly on the kernel-thread stack, effectively stealing this stack.
     2094The exception to this rule is the program main, \ie the initial kernel thread that is given to any program.
     2095In order to respect C expectations, the stack of the initial kernel thread is used by program main rather than the main processor, allowing it to grow dynamically as in a normal C program.
     2096
     2097Finally, 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.
     2098Because preemption frequency is usually long, 1 millisecond, performance cost is negligible.
     2099
     2100Preemption is normally handled by setting a count-down timer on each virtual processor.
     2101When 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.
     2102Multiple signal handlers may be pending.
     2103When 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.
     2104The 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;
     2105therefore, all virtual processors in a cluster need to have the same signal mask.
     2106
     2107However, on UNIX systems:
    24672108\begin{quote}
    24682109A process-directed signal may be delivered to any one of the threads that does not currently have the signal blocked.
     
    24702111SIGNAL(7) - Linux Programmer's Manual
    24712112\end{quote}
    2472 For the sake of simplicity, and in order to prevent the case of having two threads receiving alarms simultaneously, \CFA programs block the {\tt SIGALRM} signal on every kernel thread except one.
    2473 
    2474 Now because of how involuntary context-switches are handled, the kernel thread handling {\tt SIGALRM} cannot also be a processor thread.
    2475 Hence, involuntary context-switching is done by sending signal {\tt SIGUSR1} to the corresponding proces\-sor and having the thread yield from inside the signal handler.
    2476 This approach effectively context-switches away from the signal handler back to the kernel and the signal handler frame is eventually unwound when the thread is scheduled again.
    2477 As a result, a signal handler can start on one kernel thread and terminate on a second kernel thread (but the same user thread).
    2478 It is important to note that signal handlers save and restore signal masks because user-thread migration can cause a signal mask to migrate from one kernel thread to another.
    2479 This behaviour is only a problem if all kernel threads, among which a user thread can migrate, differ in terms of signal masks\footnote{Sadly, official POSIX documentation is silent on what distinguishes ``async-signal-safe'' routines from other routines}.
    2480 However, since the kernel thread handling preemption requires a different signal mask, executing user threads on the kernel-alarm thread can cause deadlocks.
    2481 For this reason, the alarm thread is in a tight loop around a system call to @sigwaitinfo@, requiring very little CPU time for preemption.
    2482 One final detail about the alarm thread is how to wake it when additional communication is required (\eg on thread termination).
    2483 This unblocking is also done using {\tt SIGALRM}, but sent through the @pthread_sigqueue@.
    2484 Indeed, @sigwait@ can differentiate signals sent from @pthread_sigqueue@ from signals sent from alarms or the kernel.
    2485 
    2486 
    2487 \subsection{Scheduler}
    2488 Finally, an aspect that was not mentioned yet is the scheduling algorithm.
    2489 Currently, the \CFA scheduler uses a single ready queue for all processors, which is the simplest approach to scheduling.
    2490 Further discussion on scheduling is present in section \ref{futur:sched}.
    2491 
    2492 
    2493 \section{Internal Scheduling} \label{impl:intsched}
    2494 
    2495 The following figure is the traditional illustration of a monitor (repeated from page~\pageref{fig:ClassicalMonitor} for convenience):
    2496 
    2497 \begin{figure}
    2498 \begin{center}
    2499 {\resizebox{0.4\textwidth}{!}{\input{monitor.pstex_t}}}
    2500 \end{center}
    2501 \caption{Traditional illustration of a monitor}
    2502 \end{figure}
    2503 
    2504 This picture has several components, the two most important being the entry queue and the AS-stack.
    2505 The entry queue is an (almost) FIFO list where threads waiting to enter are parked, while the acceptor/signaller (AS) stack is a FILO list used for threads that have been signalled or otherwise marked as running next.
    2506 
    2507 For \CFA, this picture does not have support for blocking multiple monitors on a single condition.
    2508 To support bulk acquire two changes to this picture are required.
    2509 First, it is no longer helpful to attach the condition to \emph{a single} monitor.
    2510 Secondly, the thread waiting on the condition has to be separated across multiple monitors, seen in figure \ref{fig:monitor_cfa}.
    2511 
    2512 \begin{figure}
    2513 \begin{center}
    2514 {\resizebox{0.8\textwidth}{!}{\input{int_monitor}}}
    2515 \end{center}
    2516 \caption{Illustration of \CFA Monitor}
    2517 \label{fig:monitor_cfa}
    2518 \end{figure}
    2519 
    2520 This picture and the proper entry and leave algorithms (see listing \ref{f:entry2}) is the fundamental implementation of internal scheduling.
    2521 Note that when a thread is moved from the condition to the AS-stack, it is conceptually split into N pieces, where N is the number of monitors specified in the parameter list.
    2522 The thread is woken up when all the pieces have popped from the AS-stacks and made active.
    2523 In this picture, the threads are split into halves but this is only because there are two monitors.
    2524 For a specific signalling operation every monitor needs a piece of thread on its AS-stack.
    2525 
    2526 \begin{figure}
    2527 \begin{multicols}{2}
    2528 Entry
    2529 \begin{cfa}
    2530 if monitor is free
    2531         enter
    2532 elif already own the monitor
    2533         continue
    2534 else
    2535         block
    2536 increment recursion
    2537 
    2538 \end{cfa}
    2539 \columnbreak
    2540 Exit
    2541 \begin{cfa}
    2542 decrement recursion
    2543 if recursion == 0
    2544         if signal_stack not empty
    2545                 set_owner to thread
    2546                 if all monitors ready
    2547                         wake-up thread
    2548 
    2549         if entry queue not empty
    2550                 wake-up thread
    2551 \end{cfa}
    2552 \end{multicols}
    2553 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling},label={f:entry2}]
    2554 \end{cfa}
    2555 \end{figure}
    2556 
    2557 The solution discussed in \ref{s:InternalScheduling} can be seen in the exit routine of listing \ref{f:entry2}.
    2558 Basically, the solution boils down to having a separate data structure for the condition queue and the AS-stack, and unconditionally transferring ownership of the monitors but only unblocking the thread when the last monitor has transferred ownership.
    2559 This solution is deadlock safe as well as preventing any potential barging.
    2560 The data structures used for the AS-stack are reused extensively for external scheduling, but in the case of internal scheduling, the data is allocated using variable-length arrays on the call stack of the @wait@ and @signal_block@ routines.
    2561 
    2562 \begin{figure}
    2563 \begin{center}
    2564 {\resizebox{0.8\textwidth}{!}{\input{monitor_structs.pstex_t}}}
    2565 \end{center}
    2566 \caption{Data structures involved in internal/external scheduling}
    2567 \label{fig:structs}
    2568 \end{figure}
    2569 
    2570 Figure \ref{fig:structs} shows a high-level representation of these data structures.
    2571 The main idea behind them is that, a thread cannot contain an arbitrary number of intrusive ``next'' pointers for linking onto monitors.
    2572 The @condition node@ is the data structure that is queued onto a condition variable and, when signalled, the condition queue is popped and each @condition criterion@ is moved to the AS-stack.
    2573 Once all the criteria have been popped from their respective AS-stacks, the thread is woken up, which is what is shown in listing \ref{f:entry2}.
    2574 
    2575 % ======================================================================
    2576 % ======================================================================
    2577 \section{External Scheduling}
    2578 % ======================================================================
    2579 % ======================================================================
    2580 Similarly to internal scheduling, external scheduling for multiple monitors relies on the idea that waiting-thread queues are no longer specific to a single monitor, as mentioned in section \ref{extsched}.
    2581 For internal scheduling, these queues are part of condition variables, which are still unique for a given scheduling operation (\ie no signal statement uses multiple conditions).
    2582 However, in the case of external scheduling, there is no equivalent object which is associated with @waitfor@ statements.
    2583 This absence means the queues holding the waiting threads must be stored inside at least one of the monitors that is acquired.
    2584 These monitors being the only objects that have sufficient lifetime and are available on both sides of the @waitfor@ statement.
    2585 This requires an algorithm to choose which monitor holds the relevant queue.
    2586 It is also important that said algorithm be independent of the order in which users list parameters.
    2587 The proposed algorithm is to fall back on monitor lock ordering (sorting by address) and specify that the monitor that is acquired first is the one with the relevant waiting queue.
    2588 This assumes that the lock acquiring order is static for the lifetime of all concerned objects but that is a reasonable constraint.
    2589 
    2590 This algorithm choice has two consequences:
    2591 \begin{itemize}
    2592         \item The queue of the monitor with the lowest address is no longer a true FIFO queue because threads can be moved to the front of the queue.
    2593 These queues need to contain a set of monitors for each of the waiting threads.
    2594 Therefore, another thread whose set contains the same lowest address monitor but different lower priority monitors may arrive first but enter the critical section after a thread with the correct pairing.
    2595         \item The queue of the lowest priority monitor is both required and potentially unused.
    2596 Indeed, since it is not known at compile time which monitor is the monitor which has the lowest address, every monitor needs to have the correct queues even though it is possible that some queues go unused for the entire duration of the program, for example if a monitor is only used in a specific pair.
    2597 \end{itemize}
    2598 Therefore, the following modifications need to be made to support external scheduling:
    2599 \begin{itemize}
    2600         \item The threads waiting on the entry queue need to keep track of which routine they are trying to enter, and using which set of monitors.
    2601 The @mutex@ routine already has all the required information on its stack, so the thread only needs to keep a pointer to that information.
    2602         \item The monitors need to keep a mask of acceptable routines.
    2603 This mask contains for each acceptable routine, a routine pointer and an array of monitors to go with it.
    2604 It also needs storage to keep track of which routine was accepted.
    2605 Since this information is not specific to any monitor, the monitors actually contain a pointer to an integer on the stack of the waiting thread.
    2606 Note that if a thread has acquired two monitors but executes a @waitfor@ with only one monitor as a parameter, setting the mask of acceptable routines to both monitors will not cause any problems since the extra monitor will not change ownership regardless.
    2607 This becomes relevant when @when@ clauses affect the number of monitors passed to a @waitfor@ statement.
    2608         \item The entry/exit routines need to be updated as shown in listing \ref{f:entry3}.
    2609 \end{itemize}
    2610 
    2611 \subsection{External Scheduling - Destructors}
    2612 Finally, to support the ordering inversion of destructors, the code generation needs to be modified to use a special entry routine.
    2613 This routine is needed because of the storage requirements of the call order inversion.
    2614 Indeed, when waiting for the destructors, storage is needed for the waiting context and the lifetime of said storage needs to outlive the waiting operation it is needed for.
    2615 For regular @waitfor@ statements, the call stack of the routine itself matches this requirement but it is no longer the case when waiting for the destructor since it is pushed on to the AS-stack for later.
    2616 The @waitfor@ semantics can then be adjusted correspondingly, as seen in listing \ref{f:entry-dtor}
    2617 
    2618 \begin{figure}
    2619 \begin{multicols}{2}
    2620 Entry
    2621 \begin{cfa}
    2622 if monitor is free
    2623         enter
    2624 elif already own the monitor
    2625         continue
    2626 elif matches waitfor mask
    2627         push criteria to AS-stack
    2628         continue
    2629 else
    2630         block
    2631 increment recursion
    2632 \end{cfa}
    2633 \columnbreak
    2634 Exit
    2635 \begin{cfa}
    2636 decrement recursion
    2637 if recursion == 0
    2638         if signal_stack not empty
    2639                 set_owner to thread
    2640                 if all monitors ready
    2641                         wake-up thread
    2642                 endif
    2643         endif
    2644 
    2645         if entry queue not empty
    2646                 wake-up thread
    2647         endif
    2648 \end{cfa}
    2649 \end{multicols}
    2650 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={f:entry3}]
    2651 \end{cfa}
    2652 \end{figure}
    2653 
    2654 \begin{figure}
    2655 \begin{multicols}{2}
    2656 Destructor Entry
    2657 \begin{cfa}
    2658 if monitor is free
    2659         enter
    2660 elif already own the monitor
    2661         increment recursion
    2662         return
    2663 create wait context
    2664 if matches waitfor mask
    2665         reset mask
    2666         push self to AS-stack
    2667         baton pass
    2668 else
    2669         wait
    2670 increment recursion
    2671 \end{cfa}
    2672 \columnbreak
    2673 Waitfor
    2674 \begin{cfa}
    2675 if matching thread is already there
    2676         if found destructor
    2677                 push destructor to AS-stack
    2678                 unlock all monitors
    2679         else
    2680                 push self to AS-stack
    2681                 baton pass
    2682         endif
    2683         return
    2684 endif
    2685 if non-blocking
    2686         Unlock all monitors
    2687         Return
    2688 endif
    2689 
    2690 push self to AS-stack
    2691 set waitfor mask
    2692 block
    2693 return
    2694 \end{cfa}
    2695 \end{multicols}
    2696 \begin{cfa}[caption={Pseudo code for the \protect\lstinline|waitfor| routine and the \protect\lstinline|mutex| entry routine for destructors},label={f:entry-dtor}]
    2697 \end{cfa}
    2698 \end{figure}
    2699 
    2700 
    2701 % ======================================================================
    2702 % ======================================================================
    2703 \section{Putting It All Together}
    2704 % ======================================================================
    2705 % ======================================================================
    2706 
    2707 
    2708 \section{Threads As Monitors}
    2709 As it was subtly alluded in section \ref{threads}, @thread@s in \CFA are in fact monitors, which means that all monitor features are available when using threads.
    2710 For example, here is a very simple two thread pipeline that could be used for a simulator of a game engine:
    2711 \begin{figure}
    2712 \begin{cfa}[caption={Toy simulator using \protect\lstinline|thread|s and \protect\lstinline|monitor|s.},label={f:engine-v1}]
    2713 // Visualization declaration
    2714 thread Renderer {} renderer;
    2715 Frame * simulate( Simulator & this );
    2716 
    2717 // Simulation declaration
    2718 thread Simulator{} simulator;
    2719 void render( Renderer & this );
    2720 
    2721 // Blocking call used as communication
    2722 void draw( Renderer & mutex this, Frame * frame );
    2723 
    2724 // Simulation loop
    2725 void main( Simulator & this ) {
    2726         while( true ) {
    2727                 Frame * frame = simulate( this );
    2728                 draw( renderer, frame );
    2729         }
    2730 }
    2731 
    2732 // Rendering loop
    2733 void main( Renderer & this ) {
    2734         while( true ) {
    2735                 waitfor( draw, this );
    2736                 render( this );
    2737         }
    2738 }
    2739 \end{cfa}
    2740 \end{figure}
    2741 One of the obvious complaints of the previous code snippet (other than its toy-like simplicity) is that it does not handle exit conditions and just goes on forever.
    2742 Luckily, the monitor semantics can also be used to clearly enforce a shutdown order in a concise manner:
    2743 \begin{figure}
    2744 \begin{cfa}[caption={Same toy simulator with proper termination condition.},label={f:engine-v2}]
    2745 // Visualization declaration
    2746 thread Renderer {} renderer;
    2747 Frame * simulate( Simulator & this );
    2748 
    2749 // Simulation declaration
    2750 thread Simulator{} simulator;
    2751 void render( Renderer & this );
    2752 
    2753 // Blocking call used as communication
    2754 void draw( Renderer & mutex this, Frame * frame );
    2755 
    2756 // Simulation loop
    2757 void main( Simulator & this ) {
    2758         while( true ) {
    2759                 Frame * frame = simulate( this );
    2760                 draw( renderer, frame );
    2761 
    2762                 // Exit main loop after the last frame
    2763                 if( frame->is_last ) break;
    2764         }
    2765 }
    2766 
    2767 // Rendering loop
    2768 void main( Renderer & this ) {
    2769         while( true ) {
    2770                    waitfor( draw, this );
    2771                 or waitfor( ^?{}, this ) {
    2772                         // Add an exit condition
    2773                         break;
    2774                 }
    2775 
    2776                 render( this );
    2777         }
    2778 }
    2779 
    2780 // Call destructor for simulator once simulator finishes
    2781 // Call destructor for renderer to signify shutdown
    2782 \end{cfa}
    2783 \end{figure}
    2784 
    2785 \section{Fibers \& Threads}
    2786 As mentioned in section \ref{preemption}, \CFA uses preemptive threads by default but can use fibers on demand.
    2787 Currently, using fibers is done by adding the following line of code to the program~:
    2788 \begin{cfa}
    2789 unsigned int default_preemption() {
    2790         return 0;
    2791 }
    2792 \end{cfa}
    2793 This routine is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice, \ie no preemption.
    2794 However, once clusters are fully implemented, it will be possible to create fibers and \textbf{uthread} in the same system, as in listing \ref{f:fiber-uthread}
    2795 \begin{figure}
    2796 \lstset{language=CFA,deletedelim=**[is][]{`}{`}}
    2797 \begin{cfa}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={f:fiber-uthread}]
    2798 // Cluster forward declaration
    2799 struct cluster;
    2800 
    2801 // Processor forward declaration
    2802 struct processor;
    2803 
    2804 // Construct clusters with a preemption rate
    2805 void ?{}(cluster& this, unsigned int rate);
    2806 // Construct processor and add it to cluster
    2807 void ?{}(processor& this, cluster& cluster);
    2808 // Construct thread and schedule it on cluster
    2809 void ?{}(thread& this, cluster& cluster);
    2810 
    2811 // Declare two clusters
    2812 cluster thread_cluster = { 10`ms };                     // Preempt every 10 ms
    2813 cluster fibers_cluster = { 0 };                         // Never preempt
    2814 
    2815 // Construct 4 processors
    2816 processor processors[4] = {
    2817         //2 for the thread cluster
    2818         thread_cluster;
    2819         thread_cluster;
    2820         //2 for the fibers cluster
    2821         fibers_cluster;
    2822         fibers_cluster;
    2823 };
    2824 
    2825 // Declares thread
    2826 thread UThread {};
    2827 void ?{}(UThread& this) {
    2828         // Construct underlying thread to automatically
    2829         // be scheduled on the thread cluster
    2830         (this){ thread_cluster }
    2831 }
    2832 
    2833 void main(UThread & this);
    2834 
    2835 // Declares fibers
    2836 thread Fiber {};
    2837 void ?{}(Fiber& this) {
    2838         // Construct underlying thread to automatically
    2839         // be scheduled on the fiber cluster
    2840         (this.__thread){ fibers_cluster }
    2841 }
    2842 
    2843 void main(Fiber & this);
    2844 \end{cfa}
    2845 \end{figure}
    2846 
    2847 
    2848 % ======================================================================
    2849 % ======================================================================
    2850 \section{Performance Results} \label{results}
    2851 % ======================================================================
    2852 % ======================================================================
    2853 \section{Machine Setup}
    2854 Table \ref{tab:machine} shows the characteristics of the machine used to run the benchmarks.
    2855 All tests were made on this machine.
    2856 \begin{table}
    2857 \begin{center}
    2858 \begin{tabular}{| l | r | l | r |}
     2113Hence, the timer-expiry signal, which is generated \emph{externally} by the UNIX kernel to the UNIX process, is delivered to any of its UNIX subprocesses (kernel threads).
     2114To ensure each virtual processor receives its own preemption signals, a discrete-event simulation is run on one virtual processor, and only it sets timer events.
     2115Virtual processors register an expiration time with the discrete-event simulator, which is inserted in sorted order.
     2116The simulation sets the count-down timer to the value at the head of the event list, and when the timer expires, all events less than or equal to the current time are processed.
     2117Processing a preemption event sends an \emph{internal} @SIGUSR1@ signal to the registered virtual processor, which is always delivered to that processor.
     2118
     2119
     2120\section{Performance}
     2121\label{results}
     2122
     2123To verify the implementation of the \CFA runtime, a series of microbenchmarks are performed comparing \CFA with other widely used programming languages with concurrency.
     2124Table~\ref{t:machine} shows the specifications of the computer used to run the benchmarks, and the versions of the software used in the comparison.
     2125
     2126\begin{table}[h]
     2127\centering
     2128\caption{Experiment environment}
     2129\label{t:machine}
     2130
     2131\begin{tabular}{|l|r||l|r|}
    28592132\hline
    2860 Architecture            & x86\_64                       & NUMA node(s)  & 8 \\
     2133Architecture            & x86\_64                               & NUMA node(s)  & 8 \\
    28612134\hline
    2862 CPU op-mode(s)          & 32-bit, 64-bit                & Model name    & AMD Opteron\texttrademark  Processor 6380 \\
     2135CPU op-mode(s)          & 32-bit, 64-bit                & Model name    & AMD Opteron\texttrademark\ Processor 6380 \\
    28632136\hline
    2864 Byte Order                      & Little Endian                 & CPU Freq              & 2.5\si{\giga\hertz} \\
     2137Byte Order                      & Little Endian                 & CPU Freq              & 2.5 GHz \\
    28652138\hline
    2866 CPU(s)                  & 64                            & L1d cache     & \SI{16}{\kibi\byte} \\
     2139CPU(s)                          & 64                                    & L1d cache     & 16 KiB \\
    28672140\hline
    2868 Thread(s) per core      & 2                             & L1i cache     & \SI{64}{\kibi\byte} \\
     2141Thread(s) per core      & 2                                     & L1i cache     & 64 KiB \\
    28692142\hline
    2870 Core(s) per socket      & 8                             & L2 cache              & \SI{2048}{\kibi\byte} \\
     2143Core(s) per socket      & 8                                     & L2 cache              & 2048 KiB \\
    28712144\hline
    2872 Socket(s)                       & 4                             & L3 cache              & \SI{6144}{\kibi\byte} \\
     2145Socket(s)                       & 4                                     & L3 cache              & 6144 KiB \\
    28732146\hline
    28742147\hline
    2875 Operating system                & Ubuntu 16.04.3 LTS    & Kernel                & Linux 4.4-97-generic \\
     2148Operating system        & Ubuntu 16.04.3 LTS    & Kernel                & Linux 4.4-97-generic \\
    28762149\hline
    2877 Compiler                        & GCC 6.3               & Translator    & CFA 1 \\
     2150gcc                                     & 6.3                                   & \CFA                  & 1.0.0 \\
    28782151\hline
    2879 Java version            & OpenJDK-9             & Go version    & 1.9.2 \\
     2152Java                            & OpenJDK-9                     & Go                    & 1.9.2 \\
    28802153\hline
    28812154\end{tabular}
    2882 \end{center}
    2883 \caption{Machine setup used for the tests}
    2884 \label{tab:machine}
    28852155\end{table}
    28862156
    2887 \section{Micro Benchmarks}
    2888 All benchmarks are run using the same harness to produce the results, seen as the @BENCH()@ macro in the following examples.
    2889 This macro uses the following logic to benchmark the code:
    2890 \begin{cfa}
    2891 #define BENCH(run, result) \
    2892         before = gettime(); \
    2893         run; \
    2894         after  = gettime(); \
    2895         result = (after - before) / N;
    2896 \end{cfa}
    2897 The method used to get time is @clock_gettime(CLOCK_THREAD_CPUTIME_ID);@.
    2898 Each benchmark is using many iterations of a simple call to measure the cost of the call.
    2899 The specific number of iterations depends on the specific benchmark.
    2900 
    2901 \subsection{Context-Switching}
    2902 The first interesting benchmark is to measure how long context-switches take.
    2903 The simplest approach to do this is to yield on a thread, which executes a 2-step context switch.
    2904 Yielding causes the thread to context-switch to the scheduler and back, more precisely: from the \textbf{uthread} to the \textbf{kthread} then from the \textbf{kthread} back to the same \textbf{uthread} (or a different one in the general case).
    2905 In order to make the comparison fair, coroutines also execute a 2-step context-switch by resuming another coroutine which does nothing but suspending in a tight loop, which is a resume/suspend cycle instead of a yield.
    2906 Figure~\ref{f:ctx-switch} shows the code for coroutines and threads with the results in table \ref{tab:ctx-switch}.
    2907 All omitted tests are functionally identical to one of these tests.
    2908 The difference between coroutines and threads can be attributed to the cost of scheduling.
     2157All benchmarks are run using the following harness:
     2158\begin{cfa}
     2159unsigned int N = 10_000_000;
     2160#define BENCH( run, result ) Time before = getTimeNsec(); run; result = (getTimeNsec() - before) / N;
     2161\end{cfa}
     2162The method used to get time is @clock_gettime( CLOCK_REALTIME )@.
     2163Each 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.
     2164
     2165
     2166\paragraph{Context-Switching}
     2167
     2168In procedural programming, the cost of a routine call is important as modularization (refactoring) increases.
     2169(In many cases, a compiler inlines routine calls to eliminate this cost.)
     2170Similarly, when modularization extends to coroutines/tasks, the time for a context switch becomes a relevant factor.
     2171The coroutine context-switch is 2-step using resume/suspend, \ie from resumer to suspender and from suspender to resumer.
     2172The thread context switch is 2-step using yield, \ie enter and return from the runtime kernel.
     2173Figure~\ref{f:ctx-switch} shows the code for coroutines/threads with all results in Table~\ref{tab:ctx-switch}.
     2174All omitted tests for other languages are functionally identical to this test (as for all other tests).
     2175The difference in performance between coroutine and thread context-switch is the cost of scheduling for threads, whereas coroutines are self-scheduling.
     2176
    29092177\begin{figure}
    2910 \begin{multicols}{2}
    2911 \CFA Coroutines
    2912 \begin{cfa}
    2913 coroutine GreatSuspender {};
    2914 void main(GreatSuspender& this) {
    2915         while(true) { suspend(); }
    2916 }
     2178\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
     2179
     2180\newbox\myboxA
     2181\begin{lrbox}{\myboxA}
     2182\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     2183coroutine C {} c;
     2184void main( C & ) { for ( ;; ) { @suspend();@ } }
    29172185int main() {
    2918         GreatSuspender s;
    2919         resume(s);
     2186        Duration result;
    29202187        BENCH(
    2921                 for(size_t i=0; i<n; i++) {
    2922                         resume(s);
    2923                 },
     2188                for ( size_t i = 0; i < N; i += 1 ) { @resume( c );@ },
    29242189                result
    29252190        )
    2926         printf("%llu\n", result);
    2927 }
    2928 \end{cfa}
    2929 \columnbreak
    2930 \CFA Threads
    2931 \begin{cfa}
    2932 
    2933 
     2191        sout | result`ns | endl;
     2192}
     2193\end{cfa}
     2194\end{lrbox}
     2195
     2196\newbox\myboxB
     2197\begin{lrbox}{\myboxB}
     2198\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    29342199
    29352200
    29362201int main() {
    2937 
    2938 
     2202        Duration result;
    29392203        BENCH(
    2940                 for(size_t i=0; i<n; i++) {
    2941                         yield();
    2942                 },
     2204                for ( size_t i = 0; i < N; i += 1 ) { @yield();@ },
    29432205                result
    29442206        )
    2945         printf("%llu\n", result);
    2946 }
    2947 \end{cfa}
    2948 \end{multicols}
    2949 \begin{cfa}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={f:ctx-switch}]
    2950 \end{cfa}
     2207        sout | result`ns | endl;
     2208}
     2209\end{cfa}
     2210\end{lrbox}
     2211
     2212\subfloat[Coroutine]{\label{f:GlobalVariables}\usebox\myboxA}
     2213\quad
     2214\subfloat[Thread]{\label{f:ExternalState}\usebox\myboxB}
     2215\caption{\CFA Context-switch benchmark}
     2216\label{f:ctx-switch}
    29512217\end{figure}
    29522218
    29532219\begin{table}
    2954 \begin{center}
    2955 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |}
     2220\centering
     2221\caption{Context Switch comparison (nanoseconds)}
     2222\label{tab:ctx-switch}
     2223
     2224\begin{tabular}{|r|*{3}{D{.}{.}{3.2}|}}
    29562225\cline{2-4}
    2957 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
     2226\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    29582227\hline
    2959 Kernel Thread   & 241.5 & 243.86        & 5.08 \\
     2228Kernel Thread   & 241.5         & 243.86        & 5.08 \\
    29602229\CFA Coroutine  & 38            & 38            & 0    \\
    29612230\CFA Thread             & 103           & 102.96        & 2.96 \\
    2962 \uC Coroutine   & 46            & 45.86 & 0.35 \\
    2963 \uC Thread              & 98            & 99.11 & 1.42 \\
     2231\uC Coroutine   & 46            & 45.86         & 0.35 \\
     2232\uC Thread              & 98            & 99.11         & 1.42 \\
    29642233Goroutine               & 150           & 149.96        & 3.16 \\
    29652234Java Thread             & 289           & 290.68        & 8.72 \\
    29662235\hline
    29672236\end{tabular}
    2968 \end{center}
    2969 \caption{Context Switch comparison.
    2970 All numbers are in nanoseconds(\si{\nano\second})}
    2971 \label{tab:ctx-switch}
    29722237\end{table}
    29732238
    2974 \subsection{Mutual-Exclusion}
    2975 The next interesting benchmark is to measure the overhead to enter/leave a critical-section.
    2976 For monitors, the simplest approach is to measure how long it takes to enter and leave a monitor routine.
    2977 Figure~\ref{f:mutex} shows the code for \CFA.
     2239
     2240\paragraph{Mutual-Exclusion}
     2241
     2242Mutual exclusion is measured by entering/leaving a critical section.
     2243For monitors, entering and leaving a monitor routine is measured.
     2244Figure~\ref{f:mutex} shows the code for \CFA with all results in Table~\ref{tab:mutex}.
    29782245To put the results in context, the cost of entering a non-inline routine and the cost of acquiring and releasing a @pthread_mutex@ lock is also measured.
    2979 The results can be shown in table \ref{tab:mutex}.
    2980 
    2981 \begin{figure}
    2982 \begin{cfa}[caption={\CFA benchmark code used to measure mutex routines.},label={f:mutex}]
    2983 monitor M {};
    2984 void __attribute__((noinline)) call( M & mutex m /*, m2, m3, m4*/ ) {}
    2985 
     2246Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects.
     2247
     2248\begin{samepage}
     2249\begin{figure}[!p]
     2250\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
     2251\begin{cfa}
     2252monitor M {} m1/*, m2, m3, m4*/;
     2253void __attribute__((noinline)) do_call( M & mutex m/*, m2, m3, m4*/ ) {}
    29862254int main() {
    2987         M m/*, m2, m3, m4*/;
    2988         BENCH(
    2989                 for(size_t i=0; i<n; i++) {
    2990                         call(m/*, m2, m3, m4*/);
    2991                 },
    2992                 result
    2993         )
    2994         printf("%llu\n", result);
    2995 }
    2996 \end{cfa}
     2255        Duration result;
     2256        BENCH( for( size_t i = 0; i < N; i += 1 ) { @do_call( m1/*, m2, m3, m4*/ );@ }, result )
     2257        sout | result`ns | endl;
     2258}
     2259\end{cfa}
     2260\caption{\CFA benchmark code used to measure mutex routines.}
     2261\label{f:mutex}
    29972262\end{figure}
    29982263
    2999 \begin{table}
    3000 \begin{center}
    3001 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |}
     2264\begin{table}[!p]
     2265\centering
     2266\caption{Mutex routine comparison (nanoseconds)}
     2267\label{tab:mutex}
     2268
     2269\begin{tabular}{|r|*{3}{D{.}{.}{3.2}|}}
    30022270\cline{2-4}
    3003 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
     2271\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    30042272\hline
    3005 C routine                                               & 2             & 2             & 0    \\
    3006 FetchAdd + FetchSub                             & 26            & 26            & 0    \\
    3007 Pthreads Mutex Lock                             & 31            & 31.86 & 0.99 \\
     2273C routine                                                       & 2                     & 2                     & 0    \\
     2274FetchAdd + FetchSub                                     & 26            & 26            & 0    \\
     2275Pthreads Mutex Lock                                     & 31            & 31.86         & 0.99 \\
    30082276\uC @monitor@ member routine            & 30            & 30            & 0    \\
    3009 \CFA @mutex@ routine, 1 argument        & 41            & 41.57 & 0.9  \\
    3010 \CFA @mutex@ routine, 2 argument        & 76            & 76.96 & 1.57 \\
     2277\CFA @mutex@ routine, 1 argument        & 41            & 41.57         & 0.9  \\
     2278\CFA @mutex@ routine, 2 argument        & 76            & 76.96         & 1.57 \\
    30112279\CFA @mutex@ routine, 4 argument        & 145           & 146.68        & 3.85 \\
    3012 Java synchronized routine                       & 27            & 28.57 & 2.6  \\
     2280Java synchronized routine                       & 27            & 28.57         & 2.6  \\
    30132281\hline
    30142282\end{tabular}
    3015 \end{center}
    3016 \caption{Mutex routine comparison.
    3017 All numbers are in nanoseconds(\si{\nano\second})}
    3018 \label{tab:mutex}
    30192283\end{table}
    3020 
    3021 \subsection{Internal Scheduling}
    3022 The internal-scheduling benchmark measures the cost of waiting on and signalling a condition variable.
    3023 Figure~\ref{f:int-sched} shows the code for \CFA, with results table \ref{tab:int-sched}.
    3024 As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    3025 
    3026 \begin{figure}
    3027 \begin{cfa}[caption={Benchmark code for internal scheduling},label={f:int-sched}]
     2284\end{samepage}
     2285
     2286
     2287\paragraph{Internal Scheduling}
     2288
     2289Internal scheduling is measured by waiting on and signalling a condition variable.
     2290Figure~\ref{f:int-sched} shows the code for \CFA, with results in Table~\ref{tab:int-sched}.
     2291Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects.
     2292
     2293\begin{samepage}
     2294\begin{figure}[!p]
     2295\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
     2296\begin{cfa}
    30282297volatile int go = 0;
    30292298condition c;
    3030 monitor M {};
    3031 M m1;
    3032 
    3033 void __attribute__((noinline)) do_call( M & mutex a1 ) { signal(c); }
    3034 
     2299monitor M {} m;
     2300void __attribute__((noinline)) do_call( M & mutex a1 ) { signal( c ); }
    30352301thread T {};
    3036 void ^?{}( T & mutex this ) {}
    30372302void main( T & this ) {
    3038         while(go == 0) { yield(); }
    3039         while(go == 1) { do_call(m1); }
    3040 }
    3041 int  __attribute__((noinline)) do_wait( M & mutex a1 ) {
    3042         go = 1;
    3043         BENCH(
    3044                 for(size_t i=0; i<n; i++) {
    3045                         wait(c);
    3046                 },
    3047                 result
    3048         )
    3049         printf("%llu\n", result);
    3050         go = 0;
    3051         return 0;
     2303        while ( go == 0 ) { yield(); }  // wait for other thread to start
     2304        while ( go == 1 ) { @do_call( m );@ }
     2305}
     2306int  __attribute__((noinline)) do_wait( M & mutex m ) {
     2307        Duration result;
     2308        go = 1; // continue other thread
     2309        BENCH( for ( size_t i = 0; i < N; i += 1 ) { @wait( c );@ }, result );
     2310        go = 0; // stop other thread
     2311        sout | result`ns | endl;
    30522312}
    30532313int main() {
    30542314        T t;
    3055         return do_wait(m1);
    3056 }
    3057 \end{cfa}
     2315        do_wait( m );
     2316}
     2317\end{cfa}
     2318\caption{Internal scheduling benchmark}
     2319\label{f:int-sched}
    30582320\end{figure}
    30592321
    3060 \begin{table}
    3061 \begin{center}
    3062 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |}
     2322\begin{table}[!p]
     2323\centering
     2324\caption{Internal scheduling comparison (nanoseconds)}
     2325\label{tab:int-sched}
     2326\begin{tabular}{|r|*{3}{D{.}{.}{5.2}|}}
    30632327\cline{2-4}
    3064 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
     2328\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    30652329\hline
    3066 Pthreads Condition Variable                     & 5902.5        & 6093.29       & 714.78 \\
    3067 \uC @signal@                                    & 322           & 323   & 3.36   \\
    3068 \CFA @signal@, 1 @monitor@      & 352.5 & 353.11        & 3.66   \\
    3069 \CFA @signal@, 2 @monitor@      & 430           & 430.29        & 8.97   \\
    3070 \CFA @signal@, 4 @monitor@      & 594.5 & 606.57        & 18.33  \\
    3071 Java @notify@                           & 13831.5       & 15698.21      & 4782.3 \\
     2330Pthreads Condition Variable             & 5902.5        & 6093.29       & 714.78 \\
     2331\uC @signal@                                    & 322           & 323           & 3.36   \\
     2332\CFA @signal@, 1 @monitor@              & 352.5         & 353.11        & 3.66   \\
     2333\CFA @signal@, 2 @monitor@              & 430           & 430.29        & 8.97   \\
     2334\CFA @signal@, 4 @monitor@              & 594.5         & 606.57        & 18.33  \\
     2335Java @notify@                                   & 13831.5       & 15698.21      & 4782.3 \\
    30722336\hline
    30732337\end{tabular}
    3074 \end{center}
    3075 \caption{Internal scheduling comparison.
    3076 All numbers are in nanoseconds(\si{\nano\second})}
    3077 \label{tab:int-sched}
    30782338\end{table}
    3079 
    3080 \subsection{External Scheduling}
    3081 The Internal scheduling benchmark measures the cost of the @waitfor@ statement (@_Accept@ in \uC).
    3082 Figure~\ref{f:ext-sched} shows the code for \CFA, with results in table \ref{tab:ext-sched}.
    3083 As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    3084 
     2339\end{samepage}
     2340
     2341
     2342\paragraph{External Scheduling}
     2343
     2344External scheduling is measured by accepting a call using the @waitfor@ statement (@_Accept@ in \uC).
     2345Figure~\ref{f:ext-sched} shows the code for \CFA, with results in Table~\ref{tab:ext-sched}.
     2346Note, the incremental cost of bulk acquire for \CFA, which is largely a fixed cost for small numbers of mutex objects.
     2347
     2348\begin{samepage}
    30852349\begin{figure}
    3086 \begin{cfa}[caption={Benchmark code for external scheduling},label={f:ext-sched}]
     2350\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
     2351\begin{cfa}
    30872352volatile int go = 0;
    3088 monitor M {};
    3089 M m1;
     2353monitor M {} m;
    30902354thread T {};
    3091 
    3092 void __attribute__((noinline)) do_call( M & mutex a1 ) {}
    3093 
    3094 void ^?{}( T & mutex this ) {}
    3095 void main( T & this ) {
    3096         while(go == 0) { yield(); }
    3097         while(go == 1) { do_call(m1); }
    3098 }
    3099 int  __attribute__((noinline)) do_wait( M & mutex a1 ) {
    3100         go = 1;
    3101         BENCH(
    3102                 for(size_t i=0; i<n; i++) {
    3103                         waitfor(call, a1);
    3104                 },
    3105                 result
    3106         )
    3107         printf("%llu\n", result);
    3108         go = 0;
    3109         return 0;
     2355void __attribute__((noinline)) do_call( M & mutex ) {}
     2356void main( T & ) {
     2357        while ( go == 0 ) { yield(); }  // wait for other thread to start
     2358        while ( go == 1 ) { @do_call( m );@ }
     2359}
     2360int __attribute__((noinline)) do_wait( M & mutex m ) {
     2361        Duration result;
     2362        go = 1; BENCH( for ( size_t i = 0; i < N; i += 1 ) { @waitfor( do_call, m );@ }, result ) go = 0;
     2363        sout | result`ns | endl;
    31102364}
    31112365int main() {
    31122366        T t;
    3113         return do_wait(m1);
    3114 }
    3115 \end{cfa}
     2367        do_wait( m );
     2368}
     2369\end{cfa}
     2370\caption{Benchmark code for external scheduling}
     2371\label{f:ext-sched}
    31162372\end{figure}
    31172373
    31182374\begin{table}
    3119 \begin{center}
    3120 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |}
     2375\centering
     2376\caption{External scheduling comparison (nanoseconds)}
     2377\label{tab:ext-sched}
     2378\begin{tabular}{|r|*{3}{D{.}{.}{3.2}|}}
    31212379\cline{2-4}
    3122 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
     2380\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} &\multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    31232381\hline
    3124 \uC @Accept@                                    & 350           & 350.61        & 3.11  \\
    3125 \CFA @waitfor@, 1 @monitor@     & 358.5 & 358.36        & 3.82  \\
     2382\uC @Accept@                            & 350           & 350.61        & 3.11  \\
     2383\CFA @waitfor@, 1 @monitor@     & 358.5         & 358.36        & 3.82  \\
    31262384\CFA @waitfor@, 2 @monitor@     & 422           & 426.79        & 7.95  \\
    3127 \CFA @waitfor@, 4 @monitor@     & 579.5 & 585.46        & 11.25 \\
     2385\CFA @waitfor@, 4 @monitor@     & 579.5         & 585.46        & 11.25 \\
    31282386\hline
    31292387\end{tabular}
    3130 \end{center}
    3131 \caption{External scheduling comparison.
    3132 All numbers are in nanoseconds(\si{\nano\second})}
    3133 \label{tab:ext-sched}
    31342388\end{table}
    3135 
    3136 
    3137 \subsection{Object Creation}
    3138 Finally, the last benchmark measures the cost of creation for concurrent objects.
    3139 Figure~\ref{f:creation} shows the code for @pthread@s and \CFA threads, with results shown in table \ref{tab:creation}.
    3140 As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    3141 The only note here is that the call stacks of \CFA coroutines are lazily created, therefore without priming the coroutine, the creation cost is very low.
     2389\end{samepage}
     2390
     2391
     2392\paragraph{Object Creation}
     2393
     2394Object creation is measured by creating/deleting the specific kind of concurrent object.
     2395Figure~\ref{f:creation} shows the code for \CFA, with results in Table~\ref{tab:creation}.
     2396The only note here is that the call stacks of \CFA coroutines are lazily created, therefore without priming the coroutine to force stack creation, the creation cost is artificially low.
    31422397
    31432398\begin{figure}
    3144 \begin{center}
    3145 @pthread@
    3146 \begin{cfa}
     2399\centering
     2400\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
     2401\begin{cfa}
     2402thread MyThread {};
     2403void main( MyThread & ) {}
    31472404int main() {
    3148         BENCH(
    3149                 for(size_t i=0; i<n; i++) {
    3150                         pthread_t thread;
    3151                         if(pthread_create(&thread,NULL,foo,NULL)<0) {
    3152                                 perror( "failure" );
    3153                                 return 1;
    3154                         }
    3155 
    3156                         if(pthread_join(thread, NULL)<0) {
    3157                                 perror( "failure" );
    3158                                 return 1;
    3159                         }
    3160                 },
    3161                 result
    3162         )
    3163         printf("%llu\n", result);
    3164 }
    3165 \end{cfa}
    3166 
    3167 
    3168 
    3169 \CFA Threads
    3170 \begin{cfa}
    3171 int main() {
    3172         BENCH(
    3173                 for(size_t i=0; i<n; i++) {
    3174                         MyThread m;
    3175                 },
    3176                 result
    3177         )
    3178         printf("%llu\n", result);
    3179 }
    3180 \end{cfa}
    3181 \end{center}
    3182 \caption{Benchmark code for \protect\lstinline|pthread|s and \CFA to measure object creation}
     2405        Duration result;
     2406        BENCH( for ( size_t i = 0; i < N; i += 1 ) { @MyThread m;@ }, result )
     2407        sout | result`ns | endl;
     2408}
     2409\end{cfa}
     2410\caption{Benchmark code for \CFA object creation}
    31832411\label{f:creation}
    31842412\end{figure}
    31852413
    31862414\begin{table}
    3187 \begin{center}
    3188 \begin{tabular}{| l | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] | S[table-format=5.2,table-number-alignment=right] |}
     2415\centering
     2416\caption{Creation comparison (nanoseconds)}
     2417\label{tab:creation}
     2418\begin{tabular}{|r|*{3}{D{.}{.}{5.2}|}}
    31892419\cline{2-4}
    3190 \multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
     2420\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Median} & \multicolumn{1}{c|}{Average} & \multicolumn{1}{c|}{Std Dev} \\
    31912421\hline
    3192 Pthreads                        & 26996 & 26984.71      & 156.6  \\
    3193 \CFA Coroutine Lazy     & 6             & 5.71  & 0.45   \\
     2422Pthreads                                & 26996         & 26984.71      & 156.6  \\
     2423\CFA Coroutine Lazy             & 6                     & 5.71          & 0.45   \\
    31942424\CFA Coroutine Eager    & 708           & 706.68        & 4.82   \\
    3195 \CFA Thread                     & 1173.5        & 1176.18       & 15.18  \\
    3196 \uC Coroutine           & 109           & 107.46        & 1.74   \\
    3197 \uC Thread                      & 526           & 530.89        & 9.73   \\
    3198 Goroutine                       & 2520.5        & 2530.93       & 61,56  \\
    3199 Java Thread                     & 91114.5       & 92272.79      & 961.58 \\
     2425\CFA Thread                             & 1173.5        & 1176.18       & 15.18  \\
     2426\uC Coroutine                   & 109           & 107.46        & 1.74   \\
     2427\uC Thread                              & 526           & 530.89        & 9.73   \\
     2428Goroutine                               & 2520.5        & 2530.93       & 61.56  \\
     2429Java Thread                             & 91114.5       & 92272.79      & 961.58 \\
    32002430\hline
    32012431\end{tabular}
    3202 \end{center}
    3203 \caption{Creation comparison.
    3204 All numbers are in nanoseconds(\si{\nano\second}).}
    3205 \label{tab:creation}
    32062432\end{table}
    32072433
    32082434
    3209 
    32102435\section{Conclusion}
    3211 This paper has achieved a minimal concurrency \textbf{api} that is simple, efficient and usable as the basis for higher-level features.
    3212 The approach presented is based on a lightweight thread-system for parallelism, which sits on top of clusters of processors.
    3213 This M:N model is judged to be both more efficient and allow more flexibility for users.
    3214 Furthermore, this document introduces monitors as the main concurrency tool for users.
    3215 This paper also offers a novel approach allowing multiple monitors to be accessed simultaneously without running into the Nested Monitor Problem~\cite{Lister77}.
    3216 It also offers a full implementation of the concurrency runtime written entirely in \CFA, effectively the largest \CFA code base to date.
    3217 
    3218 
    3219 % ======================================================================
    3220 % ======================================================================
     2436
     2437This paper demonstrate a concurrency API that is simple, efficient, and able to build higher-level concurrency features.
     2438The 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.
     2439The M:N model is judged to be efficient and provide greater flexibility than a 1:1 threading model.
     2440High-level objects (monitor/task) are the core mechanism for mutual exclusion and synchronization.
     2441A novel aspect is allowing multiple mutex-objects to be accessed simultaneously reducing the potential for deadlock for this complex scenario.
     2442These concepts and the entire \CFA runtime-system are written in the \CFA language, demonstrating the expressiveness of the \CFA language.
     2443Performance comparisons with other concurrent systems/languages show the \CFA approach is competitive across all low-level operations, which translates directly into good performance in well-written concurrent applications.
     2444C programmers should feel comfortable using these mechanisms for developing concurrent applications, with the ability to obtain maximum available performance by mechanisms at the appropriate level.
     2445
     2446
    32212447\section{Future Work}
    3222 % ======================================================================
    3223 % ======================================================================
    3224 
    3225 \subsection{Performance} \label{futur:perf}
    3226 This paper presents a first implementation of the \CFA concurrency runtime.
    3227 Therefore, there is still significant work to improve performance.
    3228 Many of the data structures and algorithms may change in the future to more efficient versions.
    3229 For example, the number of monitors in a single bulk acquire is only bound by the stack size, this is probably unnecessarily generous.
    3230 It may be possible that limiting the number helps increase performance.
    3231 However, it is not obvious that the benefit would be significant.
    3232 
    3233 \subsection{Flexible Scheduling} \label{futur:sched}
     2448
     2449While concurrency in \CFA has a strong start, development is still underway and there are missing features.
     2450
     2451\paragraph{Flexible Scheduling}
     2452\label{futur:sched}
     2453
    32342454An important part of concurrency is scheduling.
    32352455Different scheduling algorithms can affect performance (both in terms of average and variation).
    32362456However, no single scheduler is optimal for all workloads and therefore there is value in being able to change the scheduler for given programs.
    3237 One solution is to offer various tweaking options to users, allowing the scheduler to be adjusted to the requirements of the workload.
    3238 However, in order to be truly flexible, it would be interesting to allow users to add arbitrary data and arbitrary scheduling algorithms.
    3239 For example, a web server could attach Type-of-Service information to threads and have a ``ToS aware'' scheduling algorithm tailored to this specific web server.
    3240 This path of flexible schedulers will be explored for \CFA.
    3241 
    3242 \subsection{Non-Blocking I/O} \label{futur:nbio}
    3243 While most of the parallelism tools are aimed at data parallelism and control-flow parallelism, many modern workloads are not bound on computation but on IO operations, a common case being web servers and XaaS (anything as a service).
    3244 These types of workloads often require significant engineering around amortizing costs of blocking IO operations.
    3245 At its core, non-blocking I/O is an operating system level feature that allows queuing IO operations (\eg network operations) and registering for notifications instead of waiting for requests to complete.
    3246 In this context, the role of the language makes Non-Blocking IO easily available and with low overhead.
    3247 The current trend is to use asynchronous programming using tools like callbacks and/or futures and promises, which can be seen in frameworks like Node.js~\cite{NodeJs} for JavaScript, Spring MVC~\cite{SpringMVC} for Java and Django~\cite{Django} for Python.
    3248 However, while these are valid solutions, they lead to code that is harder to read and maintain because it is much less linear.
    3249 
    3250 \subsection{Other Concurrency Tools} \label{futur:tools}
    3251 While monitors offer a flexible and powerful concurrent core for \CFA, other concurrency tools are also necessary for a complete multi-paradigm concurrency package.
    3252 Examples of such tools can include simple locks and condition variables, futures and promises~\cite{promises}, executors and actors.
     2457One solution is to offer various tweaking options, allowing the scheduler to be adjusted to the requirements of the workload.
     2458However, to be truly flexible, it is necessary to have a pluggable scheduler.
     2459Currently, 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.
     2460
     2461\paragraph{Non-Blocking I/O}
     2462\label{futur:nbio}
     2463
     2464Many modern workloads are not bound by computation but IO operations, a common case being web servers and XaaS~\cite{XaaS} (anything as a service).
     2465These types of workloads require significant engineering to amortizing costs of blocking IO-operations.
     2466At 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.
     2467Current 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.
     2468However, these solutions lead to code that is hard create, read and maintain.
     2469A 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.
     2470A non-blocking I/O library is currently under development for \CFA.
     2471
     2472\paragraph{Other Concurrency Tools}
     2473\label{futur:tools}
     2474
     2475While monitors offer a flexible and powerful concurrent for \CFA, other concurrency tools are also necessary for a complete multi-paradigm concurrency package.
     2476Examples of such tools can include futures and promises~\cite{promises}, executors and actors.
    32532477These additional features are useful when monitors offer a level of abstraction that is inadequate for certain tasks.
    32542478
    3255 \subsection{Implicit Threading} \label{futur:implcit}
    3256 Simpler applications can benefit greatly from having implicit parallelism.
    3257 That is, parallelism that does not rely on the user to write concurrency.
    3258 This type of parallelism can be achieved both at the language level and at the library level.
    3259 The canonical example of implicit parallelism is parallel for loops, which are the simplest example of a divide and conquer algorithms~\cite{uC++book}.
    3260 Table \ref{f:parfor} shows three different code examples that accomplish point-wise sums of large arrays.
    3261 Note that none of these examples explicitly declare any concurrency or parallelism objects.
    3262 
    3263 \begin{table}
    3264 \begin{center}
    3265 \begin{tabular}[t]{|c|c|c|}
    3266 Sequential & Library Parallel & Language Parallel \\
    3267 \begin{cfa}[tabsize=3]
    3268 void big_sum(
    3269         int* a, int* b,
    3270         int* o,
    3271         size_t len)
    3272 {
    3273         for(
    3274                 int i = 0;
    3275                 i < len;
    3276                 ++i )
    3277         {
    3278                 o[i]=a[i]+b[i];
    3279         }
    3280 }
    3281 
    3282 
    3283 
    3284 
    3285 
    3286 int* a[10000];
    3287 int* b[10000];
    3288 int* c[10000];
    3289 //... fill in a & b
    3290 big_sum(a,b,c,10000);
    3291 \end{cfa} &\begin{cfa}[tabsize=3]
    3292 void big_sum(
    3293         int* a, int* b,
    3294         int* o,
    3295         size_t len)
    3296 {
    3297         range ar(a, a+len);
    3298         range br(b, b+len);
    3299         range or(o, o+len);
    3300         parfor( ai, bi, oi,
    3301         [](     int* ai,
    3302                 int* bi,
    3303                 int* oi)
    3304         {
    3305                 oi=ai+bi;
    3306         });
    3307 }
    3308 
    3309 
    3310 int* a[10000];
    3311 int* b[10000];
    3312 int* c[10000];
    3313 //... fill in a & b
    3314 big_sum(a,b,c,10000);
    3315 \end{cfa}&\begin{cfa}[tabsize=3]
    3316 void big_sum(
    3317         int* a, int* b,
    3318         int* o,
    3319         size_t len)
    3320 {
    3321         parfor (ai,bi,oi)
    3322             in (a, b, o )
    3323         {
    3324                 oi = ai + bi;
    3325         }
    3326 }
    3327 
    3328 
    3329 
    3330 
    3331 
    3332 
    3333 
    3334 int* a[10000];
    3335 int* b[10000];
    3336 int* c[10000];
    3337 //... fill in a & b
    3338 big_sum(a,b,c,10000);
    3339 \end{cfa}
    3340 \end{tabular}
    3341 \end{center}
    3342 \caption{For loop to sum numbers: Sequential, using library parallelism and language parallelism.}
    3343 \label{f:parfor}
    3344 \end{table}
    3345 
    3346 Implicit parallelism is a restrictive solution and therefore has its limitations.
    3347 However, it is a quick and simple approach to parallelism, which may very well be sufficient for smaller applications and reduces the amount of boilerplate needed to start benefiting from parallelism in modern CPUs.
    3348 
    3349 
    3350 % A C K N O W L E D G E M E N T S
    3351 % -------------------------------
     2479\paragraph{Implicit Threading}
     2480\label{futur:implcit}
     2481
     2482Basic concurrent (embarrassingly parallel) applications can benefit greatly from implicit concurrency, where sequential programs are converted to concurrent, possibly with some help from pragmas to guide the conversion.
     2483This type of concurrency can be achieved both at the language level and at the library level.
     2484The canonical example of implicit concurrency is concurrent nested @for@ loops, which are amenable to divide and conquer algorithms~\cite{uC++book}.
     2485The \CFA language features should make it possible to develop a reasonable number of implicit concurrency mechanism to solve basic HPC data-concurrency problems.
     2486However, implicit concurrency is a restrictive solution and has its limitations, so it can never replace explicit concurrent programming.
     2487
     2488
    33522489\section{Acknowledgements}
    33532490
    3354 Thanks to Aaron Moss, Rob Schluntz and Andrew Beach for their work on the \CFA project as well as all the discussions which helped concretize the ideas in this paper.
    3355 Partial funding was supplied by the Natural Sciences and Engineering Research Council of Canada and a corporate partnership with Huawei Ltd.
    3356 
    3357 
    3358 % B I B L I O G R A P H Y
    3359 % -----------------------------
    3360 %\bibliographystyle{plain}
     2491The authors would like to recognize the design assistance of Aaron Moss, Rob Schluntz and Andrew Beach on the features described in this paper.
     2492Funding for this project has been provided by Huawei Ltd.\ (\url{http://www.huawei.com}), and Peter Buhr is partially funded by the Natural Sciences and Engineering Research Council of Canada.
     2493
     2494{%
     2495\fontsize{9bp}{12bp}\selectfont%
    33612496\bibliography{pl,local}
    3362 
     2497}%
    33632498
    33642499\end{document}
Note: See TracChangeset for help on using the changeset viewer.