Changes in / [fc263b5:34ca532]


Ignore:
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed

  • doc/bibliography/pl.bib

    rfc263b5 r34ca532  
    648648    year        = 2008,
    649649    pages       = {8-15},
     650}
     651
     652@article{Joung00,
     653    author      = {Joung, Yuh-Jzer},
     654    title       = {Asynchronous group mutual exclusion},
     655    journal     = {Distributed Computing},
     656    year        = {2000},
     657    month       = {Nov},
     658    volume      = {13},
     659    number      = {4},
     660    pages       = {189--206},
    650661}
    651662

  • doc/papers/concurrency/Paper.tex

    rfc263b5 r34ca532  
    11791179\begin{cfa}
    11801180thread Adder {
    1181     int * row, cols, * subtotal;                        $\C{// communication}$
     1181    int * row, cols, & subtotal;                        $\C{// communication}$
    11821182};
    11831183void ?{}( Adder & adder, int row[], int cols, int & subtotal ) {
    1184     adder.[ row, cols, subtotal ] = [ row, cols, &subtotal ];
     1184    adder.[ row, cols, &subtotal ] = [ row, cols, &subtotal ];
    11851185}
    11861186void main( Adder & adder ) with( adder ) {
    1187     *subtotal = 0;
     1187    subtotal = 0;
    11881188    for ( int c = 0; c < cols; c += 1 ) {
    1189                 *subtotal += row[c];
     1189                subtotal += row[c];
    11901190    }
    11911191}
    … …  
    12131213
    12141214Uncontrolled non-deterministic execution is meaningless.
    1215 To reestablish meaningful execution requires mechanisms to reintroduce determinism (control non-determinism), called synchronization and mutual exclusion, where \newterm{synchronization} is a timing relationship among threads and \newterm{mutual exclusion} is an access-control mechanism on data shared by threads.
     1215To reestablish meaningful execution requires mechanisms to reintroduce determinism (control non-determinism), called synchronization and mutual exclusion, where synchronization is a timing relationship among threads and mutual exclusion is an access-control mechanism on data shared by threads.
    12161216Since many deterministic challenges appear with the use of mutable shared state, some languages/libraries disallow it (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka~\cite{Akka} (Scala)).
    12171217In these paradigms, interaction among concurrent objects is performed by stateless message-passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms closely relate to networking concepts (\eg channels~\cite{CSP,Go}).
    … …  
    12331233
    12341234
    1235 \subsection{Basics}
    1236 
    1237 Non-determinism requires concurrent systems to offer support for mutual-exclusion and synchronization.
    1238 Mutual-exclusion is the concept that only a fixed number of threads can access a critical section at any given time, where a critical section is a group of instructions on an associated portion of data that requires the restricted access.
    1239 On the other hand, synchronization enforces relative ordering of execution and synchronization tools provide numerous mechanisms to establish timing relationships among threads.
    1240 
    1241 
    1242 \subsubsection{Mutual-Exclusion}
    1243 
    1244 As mentioned above, mutual-exclusion is the guarantee that only a fix number of threads can enter a critical section at once.
     1235\subsection{Mutual Exclusion}
     1236
     1237A group of instructions manipulating a specific instance of shared data that must be performed atomically is called an (individual) \newterm{critical-section}~\cite{Dijkstra65}.
     1238A generalization is a \newterm{group critical-section}~\cite{Joung00}, where multiple tasks with the same session may use the resource simultaneously, but different sessions may not use the resource simultaneously.
     1239The readers/writer problem~\cite{Courtois71} is an instance of a group critical-section, where readers have the same session and all writers have a unique session.
     1240\newterm{Mutual exclusion} enforces the correction number of threads are using a critical section at the same time.
     1241
    12451242However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use.
    1246 Methods range from low-level locks, which are fast and flexible but require significant attention to be correct, to  higher-level concurrency techniques, which sacrifice some performance in order to improve ease of use.
    1247 Ease of use comes by either guaranteeing some problems cannot occur (\eg being deadlock free) or by offering a more explicit coupling between data and corresponding critical section.
     1243Methods range from low-level locks, which are fast and flexible but require significant attention for correctness, to higher-level concurrency techniques, which sacrifice some performance to improve ease of use.
     1244Ease of use comes by either guaranteeing some problems cannot occur (\eg deadlock free), or by offering a more explicit coupling between shared data and critical section.
    12481245For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations (\eg reading/writing large types atomically).
    1249 Another challenge with low-level locks is composability.
    1250 Locks have restricted composability because it takes careful organizing for multiple locks to be used while preventing deadlocks.
    1251 Easing composability is another feature higher-level mutual-exclusion mechanisms often offer.
    1252 
    1253 
    1254 \subsubsection{Synchronization}
    1255 
    1256 As with mutual-exclusion, low-level synchronization primitives often offer good performance and good flexibility at the cost of ease of use.
    1257 Again, higher-level mechanisms often simplify usage by adding either better coupling between synchronization and data (\eg message passing) or offering a simpler solution to otherwise involved challenges.
     1246However, a significant challenge with (low-level) locks is composability because it takes careful organization for multiple locks to be used while preventing deadlock.
     1247Easing composability is another feature higher-level mutual-exclusion mechanisms offer.
     1248
     1249
     1250\subsection{Synchronization}
     1251
     1252Synchronization enforces relative ordering of execution, and synchronization tools provide numerous mechanisms to establish these timing relationships.
     1253Low-level synchronization primitives offer good performance and flexibility at the cost of ease of use.
     1254Higher-level mechanisms often simplify usage by adding better coupling between synchronization and data (\eg message passing), or offering a simpler solution to otherwise involved challenges, \eg barrier lock.
    12581255As mentioned above, synchronization can be expressed as guaranteeing that event \textit{X} always happens before \textit{Y}.
    1259 Most of the time, synchronization happens within a critical section, where threads must acquire mutual-exclusion in a certain order.
    1260 However, it may also be desirable to guarantee that event \textit{Z} does not occur between \textit{X} and \textit{Y}.
    1261 Not satisfying this property is called \textbf{barging}.
    1262 For example, where event \textit{X} tries to effect event \textit{Y} but another thread acquires the critical section and emits \textit{Z} before \textit{Y}.
    1263 The classic example is the thread that finishes using a resource and unblocks a thread waiting to use the resource, but the unblocked thread must compete to acquire the resource.
     1256Often synchronization is used to order access to a critical section, \eg ensuring the next kind of thread to enter a critical section is a reader thread
     1257If a writer thread is scheduled for next access, but another reader thread acquires the critical section first, the reader has \newterm{barged}.
     1258Barging can result in staleness/freshness problems, where a reader barges ahead of a write and reads temporally stale data, or a writer barges ahead of another writer overwriting data with a fresh value preventing the previous value from having an opportunity to be read.
    12641259Preventing or detecting barging is an involved challenge with low-level locks, which can be made much easier by higher-level constructs.
    1265 This challenge is often split into two different methods, barging avoidance and barging prevention.
    1266 Algorithms that use flag variables to detect barging threads are said to be using barging avoidance, while algorithms that baton-pass locks~\cite{Andrews89} between threads instead of releasing the locks are said to be using barging prevention.
     1260This challenge is often split into two different approaches, barging avoidance and barging prevention.
     1261Algorithms that allow a barger but divert it until later are avoiding the barger, while algorithms that preclude a barger from entering during synchronization in the critical section prevent the barger completely.
     1262baton-pass locks~\cite{Andrews89} between threads instead of releasing the locks are said to be using barging prevention.
    12671263
    12681264

  • doc/papers/general/Paper.tex

    rfc263b5 r34ca532  
    653653}
    654654\end{cfa}
    655 Since @pair( T *, T * )@ is a concrete type, there are no implicit parameters passed to @lexcmp@, so the generated code is identical to a function written in standard C using @void *@, yet the \CFA version is type-checked to ensure the fields of both pairs and the arguments to the comparison function match in type.
     655Since @pair( T *, T * )@ is a concrete type, there are no implicit parameters passed to @lexcmp@, so the generated code is identical to a function written in standard C using @void *@, yet the \CFA version is type-checked to ensure the members of both pairs and the arguments to the comparison function match in type.
    656656
    657657Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}.
    … …  
    815815\subsection{Member Access}
    816816
    817 It is also possible to access multiple fields from a single expression using a \newterm{member-access}.
     817It is also possible to access multiple members from a single expression using a \newterm{member-access}.
    818818The result is a single tuple-valued expression whose type is the tuple of the types of the members, \eg:
    819819\begin{cfa}
    … …  
    10201020\begin{cfa}
    10211021forall( dtype T0, dtype T1 | sized(T0) | sized(T1) ) struct _tuple2 {
    1022         T0 field_0;  T1 field_1;                                        $\C{// generated before the first 2-tuple}$
     1022        T0 member_0;  T1 member_1;                                      $\C{// generated before the first 2-tuple}$
    10231023};
    10241024_tuple2(int, int) f() {
    10251025        _tuple2(double, double) x;
    10261026        forall( dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2) ) struct _tuple3 {
    1027                 T0 field_0;  T1 field_1;  T2 field_2;   $\C{// generated before the first 3-tuple}$
     1027                T0 member_0;  T1 member_1;  T2 member_2;        $\C{// generated before the first 3-tuple}$
    10281028        };
    10291029        _tuple3(int, double, int) y;
    … …  
    10331033
    10341034\begin{comment}
    1035 Since tuples are essentially structures, tuple indexing expressions are just field accesses:
     1035Since tuples are essentially structures, tuple indexing expressions are just member accesses:
    10361036\begin{cfa}
    10371037void f(int, [double, char]);
    … …  
    10471047_tuple2(int, double) x;
    10481048
    1049 x.field_0+x.field_1;
    1050 printf("%d %g\n", x.field_0, x.field_1);
    1051 f(x.field_0, (_tuple2){ x.field_1, 'z' });
    1052 \end{cfa}
    1053 Note that due to flattening, @x@ used in the argument position is converted into the list of its fields.
     1049x.member_0+x.member_1;
     1050printf("%d %g\n", x.member_0, x.member_1);
     1051f(x.member_0, (_tuple2){ x.member_1, 'z' });
     1052\end{cfa}
     1053Note that due to flattening, @x@ used in the argument position is converted into the list of its members.
    10541054In the call to @f@, the second and third argument components are structured into a tuple argument.
    10551055Similarly, tuple member expressions are recursively expanded into a list of member access expressions.
    … …  
    10831083
    10841084The various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions.
    1085 A variable is generated to store the value produced by a statement expression, since its fields may need to be constructed with a non-trivial constructor and it may need to be referred to multiple time, \eg in a unique expression.
     1085A variable is generated to store the value produced by a statement expression, since its members may need to be constructed with a non-trivial constructor and it may need to be referred to multiple time, \eg in a unique expression.
    10861086The use of statement expressions allows the translator to arbitrarily generate additional temporary variables as needed, but binds the implementation to a non-standard extension of the C language.
    10871087However, there are other places where the \CFA translator makes use of GNU C extensions, such as its use of nested functions, so this restriction is not new.
    … …  
    14931493
    14941494Heterogeneous data is often aggregated into a structure/union.
    1495 To reduce syntactic noise, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate field-qualification by opening a scope containing the field identifiers.
     1495To reduce syntactic noise, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate member-qualification by opening a scope containing the member identifiers.
    14961496\begin{cquote}
    14971497\vspace*{-\baselineskip}%???
    … …  
    15301530The type must be an aggregate type.
    15311531(Enumerations are already opened.)
    1532 The object is the implicit qualifier for the open structure-fields.
     1532The object is the implicit qualifier for the open structure-members.
    15331533
    15341534All expressions in the expression list are open in parallel within the compound statement, which is different from Pascal, which nests the openings from left to right.
    1535 The difference between parallel and nesting occurs for fields with the same name and type:
    1536 \begin{cfa}
    1537 struct S { int `i`; int j; double m; } s, w;    $\C{// field i has same type in structure types S and T}$
     1535The difference between parallel and nesting occurs for members with the same name and type:
     1536\begin{cfa}
     1537struct S { int `i`; int j; double m; } s, w;    $\C{// member i has same type in structure types S and T}$
    15381538struct T { int `i`; int k; int m; } t, w;
    15391539with ( s, t ) {                                                         $\C{// open structure variables s and t in parallel}$
    … …  
    15491549For parallel semantics, both @s.i@ and @t.i@ are visible, so @i@ is ambiguous without qualification;
    15501550for nested semantics, @t.i@ hides @s.i@, so @i@ implies @t.i@.
    1551 \CFA's ability to overload variables means fields with the same name but different types are automatically disambiguated, eliminating most qualification when opening multiple aggregates.
     1551\CFA's ability to overload variables means members with the same name but different types are automatically disambiguated, eliminating most qualification when opening multiple aggregates.
    15521552Qualification or a cast is used to disambiguate.
    15531553
    … …  
    15551555\begin{cfa}
    15561556void ?{}( S & s, int i ) with ( s ) {           $\C{// constructor}$
    1557         `s.i = i;`  j = 3;  m = 5.5;                    $\C{// initialize fields}$
     1557        `s.i = i;`  j = 3;  m = 5.5;                    $\C{// initialize members}$
    15581558}
    15591559\end{cfa}
    … …  
    16591659\lstMakeShortInline@%
    16601660\end{cquote}
    1661 The only exception is bit field specification, which always appear to the right of the base type.
     1661The only exception is bit-field specification, which always appear to the right of the base type.
    16621662% Specifically, the character @*@ is used to indicate a pointer, square brackets @[@\,@]@ are used to represent an array or function return value, and parentheses @()@ are used to indicate a function parameter.
    16631663However, unlike C, \CFA type declaration tokens are distributed across all variables in the declaration list.
    … …  
    17151715// pointer to array of 5 doubles
    17161716
    1717 // common bit field syntax
     1717// common bit-field syntax
    17181718
    17191719
    … …  
    19111911\subsection{Type Nesting}
    19121912
    1913 Nested types provide a mechanism to organize associated types and refactor a subset of fields into a named aggregate (\eg sub-aggregates @name@, @address@, @department@, within aggregate @employe@).
     1913Nested types provide a mechanism to organize associated types and refactor a subset of members into a named aggregate (\eg sub-aggregates @name@, @address@, @department@, within aggregate @employe@).
    19141914Java nested types are dynamic (apply to objects), \CC are static (apply to the \lstinline[language=C++]@class@), and C hoists (refactors) nested types into the enclosing scope, meaning there is no need for type qualification.
    19151915Since \CFA in not object-oriented, adopting dynamic scoping does not make sense;
    1916 instead \CFA adopts \CC static nesting, using the field-selection operator ``@.@'' for type qualification, as does Java, rather than the \CC type-selection operator ``@::@'' (see Figure~\ref{f:TypeNestingQualification}).
     1916instead \CFA adopts \CC static nesting, using the member-selection operator ``@.@'' for type qualification, as does Java, rather than the \CC type-selection operator ``@::@'' (see Figure~\ref{f:TypeNestingQualification}).
    19171917\begin{figure}
    19181918\centering
    … …  
    20132013\end{cfa}
    20142014@VLA@ is a \newterm{managed type}\footnote{
    2015 A managed type affects the runtime environment versus a self-contained type.}: a type requiring a non-trivial constructor or destructor, or with a field of a managed type.
     2015A managed type affects the runtime environment versus a self-contained type.}: a type requiring a non-trivial constructor or destructor, or with a member of a managed type.
    20162016A managed type is implicitly constructed at allocation and destructed at deallocation to ensure proper interaction with runtime resources, in this case, the @data@ array in the heap.
    20172017For details of the code-generation placement of implicit constructor and destructor calls among complex executable statements see~\cite[\S~2.2]{Schluntz17}.
    … …  
    20362036
    20372037\CFA constructors may be explicitly called, like Java, and destructors may be explicitly called, like \CC.
    2038 Explicit calls to constructors double as a \CC-style \emph{placement syntax}, useful for construction of member fields in user-defined constructors and reuse of existing storage allocations.
     2038Explicit calls to constructors double as a \CC-style \emph{placement syntax}, useful for construction of members in user-defined constructors and reuse of existing storage allocations.
    20392039Like the other operators in \CFA, there is a concise syntax for constructor/destructor function calls:
    20402040\begin{cfa}
    … …  
    20592059For compatibility with C, a copy constructor from the first union member type is also defined.
    20602060For @struct@ types, each of the four functions are implicitly defined to call their corresponding functions on each member of the struct.
    2061 To better simulate the behaviour of C initializers, a set of \newterm{field constructors} is also generated for structures.
     2061To better simulate the behaviour of C initializers, a set of \newterm{member constructors} is also generated for structures.
    20622062A constructor is generated for each non-empty prefix of a structure's member-list to copy-construct the members passed as parameters and default-construct the remaining members.
    2063 To allow users to limit the set of constructors available for a type, when a user declares any constructor or destructor, the corresponding generated function and all field constructors for that type are hidden from expression resolution;
     2063To allow users to limit the set of constructors available for a type, when a user declares any constructor or destructor, the corresponding generated function and all member constructors for that type are hidden from expression resolution;
    20642064similarly, the generated default constructor is hidden upon declaration of any constructor.
    20652065These semantics closely mirror the rule for implicit declaration of constructors in \CC\cite[p.~186]{ANSI98:C++}.
    … …  
    27932793C provides variadic functions through @va_list@ objects, but the programmer is responsible for managing the number of arguments and their types, so the mechanism is type unsafe.
    27942794KW-C~\cite{Buhr94a}, a predecessor of \CFA, introduced tuples to C as an extension of the C syntax, taking much of its inspiration from SETL.
    2795 The main contributions of that work were adding MRVF, tuple mass and multiple assignment, and record-field access.
     2795The main contributions of that work were adding MRVF, tuple mass and multiple assignment, and record-member access.
    27962796\CCeleven introduced @std::tuple@ as a library variadic template structure.
    27972797Tuples are a generalization of @std::pair@, in that they allow for arbitrary length, fixed-size aggregation of heterogeneous values.

  • src/Parser/parser.yy

    rfc263b5 r34ca532  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu May 24 16:49:58 2018
    13 // Update Count     : 3367
     12// Last Modified On : Thu May 24 18:11:59 2018
     13// Update Count     : 3369
    1414//
    1515
    … …  
    12651265
    12661266declaration_list_opt:                                                                   // used at beginning of switch statement
    1267         pop
     1267        pop     // empty
    12681268                { $$ = nullptr; }
    12691269        | declaration_list
    … …  
    14071407                { $$ = DeclarationNode::newTuple( $3 ); }
    14081408        | '[' push cfa_parameter_list pop ',' push cfa_abstract_parameter_list pop ']'
    1409                 // To obtain LR(1 ), the last cfa_abstract_parameter_list is added into this flattened rule to lookahead to the
    1410                 // ']'.
     1409                // To obtain LR(1 ), the last cfa_abstract_parameter_list is added into this flattened rule to lookahead to the ']'.
    14111410                { $$ = DeclarationNode::newTuple( $3->appendList( $7 ) ); }
    14121411        ;
    … …  
    22582257        TRAIT no_attr_identifier_or_type_name '(' push type_parameter_list pop ')' '{' '}'
    22592258                { $$ = DeclarationNode::newTrait( $2, $5, 0 ); }
    2260         | TRAIT no_attr_identifier_or_type_name '(' push type_parameter_list pop ')' '{'
    2261                 { typedefTable.enterScope(); }
    2262           trait_declaration_list '}'
     2259        | TRAIT no_attr_identifier_or_type_name '(' push type_parameter_list pop ')' '{' push trait_declaration_list '}'
    22632260                { $$ = DeclarationNode::newTrait( $2, $5, $10 ); }
    22642261        ;

  • src/libcfa/concurrency/alarm.c

    rfc263b5 r34ca532  
    1010// Created On       : Fri Jun 2 11:31:25 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Mon Apr  9 13:36:18 2018
    13 // Update Count     : 61
     12// Last Modified On : Fri May 25 06:25:47 2018
     13// Update Count     : 67
    1414//
    1515
    … …  
    3737
    3838void __kernel_set_timer( Duration alarm ) {
    39         verifyf(alarm >= 1`us || alarm == 0, "Setting timer to < 1us (%luns)", alarm.tv);
     39        verifyf(alarm >= 1`us || alarm == 0, "Setting timer to < 1us (%jins)", alarm.tv);
    4040        setitimer( ITIMER_REAL, &(itimerval){ alarm }, NULL );
    4141}

  • src/tests/concurrent/examples/matrixSum.c

    rfc263b5 r34ca532  
    1111// Created On       : Mon Oct  9 08:29:28 2017
    1212// Last Modified By : Peter A. Buhr
    13 // Last Modified On : Tue Dec  5 22:56:46 2017
    14 // Update Count     : 4
     13// Last Modified On : Fri May 25 09:34:27 2018
     14// Update Count     : 10
    1515//
    1616
    … …  
    2020
    2121thread Adder {
    22     int * row, cols, * subtotal;                                                // communication
     22        int * row, cols, & subtotal;                                            // communication
    2323};
    2424
    2525void ?{}( Adder & adder, int row[], int cols, int & subtotal ) {
    26     adder.row = row;
    27     adder.cols = cols;
    28     adder.subtotal = &subtotal;
     26        adder.[ row, cols ] = [ row, cols ];                            // expression disallowed in multi-member access
     27        &adder.subtotal = &subtotal;
    2928}
    3029
    31 void main( Adder & adder ) with( adder ) {
    32     *subtotal = 0;
    33     for ( int c = 0; c < cols; c += 1 ) {
    34                 *subtotal += row[c];
    35     } // for
     30void main( Adder & adder ) with( adder ) {                              // thread starts here
     31        subtotal = 0;
     32        for ( int c = 0; c < cols; c += 1 ) {
     33                subtotal += row[c];
     34        } // for
    3635}
    3736
    3837int main() {
    39     const int rows = 10, cols = 1000;
    40     int matrix[rows][cols], subtotals[rows], total = 0;
    41     processor p;                                                                                // extra kernel thread
     38        const int rows = 10, cols = 1000;
     39        int matrix[rows][cols], subtotals[rows], total = 0;
     40        processor p;                                                                            // add kernel thread
    4241
    43     for ( int r = 0; r < rows; r += 1 ) {
     42        for ( int r = 0; r < rows; r += 1 ) {
    4443                for ( int c = 0; c < cols; c += 1 ) {
    4544                        matrix[r][c] = 1;
    4645                } // for
    47     } // for
    48     Adder * adders[rows];
    49     for ( int r = 0; r < rows; r += 1 ) {                               // start threads to sum rows
     46        } // for
     47        Adder * adders[rows];
     48        for ( int r = 0; r < rows; r += 1 ) {                           // start threads to sum rows
    5049                adders[r] = &(*malloc()){ matrix[r], cols, subtotals[r] };
    5150//              adders[r] = new( matrix[r], cols, &subtotals[r] );
    52     } // for
    53     for ( int r = 0; r < rows; r += 1 ) {                               // wait for threads to finish
     51        } // for
     52        for ( int r = 0; r < rows; r += 1 ) {                           // wait for threads to finish
    5453                delete( adders[r] );
    5554                total += subtotals[r];                                                  // total subtotals
    56     } // for
    57     sout | total | endl;
     55        } // for
     56        sout | total | endl;
    5857}
    5958
Note: See TracChangeset for help on using the changeset viewer.