Changeset 08b5a7e for doc/papers


Ignore:
Timestamp:
Jun 7, 2018, 4:13:24 PM (3 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, with_gc
Children:
7951100, 85b1deb, 90cedbdd
Parents:
95487027
Message:

more updates

File:
1 edited

Legend:

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

    r95487027 r08b5a7e  
    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}}}
    6158\newcommand{\uC}{$\mu$\CC}
    62 \newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace}
    63 \newcommand{\TODO}{{\Textbf{TODO}}}
     59\newcommand{\TODO}[1]{{\Textbf{#1}}}
    6460
    6561%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     
    258254\section{Introduction}
    259255
    260 This paper provides a minimal concurrency \newterm{Abstract Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
     256This paper provides a minimal concurrency \newterm{Application Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
    261257While the simplest concurrency system is a thread and a lock, this low-level approach is hard to master.
    262258An easier approach for programmers is to support higher-level constructs as the basis of concurrency.
     
    587583As such, library support for threading is far from widespread.
    588584At the time of writing the paper, neither \protect\lstinline|gcc| nor \protect\lstinline|clang| support ``threads.h'' in their standard libraries.}.
    589 On 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.
     585In 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.
    590586As 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.
    591587Furthermore, because C is a system-level language, programmers expect to choose precisely which features they need and which cost they are willing to pay.
     
    625621\newbox\myboxA
    626622\begin{lrbox}{\myboxA}
    627 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     623\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    628624`int f1, f2, state = 1;`   // single global variables
    629625int fib() {
     
    642638        }
    643639}
    644 \end{lstlisting}
     640\end{cfa}
    645641\end{lrbox}
    646642
    647643\newbox\myboxB
    648644\begin{lrbox}{\myboxB}
    649 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     645\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    650646#define FIB_INIT `{ 0, 1 }`
    651647typedef struct { int f2, f1; } Fib;
     
    664660        }
    665661}
    666 \end{lstlisting}
     662\end{cfa}
    667663\end{lrbox}
    668664
     
    677673\newbox\myboxA
    678674\begin{lrbox}{\myboxA}
    679 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     675\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    680676`coroutine` Fib { int fn; };
    681677void main( Fib & fib ) with( fib ) {
     
    697693        }
    698694}
    699 \end{lstlisting}
     695\end{cfa}
    700696\end{lrbox}
    701697\newbox\myboxB
    702698\begin{lrbox}{\myboxB}
    703 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     699\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    704700`coroutine` Fib { int ret; };
    705701void main( Fib & f ) with( fib ) {
     
    721717
    722718
    723 \end{lstlisting}
     719\end{cfa}
    724720\end{lrbox}
    725721\subfloat[3 States, internal variables]{\label{f:Coroutine3States}\usebox\myboxA}
     
    769765\newbox\myboxA
    770766\begin{lrbox}{\myboxA}
    771 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     767\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    772768`coroutine` Format {
    773769        char ch;   // used for communication
     
    801797        }
    802798}
    803 \end{lstlisting}
     799\end{cfa}
    804800\end{lrbox}
    805801
    806802\newbox\myboxB
    807803\begin{lrbox}{\myboxB}
    808 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     804\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    809805struct Format {
    810806        char ch;
     
    838834        format( &fmt );
    839835}
    840 \end{lstlisting}
     836\end{cfa}
    841837\end{lrbox}
    842838\subfloat[\CFA Coroutine]{\label{f:CFAFmt}\usebox\myboxA}
     
    10441040};
    10451041\end{cfa}
    1046 & {\Large $\Rightarrow$} &
     1042&
     1043{\Large $\Rightarrow$}
     1044&
    10471045\begin{tabular}{@{}ccc@{}}
    10481046\begin{cfa}
     
    14451443\label{s:InternalScheduling}
    14461444
    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:BoundedBuffer}, may be full/empty so produce/consumer threads must block.
     1445While 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.
    14481446Leaving the monitor and trying again (busy waiting) is impractical for high-level programming.
    14491447Monitors 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.
    14501448The 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 behalf of other threads attempting entry.
     1449\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.
    14521450
    14531451Figure~\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@.
     
    14581456\begin{enumerate}
    14591457\item
    1460 The signalling thread leaves immediately, and the signalled thread continues.
     1458The signalling thread returns immediately, and the signalled thread continues.
    14611459\item
    1462 The signalling thread continues and the signalled thread is marked for urgent unblocking at subsequent scheduling points (exit/wait).
     1460The signalling thread continues and the signalled thread is marked for urgent unblocking at the next scheduling point (exit/wait).
    14631461\item
    1464 The signalling thread blocks but is marked for urgrent unblocking and the signalled thread continues.
     1462The signalling thread blocks but is marked for urgrent unblocking at the next scheduling point and the signalled thread continues.
    14651463\end{enumerate}
    14661464The first approach is too restrictive, as it precludes solving a reasonable class of problems (\eg dating service).
    14671465\CFA supports the next two semantics as both are useful.
    14681466Finally, while it is common to store a @condition@ as a field of the monitor, in \CFA, a @condition@ variable can be created/stored independently.
     1467Furthermore, 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.
    14691468
    14701469\begin{figure}
     
    14721471\newbox\myboxA
    14731472\begin{lrbox}{\myboxA}
    1474 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     1473\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    14751474forall( otype T ) { // distribute forall
    14761475        monitor Buffer {
     
    14961495        }
    14971496}
    1498 \end{lstlisting}
     1497\end{cfa}
    14991498\end{lrbox}
    15001499
    15011500\newbox\myboxB
    15021501\begin{lrbox}{\myboxB}
    1503 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     1502\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    15041503forall( otype T ) { // distribute forall
    15051504        monitor Buffer {
     
    15251524        }
    15261525}
    1527 \end{lstlisting}
     1526\end{cfa}
    15281527\end{lrbox}
    15291528
     
    15321531\subfloat[External Scheduling]{\label{f:BBExt}\usebox\myboxB}
    15331532\caption{Generic Bounded-Buffer}
    1534 \label{f:BoundedBuffer}
     1533\label{f:GenericBoundedBuffer}
    15351534\end{figure}
    15361535
     
    15381537External 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.
    15391538If 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.
    1540 Threads making calls to routines that are currently excluded wait outside (externally) of the monitor on a calling queue.
    1541 
    1542 An important aspect of monitor implementation is barging, \ie can calling threads barge ahead of signalled threads?
     1539Threads 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.
     1540
     1541Both internal and external scheduling extend to multiple monitors in a natural way.
     1542\begin{cfa}
     1543monitor M { `condition e`; ... };
     1544void foo( M & mutex m1, M & mutex m2 ) {
     1545        ... wait( `e` ); ...                                    $\C{// wait( e, m1, m2 )}$
     1546        ... wait( `e, m1` ); ...
     1547        ... wait( `e, m2` ); ...
     1548}
     1549
     1550void rtn$\(_1\)$( M & mutex m1, M & mutex m2 );
     1551void rtn$\(_2\)$( M & mutex m1 );
     1552void bar( M & mutex m1, M & mutex m2 ) {
     1553        ... waitfor( `rtn` ); ...                               $\C{// waitfor( rtn\(_1\), m1, m2 )}$
     1554        ... waitfor( `rtn, m1` ); ...                   $\C{// waitfor( rtn\(_2\), m1 )}$
     1555}
     1556\end{cfa}
     1557For @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 )@.
     1558To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @wait( e, m1 )@.
     1559Wait statically verifies the released monitors are the acquired mutex-parameters so unconditional release is safe.
     1560Similarly, 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 )@.
     1561To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @waitfor( rtn, m1 )@.
     1562Waitfor statically verifies the released monitors are the same as the acquired mutex-parameters of the given routine or routine pointer.
     1563To statically verify the released monitors match with the accepted routine's mutex parameters, the routine (pointer) prototype must be accessible.
     1564
     1565Given the ability to release a subset of acquired monitors can result in a \newterm{nested monitor}~\cite{Lister77} deadlock.
     1566\begin{cfa}
     1567void foo( M & mutex m1, M & mutex m2 ) {
     1568        ... wait( `e, m1` ); ...                                $\C{// release m1, keeping m2 acquired )}$
     1569void baz( M & mutex m1, M & mutex m2 ) {        $\C{// must acquire m1 and m2 )}$
     1570        ... signal( `e` ); ...
     1571\end{cfa}
     1572The @wait@ only releases @m1@ so the signalling thread cannot acquire both @m1@ and @m2@ to  enter @baz@ to get to the @signal@.
     1573While deadlock issues can occur with multiple/nesting acquisition, this issue results from the fact that locks, and by extension monitors, are not perfectly composable.
     1574
     1575Finally, an important aspect of monitor implementation is barging, \ie can calling threads barge ahead of signalled threads?
    15431576If 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).
    1544 \CFA scheduling does \emph{not} have barging, which simplifies synchronization among threads in the monitor.
     1577\begin{quote}
     1578However, 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.
     1579It 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}
     1580\end{quote}
     1581\CFA scheduling \emph{precludes} barging, which simplifies synchronization among threads in the monitor and increases correctness.
     1582For example, there are no loops in either bounded buffer solution in Figure~\ref{f:GenericBoundedBuffer}.
    15451583Supporting 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.
    15461584
    1547 Indeed, 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.
    1548 
    1549 First, here is a simple example of internal scheduling:
    1550 
    1551 \begin{cfa}
    1552 monitor A {
    1553         condition e;
    1554 }
    1555 
    1556 void foo(A& mutex a1, A& mutex a2) {
     1585
     1586\subsection{Barging Prevention}
     1587
     1588Figure~\ref{f:BargingPrevention} shows \CFA code where bulk acquire adds complexity to the internal-signalling semantics.
     1589The complexity begins at the end of the inner @mutex@ statement, where the semantics of internal scheduling need to be extended for multiple monitors.
     1590The problem is that bulk acquire is used in the inner @mutex@ statement where one of the monitors is already acquired.
     1591When 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.
     1592However, both the signalling and signalled threads still need monitor @m1@.
     1593
     1594\begin{figure}
     1595\newbox\myboxA
     1596\begin{lrbox}{\myboxA}
     1597\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1598monitor M m1, m2;
     1599condition c;
     1600mutex( m1 ) {
    15571601        ...
    1558         // Wait for cooperation from bar()
    1559         wait(a1.e);
     1602        mutex( m1, m2 ) {
     1603                ... `wait( c )`; // block and release m1, m2
     1604                // m1, m2 acquired
     1605        } // $\LstCommentStyle{\color{red}release m2}$
     1606        // m1 acquired
     1607} // release m1
     1608\end{cfa}
     1609\end{lrbox}
     1610
     1611\newbox\myboxB
     1612\begin{lrbox}{\myboxB}
     1613\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1614
     1615
     1616mutex( m1 ) {
    15601617        ...
    1561 }
    1562 
    1563 void bar(A& mutex a1, A& mutex a2) {
    1564         // Provide cooperation for foo()
    1565         ...
    1566         // Unblock foo
    1567         signal(a1.e);
    1568 }
    1569 \end{cfa}
    1570 
    1571 % ======================================================================
    1572 % ======================================================================
    1573 \subsection{Internal Scheduling - Multi-Monitor}
    1574 % ======================================================================
    1575 % ======================================================================
    1576 It is easy to understand the problem of multi-monitor scheduling using a series of pseudo-code examples.
    1577 Note 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.
    1578 Indeed, @wait@ statements always use the implicit condition variable as parameters and explicitly name the monitors (A and B) associated with the condition.
    1579 Note 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.
    1580 The example below shows the simple case of having two threads (one for each column) and a single monitor A.
    1581 
    1582 \begin{multicols}{2}
    1583 thread 1
    1584 \begin{cfa}
    1585 acquire A
    1586         wait A
    1587 release A
    1588 \end{cfa}
    1589 
    1590 \columnbreak
    1591 
    1592 thread 2
    1593 \begin{cfa}
    1594 acquire A
    1595         signal A
    1596 release A
    1597 \end{cfa}
    1598 \end{multicols}
    1599 One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling.
    1600 It is important to note here that both @wait@ and @signal@ must be called with the proper monitor(s) already acquired.
    1601 This semantic is a logical requirement for barging prevention.
    1602 
    1603 A direct extension of the previous example is a bulk acquire version:
    1604 \begin{multicols}{2}
    1605 \begin{cfa}
    1606 acquire A & B
    1607         wait A & B
    1608 release A & B
    1609 \end{cfa}
    1610 \columnbreak
    1611 \begin{cfa}
    1612 acquire A & B
    1613         signal A & B
    1614 release A & B
    1615 \end{cfa}
    1616 \end{multicols}
    1617 \noindent This version uses bulk acquire (denoted using the {\sf\&} symbol), but the presence of multiple monitors does not add a particularly new meaning.
    1618 Synchronization happens between the two threads in exactly the same way and order.
    1619 The only difference is that mutual exclusion covers a group of monitors.
    1620 On the implementation side, handling multiple monitors does add a degree of complexity as the next few examples demonstrate.
    1621 
    1622 While 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.
    1623 For 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.
    1624 For example, the following cfa-code runs into the nested-monitor problem:
    1625 \begin{multicols}{2}
    1626 \begin{cfa}
    1627 acquire A
    1628         acquire B
    1629                 wait B
    1630         release B
    1631 release A
    1632 \end{cfa}
    1633 
    1634 \columnbreak
    1635 
    1636 \begin{cfa}
    1637 acquire A
    1638         acquire B
    1639                 signal B
    1640         release B
    1641 release A
    1642 \end{cfa}
    1643 \end{multicols}
    1644 \noindent The @wait@ only releases monitor @B@ so the signalling thread cannot acquire monitor @A@ to get to the @signal@.
    1645 Attempting 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@.
    1646 
    1647 However, for monitors as for locks, it is possible to write a program using nesting without encountering any problems if nesting is done correctly.
    1648 For 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}.
    1649 
    1650 \begin{multicols}{2}
    1651 \begin{cfa}
    1652 acquire A
    1653         acquire B
    1654                 wait B
    1655         release B
    1656 release A
    1657 \end{cfa}
    1658 
    1659 \columnbreak
    1660 
    1661 \begin{cfa}
    1662 
    1663 acquire B
    1664         signal B
    1665 release B
    1666 
    1667 \end{cfa}
    1668 \end{multicols}
    1669 
    1670 \noindent However, this simple refactoring may not be possible, forcing more complex restructuring.
    1671 
    1672 % ======================================================================
    1673 % ======================================================================
    1674 \subsection{Internal Scheduling - In Depth}
    1675 % ======================================================================
    1676 % ======================================================================
    1677 
    1678 A larger example is presented to show complex issues for bulk acquire and its implementation options are analyzed.
    1679 Figure~\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}.
    1680 For 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.
    1681 
    1682 \begin{figure}
    1683 \begin{multicols}{2}
    1684 Waiting thread
    1685 \begin{cfa}[numbers=left]
    1686 acquire A
    1687         // Code Section 1
    1688         acquire A & B
    1689                 // Code Section 2
    1690                 wait A & B
    1691                 // Code Section 3
    1692         release A & B
    1693         // Code Section 4
    1694 release A
    1695 \end{cfa}
    1696 \columnbreak
    1697 Signalling thread
    1698 \begin{cfa}[numbers=left, firstnumber=10,escapechar=|]
    1699 acquire A
    1700         // Code Section 5
    1701         acquire A & B
    1702                 // Code Section 6
    1703                 |\label{line:signal1}|signal A & B
    1704                 // Code Section 7
    1705         |\label{line:releaseFirst}|release A & B
    1706         // Code Section 8
    1707 |\label{line:lastRelease}|release A
    1708 \end{cfa}
    1709 \end{multicols}
    1710 \begin{cfa}[caption={Internal scheduling with bulk acquire},label={f:int-bulk-cfa}]
    1711 \end{cfa}
    1712 \begin{center}
    1713 \begin{cfa}[xleftmargin=.4\textwidth]
    1714 monitor A a;
    1715 monitor B b;
    1716 condition c;
    1717 \end{cfa}
    1718 \end{center}
    1719 \begin{multicols}{2}
    1720 Waiting thread
    1721 \begin{cfa}
    1722 mutex(a) {
    1723         // Code Section 1
    1724         mutex(a, b) {
    1725                 // Code Section 2
    1726                 wait(c);
    1727                 // Code Section 3
    1728         }
    1729         // Code Section 4
    1730 }
    1731 \end{cfa}
    1732 \columnbreak
    1733 Signalling thread
    1734 \begin{cfa}
    1735 mutex(a) {
    1736         // Code Section 5
    1737         mutex(a, b) {
    1738                 // Code Section 6
    1739                 signal(c);
    1740                 // Code Section 7
    1741         }
    1742         // Code Section 8
    1743 }
    1744 \end{cfa}
    1745 \end{multicols}
    1746 \begin{cfa}[caption={Equivalent \CFA code for listing \ref{f:int-bulk-cfa}},label={f:int-bulk-cfa}]
    1747 \end{cfa}
    1748 \begin{multicols}{2}
    1749 Waiter
    1750 \begin{cfa}[numbers=left]
    1751 acquire A
    1752         acquire A & B
    1753                 wait A & B
    1754         release A & B
    1755 release A
    1756 \end{cfa}
    1757 
    1758 \columnbreak
    1759 
    1760 Signaller
    1761 \begin{cfa}[numbers=left, firstnumber=6,escapechar=|]
    1762 acquire A
    1763         acquire A & B
    1764                 signal A & B
    1765         release A & B
    1766         |\label{line:secret}|// Secretly keep B here
    1767 release A
    1768 // Wakeup waiter and transfer A & B
    1769 \end{cfa}
    1770 \end{multicols}
    1771 \begin{cfa}[caption={Figure~\ref{f:int-bulk-cfa}, with delayed signalling comments},label={f:int-secret}]
    1772 \end{cfa}
     1618        mutex( m1, m2 ) {
     1619                ... `signal( c )`; ...
     1620                // m1, m2 acquired
     1621        } // $\LstCommentStyle{\color{red}release m2}$
     1622        // m1 acquired
     1623} // release m1
     1624\end{cfa}
     1625\end{lrbox}
     1626
     1627\newbox\myboxC
     1628\begin{lrbox}{\myboxC}
     1629\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1630
     1631
     1632mutex( m1 ) {
     1633        ... `wait( c )`; ...
     1634        // m1 acquired
     1635} // $\LstCommentStyle{\color{red}release m1}$
     1636
     1637
     1638
     1639
     1640\end{cfa}
     1641\end{lrbox}
     1642
     1643\begin{cquote}
     1644\subfloat[Waiting Thread]{\label{f:WaitingThread}\usebox\myboxA}
     1645\hspace{2\parindentlnth}
     1646\subfloat[Signalling Thread]{\label{f:SignallingThread}\usebox\myboxB}
     1647\hspace{2\parindentlnth}
     1648\subfloat[Other Waiting Thread]{\label{f:SignallingThread}\usebox\myboxC}
     1649\end{cquote}
     1650\caption{Barging Prevention}
     1651\label{f:BargingPrevention}
    17731652\end{figure}
    17741653
    1775 The 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.
    1776 The 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.
    1777 When 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.
    1778 This 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@.
    1779 There are three options:
    1780 
    1781 \subsubsection{Delaying Signals}
    17821654The 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.
    17831655It 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.
     
    17921664Depending on the order of signals (listing \ref{f:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
    17931665
     1666\begin{comment}
    17941667\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.
    17951668\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.
     
    18011674In 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.
    18021675
     1676
    18031677\subsubsection{Dependency graphs}
    1804 
    18051678
    18061679\begin{figure}
     
    18811754
    18821755\subsubsection{Partial Signalling} \label{partial-sig}
     1756\end{comment}
     1757
    18831758Finally, the solution that is chosen for \CFA is to use partial signalling.
    18841759Again 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@.
     
    18951770\end{itemize}
    18961771
    1897 % ======================================================================
    1898 % ======================================================================
     1772
    18991773\subsection{Signalling: Now or Later}
    1900 % ======================================================================
    1901 % ======================================================================
    1902 \begin{table}
    1903 \begin{tabular}{|c|c|}
    1904 @signal@ & @signal_block@ \\
    1905 \hline
    1906 \begin{cfa}[tabsize=3]
    1907 monitor DatingService {
    1908         // compatibility codes
    1909         enum{ CCodes = 20 };
    1910 
    1911         int girlPhoneNo
    1912         int boyPhoneNo;
     1774
     1775\begin{figure}
     1776\centering
     1777\newbox\myboxA
     1778\begin{lrbox}{\myboxA}
     1779\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1780enum { CCodes = 20 };
     1781monitor DS {
     1782        int GirlPhNo, BoyPhNo;
     1783        condition Girls[CCodes], Boys[CCodes];
     1784        condition exchange;
    19131785};
    1914 
    1915 condition girls[CCodes];
    1916 condition boys [CCodes];
    1917 condition exchange;
    1918 
    1919 int girl(int phoneNo, int cfa) {
    1920         // no compatible boy ?
    1921         if(empty(boys[cfa])) {
    1922                 wait(girls[cfa]);               // wait for boy
    1923                 girlPhoneNo = phoneNo;          // make phone number available
    1924                 signal(exchange);               // wake boy from chair
     1786int girl( DS & mutex ds, int phNo, int ccode ) {
     1787        if ( is_empty( Boys[ccode] ) ) {
     1788                wait( Girls[ccode] );
     1789                GirlPhNo = phNo;
     1790                exchange.signal();
    19251791        } else {
    1926                 girlPhoneNo = phoneNo;          // make phone number available
    1927                 signal(boys[cfa]);              // wake boy
    1928                 wait(exchange);         // sit in chair
    1929         }
    1930         return boyPhoneNo;
    1931 }
    1932 int boy(int phoneNo, int cfa) {
    1933         // same as above
    1934         // with boy/girl interchanged
    1935 }
    1936 \end{cfa}&\begin{cfa}[tabsize=3]
    1937 monitor DatingService {
    1938 
    1939         enum{ CCodes = 20 };    // compatibility codes
    1940 
    1941         int girlPhoneNo;
    1942         int boyPhoneNo;
     1792                GirlPhNo = phNo;
     1793                signal( Boys[ccode] );
     1794                exchange.wait();
     1795        } // if
     1796        return BoyPhNo;
     1797}
     1798int boy( DS & mutex ds, int phNo, int ccode ) {
     1799        // as above with boy/girl interchanged
     1800}
     1801\end{cfa}
     1802\end{lrbox}
     1803
     1804\newbox\myboxB
     1805\begin{lrbox}{\myboxB}
     1806\begin{cfa}[aboveskip=0pt,belowskip=0pt]
     1807
     1808monitor DS {
     1809        int GirlPhNo, BoyPhNo;
     1810        condition Girls[CCodes], Boys[CCodes];
     1811
    19431812};
    1944 
    1945 condition girls[CCodes];
    1946 condition boys [CCodes];
    1947 // exchange is not needed
    1948 
    1949 int girl(int phoneNo, int cfa) {
    1950         // no compatible boy ?
    1951         if(empty(boys[cfa])) {
    1952                 wait(girls[cfa]);               // wait for boy
    1953                 girlPhoneNo = phoneNo;          // make phone number available
    1954                 signal(exchange);               // wake boy from chair
     1813int girl( DS & mutex ds, int phNo, int ccode ) {
     1814        if ( is_empty( Boys[ccode] ) ) { // no compatible
     1815                wait( Girls[ccode] ); // wait for boy
     1816                GirlPhNo = phNo; // make phone number available
     1817
    19551818        } else {
    1956                 girlPhoneNo = phoneNo;          // make phone number available
    1957                 signal_block(boys[cfa]);                // wake boy
    1958 
    1959                 // second handshake unnecessary
    1960 
    1961         }
    1962         return boyPhoneNo;
    1963 }
    1964 
    1965 int boy(int phoneNo, int cfa) {
    1966         // same as above
    1967         // with boy/girl interchanged
    1968 }
    1969 \end{cfa}
    1970 \end{tabular}
    1971 \caption{Dating service example using \protect\lstinline|signal| and \protect\lstinline|signal_block|. }
    1972 \label{tbl:datingservice}
    1973 \end{table}
     1819                GirlPhNo = phNo; // make phone number available
     1820                signal_block( Boys[ccode] ); // restart boy
     1821
     1822        } // if
     1823        return BoyPhNo;
     1824}
     1825int boy( DS & mutex ds, int phNo, int ccode ) {
     1826        // as above with boy/girl interchanged
     1827}
     1828\end{cfa}
     1829\end{lrbox}
     1830
     1831\subfloat[\lstinline@signal@]{\label{f:DatingSignal}\usebox\myboxA}
     1832\qquad
     1833\subfloat[\lstinline@signal_block@]{\label{f:DatingSignalBlock}\usebox\myboxB}
     1834\caption{Dating service. }
     1835\label{f:Dating service}
     1836\end{figure}
     1837
    19741838An important note is that, until now, signalling a monitor was a delayed operation.
    19751839The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the @signal@ statement.
     
    19881852% ======================================================================
    19891853An alternative to internal scheduling is external scheduling (see Table~\ref{tbl:sched}).
     1854
     1855\begin{comment}
    19901856\begin{table}
    19911857\begin{tabular}{|c|c|c|}
     
    20511917\label{tbl:sched}
    20521918\end{table}
     1919\end{comment}
     1920
    20531921This method is more constrained and explicit, which helps users reduce the non-deterministic nature of concurrency.
    20541922Indeed, as the following examples demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occurring.
Note: See TracChangeset for help on using the changeset viewer.