Changeset 7b69174 for doc/proposals


Ignore:
Timestamp:
Sep 29, 2016, 10:48:02 AM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
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, resolv-new, with_gc
Children:
aee7e35
Parents:
694ee7d
Message:

New proposal version for Internal Scheduling semantics written

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/proposals/concurrency/concurrency.tex

    r694ee7d r7b69174  
    2323\usepackage{xspace}
    2424\usepackage{graphicx}
     25\usepackage{tabularx}
    2526\usepackage{varioref}                                                                   % extended references
    2627\usepackage{listings}                                                                   % format program code
     
    195196
    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 :
    198199
    199200\begin{lstlisting}
     
    213214\end{lstlisting}
    214215
    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.
    216217
    217218\begin{tabular}{ c c }
    218219Thread 1 & Thread 2 \\
    219220\begin{lstlisting}
    220         void foo(monitor& mutex m) {
    221                 //...
    222                 wait(m.e);
    223                 //...
    224         }
    225 
    226         foo(a);
    227 \end{lstlisting}&\begin{lstlisting}
    228         void bar(monitor& mutex b, condition& e) {
    229                 signal(e);
    230         }
    231 
    232 
    233 
    234         bar(b, a.e);
     221void foo(monitor& mutex a, monitor& mutex b) {
     222        //...
     223        wait(a.e);
     224        //...
     225}
     226
     227foo(a, b);
     228\end{lstlisting}&\begin{lstlisting}
     229void bar(monitor& mutex a, monitor& mutex b) {
     230        signal(a.e);
     231}
     232
     233
     234
     235bar(a, b);
    235236\end{lstlisting}
    236237\end{tabular}
    237238\\
    238239
    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.
    240 
    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 :
     241
     242\begin{tabular}{|c|c|c|}
     243Context 1 & Context 2 & Context 3 \\
     244\hline
     245\begin{lstlisting}
     246void foo(monitor& mutex a,
     247         monitor& mutex b) {
     248        wait(a.e);
     249}
     250
     251
     252
     253
     254
     255
     256foo(a,b);
     257\end{lstlisting}&\begin{lstlisting}
     258void bar(monitor& mutex a,
     259         monitor& nomutex b) {
     260        foo(a,b);
     261}
     262
     263void foo(monitor& mutex a,
     264         monitor& mutex b) {
     265        wait(a.e);
     266}
     267
     268bar(a, b);
     269\end{lstlisting}&\begin{lstlisting}
     270void bar(monitor& mutex a,
     271         monitor& nomutex b) {
     272        foo(a,b);
     273}
     274
     275void baz(monitor& nomutex a,
     276         monitor& mutex b) {
     277        wait(a.e);
     278}
     279
     280bar(a, b);
     281\end{lstlisting}
     282\end{tabular}
     283\\
     284
     285This can be interpreted in two different ways.
     286\begin{enumerate}
     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.
     289\end{enumerate}
     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.
     291
     292\begin{center}
     293\begin{tabular}{c c c}
     294\begin{lstlisting}
     295enterMonitor(a);
     296enterMonitor(b);
     297// do stuff
     298leaveMonitor(b);
     299leaveMonitor(a);
     300\end{lstlisting}& != &\begin{lstlisting}
     301enterMonitor(a);
     302enterMonitor(a, b);
     303// do stuff
     304leaveMonitor(a, b);
     305leaveMonitor(a);
     306\end{lstlisting}
     307\end{tabular}
     308\end{center}
     309
     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.
     311\\
     312
     313The following examples shows three alternatives of explicit wait semantics :
     314\\
     315
     316\begin{tabular}{|c|c|c|}
     317Case 1 & Case 2 & Case 3 \\
     318Branding on construction & Explicit release list & Explicit ignore list \\
     319\hline
     320\begin{lstlisting}
     321void foo(monitor& mutex a,
     322         monitor& mutex b,
     323           condition& c)
     324{
     325        // Releases monitors
     326        // branded on construction
     327        wait(c);
     328}
     329
     330monitor a;
     331monitor b;
     332condition1 c1 = {a};
     333condition2 c2 = {a, b};
     334
     335//Will release only a
     336foo(a,b,c1);
     337
     338//Will release a and b
     339foo(a,b,c2);
     340\end{lstlisting}&\begin{lstlisting}
     341void foo(monitor& mutex a,
     342         monitor& mutex b,
     343           condition& c)
     344{
     345        // Releases monitor a
     346        // Holds monitor b
     347        waitRelease(c, [a]);
     348}
     349
     350monitor a;
     351monitor b;
     352condition c;
     353
     354
     355
     356foo(a,b,c);
     357
     358
     359
     360\end{lstlisting}&\begin{lstlisting}
     361void foo(monitor& mutex a,
     362         monitor& mutex b,
     363           condition& c)
     364{
     365        // Releases monitor a
     366        // Holds monitor b
     367        waitHold(c, [b]);
     368}
     369
     370monitor a;
     371monitor b;
     372condition c;
     373
     374
     375
     376foo(a,b,c);
     377
     378
     379
     380\end{lstlisting}
     381\end{tabular}
     382
     383(Note : Case 2 and 3 use tuple semantics to pass a variable length list of elements.)
     384\\
     385
     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 :
     387\begin{lstlisting}
     388void wait(condition& cond) {
     389        waitHold(cond, []);
     390}
     391\end{lstlisting}
     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 :
     393\begin{lstlisting}
     394extern void doStuff();
     395
    244396void foo(monitor& mutex m) {
    245397        //...
    246         wait(m.e);
     398        doStuff(); //warning can release monitor m
    247399        //...
    248400}
    249 
    250 foo(a);
    251 \end{lstlisting}&\begin{lstlisting}
    252 void bar(monitor& mutex a, monitor& mutex b) {
    253         signal(a.e);
    254 }
    255 
    256 
    257 
    258 bar(a, b);
    259 \end{lstlisting}
    260 \end{tabular}
    261 \\
    262 
    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 :
    264 
    265 \begin{lstlisting}
    266         mutex struct A {
    267                 condition e;
    268         }
    269 
    270         void ?{}(A& this) {
    271                 &e{this};
    272         }
    273 
    274         void foo(A& mutex a) {
    275                 //...
    276                 wait(a.e);
    277                 //...
    278         }
    279 
    280         void bar(A& mutex a) {
    281                 signal(a.e);
    282         }
    283 \end{lstlisting}
    284 
    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. :
    286 
    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 }
    296 
    297 foo(a, b);
    298 \end{lstlisting}&\begin{lstlisting}
    299 void bar(monitor& mutex a) {
    300         signal(a.e);
    301 }
    302 
    303 
    304 
    305 
    306 bar(a);
    307 \end{lstlisting}
    308 \end{tabular}
    309 \\
    310 
    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 }
    325 
    326 foo(a, b);
    327 \end{lstlisting}&\begin{lstlisting}
    328 void bar(monitor& mutex a, monitor& mutex b) {
    329         signal(e);
    330 }
    331 
    332 
    333 
    334 bar(a, b);
    335 \end{lstlisting}
    336 \end{tabular}
    337 \\
    338 
    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);
    345 
    346         //copying an condition variable is forbidden
    347         void ?{}(condition* this, const condition& other) = delete;
    348         void ?=?(condition* this, const condition& other) = delete;
    349 
    350         //releases branded locks and waits for signal
    351         void wait(condition* this);
    352 
    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}
     401\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 :
     403\begin{lstlisting}
     404struct condition { /*...*/ };
     405
     406void wait(condition& cond, [...] monitorsToRelease); // Second argument is a variable length tuple.
     407void signal(condition& cond);
     408
     409struct conditionN { /*...*/ };
     410
     411void ?{}(conditionN* this, /*list of N monitors to release*/);
     412void wait(conditionN& cond);
     413void signal(conditionN& cond);
     414\end{lstlisting}
     415
     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.
    358417
    359418\subsection{External scheduling}
Note: See TracChangeset for help on using the changeset viewer.