Changeset c03c1ac for doc/theses/colby_parsons_MMAth
- Timestamp:
- Jul 20, 2023, 3:47:25 PM (13 months ago)
- Branches:
- master
- Children:
- 47b7142
- Parents:
- 0e8f4c6
- Location:
- doc/theses/colby_parsons_MMAth/text
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/colby_parsons_MMAth/text/channels.tex
r0e8f4c6 rc03c1ac 246 246 \begin{lrbox}{\myboxB} 247 247 \begin{cfa}[aboveskip=0pt,belowskip=0pt] 248 channel( size_t ) chan{ 128 };248 channel( int ) chan{ 128 }; 249 249 thread Consumer {}; 250 250 thread Producer {}; … … 253 253 try { 254 254 for () 255 insert( chan, 5 );255 chan << 5; 256 256 } catch( channel_closed * ) { 257 257 // unhandled resume or full … … 259 259 } 260 260 void main( Consumer & this ) { 261 int i; 261 262 try { 262 for () { i nt i = remove( chan ); }263 for () { i << chan; } 263 264 @} catchResume( channel_closed * ) {@ 264 265 // handled resume => consume from chan … … 273 274 close( chan ); 274 275 } 275 276 276 277 277 -
doc/theses/colby_parsons_MMAth/text/waituntil.tex
r0e8f4c6 rc03c1ac 15 15 16 16 Now the problem is extended. 17 Some stalls are wheelchair accessible and some stalls have specificgender identification.17 Some stalls are wheelchair accessible and some stalls have gender identification. 18 18 Each person (thread) may be limited to only one kind of stall or may choose among different kinds of stalls that match their criteria. 19 19 Immediately, the problem becomes more difficult. 20 A single queue no longer fullysolves the problem.20 A single queue no longer solves the problem. 21 21 What 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 theevery matching kind of stall(s) until a suitable one is free.22 The na\"ive solution has each thread spin indefinitely continually checking every matching kind of stall(s) until a suitable one is free. 23 23 This 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. 24 24 Waiting 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. … … 38 38 (@G1@(x) $\rightarrow$ P @|@ @G2@(y) $\rightarrow$ Q ) 39 39 \end{cfa} 40 waits for either channel @x@ or @y@ to have a value, if and only guards @G1@ and @G2@ are true;40 waits for either channel @x@ or @y@ to have a value, if and only if guards @G1@ and @G2@ are true; 41 41 if only one guard is true, only one channel receives, and if both guards are false, no receive occurs. 42 42 % 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. … … 51 51 but require $2^N-1$ @if@ statements, where $N$ is the number of guards. 52 52 The 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.53 Figure~\ref{f:wu_if} shows in \CFA an example of applying rule 2.4 for three guards. 54 54 Also, notice the additional code duplication for statements @S1@, @S2@, and @S3@. 55 55 … … 102 102 103 103 When 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.104 While CSP waits on channels, the earliest known implementation of synch\-ronous multiplexing is Unix's @select@~\cite{linux:select}, multiplexing over file descriptors. 105 105 The @select@ system-call is passed three sets of file descriptors (read, write, exceptional) to wait on and an optional timeout. 106 106 @select@ blocks until either some subset of file descriptors are available or the timeout expires. … … 111 111 It is possible to achieve exclusive-or semantics with @select@ by arbitrarily operating on only one of the returned descriptors. 112 112 @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 structure s, 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. 114 114 @epoll@ further reduces the data passed per call by keeping the interest set in the kernel, rather than supplying it on every call. 115 115 … … 117 117 Later, \gls{synch_multiplex} started to appear in applications, via programming languages, to support fast multiplexed concurrent communication among threads. 118 118 An early example of \gls{synch_multiplex} is the @select@ statement in Ada~\cite[\S~9.7]{Ichbiah79}. 119 Th e @select@ statement in Ada allows a task object, with their own threads, to multiplex over a subset of asynchronous callsits methods.120 The Ada @select@ statementhas the same exclusive-or semantics and guards as Occam ALT;119 This @select@ allows a task object, with their own threads, to multiplex over a subset of asynchronous calls to its methods. 120 The Ada @select@ has the same exclusive-or semantics and guards as Occam ALT; 121 121 however, it multiplexes over methods rather than channels. 122 122 … … 153 153 \end{figure} 154 154 155 Figure~\ref{f:BB_Ada} shows the outline of a bounded buffer implemented with Ada task.155 Figure~\ref{f:BB_Ada} shows the outline of a bounded buffer implemented with an Ada task. 156 156 Note, 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. 157 157 The thread executing the loop in the task body blocks at the \lstinline[language=ada]{select} until a call occurs to @insert@ or @remove@. 158 158 Then 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.159 Hence, the \lstinline[language=ada]{select} statement provides rendezvous points for threads, rather than providing channels with message passing. 160 160 The \lstinline[language=ada]{select} statement also provides a timeout and @else@ (nonblocking), which changes synchronous multiplexing to asynchronous. 161 161 Now the thread polls rather than blocks. … … 250 250 While these approaches solve the \gls{synch_multiplex} problem, they introduce other issues. 251 251 Consider 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 waitsfor each response.252 It must sequentially request the @N@ resources and wait for each response. 253 253 During the receives for the @N@ resources, it can receive other communication, and has to save and postpone these communications, or discard them. 254 254 % 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. … … 257 257 258 258 The 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.259 There 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. 260 260 All 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. 261 261 The \CFA @waituntil@ is polymorphic and provides \gls{synch_multiplex} over any objects that satisfy the trait in Figure~\ref{f:wu_trait}. … … 281 281 \end{figure} 282 282 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 guard ed clauses, both @or@ and @and@ semantics, and provides an@else@ for asynchronous multiplexing.283 Currently 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. 284 The @waituntil@ statement supports guard clauses, both @or@ and @and@ semantics, and timeout and @else@ for asynchronous multiplexing. 285 285 Figure~\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. 286 Note, the expression inside a @waituntil@ clause is evaluated once at the start of the @waituntil@ algorithm. 286 287 287 288 \begin{figure} … … 304 305 \section{Waituntil Semantics} 305 306 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, locksand futures.307 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 locks, channels, and futures. 307 308 308 309 \subsection{Statement Semantics} … … 314 315 \begin{cfa} 315 316 future(int) bar, foo; 316 317 waituntil( foo ) { ... } 318 or waituntil( bar ) { ... } 317 waituntil( foo ) { ... } or waituntil( bar ) { ... } 318 \end{cfa} 319 The reason for this semantics is that prioritizing resources can be useful in certain problems. 320 In 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} 322 waituntil( foo ) { ... } or waituntil( bar ) { ... } // prioritize foo 323 waituntil( bar ) { ... } or waituntil( foo ) { ... } // prioritize bar 319 324 \end{cfa} 320 325 … … 323 328 When 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. 324 329 This 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 bethe same as just acquiring those resources consecutively by a sequence of @waituntil@ statements.330 If 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. 326 331 327 332 As for normal C expressions, the @and@ operator binds more tightly than the @or@. … … 376 381 More detail on channels and their interaction with @waituntil@ appear in Section~\ref{s:wu_chans}. 377 382 383 The trait is used by having a blocking object return a type that supports the @is_selectable@ trait. 384 This feature leverages \CFA's ability to overload on return type to select the correct overloaded routine for the @waituntil@ context. 385 A selectable type is needed for types that want to support multiple operations such as channels that allow both reading and writing. 386 378 387 \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 389 The @waituntil@ statement is not inherently complex, and Figure~\ref{f:WU_Impl} only shows the basic outline of the @waituntil@ algorithm. 380 390 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}. 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}$ 391 The following sections then use examples to fill in details missing in Figure~\ref{f:WU_Impl}. 392 The full pseudocode for the @waituntil@ algorithm is presented in Figure~\ref{f:WU_Full_Impl}. 393 394 \begin{figure} 395 \begin{cfa} 396 select_nodes s[N]; $\C[3.25in]{// declare N select nodes}$ 397 for ( node in s ) $\C{// register nodes}$ 390 398 register_select( resource, node ); 391 399 while ( statement predicate not satisfied ) { $\C{// check predicate}$ 392 // block 400 // block until clause(s) satisfied 393 401 for ( resource in waituntil statement ) { $\C{// run true code blocks}$ 394 if ( statement predicate is satisfied ) break;395 402 if ( resource is avail ) run code block 396 } 403 if ( statement predicate is satisfied ) break; 404 } 397 405 } 398 406 for ( node in s ) $\C{// deregister nodes}\CRT$ … … 403 411 \end{figure} 404 412 413 The basic steps of the algorithm are: 405 414 \begin{enumerate} 406 415 \item … … 412 421 \item 413 422 The 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 thecompleted clauses have their code blocks run.423 In each iteration, if the predicate is unsatisfied, the @waituntil@ thread blocks. 424 When another thread satisfies a resource clause (\eg sends to a channel), it unblocks the @waituntil@ thread. 425 This thread checks all clauses for completion, and any completed clauses have their code blocks run. 417 426 While 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.419 427 420 428 \item 421 429 Once the thread escapes the loop, the @select_nodes@ are unregistered from the resources. 422 430 \end{enumerate} 423 424 431 These 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 moredetail.432 The following sections shed light on the specific changes and provide more implementation detail. 426 433 427 434 \subsection{Locks}\label{s:wu_locks} … … 437 444 \end{cfa} 438 445 Implicitly, 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. 446 When the lock schedules this thread, it unblocks and runs the code block associated with the lock and then releases the lock. 441 447 442 448 In detail, when a thread waits on multiple locks via a @waituntil@, it enqueues a @select_node@ in each of the lock's waiting queues. 443 449 When 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. 450 Now, 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. 451 Immediately releasing the lock prevents the waiting thread from holding multiple locks and potentially introducing a deadlock. 452 As such, the only unregistered nodes associated with locks are the ones that have not run. 448 453 449 454 \subsection{Timeouts} 450 455 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. 456 A 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}] 461 waituntil( i << C1 ) {} 462 or waituntil( i << C2 ) {} 463 or waituntil( i << C3 ) {} 464 or waituntil( timeout( D1 ) ) {} 465 or waituntil( timeout( D2 ) ) {} 466 or waituntil( timeout( D3 ) ) {} 467 \end{cfa} 468 & 469 \begin{cfa}[deletekeywords={timeout}] 470 waituntil( i << C1 ) {} 471 or waituntil( i << C2 ) {} 472 or waituntil( i << C3 ) {} 473 or waituntil( min( timeout( D1 ), timeout( D2 ), timeout( D3 ) ) {} 474 475 476 \end{cfa} 477 \end{tabular} 478 \end{cquote} 479 These examples are basically equivalence. 480 Here, the multiple timeouts are useful because the durations can change during execution and the separate clauses provide different code blocks if a timeout triggers. 481 Multiple timeouts can also be used with @and@ to provide a minimal delay before proceeding. 482 In 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}] 484 waituntil( i << C1 ); and waituntil( timeout( 1`s ) ); 485 or waituntil( i << C2 ); and waituntil( timeout( 3`s ) ); 486 \end{cfa} 487 If only @C2@ is satisfied, \emph{both} timeout code-blocks trigger. 488 Note, the \CFA @waitfor@ statement only provides a single @timeout@ clause because it only supports @or@ semantics. 489 490 The \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. 491 Instead, \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. 492 For 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. 464 493 465 494 \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 496 Channels require more complexity to allow synchronous multiplexing. 497 For 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). 498 For futures, the outside thread deliveries a value to the future and unblocks any waiting threads, including WUTs. 499 In 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. 500 Similarly, for channels, when an outside thread inserts a value into a channel, it must unblock the WUT. 501 However, for channels, there is a race issue. 502 If 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). 503 This scenario is a \gls{toctou} race that needs to be consolidated. 504 To 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. 505 Now the unblocked WUT is guaranteed to have a satisfied resource and its code block can safely executed. 506 The 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 508 Furthermore, 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} 510 waituntil( i << A ) {} and waituntil( i << B ) {} 511 or waituntil( i << C ) {} and waituntil( i << D ) {} 512 \end{cfa} 513 If exclusive-or semantics are followed, only the code blocks for @A@ and @B@ are run, or the code blocks for @C@ and @D@. 514 However, four outside threads can simultaneously put values into @i@ and attempt to unblock the WUT to run the four code-blocks. 515 This case introduces a race with complexity that increases with the size of the @waituntil@ statement. 516 However, 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. 517 This approach is a poor solution for two reasons. 518 It is possible that once all the locks are acquired the subtree is not satisfied and the locks must be released. 519 This work incurs a high cost for signalling threads and heavily increase contention on internal channel locks. 494 520 Furthermore, 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. 521 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. 522 523 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. 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.} 496 527 497 528 Channels 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. 529 Supporting 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} 531 waituntil( i << A ) { @B << i;@ } 532 or waituntil( i << B ) { @A << i;@ } 533 \end{cfa} 499 534 This poses a problem when dealing with the special-cased @or@ where the clauses need to win a race to operate on a channel. 500 535 When 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. … … 503 538 504 539 Go 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 beheld.540 This eliminates the race since no other threads can operate on the blocked channel since its lock is held. 506 541 This approach is not used in \CFA since the @waituntil@ is polymorphic. 507 542 Not 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 raceto 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 willset its own race flag back to the initial value.543 Instead, this race is consolidated in \CFA in two phases by having an intermediate pending status value for the race. 544 This race case is detectable, and if detected, the outside thread first races to set its own race flag to be pending. 545 If it succeeds, it then attempts to set the WUT's race flag to its success value. 546 If 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. 512 547 If 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. 513 548 This protocol ensures that signals will not be lost and that the two races can be resolved in a safe manner. … … 577 612 \begin{cfa} 578 613 bool when_conditions[N]; 579 for ( node in s ) $\C{// evaluate guards}$580 581 582 583 584 585 select_nodes s[N]; $\C[3.25in]{// declare N select nodes}$614 for ( 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 620 select_nodes s[N]; $\C{// declare N select nodes}$ 586 621 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$ 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$ 611 645 } 612 646 \end{cfa} … … 618 652 Some things to note are as follows: 619 653 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 eva ulating each guard at the beginning of the @waituntil@, and it is used to conditionally omit operations on resources with @false@ guards.654 The @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. 621 655 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. 622 656 623 657 \section{Waituntil Performance} 658 659 Similar facilities to @waituntil@ are discussed at the start of this chapter in C, Ada, Rust, \CC, and OCaml. 660 However, these facilities are either not meaningful or feasible to benchmark against. 661 The 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. 662 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. 663 Rust and \CC only offer a busy-wait based approach, which is not comparable to a blocking approach. 664 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@. 665 624 666 The 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. 625 667 As 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@.631 668 Given 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. 632 669 633 670 \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 672 The 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. 673 The 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. 674 The number of resource clauses $C$ is also varied across 2, 4, and 8 clauses, where each clause has different channel that is waits on. 675 Each producer and consumer repeatedly waits to either produce or consume from one of the $C$ clauses and respective channels. 676 For example, in \CFA syntax, the work loop in the consumer main with $C = 4$ clauses is: 677 \begin{cfa} 678 for () 679 waituntil( val << chans[0] ); or waituntil( val << chans[1] ); 680 or waituntil( val << chans[2] ); or waituntil( val << chans[3] ); 645 681 \end{cfa} 646 682 A 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.