Changeset 1ecee81 for doc


Ignore:
Timestamp:
Mar 16, 2019, 11:59:51 AM (3 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
arm-eh, cleanup-dtors, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
3f8ec70
Parents:
35a2d47
Message:

update title/introduction

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/concurrency/Paper.tex

    r35a2d47 r1ecee81  
    228228}
    229229
    230 \title{\texorpdfstring{Advanced Control-flow in \protect\CFA}{Advanced Control-flow in Cforall}}
     230\title{\texorpdfstring{Advanced Control-flow and Concurrency in \protect\CFA}{Advanced Control-flow in Cforall}}
    231231
    232232\author[1]{Thierry Delisle}
     
    242242\abstract[Summary]{
    243243\CFA is a modern, polymorphic, non-object-oriented, backwards-compatible extension of the C programming language.
    244 This paper discusses the advanced control-flow features in \CFA, which include concurrency and parallelism, and its supporting runtime system.
    245 These features are created from scratch as ISO C's concurrency is low-level and unimplemented, so C programmers continue to rely on the C pthreads library.
    246 \CFA provides high-level control-flow mechanisms, like coroutines and user-level threads, and monitors for mutual exclusion and synchronization.
    247 A unique contribution of this work is allowing multiple monitors to be safely acquired \emph{simultaneously} (deadlock free), while integrating this capability with all monitor synchronization mechanisms.
    248 All features respect the expectations of C programmers, while being fully integrate with the \CFA polymorphic type-system and other language features.
     244This paper discusses some advanced control-flow and concurrency/parallelism features in \CFA, along with the supporting runtime.
     245These features are created from scratch because they do not exist in ISO C, or are low-level and/or unimplemented, so C programmers continue to rely on library features, like C pthreads.
     246\CFA introduces language-level control-flow mechanisms, like coroutines, user-level threading, and monitors for mutual exclusion and synchronization.
     247A unique contribution of this work is allowing multiple monitors to be safely acquired \emph{simultaneously} (deadlock free), while integrating this capability with monitor synchronization mechanisms.
     248These features also integrate with the \CFA polymorphic type-system and exception handling, while respecting the expectations and style of C programmers.
    249249Experimental results show comparable performance of the new features with similar mechanisms in other concurrent programming-languages.
    250250}%
     
    261261\section{Introduction}
    262262
    263 This paper discusses the design of advanced, high-level control-flow extensions (especially concurrency and parallelism) in \CFA and its runtime.
     263This paper discusses the design of language-level control-flow and concurrency/parallelism extensions in \CFA and its runtime.
    264264\CFA is a modern, polymorphic, non-object-oriented\footnote{
    265265\CFA has features often associated with object-oriented programming languages, such as constructors, destructors, virtuals and simple inheritance.
    266266However, functions \emph{cannot} be nested in structures, so there is no lexical binding between a structure and set of functions (member/method) implemented by an implicit \lstinline@this@ (receiver) parameter.},
    267267backwards-compatible extension of the C programming language~\cite{Moss18}.
    268 Within the \CFA framework, new control-flow features were created from scratch.
    269 ISO \Celeven defines only a subset of the \CFA extensions, and with respect to concurrency~\cite[\S~7.26]{C11}, the features are largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}.
     268Within the \CFA framework, new control-flow features are created from scratch.
     269ISO \Celeven defines only a subset of the \CFA extensions.
     270The overlapping features are concurrency~\cite[\S~7.26]{C11};
     271however, \Celeven concurrency is largely wrappers for a subset of the pthreads library~\cite{Butenhof97,Pthreads}.
    270272Furthermore, \Celeven and pthreads concurrency is basic, based on thread fork/join in a function and a few locks, which is low-level and error prone;
    271 no high-level language concurrency features exist.
    272 Interestingly, almost a decade after publication of the \Celeven standard, neither gcc-8, clang-8 nor msvc-19 (most recent versions) support the \Celeven include @threads.h@, indicating little interest in the C concurrency approach.
    273 Finally, while the \Celeven standard does not state a concurrent threading-model, the historical association with pthreads suggests the threading model is kernel-level threading (1:1)~\cite{ThreadModel}.
     273no high-level language concurrency features are defined.
     274Interestingly, almost a decade after publication of the \Celeven standard, neither gcc-8, clang-8 nor msvc-19 (most recent versions) support the \Celeven include @threads.h@, indicating little interest in the C11 concurrency approach.
     275Finally, while the \Celeven standard does not state a concurrent threading-model, the historical association with pthreads suggests implementations would adopt kernel-level threading (1:1)~\cite{ThreadModel}.
    274276
    275277In contrast, there has been a renewed interest during the past decade in user-level (M:N, green) threading in old and new programming languages.
     
    284286
    285287A further effort over the past decade is the development of language memory-models to deal with the conflict between certain language features and compiler/hardware optimizations.
    286 This issue can be rephrased as some features are pervasive (language and runtime) and cannot be safely added via a library to prevent invalidation by sequential optimizations~\cite{Buhr95a,Boehm05}.
     288This issue can be rephrased as: some language features are pervasive (language and runtime) and cannot be safely added via a library to prevent invalidation by sequential optimizations~\cite{Buhr95a,Boehm05}.
    287289The consequence is that a language must be cognizant of these features and provide sufficient tools to program around any safety issues.
    288290For example, C created the @volatile@ qualifier to provide correct execution for @setjmp@/@logjmp@ (concurrency came later).
    289 The simplest solution is to provide a handful of complex qualifiers and functions (e.g., @volatile@ and atomics) allowing programmers to write consistent/race-free programs, often in the sequentially-consistent memory-model~\cite{Boehm12}.
     291The common solution is to provide a handful of complex qualifiers and functions (e.g., @volatile@ and atomics) allowing programmers to write consistent/race-free programs, often in the sequentially-consistent memory-model~\cite{Boehm12}.
    290292
    291293While having a sufficient memory-model allows sound libraries to be constructed, writing these libraries can quickly become awkward and error prone, and using these low-level libraries has the same issues.
    292294Essentially, using low-level explicit locks is the concurrent equivalent of assembler programming.
    293295Just as most assembler programming is replaced with programming in a high-level language, explicit locks can be replaced with high-level concurrency constructs in a programming language.
    294 The goal is to get the compiler to check for correct usage and follow any complex coding conventions implicitly.
     296Then the goal is for the compiler to check for correct usage and follow any complex coding conventions implicitly.
    295297The drawback is that language constructs may preclude certain specialized techniques, therefore introducing inefficiency or inhibiting concurrency.
    296298For most concurrent programs, these drawbacks are insignificant in comparison to the speed of composition, and subsequent reliability and maintainability of the high-level concurrent program.
     
    299301As stated, this observation applies to non-concurrent forms of complex control-flow, like exception handling and coroutines.
    300302
    301 Adapting the programming language allows matching the control-flow model with the programming-language style, versus adapting to one general (sound) library/paradigm.
     303Adapting the programming language to these features also allows matching the control-flow model with the programming-language style, versus adopting one general (sound) library/paradigm.
    302304For example, it is possible to provide exceptions, coroutines, monitors, and tasks as specialized types in an object-oriented language, integrating these constructs to allow leveraging the type-system (static type-checking) and all other object-oriented capabilities~\cite{uC++}.
    303305It is also possible to leverage call/return for blocking communication via new control structures, versus switching to alternative communication paradigms, like channels or message passing.
     
    308310Finally, with extended language features and user-level threading it is possible to discretely fold locking and non-blocking I/O multiplexing into the language's I/O libraries, so threading implicitly dovetails with the I/O subsystem.
    309311
    310 \CFA embraces language extensions and user-level threading to provide advanced control-flow and concurrency.
    311 We attempt to show the \CFA extensions and runtime are demonstrably better than those proposed for \CC and other concurrent, imperative programming languages.
     312\CFA embraces language extensions and user-level threading to provide advanced control-flow (exception handling\footnote{
     313\CFA exception handling will be presented in a separate paper.
     314The key feature that dovetails with this paper is non-local exceptions allowing exceptions to be raised across stacks, with synchronous exceptions raised among coroutines and asynchronous exceptions raised among threads, similar to that in \uC~\cite[\S~5]{uC++}
     315} and coroutines) and concurrency.
     316We show the \CFA language extensions are demonstrably better than those proposed for \Celeven, \CC and other concurrent, imperative programming languages, and that the \CFA runtime is competitive with other similar extensions.
    312317The contributions of this work are:
    313318\begin{itemize}
Note: See TracChangeset for help on using the changeset viewer.