Changeset c03c1ac


Ignore:
Timestamp:
Jul 20, 2023, 3:47:25 PM (16 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
47b7142
Parents:
0e8f4c6
Message:

more proofreading waituntil chapter

Location:
doc/theses/colby_parsons_MMAth/text
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/colby_parsons_MMAth/text/channels.tex

    r0e8f4c6 rc03c1ac  
    246246\begin{lrbox}{\myboxB}
    247247\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    248 channel( size_t ) chan{ 128 };
     248channel( int ) chan{ 128 };
    249249thread Consumer {};
    250250thread Producer {};
    … …  
    253253        try {
    254254                for ()
    255                         insert( chan, 5 );
     255                        chan << 5;
    256256        } catch( channel_closed * ) {
    257257                // unhandled resume or full
    … …  
    259259}
    260260void main( Consumer & this ) {
     261        int i;
    261262        try {
    262                 for () { int i = remove( chan ); }
     263                for () { i << chan; }
    263264        @} catchResume( channel_closed * ) {@
    264265                // handled resume => consume from chan
    … …  
    273274        close( chan );
    274275}
    275 
    276276
    277277

  • doc/theses/colby_parsons_MMAth/text/waituntil.tex

    r0e8f4c6 rc03c1ac  
    1515
    1616Now the problem is extended.
    17 Some stalls are wheelchair accessible and some stalls have specific gender identification.
     17Some stalls are wheelchair accessible and some stalls have gender identification.
    1818Each person (thread) may be limited to only one kind of stall or may choose among different kinds of stalls that match their criteria.
    1919Immediately, the problem becomes more difficult.
    20 A single queue no longer fully solves the problem.
     20A single queue no longer solves the problem.
    2121What happens when there is a stall available that the person at the front of the queue cannot choose?
    22 The na\"ive solution has each thread spin indefinitely continually checking the every matching kind of stall(s) until a suitable one is free.
     22The na\"ive solution has each thread spin indefinitely continually checking every matching kind of stall(s) until a suitable one is free.
    2323This approach is insufficient since it wastes cycles and results in unfairness among waiting threads as a thread can acquire the first matching stall without regard to the waiting time of other threads.
    2424Waiting for the first appropriate stall (resource) that becomes available without spinning is an example of \gls{synch_multiplex}: the ability to wait synchronously for one or more resources based on some selection criteria.
    … …  
    3838(@G1@(x) $\rightarrow$ P @|@ @G2@(y) $\rightarrow$ Q )
    3939\end{cfa}
    40 waits for either channel @x@ or @y@ to have a value, if and only guards @G1@ and @G2@ are true;
     40waits for either channel @x@ or @y@ to have a value, if and only if guards @G1@ and @G2@ are true;
    4141if only one guard is true, only one channel receives, and if both guards are false, no receive occurs.
    4242% extended CSP with a \gls{synch_multiplex} construct @ALT@, which waits for one resource to be available and then executes a corresponding block of code.
    … …  
    5151but require $2^N-1$ @if@ statements, where $N$ is the number of guards.
    5252The exponential blowup comes from applying rule 2.4 repeatedly, since it works on one guard at a time.
    53 Figure~\ref{f:wu_if} shows an example of applying rule 2.4 for three guards.
     53Figure~\ref{f:wu_if} shows in \CFA an example of applying rule 2.4 for three guards.
    5454Also, notice the additional code duplication for statements @S1@, @S2@, and @S3@.
    5555
    … …  
    102102
    103103When discussing \gls{synch_multiplex} implementations, the resource being multiplexed is important.
    104 While CSP wait on channels, the earliest known implementation of synch\-ronous multiplexing is Unix's @select@~\cite{linux:select}, multiplexing over file descriptors.
     104While CSP waits on channels, the earliest known implementation of synch\-ronous multiplexing is Unix's @select@~\cite{linux:select}, multiplexing over file descriptors.
    105105The @select@ system-call is passed three sets of file descriptors (read, write, exceptional) to wait on and an optional timeout.
    106106@select@ blocks until either some subset of file descriptors are available or the timeout expires.
    … …  
    111111It is possible to achieve exclusive-or semantics with @select@ by arbitrarily operating on only one of the returned descriptors.
    112112@select@ passes the interest set of file descriptors between application and kernel in the form of a worst-case sized bit-mask, where the worst-case is the largest numbered file descriptor.
    113 @poll@ reduces the size of the interest sets changing from a bit mask to a linked data structures, independent of the file-descriptor values.
     113@poll@ reduces the size of the interest sets changing from a bit mask to a linked data structure, independent of the file-descriptor values.
    114114@epoll@ further reduces the data passed per call by keeping the interest set in the kernel, rather than supplying it on every call.
    115115
    … …  
    117117Later, \gls{synch_multiplex} started to appear in applications, via programming languages, to support fast multiplexed concurrent communication among threads.
    118118An early example of \gls{synch_multiplex} is the @select@ statement in Ada~\cite[\S~9.7]{Ichbiah79}.
    119 The @select@ statement in Ada allows a task object, with their own threads, to multiplex over a subset of asynchronous calls its methods.
    120 The Ada @select@ statement has the same exclusive-or semantics and guards as Occam ALT;
     119This @select@ allows a task object, with their own threads, to multiplex over a subset of asynchronous calls to its methods.
     120The Ada @select@ has the same exclusive-or semantics and guards as Occam ALT;
    121121however, it multiplexes over methods rather than channels.
    122122
    … …  
    153153\end{figure}
    154154
    155 Figure~\ref{f:BB_Ada} shows the outline of a bounded buffer implemented with Ada task.
     155Figure~\ref{f:BB_Ada} shows the outline of a bounded buffer implemented with an Ada task.
    156156Note, a task method is associated with the \lstinline[language=ada]{accept} clause of the \lstinline[language=ada]{select} statement, rather than being a separate routine.
    157157The thread executing the loop in the task body blocks at the \lstinline[language=ada]{select} until a call occurs to @insert@ or @remove@.
    158158Then the appropriate \lstinline[language=ada]{accept} method is run with the called arguments.
    159 Hence, the @select@ statement provides rendezvous points for threads, rather than providing channels with message passing.
     159Hence, the \lstinline[language=ada]{select} statement provides rendezvous points for threads, rather than providing channels with message passing.
    160160The \lstinline[language=ada]{select} statement also provides a timeout and @else@ (nonblocking), which changes synchronous multiplexing to asynchronous.
    161161Now the thread polls rather than blocks.
    … …  
    250250While these approaches solve the \gls{synch_multiplex} problem, they introduce other issues.
    251251Consider the case where a thread has a single source of communication and it wants a set of @N@ resources.
    252 It sequentially requests the @N@ resources and waits for each response.
     252It must sequentially request the @N@ resources and wait for each response.
    253253During the receives for the @N@ resources, it can receive other communication, and has to save and postpone these communications, or discard them.
    254254% If the requests for the other resources need to be retracted, the burden falls on the programmer to determine how to synchronize appropriately to ensure that only one resource is delivered.
    … …  
    257257
    258258The new \CFA \gls{synch_multiplex} utility introduced in this work is the @waituntil@ statement.
    259 There is a @waitfor@ statement in \CFA that supports Ada-style \gls{synch_multiplex} over monitor methods, so this @waituntil@ focuses on synchronizing over other resources.
     259There already exists a @waitfor@ statement in \CFA that supports Ada-style \gls{synch_multiplex} over monitor methods~\cite{Delisle21}, so this @waituntil@ focuses on synchronizing over other resources.
    260260All of the \gls{synch_multiplex} features mentioned so far are monomorphic, only waiting on one kind of resource: Unix @select@ supports file descriptors, Go's @select@ supports channel operations, \uC's @select@ supports futures, and Ada's @select@ supports monitor method calls.
    261261The \CFA @waituntil@ is polymorphic and provides \gls{synch_multiplex} over any objects that satisfy the trait in Figure~\ref{f:wu_trait}.
    … …  
    281281\end{figure}
    282282
    283 Currently locks, channels, futures and timeouts are supported by the @waituntil@ statement, and can be expanded through the @is_selectable@ trait as other use-cases arise.
    284 The @waituntil@ statement supports guarded clauses, both @or@ and @and@ semantics, and provides an @else@ for asynchronous multiplexing.
     283Currently locks, channels, futures and timeouts are supported by the @waituntil@ statement, and this set can be expanded through the @is_selectable@ trait as other use-cases arise.
     284The @waituntil@ statement supports guard clauses, both @or@ and @and@ semantics, and timeout and @else@ for asynchronous multiplexing.
    285285Figure~\ref{f:wu_example} shows a \CFA @waituntil@ usage, which is waiting for either @Lock@ to be available \emph{or} for a value to be read from @Channel@ into @i@ \emph{and} for @Future@ to be fulfilled \emph{or} a timeout of one second.
     286Note, the expression inside a @waituntil@ clause is evaluated once at the start of the @waituntil@ algorithm.
    286287
    287288\begin{figure}
    … …  
    304305\section{Waituntil Semantics}
    305306
    306 The @waituntil@ semantics has two parts: the semantics of the statement itself, \ie @and@, @or@, @when@ guards, and @else@ semantics, and the semantics of how the @waituntil@ interacts with types like channels, locks and futures.
     307The @waituntil@ semantics has two parts: the semantics of the statement itself, \ie @and@, @or@, @when@ guards, and @else@ semantics, and the semantics of how the @waituntil@ interacts with types like locks, channels, and futures.
    307308
    308309\subsection{Statement Semantics}
    … …  
    314315\begin{cfa}
    315316future(int) bar, foo;
    316 
    317 waituntil( foo ) { ... }
    318 or waituntil( bar ) { ... }
     317waituntil( foo ) { ... } or waituntil( bar ) { ... }
     318\end{cfa}
     319The reason for this semantics is that prioritizing resources can be useful in certain problems.
     320In the rare case where there is a starvation problem with the ordering, it possible to follow a @waituntil@ with its reverse form:
     321\begin{cfa}
     322waituntil( foo ) { ... } or waituntil( bar ) { ... } // prioritize foo
     323waituntil( bar ) { ... } or waituntil( foo ) { ... } // prioritize bar
    319324\end{cfa}
    320325
    … …  
    323328When an @and@ clause becomes available, the waiting thread unblocks and runs that clause's code-block, and then the thread waits again for the next available clause or the @waituntil@ statement is now true.
    324329This semantics allows work to be done in parallel while synchronizing over a set of resources, and furthermore, gives a good reason to use the @and@ operator.
    325 If the @and@ operator waited for all clauses to be available before running, it would be the same as just acquiring those resources consecutively by a sequence of @waituntil@ statements.
     330If the @and@ operator waited for all clauses to be available before running, it is the same as just acquiring those resources consecutively by a sequence of @waituntil@ statements.
    326331
    327332As for normal C expressions, the @and@ operator binds more tightly than the @or@.
    … …  
    376381More detail on channels and their interaction with @waituntil@ appear in Section~\ref{s:wu_chans}.
    377382
     383The trait is used by having a blocking object return a type that supports the @is_selectable@ trait.
     384This feature leverages \CFA's ability to overload on return type to select the correct overloaded routine for the @waituntil@ context.
     385A selectable type is needed for types that want to support multiple operations such as channels that allow both reading and writing.
     386
    378387\section{\lstinline{waituntil} Implementation}
    379 The @waituntil@ statement is not inherently complex, and the pseudo code is presented in Figure~\ref{f:WU_Impl}.
     388
     389The @waituntil@ statement is not inherently complex, and Figure~\ref{f:WU_Impl} only shows the basic outline of the @waituntil@ algorithm.
    380390The 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}.
    384 The basic steps of the @waituntil@ statement are:
    385 
    386 \begin{figure}
    387 \begin{cfa}
    388 select_nodes s[N];                                                               $\C[3.25in]{// declare N select nodes}$
    389 for ( node in s )                                                                $\C{// register nodes}$
     391The following sections then use examples to fill in details missing in Figure~\ref{f:WU_Impl}.
     392The full pseudocode for the @waituntil@ algorithm is presented in Figure~\ref{f:WU_Full_Impl}.
     393
     394\begin{figure}
     395\begin{cfa}
     396select_nodes s[N];                                                              $\C[3.25in]{// declare N select nodes}$
     397for ( node in s )                                                               $\C{// register nodes}$
    390398        register_select( resource, node );
    391399while ( statement predicate not satisfied ) {   $\C{// check predicate}$
    392         // block
     400        // block until clause(s) satisfied
    393401        for ( resource in waituntil statement ) {       $\C{// run true code blocks}$
    394         if ( statement predicate is satisfied ) break;
    395402                if ( resource is avail ) run code block
    396     }
     403                if ( statement predicate is satisfied ) break;
     404        }
    397405}
    398406for ( node in s )                                                               $\C{// deregister nodes}\CRT$
    … …  
    403411\end{figure}
    404412
     413The basic steps of the algorithm are:
    405414\begin{enumerate}
    406415\item
    … …  
    412421\item
    413422The thread executing the @waituntil@ then loops until the statement's predicate is satisfied.
    414 In each iteration, if the predicate is unsatisfied, the thread blocks.
    415 If clauses becomes satisfied, the thread unblocks, and for each satisfied clause the block fails and the thread proceeds, otherwise the block succeeds (like a semaphore where a block is a @P()@ and a satisfied clause is a @V()@).
    416 After proceeding past the block all clauses are checked for completion and the completed clauses have their code blocks run.
     423In each iteration, if the predicate is unsatisfied, the @waituntil@ thread blocks.
     424When another thread satisfies a resource clause (\eg sends to a  channel), it unblocks the @waituntil@ thread.
     425This thread checks all clauses for completion, and any completed clauses have their code blocks run.
    417426While checking clause completion, if enough clauses have been run such that the statement predicate is satisfied, the loop exits early.
    418 In the case where the block succeeds, the thread will be woken by the thread that marks one of the resources as available.
    419427
    420428\item
    421429Once the thread escapes the loop, the @select_nodes@ are unregistered from the resources.
    422430\end{enumerate}
    423 
    424431These steps give a basic overview of how the statement works.
    425 Digging into parts of the implementation will shed light on the specifics and provide more detail.
     432The following sections shed light on the specific changes and provide more implementation detail.
    426433
    427434\subsection{Locks}\label{s:wu_locks}
    … …  
    437444\end{cfa}
    438445Implicitly, the @waituntil@ is calling the lock acquire for each of these locks to establish a position in the lock's queue of waiting threads.
    439 When the lock schedules this thread, it unblocks and performs the @waituntil@ code to determine if it can proceed.
    440 If it cannot proceed, it blocks again on the @waituntil@ lock, holding the acquired lock.
     446When the lock schedules this thread, it unblocks and runs the code block associated with the lock and then releases the lock.
    441447
    442448In detail, when a thread waits on multiple locks via a @waituntil@, it enqueues a @select_node@ in each of the lock's waiting queues.
    443449When a @select_node@ reaches the front of the lock's queue and gains ownership, the thread blocked on the @waituntil@ is unblocked.
    444 Now, the lock is temporarily held by the @waituntil@ thread until the node is unregistered, versus the thread waiting on the lock.
    445 To prevent the waiting thread from holding many locks at once and potentially introducing a deadlock, the node is unregistered right after the corresponding code block is executed.
    446 This prevents deadlocks since the waiting thread will never hold a lock while waiting on another resource.
    447 As such the only nodes unregistered at the end are the ones that have not run.
     450Now, the lock is held by the @waituntil@ thread until the code block is executed, and then the node is unregistered, during which the lock is released.
     451Immediately releasing the lock prevents the waiting thread from holding multiple locks and potentially introducing a deadlock.
     452As such, the only unregistered nodes associated with locks are the ones that have not run.
    448453
    449454\subsection{Timeouts}
    450455
    451 Timeouts in the @waituntil@ take the form of a duration being passed to a @sleep@ or @timeout@ call.
    452 An example is shown in the following code.
    453 
    454 \begin{cfa}
    455 waituntil( sleep( 1`ms ) ) {}
    456 waituntil( timeout( 1`s ) ) {} or waituntil( timeout( 2`s ) ) {}
    457 waituntil( timeout( 1`ns ) ) {} and waituntil( timeout( 2`s ) ) {}
    458 \end{cfa}
    459 
    460 The timeout implementation highlights a key part of the @waituntil@ semantics, the expression inside a @waituntil()@ is evaluated once at the start of the @waituntil@ algorithm.
    461 As such, calls to these @sleep@ and @timeout@ routines do not block, but instead return a type that supports the @is_selectable@ trait.
    462 This feature leverages \CFA's ability to overload on return type; a call to @sleep@ outside a @waituntil@ will call a different @sleep@ that does not return a type, which will block for the appropriate duration.
    463 This mechanism of returning a selectable type is needed for types that want to support multiple operations such as channels that allow both reading and writing.
     456A timeout for the @waituntil@ statement is a duration passed to \lstinline[deletekeywords={timeout}]{timeout}, \eg:
     457\begin{cquote}
     458\begin{tabular}{@{}l|l@{}}
     459\multicolumn{2}{@{}l@{}}{\lstinline{Duration D1\{ 1`ms \}, D2\{ 2`ms \}, D3\{ 3`ms \};}} \\
     460\begin{cfa}[deletekeywords={timeout}]
     461waituntil( i << C1 ) {}
     462or waituntil( i << C2 ) {}
     463or waituntil( i << C3 ) {}
     464or waituntil( timeout( D1 ) ) {}
     465or waituntil( timeout( D2 ) ) {}
     466or waituntil( timeout( D3 ) ) {}
     467\end{cfa}
     468&
     469\begin{cfa}[deletekeywords={timeout}]
     470waituntil( i << C1 ) {}
     471or waituntil( i << C2 ) {}
     472or waituntil( i << C3 ) {}
     473or waituntil( min( timeout( D1 ), timeout( D2 ),  timeout( D3 ) ) {}
     474
     475
     476\end{cfa}
     477\end{tabular}
     478\end{cquote}
     479These examples are basically equivalence.
     480Here, the multiple timeouts are useful because the durations can change during execution and the separate clauses provide different code blocks if a timeout triggers.
     481Multiple timeouts can also be used with @and@ to provide a minimal delay before proceeding.
     482In following example, either channels @C1@ or @C2@ must be satisfied but nothing can be done for at least 1 or 3 seconds after the channel read.
     483\begin{cfa}[deletekeywords={timeout}]
     484waituntil( i << C1 ); and waituntil( timeout( 1`s ) );
     485or waituntil( i << C2 ); and waituntil( timeout( 3`s ) );
     486\end{cfa}
     487If only @C2@ is satisfied, \emph{both} timeout code-blocks trigger.
     488Note, the \CFA @waitfor@ statement only provides a single @timeout@ clause because it only supports @or@ semantics.
     489
     490The \lstinline[deletekeywords={timeout}]{timeout} routine is different from UNIX @sleep@, which blocks for the specified duration and returns the amount of time elapsed since the call started.
     491Instead, \lstinline[deletekeywords={timeout}]{timeout} returns a type that supports the @is_selectable@ trait, allowing the type system to select the correct overloaded routine for this context.
     492For the @waituntil@, it is more idiomatic for the \lstinline[deletekeywords={timeout}]{timeout} to use the same syntax as other blocking operations instead of having a special language clause.
    464493
    465494\subsection{Channels}\label{s:wu_chans}
    466 To support both waiting on both reading and writing to channels, the operators @?<<?@ and @?>>?@ are used read and write to a channel respectively, where the left-hand operand is the value being read into/written and the right-hand operand is the channel.
    467 Channels require significant complexity to synchronously multiplex on for a few reasons.
    468 First, reading or writing to a channel is a mutating operation;
    469 If a read or write to a channel occurs, the state of the channel has changed.
    470 In comparison, for standard locks and futures, if a lock is acquired then released or a future is ready but not accessed, the state of the lock and the future is not permanently modified.
    471 In this way, a @waituntil@ over locks or futures that completes with resources available but not consumed is not an issue.
    472 However, if a thread modifies a channel on behalf of a thread blocked on a @waituntil@ statement, it is important that the corresponding @waituntil@ code block is run, otherwise there is a potentially erroneous mismatch between the channel state and associated side effects.
    473 As such, the @unregister_select@ routine has a boolean return that is used by channels to indicate when the operation was completed but the block was not run yet.
    474 When the return is @true@, the corresponding code block is run after the unregister.
    475 Furthermore, if both @and@ and @or@ operators are used, the @or@ operators have to stop behaving like exclusive-or semantics due to the race between channel operations and unregisters.
    476 
    477 It was deemed important that exclusive-or semantics were maintained when only @or@ operators were 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.
    478 This approach is infeasible in the case where @and@ and @or@ operators are used.
    479 To show this consider the following @waituntil@ statement.
    480 
    481 \begin{cfa}
    482 waituntil( i >> A ) {} and waituntil( i >> B ) {}
    483 or waituntil( i >> C ) {} and waituntil( i >> D ) {}
    484 \end{cfa}
    485 
    486 If exclusive-or semantics were followed, this @waituntil@ would only run the code blocks for @A@ and @B@, or the code blocks for @C@ and @D@.
    487 However, to race before operation completion in this case introduces a race whose complexity increases with the size of the @waituntil@ statement.
    488 In the example above, for @i@ to be inserted into @C@, to ensure the exclusive-or it must be ensured that @i@ can also be inserted into @D@.
    489 Furthermore, the race for the @or@ would also need to be won.
    490 However, due to TOCTOU issues, one cannot know that all resources are available without acquiring all the internal locks of channels in the subtree.
    491 This is not a good solution for two reasons.
    492 It is possible that once all the locks are acquired the subtree is not satisfied and the locks must all be released.
    493 This would incur a high cost for signalling threads and heavily increase contention on internal channel locks.
     495
     496Channels require more complexity to allow synchronous multiplexing.
     497For locks, when an outside thread releases a lock and unblocks the waituntil thread (WUT), the lock's MX property is passed to the WUT (no spinning locks).
     498For futures, the outside thread deliveries a value to the future and unblocks any waiting threads, including WUTs.
     499In either case, after the WUT unblocks it is safe to execute its the corresponding code block knowing access to the resource is protected by the lock or the read-only state of the future.
     500Similarly, for channels, when an outside thread inserts a value into a channel, it must unblock the WUT.
     501However, for channels, there is a race issue.
     502If the outside thread inserts into the channel and unblocks the WUT, there is a race such that, another thread can remove the channel data, so after the WUT unblocks and attempts to remove from the buffer, it fails, and the WUT must reblock (busy waiting).
     503This scenario is a \gls{toctou} race that needs to be consolidated.
     504To close the race, the outside thread must detect this case and insert directly into the left-hand side of the channel expression (@i << chan@) rather than into the channel, and then unblock the WUT.
     505Now the unblocked WUT is guaranteed to have a satisfied resource and its code block can safely executed.
     506The insertion circumvents the channel buffer via the wait-morphing in the \CFA channel implementation \see{Section~\ref{s:chan_impl}}, allowing @waituntil@ channel unblocking to not be special-cased.
     507
     508Furthermore, if both @and@ and @or@ operators are used, the @or@ operations stop behaving like exclusive-or due to the race among channel operations, \eg:
     509\begin{cfa}
     510waituntil( i << A ) {} and waituntil( i << B ) {}
     511or waituntil( i << C ) {} and waituntil( i << D ) {}
     512\end{cfa}
     513If exclusive-or semantics are followed, only the code blocks for @A@ and @B@ are run, or the code blocks for @C@ and @D@.
     514However, four outside threads can simultaneously put values into @i@ and attempt to unblock the WUT to run the four code-blocks.
     515This case introduces a race with complexity that increases with the size of the @waituntil@ statement.
     516However, due to TOCTOU issues, it is impossible to know if all resources are available without acquiring all the internal locks of channels in the subtree of the @waituntil@ clauses.
     517This approach is a poor solution for two reasons.
     518It is possible that once all the locks are acquired the subtree is not satisfied and the locks must be released.
     519This work incurs a high cost for signalling threads and heavily increase contention on internal channel locks.
    494520Furthermore, the @waituntil@ statement is polymorphic and can support resources that do not have internal locks, which also makes this approach infeasible.
    495 As such, the exclusive-or semantics are lost when using both @and@ and @or@ operators since they can not be supported without significant complexity and hits to @waituntil@ statement performance.
     521As 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.
     522
     523It 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.
     524\PAB{explain how this is handled.}
     525
     526\PAB{I'm lost here to the end of the section. You have no example of the case you want to discuss so a made something up.}
    496527
    497528Channels introduce another interesting consideration in their implementation.
    498 Supporting both reading and writing to a channel in A @waituntil@ means that one @waituntil@ clause may be the notifier for another @waituntil@ clause.
     529Supporting both reading and writing to a channel in a @waituntil@ means that one @waituntil@ clause may be the notifier by another @waituntil@ clause.
     530\begin{cfa}
     531waituntil( i << A ) { @B << i;@ }
     532or waituntil( i << B ) { @A << i;@ }
     533\end{cfa}
    499534This poses a problem when dealing with the special-cased @or@ where the clauses need to win a race to operate on a channel.
    500535When both a special-case @or@ is inserting to a channel on one thread and another thread is blocked in a special-case @or@ consuming from the same channel there is not one but two races that need to be consolidated by the inserting thread.
    … …  
    503538
    504539Go solves this problem in their select statement by acquiring the internal locks of all channels before registering the select on the channels.
    505 This eliminates the race since no other threads can operate on the blocked channel since its lock will be held.
     540This eliminates the race since no other threads can operate on the blocked channel since its lock is held.
    506541This approach is not used in \CFA since the @waituntil@ is polymorphic.
    507542Not all types in a @waituntil@ have an internal lock, and when using non-channel types acquiring all the locks incurs extra unneeded overhead.
    508 Instead this race is consolidated in \CFA in two phases by having an intermediate pending status value for the race.
    509 This race case is detectable, and if detected, producer will first race to set its own race flag to be pending.
    510 If it succeeds, it then attempts to set the consumer's race flag to its success value.
    511 If the producer successfully sets the consumer race flag, then the operation can proceed, if not the signalling thread will set its own race flag back to the initial value.
     543Instead, this race is consolidated in \CFA in two phases by having an intermediate pending status value for the race.
     544This race case is detectable, and if detected, the outside thread first races to set its own race flag to be pending.
     545If it succeeds, it then attempts to set the WUT's race flag to its success value.
     546If the outside thread successfully sets the WUT's race flag, then the operation can proceed, if not the signalling threads set its own race flag back to the initial value.
    512547If any other threads attempt to set the producer's flag and see a pending value, they will wait until the value changes before proceeding to ensure that in the case that the producer fails, the signal will not be lost.
    513548This protocol ensures that signals will not be lost and that the two races can be resolved in a safe manner.
    … …  
    577612\begin{cfa}
    578613bool 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}$
     614for ( node in s )                                                                       $\C[3.75in]{// evaluate guards}$
     615        if ( node has guard )
     616                when_conditions[node] = node_guard;
     617        else
     618                when_conditions[node] = true;
     619
     620select_nodes s[N];                                                                      $\C{// declare N select nodes}$
    586621try {
    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$
     622        for ( node in s )                                                               $\C{// register nodes}$
     623                if ( when_conditions[node] )
     624                        register_select( resource, node );
     625
     626        // ... set statuses for nodes with when_conditions[node] == false ...
     627
     628        while ( statement predicate not satisfied ) {   $\C{// check predicate}$
     629                // block
     630                for ( resource in waituntil statement ) {       $\C{// run true code blocks}$
     631                        if ( statement predicate is satisfied ) break;
     632                        if ( resource is avail )
     633                                try {
     634                                        if( on_selected( resource ) )   $\C{// conditionally run block}$
     635                                                run code block
     636                                } finally                                                       $\C{// for exception safety}$
     637                                        unregister_select( resource, node ); $\C{// immediate unregister}$
     638                }
     639        }
     640} finally {                                                                                     $\C{// for exception safety}$
     641        for ( registered nodes in s )                                   $\C{// deregister nodes}$
     642                if ( when_conditions[node] && unregister_select( resource, node )
     643                                && on_selected( resource ) )
     644                        run code block                                                  $\C{// run code block upon unregister}\CRT$
    611645}
    612646\end{cfa}
    … …  
    618652Some things to note are as follows:
    619653The @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.
     654The @when_conditions@ array is used to store the boolean result of evaluating each guard at the beginning of the @waituntil@, and it is used to conditionally omit operations on resources with @false@ guards.
    621655As 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.
    622656
    623657\section{Waituntil Performance}
     658
     659Similar facilities to @waituntil@ are discussed at the start of this chapter in C, Ada, Rust, \CC, and OCaml.
     660However, these facilities are either not meaningful or feasible to benchmark against.
     661The UNIX @select@ and related utilities are not comparable since they are system calls that go into the kernel and operate on file descriptors, whereas the @waituntil@ exists solely in user space.
     662Ada's @select@ only operates on methods, which is done in \CFA via the @waitfor@ utility so it is not meaningful to benchmark against the @waituntil@, which cannot wait on the same resource.
     663Rust and \CC only offer a busy-wait based approach, which is not comparable to a blocking approach.
     664OCaml's @select@ waits on channels that are not comparable with \CFA and Go channels, so OCaml @select@ is not benchmarked against Go's @select@ and \CFA's @waituntil@.
     665
    624666The two \gls{synch_multiplex} utilities that are in the realm of comparability with the \CFA @waituntil@ statement are the Go @select@ statement and the \uC @_Select@ statement.
    625667As such, two microbenchmarks are presented, one for Go and one for \uC to contrast the systems.
    626 The similar utilities discussed at the start of this chapter in C, Ada, Rust, \CC, and OCaml are either not meaningful or feasible to benchmark against.
    627 The select(2) and related utilities in C are not comparable since they are system calls that go into the kernel and operate on file descriptors, whereas the @waituntil@ exists solely in user space.
    628 Ada's @select@ only operates on methods, which is done in \CFA via the @waitfor@ utility so it is not meaningful to benchmark against the @waituntil@, which cannot wait on the same resource.
    629 Rust and \CC only offer a busy-wait based approach which is not comparable to a blocking approach.
    630 OCaml's @select@ waits on channels that are not comparable with \CFA and Go channels, so OCaml @select@ is not benchmarked against Go's @select@ and \CFA's @waituntil@.
    631668Given the differences in features, polymorphism, and expressibility between @waituntil@ and @select@, and @_Select@, the aim of the microbenchmarking in this chapter is to show that these implementations lie in the same realm of performance, not to pick a winner.
    632669
    633670\subsection{Channel Benchmark}
    634 The channel multiplexing microbenchmarks compare \CFA's @waituntil@ and Go's select, where the resource being waited on is a set of channels.
    635 The basic structure of the microbenchmark has the number of cores split evenly between producer and consumer threads, \ie, with 8 cores there would be 4 producer threads and 4 consumer threads.
    636 The number of clauses @C@ is also varied, with results shown with 2, 4, and 8 clauses.
    637 Each clause has a respective channel that is operates on.
    638 Each producer and consumer repeatedly waits to either produce or consume from one of the @C@ clauses and respective channels.
    639 An example in \CFA syntax of the work loop in the consumer main with @C = 4@ clauses follows.
    640 
    641 \begin{cfa}
    642         for (;;)
    643                 waituntil( val << chans[0] ) {} or waituntil( val << chans[1] ) {}
    644                 or waituntil( val << chans[2] ) {} or waituntil( val << chans[3] ) {}
     671
     672The channel multiplexing microbenchmarks compare \CFA's @waituntil@ and Go's \lstinline[language=Go]{select}, where the resource being waited on is a set of channels.
     673The basic structure of the microbenchmark has the number of cores split evenly between producer and consumer threads, \ie, with 8 cores there are 4 producer and 4 consumer threads.
     674The number of resource clauses $C$ is also varied across 2, 4, and 8 clauses, where each clause has different channel that is waits on.
     675Each producer and consumer repeatedly waits to either produce or consume from one of the $C$ clauses and respective channels.
     676For example, in \CFA syntax, the work loop in the consumer main with $C = 4$ clauses is:
     677\begin{cfa}
     678for ()
     679        waituntil( val << chans[0] ); or waituntil( val << chans[1] );
     680        or waituntil( val << chans[2] ); or waituntil( val << chans[3] );
    645681\end{cfa}
    646682A successful consumption is counted as a channel operation, and the throughput of these operations is measured over 10 seconds.
Note: See TracChangeset for help on using the changeset viewer.