Changes in / [7951100:b4e1876]


Ignore:
Files:
14 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/concurrency/Paper.tex

    r7951100 rb4e1876  
    5656\newcommand{\Textbf}[2][red]{{\color{#1}{\textbf{#2}}}}
    5757\newcommand{\Emph}[2][red]{{\color{#1}\textbf{\emph{#2}}}}
     58\newcommand{\R}[1]{\Textbf{#1}}
     59\newcommand{\B}[1]{{\Textbf[blue]{#1}}}
     60\newcommand{\G}[1]{{\Textbf[OliveGreen]{#1}}}
    5861\newcommand{\uC}{$\mu$\CC}
    59 \newcommand{\TODO}[1]{{\Textbf{#1}}}
     62\newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace}
     63\newcommand{\TODO}{{\Textbf{TODO}}}
    6064
    6165%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    … …  
    256260\section{Introduction}
    257261
    258 This paper provides a minimal concurrency \newterm{Application Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
     262This paper provides a minimal concurrency \newterm{Abstract Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
    259263While the simplest concurrency system is a thread and a lock, this low-level approach is hard to master.
    260264An easier approach for programmers is to support higher-level constructs as the basis of concurrency.
    … …  
    585589As such, library support for threading is far from widespread.
    586590At the time of writing the paper, neither \protect\lstinline|gcc| nor \protect\lstinline|clang| support ``threads.h'' in their standard libraries.}.
    587 In modern programming languages, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore existing and new programming languages must have tools for writing efficient concurrent programs to take advantage of parallelism.
     591On modern architectures, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore existing and new programming languages must have tools for writing efficient concurrent programs to take advantage of parallelism.
    588592As 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.
    589593Furthermore, because C is a system-level language, programmers expect to choose precisely which features they need and which cost they are willing to pay.
    … …  
    623627\newbox\myboxA
    624628\begin{lrbox}{\myboxA}
    625 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
     629\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    626630`int f1, f2, state = 1;`   // single global variables
    627631int fib() {
    … …  
    640644        }
    641645}
    642 \end{cfa}
     646\end{lstlisting}
    643647\end{lrbox}
    644648
    645649\newbox\myboxB
    646650\begin{lrbox}{\myboxB}
    647 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
     651\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    648652#define FIB_INIT `{ 0, 1 }`
    649653typedef struct { int f2, f1; } Fib;
    … …  
    662666        }
    663667}
    664 \end{cfa}
     668\end{lstlisting}
    665669\end{lrbox}
    666670
    … …  
    675679\newbox\myboxA
    676680\begin{lrbox}{\myboxA}
    677 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
     681\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    678682`coroutine` Fib { int fn; };
    679683void main( Fib & fib ) with( fib ) {
    … …  
    695699        }
    696700}
    697 \end{cfa}
     701\end{lstlisting}
    698702\end{lrbox}
    699703\newbox\myboxB
    700704\begin{lrbox}{\myboxB}
    701 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
     705\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    702706`coroutine` Fib { int ret; };
    703707void main( Fib & f ) with( fib ) {
    … …  
    719723
    720724
    721 \end{cfa}
     725\end{lstlisting}
    722726\end{lrbox}
    723727\subfloat[3 States, internal variables]{\label{f:Coroutine3States}\usebox\myboxA}
    … …  
    767771\newbox\myboxA
    768772\begin{lrbox}{\myboxA}
    769 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
     773\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    770774`coroutine` Format {
    771775        char ch;   // used for communication
    … …  
    799803        }
    800804}
    801 \end{cfa}
     805\end{lstlisting}
    802806\end{lrbox}
    803807
    804808\newbox\myboxB
    805809\begin{lrbox}{\myboxB}
    806 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
     810\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    807811struct Format {
    808812        char ch;
    … …  
    836840        format( &fmt );
    837841}
    838 \end{cfa}
     842\end{lstlisting}
    839843\end{lrbox}
    840844\subfloat[\CFA Coroutine]{\label{f:CFAFmt}\usebox\myboxA}
    … …  
    10421046};
    10431047\end{cfa}
    1044 &
    1045 {\Large $\Rightarrow$}
    1046 &
     1048& {\Large $\Rightarrow$} &
    10471049\begin{tabular}{@{}ccc@{}}
    10481050\begin{cfa}
    … …  
    14451447\label{s:InternalScheduling}
    14461448
    1447 While monitor mutual-exclusion provides safe access to shared data, the monitor data may indicate that a thread accessing it cannot proceed, \eg a bounded buffer, Figure~\ref{f:GenericBoundedBuffer}, may be full/empty so produce/consumer threads must block.
     1449While monitor mutual-exclusion provides safe access to shared data, the monitor data may indicate that a thread accessing it cannot proceed, \eg a bounded buffer, Figure~\ref{f:BoundedBuffer}, may be full/empty so produce/consumer threads must block.
    14481450Leaving the monitor and trying again (busy waiting) is impractical for high-level programming.
    14491451Monitors eliminate busy waiting by providing internal synchronization to schedule threads needing access to the shared data, where the synchronization is blocking (threads are parked) versus spinning.
    14501452The synchronization is generally achieved with internal~\cite{Hoare74} or external~\cite[\S~2.9.2]{uC++} scheduling, where \newterm{scheduling} is defined as indicating which thread acquires the critical section next.
    1451 \newterm{Internal scheduling} is characterized by each thread entering the monitor and making an individual decision about proceeding or blocking, while \newterm{external scheduling} is characterized by an entering thread making a decision about proceeding for itself and on behalf of other threads attempting entry.
     1453\newterm{Internal scheduling} is characterized by each thread entering the monitor and making an individual decision about proceeding or blocking, while \newterm{external scheduling} is characterized by an entering thread making a decision about proceeding for itself and behalf of other threads attempting entry.
    14521454
    14531455Figure~\ref{f:BBInt} shows a \CFA bounded-buffer with internal scheduling, where producers/consumers enter the monitor, see the buffer is full/empty, and block on an appropriate condition lock, @full@/@empty@.
    … …  
    14581460\begin{enumerate}
    14591461\item
    1460 The signalling thread returns immediately, and the signalled thread continues.
     1462The signalling thread leaves immediately, and the signalled thread continues.
    14611463\item
    1462 The signalling thread continues and the signalled thread is marked for urgent unblocking at the next scheduling point (exit/wait).
     1464The signalling thread continues and the signalled thread is marked for urgent unblocking at subsequent scheduling points (exit/wait).
    14631465\item
    1464 The signalling thread blocks but is marked for urgrent unblocking at the next scheduling point and the signalled thread continues.
     1466The signalling thread blocks but is marked for urgrent unblocking and the signalled thread continues.
    14651467\end{enumerate}
    14661468The first approach is too restrictive, as it precludes solving a reasonable class of problems (\eg dating service).
    14671469\CFA supports the next two semantics as both are useful.
    14681470Finally, while it is common to store a @condition@ as a field of the monitor, in \CFA, a @condition@ variable can be created/stored independently.
    1469 Furthermore, a condition variable is tied to a \emph{group} of monitors on first use (called \newterm{branding}), which means that using internal scheduling with distinct sets of monitors requires one condition variable per set of monitors.
    14701471
    14711472\begin{figure}
    … …  
    14731474\newbox\myboxA
    14741475\begin{lrbox}{\myboxA}
    1475 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1476\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    14761477forall( otype T ) { // distribute forall
    14771478        monitor Buffer {
    … …  
    14971498        }
    14981499}
    1499 \end{cfa}
     1500\end{lstlisting}
    15001501\end{lrbox}
    15011502
    15021503\newbox\myboxB
    15031504\begin{lrbox}{\myboxB}
    1504 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1505\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    15051506forall( otype T ) { // distribute forall
    15061507        monitor Buffer {
    … …  
    15261527        }
    15271528}
    1528 \end{cfa}
     1529\end{lstlisting}
    15291530\end{lrbox}
    15301531
    … …  
    15331534\subfloat[External Scheduling]{\label{f:BBExt}\usebox\myboxB}
    15341535\caption{Generic Bounded-Buffer}
    1535 \label{f:GenericBoundedBuffer}
     1536\label{f:BoundedBuffer}
    15361537\end{figure}
    15371538
    … …  
    15391540External scheduling is controlled by the @waitfor@ statement, which atomically blocks the calling thread, releases the monitor lock, and restricts the routine calls that can next acquire mutual exclusion.
    15401541If the buffer is full, only calls to @remove@ can acquire the buffer, and if the buffer is empty, only calls to @insert@ can acquire the buffer.
    1541 Threads making calls to routines that are currently excluded block outside (externally) of the monitor on a calling queue, versus blocking on condition queues inside the monitor.
    1542 
    1543 Both internal and external scheduling extend to multiple monitors in a natural way.
    1544 \begin{cfa}
    1545 monitor M { `condition e`; ... };
    1546 void foo( M & mutex m1, M & mutex m2 ) {
    1547         ... wait( `e` ); ...                                    $\C{// wait( e, m1, m2 )}$
    1548         ... wait( `e, m1` ); ...
    1549         ... wait( `e, m2` ); ...
    1550 }
    1551 
    1552 void rtn$\(_1\)$( M & mutex m1, M & mutex m2 );
    1553 void rtn$\(_2\)$( M & mutex m1 );
    1554 void bar( M & mutex m1, M & mutex m2 ) {
    1555         ... waitfor( `rtn` ); ...                               $\C{// waitfor( rtn\(_1\), m1, m2 )}$
    1556         ... waitfor( `rtn, m1` ); ...                   $\C{// waitfor( rtn\(_2\), m1 )}$
    1557 }
    1558 \end{cfa}
    1559 For @wait( e )@, the default semantics is to atomically block the signaller and release all acquired mutex types in the parameter list, \ie @wait( e, m1, m2 )@.
    1560 To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @wait( e, m1 )@.
    1561 Wait statically verifies the released monitors are the acquired mutex-parameters so unconditional release is safe.
    1562 Similarly, for @waitfor( rtn, ... )@, the default semantics is to atomically block the acceptor and release all acquired mutex types in the parameter list, \ie @waitfor( rtn, m1, m2 )@.
    1563 To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @waitfor( rtn, m1 )@.
    1564 Waitfor statically verifies the released monitors are the same as the acquired mutex-parameters of the given routine or routine pointer.
    1565 To statically verify the released monitors match with the accepted routine's mutex parameters, the routine (pointer) prototype must be accessible.
    1566 
    1567 Given the ability to release a subset of acquired monitors can result in a \newterm{nested monitor}~\cite{Lister77} deadlock.
    1568 \begin{cfa}
    1569 void foo( M & mutex m1, M & mutex m2 ) {
    1570         ... wait( `e, m1` ); ...                                $\C{// release m1, keeping m2 acquired )}$
    1571 void baz( M & mutex m1, M & mutex m2 ) {        $\C{// must acquire m1 and m2 )}$
    1572         ... signal( `e` ); ...
    1573 \end{cfa}
    1574 The @wait@ only releases @m1@ so the signalling thread cannot acquire both @m1@ and @m2@ to  enter @baz@ to get to the @signal@.
    1575 While deadlock issues can occur with multiple/nesting acquisition, this issue results from the fact that locks, and by extension monitors, are not perfectly composable.
    1576 
    1577 Finally, an important aspect of monitor implementation is barging, \ie can calling threads barge ahead of signalled threads?
     1542Threads making calls to routines that are currently excluded wait outside (externally) of the monitor on a calling queue.
     1543
     1544An important aspect of monitor implementation is barging, \ie can calling threads barge ahead of signalled threads?
    15781545If barging is allowed, synchronization between a singller and signallee is difficult, often requiring multiple unblock/block cycles (looping around a wait rechecking if a condition is met).
    1579 \begin{quote}
    1580 However, we decree that a signal operation be followed immediately by resumption of a waiting program, without possibility of an intervening procedure call from yet a third program.
    1581 It is only in this way that a waiting program has an absolute guarantee that it can acquire the resource just released by the signalling program without any danger that a third program will interpose a monitor entry and seize the resource instead.~\cite[p.~550]{Hoare74}
    1582 \end{quote}
    1583 \CFA scheduling \emph{precludes} barging, which simplifies synchronization among threads in the monitor and increases correctness.
    1584 For example, there are no loops in either bounded buffer solution in Figure~\ref{f:GenericBoundedBuffer}.
     1546\CFA scheduling does \emph{not} have barging, which simplifies synchronization among threads in the monitor.
    15851547Supporting barging prevention as well as extending internal scheduling to multiple monitors is the main source of complexity in the design and implementation of \CFA concurrency.
    15861548
    1587 
    1588 \subsection{Barging Prevention}
    1589 
    1590 Figure~\ref{f:BargingPrevention} shows \CFA code where bulk acquire adds complexity to the internal-signalling semantics.
    1591 The complexity begins at the end of the inner @mutex@ statement, where the semantics of internal scheduling need to be extended for multiple monitors.
    1592 The problem is that bulk acquire is used in the inner @mutex@ statement where one of the monitors is already acquired.
    1593 When the signalling thread reaches the end of the inner @mutex@ statement, it should transfer ownership of @m1@ and @m2@ to the waiting thread to prevent barging into the outer @mutex@ statement by another thread.
    1594 However, both the signalling and signalled threads still need monitor @m1@.
     1549Indeed, like the bulk acquire semantics, internal scheduling extends to multiple monitors in a way that is natural to the user but requires additional complexity on the implementation side.
     1550
     1551First, here is a simple example of internal scheduling:
     1552
     1553\begin{cfa}
     1554monitor A {
     1555        condition e;
     1556}
     1557
     1558void foo(A& mutex a1, A& mutex a2) {
     1559        ...
     1560        // Wait for cooperation from bar()
     1561        wait(a1.e);
     1562        ...
     1563}
     1564
     1565void bar(A& mutex a1, A& mutex a2) {
     1566        // Provide cooperation for foo()
     1567        ...
     1568        // Unblock foo
     1569        signal(a1.e);
     1570}
     1571\end{cfa}
     1572
     1573% ======================================================================
     1574% ======================================================================
     1575\subsection{Internal Scheduling - Multi-Monitor}
     1576% ======================================================================
     1577% ======================================================================
     1578It is easy to understand the problem of multi-monitor scheduling using a series of pseudo-code examples.
     1579Note that for simplicity in the following snippets of pseudo-code, waiting and signalling is done using an implicit condition variable, like Java built-in monitors.
     1580Indeed, @wait@ statements always use the implicit condition variable as parameters and explicitly name the monitors (A and B) associated with the condition.
     1581Note that in \CFA, condition variables are tied to a \emph{group} of monitors on first use (called branding), which means that using internal scheduling with distinct sets of monitors requires one condition variable per set of monitors.
     1582The example below shows the simple case of having two threads (one for each column) and a single monitor A.
     1583
     1584\begin{multicols}{2}
     1585thread 1
     1586\begin{cfa}
     1587acquire A
     1588        wait A
     1589release A
     1590\end{cfa}
     1591
     1592\columnbreak
     1593
     1594thread 2
     1595\begin{cfa}
     1596acquire A
     1597        signal A
     1598release A
     1599\end{cfa}
     1600\end{multicols}
     1601One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling.
     1602It is important to note here that both @wait@ and @signal@ must be called with the proper monitor(s) already acquired.
     1603This semantic is a logical requirement for barging prevention.
     1604
     1605A direct extension of the previous example is a bulk acquire version:
     1606\begin{multicols}{2}
     1607\begin{cfa}
     1608acquire A & B
     1609        wait A & B
     1610release A & B
     1611\end{cfa}
     1612\columnbreak
     1613\begin{cfa}
     1614acquire A & B
     1615        signal A & B
     1616release A & B
     1617\end{cfa}
     1618\end{multicols}
     1619\noindent This version uses bulk acquire (denoted using the {\sf\&} symbol), but the presence of multiple monitors does not add a particularly new meaning.
     1620Synchronization happens between the two threads in exactly the same way and order.
     1621The only difference is that mutual exclusion covers a group of monitors.
     1622On the implementation side, handling multiple monitors does add a degree of complexity as the next few examples demonstrate.
     1623
     1624While deadlock issues can occur when nesting monitors, these issues are only a symptom of the fact that locks, and by extension monitors, are not perfectly composable.
     1625For monitors, a well-known deadlock problem is the Nested Monitor Problem~\cite{Lister77}, which occurs when a @wait@ is made by a thread that holds more than one monitor.
     1626For example, the following cfa-code runs into the nested-monitor problem:
     1627\begin{multicols}{2}
     1628\begin{cfa}
     1629acquire A
     1630        acquire B
     1631                wait B
     1632        release B
     1633release A
     1634\end{cfa}
     1635
     1636\columnbreak
     1637
     1638\begin{cfa}
     1639acquire A
     1640        acquire B
     1641                signal B
     1642        release B
     1643release A
     1644\end{cfa}
     1645\end{multicols}
     1646\noindent The @wait@ only releases monitor @B@ so the signalling thread cannot acquire monitor @A@ to get to the @signal@.
     1647Attempting release of all acquired monitors at the @wait@ introduces a different set of problems, such as releasing monitor @C@, which has nothing to do with the @signal@.
     1648
     1649However, for monitors as for locks, it is possible to write a program using nesting without encountering any problems if nesting is done correctly.
     1650For example, the next cfa-code snippet acquires monitors {\sf A} then {\sf B} before waiting, while only acquiring {\sf B} when signalling, effectively avoiding the Nested Monitor Problem~\cite{Lister77}.
     1651
     1652\begin{multicols}{2}
     1653\begin{cfa}
     1654acquire A
     1655        acquire B
     1656                wait B
     1657        release B
     1658release A
     1659\end{cfa}
     1660
     1661\columnbreak
     1662
     1663\begin{cfa}
     1664
     1665acquire B
     1666        signal B
     1667release B
     1668
     1669\end{cfa}
     1670\end{multicols}
     1671
     1672\noindent However, this simple refactoring may not be possible, forcing more complex restructuring.
     1673
     1674% ======================================================================
     1675% ======================================================================
     1676\subsection{Internal Scheduling - In Depth}
     1677% ======================================================================
     1678% ======================================================================
     1679
     1680A larger example is presented to show complex issues for bulk acquire and its implementation options are analyzed.
     1681Figure~\ref{f:int-bulk-cfa} shows an example where bulk acquire adds a significant layer of complexity to the internal signalling semantics, and listing \ref{f:int-bulk-cfa} shows the corresponding \CFA code to implement the cfa-code in listing \ref{f:int-bulk-cfa}.
     1682For the purpose of translating the given cfa-code into \CFA-code, any method of introducing a monitor is acceptable, \eg @mutex@ parameters, global variables, pointer parameters, or using locals with the @mutex@ statement.
    15951683
    15961684\begin{figure}
    1597 \newbox\myboxA
    1598 \begin{lrbox}{\myboxA}
    1599 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    1600 monitor M m1, m2;
     1685\begin{multicols}{2}
     1686Waiting thread
     1687\begin{cfa}[numbers=left]
     1688acquire A
     1689        // Code Section 1
     1690        acquire A & B
     1691                // Code Section 2
     1692                wait A & B
     1693                // Code Section 3
     1694        release A & B
     1695        // Code Section 4
     1696release A
     1697\end{cfa}
     1698\columnbreak
     1699Signalling thread
     1700\begin{cfa}[numbers=left, firstnumber=10,escapechar=|]
     1701acquire A
     1702        // Code Section 5
     1703        acquire A & B
     1704                // Code Section 6
     1705                |\label{line:signal1}|signal A & B
     1706                // Code Section 7
     1707        |\label{line:releaseFirst}|release A & B
     1708        // Code Section 8
     1709|\label{line:lastRelease}|release A
     1710\end{cfa}
     1711\end{multicols}
     1712\begin{cfa}[caption={Internal scheduling with bulk acquire},label={f:int-bulk-cfa}]
     1713\end{cfa}
     1714\begin{center}
     1715\begin{cfa}[xleftmargin=.4\textwidth]
     1716monitor A a;
     1717monitor B b;
    16011718condition c;
    1602 mutex( m1 ) {
    1603         ...
    1604         mutex( m1, m2 ) {
    1605                 ... `wait( c )`; // block and release m1, m2
    1606                 // m1, m2 acquired
    1607         } // $\LstCommentStyle{\color{red}release m2}$
    1608         // m1 acquired
    1609 } // release m1
    1610 \end{cfa}
    1611 \end{lrbox}
    1612 
    1613 \newbox\myboxB
    1614 \begin{lrbox}{\myboxB}
    1615 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    1616 
    1617 
    1618 mutex( m1 ) {
    1619         ...
    1620         mutex( m1, m2 ) {
    1621                 ... `signal( c )`; ...
    1622                 // m1, m2 acquired
    1623         } // $\LstCommentStyle{\color{red}release m2}$
    1624         // m1 acquired
    1625 } // release m1
    1626 \end{cfa}
    1627 \end{lrbox}
    1628 
    1629 \newbox\myboxC
    1630 \begin{lrbox}{\myboxC}
    1631 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    1632 
    1633 
    1634 mutex( m1 ) {
    1635         ... `wait( c )`; ...
    1636         // m1 acquired
    1637 } // $\LstCommentStyle{\color{red}release m1}$
    1638 
    1639 
    1640 
    1641 
    1642 \end{cfa}
    1643 \end{lrbox}
    1644 
    1645 \begin{cquote}
    1646 \subfloat[Waiting Thread]{\label{f:WaitingThread}\usebox\myboxA}
    1647 \hspace{2\parindentlnth}
    1648 \subfloat[Signalling Thread]{\label{f:SignallingThread}\usebox\myboxB}
    1649 \hspace{2\parindentlnth}
    1650 \subfloat[Other Waiting Thread]{\label{f:SignallingThread}\usebox\myboxC}
    1651 \end{cquote}
    1652 \caption{Barging Prevention}
    1653 \label{f:BargingPrevention}
     1719\end{cfa}
     1720\end{center}
     1721\begin{multicols}{2}
     1722Waiting thread
     1723\begin{cfa}
     1724mutex(a) {
     1725        // Code Section 1
     1726        mutex(a, b) {
     1727                // Code Section 2
     1728                wait(c);
     1729                // Code Section 3
     1730        }
     1731        // Code Section 4
     1732}
     1733\end{cfa}
     1734\columnbreak
     1735Signalling thread
     1736\begin{cfa}
     1737mutex(a) {
     1738        // Code Section 5
     1739        mutex(a, b) {
     1740                // Code Section 6
     1741                signal(c);
     1742                // Code Section 7
     1743        }
     1744        // Code Section 8
     1745}
     1746\end{cfa}
     1747\end{multicols}
     1748\begin{cfa}[caption={Equivalent \CFA code for listing \ref{f:int-bulk-cfa}},label={f:int-bulk-cfa}]
     1749\end{cfa}
     1750\begin{multicols}{2}
     1751Waiter
     1752\begin{cfa}[numbers=left]
     1753acquire A
     1754        acquire A & B
     1755                wait A & B
     1756        release A & B
     1757release A
     1758\end{cfa}
     1759
     1760\columnbreak
     1761
     1762Signaller
     1763\begin{cfa}[numbers=left, firstnumber=6,escapechar=|]
     1764acquire A
     1765        acquire A & B
     1766                signal A & B
     1767        release A & B
     1768        |\label{line:secret}|// Secretly keep B here
     1769release A
     1770// Wakeup waiter and transfer A & B
     1771\end{cfa}
     1772\end{multicols}
     1773\begin{cfa}[caption={Figure~\ref{f:int-bulk-cfa}, with delayed signalling comments},label={f:int-secret}]
     1774\end{cfa}
    16541775\end{figure}
    16551776
     1777The complexity begins at code sections 4 and 8 in listing \ref{f:int-bulk-cfa}, which are where the existing semantics of internal scheduling needs to be extended for multiple monitors.
     1778The root of the problem is that bulk acquire is used in a context where one of the monitors is already acquired, which is why it is important to define the behaviour of the previous cfa-code.
     1779When the signaller thread reaches the location where it should ``release @A & B@'' (listing \ref{f:int-bulk-cfa} line \ref{line:releaseFirst}), it must actually transfer ownership of monitor @B@ to the waiting thread.
     1780This ownership transfer is required in order to prevent barging into @B@ by another thread, since both the signalling and signalled threads still need monitor @A@.
     1781There are three options:
     1782
     1783\subsubsection{Delaying Signals}
    16561784The obvious solution to the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred.
    16571785It can be argued that that moment is when the last lock is no longer needed, because this semantics fits most closely to the behaviour of single-monitor scheduling.
    … …  
    16661794Depending on the order of signals (listing \ref{f:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
    16671795
    1668 \begin{comment}
    16691796\paragraph{Case 1: thread $\alpha$ goes first.} In this case, the problem is that monitor @A@ needs to be passed to thread $\beta$ when thread $\alpha$ is done with it.
    16701797\paragraph{Case 2: thread $\beta$ goes first.} In this case, the problem is that monitor @B@ needs to be retained and passed to thread $\alpha$ along with monitor @A@, which can be done directly or possibly using thread $\beta$ as an intermediate.
    … …  
    16761803In both cases, the threads need to be able to distinguish, on a per monitor basis, which ones need to be released and which ones need to be transferred, which means knowing when to release a group becomes complex and inefficient (see next section) and therefore effectively precludes this approach.
    16771804
    1678 
    16791805\subsubsection{Dependency graphs}
     1806
    16801807
    16811808\begin{figure}
    … …  
    17561883
    17571884\subsubsection{Partial Signalling} \label{partial-sig}
    1758 \end{comment}
    1759 
    17601885Finally, the solution that is chosen for \CFA is to use partial signalling.
    17611886Again using listing \ref{f:int-bulk-cfa}, the partial signalling solution transfers ownership of monitor @B@ at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor @A@.
    … …  
    17721897\end{itemize}
    17731898
    1774 
     1899% ======================================================================
     1900% ======================================================================
    17751901\subsection{Signalling: Now or Later}
    1776 
    1777 \begin{figure}
    1778 \centering
    1779 \newbox\myboxA
    1780 \begin{lrbox}{\myboxA}
    1781 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    1782 enum { CCodes = 20 };
    1783 monitor DS {
    1784         int GirlPhNo, BoyPhNo;
    1785         condition Girls[CCodes], Boys[CCodes];
    1786         condition exchange;
     1902% ======================================================================
     1903% ======================================================================
     1904\begin{table}
     1905\begin{tabular}{|c|c|}
     1906@signal@ & @signal_block@ \\
     1907\hline
     1908\begin{cfa}[tabsize=3]
     1909monitor DatingService {
     1910        // compatibility codes
     1911        enum{ CCodes = 20 };
     1912
     1913        int girlPhoneNo
     1914        int boyPhoneNo;
    17871915};
    1788 int girl( DS & mutex ds, int phNo, int ccode ) {
    1789         if ( is_empty( Boys[ccode] ) ) {
    1790                 wait( Girls[ccode] );
    1791                 GirlPhNo = phNo;
    1792                 exchange.signal();
     1916
     1917condition girls[CCodes];
     1918condition boys [CCodes];
     1919condition exchange;
     1920
     1921int girl(int phoneNo, int cfa) {
     1922        // no compatible boy ?
     1923        if(empty(boys[cfa])) {
     1924                wait(girls[cfa]);               // wait for boy
     1925                girlPhoneNo = phoneNo;          // make phone number available
     1926                signal(exchange);               // wake boy from chair
    17931927        } else {
    1794                 GirlPhNo = phNo;
    1795                 signal( Boys[ccode] );
    1796                 exchange.wait();
    1797         } // if
    1798         return BoyPhNo;
    1799 }
    1800 int boy( DS & mutex ds, int phNo, int ccode ) {
    1801         // as above with boy/girl interchanged
    1802 }
    1803 \end{cfa}
    1804 \end{lrbox}
    1805 
    1806 \newbox\myboxB
    1807 \begin{lrbox}{\myboxB}
    1808 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    1809 
    1810 monitor DS {
    1811         int GirlPhNo, BoyPhNo;
    1812         condition Girls[CCodes], Boys[CCodes];
    1813 
     1928                girlPhoneNo = phoneNo;          // make phone number available
     1929                signal(boys[cfa]);              // wake boy
     1930                wait(exchange);         // sit in chair
     1931        }
     1932        return boyPhoneNo;
     1933}
     1934int boy(int phoneNo, int cfa) {
     1935        // same as above
     1936        // with boy/girl interchanged
     1937}
     1938\end{cfa}&\begin{cfa}[tabsize=3]
     1939monitor DatingService {
     1940
     1941        enum{ CCodes = 20 };    // compatibility codes
     1942
     1943        int girlPhoneNo;
     1944        int boyPhoneNo;
    18141945};
    1815 int girl( DS & mutex ds, int phNo, int ccode ) {
    1816         if ( is_empty( Boys[ccode] ) ) { // no compatible
    1817                 wait( Girls[ccode] ); // wait for boy
    1818                 GirlPhNo = phNo; // make phone number available
    1819 
     1946
     1947condition girls[CCodes];
     1948condition boys [CCodes];
     1949// exchange is not needed
     1950
     1951int girl(int phoneNo, int cfa) {
     1952        // no compatible boy ?
     1953        if(empty(boys[cfa])) {
     1954                wait(girls[cfa]);               // wait for boy
     1955                girlPhoneNo = phoneNo;          // make phone number available
     1956                signal(exchange);               // wake boy from chair
    18201957        } else {
    1821                 GirlPhNo = phNo; // make phone number available
    1822                 signal_block( Boys[ccode] ); // restart boy
    1823 
    1824         } // if
    1825         return BoyPhNo;
    1826 }
    1827 int boy( DS & mutex ds, int phNo, int ccode ) {
    1828         // as above with boy/girl interchanged
    1829 }
    1830 \end{cfa}
    1831 \end{lrbox}
    1832 
    1833 \subfloat[\lstinline@signal@]{\label{f:DatingSignal}\usebox\myboxA}
    1834 \qquad
    1835 \subfloat[\lstinline@signal_block@]{\label{f:DatingSignalBlock}\usebox\myboxB}
    1836 \caption{Dating service. }
    1837 \label{f:Dating service}
    1838 \end{figure}
    1839 
     1958                girlPhoneNo = phoneNo;          // make phone number available
     1959                signal_block(boys[cfa]);                // wake boy
     1960
     1961                // second handshake unnecessary
     1962
     1963        }
     1964        return boyPhoneNo;
     1965}
     1966
     1967int boy(int phoneNo, int cfa) {
     1968        // same as above
     1969        // with boy/girl interchanged
     1970}
     1971\end{cfa}
     1972\end{tabular}
     1973\caption{Dating service example using \protect\lstinline|signal| and \protect\lstinline|signal_block|. }
     1974\label{tbl:datingservice}
     1975\end{table}
    18401976An important note is that, until now, signalling a monitor was a delayed operation.
    18411977The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the @signal@ statement.
    … …  
    18541990% ======================================================================
    18551991An alternative to internal scheduling is external scheduling (see Table~\ref{tbl:sched}).
    1856 
    1857 \begin{comment}
    18581992\begin{table}
    18591993\begin{tabular}{|c|c|c|}
    … …  
    19192053\label{tbl:sched}
    19202054\end{table}
    1921 \end{comment}
    1922 
    19232055This method is more constrained and explicit, which helps users reduce the non-deterministic nature of concurrency.
    19242056Indeed, as the following examples demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occurring.

  • src/Common/SemanticError.cc

    r7951100 rb4e1876  
    1010// Created On       : Mon May 18 07:44:20 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Jun  7 08:05:26 2018
    13 // Update Count     : 10
     12// Last Modified On : Wed May 16 15:01:20 2018
     13// Update Count     : 9
    1414//
    1515
    … …  
    9797void SemanticError( CodeLocation location, std::string error ) {
    9898        SemanticErrorThrow = true;
    99         throw SemanticErrorException( location, error );
     99        throw SemanticErrorException(location, error);
    100100}
    101101

  • src/Parser/DeclarationNode.cc

    r7951100 rb4e1876  
    1010// Created On       : Sat May 16 12:34:05 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Jun  7 12:08:55 2018
    13 // Update Count     : 1079
     12// Last Modified On : Wed Jun  6 15:57:50 2018
     13// Update Count     : 1076
    1414//
    1515
    … …  
    545545                                        type->aggregate.params->appendList( q->type->forall ); // augment forall qualifier
    546546                                } else {                                                                // not polymorphic
    547                                         type->aggregate.params = q->type->forall; // set forall qualifier
     547                                        type->aggregate.params = q->type->forall; // make polymorphic type
     548                                        // change implicit typedef from TYPEDEFname to TYPEGENname
     549                                        typedefTable.changeKind( *type->aggregate.name, TYPEGENname );
    548550                                } // if
    549551                        } else {                                                                        // not polymorphic

  • src/Parser/TypedefTable.cc

    r7951100 rb4e1876  
    1010// Created On       : Sat May 16 15:20:13 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Jun  7 13:17:56 2018
    13 // Update Count     : 192
     12// Last Modified On : Fri Jun  1 16:54:18 2018
     13// Update Count     : 155
    1414//
    1515
    … …  
    1717#include "TypedefTable.h"
    1818#include <cassert>                                                                              // for assert
    19 #include <iostream>
    2019
    2120#if 0
     21#include <iostream>
    2222#define debugPrint( code ) code
    2323#else
    … …  
    2727using namespace std;                                                                    // string, iostream
    2828
    29 debugPrint(
    30 static const char *kindName( int kind ) {
    31         switch ( kind ) {
    32           case IDENTIFIER: return "identifier";
    33           case TYPEDEFname: return "typedef";
    34           case TYPEGENname: return "typegen";
    35           default:
    36                 cerr << "Error: cfa-cpp internal error, invalid kind of identifier" << endl;
    37                 abort();
    38         } // switch
    39 } // kindName
    40 )
    41 
    4229TypedefTable::~TypedefTable() {
    4330        if ( ! SemanticErrorThrow && kindTable.currentScope() != 0 ) {
    44                 cerr << "Error: cfa-cpp internal error, scope failure " << kindTable.currentScope() << endl;
    45                 abort();
     31                std::cerr << "scope failure " << kindTable.currentScope() << endl;
    4632        } // if
    4733} // TypedefTable::~TypedefTable
    … …  
    5844} // TypedefTable::isKind
    5945
     46void TypedefTable::changeKind( const string & identifier, int kind ) {
     47        KindTable::iterator posn = kindTable.find( identifier );
     48        if ( posn != kindTable.end() ) posn->second = kind;     // exists => update
     49} // TypedefTable::changeKind
     50
    6051// SKULLDUGGERY: Generate a typedef for the aggregate name so the aggregate does not have to be qualified by
    6152// "struct". Only generate the typedef, if the name is not in use. The typedef is implicitly (silently) removed if the
    6253// name is explicitly used.
    63 void TypedefTable::makeTypedef( const string & name, int kind ) {
    64 //    Check for existence is necessary to handle:
    65 //        struct Fred {};
    66 //        void Fred();
    67 //        void fred() {
    68 //           struct Fred act; // do not add as type in this scope
    69 //           Fred();
    70 //        }
     54void TypedefTable::makeTypedef( const string & name ) {
    7155        if ( ! typedefTable.exists( name ) ) {
    72                 typedefTable.addToEnclosingScope( name, kind, "MTD" );
     56                typedefTable.addToEnclosingScope( name, TYPEDEFname, "MTD" );
    7357        } // if
    7458} // TypedefTable::makeTypedef
    7559
    76 void TypedefTable::addToScope( const string & identifier, int kind, const char * locn __attribute__((unused)) ) {
     60void TypedefTable::addToScope( const std::string & identifier, int kind, const char * locn __attribute__((unused)) ) {
    7761        auto scope = kindTable.currentScope();
    78         debugPrint( cerr << "Adding current at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl );
     62        debugPrint( cerr << "Adding at " << locn << " " << identifier << " as kind " << kind << " scope " << scope << endl );
    7963        auto ret = kindTable.insertAt( scope, identifier, kind );
    8064        if ( ! ret.second ) ret.first->second = kind;           // exists => update
    8165} // TypedefTable::addToScope
    8266
    83 void TypedefTable::addToEnclosingScope( const string & identifier, int kind, const char * locn __attribute__((unused)) ) {
     67void TypedefTable::addToEnclosingScope( const std::string & identifier, int kind, const char * locn __attribute__((unused)) ) {
    8468        assert( kindTable.currentScope() >= 1 );
    8569        auto scope = kindTable.currentScope() - 1;
    86         debugPrint( cerr << "Adding enclosing at " << locn << " " << identifier << " as " << kindName( kind ) << " scope " << scope << endl );
     70        debugPrint( cerr << "Adding+1 at " << locn << " " << identifier << " as kind " << kind << " scope " << scope << endl );
    8771        auto ret = kindTable.insertAt( scope, identifier, kind );
    8872        if ( ! ret.second ) ret.first->second = kind;           // exists => update
    … …  
    10993                        debugPrint( cerr << endl << "[" << scope << "]" );
    11094                } // while
    111                 debugPrint( cerr << " " << (*i).first << ":" << kindName( (*i).second ) );
     95                debugPrint( cerr << " " << (*i).first << ":" << (*i).second );
    11296        } // for
    11397        while ( scope > 0 ) {

  • src/Parser/TypedefTable.h

    r7951100 rb4e1876  
    1010// Created On       : Sat May 16 15:24:36 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Jun  7 12:10:17 2018
    13 // Update Count     : 85
     12// Last Modified On : Thu May 31 23:23:47 2018
     13// Update Count     : 83
    1414//
    1515
    … …  
    3030        bool exists( const std::string & identifier );
    3131        int isKind( const std::string & identifier ) const;
    32         void makeTypedef( const std::string & name, int kind = TYPEDEFname );
     32        void changeKind( const std::string & identifier, int kind );
     33        void makeTypedef( const std::string & name );
    3334        void addToScope( const std::string & identifier, int kind, const char * );
    3435        void addToEnclosingScope( const std::string & identifier, int kind, const char * );

  • src/Parser/lex.ll

    r7951100 rb4e1876  
    1010 * Created On       : Sat Sep 22 08:58:10 2001
    1111 * Last Modified By : Peter A. Buhr
    12  * Last Modified On : Thu Jun  7 08:27:40 2018
    13  * Update Count     : 679
     12 * Last Modified On : Wed Jun  6 17:31:09 2018
     13 * Update Count     : 677
    1414 */
    1515
    … …  
    452452
    453453%%
    454 
    455454// ----end of lexer----
    456455
    457456void yyerror( const char * errmsg ) {
    458         SemanticErrorThrow = true;
    459457        cout << (yyfilename ? yyfilename : "*unknown file*") << ':' << yylineno << ':' << column - yyleng + 1
    460458                 << ": " << ErrorHelpers::error_str() << errmsg << " at token \"" << (yytext[0] == '\0' ? "EOF" : yytext) << '"' << endl;

  • src/Parser/parser.yy

    r7951100 rb4e1876  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Jun  7 10:07:12 2018
    13 // Update Count     : 3527
     12// Last Modified On : Wed Jun  6 14:53:38 2018
     13// Update Count     : 3522
    1414//
    1515
    … …  
    18261826        | aggregate_key attribute_list_opt no_attr_identifier
    18271827                {
    1828                         typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname ); // create typedef
    1829                         //if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update
     1828                        typedefTable.makeTypedef( *$3 );                        // create typedef
     1829                        if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update
    18301830                        forall = false;                                                         // reset
    18311831                }
    … …  
    18341834        | aggregate_key attribute_list_opt type_name
    18351835                {
    1836                         typedefTable.makeTypedef( *$3->type->symbolic.name, forall ? TYPEGENname : TYPEDEFname ); // create typedef
    1837                         //if ( forall ) typedefTable.changeKind( *$3->type->symbolic.name, TYPEGENname ); // possibly update
     1836                        typedefTable.makeTypedef( *$3->type->symbolic.name ); // create typedef
     1837                        if ( forall ) typedefTable.changeKind( *$3->type->symbolic.name, TYPEGENname ); // possibly update
    18381838                        forall = false;                                                         // reset
    18391839                }
    … …  
    18481848        aggregate_key attribute_list_opt no_attr_identifier
    18491849                {
    1850                         typedefTable.makeTypedef( *$3, forall ? TYPEGENname : TYPEDEFname );
    1851                         //if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update
     1850                        typedefTable.makeTypedef( *$3 );
     1851                        if ( forall ) typedefTable.changeKind( *$3, TYPEGENname ); // possibly update
    18521852                        forall = false;                                                         // reset
    18531853                        $$ = DeclarationNode::newAggregate( $1, $3, nullptr, nullptr, false )->addQualifiers( $2 );
    … …  
    32643264
    32653265%%
    3266 
    32673266// ----end of grammar----
    32683267

  • src/libcfa/bits/locks.h

    r7951100 rb4e1876  
    1818#include "bits/debug.h"
    1919#include "bits/defs.h"
    20 #include <assert.h>
    21 
    22 #ifdef __cforall
    23         extern "C" {
    24                 #include <pthread.h>
    25         }
    26 #endif
    2720
    2821// pause to prevent excess processor bus usage
    … …  
    119112                __atomic_clear( &this.lock, __ATOMIC_RELEASE );
    120113        }
    121 
    122 
    123         #ifdef __CFA_WITH_VERIFY__
    124                 extern bool __cfaabi_dbg_in_kernel();
    125         #endif
    126 
    127         struct __bin_sem_t {
    128                 int_fast8_t     counter;
    129                 pthread_mutex_t lock;
    130                 pthread_cond_t  cond;
    131         };
    132 
    133         static inline void ?{}(__bin_sem_t & this) with( this ) {
    134                 counter = 0;
    135                 pthread_mutex_init(&lock, NULL);
    136                 pthread_cond_init (&cond, NULL);
    137         }
    138 
    139         static inline void ^?{}(__bin_sem_t & this) with( this ) {
    140                 pthread_mutex_destroy(&lock);
    141                 pthread_cond_destroy (&cond);
    142         }
    143 
    144         static inline void wait(__bin_sem_t & this) with( this ) {
    145                 verify(__cfaabi_dbg_in_kernel());
    146                 pthread_mutex_lock(&lock);
    147                 if(counter != 0) {   // this must be a loop, not if!
    148                         pthread_cond_wait(&cond, &lock);
    149                 }
    150                 counter = 1;
    151                 pthread_mutex_unlock(&lock);
    152         }
    153 
    154         static inline void post(__bin_sem_t & this) with( this ) {
    155                 verify(__cfaabi_dbg_in_kernel());
    156                 pthread_mutex_lock(&lock);
    157                 bool needs_signal = counter == 0;
    158                 counter = 1;
    159                 pthread_mutex_unlock(&lock);
    160                 if (!needs_signal)
    161                         pthread_cond_signal(&cond);
    162                 }
    163114#endif

  • src/libcfa/concurrency/kernel

    r7951100 rb4e1876  
    133133        // Idle lock
    134134        sem_t idleLock;
    135         // __bin_sem_t idleLock;
    136135
    137136        // Link lists fields
    138         struct __dbg_node_proc {
     137        struct {
    139138                struct processor * next;
    140139                struct processor * prev;
    … …  
    183182
    184183        // Link lists fields
    185         struct __dbg_node_cltr {
     184        struct {
    186185                cluster * next;
    187186                cluster * prev;

  • src/libcfa/concurrency/kernel.c

    r7951100 rb4e1876  
    1717#include <stddef.h>
    1818#include <errno.h>
    19 #include <string.h>
    2019extern "C" {
    2120#include <stdio.h>
    … …  
    5150thread_desc * mainThread;
    5251
    53 extern "C" {
    54 struct { __dllist_t(cluster) list; __spinlock_t lock; } __cfa_dbg_global_clusters;
    55 }
     52struct { __dllist_t(cluster) list; __spinlock_t lock; } global_clusters;
    5653
    5754//-----------------------------------------------------------------------------
    … …  
    153150
    154151void ^?{}(processor & this) with( this ){
    155         if( ! __atomic_load_n(&do_terminate, __ATOMIC_ACQUIRE) ) {
     152        if( ! do_terminate ) {
    156153                __cfaabi_dbg_print_safe("Kernel : core %p signaling termination\n", &this);
    157154                terminate(&this);
    158                 verify( __atomic_load_n(&do_terminate, __ATOMIC_SEQ_CST) );
     155                verify(this.do_terminate);
    159156                verify( kernelTLS.this_processor != &this);
    160157                P( terminated );
    … …  
    202199
    203200                thread_desc * readyThread = NULL;
    204                 for( unsigned int spin_count = 0; ! __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST); spin_count++ )
     201                for( unsigned int spin_count = 0; ! this->do_terminate; spin_count++ )
    205202                {
    206203                        readyThread = nextThread( this->cltr );
    … …  
    221218                        else
    222219                        {
    223                                 // spin(this, &spin_count);
    224                                 halt(this);
     220                                spin(this, &spin_count);
    225221                        }
    226222                }
    … …  
    549545        __cfaabi_dbg_print_safe("Kernel : Starting\n");
    550546
    551         __cfa_dbg_global_clusters.list{ __get };
    552         __cfa_dbg_global_clusters.lock{};
     547        global_clusters.list{ __get };
     548        global_clusters.lock{};
    553549
    554550        // Initialize the main cluster
    … …  
    631627        // When its coroutine terminates, it return control to the mainThread
    632628        // which is currently here
    633         __atomic_store_n(&mainProcessor->do_terminate, true, __ATOMIC_RELEASE);
     629        mainProcessor->do_terminate = true;
    634630        returnToKernel();
    635         mainThread->self_cor.state = Halted;
    636631
    637632        // THE SYSTEM IS NOW COMPLETELY STOPPED
    … …  
    649644        ^(mainThread){};
    650645
    651         ^(__cfa_dbg_global_clusters.list){};
    652         ^(__cfa_dbg_global_clusters.lock){};
     646        ^(global_clusters.list){};
     647        ^(global_clusters.lock){};
    653648
    654649        __cfaabi_dbg_print_safe("Kernel : Shutdown complete\n");
    … …  
    660655
    661656void halt(processor * this) with( *this ) {
    662         verify( ! __atomic_load_n(&do_terminate, __ATOMIC_SEQ_CST) );
    663 
    664657        with( *cltr ) {
    665658                lock      (proc_list_lock __cfaabi_dbg_ctx2);
    … …  
    671664        __cfaabi_dbg_print_safe("Kernel : Processor %p ready to sleep\n", this);
    672665
    673         // #ifdef __CFA_WITH_VERIFY__
    674         //      int sval = 0;
    675         //      sem_getvalue(&this->idleLock, &sval);
    676         //      verifyf(sval < 200, "Binary semaphore reached value %d : \n", sval);
    677         // #endif
    678 
    679         verify( ! __atomic_load_n(&do_terminate, __ATOMIC_SEQ_CST) );
     666        verify( ({int sval = 0; sem_getvalue(&this->idleLock, &sval); sval; }) < 200);
    680667        int __attribute__((unused)) ret = sem_wait(&idleLock);
    681         // verifyf(ret >= 0 || errno == EINTR, "Sem_wait returned %d (errno %d : %s\n", ret, errno, strerror(errno));
    682 
    683         // wait( idleLock );
     668        verify(ret > 0 || errno == EINTR);
    684669
    685670        __cfaabi_dbg_print_safe("Kernel : Processor %p woke up and ready to run\n", this);
    … …  
    696681        __cfaabi_dbg_print_safe("Kernel : Waking up processor %p\n", this);
    697682        int __attribute__((unused)) ret = sem_post(&this->idleLock);
    698         // verifyf(ret >= 0 || errno == EINTR, "Sem_post returned %d (errno %d : %s\n", ret, errno, strerror(errno));
    699 
    700         // #ifdef __CFA_WITH_VERIFY__
    701         //      int sval = 0;
    702         //      sem_getvalue(&this->idleLock, &sval);
    703         //      verifyf(sval < 200, "Binary semaphore reached value %d\n", sval);
    704         // #endif
    705 
    706         // post( this->idleLock );
     683        verify(ret > 0 || errno == EINTR);
     684        verify( ({int sval = 0; sem_getvalue(&this->idleLock, &sval); sval; }) < 200);
    707685}
    708686
    … …  
    820798// Global Queues
    821799void doregister( cluster     & cltr ) {
    822         lock      ( __cfa_dbg_global_clusters.lock __cfaabi_dbg_ctx2);
    823         push_front( __cfa_dbg_global_clusters.list, cltr );
    824         unlock    ( __cfa_dbg_global_clusters.lock );
     800        lock      ( global_clusters.lock __cfaabi_dbg_ctx2);
     801        push_front( global_clusters.list, cltr );
     802        unlock    ( global_clusters.lock );
    825803}
    826804
    827805void unregister( cluster     & cltr ) {
    828         lock  ( __cfa_dbg_global_clusters.lock __cfaabi_dbg_ctx2);
    829         remove( __cfa_dbg_global_clusters.list, cltr );
    830         unlock( __cfa_dbg_global_clusters.lock );
     806        lock  ( global_clusters.lock __cfaabi_dbg_ctx2);
     807        remove( global_clusters.list, cltr );
     808        unlock( global_clusters.lock );
    831809}
    832810

  • src/libcfa/concurrency/preemption.c

    r7951100 rb4e1876  
    265265// kill wrapper : signal a processor
    266266void terminate(processor * this) {
    267         disable_interrupts();
    268         __atomic_store_n(&this->do_terminate, true, __ATOMIC_SEQ_CST);
    269         wake( this );
     267        this->do_terminate = true;
     268        wake(this);
    270269        sigval_t value = { PREEMPT_TERMINATE };
    271         enable_interrupts( __cfaabi_dbg_ctx );
    272270        pthread_sigqueue( this->kernel_thread, SIGUSR1, value );
    273271}
    … …  
    371369        choose(sfp->si_value.sival_int) {
    372370                case PREEMPT_NORMAL   : ;// Normal case, nothing to do here
    373                 case PREEMPT_TERMINATE: verify( __atomic_load_n( &kernelTLS.this_processor->do_terminate, __ATOMIC_SEQ_CST ) );
     371                case PREEMPT_TERMINATE: verify( kernelTLS.this_processor->do_terminate);
    374372                default:
    375373                        abort( "internal error, signal value is %d", sfp->si_value.sival_int );
    … …  
    490488}
    491489
    492 #ifdef __CFA_WITH_VERIFY__
    493 bool __cfaabi_dbg_in_kernel() {
    494         return !kernelTLS.preemption_state.enabled;
    495 }
    496 #endif
    497 
    498490// Local Variables: //
    499491// mode: c //

  • src/libcfa/stdhdr/assert.h

    r7951100 rb4e1876  
    3333        #define verify(x) assert(x)
    3434        #define verifyf(x, ...) assertf(x, __VA_ARGS__)
    35         #define __CFA_WITH_VERIFY__
    3635#else
    3736        #define verify(x)

  • src/prelude/sync-builtins.cf

    r7951100 rb4e1876  
    248248#endif
    249249
    250 _Bool __atomic_load_n(const volatile _Bool *, int);
    251 void __atomic_load(const volatile _Bool *, volatile _Bool *, int);
    252250char __atomic_load_n(const volatile char *, int);
    253251char __atomic_load_1(const volatile char *, int);
    … …  
    287285
    288286void __atomic_store_n(volatile _Bool *, _Bool, int);
     287void __atomic_store_1(volatile _Bool *, _Bool, int);
    289288void __atomic_store(volatile _Bool *, _Bool *, int);
    290289void __atomic_store_n(volatile char *, char, int);

  • src/tests/preempt_longrun/processor.c

    r7951100 rb4e1876  
    22#include <thread>
    33#include <time>
    4 
    5 #include <unistd.h>
    64
    75#ifndef PREEMPTION_RATE
    … …  
    1715int main(int argc, char* argv[]) {
    1816        processor * p[15];
    19         write(STDERR_FILENO, "Preparing\n", sizeof("Preparing\n"));
    2017        for ( int pi = 0; pi < 15; pi++ ) {
    2118                p[pi] = new();
    2219        }
    23         write(STDERR_FILENO, "Starting\n", sizeof("Starting\n"));
    2420        for ( int i = 0; i < N; i++) {
    2521                int pi = i % 15;
    … …  
    2723                p[pi] = new();
    2824        }
    29         write(STDERR_FILENO, "Stopping\n", sizeof("Stopping\n"));
    3025        for ( int pi = 0; pi < 15; pi++ ) {
    3126                delete( p[pi] );
    3227        }
    33         write(STDERR_FILENO, "Done\n", sizeof("Done\n"));
    3428}
Note: See TracChangeset for help on using the changeset viewer.