Changes in / [b7778c1:bb9d8e8]


Ignore:
Location:
doc/proposals/concurrency
Files:
1 deleted
8 edited

Legend:

Unmodified
Added
Removed

  • doc/proposals/concurrency/Makefile

    rb7778c1 rbb9d8e8  
    1616text/basics \
    1717text/concurrency \
    18 text/internals \
    1918text/parallelism \
    2019text/together \

  • doc/proposals/concurrency/style/cfa-format.tex

    rb7778c1 rbb9d8e8  
    133133  belowskip=3pt,
    134134  keepspaces=true,
    135   tabsize=4,
    136135  % frame=lines,
    137136  literate=,
    … …  
    151150  keywordstyle=\bfseries\color{blue},
    152151  keywordstyle=[2]\bfseries\color{Plum},
    153   commentstyle=\sf\itshape\color{OliveGreen},             % green and italic comments
     152  commentstyle=\itshape\color{OliveGreen},                  % green and italic comments
    154153  identifierstyle=\color{identifierCol},
    155154  stringstyle=\sf\color{Mahogany},                                % use sanserif font
    … …  
    159158  belowskip=3pt,
    160159  keepspaces=true,
    161   tabsize=4,
    162160  % frame=lines,
    163161  literate=,

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

    rb7778c1 rbb9d8e8  
    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 Indeed, while 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. Indeed, concurrency challenges appear with non-determinism. Using mutual-exclusion or synchronisation are ways of limiting the lack of determinism in a system. A scheduler introduces order of execution uncertainty, while preemption introduces uncertainty about where context-switches occur. Now it is important to understand that uncertainty is not 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.
     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.
    1410
    1511\section{\protect\CFA 's Thread Building Blocks}
    16 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 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 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.
    1713
    1814\section{Coroutines: A stepping stone}\label{coroutine}
    19 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-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 \acrshort{api} of coroutines revolve around two features: independent call stacks and \code{suspend}/\code{resume}.
    20 
    21 A good example of a problem made easier with coroutines is genereting the fibonacci sequence. This problem comes with the challenge of decoupling how a sequence is generated and how it is used. Figure \ref{fig: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 will be used, while the rightmost approach requires to user to hold internal state between calls on behalf of th sequence generator and makes it much harder to handle corner cases like the Fibonacci seed.
    22 \begin{figure}
    23 \label{fig:fibonacci-c}
    24 \caption{Different implementations of a fibonacci sequence generator in C.}
    25 \begin{center}
    26 \begin{tabular}{c @{\hskip 0.025in}|@{\hskip 0.025in} c @{\hskip 0.025in}|@{\hskip 0.025in} c}
    27 \begin{ccode}[tabsize=2]
    28 //Using callbacks
    29 void fibonacci_func(
    30         int n,
    31         void (*callback)(int)
    32 ) {
    33         int first = 0;
    34         int second = 1;
    35         int next, i;
    36         for(i = 0; i < n; i++)
    37         {
    38                 if(i <= 1)
    39                         next = i;
    40                 else {
    41                         next = f1 + f2;
    42                         f1 = f2;
    43                         f2 = next;
    44                 }
    45                 callback(next);
    46         }
    47 }
    48 \end{ccode}&\begin{ccode}[tabsize=2]
    49 //Using output array
    50 void fibonacci_array(
    51         int n,
    52         int * array
    53 ) {
    54         int f1 = 0; int f2 = 1;
    55         int next, i;
    56         for(i = 0; i < n; i++)
    57         {
    58                 if(i <= 1)
    59                         next = i;
    60                 else {
    61                         next = f1 + f2;
    62                         f1 = f2;
    63                         f2 = next;
    64                 }
    65                 *array = next;
    66                 array++;
    67         }
    68 }
    69 \end{ccode}&\begin{ccode}[tabsize=2]
    70 //Using external state
    71 typedef struct {
    72         int f1, f2;
    73 } iterator_t;
    74 
    75 int fibonacci_state(
    76         iterator_t * it
    77 ) {
    78         int f;
    79         f = it->f1 + it->f2;
    80         it->f2 = it->f1;
    81         it->f1 = f;
    82         return f;
    83 }
    84 
    85 
    86 
    87 
    88 
    89 
    90 \end{ccode}
    91 \end{tabular}
    92 \end{center}
    93 \end{figure}
    94 
    95 
    96 Figure \ref{fig:fibonacci-cfa} is an example of a solution to the fibonnaci problem using \CFA coroutines, using the coroutine stack to hold 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 a easy to use as the \code{fibonacci_state} solution, while the imlpementation is very similar to the \code{fibonacci_func} example.
    97 
    98 \begin{figure}
    99 \label{fig:fibonacci-cfa}
    100 \caption{Implementation of fibonacci using coroutines}
    101 \begin{cfacode}
    102 coroutine Fibonacci {
    103         int fn; //used for communication
    104 };
    105 
    106 void ?{}(Fibonacci & this) { //constructor
    107         this.fn = 0;
    108 }
    109 
    110 //main automacically called on first resume
    111 void main(Fibonacci & this) {
    112         int fn1, fn2;           //retained between resumes
    113         this.fn = 0;
    114         fn1 = this.fn;
    115         suspend(this);          //return to last resume
    116 
    117         this.fn = 1;
    118         fn2 = fn1;
    119         fn1 = this.fn;
    120         suspend(this);          //return to last resume
    121 
    122         for ( ;; ) {
    123                 this.fn = fn1 + fn2;
     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;
    12435                fn2 = fn1;
    12536                fn1 = this.fn;
    126                 suspend(this);  //return to last resume
    127         }
    128 }
    129 
    130 int next(Fibonacci & this) {
    131         resume(this); //transfer to last suspend
    132         return this.fn;
    133 }
    134 
    135 void main() { //regular program main
    136         Fibonacci f1, f2;
    137         for ( int i = 1; i <= 10; i += 1 ) {
    138                 sout | next( f1 ) | next( f2 ) | endl;
    139         }
    140 }
    141 \end{cfacode}
    142 \end{figure}
     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
     44                }
     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;
     56                }
     57        }
     58\end{cfacode}
    14359
    14460\subsection{Construction}
    145 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 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.
    146 
    147 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.
    14864
    14965Furthermore, \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:
    … …  
    16278}
    16379\end{cfacode}
    164 
    16580The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information:
    16681
    … …  
    18095}
    18196\end{ccode}
    182 The problem in this example is a storage management issue, the function pointer \code{_thunk0} is only valid until the end of the block. This extra challenge limits which solutions are viable because storing the function pointer for too long causes 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.
     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.
    18398
    18499\subsection{Alternative: Composition}
    185 One solution to this challenge is to use composition/containement, where uses add insert a coroutine field which contains the necessary information to manage the coroutine.
    186 
    187 \begin{cfacode}
    188 struct Fibonacci {
    189         int fn; //used for communication
    190         coroutine c; //composition
    191 };
    192 
    193 void ?{}(Fibonacci & this) {
    194         this.fn = 0;
    195         (this.c){}; //Call constructor to initialize coroutine
    196 }
    197 \end{cfacode}
    198 There are two downsides to this approach. The first, which is relatively minor, made aware of the main routine pointer. This information must either be store in the coroutine runtime data or in its static type structure. When using composition, all coroutine handles have the same static type structure which means the pointer to the main needs to be part of the runtime data. This requirement 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 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 the coroutine handle 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. Figure \ref{fig:fmt-line} shows the \code{Format} coroutine which rearranges text in order to group characters into blocks of fixed size. This is a good example where the control flow is made much simpler from being able to resume the coroutine from the constructor and highlights the idea that interesting control flow can occor in the constructor.
    199 \begin{figure}
    200 \label{fig:fmt-line}
    201 \caption{Formatting text into lines of 5 blocks of 4 characters.}
    202 \begin{cfacode}[tabsize=3]
    203 //format characters into blocks of 4 and groups of 5 blocks per line
    204 coroutine Format {
    205         char ch;                                                                        //used for communication
    206         int g, b;                                                               //global because used in destructor
    207 };
    208 
    209 void  ?{}(Format & fmt) {
    210         resume( fmt );                                                  //prime (start) coroutine
    211 }
    212 
    213 void ^?{}(Format & fmt) with fmt {
    214         if ( fmt.g != 0 || fmt.b != 0 )
    215         sout | endl;
    216 }
    217 
    218 void main(Format & fmt) with fmt {
    219         for ( ;; ) {                                                    //for as many characters
    220                 for(g = 0; g < 5; g++) {                //groups of 5 blocks
    221                         for(b = 0; b < 4; fb++) {       //blocks of 4 characters
    222                                 suspend();
    223                                 sout | ch;                                      //print character
    224                         }
    225                         sout | "  ";                                    //print block separator
    226                 }
    227                 sout | endl;                                            //print group separator
    228         }
    229 }
    230 
    231 void prt(Format & fmt, char ch) {
    232         fmt.ch = ch;
    233         resume(fmt);
    234 }
    235 
    236 int main() {
    237         Format fmt;
    238         char ch;
    239         Eof: for ( ;; ) {                                               //read until end of file
    240                 sin | ch;                                                       //read one character
    241                 if(eof(sin)) break Eof;                 //eof ?
    242                 prt(fmt, ch);                                           //push character for formatting
    243         }
    244 }
    245 \end{cfacode}
    246 \end{figure}
    247 
     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.
    248114
    249115\subsection{Alternative: Reserved keyword}
    … …  
    251117
    252118\begin{cfacode}
    253 coroutine Fibonacci {
    254         int fn; //used for communication
    255 };
    256 \end{cfacode}
    257 This 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 the programming language used. While 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.
     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.
    258125
    259126\subsection{Alternative: Lamda Objects}
    … …  
    292159      coroutine_desc * get_coroutine(T & this);
    293160};
    294 
    295 forall( dtype T | is_coroutine(T) ) void suspend(T &);
    296 forall( dtype T | is_coroutine(T) ) void resume (T &);
    297 \end{cfacode}
    298 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.
    299163
    300164\begin{center}
    … …  
    322186\end{center}
    323187
    324 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.
    325189
    326190\section{Thread Interface}\label{threads}
    … …  
    341205\end{cfacode}
    342206
    343 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
     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
    344208\begin{cfacode}
    345209        thread foo {};
    … …  
    350214\end{cfacode}
    351215
    352 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 these semantics it is trivial to write a thread type that takes a function pointer as a parameter and executes it on its stack asynchronously
    353 \begin{cfacode}
    354         typedef void (*voidFunc)(int);
     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);
    355219
    356220        thread FuncRunner {
    357221                voidFunc func;
    358                 int arg;
    359222        };
    360223
    361         void ?{}(FuncRunner & this, voidFunc inFunc, int arg) {
     224        //ctor
     225        void ?{}(FuncRunner & this, voidFunc inFunc) {
    362226                this.func = inFunc;
    363227        }
    364228
     229        //main
    365230        void main(FuncRunner & this) {
    366                 this.func( this.arg );
    367         }
    368 \end{cfacode}
    369 
    370 An 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}.
    371 
    372 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.
     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.
    373238\begin{cfacode}
    374239thread World;
    … …  
    389254\end{cfacode}
    390255
    391 This semantic has several advantages over explicit semantics: a thread is always started and stopped exaclty once and 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
    392257
    393258\begin{cfacode}
    … …  
    411276\end{cfacode}
    412277
    413 However, one of the drawbacks of this approach is that threads now always form a lattice, that is they are always destroyed in 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
    414279
    415280\begin{cfacode}
    … …  
    418283};
    419284
     285//main
    420286void main(MyThread & this) {
    421287        //...
    … …  
    425291        MyThread * long_lived;
    426292        {
     293                MyThread short_lived;
    427294                //Start a thread at the beginning of the scope
    428                 MyThread short_lived;
     295
     296                DoStuff();
    429297
    430298                //create another thread that will outlive the thread in this scope
    431299                long_lived = new MyThread;
    432300
    433                 DoStuff();
    434 
    435301                //Wait for the thread short_lived to finish
    436302        }
    437303        DoMoreStuff();
    438304
    439         //Now wait for the long_lived to finish
     305        //Now wait for the short_lived to finish
    440306        delete long_lived;
    441307}

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

    rb7778c1 rbb9d8e8  
    55% ======================================================================
    66
    7 This thesis presents the design for a set of concurrency features in \CFA. Since it is a new dialect of C, the following is a quick introduction to the language, specifically tailored to the features needed to support concurrency.
     7As mentionned in the introduction, the document presents the design for the concurrency features in \CFA. Since it is a new language here is a quick review of the language specifically tailored to the features needed to support concurrency.
    88
    9 \CFA is a extension of ISO-C and therefore supports all of the same paradigms as C. It is a non-object oriented system language, meaning most of the major abstractions have either no runtime overhead or can be opt-out easily. Like C, the basics of \CFA revolve around structures and routines, which are thin abstractions over machine code. The vast majority of the code produced by the \CFA translator respects memory-layouts and calling-conventions laid out by C. Interestingly, while \CFA is not an object-oriented language, lacking the concept of a received (e.g.: this), it does have some notion of objects\footnote{C defines the term objects as : [Where to I get the C11 reference manual?]}, most importantly construction and destruction of objects. Most of the following pieces of code can be found on the \CFA website \cite{www-cfa}
     9\CFA is a extension of ISO C and therefore supports much of the same paradigms as C. It is a non-object oriented system level language, meaning it has very most of the major abstractions have either no runtime cost or can be opt-out easily. Like C, the basics of \CFA revolve around structures and routines, which are thin abstractions over assembly. The vast majority of the code produced by a \CFA compiler respects memory-layouts and calling-conventions laid out by C. However, while \CFA is not an object-oriented language according to a strict definition. It does have some notion of objects, most importantly construction and destruction of objects. Most of the following pieces of code can be found as is on the \CFA website : \cite{www-cfa}
    1010
    1111\section{References}
    1212
    13 Like \CC, \CFA introduces references as an alternative to pointers. In regards to concurrency, the semantics difference between pointers and references are not particularly relevant but since this document uses mostly references here is a quick overview of the semantics :
     13Like \CC, \CFA introduces references as an alternative to pointers. In regards to concurrency, the semantics difference between pointers and references aren't particularly relevant but since this document uses mostly references here is a quick overview of the semantics :
    1414\begin{cfacode}
    1515int x, *p1 = &x, **p2 = &p1, ***p3 = &p2,
    1616&r1 = x,    &&r2 = r1,   &&&r3 = r2;
    17 ***p3 = 3;                                                      //change x
    18 r3    = 3;                                                      //change x, ***r3
    19 **p3  = ...;                                            //change p1
    20 *p3   = ...;                                            //change p2
    21 int y, z, & ar[3] = {x, y, z};          //initialize array of references
    22 typeof( ar[1]) p;                                       //is int, i.e., the type of referenced object
    23 typeof(&ar[1]) q;                                       //is int &, i.e., the type of reference
    24 sizeof( ar[1]) == sizeof(int);          //is true, i.e., the size of referenced object
    25 sizeof(&ar[1]) == sizeof(int *);        //is true, i.e., the size of a reference
     17***p3 = 3;                              // change x
     18r3 = 3;                                 // change x, ***r3
     19**p3 = ...;                             // change p1
     20&r3 = ...;                              // change r1, (&*)**r3
     21*p3 = ...;                              // change p2
     22&&r3 = ...;                             // change r2, (&(&*)*)*r3
     23&&&r3 = p3;                             // change r3 to p3, (&(&(&*)*)*)r3
     24int y, z, & ar[3] = { x, y, z };        // initialize array of references
     25&ar[1] = &z;                            // change reference array element
     26typeof( ar[1] ) p;                      // is int, i.e., the type of referenced object
     27typeof( &ar[1] ) q;                     // is int &, i.e., the type of reference
     28sizeof( ar[1] ) == sizeof( int );       // is true, i.e., the size of referenced object
     29sizeof( &ar[1] ) == sizeof( int *);     // is true, i.e., the size of a reference
    2630\end{cfacode}
    2731The important thing to take away from this code snippet is that references offer a handle to an object much like pointers but which is automatically derefferenced when convinient.
    … …  
    2933\section{Overloading}
    3034
    31 Another important feature of \CFA is function overloading as in Java and \CC, where routine with the same name are selected based on the numbers and type of the arguments. As well, \CFA uses the return type as part of the selection criteria, as in Ada\cite{Ada}. For routines with multiple parameters and returns, the selection is complex.
     35Another important feature \CFA has in common with \CC is function overloading :
    3236\begin{cfacode}
    33 //selection based on type and number of parameters
    34 void f(void);                   //(1)
    35 void f(char);                   //(2)
    36 void f(int, double);    //(3)
    37 f();                                    //select (1)
    38 f('a');                                 //select (2)
    39 f(3, 5.2);                              //select (3)
     37// selection based on type and number of parameters
     38void f( void );                         // (1)
     39void f( char );                         // (2)
     40void f( int, double );                  // (3)
     41f();                                    // select (1)
     42f( 'a' );                               // select (2)
     43f( 3, 5.2 );                            // select (3)
    4044
    41 //selection based on  type and number of returns
    42 char   f(int);                  //(1)
    43 double f(int);                  //(2)
    44 char   c = f(3);                //select (1)
    45 double d = f(4);                //select (2)
     45// selection based on  type and number of returns
     46char f( int );                          // (1)
     47double f( int );                        // (2)
     48[ int, double ] f( int );               // (3)
     49char c = f( 3 );                        // select (1)
     50double d = f( 4 );                      // select (2)
     51[ int, double ] t = f( 5 );             // select (3)
    4652\end{cfacode}
    47 This feature is particularly important for concurrency since the runtime system relies on creating different types to represent concurrency objects. Therefore, overloading is necessary to prevent the need for long prefixes and other naming conventions that prevent name clashes. As seen in chapter \ref{basics}, routines main is an example that benefits from overloading.
     53This feature is particularly important for concurrency since the runtime system relies on creating different types do represent concurrency objects. Therefore, overloading is necessary to prevent the need for long prefixes and other naming conventions that prevent clashes. As seen in chapter \ref{basics}, the main is an example of routine that benefits from overloading when concurrency in introduced.
    4854
    4955\section{Operators}
    5056Overloading also extends to operators. The syntax for denoting operator-overloading is to name a routine with the symbol of the operator and question marks where the arguments of the operation would be, like so :
    5157\begin{cfacode}
    52 int ++? (int op);                       //unary prefix increment
    53 int ?++ (int op);                       //unary postfix increment
    54 int ?+? (int op1, int op2);             //binary plus
    55 int ?<=?(int op1, int op2);             //binary less than
    56 int ?=? (int & op1, int op2);           //binary assignment
    57 int ?+=?(int & op1, int op2);           //binary plus-assignment
     58int ++?( int op );                      // unary prefix increment
     59int ?++( int op );                      // unary postfix increment
     60int ?+?( int op1, int op2 );            // binary plus
     61int ?<=?( int op1, int op2 );           // binary less than
     62int ?=?( int & op1, int op2 );          // binary assignment
     63int ?+=?( int & op1, int op2 );         // binary plus-assignment
    5864
    59 struct S {int i, j;};
    60 S ?+?(S op1, S op2) {                           //add two structures
    61         return (S){op1.i + op2.i, op1.j + op2.j};
     65struct S { int i, j; };
     66S ?+?( S op1, S op2 ) {                 // add two structures
     67        return (S){ op1.i + op2.i, op1.j + op2.j };
    6268}
    63 S s1 = {1, 2}, s2 = {2, 3}, s3;
    64 s3 = s1 + s2;                                           //compute sum: s3 == {2, 5}
     69S s1 = { 1, 2 }, s2 = { 2, 3 }, s3;
     70s3 = s1 + s2;                           // compute sum: s3 == { 2, 5 }
    6571\end{cfacode}
    66 While concurrency does not use operator overloading directly, this feature is more important as an introduction for the syntax of constructors.
     72
     73Since concurrency does not use operator overloading, this feature is more important as an introduction for the syntax of constructors.
    6774
    6875\section{Constructors/Destructors}
    69 Object life-time is often a challenge in concurrency. \CFA uses the approach of giving concurrent meaning to object life-time as a mean of synchronization and/or mutual exclusion. Since \CFA relies heavily on the life time of objects, constructors and destructors are a core feature required for concurrency and parallelism. \CFA uses the following syntax for constructors and destructors :
     76Object life time is often a challenge in concurrency. \CFA uses the approach of giving concurrent meaning to object life time as a mean of synchronization and/or mutual exclusion. Since \CFA relies heavily on the life time of objects, Constructors \& Destructors are a the core of the features required for concurrency and parallelism. \CFA uses the following syntax for constructors and destructors :
    7077\begin{cfacode}
    7178struct S {
    … …  
    7380        int * ia;
    7481};
    75 void ?{}(S & s, int asize) {    //constructor operator
    76         s.size = asize;                         //initialize fields
    77         s.ia = calloc(size, sizeof(S));
     82void ?{}( S & s, int asize ) with s {   // constructor operator
     83        size = asize;                   // initialize fields
     84        ia = calloc( size, sizeof( S ) );
    7885}
    79 void ^?{}(S & s) {                              //destructor operator
    80         free(ia);                                       //de-initialization fields
     86void ^?{}( S & s ) with s {             // destructor operator
     87        free( ia );                     // de-initialization fields
    8188}
    8289int main() {
    83         S x = {10}, y = {100};          //implict calls: ?{}(x, 10), ?{}(y, 100)
    84         ...                                                     //use x and y
    85         ^x{};  ^y{};                            //explicit calls to de-initialize
    86         x{20};  y{200};                         //explicit calls to reinitialize
    87         ...                                                     //reuse x and y
    88 }                                                               //implict calls: ^?{}(y), ^?{}(x)
     90        S x = { 10 }, y = { 100 };      // implict calls: ?{}( x, 10 ), ?{}( y, 100 )
     91        ...                             // use x and y
     92        ^x{};  ^y{};                    // explicit calls to de-initialize
     93        x{ 20 };  y{ 200 };             // explicit calls to reinitialize
     94        ...                             // reuse x and y
     95}                                       // implict calls: ^?{}( y ), ^?{}( x )
    8996\end{cfacode}
    90 The language guarantees that every object and all their fields are constructed. Like \CC, construction of an object is automatically done on allocation and destruction of the object is done on deallocation. Allocation and deallocation can occur on the stack or on the heap.
    91 \begin{cfacode}
    92 {
    93         struct S s = {10};      //allocation, call constructor
    94         ...
    95 }                                               //deallocation, call destructor
    96 struct S * s = new();   //allocation, call constructor
    97 ...
    98 delete(s);                              //deallocation, call destructor
    99 \end{cfacode}
    100 Note that like \CC, \CFA introduces \code{new} and \code{delete}, which behave like \code{malloc} and \code{free} in addition to constructing and destructing objects, after calling \code{malloc} and before calling \code{free} respectively.
     97The language guarantees that every object and all their fields are constructed. Like \CC construction is automatically done on declaration and destruction done when the declared variables reach the end of its scope.
    10198
    102 \section{Parametric Polymorphism}
    103 Routines in \CFA can also be reused for multiple types. This is done using the \code{forall} clause which gives \CFA it's name. \code{forall} clauses allow seperatly compiled routines to support generic usage over multiple types. For example, the following sum function will work for any type which support construction from 0 and addition :
    104 \begin{cfacode}
    105 //constraint type, 0 and +
    106 forall(otype T | { void ?{}(T *, zero_t); T ?+?(T, T); })
    107 T sum(T a[ ], size_t size) {
    108         T total = 0;                            //construct T from 0
    109         for(size_t i = 0; i < size; i++)
    110                 total = total + a[i];   //select appropriate +
    111         return total;
    112 }
    113 
    114 S sa[5];
    115 int i = sum(sa, 5);                             //use S's 0 construction and +
    116 \end{cfacode}
    117 
    118 Since writing constraints on types can become cumbersome for more constrained functions, \CFA also has the concept of traits. Traits are named collection of constraints which can be used both instead and in addition to regular constraints:
    119 \begin{cfacode}
    120 trait sumable( otype T ) {
    121         void ?{}(T *, zero_t);          //constructor from 0 literal
    122         T ?+?(T, T);                            //assortment of additions
    123         T ?+=?(T *, T);
    124         T ++?(T *);
    125         T ?++(T *);
    126 };
    127 forall( otype T | sumable(T) )  //use trait
    128 T sum(T a[], size_t size);
    129 \end{cfacode}
    130 
    131 \section{with Clause/Statement}
    132 Since \CFA lacks the concept of a receiver, certain functions end-up needing to repeat variable names often, to solve this \CFA offers the \code{with} statement which opens an aggregate scope making its fields directly accessible (like Pascal).
    133 \begin{cfacode}
    134 struct S { int i, j; };
    135 int mem(S & this) with this             //with clause
    136         i = 1;                                          //this->i
    137         j = 2;                                          //this->j
    138 }
    139 int foo() {
    140         struct S1 { ... } s1;
    141         struct S2 { ... } s2;
    142         with s1                                         //with statement
    143         {
    144                 //access fields of s1
    145                 //without qualification
    146                 with s2                                 //nesting
    147                 {
    148                         //access fields of s1 and s2
    149                         //without qualification
    150                 }
    151         }
    152         with s1, s2                             //scopes open in parallel
    153         {
    154                 //access fields of s1 and s2
    155                 //without qualification
    156         }
    157 }
    158 \end{cfacode}
    159 
    160 For more information on \CFA see \cite{cforall-ug,rob-thesis,www-cfa}.
     99For more information see \cite{cforall-ug,rob-thesis,www-cfa}.

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

    rb7778c1 rbb9d8e8  
    700700\end{tabular}
    701701\end{center}
    702 This method is more constrained and explicit, which may help users tone down the undeterministic nature of concurrency. Indeed, as the following examples demonstrates, external scheduling allows users to wait for events from other threads without the concern of unrelated events occuring. External scheduling can generally be done either in terms of control flow (e.g., \uC) or in terms of data (e.g. Go). Of course, both of these paradigms have their own strenghts and weaknesses but for this project control-flow semantics were chosen to stay consistent with the rest of the languages semantics. Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multi-monitor routines. The previous example shows a simple use \code{_Accept} versus \code{wait}/\code{signal} and its advantages. Note that while other languages often use \code{accept} as the core external scheduling keyword, \CFA uses \code{waitfor} to prevent name collisions with existing socket \acrshort{api}s.
     702This method is more constrained and explicit, which may help users tone down the undeterministic nature of concurrency. Indeed, as the following examples demonstrates, external scheduling allows users to wait for events from other threads without the concern of unrelated events occuring. External scheduling can generally be done either in terms of control flow (e.g., \uC) or in terms of data (e.g. Go). Of course, both of these paradigms have their own strenghts and weaknesses but for this project control-flow semantics were chosen to stay consistent with the rest of the languages semantics. Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multi-monitor routines. The previous example shows a simple use \code{_Accept} versus \code{wait}/\code{signal} and its advantages. Note that while other languages often use \code{accept} as the core external scheduling keyword, \CFA uses \code{waitfor} to prevent name collisions with existing socket APIs.
    703703
    704704In the case of internal scheduling, the call to \code{wait} only guarantees that \code{V} is the last routine to access the monitor. This entails that the routine \code{V} may have acquired mutual exclusion several times while routine \code{P} was waiting. On the other hand, external scheduling guarantees that while routine \code{P} was waiting, no routine other than \code{V} could acquire the monitor.

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

    rb7778c1 rbb9d8e8  
    33% ======================================================================
    44
    5 This thesis provides a minimal concurrency \acrshort{api} that is simple, efficient and can be reused to build higher-level features. The simplest possible concurrency system is a thread and a lock but this low-level approach is hard to master. An easier approach for users is to support higher-level constructs as the basis of concurrency. Indeed, for highly productive concurrent programming, high-level approaches are much more popular~\cite{HPP:Study}. Examples are task based, message passing and implicit threading. The high-level approach and its minimal \acrshort{api} are tested in a dialect of C, call \CFA. [Is there value to say that this thesis is also an early definition of the \CFA language and library in regards to concurrency?]
     5This proposal provides a minimal concurrency API that is simple, efficient and can be reused to build higher-level features. The simplest possible concurrency system is a thread and a lock but this low-level approach is hard to master. An easier approach for users is to support higher-level constructs as the basis of the concurrency, in \CFA. Indeed, for highly productive concurrent programming, high-level approaches are much more popular~\cite{HPP:Study}. Examples are task based, message passing and implicit threading. Therefore a high-level approach is adopted in \CFA
    66
    7 There are actually two problems that need to be solved in the design of concurrency for a programming language: which concurrency and which parallelism tools are available to the programmer. While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite{Buhr05a}. Concurrency tools need to handle mutual exclusion and synchronization, while parallelism tools are about performance, cost and resource utilization.
     7There are actually two problems that need to be solved in the design of concurrency for a programming language: which concurrency and which parallelism tools are available to the programmers. While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite{Buhr05a}. Concurrency tools need to handle mutual exclusion and synchronization, while parallelism tools are about performance, cost and resource utilization.

  • doc/proposals/concurrency/thesis.tex

    rb7778c1 rbb9d8e8  
    103103\input{parallelism}
    104104
    105 \input{internals}
    106 
    107105\input{together}
    108106

  • doc/proposals/concurrency/version

    rb7778c1 rbb9d8e8  
    1 0.10.95
     10.10.2
Note: See TracChangeset for help on using the changeset viewer.