Changes in / [65cb413:b715c9a]
- Location:
- doc/proposals/concurrency
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/proposals/concurrency/concurrency.tex
r65cb413 rb715c9a 350 350 351 351 \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. 371 372 As for simple mutual exclusion, these semantics must also be extended to include \gls{group-acquire} : 352 373 353 \begin{center} 374 354 \begin{tabular}{ c @{\hskip 0.65in} c } 375 Thread 1 & Thread 2 \\ 376 \begin{lstlisting} 377 void foo(A & mutex a, 378 A & mutex b) { 379 //... 380 wait(a.e); 381 //... 382 } 383 384 foo(a, b); 385 \end{lstlisting} &\begin{lstlisting} 386 void bar(A & mutex a, 387 A & mutex b) { 388 signal(a.e); 389 } 390 391 392 393 bar(a, b); 355 \begin{lstlisting}[language=Pseudo] 356 acquire A 357 wait A 358 release A 359 \end{lstlisting}&\begin{lstlisting}[language=Pseudo] 360 acquire A 361 signal A 362 release A 394 363 \end{lstlisting} 395 364 \end{tabular} 396 365 \end{center} 397 366 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 367 Easy : like uC++ 368 369 \begin{center} 370 \begin{tabular}{ c @{\hskip 0.65in} c } 371 \begin{lstlisting}[language=Pseudo] 406 372 acquire A 407 acquire B & C 408 409 //Do stuff 410 411 release B & C 373 acquire B 374 wait B 375 release B 412 376 release A 413 \end{lstlisting} &\begin{lstlisting}[language=pseudo] 414 monitor A, B, C 415 377 \end{lstlisting}&\begin{lstlisting}[language=Pseudo] 378 acquire A 379 acquire B 380 signal B 381 release B 382 release A 383 \end{lstlisting} 384 \end{tabular} 385 \end{center} 386 387 Also easy : like uC++ 388 389 \begin{center} 390 \begin{tabular}{ c @{\hskip 0.65in} c } 391 \begin{lstlisting}[language=Pseudo] 392 acquire A & B 393 wait A & B 394 release A & B 395 \end{lstlisting}&\begin{lstlisting}[language=Pseudo] 396 acquire A & B 397 signal A & B 398 release A & B 399 \end{lstlisting} 400 \end{tabular} 401 \end{center} 402 403 Simplest extension : can be made like uC++ by tying B to A 404 405 \begin{center} 406 \begin{tabular}{ c @{\hskip 0.65in} c } 407 \begin{lstlisting}[language=Pseudo] 408 acquire 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 416 release A 417 \end{lstlisting}&\begin{lstlisting}[language=Pseudo] 418 acquire 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 426 release A 427 \end{lstlisting} 428 \end{tabular} 429 \end{center} 430 431 Hard extension : 432 433 Incorrect 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 441 Since 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] 416 446 acquire A 417 447 acquire B 418 448 acquire C 419 //Do stuff 420 release C 421 release B 422 release A 449 wait A & B & C 450 1: release C 451 2: release B 452 3: release A 453 \end{lstlisting}&\begin{lstlisting}[language=Pseudo] 454 acquire A 455 acquire B 456 acquire C 457 signal A & B & C 458 4: release C 459 5: release B 460 6: release A 423 461 \end{lstlisting} 424 462 \end{tabular} 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 463 \end{center} 464 465 To 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 } 429 476 \begin{lstlisting}[language=Pseudo] 430 1: monitor A, B, C431 2: condition c1432 3:433 4: acquire A434 5: acquire A & B & C435 6: signal c1436 7: release A & B & C437 8: release A438 \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, C447 condition c1448 449 acquire A & B & C450 signal c1451 release A & B & C452 477 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 478 acquire C 479 acquire B 480 wait A & B & C 481 1: release B 482 2: release C 483 3: release A 484 \end{lstlisting}&\begin{lstlisting}[language=Pseudo] 485 acquire B 486 acquire A 487 acquire C 488 signal A & B & C 489 4: release C 490 5: release A 491 6: release B 494 492 \end{lstlisting} 495 493 \end{tabular} 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. 494 \end{center} 495 496 To 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. 503 656 504 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. -
doc/proposals/concurrency/style.tex
r65cb413 rb715c9a 1 1 \input{common} % bespoke macros used in the document 2 2 3 \CFADefaultStyle3 % \CFADefaultStyle 4 4 5 5 \lstset{ -
doc/proposals/concurrency/version
r65cb413 rb715c9a 1 0.7.1 341 0.7.141
Note: See TracChangeset
for help on using the changeset viewer.