Changes in / [34ca532:fc263b5]


Ignore:
Files:
1 deleted
6 edited

Legend:

Unmodified
Added
Removed

  • doc/bibliography/pl.bib

    r34ca532 rfc263b5  
    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},
    661650}
    662651

  • doc/papers/concurrency/Paper.tex

    r34ca532 rfc263b5  
    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 synchronization is a timing relationship among threads and 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 \newterm{synchronization} is a timing relationship among threads and \newterm{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{Mutual Exclusion}
    1236 
    1237 A group of instructions manipulating a specific instance of shared data that must be performed atomically is called an (individual) \newterm{critical-section}~\cite{Dijkstra65}.
    1238 A 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.
    1239 The 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 
     1235\subsection{Basics}
     1236
     1237Non-determinism requires concurrent systems to offer support for mutual-exclusion and synchronization.
     1238Mutual-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.
     1239On 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
     1244As mentioned above, mutual-exclusion is the guarantee that only a fix number of threads can enter a critical section at once.
    12421245However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use.
    1243 Methods 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.
    1244 Ease 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.
     1246Methods 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.
     1247Ease 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.
    12451248For 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).
    1246 However, a significant challenge with (low-level) locks is composability because it takes careful organization for multiple locks to be used while preventing deadlock.
    1247 Easing composability is another feature higher-level mutual-exclusion mechanisms offer.
    1248 
    1249 
    1250 \subsection{Synchronization}
    1251 
    1252 Synchronization enforces relative ordering of execution, and synchronization tools provide numerous mechanisms to establish these timing relationships.
    1253 Low-level synchronization primitives offer good performance and flexibility at the cost of ease of use.
    1254 Higher-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.
     1249Another challenge with low-level locks is composability.
     1250Locks have restricted composability because it takes careful organizing for multiple locks to be used while preventing deadlocks.
     1251Easing composability is another feature higher-level mutual-exclusion mechanisms often offer.
     1252
     1253
     1254\subsubsection{Synchronization}
     1255
     1256As with mutual-exclusion, low-level synchronization primitives often offer good performance and good flexibility at the cost of ease of use.
     1257Again, 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.
    12551258As mentioned above, synchronization can be expressed as guaranteeing that event \textit{X} always happens before \textit{Y}.
    1256 Often 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
    1257 If a writer thread is scheduled for next access, but another reader thread acquires the critical section first, the reader has \newterm{barged}.
    1258 Barging 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.
     1259Most of the time, synchronization happens within a critical section, where threads must acquire mutual-exclusion in a certain order.
     1260However, it may also be desirable to guarantee that event \textit{Z} does not occur between \textit{X} and \textit{Y}.
     1261Not satisfying this property is called \textbf{barging}.
     1262For 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}.
     1263The 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.
    12591264Preventing or detecting barging is an involved challenge with low-level locks, which can be made much easier by higher-level constructs.
    1260 This challenge is often split into two different approaches, barging avoidance and barging prevention.
    1261 Algorithms 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.
    1262 baton-pass locks~\cite{Andrews89} between threads instead of releasing the locks are said to be using barging prevention.
     1265This challenge is often split into two different methods, barging avoidance and barging prevention.
     1266Algorithms 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.
    12631267
    12641268

  • doc/papers/general/Paper.tex

    r34ca532 rfc263b5  
    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 members 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 fields 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 members from a single expression using a \newterm{member-access}.
     817It is also possible to access multiple fields 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 member_0;  T1 member_1;                                      $\C{// generated before the first 2-tuple}$
     1022        T0 field_0;  T1 field_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 member_0;  T1 member_1;  T2 member_2;        $\C{// generated before the first 3-tuple}$
     1027                T0 field_0;  T1 field_1;  T2 field_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 member accesses:
     1035Since tuples are essentially structures, tuple indexing expressions are just field accesses:
    10361036\begin{cfa}
    10371037void f(int, [double, char]);
    … …  
    10471047_tuple2(int, double) x;
    10481048
    1049 x.member_0+x.member_1;
    1050 printf("%d %g\n", x.member_0, x.member_1);
    1051 f(x.member_0, (_tuple2){ x.member_1, 'z' });
    1052 \end{cfa}
    1053 Note that due to flattening, @x@ used in the argument position is converted into the list of its members.
     1049x.field_0+x.field_1;
     1050printf("%d %g\n", x.field_0, x.field_1);
     1051f(x.field_0, (_tuple2){ x.field_1, 'z' });
     1052\end{cfa}
     1053Note that due to flattening, @x@ used in the argument position is converted into the list of its fields.
    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 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.
     1085A 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.
    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 member-qualification by opening a scope containing the member identifiers.
     1495To 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.
    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-members.
     1532The object is the implicit qualifier for the open structure-fields.
    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 members with the same name and type:
    1536 \begin{cfa}
    1537 struct S { int `i`; int j; double m; } s, w;    $\C{// member i has same type in structure types S and T}$
     1535The difference between parallel and nesting occurs for fields with the same name and type:
     1536\begin{cfa}
     1537struct S { int `i`; int j; double m; } s, w;    $\C{// field 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 members 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 fields 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 members}$
     1557        `s.i = i;`  j = 3;  m = 5.5;                    $\C{// initialize fields}$
    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 members 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 fields 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 member-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 field-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 member 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 field 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 members 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 member fields 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{member constructors} is also generated for structures.
     2061To better simulate the behaviour of C initializers, a set of \newterm{field 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 member 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 field 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-member access.
     2795The main contributions of that work were adding MRVF, tuple mass and multiple assignment, and record-field 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

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

  • src/libcfa/concurrency/alarm.c

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

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

    r34ca532 rfc263b5  
    1111// Created On       : Mon Oct  9 08:29:28 2017
    1212// Last Modified By : Peter A. Buhr
    13 // Last Modified On : Fri May 25 09:34:27 2018
    14 // Update Count     : 10
     13// Last Modified On : Tue Dec  5 22:56:46 2017
     14// Update Count     : 4
    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, cols ] = [ row, cols ];                            // expression disallowed in multi-member access
    27         &adder.subtotal = &subtotal;
     26    adder.row = row;
     27    adder.cols = cols;
     28    adder.subtotal = &subtotal;
    2829}
    2930
    30 void 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
     31void main( Adder & adder ) with( adder ) {
     32    *subtotal = 0;
     33    for ( int c = 0; c < cols; c += 1 ) {
     34                *subtotal += row[c];
     35    } // for
    3536}
    3637
    3738int main() {
    38         const int rows = 10, cols = 1000;
    39         int matrix[rows][cols], subtotals[rows], total = 0;
    40         processor p;                                                                            // add kernel thread
     39    const int rows = 10, cols = 1000;
     40    int matrix[rows][cols], subtotals[rows], total = 0;
     41    processor p;                                                                                // extra kernel thread
    4142
    42         for ( int r = 0; r < rows; r += 1 ) {
     43    for ( int r = 0; r < rows; r += 1 ) {
    4344                for ( int c = 0; c < cols; c += 1 ) {
    4445                        matrix[r][c] = 1;
    4546                } // for
    46         } // for
    47         Adder * adders[rows];
    48         for ( int r = 0; r < rows; r += 1 ) {                           // start threads to sum rows
     47    } // for
     48    Adder * adders[rows];
     49    for ( int r = 0; r < rows; r += 1 ) {                               // start threads to sum rows
    4950                adders[r] = &(*malloc()){ matrix[r], cols, subtotals[r] };
    5051//              adders[r] = new( matrix[r], cols, &subtotals[r] );
    51         } // for
    52         for ( int r = 0; r < rows; r += 1 ) {                           // wait for threads to finish
     52    } // for
     53    for ( int r = 0; r < rows; r += 1 ) {                               // wait for threads to finish
    5354                delete( adders[r] );
    5455                total += subtotals[r];                                                  // total subtotals
    55         } // for
    56         sout | total | endl;
     56    } // for
     57    sout | total | endl;
    5758}
    5859
Note: See TracChangeset for help on using the changeset viewer.