Changeset 7b69174 for doc

Sep 29, 2016, 10:48:02 AM (8 years ago)
Thierry Delisle <tdelisle@…>
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

New proposal version for Internal Scheduling semantics written

1 edited


  • doc/proposals/concurrency/concurrency.tex

    r694ee7d r7b69174  
    2526\usepackage{varioref}                                                                   % extended references
    2627\usepackage{listings}                                                                   % format program code
    196197\subsubsection{Internal scheduling}
    197 Monitors should also be able to do some sort of synchronization to be able to somewhat schedule what threads access it. 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 :
     198Monitors 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 :
    215 Here routine \texttt{foo} will wait on the \texttt{signal} from \texttt{bar} before making further progress, effectively ensuring a basic ordering. However, nothing prevents users from miss-using this syntax and therefore some additionnal protection would be useful. For example, if \texttt{bar} was rewritten as follows:
     216Here routine \texttt{foo} waits on the \texttt{signal} from \texttt{bar} before making further progress, effectively ensuring a basic ordering. This can easily be extended to multi-monitor calls by offering the same guarantee.
    217218\begin{tabular}{ c c }
    218219Thread 1 & Thread 2 \\
    220         void foo(monitor& mutex m) {
    221                 //...
    222                 wait(m.e);
    223                 //...
    224         }
    226         foo(a);
    227 \end{lstlisting}&\begin{lstlisting}
    228         void bar(monitor& mutex b, condition& e) {
    229                 signal(e);
    230         }
    234         bar(b, a.e);
     221void foo(monitor& mutex a, monitor& mutex b) {
     222        //...
     223        wait(a.e);
     224        //...
     227foo(a, b);
     229void bar(monitor& mutex a, monitor& mutex b) {
     230        signal(a.e);
     235bar(a, b);
    239 In this example, thread 2 tries to \texttt{signal} a condition variable for which it did not acquire the lock. There are at least two solutions to this problem. Either the wait routine tries to reacquire every needed lock upon exit or the signaller must implicitly transfer lock ownership to the signalled task. The first case can be easily implemented by hand and does not prevent any barging and therefore the second approach is preferred. This effectively means that condition variables need to be both aware of the locks used by the waiting task and the signaller. However, before we look at what this lock awareness means we need to look at another example to properly grasp the problem.
    241 \begin{tabular}{ c c }
    242 Thread 1 & Thread 2 \\
    243 \begin{lstlisting}
     240A 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 :
     243Context 1 & Context 2 & Context 3 \\
     246void foo(monitor& mutex a,
     247         monitor& mutex b) {
     248        wait(a.e);
     258void bar(monitor& mutex a,
     259         monitor& nomutex b) {
     260        foo(a,b);
     263void foo(monitor& mutex a,
     264         monitor& mutex b) {
     265        wait(a.e);
     268bar(a, b);
     270void bar(monitor& mutex a,
     271         monitor& nomutex b) {
     272        foo(a,b);
     275void baz(monitor& nomutex a,
     276         monitor& mutex b) {
     277        wait(a.e);
     280bar(a, b);
     285This can be interpreted in two different ways.
     287        \item \texttt{wait} atomically releases the monitors \underline{theoretically} acquired by the inner-most mutex routine.
     288        \item \texttt{wait} atomically releases the monitors \underline{actually} acquired by the inner-most mutex routine.
     290While the difference between these two is subtle, it has a significant impact. In the first case it means that the calls to \texttt{foo} would behave the same in Context 1 and 2. This semantic would also mean that the call to \texttt{wait} in routine \texttt{baz} would only release \texttt{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.
     293\begin{tabular}{c c c}
     297// do stuff
     300\end{lstlisting}& != &\begin{lstlisting}
     302enterMonitor(a, b);
     303// do stuff
     304leaveMonitor(a, b);
     310This is not intuitive because even if both methods will 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 \texttt{wait} will be different. The alternative is option 2, that is releasing \underline{actually} acquired monitors. This solves the issue of having the two acquiring method differ at the cost of making routine \texttt{foo} behave differently depending on from which context it is called (Context 1 or 2). Indeed in Context 2, routine \texttt{foo} will actually behave like routine \texttt{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.
     313The following examples shows three alternatives of explicit wait semantics :
     317Case 1 & Case 2 & Case 3 \\
     318Branding on construction & Explicit release list & Explicit ignore list \\
     321void foo(monitor& mutex a,
     322         monitor& mutex b,
     323           condition& c)
     325        // Releases monitors
     326        // branded on construction
     327        wait(c);
     330monitor a;
     331monitor b;
     332condition1 c1 = {a};
     333condition2 c2 = {a, b};
     335//Will release only a
     338//Will release a and b
     341void foo(monitor& mutex a,
     342         monitor& mutex b,
     343           condition& c)
     345        // Releases monitor a
     346        // Holds monitor b
     347        waitRelease(c, [a]);
     350monitor a;
     351monitor b;
     352condition c;
     361void foo(monitor& mutex a,
     362         monitor& mutex b,
     363           condition& c)
     365        // Releases monitor a
     366        // Holds monitor b
     367        waitHold(c, [b]);
     370monitor a;
     371monitor b;
     372condition c;
     383(Note : Case 2 and 3 use tuple semantics to pass a variable length list of elements.)
     386All these cases have there pros and cons. Case 1 is more distinct because it means programmers need to be carefull about where the condition was initialized as well as where it is used. On the other hand, it is very clear and explicit which monitor will be released and which monitor will stay acquired. This is similar to Case 2, which releases only the monitors explictly listed. However, in Case 2, calling the \texttt{wait} routine instead of the \texttt{waitRelease} routine will release 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 \texttt{wait} routine can be written as follows :
     388void wait(condition& cond) {
     389        waitHold(cond, []);
     392This alternative offers nice and consistent behavior between \texttt{wait} and \texttt{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 :
     394extern void doStuff();
    244396void foo(monitor& mutex m) {
    245397        //...
    246         wait(m.e);
     398        doStuff(); //warning can release monitor m
    247399        //...
    250 foo(a);
    251 \end{lstlisting}&\begin{lstlisting}
    252 void bar(monitor& mutex a, monitor& mutex b) {
    253         signal(a.e);
    254 }
    258 bar(a, b);
    259 \end{lstlisting}
    260 \end{tabular}
    261 \\
    263 Here, the issue is that even if thread 2 does hold the proper lock, it also holds an extra lock that must be delt with. The proposed solution is to make 2 changes to the condition variable declaration. First, the condition variable should be constructed with a reference to the monitor it syncrhonizes :
    265 \begin{lstlisting}
    266         mutex struct A {
    267                 condition e;
    268         }
    270         void ?{}(A& this) {
    271                 &e{this};
    272         }
    274         void foo(A& mutex a) {
    275                 //...
    276                 wait(a.e);
    277                 //...
    278         }
    280         void bar(A& mutex a) {
    281                 signal(a.e);
    282         }
    283 \end{lstlisting}
    285 By explicitly tying a condition variable to a particular monitor it is possible for the run-time to know which monitor needs to be signaled. This also enables run-time check to make sure that the proper context is acquired before trying to \texttt{signal} a condition variable. In this case, run time checks are probably sufficient since \texttt{signal} should be used inside a critical section and even though multi-threading applications are often non-deterministic, the inside of critical sections should be relatively reliable. This implementation of the condition variable object also means that the context of the dual monitor routine, the routine will hold-on to the monitor that is not referenced by the condition variable, i.e. :
    287 \begin{tabular}{ c c }
    288 Thread 1 & Thread 2 \\
    289 \begin{lstlisting}
    290 void foo(monitor& mutex a,
    291          monitor& mutex b) {
    292         //...
    293         wait(a.e); //releases a, holds b
    294         //...
    295 }
    297 foo(a, b);
    298 \end{lstlisting}&\begin{lstlisting}
    299 void bar(monitor& mutex a) {
    300         signal(a.e);
    301 }
    306 bar(a);
    307 \end{lstlisting}
    308 \end{tabular}
    309 \\
    311 The second aspect to this solution is the support for multi-monitor condition variables :
    312 \begin{lstlisting}
    313 monitor m1;
    314 monitor m2;
    315 condition2 e = {m1, m2};
    316 \end{lstlisting}
    317 \begin{tabular}{ c c }
    318 Thread 1 & Thread 2 \\
    319 \begin{lstlisting}
    320 void foo(monitor& mutex a, monitor& mutex b) {
    321         //...
    322         wait(e); //releases a & b
    323         //...
    324 }
    326 foo(a, b);
    327 \end{lstlisting}&\begin{lstlisting}
    328 void bar(monitor& mutex a, monitor& mutex b) {
    329         signal(e);
    330 }
    334 bar(a, b);
    335 \end{lstlisting}
    336 \end{tabular}
    337 \\
    339 Notice here that the type used for the condition variable (\texttt{condition2}) explicitly states the number of monitors that will be synchronized at compile time. The risk with this condition variable semantics is that the user must be in a context where all monitors were properly acquired before waiting/signalling. This can be enforced by run-time checks but would be very difficult to statically enforce. An option that can be used to alleviate this risk is to have the signal routine acquire the monitors that were used to brand the condition variable. This guarantees that the proper locks will be transferred to the signaled but does inherit the risks the come with acquiring multiple locks some of the locks were already acquired.
    340 This would lead to an API similar to this :
    341 \begin{lstlisting}
    342         //default ctor which brands the condition variable on construction
    343         void ?{}(condition* this, monitor& brand);
    344         void ^?{}(condition* this);
    346         //copying an condition variable is forbidden
    347         void ?{}(condition* this, const condition& other) = delete;
    348         void ?=?(condition* this, const condition& other) = delete;
    350         //releases branded locks and waits for signal
    351         void wait(condition* this);
    353         //acquires branded locks and transfers them to the signalled task
    354         //(upon exit for signal and dirrectly for signalBlock)
    355         void signal(condition* this);
    356         void signalBlock(condition* this);
    357 \end{lstlisting}
     402Indeed, if Case 2 or 3 are chosen it any code can violate the mutual exclusion of calling code by issuing calls to \texttt{wait} or \texttt{waitHold} in a nested monitor context. Case 2 can be salvaged by removing the \texttt{wait} routine from the API but Case 3 cannot prevent users from calling \texttt{waitHold(someCondition, [])}. For this reason the syntax proposed in Case 3 is rejected. Note that syntaxes proposed in case 1 and 2 are not exclusive. Indeed, by supporting two types of condition as follows both cases can be supported :
     404struct condition { /*...*/ };
     406void wait(condition& cond, [...] monitorsToRelease); // Second argument is a variable length tuple.
     407void signal(condition& cond);
     409struct conditionN { /*...*/ };
     411void ?{}(conditionN* this, /*list of N monitors to release*/);
     412void wait(conditionN& cond);
     413void signal(conditionN& cond);
     416Regardless 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 \texttt{signal} needs to be called from the same monitor(s) than the call to \texttt{wait}. Otherwise, mutual exclusion cannot be properly transferred back to the waiting monitor.
    359418\subsection{External scheduling}
Note: See TracChangeset for help on using the changeset viewer.