Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    rcf966b5 rb3ffb61  
    1111Execution 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.
    1212
    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, stack-full 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 (a.k.a non-preemptive scheduling). The oracle/scheduler can either be a stack-less or stack-full 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 synchronization are ways of limiting non-determinism in a concurrent system. Now it is important to understand that uncertainty is desirable; 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.
     13Therefore, 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 (a.k.a non-preemptive scheduling). 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
     15A 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.
    1616
    1717\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.
     18One 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.
    1919
    2020\section{Coroutines: A stepping stone}\label{coroutine}
    2121While 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}.
    2222
    23 \begin{table}
     23\begin{figure}
    2424\begin{center}
    2525\begin{tabular}{c @{\hskip 0.025in}|@{\hskip 0.025in} c @{\hskip 0.025in}|@{\hskip 0.025in} c}
    … …  
    6262void fibonacci_array(
    6363        int n,
    64         int* array
     64        int * array
    6565) {
    6666        int f1 = 0; int f2 = 1;
    … …  
    9999
    100100int fibonacci_state(
    101         Iterator_t* it
     101        Iterator_t * it
    102102) {
    103103        int f;
    … …  
    129129\end{tabular}
    130130\end{center}
    131 \caption{Different implementations of a Fibonacci sequence generator in C.},
     131\caption{Different implementations of a fibonacci sequence generator in C.}
    132132\label{lst:fibonacci-c}
    133 \end{table}
    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. Table \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 Listing \ref{lst:fibonacci-cfa} is an example of a solution to the Fibonacci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the next 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 implementation is very similar to the \code{fibonacci_func} example.
     133\end{figure}
     134
     135A 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
     137Figure \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.
    138138
    139139\begin{figure}
    140 \begin{cfacode}[caption={Implementation of Fibonacci using coroutines},label={lst:fibonacci-cfa}]
     140\begin{cfacode}
    141141coroutine Fibonacci {
    142142        int fn; //used for communication
    143143};
    144144
    145 void ?{}(Fibonacci& this) { //constructor
     145void ?{}(Fibonacci & this) { //constructor
    146146        this.fn = 0;
    147147}
    148148
    149 //main automatically called on first resume
    150 void main(Fibonacci& this) with (this) {
     149//main automacically called on first resume
     150void main(Fibonacci & this) with (this) {
    151151        int fn1, fn2;           //retained between resumes
    152152        fn  = 0;
    … …  
    167167}
    168168
    169 int next(Fibonacci& this) {
     169int next(Fibonacci & this) {
    170170        resume(this); //transfer to last suspend
    171171        return this.fn;
    … …  
    179179}
    180180\end{cfacode}
     181\caption{Implementation of fibonacci using coroutines}
     182\label{lst:fibonacci-cfa}
    181183\end{figure}
    182184
    183 Listing \ref{lst:fmt-line} shows the \code{Format} coroutine for restructuring text into groups of character 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.
     185Figure \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.
    184186
    185187\begin{figure}
    186 \begin{cfacode}[tabsize=3,caption={Formatting text into lines of 5 blocks of 4 characters.},label={lst:fmt-line}]
     188\begin{cfacode}[tabsize=3]
    187189//format characters into blocks of 4 and groups of 5 blocks per line
    188190coroutine Format {
    … …  
    191193};
    192194
    193 void  ?{}(Format& fmt) {
     195void  ?{}(Format & fmt) {
    194196        resume( fmt );                                                  //prime (start) coroutine
    195197}
    196198
    197 void ^?{}(Format& fmt) with fmt {
     199void ^?{}(Format & fmt) with fmt {
    198200        if ( fmt.g != 0 || fmt.b != 0 )
    199201        sout | endl;
    200202}
    201203
    202 void main(Format& fmt) with fmt {
     204void main(Format & fmt) with fmt {
    203205        for ( ;; ) {                                                    //for as many characters
    204206                for(g = 0; g < 5; g++) {                //groups of 5 blocks
    … …  
    228230}
    229231\end{cfacode}
     232\caption{Formatting text into lines of 5 blocks of 4 characters.}
     233\label{lst:fmt-line}
    230234\end{figure}
    231235
    232236\subsection{Construction}
    233 One important design challenge for implementing 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.
    234 
    235 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. There are several solutions to this problem but the chosen options effectively forces the design of the coroutine.
     237One 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
     239The 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.
    236240
    237241Furthermore, \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:
    … …  
    254258
    255259\begin{ccode}
    256 extern void async(/* omitted */, void (*func)(void*), void* obj);
    257 
    258 void noop(/* omitted */, void* obj){}
     260extern void async(/* omitted */, void (*func)(void *), void *obj);
     261
     262void noop(/* omitted */, void *obj){}
    259263
    260264void bar(){
    261265        int a;
    262         void _thunk0(int* _p0){
     266        void _thunk0(int *_p0){
    263267                /* omitted */
    264268                noop(/* omitted */, _p0);
    265269        }
    266270        /* omitted */
    267         async(/* omitted */, ((void (*)(void*))(&_thunk0)), (&a));
     271        async(/* omitted */, ((void (*)(void *))(&_thunk0)), (&a));
    268272}
    269273\end{ccode}
    270 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.
     274The 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.
    271275
    272276\subsection{Alternative: Composition}
    273 One solution to this challenge is to use composition/containment, where coroutine fields are added to manage the coroutine.
     277One solution to this challenge is to use composition/containement, where coroutine fields are added to manage the coroutine.
    274278
    275279\begin{cfacode}
    … …  
    279283};
    280284
    281 void FibMain(void*) {
     285void FibMain(void *) {
    282286        //...
    283287}
    284288
    285 void ?{}(Fibonacci& this) {
     289void ?{}(Fibonacci & this) {
    286290        this.fn = 0;
    287291        //Call constructor to initialize coroutine
    … …  
    289293}
    290294\end{cfacode}
    291 The downside of this approach is that users need to correctly construct the coroutine handle before using it. Like any other objects, the user must carefully choose construction order to prevent usage of objects not yet constructed. 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.
     295The 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.
    292296
    293297\subsection{Alternative: Reserved keyword}
    … …  
    299303};
    300304\end{cfacode}
    301 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 wanting 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.
    302 
    303 \subsection{Alternative: Lambda Objects}
    304 
    305 For coroutines as for threads, many implementations are based on routine pointers or function objects~\cite{Butenhof97, ANSI14:C++, MS:VisualC++, BoostCoroutines15}. For example, Boost implements coroutines in terms of four functor object types:
     305The \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.
     306
     307\subsection{Alternative: Lamda Objects}
     308
     309For coroutines as for threads, many implementations are based on routine pointers or function objects\cite{Butenhof97, ANSI14:C++, MS:VisualC++, BoostCoroutines15}. For example, Boost implements coroutines in terms of four functor object types:
    306310\begin{cfacode}
    307311asymmetric_coroutine<>::pull_type
    … …  
    314318A variation of this would be to use a simple function pointer in the same way pthread does for threads :
    315319\begin{cfacode}
    316 void foo( coroutine_t cid, void* arg ) {
    317         int* value = (int*)arg;
     320void foo( coroutine_t cid, void * arg ) {
     321        int * value = (int *)arg;
    318322        //Coroutine body
    319323}
    … …  
    325329}
    326330\end{cfacode}
    327 This semantics is more common for thread interfaces but coroutines work equally well. As discussed in section \ref{threads}, this approach is superseded by static approaches in terms of expressivity.
     331This 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.
    328332
    329333\subsection{Alternative: Trait-based coroutines}
    … …  
    333337\begin{cfacode}
    334338trait is_coroutine(dtype T) {
    335       void main(T& this);
    336       coroutine_desc* get_coroutine(T& this);
    337 };
    338 
    339 forall( dtype T | is_coroutine(T) ) void suspend(T&);
    340 forall( dtype T | is_coroutine(T) ) void resume (T&);
    341 \end{cfacode}
    342 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 implement the main routine.
     339      void main(T & this);
     340      coroutine_desc * get_coroutine(T & this);
     341};
     342
     343forall( dtype T | is_coroutine(T) ) void suspend(T &);
     344forall( dtype T | is_coroutine(T) ) void resume (T &);
     345\end{cfacode}
     346This 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.
    343347
    344348\begin{center}
    … …  
    355359
    356360static inline
    357 coroutine_desc* get_coroutine(
    358         struct MyCoroutine& this
     361coroutine_desc * get_coroutine(
     362        struct MyCoroutine & this
    359363) {
    360364        return &this.__cor;
    361365}
    362366
    363 void main(struct MyCoroutine* this);
     367void main(struct MyCoroutine * this);
    364368\end{cfacode}
    365369\end{tabular}
    366370\end{center}
    367371
    368 The combination of these two approaches allows users new to coroutining and concurrency to have an easy and concise specification, while more advanced users have tighter control on memory layout and initialization.
     372The 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.
    369373
    370374\section{Thread Interface}\label{threads}
    … …  
    375379\end{cfacode}
    376380
    377 As for coroutines, the keyword is a thin wrapper around a \CFA trait:
     381As for coroutines, the keyword is a thin wrapper arount a \CFA trait:
    378382
    379383\begin{cfacode}
    … …  
    385389\end{cfacode}
    386390
    387 Obviously, for this thread implementation to be useful 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 supersedes 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
     391Obviously, 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
    388392\begin{cfacode}
    389393thread foo {};
    … …  
    412416        this.func( this.arg );
    413417}
    414 
    415 void hello(/*unused*/ int) {
    416         sout | "Hello World!" | endl;
    417 }
    418 
    419 int main() {
    420         FuncRunner f = {hello, 42};
    421         return 0'
    422 }
    423418\end{cfacode}
    424419
    … …  
    444439\end{cfacode}
    445440
    446 This semantic has several advantages over explicit semantics: a thread is always started and stopped exactly once, users cannot make any programming errors, and it naturally scales to multiple threads meaning basic synchronization is very simple.
     441This 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.
    447442
    448443\begin{cfacode}
    … …  
    452447
    453448//main
    454 void main(MyThread& this) {
     449void main(MyThread & this) {
    455450        //...
    456451}
    … …  
    466461\end{cfacode}
    467462
    468 However, one of the drawbacks of this approach is that threads always form a lattice, i.e., 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.
     463However, 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.
    469464
    470465\begin{cfacode}
    … …  
    473468};
    474469
    475 void main(MyThread& this) {
     470void main(MyThread & this) {
    476471        //...
    477472}
    478473
    479474void foo() {
    480         MyThread* long_lived;
     475        MyThread * long_lived;
    481476        {
    482477                //Start a thread at the beginning of the scope
Note: See TracChangeset for help on using the changeset viewer.