Changeset 03bb816
- Timestamp:
- Apr 6, 2017, 3:39:34 PM (8 years ago)
- 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:
- 3db60cb
- Parents:
- 7444113
- Location:
- doc/proposals/concurrency
- Files:
-
- 2 added
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/proposals/concurrency/concurrency.tex
r7444113 r03bb816 61 61 \newcommand{\uC}{$\mu$\CC} 62 62 \newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace} 63 \newcommand{\code}[1]{\lstinline {#1}}63 \newcommand{\code}[1]{\lstinline[language=CFA]{#1}} 64 64 \newcommand{\pseudo}[1]{\lstinline[language=Pseudo]{#1}} 65 65 … … 160 160 Here, 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. 161 161 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.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 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. 163 163 164 164 The next semantic decision is to establish when mutex/nomutex may be used as a type qualifier. Consider the following declarations: … … 368 368 \end{lstlisting} 369 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. 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. 371 372 As for simple mutual exclusion, these semantics must also be extended to include \gls{group-acquire} : 371 373 \begin{center} 372 374 \begin{tabular}{ c @{\hskip 0.65in} c } 373 375 Thread 1 & Thread 2 \\ 374 376 \begin{lstlisting} 375 void foo( monitor& mutex a,376 monitor& mutex b) {377 void foo(A & mutex a, 378 A & mutex b) { 377 379 //... 378 380 wait(a.e); … … 382 384 foo(a, b); 383 385 \end{lstlisting} &\begin{lstlisting} 384 void bar( monitor& mutex a,385 monitor& mutex b) {386 void bar(A & mutex a, 387 A & mutex b) { 386 388 signal(a.e); 387 389 } … … 393 395 \end{tabular} 394 396 \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): 396 397 \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); 397 398 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 : 399 400 \begin{table}[h!] 401 \centering 402 \begin{tabular}{c c} 403 \begin{lstlisting}[language=pseudo] 404 monitor A, B, C 405 406 acquire A 407 acquire B & C 408 409 //Do stuff 410 411 release B & C 412 release A 413 \end{lstlisting} &\begin{lstlisting}[language=pseudo] 414 monitor A, B, C 415 416 acquire A 417 acquire B 418 acquire C 419 //Do stuff 420 release C 421 release B 422 release A 449 423 \end{lstlisting} 450 424 \end{tabular} 451 \end{center} 452 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 455 456 \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); 425 \end{table} 426 427 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 : 428 429 \begin{lstlisting}[language=Pseudo] 430 1: monitor A, B, C 431 2: condition c1 432 3: 433 4: acquire A 434 5: acquire A & B & C 435 6: signal c1 436 7: release A & B & C 437 8: release A 438 \end{lstlisting} 439 440 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. 441 442 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. 443 444 Option 1 reacquires the lock after the signal statement, this can be rewritten as follows without the need for non-disjoint sets : 445 \begin{lstlisting}[language=Pseudo] 446 monitor A, B, C 447 condition c1 448 449 acquire A & B & C 450 signal c1 451 release A & B & C 452 acquire A 453 454 release A 455 \end{lstlisting} 456 457 This pseudo code has almost exaclty the same semantics as the code acquiring intersecting sets of monitors. 458 459 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 : 460 461 \begin{lstlisting}[language=Pseudo] 462 monitor A, B, C 463 condition c1 464 465 acquire A 466 acquire B & C 467 signalBlock c1 468 release B & C 469 release A 470 \end{lstlisting} 471 472 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 : 473 \begin{table}[h!] 474 \centering 475 \begin{tabular}{c @{\hskip 0.65in} c} 476 \begin{lstlisting}[language=pseudo] 477 monitor A, B, C 478 condition c1 479 480 acquire A 481 acquire B & C 482 signalBlock c1 with A 483 release B & C 484 release A 485 \end{lstlisting} &\begin{lstlisting}[language=pseudo] 486 monitor A, B, C 487 condition c1 488 489 acquire A 490 acquire A & B & C 491 signal c1 492 release A & B & C 493 release A 512 494 \end{lstlisting} 513 495 \end{tabular} 514 \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 : 518 \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); 551 \end{lstlisting} 552 \end{tabular} 553 \end{center} 554 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 \\ 496 \end{table} 497 498 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. 499 500 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. 501 502 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. 503 504 % 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. 505 506 % \subsubsection{Internal scheduling: Context} \label{insched-context} 507 % 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 : 508 509 % \begin{lstlisting} 510 % //Forward declarations 511 % monitor a, b, c 512 % void foo( monitor & mutex a, 513 % monitor & mutex b); 514 % void bar( monitor & mutex a, 515 % monitor & mutex b); 516 % void baz( monitor & mutex a, 517 % monitor & mutex b, 518 % monitor & mutex c); 519 520 % //Routines defined inline to illustrate context changed compared to the stack 521 522 % //main thread 523 % foo(a, b) { 524 % //thread calls foo 525 % //acquiring context a & b 526 527 % baz(a, b) { 528 % //thread calls baz 529 % //no context change 530 531 % bar(a, b, c) { 532 % //thread calls bar 533 % //acquiring context a & b & c 534 535 % //Do stuff 536 537 % return; 538 % //call to bar returns 539 % } 540 % //context back to a & b 541 542 % return; 543 % //call to baz returns 544 % } 545 % //no context change 546 547 % return; 548 % //call to foo returns 549 % } 550 % //context back to initial state 551 552 % \end{lstlisting} 553 554 % 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. 555 556 % \subsubsection{Internal scheduling: Waiting} \label{insched-wait} 557 558 % \subsubsection{Internal scheduling: Baton Passing} \label{insched-signal} 559 % 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. 560 % \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. 561 562 % \subsubsection{Internal scheduling: Implementation} \label{insched-impl} 563 % 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. 564 565 % 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. 566 567 % \newpage 568 % \begin{lstlisting} 569 % void ctor( monitor ** _monitors, int _count ) { 570 % bool ctx_changed = false; 571 % for( mon in _monitors ) { 572 % ctx_changed = acquire( mon ) || ctx_changed; 573 % } 574 575 % if( ctx_changed ) { 576 % set_representative(); 577 % set_context(); 578 % } 579 % } 580 581 % void dtor( monitor ** _monitors, int _count ) { 582 % if( context_will_exit( _monitors, count ) ) { 583 % baton_pass(); 584 % return; 585 % } 586 587 % for( mon in _monitors ) { 588 % release( mon ); 589 % } 590 % } 591 592 % \end{lstlisting} 593 594 595 596 % 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): 597 598 % \begin{table}[h!] 599 % \centering 600 % \begin{tabular}{|c|c|c|} 601 % Context 1 & Context 2 & Context 3 \\ 602 % \hline 603 % \begin{lstlisting} 604 % condition e; 605 606 % //acquire a & b 607 % void foo(monitor & mutex a, 608 % monitor & mutex b) { 609 610 % wait(e); //release a & b 611 % } 612 613 614 615 616 617 618 % foo(a,b); 619 % \end{lstlisting} &\begin{lstlisting} 620 % condition e; 621 622 % //acquire a 623 % void bar(monitor & mutex a, 624 % monitor & nomutex b) { 625 % foo(a,b); 626 % } 627 628 % //acquire a & b 629 % void foo(monitor & mutex a, 630 % monitor & mutex b) { 631 % wait(e); //release a & b 632 % } 633 634 % bar(a, b); 635 % \end{lstlisting} &\begin{lstlisting} 636 % condition e; 637 638 % //acquire a 639 % void bar(monitor & mutex a, 640 % monitor & nomutex b) { 641 % baz(a,b); 642 % } 643 644 % //acquire b 645 % void baz(monitor & nomutex a, 646 % monitor & mutex b) { 647 % wait(e); //release b 648 % } 649 650 % bar(a, b); 651 % \end{lstlisting} 652 % \end{tabular} 653 % \end{table} 654 655 % 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. 656 657 658 % \begin{center} 659 % \begin{tabular}{|c|c|c|} 660 % \begin{lstlisting} 661 % condition e; 662 663 % //acquire b 664 % void foo(monitor & nomutex a, 665 % monitor & mutex b) { 666 % bar(a,b); 667 % } 668 669 % //acquire a 670 % void bar(monitor & mutex a, 671 % monitor & nomutex b) { 672 673 % wait(e); //release a 674 % //keep b 675 % } 676 677 % foo(a, b); 678 % \end{lstlisting} &\begin{lstlisting} 679 % condition e; 680 681 % //acquire a & b 682 % void foo(monitor & mutex a, 683 % monitor & mutex b) { 684 % bar(a,b); 685 % } 686 687 % //acquire b 688 % void bar(monitor & mutex a, 689 % monitor & nomutex b) { 690 691 % wait(e); //release b 692 % //keep a 693 % } 694 695 % foo(a, b); 696 % \end{lstlisting} &\begin{lstlisting} 697 % condition e; 698 699 % //acquire a & b 700 % void foo(monitor & mutex a, 701 % monitor & mutex b) { 702 % bar(a,b); 703 % } 704 705 % //acquire none 706 % void bar(monitor & nomutex a, 707 % monitor & nomutex b) { 708 709 % wait(e); //release a & b 710 % //keep none 711 % } 712 713 % foo(a, b); 714 % \end{lstlisting} 715 % \end{tabular} 716 % \end{center} 717 % 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. 718 719 % 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 : 720 % \begin{center} 721 % \begin{tabular}{ c c c } 722 % \begin{lstlisting} 723 % condition e; 724 725 % //acquire a & b 726 % void foo(monitor & mutex a, 727 % monitor & mutex b) { 728 % bar(a,b); 729 % } 730 731 % //acquire b 732 % void bar(monitor & mutex a, 733 % monitor & nomutex b) { 734 735 % wait(e); //release b 736 % //keep a 737 % } 738 739 % foo(a, b); 740 % \end{lstlisting} &\begin{lstlisting} 741 % => 742 % \end{lstlisting} &\begin{lstlisting} 743 % condition e; 744 745 % //acquire a & b 746 % void foo(monitor & mutex a, 747 % monitor & mutex b) { 748 % wait_release(e,b); //release b 749 % //keep a 750 % } 751 752 % foo(a, b); 753 % \end{lstlisting} 754 % \end{tabular} 755 % \end{center} 756 757 % 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. 758 759 % 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. 760 % \\ 559 761 560 762 % ####### # # ####### ##### ##### # # ####### ###### -
doc/proposals/concurrency/glossary.tex
r7444113 r03bb816 14 14 15 15 \longnewglossaryentry{group-acquire} 16 {name={bulk edacquiring}}16 {name={bulk acquiring}} 17 17 { 18 18 Implicitly acquiring several monitors when entering a monitor. 19 } 20 21 \longnewglossaryentry{mon-ctx} 22 {name={monitor context}} 23 { 24 The state of the current thread regarding which monitors are owned. 19 25 } 20 26 -
doc/proposals/concurrency/style.tex
r7444113 r03bb816 1 1 \input{common} % bespoke macros used in the document 2 3 \CFADefaultStyle 2 4 3 5 \lstset{ -
doc/proposals/concurrency/version
r7444113 r03bb816 1 0.7. 611 0.7.134
Note: See TracChangeset
for help on using the changeset viewer.