Changeset fe84230 for doc/proposals


Ignore:
Timestamp:
Nov 7, 2016, 10:47:32 AM (7 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:
84118d8
Parents:
9a8dfcc
Message:
  • Added custom style file.
  • Updated text up-to internal scheduling
Location:
doc/proposals/concurrency
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed

  • doc/proposals/concurrency/concurrency.tex

    r9a8dfcc rfe84230  
    11% requires tex packages: texlive-base texlive-latex-base tex-common texlive-humanities texlive-latex-extra texlive-fonts-recommended
    22
    3 % inline code ©...© (copyright symbol) emacs: C-q M-)
    4 % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
    5 % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
    6 % green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
    7 % LaTex escape §...§ (section symbol) emacs: C-q M-'
    8 % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
     3% inline code �...� (copyright symbol) emacs: C-q M-)
     4% red highlighting �...� (registered trademark symbol) emacs: C-q M-.
     5% blue highlighting �...� (sharp s symbol) emacs: C-q M-_
     6% green highlighting �...� (cent symbol) emacs: C-q M-"
     7% LaTex escape �...� (section symbol) emacs: C-q M-'
     8% keyword escape �...� (pilcrow symbol) emacs: C-q M-^
    99% math escape $...$ (dollar symbol)
    1010
    … …  
    3535\usepackage{fancyhdr}
    3636\renewcommand{\linenumberfont}{\scriptsize\sffamily}
    37 \input{common}                                                  % bespoke macros used in the document
     37\input{style}                                                   % bespoke macros used in the document
    3838\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
    3939\usepackage{breakurl}
    … …  
    153153        void ?{}(counter_t & nomutex this);
    154154        size_t ++?(counter_t & mutex this);
    155         void ?{}(size_t * this, counter_t & mutex cnt); //need for mutex is platform dependent here
     155
     156        //need for mutex is platform dependent here
     157        void ?{}(size_t * this, counter_t & mutex cnt);
    156158\end{lstlisting}
    157159*semantics of the declaration of \code{mutex struct counter_t} are discussed in details in section \ref{data}
    … …  
    195197        }
    196198
    197         void ?{}(int * this, counter_t & mutex cnt) { //need for mutex is platform dependent here
     199        //need for mutex is platform dependent here
     200        void ?{}(int * this, counter_t & mutex cnt) {
    198201                *this = (int)cnt;
    199202        }
    … …  
    224227\end{lstlisting}
    225228
    226 This code acquires both locks before entering the critical section. In practice, writing multi-locking routines that can not lead to deadlocks can be tricky. Having language support for such a feature is therefore a significant asset for \CFA. In the case presented above, \CFA guarantees that the order of aquisition will be consistent across calls to routines using the same monitors as arguments. However, since \CFA monitors use multi-acquiring locks users can effectively force the acquiring order. For example, notice which routines use \code{mutex}/\code{nomutex} and how this affects aquiring order :
     229This code acquires both locks before entering the critical section (Referenced as \gls{group-acquire} from now on). In practice, writing multi-locking routines that can not lead to deadlocks can be tricky. Having language support for such a feature is therefore a significant asset for \CFA. In the case presented above, \CFA guarantees that the order of aquisition will be consistent across calls to routines using the same monitors as arguments. However, since \CFA monitors use multi-acquiring locks users can effectively force the acquiring order. For example, notice which routines use \code{mutex}/\code{nomutex} and how this affects aquiring order :
    227230\begin{lstlisting}
    228231        void foo(A & mutex a, B & mutex a) {
    … …  
    282285
    283286\subsection{Internal scheduling} \label{insched}
    284 Monitors should also be able to schedule what threads access it 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 wait for them to be signaled. Here is a simple example of such a technique :
     287Monitors also need to schedule waiting threads within it 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 :
    285288
    286289\begin{lstlisting}
    … …  
    300303\end{lstlisting}
    301304
    302 Here routine \code{foo} waits on 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.
    303 
     305Here 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.
    304306\begin{center}
    305307\begin{tabular}{ c @{\hskip 0.65in} c }
    … …  
    307309\begin{lstlisting}
    308310void foo(monitor & mutex a,
    309          monitor & mutex b) {
     311           monitor & mutex b) {
    310312        //...
    311313        wait(a.e);
    … …  
    316318\end{lstlisting} &\begin{lstlisting}
    317319void bar(monitor & mutex a,
    318          monitor & mutex b) {
     320           monitor & mutex b) {
    319321        signal(a.e);
    320322}
    … …  
    326328\end{tabular}
    327329\end{center}
    328 
    329 A direct extension of the single monitor semantics would be 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. On the technical side, partially releasing lock is feasible but from the user perspective a choice must be made for the syntax of this feature. It is possible to do without any extra syntax by relying on order of acquisition (Note that here the use of helper routines is irrelevant, only routines the acquire mutual exclusion have an impact on internal scheduling):
     330A 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):
    330331
    331332\begin{center}
    … …  
    337338
    338339void foo(monitor & mutex a,
    339          monitor & mutex b) {
     340           monitor & mutex b) {
     341
    340342        wait(e);
    341343}
    … …  
    351353
    352354void bar(monitor & mutex a,
    353          monitor & nomutex b) {
     355           monitor & nomutex b) {
    354356        foo(a,b);
    355357}
    356358
    357359void foo(monitor & mutex a,
    358          monitor & mutex b) {
     360           monitor & mutex b) {
    359361        wait(e);
    360362}
    … …  
    365367
    366368void bar(monitor & mutex a,
    367          monitor & nomutex b) {
    368         foo(a,b);
     369           monitor & nomutex b) {
     370        baz(a,b);
    369371}
    370372
    371373void baz(monitor & nomutex a,
    372          monitor & mutex b) {
     374           monitor & mutex b) {
    373375        wait(e);
    374376}
    … …  
    379381\end{center}
    380382
    381 This can be interpreted in two different ways :
    382 \begin{flushleft}
    383 \begin{enumerate}
    384         \item \code{wait} atomically releases the monitors acquired by the inner-most routine, \underline{ignoring} nested calls.
    385         \item \code{wait} atomically releases the monitors acquired by the inner-most routine, \underline{considering} nested calls.
    386 \end{enumerate}
    387 \end{flushleft}
    388 While the difference between these two is subtle, it has a significant impact. In the first case it means that the calls to \code{foo} would behave the same in Context 1 and 2. This semantic would also mean that the call to \code{wait} in routine \code{baz} would only release \code{monitor b}. While this may seem intuitive with these examples, it does have one significant implication, it creates a strong distinction between acquiring multiple monitors in sequence and acquiring the same monitors simulatenously, i.e. :
     383Note that in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Context 1 is the simplest way of acquiring more than one monitor (\gls{group-acquire}), using a routine wiht 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 will 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.
     384
    389385
    390386\begin{center}
    391 \begin{tabular}{c @{\hskip 0.35in} c @{\hskip 0.35in} c}
    392 \begin{lstlisting}
    393 enterMonitor(a);
    394 enterMonitor(b);
    395 // do stuff
    396 leaveMonitor(b);
    397 leaveMonitor(a);
    398 \end{lstlisting} & != &\begin{lstlisting}
    399 enterMonitor(a);
    400 enterMonitor(a, b);
    401 // do stuff
    402 leaveMonitor(a, b);
    403 leaveMonitor(a);
     387\begin{tabular}{|c|c|c|}
     388\begin{lstlisting}
     389condition e;
     390
     391//acquire a
     392void foo(monitor & nomutex a,
     393           monitor & mutex b) {
     394        bar(a,b);
     395}
     396
     397//acquire a
     398void bar(monitor & mutex a,
     399           monitor & nomutex b) {
     400
     401        //release a
     402        //keep b
     403        wait(e);
     404}
     405
     406foo(a, b);
     407\end{lstlisting} &\begin{lstlisting}
     408condition e;
     409
     410//acquire a & b
     411void foo(monitor & mutex a,
     412           monitor & mutex b) {
     413        bar(a,b);
     414}
     415
     416//acquire b
     417void bar(monitor & mutex a,
     418           monitor & nomutex b) {
     419
     420        //release b
     421        //keep a
     422        wait(e);
     423}
     424
     425foo(a, b);
     426\end{lstlisting} &\begin{lstlisting}
     427condition e;
     428
     429//acquire a & b
     430void foo(monitor & mutex a,
     431           monitor & mutex b) {
     432        bar(a,b);
     433}
     434
     435//acquire none
     436void bar(monitor & nomutex a,
     437           monitor & nomutex b) {
     438
     439        //release a & b
     440        //keep none
     441        wait(e);
     442}
     443
     444foo(a, b);
    404445\end{lstlisting}
    405446\end{tabular}
    406447\end{center}
    407 
    408 This is not intuitive because even if both methods display the same monitors state both inside and outside the critical section respectively, the behavior is different. Furthermore, the actual acquiring order will be exaclty the same since acquiring a monitor from inside its mutual exclusion is a no-op. This means that even if the data and the actual control flow are the same using both methods, the behavior of the \code{wait} will be different. The alternative is option 2, that is releasing acquired monitors, \underline{considering} nesting. This solves the issue of having the two acquiring method differ at the cost of making routine \code{foo} behave differently depending on from which context it is called (Context 1 or 2). Indeed in Context 2, routine \code{foo} actually behaves like routine \code{baz} rather than having the same behavior than in Context 1. The fact that both implicit approaches can be unintuitive depending on the perspective may be a sign that the explicit approach is superior. For this reason this \CFA does not support implicit monitor releasing and uses explicit semantics.
    409 \\
    410 
    411 The following examples shows three alternatives of explicit wait semantics :
    412 \\
    413 
    414 \begin{center}
    415 \begin{tabular}{|c|c|c|}
    416 Case 1 & Case 2 & Case 3 \\
    417 Branding on construction & Explicit release list & Explicit ignore list \\
    418 \hline
    419 \begin{lstlisting}
    420 void foo(monitor & mutex a,
    421          monitor & mutex b,
    422            condition & c)
    423 {
    424         // Releases monitors
    425         // branded in ctor
    426         wait(c);
    427 }
    428 
    429 monitor a;
    430 monitor b;
    431 condition1 c1 = {a};
    432 condition2 c2 = {a, b};
    433 
    434 //Will release only a
    435 foo(a,b,c1);
    436 
    437 //Will release a and b
    438 foo(a,b,c2);
    439 \end{lstlisting} &\begin{lstlisting}
    440 void foo(monitor & mutex a,
    441          monitor & mutex b,
    442            condition & c)
    443 {
    444         // Releases monitor a
    445         // Holds monitor b
    446         waitRelease(c, [a]);
    447 }
    448 
    449 monitor a;
    450 monitor b;
    451 condition c;
    452 
    453 
    454 
    455 foo(a,b,c);
    456 
    457 
    458 
    459 \end{lstlisting} &\begin{lstlisting}
    460 void foo(monitor & mutex a,
    461          monitor & mutex b,
    462            condition & c)
    463 {
    464         // Releases monitor a
    465         // Holds monitor b
    466         waitHold(c, [b]);
    467 }
    468 
    469 monitor a;
    470 monitor b;
    471 condition c;
    472 
    473 
    474 
    475 foo(a,b,c);
    476 
    477 
    478 
    479 \end{lstlisting}
    480 \end{tabular}
    481 \end{center}
    482 (Note : Case 2 and 3 use tuple semantics to pass a variable length list of elements.)
    483 \\
    484 
    485 All these cases have their pros and cons. Case 1 is more distinct because it means programmers need to be carefull about where the condition is initialized as well as where it is used. On the other hand, it is very clear and explicitly states which monitor is released and which monitor stays acquired. This is similar to Case 2, which releases only the monitors explictly listed. However, in Case 2, calling the \code{wait} routine instead of the \code{waitRelease} routine releases all the acquired monitor. The Case 3 is an improvement on that since it releases all the monitors except those specified. The result is that the \code{wait} routine can be written as follows :
    486 \begin{lstlisting}
    487 void wait(condition & cond) {
    488         waitHold(cond, []);
    489 }
    490 \end{lstlisting}
    491 This alternative offers nice and consistent behavior between \code{wait} and \code{waitHold}. However, one large pitfall is that mutual exclusion can now be violated by calls to library code. Indeed, even if the following example seems benign there is one significant problem :
    492 \begin{lstlisting}
    493 monitor global;
    494 
    495 extern void doStuff(); //uses global
    496 
    497 void foo(monitor & mutex m) {
    498         //...
    499         doStuff(); //warning can release monitor m
    500         //...
    501 }
    502 
    503 foo(global);
    504 \end{lstlisting}
    505 
    506 Indeed, if Case 2 or 3 are chosen it any code can violate the mutual exclusion of the calling code by issuing calls to \code{wait} or \code{waitHold} in a nested monitor context. Case 2 can be salvaged by removing the \code{wait} routine from the API but Case 3 cannot prevent users from calling \code{waitHold(someCondition, [])}. For this reason the syntax proposed in Case 3 is rejected. Note that the syntax proposed in case 1 and 2 are not exclusive. Indeed, by supporting two types of condition both cases can be supported :
    507 \begin{lstlisting}
    508 struct condition { /*...*/ };
    509 
    510 // Second argument is a variable length tuple.
    511 void wait(condition & cond, [...] monitorsToRelease);
    512 void signal(condition & cond);
    513 
    514 struct conditionN { /*...*/ };
    515 
    516 void ?{}(conditionN* this, /*list of N monitors to release*/);
    517 void wait(conditionN & cond);
    518 void signal(conditionN & cond);
    519 \end{lstlisting}
    520 
    521 Regardless of the option chosen for wait semantics, signal must be symmetrical. 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.
    522 
    523 Finally, an additionnal semantic which can be very usefull is the \code{signalBlock} 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.
     448Note the right-most example which uses a helper routine and therefore is not relevant to find which monitors will be released.
     449
     450These 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.
     451
     452Regardless of the context in which the \code{wait} statement is used, \code{signal} must used 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.
     453
     454Finally, 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.
    524455\\
    525456
    … …  
    531462% #        #   #     #    ###    #     # #     # #     # #       #     #
    532463% ####### #     #    #    ###     #####   #####  #     # ####### ######
    533 
     464\newpage
    534465\subsection{External scheduling} \label{extsched}
    535466As one might expect, the alternative to Internal scheduling is to use External scheduling instead. This method is somewhat more robust to deadlocks since one of the threads keeps a relatively tight control on scheduling. Indeed, as the following examples will demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occuring. External scheduling can generally be done either in terms of control flow (ex: \uC) or in terms of data (ex: Go). Of course, both of these paradigms have their own strenghts and weaknesses but for this project control flow semantics where chosen to stay consistent with the rest of the languages semantics. Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multi-monitor routines. The following example shows what a simple use \code{accept} versus \code{wait}/\code{signal} and its advantages.

  • doc/proposals/concurrency/glossary.tex

    r9a8dfcc rfe84230  
    1111{
    1212Locking done by the called routine. With this technique, a monitor routine called by another routine will aquire the monitor \emph{after} entering the routine body but prior to any other code.
     13}
     14
     15\longnewglossaryentry{group-acquire}
     16{name={grouped acquiring}}
     17{
     18Implicitly acquiring several monitors when entering a monitor.
    1319}
    1420

  • doc/proposals/concurrency/version

    r9a8dfcc rfe84230  
    1 0.5.116
     10.5.146
Note: See TracChangeset for help on using the changeset viewer.