Context Navigation

-                      r14c0f7b
+                      rf496046
 More detail on channels and their interaction with @waituntil@ appear in Section~\ref{s:wu_chans}.
+The trait is used by having a blocking object return a type that supports the @is_selectable@ trait.
+The trait can be used directly by having a blocking object support the @is_selectable@ trait, or it can be used indirectly through routines that take the object as an argument.
+When used indirectly, the object's routine returns a type that supports the @is_selectable@ trait.
 This feature leverages \CFA's ability to overload on return type to select the correct overloaded routine for the @waituntil@ context.
 A selectable type is needed for types that want to support multiple operations such as channels that allow both reading and writing.
+Indirect support through routines is needed for types that want to support multiple operations such as channels that allow both reading and writing.
 \section{\lstinline{waituntil} Implementation}
 …
 This work incurs a high cost for signalling threads and heavily increase contention on internal channel locks.
 Furthermore, the @waituntil@ statement is polymorphic and can support resources that do not have internal locks, which also makes this approach infeasible.
 As such, the exclusive-or semantics is lost when using both @and@ and @or@ operators since it cannot be supported without significant complexity and significantly affects @waituntil@ performance.
+As such, the exclusive-or semantics are lost when using both @and@ and @or@ operators since it cannot be supported without significant complexity and significantly affects @waituntil@ performance.
 It was deemed important that exclusive-or semantics are maintained when only @or@ operators are used, so this situation has been special-cased, and is handled by having all clauses race to set a value \emph{before} operating on the channel.
 …
 If any other threads attempt to set a WUT's race pointer and see a pending value, they wait until the value changes before proceeding to ensure that, in the case the WUT fails, the signal is not lost.
 This protocol ensures that signals cannot be lost and that the two races can be resolved in a safe manner.
+\PAB{I bet one of the readers is going to ask you to write the pseudo code for this algorithm.}
+The implementation of this protocol is shown in Figure~\ref{f:WU_DeadlockAvoidance}.
+\begin{figure}
+\begin{cfa}
+bool pending_set_other( select_node & other, select_node & mine ) {
+    unsigned long int cmp_status = UNSAT;
+    // Try to set other status, if we succeed break and return true
+    while( !CAS( other.clause_status, &cmp_status, SAT ) ) {
+        if ( cmp_status == SAT )
+            return false; // If other status is SAT we lost so return false
+        // Toggle own status flag to allow other thread to potentially win
+        mine.status = UNSAT;
+        // Reset compare flag
+        cmp_status = UNSAT;
+        // Attempt to set own status flag back to PENDING to retry
+        if ( !CAS( mine.clause_status, &cmp_status, PENDING ) )
+            return false; // If we fail then we lost so return false
+        // Reset compare flag
+        cmp_status = UNSAT;
+    }
+    return true;
+}
+\end{cfa}
+\caption{Exclusive-or \lstinline{waituntil} channel deadlock avoidance protocol}
+\label{f:WU_DeadlockAvoidance}
+\end{figure}
 Channels in \CFA have exception-based shutdown mechanisms that the @waituntil@ statement needs to support.
 …
 It is trivial to check when a synchronous multiplexing utility is done for the or/xor relationship, since any resource becoming available means that the blocked thread can proceed and the @waituntil@ statement is finished.
+In \uC and \CFA, the \gls{synch_multiplex} mechanism have both an and/or relationship, which make the problem of checking for completion of the statement difficult.
+\PAB{Show an example of why this is difficult.}
+In \uC and \CFA, the \gls{synch_multiplex} mechanism have both an and/or relationship, which along with guards, make the problem of checking for completion of the statement difficult.
+Consider the @waituntil@ in Figure~\ref{f:WU_ComplexPredicate}.
+When the @waituntil@ thread wakes up, checking if the statement is complete is non-trivial.
+The predicate that will return if the statement in Figure~\ref{f:WU_ComplexPredicate} is satisfied is the following.
+\begin{cfa}
+A && B || C || !GA && B || !GB && A || !GA && !GB && !GC
+\end{cfa}
+Which simplifies to:
+\begin{cfa}
+( A || !GA ) && ( B || !GB ) || C || !GA && !GB && !GC
+\end{cfa}
+Checking a predicate this large with each iteration is expensive so \uC and \CFA both take steps to simplify checking statement completion.
+\begin{figure}
+\begin{cfa}
+when( GA ) waituntil( A ) {}
+and when( GB ) waituntil( B ) {}
+or when( GC ) waituntil( C ) {}
+\end{cfa}
+\caption{\lstinline{waituntil} with a non-trivial predicate}
+\label{f:WU_ComplexPredicate}
+\end{figure}
 In the \uC @_Select@ statement, this problem is solved by constructing a tree of the resources, where the internal nodes are operators and the leaves are booleans storing the state of each resource.
 …
 Once the root of the tree has both subtrees marked as @true@ then the statement is complete.
 As an optimization, when the internal nodes are updated, the subtrees marked as @true@ are pruned and not examined again.
