Ignore:
Timestamp:
Jun 16, 2017, 12:01:25 PM (7 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
1a42132
Parents:
816d61c (diff), 974bcdd (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg2:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r816d61c rf13ee31  
    77
    88\section{Basics of concurrency}
    9 At its core, concurrency is based on having multiple call stacks and potentially multiple threads of execution for these stacks. Concurrency alone 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 but in any case a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to be present, the only feature missing is preemption. Indeed, concurrency challenges appear with the lack of determinism. Guaranteeing mutual-exclusion or synchronisation are simply ways of limiting the lack of determinism in the system. A scheduler introduces order of execution uncertainty while preemption introduces incertainty about when 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 the user the illusion that hundred of tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as little determinism as correctness will allow\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.
    1010
    1111\section{\protect\CFA 's Thread Building Blocks}
    12 % As a system-level language, \CFA should offer both performance and flexibilty as its primary goals, simplicity and user-friendliness being a secondary concern. Therefore, the core of parallelism in \CFA should prioritize power and efficiency. With this said, deconstructing popular paradigms in order to get simple building blocks yields \glspl{uthread} as the core parallelism block. \Glspl{pool} and other parallelism paradigms can then be built on top of the underlying threading model.
    13 One of the important features that is missing to C is threading. On modern architectures, the lack of threading is becoming less and less forgivable\cite{Sutter05, Sutter05b} and therefore any modern programming language should 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 an a way that is as natural as possible to programmers used to imperative languages. And being a system level language means programmers will expect to be able to choose precisely which features they need and which cost they are willing to pay.
    14 
    15 \section{Coroutines A stepping stone}\label{coroutine}
    16 While 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 the concurrency system. Indeed, while having nothing todo with parallelism and arguably little to do with concurrency, coroutines need to deal with context-switchs and 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}.
     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.
     13
     14\section{Coroutines: A stepping stone}\label{coroutine}
     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 todo with parallelism and arguably little to do with concurrency, coroutines need to deal with context-switchs and 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}.
    1716
    1817Here is an example of a solution to the fibonnaci problem using \CFA coroutines:
    … …  
    2625        }
    2726
     27        // main automacically called on first resume
    2828        void main(Fibonacci* this) {
    2929                int fn1, fn2;           // retained between resumes
    … …  
    5959
    6060\subsection{Construction}
    61 One important design challenge for coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run some code after the user-constructor runs. In the case of the coroutines this challenge is simpler since there is no loss of determinism brough by preemption or scheduling, however, the underlying challenge remains the same for coroutines and threads.
    62 
    63 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 (Obviously we only solve cases where these two statements don't conflict). There are several solutions to this problem but the chosen options effectively forces the design of the coroutine.
    64 
    65 Furthermore, \CFA faces an extra challenge which is that polymorphique routines rely on 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:
     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.
     64
     65Furthermore, \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:
    6666
    6767\begin{cfacode}
    … …  
    7878}
    7979\end{cfacode}
    80 Indeed, the generated C code\footnote{Code trimmed down for brevity} shows that a local thunk is created in order to hold type information:
     80The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information:
    8181
    8282\begin{ccode}
    … …  
    9595}
    9696\end{ccode}
    97 The problem in the this example is that there 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.
     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.
    9898
    9999\subsection{Alternative: Composition}
    100 One solution to this challenge would be to use inheritence,
     100One solution to this challenge would be to use composition/containement,
    101101
    102102\begin{cfacode}
    103103        struct Fibonacci {
    104104              int fn; // used for communication
    105               coroutine c;
     105              coroutine c; //composition
    106106        };
    107107
    … …  
    111111        }
    112112\end{cfacode}
    113 
    114 There 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 we use a parameter or a virtual pointer, this means the coroutine data must be made larger to store a value that is actually a compile time constant (The address of the main routine). The second problem which is both subtle but significant, is that now users can get the initialisation order of there coroutines wrong. Indeed, every field of a \CFA struct will be constructed but in the order of declaration, unless users explicitly write otherwise. This means that users who forget to initialize a the coroutine at the right time 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.
     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.
    115114
    116115\subsection{Alternative: Reserved keyword}
    … …  
    122121        };
    123122\end{cfacode}
    124 
    125123This 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.
    126124While 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.
    … …  
    128126\subsection{Alternative: Lamda Objects}
    129127
    130 For coroutines as for threads, many implementations are based on routine pointers or function objects\cit. For example, Boost implements coroutines in terms of four functor object types \code{asymmetric_coroutine<>::pull_type}, \code{asymmetric_coroutine<>::push_type}, \code{symmetric_coroutine<>::call_type}, \code{symmetric_coroutine<>::yield_type}. Often, the canonical threading paradigm in languages is based on function pointers, pthread being one of the most well known example. The main problem of these 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 and \CFA and solves several issues, added support for routine/lambda based coroutines adds very little.
    131 
    132 \subsection{Trait based coroutines}
    133 
    134 Finally the underlying approach, which is the one closest to \CFA idioms, is to use trait-based lazy coroutines. This approach defines a coroutine as \say{anything that \say{satisfies the trait \code{is_coroutine} and is used as a coroutine} is a coroutine}.
     128For coroutines as for threads, many implementations are based on routine pointers or function objects\cit. For example, Boost implements coroutines in terms of four functor object types:
     129\begin{cfacode}
     130asymmetric_coroutine<>::pull_type
     131asymmetric_coroutine<>::push_type
     132symmetric_coroutine<>::call_type
     133symmetric_coroutine<>::yield_type
     134\end{cfacode}
     135Often, 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.
     136
     137A variation of this would be to use an simple function pointer in the same way pthread does for threads :
     138\begin{cfacode}
     139void foo( coroutine_t cid, void * arg ) {
     140        int * value = (int *)arg;
     141        //Coroutine body
     142}
     143
     144int main() {
     145        int value = 0;
     146        coroutine_t cid = coroutine_create( &foo, (void*)&value );
     147        coroutine_resume( &cid );
     148}
     149\end{cfacode}
     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.
     151
     152\subsection{Alternative: Trait-based coroutines}
     153
     154Finally the underlying approach, which is the one closest to \CFA idioms, is to use trait-based lazy coroutines. This approach defines a coroutine as anything that satisfies the trait \code{is_coroutine} and is used as a coroutine is a coroutine.
    135155
    136156\begin{cfacode}
    … …  
    140160};
    141161\end{cfacode}
    142 
    143 This entails that 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.
     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.
     163
     164\begin{center}
     165\begin{tabular}{c c c}
     166\begin{cfacode}[tabsize=3]
     167coroutine MyCoroutine {
     168        int someValue;
     169};
     170\end{cfacode} & == & \begin{cfacode}[tabsize=3]
     171struct MyCoroutine {
     172        int someValue;
     173        coroutine_desc __cor;
     174};
     175
     176static inline
     177coroutine_desc * get_coroutine(
     178        struct MyCoroutine * this
     179) {
     180        return &this->__cor;
     181}
     182
     183void main(struct MyCoroutine * this);
     184\end{cfacode}
     185\end{tabular}
     186\end{center}
     187
    144188
    145189
    146190\section{Thread Interface}\label{threads}
    147 The basic building blocks of multi-threading in \CFA are \glspl{cfathread}. By default these are implemented as \glspl{uthread}, and as such, offer a flexible and lightweight threading interface (lightweight compared to \glspl{kthread}). A thread can be declared using a SUE declaration \code{thread} as follows:
     191The basic building blocks of multi-threading in \CFA are \glspl{cfathread}. Both use and kernel threads are supported, where user threads are the concurrency mechanism and kernel threads are the parallel mechanism. User threads offer a flexible and lightweight interface. A thread can be declared using a struct declaration \code{thread} as follows:
    148192
    149193\begin{cfacode}
    … …  
    151195\end{cfacode}
    152196
    153 Like for coroutines, the keyword is a thin wrapper arount a \CFA trait:
     197As for coroutines, the keyword is a thin wrapper arount a \CFA trait:
    154198
    155199\begin{cfacode}
    … …  
    170214\end{cfacode}
    171215
    172 In this example, threads of type \code{foo} will start there execution in the \code{void main(foo*)} routine which in this case prints \code{"Hello World!"}. While this proposoal encourages this approach which enforces strongly type 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
     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
    173217\begin{cfacode}
    174218        typedef void (*voidFunc)(void);
    … …  
    201245void main() {
    202246        World w;
    203         //Thread run forks here
    204 
    205         //Printing "Hello " and "World!" will be run concurrently
     247        //Thread forks here
     248
     249        //Printing "Hello " and "World!" are run concurrently
    206250        sout | "Hello " | endl;
    207251
    … …  
    210254\end{cfacode}
    211255
    212 This 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. However, 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. While this seems like a significant limitation, existing \CFA semantics can solve this problem. Indeed, using dynamic allocation to create threads will naturally let threads outlive the scope in which the thread was created much like dynamically allocating memory will let objects outlive the scope in which thy were created
     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
     257
     258\begin{cfacode}
     259        thread MyThread {
     260                //...
     261        };
     262
     263        //main
     264        void main(MyThread* this) {
     265                //...
     266        }
     267
     268        void foo() {
     269                MyThread thrds[10];
     270                //Start 10 threads at the beginning of the scope
     271
     272                DoStuff();
     273
     274                //Wait for the 10 threads to finish
     275        }
     276\end{cfacode}
     277
     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 os 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
    213279
    214280\begin{cfacode}
    … …  
    241307        }
    242308\end{cfacode}
    243 
    244 Another advantage of this semantic is that it naturally scale to multiple threads meaning basic synchronisation is very simple
    245 
    246 \begin{cfacode}
    247         thread MyThread {
    248                 //...
    249         };
    250 
    251         //main
    252         void main(MyThread* this) {
    253                 //...
    254         }
    255 
    256         void foo() {
    257                 MyThread thrds[10];
    258                 //Start 10 threads at the beginning of the scope
    259 
    260                 DoStuff();
    261 
    262                 //Wait for the 10 threads to finish
    263         }
    264 \end{cfacode}
Note: See TracChangeset for help on using the changeset viewer.