Changeset fe3cd36


Ignore:
Timestamp:
Jul 1, 2018, 9:00:30 AM (6 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer, pthread-emulation, qualifiedEnum
Children:
7c919446
Parents:
22cf65e
Message:

submitted version

File:
1 edited

Legend:

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

    r22cf65e rfe3cd36  
    33\articletype{RESEARCH ARTICLE}%
    44
    5 \received{26 April 2016}
    6 \revised{6 June 2016}
    7 \accepted{6 June 2016}
     5\received{XXXXX}
     6\revised{XXXXX}
     7\accepted{XXXXX}
    88
    99\raggedbottom
     
    948948\subsection{Coroutine Implementation}
    949949
    950 A significant implementation challenge for coroutines (and threads, see section \ref{threads}) is adding extra fields and executing code after/before the coroutine constructor/destructor and coroutine main to create/initialize/de-initialize/destroy extra fields and the stack.
     950A significant implementation challenge for coroutines (and threads, see Section~\ref{threads}) is adding extra fields and executing code after/before the coroutine constructor/destructor and coroutine main to create/initialize/de-initialize/destroy extra fields and the stack.
    951951There are several solutions to this problem and the chosen option forced the \CFA coroutine design.
    952952
     
    13011301
    13021302For maximum usability, monitors have \newterm{multi-acquire} semantics allowing a thread to acquire it multiple times without deadlock.
    1303 For example, atomically printing the contents of a binary tree:
    1304 \begin{cfa}
    1305 monitor Tree {
    1306         Tree * left, * right;
    1307         // value
    1308 };
    1309 void print( Tree & mutex tree ) {                       $\C{// prefix traversal}$
    1310         // write value
    1311         print( *tree->left );                                   $\C{// multiply acquire monitor lock for tree on each recursion}$
    1312         print( *tree->right );
    1313 }
     1303\begin{cfa}
     1304monitor M { ... } m;
     1305void foo( M & mutex m ) { ... }                         $\C{// acquire mutual exclusion}$
     1306void bar( M & mutex m ) {                                       $\C{// acquire mutual exclusion}$
     1307        ... `foo( m );` ...                                             $\C{// reacquire mutual exclusion}$
     1308}
     1309`bar( m );`                                                                     $\C{// nested monitor call}$
    13141310\end{cfa}
    13151311
     
    14061402\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}}
    14071403\begin{cfa}
    1408 monitor M {};
     1404monitor M { ... };
    14091405void foo( M & mutex m1, M & mutex m2 ) {
    14101406        // critical section
     
    16521648@waitfor@ statically verifies the released monitors are the same as the acquired mutex-parameters of the given routine or routine pointer.
    16531649To statically verify the released monitors match with the accepted routine's mutex parameters, the routine (pointer) prototype must be accessible.
    1654 
    16551650% When an overloaded routine appears in an @waitfor@ statement, calls to any routine with that name are accepted.
    16561651% The rationale is that members with the same name should perform a similar function, and therefore, all should be eligible to accept a call.
    1657 As always, overloaded routines can be disambiguated using a cast:
     1652Overloaded routines can be disambiguated using a cast:
    16581653\begin{cfa}
    16591654void rtn( M & mutex m );
     
    17621757Signalled threads are moved to the urgent queue and the waiter at the front defines the set of monitors necessary for it to unblock.
    17631758Partial signalling transfers ownership of monitors to the front waiter.
    1764 When the signaller thread exits or waits in the monitor the front waiter is unblocked if all its monitors are released.
    1765 The benefit of this solution is encapsulating complexity into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
     1759When the signaller thread exits or waits in the monitor, the front waiter is unblocked if all its monitors are released.
     1760The benefit is encapsulating complexity into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
    17661761
    17671762
     
    17731768Similarly, monitor routines can be added at any time in \CFA, making it less clear for programmers and more difficult to implement.
    17741769\begin{cfa}
    1775 monitor M {};
     1770monitor M { ... };
    17761771void `f`( M & mutex m );
    17771772void g( M & mutex m ) { waitfor( `f` ); }       $\C{// clear which f}$
     
    18191814External scheduling, like internal scheduling, becomes significantly more complex for multi-monitor semantics.
    18201815Even in the simplest case, new semantics needs to be established.
    1821 \begin{cfa}
    1822 monitor M {};
     1816\newpage
     1817\begin{cfa}
     1818monitor M { ... };
    18231819void f( M & mutex m1 );
    18241820void g( M & mutex m1, M & mutex m2 ) {
     
    18331829This behaviour can be extended to the multi-monitor @waitfor@ statement.
    18341830\begin{cfa}
    1835 monitor M {};
     1831monitor M { ... };
    18361832void f( M & mutex m1, M & mutex m2 );
    18371833void g( M & mutex m1, M & mutex m2 ) {
     
    22442240\lstset{language=CFA,moredelim=**[is][\color{red}]{@}{@},deletedelim=**[is][]{`}{`}}
    22452241\begin{cfa}
    2246 monitor M {} m1/*, m2, m3, m4*/;
     2242monitor M { ... } m1/*, m2, m3, m4*/;
    22472243void __attribute__((noinline)) do_call( M & mutex m/*, m2, m3, m4*/ ) {}
    22482244int main() {
     
    22982294volatile int go = 0;
    22992295condition c;
    2300 monitor M {} m;
     2296monitor M { ... } m;
    23012297void __attribute__((noinline)) do_call( M & mutex a1 ) { signal( c ); }
    23022298thread T {};
     
    23492345\begin{cfa}
    23502346volatile int go = 0;
    2351 monitor M {} m;
     2347monitor M { ... } m;
    23522348thread T {};
    23532349void __attribute__((noinline)) do_call( M & mutex ) {}
Note: See TracChangeset for help on using the changeset viewer.