+To support statement guards in \uC, the tree prunes a branch if the corresponding guard is false.
+\PAB{Show an example.}
+To support statement guards in \uC, the tree is modified to remove an internal node if a guard is false to maintain the appropriate predicate representation.
+An diagram of the tree for the statement in Figure~\ref{f:WU_ComplexPredicate} is shown in Figure~\ref{f:uC_select_tree}, alongside the modification of the tree that occurs when @GA@ is @false@.
+\begin{figure}
+\begin{center}
+\input{diagrams/uCpp_select_tree.tikz}
+\end{center}
+\caption{\uC select tree modification}
+\label{f:uC_select_tree}
+\end{figure}
 The \CFA @waituntil@ statement blocks a thread until a set of resources have become available that satisfy the underlying predicate.
 …
 Leveraging the compiler, a predicate routine is generated per @waituntil@ that when passes the statuses of the resources, returns @true@ when the @waituntil@ is done, and false otherwise.
 To support guards on the \CFA @waituntil@ statement, the status of a resource disabled by a guard is set to a boolean value that ensures that the predicate function behaves as if that resource is no longer part of the predicate.
+\PAB{Show an example.}
+The generated code allows the predicate that is checked with each iteration to be simplified to not check guard values.
+For example, the following would be generated for the @waituntil@ shown in Figure~\ref{f:WU_ComplexPredicate}.
+\begin{cfa}
+// statement completion predicate
+bool check_completion( select_node * nodes ) {
+    return nodes[0].status && nodes[1].status || nodes[2].status;
+}
+// skip statement if all guards false
+if ( GA || GB || GC ) {
+    select_node nodes[3];
+    nodes[0].status = !GA && GB; // A's status
+    nodes[1].status = !GB && GA; // B's status
+    nodes[2].status = !GC;       // C's status
+    // ... rest of waituntil codegen ...
+}
+\end{cfa}
 \uC's @_Select@, supports operators both inside and outside of the \lstinline[language=uC++]{_Select} clauses.
 In the following example, the code blocks run once their corresponding predicate inside the round braces is satisfied.
+% C_TODO put this is uC++ code style not cfa-style
 \begin{lstlisting}[language=uC++,{moredelim=**[is][\color{red}]{@}{@}}]
 Future_ISM<int> A, B, C, D;
 …
 however, that opens the potential for livelock.
 Another possibility is to use resource ordering similar to \CFA's @mutex@ statement, but that alone is insufficient, if the resource ordering is not used universally.
-Additionally, using resource ordering could conflict with other semantics of the @waituntil@ statement.
-For example, consider if the locks in the example must be acquired in the order @D@, @B@, @C@, @A@ because of other @waituntil@ statements.
-\PAB{I don't understand: If all the locks are available, it becomes complex to both respect the ordering of the \lstinline{waituntil} when choosing which code block to run and also respect the lock ordering of \lstinline{D}, \lstinline{B}, \lstinline{C}, \lstinline{A} at the same time.}
 One other way this could be implemented is to wait until all resources for a given clause are available before proceeding to acquire them, but this also quickly becomes a poor approach.
 This approach does not work due to \gls{toctou} issues;
 …
 \begin{cfa}
 bool when_conditions[N];
 for ( node in s )                                                                       $\C[3.75in]{// evaluate guards}$
+for ( node in nodes )                                                                   $\C[3.75in]{// evaluate guards}$
         if ( node has guard )
                 when_conditions[node] = node_guard;
 …
                 when_conditions[node] = true;
+select_nodes s[N];                                                                      $\C{// declare N select nodes}$
+if ( any when_conditions[node] == true ) {
+select_nodes nodes[N];                                                                  $\C{// declare N select nodes}$
 try {
+        for ( node in s )                                                               $\C{// register nodes}$
+                if ( when_conditions[node] )
+                        register_select( resource, node );
+        // ... set statuses for nodes with when_conditions[node] == false ...
         while ( statement predicate not satisfied ) {   $\C{// check predicate}$
                 // block
                 for ( resource in waituntil statement ) {       $\C{// run true code blocks}$
                         if ( statement predicate is satisfied ) break;
                         if ( resource is avail )
                                 try {
                                         if( on_selected( resource ) )   $\C{// conditionally run block}$
                                                 run code block
                                 } finally                                                       $\C{// for exception safety}$
                                         unregister_select( resource, node ); $\C{// immediate unregister}$
+                }
+        }
+    // ... set statuses for nodes with when_conditions[node] == false ...
+    for ( node in nodes )                                                               $\C{// register nodes}$
+        if ( when_conditions[node] )
+            register_select( resource, node );
+    while ( !check_completion( nodes ) ) {      $\C{// check predicate}$
+        // block
+        for ( resource in waituntil statement ) {       $\C{// run true code blocks}$
+            if ( check_completion( nodes ) ) break;
+            if ( resource is avail )
+                try {
+                    if( on_selected( resource ) )       $\C{// conditionally run block}$
+                        run code block
+                } finally                                                       $\C{// for exception safety}$
+                    unregister_select( resource, node ); $\C{// immediate unregister}$
+        }
+    }
 } finally {                                                                                     $\C{// for exception safety}$
         for ( registered nodes in s )                                   $\C{// deregister nodes}$
+        for ( registered nodes in nodes )                                       $\C{// deregister nodes}$
                 if ( when_conditions[node] && unregister_select( resource, node )
                                 && on_selected( resource ) )
                         run code block                                                  $\C{// run code block upon unregister}\CRT$
+}
+}
 \end{cfa}

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset f496046 for doc/theses/colby_parsons_MMAth/text/waituntil.tex

Legend:

doc/theses/colby_parsons_MMAth/text/waituntil.tex

Download in other formats: