Changeset 154fdc8 for doc/proposals


Ignore:
Timestamp:
Apr 19, 2017, 10:15:45 AM (8 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
cd348e7
Parents:
221c2de7 (diff), de4ce0e (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc/proposals/concurrency
Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed

  • TabularUnified doc/proposals/concurrency/concurrency.tex

    r221c2de7 r154fdc8  
    6161\newcommand{\uC}{$\mu$\CC}
    6262\newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace}
    63 \newcommand{\code}[1]{\lstinline{#1}}
     63\newcommand{\code}[1]{\lstinline[language=CFA]{#1}}
    6464\newcommand{\pseudo}[1]{\lstinline[language=Pseudo]{#1}}
    6565
    … …  
    160160Here, the constructor(\code{?\{\}}) uses the \code{nomutex} keyword to signify that it does not acquire the monitor mutual exclusion when constructing. This semantics is because an object not yet constructed should never be shared and therefore does not require mutual exclusion. The prefix increment operator uses \code{mutex} to protect the incrementing process from race conditions. Finally, there is a conversion operator from \code{counter_t} to \code{size_t}. This conversion may or may not require the \code{mutex} key word depending on whether or not reading an \code{size_t} is an atomic operation or not.
    161161
    162 Having both \code{mutex} and \code{nomutex} keywords could be argued to be redundant based on the meaning of a routine having neither of these keywords. For example, given a routine without wualifiers \code{void foo(counter_t & this)} then one could argue that it should default to the safest option \code{mutex}. On the other hand, the option of having routine \code{void foo(counter_t & this)} mean \code{nomutex} is unsafe by default and may easily cause subtle errors. It can be argued that \code{nomutex} is the more "normal" behaviour, the \code{nomutex} keyword effectively stating explicitly that "this routine has nothing special". Another alternative is to make having exactly one of these keywords mandatory, which would provide the same semantics but without the ambiguity of supporting routine \code{void foo(counter_t & this)}. Mandatory keywords would also have the added benefice of being self-documented but at the cost of extra typing. In the end, which solution should be picked is still up for debate. For the reminder of this proposal, the explicit approach is used for clarity.
     162Having both \code{mutex} and \code{nomutex} keywords could be argued to be redundant based on the meaning of a routine having neither of these keywords. For example, given a routine without quualifiers \code{void foo(counter_t & this)} then one could argue that it should default to the safest option \code{mutex}. On the other hand, the option of having routine \code{void foo(counter_t & this)} mean \code{nomutex} is unsafe by default and may easily cause subtle errors. It can be argued that \code{nomutex} is the more "normal" behaviour, the \code{nomutex} keyword effectively stating explicitly that "this routine has nothing special". Another alternative is to make having exactly one of these keywords mandatory, which would provide the same semantics but without the ambiguity of supporting routine \code{void foo(counter_t & this)}. Mandatory keywords would also have the added benefice of being self-documented but at the cost of extra typing. In the end, which solution should be picked is still up for debate. For the reminder of this proposal, the explicit approach is used for clarity.
    163163
    164164The next semantic decision is to establish when mutex/nomutex may be used as a type qualifier. Consider the following declarations:
    … …  
    350350
    351351\subsection{Internal scheduling} \label{insched}
    352 Monitors also need to schedule waiting threads internally as a mean of synchronization. Internal scheduling is one of the simple examples of such a feature. It allows users to declare condition variables and have threads wait and signaled from them. Here is a simple example of such a technique :
    353 
    354 \begin{lstlisting}
    355         mutex struct A {
    356                 condition e;
    357         }
    358 
    359         void foo(A & mutex a) {
    360                 //...
    361                 wait(a.e);
    362                 //...
    363         }
    364 
    365         void bar(A & mutex a) {
    366                 signal(a.e);
    367         }
    368 \end{lstlisting}
    369 
    370 Note that in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering. This semantic can easily be extended to multi-monitor calls by offering the same guarantee.
     352
    371353\begin{center}
    372354\begin{tabular}{ c @{\hskip 0.65in} c }
    373 Thread 1 & Thread 2 \\
    374 \begin{lstlisting}
    375 void foo(monitor & mutex a,
    376            monitor & mutex b) {
    377         //...
    378         wait(a.e);
    379         //...
    380 }
    381 
    382 foo(a, b);
    383 \end{lstlisting} &\begin{lstlisting}
    384 void bar(monitor & mutex a,
    385            monitor & mutex b) {
    386         signal(a.e);
    387 }
    388 
    389 
    390 
    391 bar(a, b);
     355\begin{lstlisting}[language=Pseudo]
     356acquire A
     357        wait A
     358release A
     359\end{lstlisting}&\begin{lstlisting}[language=Pseudo]
     360acquire A
     361        signal A
     362release A
    392363\end{lstlisting}
    393364\end{tabular}
    394365\end{center}
    395 A direct extension of the single monitor semantics is to release all locks when waiting and transferring ownership of all locks when signalling. However, for the purpose of synchronization it may be usefull to only release some of the locks but keep others. It is possible to support internal scheduling and \gls{group-acquire} without any extra syntax by relying on order of acquisition. Here is an example of the different contexts in which internal scheduling can be used. (Note that here the use of helper routines is irrelevant, only routines acquire mutual exclusion have an impact on internal scheduling):
     366
     367Easy : like uC++
    396368
    397369\begin{center}
    398 \begin{tabular}{|c|c|c|}
    399 Context 1 & Context 2 & Context 3 \\
    400 \hline
    401 \begin{lstlisting}
    402 condition e;
    403 
    404 //acquire a & b
    405 void foo(monitor & mutex a,
    406            monitor & mutex b) {
    407 
    408         wait(e); //release a & b
    409 }
    410 
    411 
    412 
    413 
    414 
    415 
    416 foo(a,b);
    417 \end{lstlisting} &\begin{lstlisting}
    418 condition e;
    419 
    420 //acquire a
    421 void bar(monitor & mutex a,
    422            monitor & nomutex b) {
    423         foo(a,b);
    424 }
    425 
    426 //acquire a & b
    427 void foo(monitor & mutex a,
    428            monitor & mutex b) {
    429         wait(e);  //release a & b
    430 }
    431 
    432 bar(a, b);
    433 \end{lstlisting} &\begin{lstlisting}
    434 condition e;
    435 
    436 //acquire a
    437 void bar(monitor & mutex a,
    438            monitor & nomutex b) {
    439         baz(a,b);
    440 }
    441 
    442 //acquire b
    443 void baz(monitor & nomutex a,
    444            monitor & mutex b) {
    445         wait(e);  //release b
    446 }
    447 
    448 bar(a, b);
     370\begin{tabular}{ c @{\hskip 0.65in} c }
     371\begin{lstlisting}[language=Pseudo]
     372acquire A
     373        acquire B
     374                wait B
     375        release B
     376release A
     377\end{lstlisting}&\begin{lstlisting}[language=Pseudo]
     378acquire A
     379        acquire B
     380                signal B
     381        release B
     382release A
    449383\end{lstlisting}
    450384\end{tabular}
    451385\end{center}
    452386
    453 Context 1 is the simplest way of acquiring more than one monitor (\gls{group-acquire}), using a routine with multiple parameters having the \code{mutex} keyword. Context 2 also uses \gls{group-acquire} as well in routine \code{foo}. However, the routine is called by routine \code{bar}, which only acquires monitor \code{a}. Since monitors can be acquired multiple times this does not cause a deadlock by itself but it does force the acquiring order to \code{a} then \code{b}. Context 3 also forces the acquiring order to be \code{a} then \code{b} but does not use \gls{group-acquire}. The previous example tries to illustrate the semantics that must be established to support releasing monitors in a \code{wait} statement. In all cases, the behavior of the wait statment is to release all the locks that were acquired my the inner-most monitor call. That is \code{a & b} in context 1 and 2 and \code{b} only in context 3. Here are a few other examples of this behavior.
    454 
     387Also easy : like uC++
    455388
    456389\begin{center}
    457 \begin{tabular}{|c|c|c|}
    458 \begin{lstlisting}
    459 condition e;
    460 
    461 //acquire b
    462 void foo(monitor & nomutex a,
    463            monitor & mutex b) {
    464         bar(a,b);
    465 }
    466 
    467 //acquire a
    468 void bar(monitor & mutex a,
    469            monitor & nomutex b) {
    470 
    471         wait(e); //release a
    472                   //keep b
    473 }
    474 
    475 foo(a, b);
    476 \end{lstlisting} &\begin{lstlisting}
    477 condition e;
    478 
    479 //acquire a & b
    480 void foo(monitor & mutex a,
    481            monitor & mutex b) {
    482         bar(a,b);
    483 }
    484 
    485 //acquire b
    486 void bar(monitor & mutex a,
    487            monitor & nomutex b) {
    488 
    489         wait(e); //release b
    490                   //keep a
    491 }
    492 
    493 foo(a, b);
    494 \end{lstlisting} &\begin{lstlisting}
    495 condition e;
    496 
    497 //acquire a & b
    498 void foo(monitor & mutex a,
    499            monitor & mutex b) {
    500         bar(a,b);
    501 }
    502 
    503 //acquire none
    504 void bar(monitor & nomutex a,
    505            monitor & nomutex b) {
    506 
    507         wait(e); //release a & b
    508                   //keep none
    509 }
    510 
    511 foo(a, b);
     390\begin{tabular}{ c @{\hskip 0.65in} c }
     391\begin{lstlisting}[language=Pseudo]
     392acquire A & B
     393        wait A & B
     394release A & B
     395\end{lstlisting}&\begin{lstlisting}[language=Pseudo]
     396acquire A & B
     397        signal A & B
     398release A & B
    512399\end{lstlisting}
    513400\end{tabular}
    514401\end{center}
    515 Note the right-most example is actually a trick pulled on the reader. Monitor state information is stored in thread local storage rather then in the routine context, which means that helper routines and other \code{nomutex} routines are invisible to the runtime system in regards to concurrency. This means that in the right-most example, the routine parameters are completly unnecessary. However, calling this routine from outside a valid monitor context is undefined.
    516 
    517 These semantics imply that in order to release of subset of the monitors currently held, users must write (and name) a routine that only acquires the desired subset and simply calls wait. While users can use this method, \CFA offers the \code{wait_release}\footnote{Not sure if an overload of \code{wait} would work...} which will release only the specified monitors. In the center previous examples, the code in the center uses the \code{bar} routine to only release monitor \code{b}. Using the \code{wait_release} helper, this can be rewritten without having the name two routines :
     402
     403Simplest extension : can be made like uC++ by tying B to A
     404
    518405\begin{center}
    519 \begin{tabular}{ c c c }
    520 \begin{lstlisting}
    521         condition e;
    522 
    523         //acquire a & b
    524         void foo(monitor & mutex a,
    525                    monitor & mutex b) {
    526                 bar(a,b);
    527         }
    528 
    529         //acquire b
    530         void bar(monitor & mutex a,
    531                    monitor & nomutex b) {
    532 
    533                 wait(e); //release b
    534                           //keep a
    535         }
    536 
    537         foo(a, b);
    538 \end{lstlisting} &\begin{lstlisting}
    539         =>
    540 \end{lstlisting} &\begin{lstlisting}
    541         condition e;
    542 
    543         //acquire a & b
    544         void foo(monitor & mutex a,
    545                    monitor & mutex b) {
    546                 wait_release(e,b); //release b
    547                                          //keep a
    548         }
    549 
    550         foo(a, b);
     406\begin{tabular}{ c @{\hskip 0.65in} c }
     407\begin{lstlisting}[language=Pseudo]
     408acquire A
     409        // Code Section 1
     410        acquire B
     411                // Code Section 2
     412                wait A & B
     413                // Code Section 3
     414        release B
     415        // Code Section 4
     416release A
     417\end{lstlisting}&\begin{lstlisting}[language=Pseudo]
     418acquire A
     419        // Code Section 5
     420        acquire B
     421                // Code Section 6
     422                signal A & B
     423                // Code Section 7
     424        release B
     425        // Code Section 8
     426release A
    551427\end{lstlisting}
    552428\end{tabular}
    553429\end{center}
    554430
    555 Regardless of the context in which the \code{wait} statement is used, \code{signal} must be called holding the same set of monitors. In all cases, signal only needs a single parameter, the condition variable that needs to be signalled. But \code{signal} needs to be called from the same monitor(s) that call to \code{wait}. Otherwise, mutual exclusion cannot be properly transferred back to the waiting monitor.
    556 
    557 Finally, an additional semantic which can be very usefull is the \code{signal_block} routine. This routine behaves like signal for all of the semantics discussed above, but with the subtelty that mutual exclusion is transferred to the waiting task immediately rather than wating for the end of the critical section.
    558 \\
     431Hard extension :
     432
     433Incorrect options for the signal :
     434
     435\begin{description}
     436 \item[-] Release B and baton pass after Code Section 8 : Passing b without having it
     437 \item[-] Keep B during Code Section 8 : Can lead to deadlocks since we secretly keep a lock longer than specified by the user
     438 \item[-] Instead of release B transfer A and B to waiter then try to reacquire A before running Code Section 8 : This allows barging
     439\end{description}
     440
     441Since we don't want barging we need to pass A \& B and somehow block and get A back.
     442
     443\begin{center}
     444\begin{tabular}{ c @{\hskip 0.65in} c }
     445\begin{lstlisting}[language=Pseudo]
     446acquire A
     447        acquire B
     448                acquire C
     449                        wait A & B & C
     450                1: release C
     451        2: release B
     4523: release A
     453\end{lstlisting}&\begin{lstlisting}[language=Pseudo]
     454acquire A
     455        acquire B
     456                acquire C
     457                        signal A & B & C
     458                4: release C
     459        5: release B
     4606: release A
     461\end{lstlisting}
     462\end{tabular}
     463\end{center}
     464
     465To prevent barging :
     466
     467\begin{description}
     468 \item[-] When the signaller hits 4 : pass A, B, C to waiter
     469 \item[-] When the waiter hits 2 : pass A, B to signaller
     470 \item[-] When the signaller hits 5 : pass A to waiter
     471\end{description}
     472
     473
     474\begin{center}
     475\begin{tabular}{ c @{\hskip 0.65in} c }
     476\begin{lstlisting}[language=Pseudo]
     477acquire A
     478        acquire C
     479                acquire B
     480                        wait A & B & C
     481                1: release B
     482        2: release C
     4833: release A
     484\end{lstlisting}&\begin{lstlisting}[language=Pseudo]
     485acquire B
     486        acquire A
     487                acquire C
     488                        signal A & B & C
     489                4: release C
     490        5: release A
     4916: release B
     492\end{lstlisting}
     493\end{tabular}
     494\end{center}
     495
     496To prevent barging : When the signaller hits 4 : pass A, B, C to waiter. When the waiter hits 1 it must release B,
     497
     498\begin{description}
     499 \item[-]
     500 \item[-] When the waiter hits 1 : pass A, B to signaller
     501 \item[-] When the signaller hits 5 : pass A, B to waiter
     502 \item[-] When the waiter hits 2 : pass A to signaller
     503\end{description}
     504
     505% Monitors also need to schedule waiting threads internally as a mean of synchronization. Internal scheduling is one of the simple examples of such a feature. It allows users to declare condition variables and have threads wait and signaled from them. Here is a simple example of such a technique :
     506
     507% \begin{lstlisting}
     508%       mutex struct A {
     509%               condition e;
     510%       }
     511
     512%       void foo(A & mutex a) {
     513%               //...
     514%               wait(a.e);
     515%               //...
     516%       }
     517
     518%       void bar(A & mutex a) {
     519%               signal(a.e);
     520%       }
     521% \end{lstlisting}
     522
     523% Note that in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering.
     524
     525% As for simple mutual exclusion, these semantics must also be extended to include \gls{group-acquire} :
     526% \begin{center}
     527% \begin{tabular}{ c @{\hskip 0.65in} c }
     528% Thread 1 & Thread 2 \\
     529% \begin{lstlisting}
     530% void foo(A & mutex a,
     531%            A & mutex b) {
     532%       //...
     533%       wait(a.e);
     534%       //...
     535% }
     536
     537% foo(a, b);
     538% \end{lstlisting} &\begin{lstlisting}
     539% void bar(A & mutex a,
     540%            A & mutex b) {
     541%       signal(a.e);
     542% }
     543
     544
     545
     546% bar(a, b);
     547% \end{lstlisting}
     548% \end{tabular}
     549% \end{center}
     550
     551% To define the semantics of internal scheduling, it is important to look at nesting and \gls{group-acquire}. Indeed, beyond concerns about lock ordering, without scheduling the two following pseudo codes are mostly equivalent. In fact, if we assume monitors are ordered alphabetically, these two pseudo codes would probably lead to exactly the same implementation :
     552
     553% \begin{table}[h!]
     554% \centering
     555% \begin{tabular}{c c}
     556% \begin{lstlisting}[language=pseudo]
     557% monitor A, B, C
     558
     559% acquire A
     560%       acquire B & C
     561
     562%                       //Do stuff
     563
     564%       release B & C
     565% release A
     566% \end{lstlisting} &\begin{lstlisting}[language=pseudo]
     567% monitor A, B, C
     568
     569% acquire A
     570%       acquire B
     571%               acquire C
     572%                       //Do stuff
     573%               release C
     574%       release B
     575% release A
     576% \end{lstlisting}
     577% \end{tabular}
     578% \end{table}
     579
     580% Once internal scheduling is introduce however, semantics of \gls{group-acquire} become relevant. For example, let us look into the semantics of the following pseudo-code :
     581
     582% \begin{lstlisting}[language=Pseudo]
     583% 1: monitor A, B, C
     584% 2: condition c1
     585% 3:
     586% 4: acquire A
     587% 5:            acquire A & B & C
     588% 6:                            signal c1
     589% 7:            release A & B & C
     590% 8: release A
     591% \end{lstlisting}
     592
     593% Without \gls{group-acquire} signal simply baton passes the monitor lock on the next release. In the case above, we therefore need to indentify the next release. If line 8 is picked at the release point, then the signal will attempt to pass A \& B \& C, without having ownership of B \& C. Since this violates mutual exclusion, we conclude that line 7 is the only valid location where signalling can occur. The traditionnal meaning of signalling is to transfer ownership of the monitor(s) and immediately schedule the longest waiting task. However, in the discussed case, the signalling thread expects to maintain ownership of monitor A. This can be expressed in two differents ways : 1) the thread transfers ownership of all locks and reacquires A when it gets schedulled again or 2) it transfers ownership of all three monitors and then expects the ownership of A to be transferred back.
     594
     595% However, the question is does these behavior motivate supporting acquireing non-disjoint set of monitors. Indeed, if the previous example was modified to only acquire B \& C at line 5 (an release the accordingly) then in respects to scheduling, we could add the simplifying constraint that all monitors in a bulk will behave the same way, simplifying the problem back to a single monitor problem which has already been solved. For this constraint to be acceptble however, we need to demonstrate that in does not prevent any meaningful possibilities. And, indeed, we can look at the two previous interpretation of the above pseudo-code and conclude that supporting the acquiring of non-disjoint set of monitors does not add any expressiveness to the language.
     596
     597% Option 1 reacquires the lock after the signal statement, this can be rewritten as follows without the need for non-disjoint sets :
     598% \begin{lstlisting}[language=Pseudo]
     599% monitor A, B, C
     600% condition c1
     601
     602% acquire A & B & C
     603%       signal c1
     604% release A & B & C
     605% acquire A
     606
     607% release A
     608% \end{lstlisting}
     609
     610% This pseudo code has almost exaclty the same semantics as the code acquiring intersecting sets of monitors.
     611
     612% Option 2 uses two-way lock ownership transferring instead of reacquiring monitor A. Two-way monitor ownership transfer is normally done using signalBlock semantics, which immedietely transfers ownership of a monitor before getting the ownership back when the other thread no longer needs the monitor. While the example pseudo-code for Option 2 seems toe transfer ownership of A, B and C and only getting A back, this is not a requirement. Getting back all 3 monitors and releasing B and C differs only in performance. For this reason, the second option could arguably be rewritten as :
     613
     614% \begin{lstlisting}[language=Pseudo]
     615% monitor A, B, C
     616% condition c1
     617
     618% acquire A
     619%       acquire B & C
     620%               signalBlock c1
     621%       release B & C
     622% release A
     623% \end{lstlisting}
     624
     625% Obviously, the difference between these two snippets of pseudo code is that the first one transfers ownership of A, B and C while the second one only transfers ownership of B and C. However, this limitation can be removed by allowing user to release extra monitors when using internal scheduling, referred to as extended internal scheduling (pattent pending) from this point on. Extended internal scheduling means the two following pseudo-codes are functionnaly equivalent :
     626% \begin{table}[h!]
     627% \centering
     628% \begin{tabular}{c @{\hskip 0.65in} c}
     629% \begin{lstlisting}[language=pseudo]
     630% monitor A, B, C
     631% condition c1
     632
     633% acquire A
     634%       acquire B & C
     635%               signalBlock c1 with A
     636%       release B & C
     637% release A
     638% \end{lstlisting} &\begin{lstlisting}[language=pseudo]
     639% monitor A, B, C
     640% condition c1
     641
     642% acquire A
     643%       acquire A & B & C
     644%               signal c1
     645%       release A & B & C
     646% release A
     647% \end{lstlisting}
     648% \end{tabular}
     649% \end{table}
     650
     651% It must be stated that the extended internal scheduling only makes sense when using wait and signalBlock, since they need to prevent barging, which cannot be done in the context of signal since the ownership transfer is strictly one-directionnal.
     652
     653% One critic that could arise is that extended internal schedulling is not composable since signalBlock must be explicitly aware of which context it is in. However, this argument is not relevant since acquire A, B and C in a context where a subset of them is already acquired cannot be achieved without spurriously releasing some locks or having an oracle aware of all monitors. Therefore, composability of internal scheduling is no more an issue than composability of monitors in general.
     654
     655% The main benefit of using extended internal scheduling is that it offers the same expressiveness as intersecting monitor set acquiring but greatly simplifies the selection of a leader (or representative) for a group of monitor. Indeed, when using intersecting sets, it is not obvious which set intersects with other sets which means finding a leader representing only the smallest scope is a hard problem. Where as when using disjoint sets, any monitor that would be intersecting must be specified in the extended set, the leader can be chosen as any monitor in the primary set.
     656
     657% We need to make sure the semantics for internally scheduling N monitors are a natural extension of the single monitor semantics. For this reason, we introduce the concept of \gls{mon-ctx}. In terms of context internal scheduling means "releasing a \gls{mon-ctx} and waiting for an other thread to acquire the same \gls{mon-ctx} and baton-pass it back to the initial thread". This definitions requires looking into what a \gls{mon-ctx} is and what the semantics of waiting and baton-passing are.
     658
     659% \subsubsection{Internal scheduling: Context} \label{insched-context}
     660% Monitor scheduling operations are defined in terms of the context they are in. In languages that only supports operations on a single monitor at once, the context is completly defined by which most recently acquired monitors. Indeed, acquiring several monitors will form a stack of monitors which will be released in FILO order. In \CFA, a \gls{mon-ctx} cannot be simply defined by the last monitor that was acquired since \gls{group-acquire} means multiple monitors can be "the last monitor acquired". The \gls{mon-ctx} is therefore defined as the last set of monitors to have been acquired. This means taht when any new monitor is acquired, the group it belongs to is the new \gls{mon-ctx}. Correspondingly, if any monitor is released, the \gls{mon-ctx} reverts back to the context that was used prior to the monitor being acquired. In the most common case, \gls{group-acquire} means every monitor of a group will be acquired in released at the same time. However, since every monitor has its own recursion level, \gls{group-acquire} does not prevent users from reacquiring certain monitors while acquireing new monitors in the same operation. For example :
     661
     662% \begin{lstlisting}
     663% //Forward declarations
     664% monitor a, b, c
     665% void foo( monitor & mutex a,
     666%             monitor & mutex b);
     667% void bar( monitor & mutex a,
     668%             monitor & mutex b);
     669% void baz( monitor & mutex a,
     670%             monitor & mutex b,
     671%             monitor & mutex c);
     672
     673% //Routines defined inline to illustrate context changed compared to the stack
     674
     675% //main thread
     676% foo(a, b) {
     677%       //thread calls foo
     678%       //acquiring context a & b
     679
     680%       baz(a, b) {
     681%               //thread calls baz
     682%               //no context change
     683
     684%               bar(a, b, c) {
     685%                       //thread calls bar
     686%                       //acquiring context a & b & c
     687
     688%                       //Do stuff
     689
     690%                       return;             
     691%                       //call to bar returns
     692%               }
     693%               //context back to a & b
     694
     695%               return;
     696%               //call to baz returns
     697%       }
     698%       //no context change
     699
     700%       return;
     701%       //call to foo returns
     702% }
     703% //context back to initial state
     704
     705% \end{lstlisting}
     706
     707% As illustrated by the previous example, context changes can be caused by only one of the monitors comming into context or going out of context.
     708
     709% \subsubsection{Internal scheduling: Waiting} \label{insched-wait}
     710
     711% \subsubsection{Internal scheduling: Baton Passing} \label{insched-signal}
     712% Baton passing in internal scheduling is done in terms of \code{signal} and \code{signalBlock}\footnote{Arguably, \code{signal_now} is a more evocative name and \code{signal} could be changed appropriately. }. While \code{signalBlock} is the more straight forward way of baton passing, transferring ownership immediately, it must rely on \code{signal} which is why t is discussed first.
     713% \code{signal} has for effect to transfer the current context to another thread when the context would otherwise be released. This means that instead of releasing the concerned monitors, the first thread on the condition ready-queue is scheduled to run. The monitors are not released and when the signalled thread runs, it assumes it regained ownership of all the monitors it had in its context.
     714
     715% \subsubsection{Internal scheduling: Implementation} \label{insched-impl}
     716% Too implement internal scheduling, three things are need : a data structure for waiting tasks, a data structure for signalled task and a leaving procedure to run the signalled task. In the case of both data structures, it is desireable to have to use intrusive data structures in order to prevent the need for any dynamic allocation. However, in both cases being able to queue several items in the same position in a queue is non trivial, even more so in the presence of concurrency. However, within a given \gls{mon-ctx}, all monitors have exactly the same behavior in regards to scheduling. Therefore, the problem of queuing multiple monitors at once can be ignored by choosing one monitor to represent every monitor in a context. While this could prove difficult in other situations, \gls{group-acquire} requires that the monitors be sorted according to some stable predicate. Since monitors are sorted in all contexts, the representative can simply be the first in the list. Choosing a representative means a simple intrusive queue inside the condition is sufficient to implement the data structure for both waiting and signalled monitors.
     717
     718% Since \CFA monitors don't have a complete image of the \gls{mon-ctx}, choosing the representative and maintaning the current context information cannot easily be done by any single monitors. However, as discussed in section [Missing section here], monitor mutual exclusion is implemented using an raii object which is already in charge of sorting monitors. This object has a complete picture of the \gls{mon-ctx} which means it is well suited to choose the reprensentative and detect context changes.
     719
     720% \newpage
     721% \begin{lstlisting}
     722% void ctor( monitor ** _monitors, int _count ) {
     723%       bool ctx_changed = false;
     724%       for( mon in _monitors ) {
     725%               ctx_changed = acquire( mon ) || ctx_changed;
     726%       }
     727
     728%       if( ctx_changed ) {
     729%               set_representative();
     730%               set_context();
     731%       }
     732% }
     733
     734% void dtor( monitor ** _monitors, int _count ) {
     735%       if( context_will_exit( _monitors, count ) ) {
     736%               baton_pass();
     737%               return;
     738%       }
     739
     740%       for( mon in _monitors ) {
     741%               release( mon );
     742%       }
     743% }
     744
     745% \end{lstlisting}
     746
     747
     748
     749% A direct extension of the single monitor semantics is to release all locks when waiting and transferring ownership of all locks when signalling. However, for the purpose of synchronization it may be usefull to only release some of the locks but keep others. It is possible to support internal scheduling and \gls{group-acquire} without any extra syntax by relying on order of acquisition. Here is an example of the different contexts in which internal scheduling can be used. (Note that here the use of helper routines is irrelevant, only routines acquire mutual exclusion have an impact on internal scheduling):
     750
     751% \begin{table}[h!]
     752% \centering
     753% \begin{tabular}{|c|c|c|}
     754% Context 1 & Context 2 & Context 3 \\
     755% \hline
     756% \begin{lstlisting}
     757% condition e;
     758
     759% //acquire a & b
     760% void foo(monitor & mutex a,
     761%            monitor & mutex b) {
     762
     763%       wait(e); //release a & b
     764% }
     765
     766
     767
     768
     769
     770
     771% foo(a,b);
     772% \end{lstlisting} &\begin{lstlisting}
     773% condition e;
     774
     775% //acquire a
     776% void bar(monitor & mutex a,
     777%            monitor & nomutex b) {
     778%       foo(a,b);
     779% }
     780
     781% //acquire a & b
     782% void foo(monitor & mutex a,
     783%            monitor & mutex b) {
     784%       wait(e);  //release a & b
     785% }
     786
     787% bar(a, b);
     788% \end{lstlisting} &\begin{lstlisting}
     789% condition e;
     790
     791% //acquire a
     792% void bar(monitor & mutex a,
     793%            monitor & nomutex b) {
     794%       baz(a,b);
     795% }
     796
     797% //acquire b
     798% void baz(monitor & nomutex a,
     799%            monitor & mutex b) {
     800%       wait(e);  //release b
     801% }
     802
     803% bar(a, b);
     804% \end{lstlisting}
     805% \end{tabular}
     806% \end{table}
     807
     808% Context 1 is the simplest way of acquiring more than one monitor (\gls{group-acquire}), using a routine with multiple parameters having the \code{mutex} keyword. Context 2 also uses \gls{group-acquire} as well in routine \code{foo}. However, the routine is called by routine \code{bar}, which only acquires monitor \code{a}. Since monitors can be acquired multiple times this does not cause a deadlock by itself but it does force the acquiring order to \code{a} then \code{b}. Context 3 also forces the acquiring order to be \code{a} then \code{b} but does not use \gls{group-acquire}. The previous example tries to illustrate the semantics that must be established to support releasing monitors in a \code{wait} statement. In all cases, the behavior of the wait statment is to release all the locks that were acquired my the inner-most monitor call. That is \code{a & b} in context 1 and 2 and \code{b} only in context 3. Here are a few other examples of this behavior.
     809
     810
     811% \begin{center}
     812% \begin{tabular}{|c|c|c|}
     813% \begin{lstlisting}
     814% condition e;
     815
     816% //acquire b
     817% void foo(monitor & nomutex a,
     818%            monitor & mutex b) {
     819%       bar(a,b);
     820% }
     821
     822% //acquire a
     823% void bar(monitor & mutex a,
     824%            monitor & nomutex b) {
     825
     826%       wait(e); //release a
     827%                 //keep b
     828% }
     829
     830% foo(a, b);
     831% \end{lstlisting} &\begin{lstlisting}
     832% condition e;
     833
     834% //acquire a & b
     835% void foo(monitor & mutex a,
     836%            monitor & mutex b) {
     837%       bar(a,b);
     838% }
     839
     840% //acquire b
     841% void bar(monitor & mutex a,
     842%            monitor & nomutex b) {
     843
     844%       wait(e); //release b
     845%                 //keep a
     846% }
     847
     848% foo(a, b);
     849% \end{lstlisting} &\begin{lstlisting}
     850% condition e;
     851
     852% //acquire a & b
     853% void foo(monitor & mutex a,
     854%            monitor & mutex b) {
     855%       bar(a,b);
     856% }
     857
     858% //acquire none
     859% void bar(monitor & nomutex a,
     860%            monitor & nomutex b) {
     861
     862%       wait(e); //release a & b
     863%                 //keep none
     864% }
     865
     866% foo(a, b);
     867% \end{lstlisting}
     868% \end{tabular}
     869% \end{center}
     870% Note the right-most example is actually a trick pulled on the reader. Monitor state information is stored in thread local storage rather then in the routine context, which means that helper routines and other \code{nomutex} routines are invisible to the runtime system in regards to concurrency. This means that in the right-most example, the routine parameters are completly unnecessary. However, calling this routine from outside a valid monitor context is undefined.
     871
     872% These semantics imply that in order to release of subset of the monitors currently held, users must write (and name) a routine that only acquires the desired subset and simply calls wait. While users can use this method, \CFA offers the \code{wait_release}\footnote{Not sure if an overload of \code{wait} would work...} which will release only the specified monitors. In the center previous examples, the code in the center uses the \code{bar} routine to only release monitor \code{b}. Using the \code{wait_release} helper, this can be rewritten without having the name two routines :
     873% \begin{center}
     874% \begin{tabular}{ c c c }
     875% \begin{lstlisting}
     876%       condition e;
     877
     878%       //acquire a & b
     879%       void foo(monitor & mutex a,
     880%                  monitor & mutex b) {
     881%               bar(a,b);
     882%       }
     883
     884%       //acquire b
     885%       void bar(monitor & mutex a,
     886%                  monitor & nomutex b) {
     887
     888%               wait(e); //release b
     889%                         //keep a
     890%       }
     891
     892%       foo(a, b);
     893% \end{lstlisting} &\begin{lstlisting}
     894%       =>
     895% \end{lstlisting} &\begin{lstlisting}
     896%       condition e;
     897
     898%       //acquire a & b
     899%       void foo(monitor & mutex a,
     900%                  monitor & mutex b) {
     901%               wait_release(e,b); //release b
     902%                                        //keep a
     903%       }
     904
     905%       foo(a, b);
     906% \end{lstlisting}
     907% \end{tabular}
     908% \end{center}
     909
     910% Regardless of the context in which the \code{wait} statement is used, \code{signal} must be called holding the same set of monitors. In all cases, signal only needs a single parameter, the condition variable that needs to be signalled. But \code{signal} needs to be called from the same monitor(s) that call to \code{wait}. Otherwise, mutual exclusion cannot be properly transferred back to the waiting monitor.
     911
     912% Finally, an additional semantic which can be very usefull is the \code{signal_block} routine. This routine behaves like signal for all of the semantics discussed above, but with the subtelty that mutual exclusion is transferred to the waiting task immediately rather than wating for the end of the critical section.
     913% \\
    559914
    560915% ####### #     # #######         #####   #####  #     # ####### ######

  • TabularUnified doc/proposals/concurrency/glossary.tex

    r221c2de7 r154fdc8  
    1414
    1515\longnewglossaryentry{group-acquire}
    16 {name={bulked acquiring}}
     16{name={bulk acquiring}}
    1717{
    1818Implicitly acquiring several monitors when entering a monitor.
     19}
     20
     21\longnewglossaryentry{mon-ctx}
     22{name={monitor context}}
     23{
     24The state of the current thread regarding which monitors are owned.
    1925}
    2026

  • TabularUnified doc/proposals/concurrency/style.tex

    r221c2de7 r154fdc8  
    11\input{common}                                          % bespoke macros used in the document
     2
     3% \CFADefaultStyle
    24
    35\lstset{

  • TabularUnified doc/proposals/concurrency/version

    r221c2de7 r154fdc8  
    1 0.7.61
     10.7.141
Note: See TracChangeset for help on using the changeset viewer.