Changeset 494a7e5 for doc/theses/colby_parsons_MMAth
- Timestamp:
- Jul 17, 2023, 12:38:48 PM (13 months ago)
- Branches:
- master
- Children:
- a0b59ed
- Parents:
- 7ed01be
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/colby_parsons_MMAth/text/waituntil.tex
r7ed01be r494a7e5 368 368 As mentioned, to support interaction with the @waituntil@ statement a type must support the trait in Figure~\ref{f:wu_trait}. 369 369 The @waituntil@ statement expects types to register and unregister themselves via calls to @register_select@ and @unregister_select@, respectively. 370 When a resource becomes available, @on_selected@ is run .370 When a resource becomes available, @on_selected@ is run, and if it returns false, the corresponding code block is not run. 371 371 Many types do not need @on_selected@, but it is provided if a type needs to perform work or checks before the resource can be accessed in the code block. 372 The register/unregister routines in the trait return booleans.372 The register/unregister routines in the trait also return booleans. 373 373 The return value of @register_select@ is @true@, if the resource is immediately available and @false@ otherwise. 374 374 The return value of @unregister_select@ is @true@, if the corresponding code block should be run after unregistration and @false@ otherwise. … … 379 379 The @waituntil@ statement is not inherently complex, and the pseudo code is presented in Figure~\ref{f:WU_Impl}. 380 380 The complexity comes from the consideration of race conditions and synchronization needed when supporting various primitives. 381 Figure~\ref{f:WU_Impl} aims to introduce the reader to the rudimentary idea and control flow of the @waituntil@. 382 The following sections then use examples to fill in details that Figure~\ref{f:WU_Impl} does not provide. 383 Finally, the full pseudocode of the waituntil is presented in Figure~\ref{f:WU_Full_Impl}. 381 384 The basic steps of the @waituntil@ statement are: 382 385 … … 422 425 Digging into parts of the implementation will shed light on the specifics and provide more detail. 423 426 424 \subsection{Locks} 427 \subsection{Locks}\label{s:wu_locks} 425 428 426 429 The \CFA runtime supports a number of spinning and blocking locks, \eg semaphore, MCS, futex, Go mutex, spinlock, owner, \etc. … … 566 569 Operators inside clauses in \CFA could potentially be implemented with careful circumvention of the problems involved, but it was not deemed an important feature when taking into account the runtime cost that would need to be paid to handle these situations. 567 570 The problem of operators inside clauses also becomes a difficult issue to handle when supporting channels. 568 If internal operators were supported, it would require some way to ensure that channels used with internal operators are modified on if and only if the corresponding code block is run, but that is not feasible due to reasons described in the exclusive-or portion of Section~\ref{s:wu_chans}. 571 If internal operators were supported, it would require some way to ensure that channels used with internal operators are modified on if and only if the corresponding code block is run, but that is not feasible due to reasons described in the exclusive-or portion of Section~\ref{s:wu_chans}. 572 573 \subsection{The full \lstinline{waituntil} picture} 574 Now that the details have been discussed, the full pseudocode of the waituntil is presented in Figure~\ref{f:WU_Full_Impl}. 575 576 \begin{figure} 577 \begin{cfa} 578 bool when_conditions[N]; 579 for ( node in s ) $\C{// evaluate guards}$ 580 if ( node has guard ) 581 when_conditions[node] = node_guard; 582 else 583 when_conditions[node] = true; 584 585 select_nodes s[N]; $\C[3.25in]{// declare N select nodes}$ 586 try { 587 for ( node in s ) $\C{// register nodes}$ 588 if ( when_conditions[node] ) 589 register_select( resource, node ); 590 591 // ... set statuses for nodes with when_conditions[node] == false ... 592 593 while ( statement predicate not satisfied ) { $\C{// check predicate}$ 594 // block 595 for ( resource in waituntil statement ) { $\C{// run true code blocks}$ 596 if ( statement predicate is satisfied ) break; 597 if ( resource is avail ) { 598 try { 599 if( on_selected( resource ) ) $\C{// conditionally run block}$ 600 run code block 601 } finally { $\C{// for exception safety}$ 602 unregister_select( resource, node ); $\C{// immediate unregister}$ 603 } 604 } 605 } 606 } 607 } finally { $\C{// for exception safety}$ 608 for ( registered nodes in s ) $\C{// deregister nodes}$ 609 if ( when_conditions[node] && unregister_select( resource, node ) && on_selected( resource ) ) 610 run code block $\C{// conditionally run code block upon unregister}\CRT$ 611 } 612 \end{cfa} 613 \caption{Full \lstinline{waituntil} Pseudocode Implementation} 614 \label{f:WU_Full_Impl} 615 \end{figure} 616 617 In comparison to Figure~\ref{f:WU_Impl}, this pseudocode now includes the specifics discussed in this chapter. 618 Some things to note are as follows: 619 The @finally@ blocks provide exception-safe RAII unregistering of nodes, and in particular, the @finally@ inside the innermost loop performs the immediate unregistering required for deadlock-freedom that was mentioned in Section~\ref{s:wu_locks}. 620 The @when_conditions@ array is used to store the boolean result of evaulating each guard at the beginning of the @waituntil@, and it is used to conditionally omit operations on resources with @false@ guards. 621 As discussed in Section~\ref{s:wu_chans}, this pseudocode includes code blocks conditional on the result of both @on_selected@ and @unregister_select@, which allows the channel implementation to ensure that all available channel resources will have their corresponding code block run. 569 622 570 623 \section{Waituntil Performance}
Note: See TracChangeset
for help on using the changeset viewer.