Changeset a2ea829 for doc/proposals/concurrency/text/basics.tex
- Timestamp:
- Nov 6, 2017, 12:23:13 PM (7 years ago)
- 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:
- b9d0fb6
- Parents:
- bbeb908
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/proposals/concurrency/text/basics.tex
rbbeb908 ra2ea829 9 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 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. 11 Execution with a single thread and multiple stacks where the thread is self-scheduling deterministically across the stacks is called coroutining. Execution with a single and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread perspective) across the stacks is called concurrency. 12 13 Therefore, a minimal concurrency system can be achieved by creating coroutines, which instead of context switching among each other, always ask an oracle where to context switch next. While coroutines can execute on the caller's stack-frame, stackfull coroutines allow full generality and are sufficient as the basis for concurrency. The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model \cit. The oracle/scheduler can either be a stackless or stackfull entity and correspondingly require one or two context switches to run a different coroutine. In any case, a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to occur, the only feature missing is preemption. 14 15 A scheduler introduces order of execution uncertainty, while preemption introduces uncertainty about where context-switches occur. Mutual-exclusion and synchronisation are ways of limiting non-determinism in a concurrent system. Now it is important to understand that uncertainty is desireable; uncertainty can be used by runtime systems to significantly increase performance and is often the basis of giving a user the illusion that tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows\cit. 14 16 15 17 \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.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. 17 19 18 20 \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. 21 While the main focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are actually a significant building block of a concurrency system. Coroutines need to deal with context-switches and other context-management operations. Therefore, this proposal includes coroutines both as an intermediate step for the implementation of threads, and a first class feature of \CFA. Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant. The core \acrshort{api} of coroutines revolve around two features: independent call stacks and \code{suspend}/\code{resume}. 22 22 23 \begin{figure} 23 \label{fig:fibonacci-c}24 24 \begin{center} 25 25 \begin{tabular}{c @{\hskip 0.025in}|@{\hskip 0.025in} c @{\hskip 0.025in}|@{\hskip 0.025in} c} … … 45 45 } 46 46 } 47 48 int main() { 49 void print_fib(int n) { 50 printf("%d\n", n); 51 } 52 53 fibonacci_func( 54 10, print_fib 55 ); 56 57 58 59 } 47 60 \end{ccode}&\begin{ccode}[tabsize=2] 48 61 //Using output array … … 62 75 f2 = next; 63 76 } 64 *array = next; 65 array++; 66 } 77 array[i] = next; 78 } 79 } 80 81 82 int main() { 83 int a[10]; 84 85 fibonacci_func( 86 10, a 87 ); 88 89 for(int i=0;i<10;i++){ 90 printf("%d\n", a[i]); 91 } 92 67 93 } 68 94 \end{ccode}&\begin{ccode}[tabsize=2] … … 70 96 typedef struct { 71 97 int f1, f2; 72 } iterator_t;98 } Iterator_t; 73 99 74 100 int fibonacci_state( 75 iterator_t * it101 Iterator_t * it 76 102 ) { 77 103 int f; 78 104 f = it->f1 + it->f2; 79 105 it->f2 = it->f1; 80 it->f1 = f;106 it->f1 = max(f,1); 81 107 return f; 82 108 } … … 87 113 88 114 115 116 int main() { 117 Iterator_t it={0,0}; 118 119 for(int i=0;i<10;i++){ 120 printf("%d\n", 121 fibonacci_state( 122 &it 123 ); 124 ); 125 } 126 127 } 89 128 \end{ccode} 90 129 \end{tabular} 91 130 \end{center} 92 131 \caption{Different implementations of a fibonacci sequence generator in C.} 132 \label{lst:fibonacci-c} 93 133 \end{figure} 94 134 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. 135 A good example of a problem made easier with coroutines is generators, like the fibonacci sequence. This problem comes with the challenge of decoupling how a sequence is generated and how it is used. Figure \ref{lst:fibonacci-c} shows conventional approaches to writing generators in C. All three of these approach suffer from strong coupling. The left and center approaches require that the generator have knowledge of how the sequence is used, while the rightmost approach requires holding internal state between calls on behalf of the generator and makes it much harder to handle corner cases like the Fibonacci seed. 136 137 Figure \ref{lst:fibonacci-cfa} is an example of a solution to the fibonnaci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the generation. This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used. Indeed, this version is as easy to use as the \code{fibonacci_state} solution, while the imlpementation is very similar to the \code{fibonacci_func} example. 97 138 98 139 \begin{figure} 99 \label{fig:fibonacci-cfa}100 140 \begin{cfacode} 101 141 coroutine Fibonacci { … … 108 148 109 149 //main automacically called on first resume 110 void main(Fibonacci & this) {150 void main(Fibonacci & this) with (this) { 111 151 int fn1, fn2; //retained between resumes 112 this.fn= 0;113 fn1 = this.fn;152 fn = 0; 153 fn1 = fn; 114 154 suspend(this); //return to last resume 115 155 116 this.fn= 1;156 fn = 1; 117 157 fn2 = fn1; 118 fn1 = this.fn;158 fn1 = fn; 119 159 suspend(this); //return to last resume 120 160 121 161 for ( ;; ) { 122 this.fn= fn1 + fn2;162 fn = fn1 + fn2; 123 163 fn2 = fn1; 124 fn1 = this.fn;164 fn1 = fn; 125 165 suspend(this); //return to last resume 126 166 } … … 140 180 \end{cfacode} 141 181 \caption{Implementation of fibonacci using coroutines} 182 \label{lst:fibonacci-cfa} 142 183 \end{figure} 143 184 144 \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. 148 149 Furthermore, \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: 150 151 \begin{cfacode} 152 //async: Runs function asynchronously on another thread 153 forall(otype T) 154 extern void async(void (*func)(T*), T* obj); 155 156 forall(otype T) 157 void noop(T *) {} 158 159 void bar() { 160 int a; 161 async(noop, &a); 162 } 163 \end{cfacode} 164 165 The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information: 166 167 \begin{ccode} 168 extern void async(/* omitted */, void (*func)(void *), void *obj); 169 170 void noop(/* omitted */, void *obj){} 171 172 void bar(){ 173 int a; 174 void _thunk0(int *_p0){ 175 /* omitted */ 176 noop(/* omitted */, _p0); 177 } 178 /* omitted */ 179 async(/* omitted */, ((void (*)(void *))(&_thunk0)), (&a)); 180 } 181 \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. 183 184 \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. 185 Figure \ref{lst:fmt-line} shows the \code{Format} coroutine which rearranges text in order to group characters into blocks of fixed size. The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor. 186 199 187 \begin{figure} 200 \label{fig:fmt-line}201 188 \begin{cfacode}[tabsize=3] 202 189 //format characters into blocks of 4 and groups of 5 blocks per line … … 244 231 \end{cfacode} 245 232 \caption{Formatting text into lines of 5 blocks of 4 characters.} 233 \label{lst:fmt-line} 246 234 \end{figure} 247 235 236 \subsection{Construction} 237 One important design challenge for coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run code after the user-constructor runs to connect the fully constructed object into the system. In the case of coroutines, this challenge is simpler since there is no non-determinism from preemption or scheduling. However, the underlying challenge remains the same for coroutines and threads. 238 239 The runtime system needs to create the coroutine's stack and more importantly prepare it for the first resumption. The timing of the creation is non-trivial since users both expect to have fully constructed objects once execution enters the coroutine main and to be able to resume the coroutine from the constructor. As regular objects, constructors can leak coroutines before they are ready. There are several solutions to this problem but the chosen options effectively forces the design of the coroutine. 240 241 Furthermore, \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: 242 243 \begin{cfacode} 244 //async: Runs function asynchronously on another thread 245 forall(otype T) 246 extern void async(void (*func)(T*), T* obj); 247 248 forall(otype T) 249 void noop(T*) {} 250 251 void bar() { 252 int a; 253 async(noop, &a); //start thread running noop with argument a 254 } 255 \end{cfacode} 256 257 The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information: 258 259 \begin{ccode} 260 extern void async(/* omitted */, void (*func)(void *), void *obj); 261 262 void noop(/* omitted */, void *obj){} 263 264 void bar(){ 265 int a; 266 void _thunk0(int *_p0){ 267 /* omitted */ 268 noop(/* omitted */, _p0); 269 } 270 /* omitted */ 271 async(/* omitted */, ((void (*)(void *))(&_thunk0)), (&a)); 272 } 273 \end{ccode} 274 The problem in this example is a storage management issue, the function pointer \code{_thunk0} is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes undefined behavior; i.e., the stack-based thunk being destroyed before it can be used. This challenge is an extension of challenges that come with second-class routines. Indeed, GCC nested routines also have the limitation that nested routine cannot be passed outside of the declaration scope. The case of coroutines and threads is simply an extension of this problem to multiple call-stacks. 275 276 \subsection{Alternative: Composition} 277 One solution to this challenge is to use composition/containement, where coroutine fields are added to manage the coroutine. 278 279 \begin{cfacode} 280 struct Fibonacci { 281 int fn; //used for communication 282 coroutine c; //composition 283 }; 284 285 void FibMain(void *) { 286 //... 287 } 288 289 void ?{}(Fibonacci & this) { 290 this.fn = 0; 291 //Call constructor to initialize coroutine 292 (this.c){myMain}; 293 } 294 \end{cfacode} 295 The downside of this approach is that users need to correctly construct the coroutine handle before using it. Like any other objects, doing so the users carefully choose construction order to prevent usage of unconstructed objects. However, in the case of coroutines, users must also pass to the coroutine information about the coroutine main, like in the previous example. This opens the door for user errors and requires extra runtime storage to pass at runtime information that can be known statically. 248 296 249 297 \subsection{Alternative: Reserved keyword} … … 255 303 }; 256 304 \end{cfacode} 257 Th is 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 bothbe constructed by users without using the language support. The reserved keywords are only present to improve ease of use for the common cases.305 The \code{coroutine} keyword means the compiler can find and inject code where needed. The downside of this approach is that it makes coroutine a special case in the language. Users wantint to extend coroutines or build their own for various reasons can only do so in ways offered by the language. Furthermore, implementing coroutines without language supports also displays the power of the programming language used. While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can still be constructed by users without using the language support. The reserved keywords are only present to improve ease of use for the common cases. 258 306 259 307 \subsection{Alternative: Lamda Objects} … … 268 316 Often, 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. 269 317 270 A variation of this would be to use a nsimple function pointer in the same way pthread does for threads :318 A variation of this would be to use a simple function pointer in the same way pthread does for threads : 271 319 \begin{cfacode} 272 320 void foo( coroutine_t cid, void * arg ) { … … 281 329 } 282 330 \end{cfacode} 283 This semantic is more common for thread interfaces than coroutines but would workequally well. As discussed in section \ref{threads}, this approach is superseeded by static approaches in terms of expressivity.331 This semantics is more common for thread interfaces than coroutines works equally well. As discussed in section \ref{threads}, this approach is superseeded by static approaches in terms of expressivity. 284 332 285 333 \subsection{Alternative: Trait-based coroutines} … … 350 398 \end{cfacode} 351 399 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 the se semantics it is trivial to write a thread type that takes a function pointer as a parameter and executes it on its stack asynchronously400 In this example, threads of type \code{foo} start execution in the \code{void main(foo &)} routine, which prints \code{"Hello World!"}. While this thesis encourages this approach to enforce strongly-typed programming, users may prefer to use the routine-based thread semantics for the sake of simplicity. With the static semantics it is trivial to write a thread type that takes a function pointer as a parameter and executes it on its stack asynchronously. 353 401 \begin{cfacode} 354 402 typedef void (*voidFunc)(int); … … 361 409 void ?{}(FuncRunner & this, voidFunc inFunc, int arg) { 362 410 this.func = inFunc; 411 this.arg = arg; 363 412 } 364 413 365 414 void main(FuncRunner & this) { 415 //thread starts here and runs the function 366 416 this.func( this.arg ); 367 417 } 368 418 \end{cfacode} 369 419 370 A n consequence of the stronglytyped approach to main is that memory layout of parameters and return values to/from a thread are now explicitly specified in the \acrshort{api}.420 A consequence of the strongly-typed approach to main is that memory layout of parameters and return values to/from a thread are now explicitly specified in the \acrshort{api}. 371 421 372 422 Of course for threads to be useful, it must be possible to start and stop threads and wait for them to complete execution. While using an \acrshort{api} such as \code{fork} and \code{join} is relatively common in the literature, such an interface is unnecessary. Indeed, the simplest approach is to use \acrshort{raii} principles and have threads \code{fork} after the constructor has completed and \code{join} before the destructor runs. … … 389 439 \end{cfacode} 390 440 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 simple441 This semantic has several advantages over explicit semantics: a thread is always started and stopped exaclty once, users cannot make any progamming errors, and it naturally scales to multiple threads meaning basic synchronisation is very simple. 392 442 393 443 \begin{cfacode} … … 411 461 \end{cfacode} 412 462 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 created463 However, one of the drawbacks of this approach is that threads now always form a lattice, that is they are always destroyed in the opposite order of construction because of block structure. This restriction is relaxed by using dynamic allocation, so threads can outlive the scope in which they are created, much like dynamically allocating memory lets objects outlive the scope in which they are created. 414 464 415 465 \begin{cfacode}
Note: See TracChangeset
for help on using the changeset viewer.