source: doc/theses/thierry_delisle_MMath/text/basics.tex @ b797d978

ADTast-experimental
Last change on this file since b797d978 was 67982887, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

specialize thesis directory-names

  • Property mode set to 100644
File size: 20.8 KB
Line 
1% ======================================================================
2% ======================================================================
3\chapter{Concurrency Basics}\label{basics}
4% ======================================================================
5% ======================================================================
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.
7
8\section{Basics of concurrency}
9At 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
11Execution 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's perspective) across the stacks is called concurrency.
12
13Therefore, a minimal concurrency system can be achieved by creating coroutines (see Section \ref{coroutine}), 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
15A 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.
16
17\section{\protect\CFA's Thread Building Blocks}
18One of the important features that are missing in C is threading\footnote{While the C11 standard defines a ``threads.h'' header, it is minimal and defined as optional. As such, library support for threading is far from widespread. At the time of writing the thesis, neither \texttt{gcc} nor \texttt{clang} support ``threads.h'' in their respective standard libraries.}. 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 efficient 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.
19
20\section{Coroutines: A Stepping Stone}\label{coroutine}
21While 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. \textbf{Coroutine}s are generalized routines which have predefined points where execution is suspended and can be resumed at a later time. Therefore, they need to deal with context switches and other context-management operations. 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 revolves around two features: independent call-stacks and \code{suspend}/\code{resume}.
22
23\begin{table}
24\begin{center}
25\begin{tabular}{c @{\hskip 0.025in}|@{\hskip 0.025in} c @{\hskip 0.025in}|@{\hskip 0.025in} c}
26\begin{ccode}[tabsize=2]
27//Using callbacks
28void fibonacci_func(
29        int n,
30        void (*callback)(int)
31) {
32        int first = 0;
33        int second = 1;
34        int next, i;
35        for(i = 0; i < n; i++)
36        {
37                if(i <= 1)
38                        next = i;
39                else {
40                        next = f1 + f2;
41                        f1 = f2;
42                        f2 = next;
43                }
44                callback(next);
45        }
46}
47
48int main() {
49        void print_fib(int n) {
50                printf("%d\n", n);
51        }
52
53        fibonacci_func(
54                10, print_fib
55        );
56
57
58
59}
60\end{ccode}&\begin{ccode}[tabsize=2]
61//Using output array
62void fibonacci_array(
63        int n,
64        int* array
65) {
66        int f1 = 0; int f2 = 1;
67        int next, i;
68        for(i = 0; i < n; i++)
69        {
70                if(i <= 1)
71                        next = i;
72                else {
73                        next = f1 + f2;
74                        f1 = f2;
75                        f2 = next;
76                }
77                array[i] = next;
78        }
79}
80
81
82int main() {
83        int a[10];
84
85        fibonacci_func(
86                10, a
87        );
88
89        for(int i=0;i<10;i++){
90                printf("%d\n", a[i]);
91        }
92
93}
94\end{ccode}&\begin{ccode}[tabsize=2]
95//Using external state
96typedef struct {
97        int f1, f2;
98} Iterator_t;
99
100int fibonacci_state(
101        Iterator_t* it
102) {
103        int f;
104        f = it->f1 + it->f2;
105        it->f2 = it->f1;
106        it->f1 = max(f,1);
107        return f;
108}
109
110
111
112
113
114
115
116int main() {
117        Iterator_t it={0,0};
118
119        for(int i=0;i<10;i++){
120                printf("%d\n",
121                        fibonacci_state(
122                                &it
123                        );
124                );
125        }
126
127}
128\end{ccode}
129\end{tabular}
130\end{center}
131\caption{Different implementations of a Fibonacci sequence generator in C.}
132\label{lst:fibonacci-c}
133\end{table}
134
135A good example of a problem made easier with coroutines is generators, e.g., generating the Fibonacci sequence. This problem comes with the challenge of decoupling how a sequence is generated and how it is used. Listing \ref{lst:fibonacci-c} shows conventional approaches to writing generators in C. All three of these approach suffer from strong coupling. The left and centre 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
137Listing \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.
138
139\begin{figure}
140\begin{cfacode}[caption={Implementation of Fibonacci using coroutines},label={lst:fibonacci-cfa}]
141coroutine Fibonacci {
142        int fn; //used for communication
143};
144
145void ?{}(Fibonacci& this) { //constructor
146        this.fn = 0;
147}
148
149//main automatically called on first resume
150void main(Fibonacci& this) with (this) {
151        int fn1, fn2;           //retained between resumes
152        fn  = 0;
153        fn1 = fn;
154        suspend(this);          //return to last resume
155
156        fn  = 1;
157        fn2 = fn1;
158        fn1 = fn;
159        suspend(this);          //return to last resume
160
161        for ( ;; ) {
162                fn  = fn1 + fn2;
163                fn2 = fn1;
164                fn1 = fn;
165                suspend(this);  //return to last resume
166        }
167}
168
169int next(Fibonacci& this) {
170        resume(this); //transfer to last suspend
171        return this.fn;
172}
173
174void main() { //regular program main
175        Fibonacci f1, f2;
176        for ( int i = 1; i <= 10; i += 1 ) {
177                sout | next( f1 ) | next( f2 ) | endl;
178        }
179}
180\end{cfacode}
181\end{figure}
182
183Listing \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.
184
185\begin{figure}
186\begin{cfacode}[tabsize=3,caption={Formatting text into lines of 5 blocks of 4 characters.},label={lst:fmt-line}]
187//format characters into blocks of 4 and groups of 5 blocks per line
188coroutine Format {
189        char ch;                                                                        //used for communication
190        int g, b;                                                               //global because used in destructor
191};
192
193void  ?{}(Format& fmt) {
194        resume( fmt );                                                  //prime (start) coroutine
195}
196
197void ^?{}(Format& fmt) with fmt {
198        if ( fmt.g != 0 || fmt.b != 0 )
199        sout | endl;
200}
201
202void main(Format& fmt) with fmt {
203        for ( ;; ) {                                                    //for as many characters
204                for(g = 0; g < 5; g++) {                //groups of 5 blocks
205                        for(b = 0; b < 4; fb++) {       //blocks of 4 characters
206                                suspend();
207                                sout | ch;                                      //print character
208                        }
209                        sout | "  ";                                    //print block separator
210                }
211                sout | endl;                                            //print group separator
212        }
213}
214
215void prt(Format & fmt, char ch) {
216        fmt.ch = ch;
217        resume(fmt);
218}
219
220int main() {
221        Format fmt;
222        char ch;
223        Eof: for ( ;; ) {                                               //read until end of file
224                sin | ch;                                                       //read one character
225                if(eof(sin)) break Eof;                 //eof ?
226                prt(fmt, ch);                                           //push character for formatting
227        }
228}
229\end{cfacode}
230\end{figure}
231
232\subsection{Construction}
233One 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
235The 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 expect both 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 option effectively forces the design of the coroutine.
236
237Furthermore, \CFA faces an extra challenge as polymorphic routines create invisible thunks when cast 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:
238
239\begin{cfacode}
240//async: Runs function asynchronously on another thread
241forall(otype T)
242extern void async(void (*func)(T*), T* obj);
243
244forall(otype T)
245void noop(T*) {}
246
247void bar() {
248        int a;
249        async(noop, &a); //start thread running noop with argument a
250}
251\end{cfacode}
252
253The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information:
254
255\begin{ccode}
256extern void async(/* omitted */, void (*func)(void*), void* obj);
257
258void noop(/* omitted */, void* obj){}
259
260void bar(){
261        int a;
262        void _thunk0(int* _p0){
263                /* omitted */
264                noop(/* omitted */, _p0);
265        }
266        /* omitted */
267        async(/* omitted */, ((void (*)(void*))(&_thunk0)), (&a));
268}
269\end{ccode}
270The 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 behaviour; 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.
271
272\subsection{Alternative: Composition}
273One solution to this challenge is to use composition/containment, where coroutine fields are added to manage the coroutine.
274
275\begin{cfacode}
276struct Fibonacci {
277        int fn; //used for communication
278        coroutine c; //composition
279};
280
281void FibMain(void*) {
282        //...
283}
284
285void ?{}(Fibonacci& this) {
286        this.fn = 0;
287        //Call constructor to initialize coroutine
288        (this.c){myMain};
289}
290\end{cfacode}
291The 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.
292
293\subsection{Alternative: Reserved keyword}
294The next alternative is to use language support to annotate coroutines as follows:
295
296\begin{cfacode}
297coroutine Fibonacci {
298        int fn; //used for communication
299};
300\end{cfacode}
301The \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
305For 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:
306\begin{cfacode}
307asymmetric_coroutine<>::pull_type
308asymmetric_coroutine<>::push_type
309symmetric_coroutine<>::call_type
310symmetric_coroutine<>::yield_type
311\end{cfacode}
312Often, the canonical threading paradigm in languages is based on function pointers, \texttt{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.
313
314A variation of this would be to use a simple function pointer in the same way \texttt{pthread} does for threads:
315\begin{cfacode}
316void foo( coroutine_t cid, void* arg ) {
317        int* value = (int*)arg;
318        //Coroutine body
319}
320
321int main() {
322        int value = 0;
323        coroutine_t cid = coroutine_create( &foo, (void*)&value );
324        coroutine_resume( &cid );
325}
326\end{cfacode}
327This 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.
328
329\subsection{Alternative: Trait-Based Coroutines}
330
331Finally, 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} (as defined below) and is used as a coroutine.
332
333\begin{cfacode}
334trait is_coroutine(dtype T) {
335      void main(T& this);
336      coroutine_desc* get_coroutine(T& this);
337};
338
339forall( dtype T | is_coroutine(T) ) void suspend(T&);
340forall( dtype T | is_coroutine(T) ) void resume (T&);
341\end{cfacode}
342This ensures that 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} simply has the effect of implementing the getter and forward declarations required for users to implement the main routine.
343
344\begin{center}
345\begin{tabular}{c c c}
346\begin{cfacode}[tabsize=3]
347coroutine MyCoroutine {
348        int someValue;
349};
350\end{cfacode} & == & \begin{cfacode}[tabsize=3]
351struct MyCoroutine {
352        int someValue;
353        coroutine_desc __cor;
354};
355
356static inline
357coroutine_desc* get_coroutine(
358        struct MyCoroutine& this
359) {
360        return &this.__cor;
361}
362
363void main(struct MyCoroutine* this);
364\end{cfacode}
365\end{tabular}
366\end{center}
367
368The 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.
369
370\section{Thread Interface}\label{threads}
371The basic building blocks of multithreading in \CFA are \glspl{cfathread}. Both user 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:
372
373\begin{cfacode}
374thread foo {};
375\end{cfacode}
376
377As for coroutines, the keyword is a thin wrapper around a \CFA trait:
378
379\begin{cfacode}
380trait is_thread(dtype T) {
381      void ^?{}(T & mutex this);
382      void main(T & this);
383      thread_desc* get_thread(T & this);
384};
385\end{cfacode}
386
387Obviously, 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 to use 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
388\begin{cfacode}
389thread foo {};
390
391void main(foo & this) {
392        sout | "Hello World!" | endl;
393}
394\end{cfacode}
395
396In 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.
397\begin{cfacode}
398typedef void (*voidFunc)(int);
399
400thread FuncRunner {
401        voidFunc func;
402        int arg;
403};
404
405void ?{}(FuncRunner & this, voidFunc inFunc, int arg) {
406        this.func = inFunc;
407        this.arg  = arg;
408}
409
410void main(FuncRunner & this) {
411        //thread starts here and runs the function
412        this.func( this.arg );
413}
414
415void hello(/*unused*/ int) {
416        sout | "Hello World!" | endl;
417}
418
419int main() {
420        FuncRunner f = {hello, 42};
421        return 0?
422}
423\end{cfacode}
424
425A 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}.
426
427Of 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.
428\begin{cfacode}
429thread World;
430
431void main(World & this) {
432        sout | "World!" | endl;
433}
434
435void main() {
436        World w;
437        //Thread forks here
438
439        //Printing "Hello " and "World!" are run concurrently
440        sout | "Hello " | endl;
441
442        //Implicit join at end of scope
443}
444\end{cfacode}
445
446This 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.
447
448\begin{cfacode}
449thread MyThread {
450        //...
451};
452
453//main
454void main(MyThread& this) {
455        //...
456}
457
458void foo() {
459        MyThread thrds[10];
460        //Start 10 threads at the beginning of the scope
461
462        DoStuff();
463
464        //Wait for the 10 threads to finish
465}
466\end{cfacode}
467
468However, one of the drawbacks of this approach is that threads always form a tree where nodes must always outlive their children, i.e., they are always destroyed in the opposite order of construction because of C scoping rules. 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.
469
470\begin{cfacode}
471thread MyThread {
472        //...
473};
474
475void main(MyThread& this) {
476        //...
477}
478
479void foo() {
480        MyThread* long_lived;
481        {
482                //Start a thread at the beginning of the scope
483                MyThread short_lived;
484
485                //create another thread that will outlive the thread in this scope
486                long_lived = new MyThread;
487
488                DoStuff();
489
490                //Wait for the thread short_lived to finish
491        }
492        DoMoreStuff();
493
494        //Now wait for the long_lived to finish
495        delete long_lived;
496}
497\end{cfacode}
Note: See TracBrowser for help on using the repository browser.