Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/proposals/concurrency/text/basics.tex

    ra2ea829 r21a1efb  
    11% ======================================================================
    22% ======================================================================
    3 \chapter{Concurrency Basics}\label{basics}
     3\chapter{Basics}\label{basics}
    44% ======================================================================
    55% ======================================================================
    6 Before any detailed discussion of the concurrency and parallelism in \CFA, it is important to describe the basics of concurrency and how they are expressed in \CFA user-code.
     6Before any detailed discussion of the concurrency and parallelism in \CFA, it is important to describe the basics of concurrency and how they are expressed in \CFA user code.
    77
    88\section{Basics of concurrency}
    9 At its core, concurrency is based on having multiple call-stacks and scheduling among threads of execution executing on these stacks. Concurrency without parallelism only requires having multiple call stacks (or contexts) for a single thread of execution.
    10 
    11 Execution with a single thread and multiple stacks where the thread is self-scheduling deterministically across the stacks is called coroutining. Execution with a single and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread perspective) across the stacks is called concurrency.
    12 
    13 Therefore, a minimal concurrency system can be achieved by creating coroutines, which instead of context switching among each other, always ask an oracle where to context switch next. While coroutines can execute on the caller's stack-frame, stackfull coroutines allow full generality and are sufficient as the basis for concurrency. The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model \cit. The oracle/scheduler can either be a stackless or stackfull entity and correspondingly require one or two context switches to run a different coroutine. In any case, a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to occur, the only feature missing is preemption.
    14 
    15 A scheduler introduces order of execution uncertainty, while preemption introduces uncertainty about where context-switches occur. Mutual-exclusion and synchronisation are ways of limiting non-determinism in a concurrent system. Now it is important to understand that uncertainty is desireable; uncertainty can be used by runtime systems to significantly increase performance and is often the basis of giving a user the illusion that tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows\cit.
     9At its core, concurrency is based on having call-stacks and potentially multiple threads of execution for these stacks. Concurrency without parallelism only requires having multiple call stacks (or contexts) for a single thread of execution, and switching between these call stacks on a regular basis. A minimal concurrency product can be achieved by creating coroutines, which instead of context switching between each other, always ask an oracle where to context switch next. While coroutines do not technically require a stack, stackfull coroutines are the closest abstraction to a practical "naked"" call stack. When writing concurrency in terms of coroutines, the oracle effectively becomes a scheduler and the whole system now follows a cooperative threading-model \cit. The oracle/scheduler can either be a stackless or stackfull entity and correspondingly require one or two context switches to run a different coroutine. In any case, a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to occur, the only feature missing is preemption. Indeed, concurrency challenges appear with non-determinism. Guaranteeing mutual-exclusion or synchronisation are simply ways of limiting the lack of determinism in a system. A scheduler introduces order of execution uncertainty, while preemption introduces incertainty about where context-switches occur. Now it is important to understand that uncertainty is not necessarily undesireable; uncertainty can often be used by systems to significantly increase performance and is often the basis of giving a user the illusion that tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows\cit.
    1610
    1711\section{\protect\CFA 's Thread Building Blocks}
    18 One of the important features that is missing in C is threading. On modern architectures, a lack of threading is unacceptable\cite{Sutter05, Sutter05b}, and therefore modern programming languages must have the proper tools to allow users to write performant concurrent programs to take advantage of parallelism. As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers familiar with imperative languages. And being a system-level language means programmers expect to choose precisely which features they need and which cost they are willing to pay.
     12One of the important features that is missing in C is threading. On modern architectures, a lack of threading is becoming less and less forgivable\cite{Sutter05, Sutter05b}, and therefore modern programming languages must have the proper tools to allow users to write performant concurrent and/or parallel programs. As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers used to imperative languages. And being a system-level language means programmers expect to choose precisely which features they need and which cost they are willing to pay.
    1913
    2014\section{Coroutines: A stepping stone}\label{coroutine}
    21 While the main focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are actually a significant building block of a concurrency system. Coroutines need to deal with context-switches and other context-management operations. Therefore, this proposal includes coroutines both as an intermediate step for the implementation of threads, and a first class feature of \CFA. Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant. The core \acrshort{api} of coroutines revolve around two features: independent call stacks and \code{suspend}/\code{resume}.
    22 
    23 \begin{figure}
    24 \begin{center}
    25 \begin{tabular}{c @{\hskip 0.025in}|@{\hskip 0.025in} c @{\hskip 0.025in}|@{\hskip 0.025in} c}
    26 \begin{ccode}[tabsize=2]
    27 //Using callbacks
    28 void fibonacci_func(
    29         int n,
    30         void (*callback)(int)
    31 ) {
    32         int first = 0;
    33         int second = 1;
    34         int next, i;
    35         for(i = 0; i < n; i++)
    36         {
    37                 if(i <= 1)
    38                         next = i;
    39                 else {
    40                         next = f1 + f2;
    41                         f1 = f2;
    42                         f2 = next;
     15While the main focus of this proposal is concurrency and parallelism, as mentionned above it is important to adress coroutines, which are actually a significant underlying aspect of a concurrency system. Indeed, while having nothing to do with parallelism and arguably little to do with concurrency, coroutines need to deal with context-switchs and other context-management operations. Therefore, this proposal includes coroutines both as an intermediate step for the implementation of threads, and a first class feature of \CFA. Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant. The core API of coroutines revolve around two features: independent call stacks and \code{suspend}/\code{resume}.
     16
     17Here is an example of a solution to the fibonnaci problem using \CFA coroutines:
     18\begin{cfacode}
     19        coroutine Fibonacci {
     20              int fn; // used for communication
     21        };
     22
     23        void ?{}(Fibonacci & this) { // constructor
     24              this.fn = 0;
     25        }
     26
     27        // main automacically called on first resume
     28        void main(Fibonacci & this) {
     29                int fn1, fn2;           // retained between resumes
     30                this.fn = 0;
     31                fn1 = this.fn;
     32                suspend(this);          // return to last resume
     33
     34                this.fn = 1;
     35                fn2 = fn1;
     36                fn1 = this.fn;
     37                suspend(this);          // return to last resume
     38
     39                for ( ;; ) {
     40                        this.fn = fn1 + fn2;
     41                        fn2 = fn1;
     42                        fn1 = this.fn;
     43                        suspend(this);  // return to last resume
    4344                }
    44                 callback(next);
    45         }
    46 }
    47 
    48 int main() {
    49         void print_fib(int n) {
    50                 printf("%d\n", n);
    51         }
    52 
    53         fibonacci_func(
    54                 10, print_fib
    55         );
    56 
    57 
    58 
    59 }
    60 \end{ccode}&\begin{ccode}[tabsize=2]
    61 //Using output array
    62 void fibonacci_array(
    63         int n,
    64         int * array
    65 ) {
    66         int f1 = 0; int f2 = 1;
    67         int next, i;
    68         for(i = 0; i < n; i++)
    69         {
    70                 if(i <= 1)
    71                         next = i;
    72                 else {
    73                         next = f1 + f2;
    74                         f1 = f2;
    75                         f2 = next;
     45        }
     46
     47        int next(Fibonacci & this) {
     48                resume(this); // transfer to last suspend
     49                return this.fn;
     50        }
     51
     52        void main() { // regular program main
     53                Fibonacci f1, f2;
     54                for ( int i = 1; i <= 10; i += 1 ) {
     55                        sout | next( f1 ) | next( f2 ) | endl;
    7656                }
    77                 array[i] = next;
    78         }
    79 }
    80 
    81 
    82 int main() {
    83         int a[10];
    84 
    85         fibonacci_func(
    86                 10, a
    87         );
    88 
    89         for(int i=0;i<10;i++){
    90                 printf("%d\n", a[i]);
    91         }
    92 
    93 }
    94 \end{ccode}&\begin{ccode}[tabsize=2]
    95 //Using external state
    96 typedef struct {
    97         int f1, f2;
    98 } Iterator_t;
    99 
    100 int fibonacci_state(
    101         Iterator_t * it
    102 ) {
    103         int f;
    104         f = it->f1 + it->f2;
    105         it->f2 = it->f1;
    106         it->f1 = max(f,1);
    107         return f;
    108 }
    109 
    110 
    111 
    112 
    113 
    114 
    115 
    116 int main() {
    117         Iterator_t it={0,0};
    118 
    119         for(int i=0;i<10;i++){
    120                 printf("%d\n",
    121                         fibonacci_state(
    122                                 &it
    123                         );
    124                 );
    125         }
    126 
    127 }
    128 \end{ccode}
    129 \end{tabular}
    130 \end{center}
    131 \caption{Different implementations of a fibonacci sequence generator in C.}
    132 \label{lst:fibonacci-c}
    133 \end{figure}
    134 
    135 A good example of a problem made easier with coroutines is generators, like the fibonacci sequence. This problem comes with the challenge of decoupling how a sequence is generated and how it is used. Figure \ref{lst:fibonacci-c} shows conventional approaches to writing generators in C. All three of these approach suffer from strong coupling. The left and center approaches require that the generator have knowledge of how the sequence is used, while the rightmost approach requires holding internal state between calls on behalf of the generator and makes it much harder to handle corner cases like the Fibonacci seed.
    136 
    137 Figure \ref{lst:fibonacci-cfa} is an example of a solution to the fibonnaci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the generation. This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used. Indeed, this version is as easy to use as the \code{fibonacci_state} solution, while the imlpementation is very similar to the \code{fibonacci_func} example.
    138 
    139 \begin{figure}
    140 \begin{cfacode}
    141 coroutine Fibonacci {
    142         int fn; //used for communication
    143 };
    144 
    145 void ?{}(Fibonacci & this) { //constructor
    146         this.fn = 0;
    147 }
    148 
    149 //main automacically called on first resume
    150 void main(Fibonacci & this) with (this) {
    151         int fn1, fn2;           //retained between resumes
    152         fn  = 0;
    153         fn1 = fn;
    154         suspend(this);          //return to last resume
    155 
    156         fn  = 1;
    157         fn2 = fn1;
    158         fn1 = fn;
    159         suspend(this);          //return to last resume
    160 
    161         for ( ;; ) {
    162                 fn  = fn1 + fn2;
    163                 fn2 = fn1;
    164                 fn1 = fn;
    165                 suspend(this);  //return to last resume
    166         }
    167 }
    168 
    169 int next(Fibonacci & this) {
    170         resume(this); //transfer to last suspend
    171         return this.fn;
    172 }
    173 
    174 void main() { //regular program main
    175         Fibonacci f1, f2;
    176         for ( int i = 1; i <= 10; i += 1 ) {
    177                 sout | next( f1 ) | next( f2 ) | endl;
    178         }
    179 }
    180 \end{cfacode}
    181 \caption{Implementation of fibonacci using coroutines}
    182 \label{lst:fibonacci-cfa}
    183 \end{figure}
    184 
    185 Figure \ref{lst:fmt-line} shows the \code{Format} coroutine which rearranges text in order to group characters into blocks of fixed size. The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor.
    186 
    187 \begin{figure}
    188 \begin{cfacode}[tabsize=3]
    189 //format characters into blocks of 4 and groups of 5 blocks per line
    190 coroutine Format {
    191         char ch;                                                                        //used for communication
    192         int g, b;                                                               //global because used in destructor
    193 };
    194 
    195 void  ?{}(Format & fmt) {
    196         resume( fmt );                                                  //prime (start) coroutine
    197 }
    198 
    199 void ^?{}(Format & fmt) with fmt {
    200         if ( fmt.g != 0 || fmt.b != 0 )
    201         sout | endl;
    202 }
    203 
    204 void main(Format & fmt) with fmt {
    205         for ( ;; ) {                                                    //for as many characters
    206                 for(g = 0; g < 5; g++) {                //groups of 5 blocks
    207                         for(b = 0; b < 4; fb++) {       //blocks of 4 characters
    208                                 suspend();
    209                                 sout | ch;                                      //print character
    210                         }
    211                         sout | "  ";                                    //print block separator
    212                 }
    213                 sout | endl;                                            //print group separator
    214         }
    215 }
    216 
    217 void prt(Format & fmt, char ch) {
    218         fmt.ch = ch;
    219         resume(fmt);
    220 }
    221 
    222 int main() {
    223         Format fmt;
    224         char ch;
    225         Eof: for ( ;; ) {                                               //read until end of file
    226                 sin | ch;                                                       //read one character
    227                 if(eof(sin)) break Eof;                 //eof ?
    228                 prt(fmt, ch);                                           //push character for formatting
    229         }
    230 }
    231 \end{cfacode}
    232 \caption{Formatting text into lines of 5 blocks of 4 characters.}
    233 \label{lst:fmt-line}
    234 \end{figure}
     57        }
     58\end{cfacode}
    23559
    23660\subsection{Construction}
    237 One important design challenge for coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run code after the user-constructor runs to connect the fully constructed object into the system. In the case of coroutines, this challenge is simpler since there is no non-determinism from preemption or scheduling. However, the underlying challenge remains the same for coroutines and threads.
    238 
    239 The runtime system needs to create the coroutine's stack and more importantly prepare it for the first resumption. The timing of the creation is non-trivial since users both expect to have fully constructed objects once execution enters the coroutine main and to be able to resume the coroutine from the constructor. As regular objects, constructors can leak coroutines before they are ready. There are several solutions to this problem but the chosen options effectively forces the design of the coroutine.
     61One important design challenge for coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run code after the user-constructor runs. In the case of coroutines, this challenge is simpler since there is no non-determinism from preemption or scheduling. However, the underlying challenge remains the same for coroutines and threads.
     62
     63The runtime system needs to create the coroutine's stack and more importantly prepare it for the first resumption. The timing of the creation is non-trivial since users both expect to have fully constructed objects once execution enters the coroutine main and to be able to resume the coroutine from the constructor. Like for regular objects, constructors can still leak coroutines before they are ready. There are several solutions to this problem but the chosen options effectively forces the design of the coroutine.
    24064
    24165Furthermore, \CFA faces an extra challenge as polymorphic routines create invisible thunks when casted to non-polymorphic routines and these thunks have function scope. For example, the following code, while looking benign, can run into undefined behaviour because of thunks:
    … …  
    24771
    24872forall(otype T)
    249 void noop(T*) {}
     73void noop(T *) {}
    25074
    25175void bar() {
    25276        int a;
    253         async(noop, &a); //start thread running noop with argument a
    254 }
    255 \end{cfacode}
    256 
     77        async(noop, &a);
     78}
     79\end{cfacode}
    25780The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information:
    25881
    … …  
    27295}
    27396\end{ccode}
    274 The problem in this example is a storage management issue, the function pointer \code{_thunk0} is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes undefined behavior; i.e., the stack-based thunk being destroyed before it can be used. This challenge is an extension of challenges that come with second-class routines. Indeed, GCC nested routines also have the limitation that nested routine cannot be passed outside of the declaration scope. The case of coroutines and threads is simply an extension of this problem to multiple call-stacks.
     97The problem in this example is a race condition between the start of the execution of \code{noop} on the other thread and the stack frame of \code{bar} being destroyed. This extra challenge limits which solutions are viable because storing the function pointer for too long only increases the chances that the race will end in undefined behavior; i.e. the stack based thunk being destroyed before it was used. This challenge is an extension of challenges that come with second-class routines. Indeed, GCC nested routines also have the limitation that the routines cannot be passed outside of the scope of the functions these were declared in. The case of coroutines and threads is simply an extension of this problem to multiple call-stacks.
    27598
    27699\subsection{Alternative: Composition}
    277 One solution to this challenge is to use composition/containement, where coroutine fields are added to manage the coroutine.
    278 
    279 \begin{cfacode}
    280 struct Fibonacci {
    281         int fn; //used for communication
    282         coroutine c; //composition
    283 };
    284 
    285 void FibMain(void *) {
    286         //...
    287 }
    288 
    289 void ?{}(Fibonacci & this) {
    290         this.fn = 0;
    291         //Call constructor to initialize coroutine
    292         (this.c){myMain};
    293 }
    294 \end{cfacode}
    295 The downside of this approach is that users need to correctly construct the coroutine handle before using it. Like any other objects, doing so the users carefully choose construction order to prevent usage of unconstructed objects. However, in the case of coroutines, users must also pass to the coroutine information about the coroutine main, like in the previous example. This opens the door for user errors and requires extra runtime storage to pass at runtime information that can be known statically.
     100One solution to this challenge would be to use composition/containement,
     101
     102\begin{cfacode}
     103        struct Fibonacci {
     104              int fn; // used for communication
     105              coroutine c; //composition
     106        };
     107
     108        void ?{}(Fibonacci & this) {
     109              this.fn = 0;
     110                (this.c){};
     111        }
     112\end{cfacode}
     113There are two downsides to this approach. The first, which is relatively minor, is that the base class needs to be made aware of the main routine pointer, regardless of whether a parameter or a virtual pointer is used, this means the coroutine data must be made larger to store a value that is actually a compile time constant (address of the main routine). The second problem, which is both subtle and significant, is that now users can get the initialisation order of there coroutines wrong. Indeed, every field of a \CFA struct is constructed but in declaration order, unless users explicitly write otherwise. This semantics means that users who forget to initialize a the coroutine may resume the coroutine with an uninitilized object. For coroutines, this is unlikely to be a problem, for threads however, this is a significant problem.
    296114
    297115\subsection{Alternative: Reserved keyword}
    … …  
    299117
    300118\begin{cfacode}
    301 coroutine Fibonacci {
    302         int fn; //used for communication
    303 };
    304 \end{cfacode}
    305 The \code{coroutine} keyword means the compiler can find and inject code where needed. The downside of this approach is that it makes coroutine a special case in the language. Users wantint to extend coroutines or build their own for various reasons can only do so in ways offered by the language. Furthermore, implementing coroutines without language supports also displays the power of the programming language used. While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can still be constructed by users without using the language support. The reserved keywords are only present to improve ease of use for the common cases.
     119        coroutine Fibonacci {
     120              int fn; // used for communication
     121        };
     122\end{cfacode}
     123This mean the compiler can solve problems by injecting code where needed. The downside of this approach is that it makes coroutine a special case in the language. Users who would want to extend coroutines or build their own for various reasons can only do so in ways offered by the language. Furthermore, implementing coroutines without language supports also displays the power of \CFA.
     124While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can both be constructed by users without using the language support. The reserved keywords are only present to improve ease of use for the common cases.
    306125
    307126\subsection{Alternative: Lamda Objects}
    … …  
    316135Often, the canonical threading paradigm in languages is based on function pointers, pthread being one of the most well known examples. The main problem of this approach is that the thread usage is limited to a generic handle that must otherwise be wrapped in a custom type. Since the custom type is simple to write in \CFA and solves several issues, added support for routine/lambda based coroutines adds very little.
    317136
    318 A variation of this would be to use a simple function pointer in the same way pthread does for threads :
     137A variation of this would be to use an simple function pointer in the same way pthread does for threads :
    319138\begin{cfacode}
    320139void foo( coroutine_t cid, void * arg ) {
    … …  
    329148}
    330149\end{cfacode}
    331 This semantics is more common for thread interfaces than coroutines works equally well. As discussed in section \ref{threads}, this approach is superseeded by static approaches in terms of expressivity.
     150This semantic is more common for thread interfaces than coroutines but would work equally well. As discussed in section \ref{threads}, this approach is superseeded by static approaches in terms of expressivity.
    332151
    333152\subsection{Alternative: Trait-based coroutines}
    … …  
    340159      coroutine_desc * get_coroutine(T & this);
    341160};
    342 
    343 forall( dtype T | is_coroutine(T) ) void suspend(T &);
    344 forall( dtype T | is_coroutine(T) ) void resume (T &);
    345 \end{cfacode}
    346 This ensures an object is not a coroutine until \code{resume} is called on the object. Correspondingly, any object that is passed to \code{resume} is a coroutine since it must satisfy the \code{is_coroutine} trait to compile. The advantage of this approach is that users can easily create different types of coroutines, for example, changing the memory layout of a coroutine is trivial when implementing the \code{get_coroutine} routine. The \CFA keyword \code{coroutine} only has the effect of implementing the getter and forward declarations required for users to only have to implement the main routine.
     161\end{cfacode}
     162This ensures an object is not a coroutine until \code{resume} (or \code{prime}) is called on the object. Correspondingly, any object that is passed to \code{resume} is a coroutine since it must satisfy the \code{is_coroutine} trait to compile. The advantage of this approach is that users can easily create different types of coroutines, for example, changing the memory foot print of a coroutine is trivial when implementing the \code{get_coroutine} routine. The \CFA keyword \code{coroutine} only has the effect of implementing the getter and forward declarations required for users to only have to implement the main routine.
    347163
    348164\begin{center}
    … …  
    370186\end{center}
    371187
    372 The combination of these two approaches allows users new to coroutinning and concurrency to have an easy and concise specification, while more advanced users have tighter control on memory layout and initialization.
     188The combination of these two approaches allows users new to concurrency to have a easy and concise method while more advanced users can expose themselves to otherwise hidden pitfalls at the benefit of tighter control on memory layout and initialization.
    373189
    374190\section{Thread Interface}\label{threads}
    … …  
    376192
    377193\begin{cfacode}
    378 thread foo {};
     194        thread foo {};
    379195\end{cfacode}
    380196
    … …  
    389205\end{cfacode}
    390206
    391 Obviously, for this thread implementation to be usefull it must run some user code. Several other threading interfaces use a function-pointer representation as the interface of threads (for example \Csharp~\cite{Csharp} and Scala~\cite{Scala}). However, this proposal considers that statically tying a \code{main} routine to a thread superseeds this approach. Since the \code{main} routine is already a special routine in \CFA (where the program begins), it is a natural extension of the semantics using overloading to declare mains for different threads (the normal main being the main of the initial thread). As such the \code{main} routine of a thread can be defined as
    392 \begin{cfacode}
    393 thread foo {};
    394 
    395 void main(foo & this) {
    396         sout | "Hello World!" | endl;
    397 }
    398 \end{cfacode}
    399 
    400 In this example, threads of type \code{foo} start execution in the \code{void main(foo &)} routine, which prints \code{"Hello World!"}. While this thesis encourages this approach to enforce strongly-typed programming, users may prefer to use the routine-based thread semantics for the sake of simplicity. With the static semantics it is trivial to write a thread type that takes a function pointer as a parameter and executes it on its stack asynchronously.
    401 \begin{cfacode}
    402 typedef void (*voidFunc)(int);
    403 
    404 thread FuncRunner {
    405         voidFunc func;
    406         int arg;
    407 };
    408 
    409 void ?{}(FuncRunner & this, voidFunc inFunc, int arg) {
    410         this.func = inFunc;
    411         this.arg  = arg;
    412 }
    413 
    414 void main(FuncRunner & this) {
    415         //thread starts here and runs the function
    416         this.func( this.arg );
    417 }
    418 \end{cfacode}
    419 
    420 A consequence of the strongly-typed approach to main is that memory layout of parameters and return values to/from a thread are now explicitly specified in the \acrshort{api}.
    421 
    422 Of course for threads to be useful, it must be possible to start and stop threads and wait for them to complete execution. While using an \acrshort{api} such as \code{fork} and \code{join} is relatively common in the literature, such an interface is unnecessary. Indeed, the simplest approach is to use \acrshort{raii} principles and have threads \code{fork} after the constructor has completed and \code{join} before the destructor runs.
     207Obviously, for this thread implementation to be usefull it must run some user code. Several other threading interfaces use a function-pointer representation as the interface of threads (for example \Csharp~\cite{Csharp} and Scala~\cite{Scala}). However, this proposal considers that statically tying a \code{main} routine to a thread superseeds this approach. Since the \code{main} routine is already a special routine in \CFA (where the program begins), it is possible naturally extend the semantics using overloading to declare mains for different threads (the normal main being the main of the initial thread). As such the \code{main} routine of a thread can be defined as
     208\begin{cfacode}
     209        thread foo {};
     210
     211        void main(foo & this) {
     212                sout | "Hello World!" | endl;
     213        }
     214\end{cfacode}
     215
     216In this example, threads of type \code{foo} start execution in the \code{void main(foo*)} routine which prints \code{"Hello World!"}. While this proposoal encourages this approach to enforce strongly-typed programming, users may prefer to use the routine based thread semantics for the sake of simplicity. With these semantics it is trivial to write a thread type that takes a function pointer as parameter and executes it on its stack asynchronously
     217\begin{cfacode}
     218        typedef void (*voidFunc)(void);
     219
     220        thread FuncRunner {
     221                voidFunc func;
     222        };
     223
     224        //ctor
     225        void ?{}(FuncRunner & this, voidFunc inFunc) {
     226                this.func = inFunc;
     227        }
     228
     229        //main
     230        void main(FuncRunner & this) {
     231                this.func();
     232        }
     233\end{cfacode}
     234
     235An advantage of the overloading approach to main is to clearly highlight where and what memory is required to pass parameters and return values to/from a thread.
     236
     237Of course for threads to be useful, it must be possible to start and stop threads and wait for them to complete execution. While using an \acrshort{api} such as \code{fork} and \code{join} is relatively common in the literature, such an interface is unnecessary. Indeed, the simplest approach is to use \acrshort{raii} principles and have threads \code{fork} once the constructor has completed and \code{join} before the destructor runs.
    423238\begin{cfacode}
    424239thread World;
    … …  
    439254\end{cfacode}
    440255
    441 This semantic has several advantages over explicit semantics: a thread is always started and stopped exaclty once, users cannot make any progamming errors, and it naturally scales to multiple threads meaning basic synchronisation is very simple.
     256This semantic has several advantages over explicit semantics typesafety is guaranteed, a thread is always started and stopped exaclty once and users cannot make any progamming errors. Another advantage of this semantic is that it naturally scale to multiple threads meaning basic synchronisation is very simple
    442257
    443258\begin{cfacode}
    … …  
    461276\end{cfacode}
    462277
    463 However, one of the drawbacks of this approach is that threads now always form a lattice, that is they are always destroyed in the opposite order of construction because of block structure. This restriction is relaxed by using dynamic allocation, so threads can outlive the scope in which they are created, much like dynamically allocating memory lets objects outlive the scope in which they are created.
     278However, one of the apparent drawbacks of this system is that threads now always form a lattice, that is they are always destroyed in opposite order of construction because of block structure. However, storage allocation is not limited to blocks; dynamic allocation can create threads that outlive the scope in which the thread is created much like dynamically allocating memory lets objects outlive the scope in which they are created
    464279
    465280\begin{cfacode}
    … …  
    468283};
    469284
     285//main
    470286void main(MyThread & this) {
    471287        //...
    … …  
    475291        MyThread * long_lived;
    476292        {
     293                MyThread short_lived;
    477294                //Start a thread at the beginning of the scope
    478                 MyThread short_lived;
     295
     296                DoStuff();
    479297
    480298                //create another thread that will outlive the thread in this scope
    481299                long_lived = new MyThread;
    482300
    483                 DoStuff();
    484 
    485301                //Wait for the thread short_lived to finish
    486302        }
    487303        DoMoreStuff();
    488304
    489         //Now wait for the long_lived to finish
     305        //Now wait for the short_lived to finish
    490306        delete long_lived;
    491307}
Note: See TracChangeset for help on using the changeset viewer.