Changeset 8a930c03 for doc/theses

doc/theses/colby_parsons_MMAth/Makefile

r2b78949	r8a930c03
98	98
99	99	${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${DATA} \
100		style/style.tex ${Macros}/common.tex ${Macros}/indexstyle local.bib ../../bibliography/pl.bib \| ${Build}
	100	glossary.tex style/style.tex ${Macros}/common.tex ${Macros}/indexstyle local.bib ../../bibliography/pl.bib \| ${Build}
101	101	# Must have *.aux file containing citations for bibtex
102	102	if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/balance.cfa

-              r2b78949
+              r8a930c03
 d_actor ** actor_arr;
 Allocation receive( d_actor & this, start_msg & msg ) with( this ) {
+allocation receive( d_actor & this, start_msg & msg ) with( this ) {
     for ( i; Set ) {
         *actor_arr[i + gstart] << shared_msg;
 …
+}
 Allocation receive( d_actor & this, d_msg & msg ) with( this ) {
+allocation receive( d_actor & this, d_msg & msg ) with( this ) {
     if ( recs == rounds ) return Delete;
     if ( recs % Batch == 0 ) {
 …
+}
 Allocation receive( filler & this, d_msg & msg ) { return Delete; }
+allocation receive( filler & this, d_msg & msg ) { return Delete; }
 int main( int argc, char * argv[] ) {

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/dynamic.cfa

r2b78949	r8a930c03
24	24
25	25	uint64_t start_time;
26		Allocation receive( derived_actor & receiver, derived_msg & msg ) {
	26	allocation receive( derived_actor & receiver, derived_msg & msg ) {
27	27	if ( msg.cnt >= Times ) {
28	28	printf("%.2f\n", ((double)(bench_time() - start_time)) / ((double)Times) ); // ns

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/executor.cfa

r2b78949	r8a930c03
25	25	struct d_msg { inline message; } shared_msg;
26	26
27		Allocation receive( d_actor & this, d_msg & msg ) with( this ) {
	27	allocation receive( d_actor & this, d_msg & msg ) with( this ) {
28	28	if ( recs == rounds ) return Finished;
29	29	if ( recs % Batch == 0 ) {

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/matrix.cfa

r2b78949	r8a930c03
24	24	}
25	25
26		Allocation receive( derived_actor & receiver, derived_msg & msg ) {
	26	allocation receive( derived_actor & receiver, derived_msg & msg ) {
27	27	for ( unsigned int i = 0; i < yc; i += 1 ) { // multiply X_row by Y_col and sum products
28	28	msg.Z[i] = 0;

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/repeat.cfa

-              r2b78949
+              r8a930c03
 Client * cl;
 Allocation receive( Server & this, IntMsg & msg ) { msg.val = 7; *cl << msg; return Nodelete; }
 Allocation receive( Server & this, CharMsg & msg ) { msg.val = 'x'; *cl << msg; return Nodelete; }
 Allocation receive( Server & this, StateMsg & msg ) { return Finished; }
+allocation receive( Server & this, IntMsg & msg ) { msg.val = 7; *cl << msg; return Nodelete; }
+allocation receive( Server & this, CharMsg & msg ) { msg.val = 'x'; *cl << msg; return Nodelete; }
+allocation receive( Server & this, StateMsg & msg ) { return Finished; }
 void terminateServers( Client & this ) with(this) {
 …
+}
 Allocation reset( Client & this ) with(this) {
+allocation reset( Client & this ) with(this) {
     times += 1;
     if ( times == Times ) { terminateServers( this ); return Finished; }
 …
+}
 Allocation process( Client & this ) with(this) {
+allocation process( Client & this ) with(this) {
     this.results++;
     if ( results == 2 * Messages ) { return reset( this ); }
 …
+}
 Allocation receive( Client & this, IntMsg & msg ) { return process( this ); }
 Allocation receive( Client & this, CharMsg & msg ) { return process( this ); }
 Allocation receive( Client & this, StateMsg & msg ) with(this) {
+allocation receive( Client & this, IntMsg & msg ) { return process( this ); }
+allocation receive( Client & this, CharMsg & msg ) { return process( this ); }
+allocation receive( Client & this, StateMsg & msg ) with(this) {
     for ( i; Messages ) {
         servers[i] << intmsg[i];

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/static.cfa

r2b78949	r8a930c03
23	23
24	24	uint64_t start_time;
25		Allocation receive( derived_actor & receiver, derived_msg & msg ) {
	25	allocation receive( derived_actor & receiver, derived_msg & msg ) {
26	26	if ( msg.cnt >= Times ) {
27	27	printf("%.2f\n", ((double)(bench_time() - start_time)) / ((double)Times) ); // ns

doc/theses/colby_parsons_MMAth/benchmarks/actors/plotData.py

r2b78949	r8a930c03
160	160
161	161	if currVariant == numVariants:
162		fig, ax = plt.subplots()
	162	fig, ax = plt.subplots(layout='constrained')
163	163	plt.title(name + " Benchmark")
164	164	plt.ylabel("Runtime (seconds)")

doc/theses/colby_parsons_MMAth/benchmarks/channels/plotData.py

r2b78949	r8a930c03
124	124
125	125	if currVariant == numVariants:
126		fig, ax = plt.subplots()
	126	fig, ax = plt.subplots(layout='constrained')
127	127	plt.title(name + " Benchmark")
128	128	plt.ylabel("Throughput (channel operations)")

doc/theses/colby_parsons_MMAth/benchmarks/mutex_stmt/plotData.py

r2b78949	r8a930c03
97	97
98	98	if currVariant == numVariants:
99		fig, ax = plt.subplots()
	99	fig, ax = plt.subplots(layout='constrained')
100	100	plt.title(name + " Benchmark: " + str(currLocks) + " Locks")
101	101	plt.ylabel("Throughput (entries)")

doc/theses/colby_parsons_MMAth/code/basic_actor_example.cfa

r2b78949	r8a930c03
19	19	}
20	20
21		Allocation receive( derived_actor & receiver, derived_msg & msg ) {
	21	allocation receive( derived_actor & receiver, derived_msg & msg ) {
22	22	printf("The message contained the string: %s\n", msg.word);
23	23	return Finished; // Return allocation status of Finished now that the actor is done work

doc/theses/colby_parsons_MMAth/glossary.tex

-              r2b78949
+              r8a930c03
 % Examples from template above
 \newabbreviation{raii}{RAII}{Resource Acquisition Is Initialization}
 \newabbreviation{rtti}{RTTI}{Run-Time Type Information}
 \newabbreviation{fcfs}{FCFS}{First Come First Served}
 \newabbreviation{toctou}{TOCTOU}{time-of-check to time-of-use}
+\newabbreviation{raii}{RAII}{\Newterm{resource acquisition is initialization}}
+\newabbreviation{rtti}{RTTI}{\Newterm{run-time type information}}
+\newabbreviation{fcfs}{FCFS}{\Newterm{first-come first-served}}
+\newabbreviation{toctou}{TOCTOU}{\Newterm{time-of-check to time-of-use}}
 \newglossaryentry{actor}

doc/theses/colby_parsons_MMAth/local.bib

-              r2b78949
+              r8a930c03
 @misc{go:select,
   author = "The Go Programming Language",
   title = "src/runtime/chan.go",
+  title = "src/runtime/select.go",
   howpublished = {\href{https://go.dev/src/runtime/select.go}},
   note = "[Online; accessed 23-May-2023]"
+}
+@misc{go:selectref,
+  author = "The Go Programming Language Specification",
+  title = "Select statements",
+  howpublished = {\href{https://go.dev/ref/spec#Select\_statements}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{boost:channel,
+  author = "Boost C++ Libraries",
+  title = "experimental::basic\_concurrent\_channel",
+  howpublished = {\href{https://www.boost.org/doc/libs/master/doc/html/boost\_asio/reference/experimental\__basic\_concurrent\_channel.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{rust:channel,
+  author = "The Rust Standard Library",
+  title = "std::sync::mpsc::sync\_channel",
+  howpublished = {\href{https://doc.rust-lang.org/std/sync/mpsc/fn.sync\_channel.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{rust:select,
+  author = "The Rust Standard Library",
+  title = "Macro futures::select",
+  howpublished = {\href{https://docs.rs/futures/latest/futures/macro.select.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{ocaml:channel,
+  author = "The OCaml Manual",
+  title = "OCaml library : Event",
+  howpublished = {\href{https://v2.ocaml.org/api/Event.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{haskell:channel,
+  author = "The Haskell Package Repository",
+  title = "Control.Concurrent.Chan",
+  howpublished = {\href{https://hackage.haskell.org/package/base-4.18.0.0/docs/Control-Concurrent-Chan.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{linux:select,
+  author = "Linux man pages",
+  title = "select(2) — Linux manual page",
+  howpublished = {\href{https://man7.org/linux/man-pages/man2/select.2.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{linux:poll,
+  author = "Linux man pages",
+  title = "poll(2) — Linux manual page",
+  howpublished = {\href{https://man7.org/linux/man-pages/man2/poll.2.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{linux:epoll,
+  author = "Linux man pages",
+  title = "epoll(7) — Linux manual page",
+  howpublished = {\href{https://man7.org/linux/man-pages/man7/epoll.7.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@article{Ichbiah79,
+  title={Preliminary Ada reference manual},
+  author={Ichbiah, Jean D},
+  journal={ACM Sigplan Notices},
+  volume={14},
+  number={6a},
+  pages={1--145},
+  year={1979},
+  publisher={ACM New York, NY, USA}
+}
+@misc{cpp:whenany,
+  author = "C++ reference",
+  title = "std::experimental::when\_any",
+  howpublished = {\href{https://en.cppreference.com/w/cpp/experimental/when\_any}},
+  note = "[Online; accessed 23-May-2023]"
+}

doc/theses/colby_parsons_MMAth/style/style.tex

-              r2b78949
+              r8a930c03
 \newsavebox{\myboxB}
+\lstnewenvironment{Golang}[1][]
+{\lstset{language=Go,literate={<-}{\makebox[2ex][c]{\textless\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}}2,
+        moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}
+{}
 \lstnewenvironment{java}[1][]
 {\lstset{language=java,moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}

doc/theses/colby_parsons_MMAth/text/channels.tex

-              r2b78949
+              r8a930c03
 Additionally all channel operations in CSP are synchronous (no buffering).
 Advanced channels as a programming language feature has been popularized in recent years by the language Go~\cite{Go}, which encourages the use of channels as its fundamental concurrent feature.
 It was the popularity of Go channels that lead to their implemention in \CFA.
+It was the popularity of Go channels that lead to their implementation in \CFA.
 Neither Go nor \CFA channels have the restrictions of the early channel-based concurrent systems.
+Other popular languages and libraries that provide channels include C++ Boost~\cite{boost:channel}, Rust~\cite{rust:channel}, Haskell~\cite{haskell:channel}, and OCaml~\cite{ocaml:channel}.
+Boost channels only support asynchronous (non-blocking) operations, and Rust channels are limited to only having one consumer per channel.
+Haskell channels are unbounded in size, and OCaml channels are zero-size.
+These restrictions in Haskell and OCaml are likely due to their functional approach, which results in them both using a list as the underlying data structure for their channel.
+These languages and libraries are not discussed further, as their channel implementation is not comparable to the bounded-buffer style channels present in Go and \CFA.
 \section{Producer-Consumer Problem}
 …
 \section{Channel Implementation}
 Currently, only the Go programming language provides user-level threading where the primary communication mechanism is channels.
 Experiments were conducted that varied the producer-consumer problem algorithm and lock type used inside the channel.
+Experiments were conducted that varied the producer-consumer algorithm and lock type used inside the channel.
 With the exception of non-\gls{fcfs} or non-FIFO algorithms, no algorithm or lock usage in the channel implementation was found to be consistently more performant that Go's choice of algorithm and lock implementation.
 Performance of channels can be improved by sharding the underlying buffer \cite{Dice11}.
 In doing so the FIFO property is lost, which is undesireable for user-facing channels.
+However, the FIFO property is lost, which is undesirable for user-facing channels.
 Therefore, the low-level channel implementation in \CFA is largely copied from the Go implementation, but adapted to the \CFA type and runtime systems.
 As such the research contributions added by \CFA's channel implementation lie in the realm of safety and productivity features.
+The Go channel implementation utilitizes cooperation between threads to achieve good performance~\cite{go:chan}.
+The cooperation between threads only occurs when producers or consumers need to block due to the buffer being full or empty.
+In these cases the blocking thread stores their relevant data in a shared location and the signalling thread will complete their operation before waking them.
+This helps improve performance in a few ways.
+First, each thread interacting with the channel with only acquire and release the internal channel lock exactly once.
+This decreases contention on the internal lock, as only entering threads will compete for the lock since signalled threads never reacquire the lock.
+The other advantage of the cooperation approach is that it eliminates the potential bottleneck of waiting for signalled threads.
+The property of acquiring/releasing the lock only once can be achieved without cooperation by \Newterm{baton passing} the lock.
+Baton passing is when one thread acquires a lock but does not release it, and instead signals a thread inside the critical section conceptually "passing" the mutual exclusion to the signalled thread.
+While baton passing is useful in some algorithms, it results in worse performance than the cooperation approach in channel implementations since all entering threads then need to wait for the blocked thread to reach the front of the ready queue and run before other operations on the channel can proceed.
+The Go channel implementation utilizes cooperation among threads to achieve good performance~\cite{go:chan}.
+This cooperation only occurs when producers or consumers need to block due to the buffer being full or empty.
+In these cases, a blocking thread stores their relevant data in a shared location and the signalling thread completes the blocking thread's operation before waking them;
+\ie the blocking thread has no work to perform after it unblocks because the signalling threads has done this work.
+This approach is similar to wait morphing for locks~\cite[p.~82]{Butenhof97} and improves performance in a few ways.
+First, each thread interacting with the channel only acquires and releases the internal channel lock once.
+As a result, contention on the internal lock is decreased, as only entering threads compete for the lock as unblocking threads do not reacquire the lock.
+The other advantage of Go's wait-morphing approach is that it eliminates the bottleneck of waiting for signalled threads to run.
+Note, the property of acquiring/releasing the lock only once can also be achieved with a different form of cooperation, called \Newterm{baton passing}.
+Baton passing occurs when one thread acquires a lock but does not release it, and instead signals a thread inside the critical section, conceptually ``passing'' the mutual exclusion from the signalling thread to the signalled thread.
+The baton-passing approach has threads cooperate to pass mutual exclusion without additional lock acquires or releases;
+the wait-morphing approach has threads cooperate by completing the signalled thread's operation, thus removing a signalled thread's need for mutual exclusion after unblocking.
+While baton passing is useful in some algorithms, it results in worse channel performance than the Go approach.
+In the baton-passing approach, all threads need to wait for the signalled thread to reach the front of the ready queue, context switch, and run before other operations on the channel can proceed, since the signalled thread holds mutual exclusion;
+in the wait-morphing approach, since the operation is completed before the signal, other threads can continue to operate on the channel without waiting for the signalled thread to run.
 In this work, all channel sizes \see{Sections~\ref{s:ChannelSize}} are implemented with bounded buffers.
 …
 \subsection{Toggle-able Statistics}
 As discussed, a channel is a concurrent layer over a bounded buffer.
 To achieve efficient buffering users should aim for as few blocking operations on a channel as possible.
 Often to achieve this users may change the buffer size, shard a channel into multiple channels, or tweak the number of producer and consumer threads.
 Fo users to be able to make informed decisions when tuning channel usage, toggle-able channel statistics are provided.
 The statistics are toggled at compile time via the @CHAN_STATS@ macro to ensure that they are entirely elided when not used.
 When statistics are turned on, four counters are maintained per channel, two for producers and two for consumers.
+To achieve efficient buffering, users should aim for as few blocking operations on a channel as possible.
+Mechanisms to reduce blocking are: change the buffer size, shard a channel into multiple channels, or tweak the number of producer and consumer threads.
+For users to be able to make informed decisions when tuning channel usage, toggle-able channel statistics are provided.
+The statistics are toggled on during the \CFA build by defining the @CHAN_STATS@ macro, which guarantees zero cost when not using this feature.
+When statistics are turned on, four counters are maintained per channel, two for inserting (producers) and two for removing (consumers).
 The two counters per type of operation track the number of blocking operations and total operations.
+In the channel destructor the counters are printed out aggregated and also per type of operation.
+An example use case of the counters follows.
+A user is buffering information between producer and consumer threads and wants to analyze channel performance.
+Via the statistics they see that producers block for a large percentage of their operations while consumers do not block often.
+They then can use this information to adjust their number of producers/consumers or channel size to achieve a larger percentage of non-blocking producer operations, thus increasing their channel throughput.
+In the channel destructor, the counters are printed out aggregated and also per type of operation.
+An example use case is noting that producer inserts are blocking often while consumer removes do not block often.
+This information can be used to increase the number of consumers to decrease the blocking producer operations, thus increasing the channel throughput.
+Whereas, increasing the channel size in this scenario is unlikely to produce a benefit because the consumers can never keep up with the producers.
 \subsection{Deadlock Detection}
+The deadlock detection in the \CFA channels is fairly basic.
+It only detects the case where threads are blocked on the channel during deallocation.
+This case is guaranteed to deadlock since the list holding the blocked thread is internal to the channel and will be deallocated.
+If a user maintained a separate reference to a thread and unparked it outside the channel they could avoid the deadlock, but would run into other runtime errors since the thread would access channel data after waking that is now deallocated.
+More robust deadlock detection surrounding channel usage would have to be implemented separate from the channel implementation since it would require knowledge about the threading system and other channel/thread state.
+The deadlock detection in the \CFA channels is fairly basic but detects a very common channel mistake during termination.
+That is, it detects the case where threads are blocked on the channel during channel deallocation.
+This case is guaranteed to deadlock since there are no other threads to supply or consume values needed by the waiting threads.
+Only if a user maintained a separate reference to the blocked threads and manually unblocks them outside the channel could the deadlock be avoid.
+However, without special semantics, this unblocking would generate other runtime errors where the unblocked thread attempts to access non-existing channel data or even a deallocated channel.
+More robust deadlock detection needs to be implemented separate from channels since it requires knowledge about the threading system and other channel/thread state.
 \subsection{Program Shutdown}
 Terminating concurrent programs is often one of the most difficult parts of writing concurrent code, particularly if graceful termination is needed.
 The difficulty of graceful termination often arises from the usage of synchronization primitives that need to be handled carefully during shutdown.
+Graceful termination can be difficult to achieve with synchronization primitives that need to be handled carefully during shutdown.
 It is easy to deadlock during termination if threads are left behind on synchronization primitives.
 Additionally, most synchronization primitives are prone to \gls{toctou} issues where there is race between one thread checking the state of a concurrent object and another thread changing the state.
 \gls{toctou} issues with synchronization primitives often involve a race between one thread checking the primitive for blocked threads and another thread blocking on it.
 Channels are a particularly hard synchronization primitive to terminate since both sending and receiving to/from a channel can block.
+Thus, improperly handled \gls{toctou} issues with channels often result in deadlocks as threads trying to perform the termination may end up unexpectedly blocking in their attempt to help other threads exit the system.
+\paragraph{Go channels} provide a set of tools to help with concurrent shutdown~\cite{go:chan}.
+Channels in Go have a @close@ operation and a \Go{select} statement that both can be used to help threads terminate.
+Thus, improperly handled \gls{toctou} issues with channels often result in deadlocks as threads performing the termination may end up unexpectedly blocking in their attempt to help other threads exit the system.
+\paragraph{Go channels} provide a set of tools to help with concurrent shutdown~\cite{go:chan} using a @close@ operation in conjunction with the \Go{select} statement.
 The \Go{select} statement is discussed in \ref{s:waituntil}, where \CFA's @waituntil@ statement is compared with the Go \Go{select} statement.
 …
 Note, panics in Go can be caught, but it is not the idiomatic way to write Go programs.
 While Go's channel closing semantics are powerful enough to perform any concurrent termination needed by a program, their lack of ease of use leaves much to be desired.
+While Go's channel-closing semantics are powerful enough to perform any concurrent termination needed by a program, their lack of ease of use leaves much to be desired.
 Since both closing and sending panic once a channel is closed, a user often has to synchronize the senders (producers) before the channel can be closed to avoid panics.
 However, in doing so it renders the @close@ operation nearly useless, as the only utilities it provides are the ability to ensure receivers no longer block on the channel and receive zero-valued elements.
 This functionality is only useful if the zero-typed element is recognized as a sentinel value, but if another sentinel value is necessary, then @close@ only provides the non-blocking feature.
 To avoid \gls{toctou} issues during shutdown, a busy wait with a \Go{select} statement is often used to add or remove elements from a channel.
 Due to Go's asymmetric approach to channel shutdown, separate synchronization between producers and consumers of a channel has to occur during shutdown.
+Hence, due to Go's asymmetric approach to channel shutdown, separate synchronization between producers and consumers of a channel has to occur during shutdown.
 \paragraph{\CFA channels} have access to an extensive exception handling mechanism~\cite{Beach21}.
 …
 When a channel in \CFA is closed, all subsequent calls to the channel raise a resumption exception at the caller.
 If the resumption is handled, the caller attempts to complete the channel operation.
 However, if channel operation would block, a termination exception is thrown.
+However, if the channel operation would block, a termination exception is thrown.
 If the resumption is not handled, the exception is rethrown as a termination.
 These termination exceptions allow for non-local transfer that is used to great effect to eagerly and gracefully shut down a thread.
 When a channel is closed, if there are any blocked producers or consumers inside the channel, they are woken up and also have a resumption thrown at them.
+The resumption exception, @channel_closed@, has a couple fields to aid in handling the exception.
+The exception contains a pointer to the channel it was thrown from, and a pointer to an element.
+In exceptions thrown from remove the element pointer will be null.
+In the case of insert the element pointer points to the element that the thread attempted to insert.
+The resumption exception, @channel_closed@, has internal fields to aid in handling the exception.
+The exception contains a pointer to the channel it is thrown from and a pointer to a buffer element.
+For exceptions thrown from @remove@, the buffer element pointer is null.
+For exceptions thrown from @insert@, the element pointer points to the buffer element that the thread attempted to insert.
+Utility routines @bool is_insert( channel_closed & e );@ and @bool is_remove( channel_closed & e );@ are provided for convenient checking of the element pointer.
 This element pointer allows the handler to know which operation failed and also allows the element to not be lost on a failed insert since it can be moved elsewhere in the handler.
+Furthermore, due to \CFA's powerful exception system, this data can be used to choose handlers based which channel and operation failed.
+Exception handlers in \CFA have an optional predicate after the exception type which can be used to optionally trigger or skip handlers based on the content of an exception.
+It is worth mentioning that the approach of exceptions for termination may incur a larger performance cost during termination that the approach used in Go.
+This should not be an issue, since termination is rarely an fast-path of an application and ensuring that termination can be implemented correctly with ease is the aim of the exception approach.
+Furthermore, due to \CFA's powerful exception system, this data can be used to choose handlers based on which channel and operation failed.
+For example, exception handlers in \CFA have an optional predicate which can be used to trigger or skip handlers based on the content of the matching exception.
+It is worth mentioning that using exceptions for termination may incur a larger performance cost than the Go approach.
+However, this should not be an issue, since termination is rarely on the fast-path of an application.
+In contrast, ensuring termination can be easily implemented correctly is the aim of the exception approach.
 \section{\CFA / Go channel Examples}
 To highlight the differences between \CFA's and Go's close semantics, three examples will be presented.
+To highlight the differences between \CFA's and Go's close semantics, three examples are presented.
 The first example is a simple shutdown case, where there are producer threads and consumer threads operating on a channel for a fixed duration.
 Once the duration ends, producers and consumers terminate without worrying about any leftover values in the channel.
 The second example extends the first example by requiring the channel to be empty upon shutdown.
+Once the duration ends, producers and consumers terminate immediately leaving unprocessed elements in the channel.
+The second example extends the first by requiring the channel to be empty after shutdown.
 Both the first and second example are shown in Figure~\ref{f:ChannelTermination}.
-First the Go solutions to these examples shown in Figure~\ref{l:go_chan_term} are discussed.
-Since some of the elements being passed through the channel are zero-valued, closing the channel in Go does not aid in communicating shutdown.
-Instead, a different mechanism to communicate with the consumers and producers needs to be used.
-This use of an additional flag or communication method is common in Go channel shutdown code, since to avoid panics on a channel, the shutdown of a channel often has to be communicated with threads before it occurs.
-In this example, a flag is used to communicate with producers and another flag is used for consumers.
-Producers and consumers need separate avenues of communication both so that producers terminate before the channel is closed to avoid panicking, and to avoid the case where all the consumers terminate first, which can result in a deadlock for producers if the channel is full.
-The producer flag is set first, then after producers terminate the consumer flag is set and the channel is closed.
-In the second example where all values need to be consumed, the main thread iterates over the closed channel to process any remaining values.
-In the \CFA solutions in Figure~\ref{l:cfa_chan_term}, shutdown is communicated directly to both producers and consumers via the @close@ call.
-In the first example where all values do not need to be consumed, both producers and consumers do not handle the resumption and finish once they receive the termination exception.
-The second \CFA example where all values must be consumed highlights how resumption is used with channel shutdown.
-The @Producer@ thread-main knows to stop producing when the @insert@ call on a closed channel raises exception @channel_closed@.
-The @Consumer@ thread-main knows to stop consuming after all elements of a closed channel are removed and the call to @remove@ would block.
-Hence, the consumer knows the moment the channel closes because a resumption exception is raised, caught, and ignored, and then control returns to @remove@ to return another item from the buffer.
-Only when the buffer is drained and the call to @remove@ would block, a termination exception is raised to stop consuming.
-The \CFA semantics allow users to communicate channel shutdown directly through the channel, without having to share extra state between threads.
-Additionally, when the channel needs to be drained, \CFA provides users with easy options for processing the leftover channel values in the main thread or in the consumer threads.
-If one wishes to consume the leftover values in the consumer threads in Go, extra synchronization between the main thread and the consumer threads is needed.
 \begin{figure}
 …
 \begin{lrbox}{\myboxA}
+\begin{Golang}[aboveskip=0pt,belowskip=0pt]
+var channel chan int = make( chan int, 128 )
+var prodJoin chan int = make( chan int, 4 )
+var consJoin chan int = make( chan int, 4 )
+var cons_done, prod_done bool = false, false;
+func producer() {
+        for {
+                if prod_done { break }
+                channel <- 5
+        }
+        prodJoin <- 0 // synch with main thd
+}
+func consumer() {
+        for {
+                if cons_done { break }
+                <- channel
+        }
+        consJoin <- 0 // synch with main thd
+}
+func main() {
+        for j := 0; j < 4; j++ { go consumer() }
+        for j := 0; j < 4; j++ { go producer() }
+        time.Sleep( time.Second * 10 )
+        prod_done = true
+        for j := 0; j < 4 ; j++ { <- prodJoin }
+        cons_done = true
+        close(channel) // ensure no cons deadlock
+        @for elem := range channel {@
+                // process leftover values
+        @}@
+        for j := 0; j < 4; j++ { <- consJoin }
+}
+\end{Golang}
+\end{lrbox}
+\begin{lrbox}{\myboxB}
 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
+channel( size_t ) Channel{ ChannelSize };
+channel( size_t ) chan{ 128 };
 thread Consumer {};
+thread Producer {};
+void main( Producer & this ) {
+        try {
+                for ()
+                        insert( chan, 5 );
+        } catch( channel_closed * ) {
+                // unhandled resume or full
+        }
+}
 void main( Consumer & this ) {
+    try {
+        for ( ;; )
+            remove( Channel );
+    @} catchResume( channel_closed * ) { @
+    // handled resume => consume from chan
+    } catch( channel_closed * ) {
+        // empty or unhandled resume
+    }
+}
+thread Producer {};
+void main( Producer & this ) {
+    size_t count = 0;
+    try {
+        for ( ;; )
+            insert( Channel, count++ );
+    } catch ( channel_closed * ) {
+        // unhandled resume or full
+    }
+}
+int main( int argc, char * argv[] ) {
+    Consumer c[Consumers];
+    Producer p[Producers];
+    sleep(Duration`s);
+    close( Channel );
+    return 0;
+}
+        try {
+                for () { int i = remove( chan ); }
+        @} catchResume( channel_closed * ) {@
+                // handled resume => consume from chan
+        } catch( channel_closed * ) {
+                // empty or unhandled resume
+        }
+}
+int main() {
+        Consumer c[4];
+        Producer p[4];
+        sleep( 10`s );
+        close( chan );
+}
 \end{cfa}
 \end{lrbox}
+\begin{lrbox}{\myboxB}
+\begin{cfa}[aboveskip=0pt,belowskip=0pt]
+var cons_done, prod_done bool = false, false;
+var prodJoin chan int = make(chan int, Producers)
+var consJoin chan int = make(chan int, Consumers)
+func consumer( channel chan uint64 ) {
+    for {
+        if cons_done { break }
+        <-channel
+    }
+    consJoin <- 0 // synch with main thd
+}
+func producer( channel chan uint64 ) {
+    var count uint64 = 0
+    for {
+        if prod_done { break }
+        channel <- count++
+    }
+    prodJoin <- 0 // synch with main thd
+}
+func main() {
+    channel = make(chan uint64, ChannelSize)
+    for j := 0; j < Consumers; j++ {
+        go consumer( channel )
+    }
+    for j := 0; j < Producers; j++ {
+        go producer( channel )
+    }
+    time.Sleep(time.Second * Duration)
+    prod_done = true
+    for j := 0; j < Producers ; j++ {
+        <-prodJoin // wait for prods
+    }
+    cons_done = true
+    close(channel) // ensure no cons deadlock
+    @for elem := range channel { @
+        // process leftover values
+    @}@
+    for j := 0; j < Consumers; j++{
+        <-consJoin // wait for cons
+    }
+}
+\end{cfa}
+\end{lrbox}
+\subfloat[\CFA style]{\label{l:cfa_chan_term}\usebox\myboxA}
+\subfloat[Go style]{\label{l:go_chan_term}\usebox\myboxA}
 \hspace*{3pt}
 \vrule
 \hspace*{3pt}
 \subfloat[Go style]{\label{l:go_chan_term}\usebox\myboxB}
+\subfloat[\CFA style]{\label{l:cfa_chan_term}\usebox\myboxB}
 \caption{Channel Termination Examples 1 and 2. Code specific to example 2 is highlighted.}
 \label{f:ChannelTermination}
 \end{figure}
+The final shutdown example uses channels to implement a barrier.
+It is shown in Figure~\ref{f:ChannelBarrierTermination}.
+The problem of implementing a barrier is chosen since threads are both producers and consumers on the barrier-internal channels, which removes the ability to easily synchronize producers before consumers during shutdown.
+As such, while the shutdown details will be discussed with this problem in mind, they are also applicable to other problems taht have individual threads both producing and consuming from channels.
+Both of these examples are implemented using \CFA syntax so that they can be easily compared.
+Figure~\ref{l:cfa_chan_bar} uses \CFA-style channel close semantics and Figure~\ref{l:go_chan_bar} uses Go-style close semantics.
+In this example it is infeasible to use the Go @close@ call since all threads are both potentially producers and consumers, causing panics on close to be unavoidable without complex synchronization.
+As such in Figure~\ref{l:go_chan_bar} to implement a flush routine for the buffer, a sentinel value of @-1@ has to be used to indicate to threads that they need to leave the barrier.
+This sentinel value has to be checked at two points.
+Figure~\ref{l:go_chan_term} shows the Go solution.
+Since some of the elements being passed through the channel are zero-valued, closing the channel in Go does not aid in communicating shutdown.
+Instead, a different mechanism to communicate with the consumers and producers needs to be used.
+Flag variables are common in Go-channel shutdown-code to avoid panics on a channel, meaning the channel shutdown has to be communicated with threads before it occurs.
+Hence, the two flags @cons_done@ and @prod_done@ are used to communicate with the producers and consumers, respectively.
+Furthermore, producers and consumers need to shutdown separately to ensure that producers terminate before the channel is closed to avoid panicking, and to avoid the case where all the consumers terminate first, which can result in a deadlock for producers if the channel is full.
+The producer flag is set first;
+then after all producers terminate, the consumer flag is set and the channel is closed leaving elements in the buffer.
+To purge the buffer, a loop is added (red) that iterates over the closed channel to process any remaining values.
+Figure~\ref{l:cfa_chan_term} shows the \CFA solution.
+Here, shutdown is communicated directly to both producers and consumers via the @close@ call.
+A @Producer@ thread knows to stop producing when the @insert@ call on a closed channel raises exception @channel_closed@.
+If a @Consumer@ thread ignores the first resumption exception from the @close@, the exception is reraised as a termination exception and elements are left in the buffer.
+If a @Consumer@ thread handles the resumptions exceptions (red), control returns to complete the remove.
+A @Consumer@ thread knows to stop consuming after all elements of a closed channel are removed and the consumer would block, which causes a termination raise of @channel_closed@.
+The \CFA semantics allow users to communicate channel shutdown directly through the channel, without having to share extra state between threads.
+Additionally, when the channel needs to be drained, \CFA provides users with easy options for processing the leftover channel values in the main thread or in the consumer threads.
+Figure~\ref{f:ChannelBarrierTermination} shows a final shutdown example using channels to implement a barrier.
+A Go and \CFA style solution are presented but both are implemented using \CFA syntax so they can be easily compared.
+Implementing a barrier is interesting because threads are both producers and consumers on the barrier-internal channels, @entryWait@ and @barWait@.
+The outline for the barrier implementation starts by initially filling the @entryWait@ channel with $N$ tickets in the barrier constructor, allowing $N$ arriving threads to remove these values and enter the barrier.
+After @entryWait@ is empty, arriving threads block when removing.
+However, the arriving threads that entered the barrier cannot leave the barrier until $N$ threads have arrived.
+Hence, the entering threads block on the empty @barWait@ channel until the $N$th arriving thread inserts $N-1$ elements into @barWait@ to unblock the $N-1$ threads calling @remove@.
+The race between these arriving threads blocking on @barWait@ and the $N$th thread inserting values into @barWait@ does not affect correctness;
+\ie an arriving thread may or may not block on channel @barWait@ to get its value.
+Finally, the last thread to remove from @barWait@ with ticket $N-2$, refills channel @entryWait@ with $N$ values to start the next group into the barrier.
+Now, the two channels makes termination synchronization between producers and consumers difficult.
+Interestingly, the shutdown details for this problem are also applicable to other problems with threads producing and consuming from the same channel.
+The Go-style solution cannot use the Go @close@ call since all threads are both potentially producers and consumers, causing panics on close to be unavoidable without complex synchronization.
+As such in Figure \ref{l:go_chan_bar}, a flush routine is needed to insert a sentinel value, @-1@, to inform threads waiting in the buffer they need to leave the barrier.
+This sentinel value has to be checked at two points along the fast-path and sentinel values daisy-chained into the buffers.
 Furthermore, an additional flag @done@ is needed to communicate to threads once they have left the barrier that they are done.
 In the \CFA version~\ref{l:cfa_chan_bar}, the barrier shutdown results in an exception being thrown at threads operating on it, which informs the threads that they must terminate.
+Also note that in the Go version~\ref{l:go_chan_bar}, the size of the barrier channels has to be larger than in the \CFA version to ensure that the main thread does not block when attempting to clear the barrier.
+For The \CFA solution~\ref{l:cfa_chan_bar}, the barrier shutdown results in an exception being thrown at threads operating on it, to inform waiting threads they must leave the barrier.
 This avoids the need to use a separate communication method other than the barrier, and avoids extra conditional checks on the fast path of the barrier implementation.
-Also note that in the Go version~\ref{l:go_chan_bar}, the size of the barrier channels has to be larger than in the \CFA version to ensure that the main thread does not block when attempting to clear the barrier.
 \begin{figure}
 …
 \begin{lrbox}{\myboxA}
+\begin{cfa}[aboveskip=0pt,belowskip=0pt]
+struct barrier {
+        channel( int ) barWait, entryWait;
+        int size;
+};
+void ?{}( barrier & this, int size ) with(this) {
+        barWait{size + 1};   entryWait{size + 1};
+        this.size = size;
+        for ( i; size )
+                insert( entryWait, i );
+}
+void wait( barrier & this ) with(this) {
+        int ticket = remove( entryWait );
+        @if ( ticket == -1 ) { insert( entryWait, -1 ); return; }@
+        if ( ticket == size - 1 ) {
+                for ( i; size - 1 )
+                        insert( barWait, i );
+                return;
+        }
+        ticket = remove( barWait );
+        @if ( ticket == -1 ) { insert( barWait, -1 ); return; }@
+        if ( size == 1 || ticket == size - 2 ) { // last ?
+                for ( i; size )
+                        insert( entryWait, i );
+        }
+}
+void flush(barrier & this) with(this) {
+        @insert( entryWait, -1 );   insert( barWait, -1 );@
+}
+enum { Threads = 4 };
+barrier b{Threads};
+@bool done = false;@
+thread Thread {};
+void main( Thread & this ) {
+        for () {
+          @if ( done ) break;@
+                wait( b );
+        }
+}
+int main() {
+        Thread t[Threads];
+        sleep(10`s);
+        done = true;
+        flush( b );
+} // wait for threads to terminate
+\end{cfa}
+\end{lrbox}
+\begin{lrbox}{\myboxB}
 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
 struct barrier {
 …
 \end{lrbox}
+\begin{lrbox}{\myboxB}
+\begin{cfa}[aboveskip=0pt,belowskip=0pt]
+struct barrier {
+        channel( int ) barWait, entryWait;
+        int size;
+};
+void ?{}( barrier & this, int size ) with(this) {
+        barWait{size + 1};   entryWait{size + 1};
+        this.size = size;
+        for ( i; size )
+                insert( entryWait, i );
+}
+void wait( barrier & this ) with(this) {
+        int ticket = remove( entryWait );
+        @if ( ticket == -1 ) { insert( entryWait, -1 ); return; }@
+        if ( ticket == size - 1 ) {
+                for ( i; size - 1 )
+                        insert( barWait, i );
+                return;
+        }
+        ticket = remove( barWait );
+        @if ( ticket == -1 ) { insert( barWait, -1 ); return; }@
+        if ( size == 1 || ticket == size - 2 ) { // last ?
+                for ( i; size )
+                        insert( entryWait, i );
+        }
+}
+void flush(barrier & this) with(this) {
+        @insert( entryWait, -1 );   insert( barWait, -1 );@
+}
+enum { Threads = 4 };
+barrier b{Threads};
+@bool done = false;@
+thread Thread {};
+void main( Thread & this ) {
+        for () {
+          @if ( done ) break;@
+                wait( b );
+        }
+}
+int main() {
+        Thread t[Threads];
+        sleep(10`s);
+        done = true;
+        flush( b );
+} // wait for threads to terminate
+\end{cfa}
+\end{lrbox}
+\subfloat[\CFA style]{\label{l:cfa_chan_bar}\usebox\myboxA}
+\subfloat[Go style]{\label{l:go_chan_bar}\usebox\myboxA}
 \hspace*{3pt}
 \vrule
 \hspace*{3pt}
 \subfloat[Go style]{\label{l:go_chan_bar}\usebox\myboxB}
+\subfloat[\CFA style]{\label{l:cfa_chan_bar}\usebox\myboxB}
 \caption{Channel Barrier Termination}
 \label{f:ChannelBarrierTermination}

doc/theses/colby_parsons_MMAth/text/waituntil.tex

-              r2b78949
+              r8a930c03
 The ability to wait for the first stall available without spinning can be done with concurrent tools that provide \gls{synch_multiplex}, the ability to wait synchronously for a resource or set of resources.
-% C_TODO: fill in citations in following section
 \section{History of Synchronous Multiplexing}
 There is a history of tools that provide \gls{synch_multiplex}.
 Some of the most well known include the set or unix system utilities signal(2)\cite{}, poll(2)\cite{}, and epoll(7)\cite{}, and the select statement provided by Go\cite{}.
+Some of the most well known include the set of unix system utilities: select(2)\cite{linux:select}, poll(2)\cite{linux:poll}, and epoll(7)\cite{linux:epoll}, and the select statement provided by Go\cite{go:selectref}.
 Before one can examine the history of \gls{synch_multiplex} implementations in detail, the preceding theory must be discussed.
 …
 If a guard is false then the resource it guards is considered to not be in the set of resources being waited on.
 Guards can be simulated using if statements, but to do so requires \[2^N\] if cases, where @N@ is the number of guards.
+This transformation from guards to if statements will be discussed further in Section~\ref{}. % C_TODO: fill ref when writing semantics section later
+The equivalence between guards and exponential if statements comes from an Occam ALT statement rule~\cite{Roscoe88}, which is presented in \CFA syntax in Figure~\ref{f:wu_if}.
+Providing guards allows for easy toggling of waituntil clauses without introducing repeated code.
+\begin{figure}
+\begin{cfa}
+when( predicate ) waituntil( A ) {}
+or waituntil( B ) {}
+// ===
+if ( predicate ) {
+    waituntil( A ) {}
+    or waituntil( B ) {}
+} else {
+    waituntil( B ) {}
+}
+\end{cfa}
+\caption{Occam's guard to if statement equivalence shown in \CFA syntax.}
+\label{f:wu_if}
+\end{figure}
 Switching to implementations, it is important to discuss the resources being multiplexed.
 …
 It is worth noting these \gls{synch_multiplex} tools mentioned so far interact directly with the operating system and are often used to communicate between processes.
 Later \gls{synch_multiplex} started to appear in user-space to support fast multiplexed concurrent communication between threads.
 An early example of \gls{synch_multiplex} is the select statement in Ada.
+An early example of \gls{synch_multiplex} is the select statement in Ada~\cite[\S~9.7]{Ichbiah79}.
 The select statement in Ada allows a task to multiplex over some subset of its own methods that it would like to @accept@ calls to.
 Tasks in Ada can be thought of as threads which are an object of a specific class, and as such have methods, fields, etc.
 …
 The @else@ changes the synchronous multiplexing to asynchronous multiplexing.
 If an @else@ clause is in a select statement and no calls to the @accept@ed methods are immediately available the code block associated with the @else@ is run and the task does not block.
+The most popular example of user-space \gls{synch_multiplex} is Go with their select statement.
+A popular example of user-space \gls{synch_multiplex} is Go with their select statement~\cite{go:selectref}.
 Go's select statement operates on channels and has the same exclusive-or semantics as the ALT primitive from Occam, and has associated code blocks for each clause like ALT and Ada.
 However, unlike Ada and ALT, Go does not provide any guards for their select statement cases.
 Go provides a timeout utility and also provides a @default@ clause which has the same semantics as Ada's @else@ clause.
+\uC provides \gls{synch_multiplex} over futures with their @_Select@ statement and Ada-style \gls{synch_multiplex} over monitor methods with their @_Accept@ statement~\cite{uC++}.
+Their @_Accept@ statement builds upon the select statement offered by Ada, by offering both @and@ and @or@ semantics, which can be used together in the same statement.
+These semantics are also supported for \uC's @_Select@ statement.
+This enables fully expressive \gls{synch_multiplex} predicates.
+There are many other languages that provide \gls{synch_multiplex}, including Rust's @select!@ over futures~\cite{rust:select}, OCaml's @select@ over channels~\cite{ocaml:channe}, and C++14's @when_any@ over futures~\cite{cpp:whenany}.
+Note that while C++14 and Rust provide \gls{synch_multiplex}, their implemetations leave much to be desired as they both rely on busy-waiting polling to wait on multiple resources.
 \section{Other Approaches to Synchronous Multiplexing}
 …
 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.
 \section{\CFA's Waituntil Statement}
+The new \CFA \gls{synch_multiplex} utility introduced in this work is the @waituntil@ statement.
+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.
+All of the \gls{synch_multiplex} features mentioned so far are monomorphic, only supporting one resource to wait on, select(2) supports file descriptors, Go's select supports channel operations, \uC's select supports futures, and Ada's select supports monitor method calls.
+The waituntil statement in \CFA is polymorphic and provides \gls{synch_multiplex} over any objects that satisfy the trait in Figure~\ref{f:wu_trait}.
+\begin{figure}
+\begin{cfa}
+forall(T & | sized(T))
+trait is_selectable {
+    // For registering a waituntil stmt on a selectable type
+    bool register_select( T &, select_node & );
+    // For unregistering a waituntil stmt from a selectable type
+    bool unregister_select( T &, select_node & );
+    // on_selected is run on the selecting thread prior to executing the statement associated with the select_node
+    void on_selected( T &, select_node & );
+};
+\end{cfa}
+\caption{Trait for types that can be passed into \CFA's waituntil statement.}
+\label{f:wu_trait}
+\end{figure}
+Currently locks, channels, futures and timeouts are supported by the waituntil statement, but this will be expanded as other use cases arise.
+The waituntil statement supports guarded clauses, like Ada, and Occam, supports both @or@, and @and@ semantics, like \uC, and provides an @else@ for asynchronous multiplexing. An example of \CFA waituntil usage is shown in Figure~\ref{f:wu_example}. In Figure~\ref{f:wu_example} the waituntil statement is waiting for either @Lock@ to be available or for a value to be read from @Channel@ into @i@ and for @Future@ to be fulfilled. The semantics of the waituntil statement will be discussed in detail in the next section.
+\begin{figure}
+\begin{cfa}
+future(int) Future;
+channel(int) Channel;
+owner_lock Lock;
+int i = 0;
+waituntil( Lock ) { ... }
+or when( i == 0 ) waituntil( i << Channel ) { ... }
+and waituntil( Future ) { ... }
+\end{cfa}
+\caption{Example of \CFA's waituntil statement}
+\label{f:wu_example}
+\end{figure}
+\section{Waituntil Semantics}
+There are two parts of the waituntil semantics to discuss, 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.
+To start, the semantics of the statement itself will be discussed.
+\subsection{Waituntil Statement Semantics}
+The @or@ semantics are the most straightforward and nearly match those laid out in the ALT statement from Occam, the clauses have an exclusive-or relationship where the first one to be available will be run and only one clause is run.
+\CFA's @or@ semantics differ from ALT semantics in one respect, instead of randomly picking a clause when multiple are available, the clause that appears first in the order of clauses will be picked.
+\eg in the following example, if @foo@ and @bar@ are both available, @foo@ will always be selected since it comes first in the order of waituntil clauses.
+\begin{cfa}
+future(int) bar;
+future(int) foo;
+waituntil( foo ) { ... }
+or waituntil( bar ) { ... }
+\end{cfa}
+The @and@ semantics match the @and@ semantics used by \uC.
+When multiple clauses are joined by @and@, the waituntil will make a thread wait for all to be available, but will run the corresponding code blocks \emph{as they become available}.
+As @and@ clauses are made available, the thread will be woken to run those clauses' code blocks and then the thread will wait again until all clauses have been run.
+This 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.
+If the @and@ operator waited for all clauses to be available before running, it would not provide much more use that just acquiring those resources one by one in subsequent lines of code.
+The @and@ operator binds more tightly than the @or@ operator.
+To give an @or@ operator higher precedence brackets can be used.
+\eg the following waituntil unconditionally waits for @C@ and one of either @A@ or @B@, since the @or@ is given higher precendence via brackets.
+\begin{cfa}
+(waituntil( A ) { ... }
+or waituntil( B ) { ... } )
+and waituntil( C ) { ... }
+\end{cfa}
+The guards in the waituntil statement are called @when@ clauses.
+The @when@ clause is passed a boolean expression.
+All the @when@ boolean expressions are evaluated before the waituntil statement is run.
+The guards in Occam's ALT effectively toggle clauses on and off, where a clause will only be evaluated and waited on if the corresponding guard is @true@.
+The guards in the waituntil statement operate the same way, but require some nuance since both @and@ and @or@ operators are supported.
+When a guard is false and a clause is removed, it can be thought of as removing that clause and its preceding operator from the statement.
+\eg in the following example the two waituntil statements are semantically the same.
+\begin{cfa}
+when(true) waituntil( A ) { ... }
+or when(false) waituntil( B ) { ... }
+and waituntil( C ) { ... }
+// ===
+waituntil( A ) { ... }
+and waituntil( C ) { ... }
+\end{cfa}
+The @else@ clause on the waituntil has identical semantics to the @else@ clause in Ada.
+If all resources are not immediately available and there is an @else@ clause, the @else@ clause is run and the thread will not block.
+\subsection{Waituntil Type Semantics}
+As described earlier, to support interaction with the waituntil statement a type must support the trait shown in Figure~\ref{f:wu_trait}.
+The waituntil statement expects types to register and unregister themselves via calls to @register_select@ and @unregister_select@ respectively.
+When a resource becomes available, @on_selected@ is run.
+Many types may not need @on_selected@, but it is provided since some types may need to check and set things before the resource can be accessed in the code block.
+The register/unregister routines in the trait return booleans.
+The return value of @register_select@ is @true@ if the resource is immediately available, and @false@ otherwise.
+The return value of @unregister_select@ is @true@ if the corresponding code block should be run after unregistration and @false@ otherwise.
+The routine @on_selected@, and the return value of @unregister_select@ were needed to support channels as a resource.
+More detail on channels and their interaction with waituntil will be discussed in Section~\ref{s:wu_chans}.
+\section{Waituntil Implementation}
+The waituntil statement is not inherently complex, and can be described as a few steps.
+The complexity of the statement comes from the consideration of race conditions and synchronization needed when supporting various primitives.
+The basic steps that the waituntil statement follows are the following.
+First the waituntil statement creates a @select_node@ per resource that is being waited on.
+The @select_node@ is an object that stores the waituntil data pertaining to one of the resources.
+Then, each @select_node@ is then registered with the corresponding resource.
+The thread executing the waituntil then enters a loop that will loop until the entire waituntil statement being satisfied.
+In each iteration of the loop the thread attempts to block.
+If any clauses are satified the block will fail and the thread will proceed, otherwise the block succeeds.
+After proceeding past the block all clauses are checked for completion and the completed clauses have their code blocks run.
+Once the thread escapes the loop, the @select_nodes@ are unregistered from the resources.
+In the case where the block suceeds, the thread will be woken by the thread that marks one of the resources as available.
+Pseudocode detailing these steps is presented in the following code block.
+\begin{cfa}
+select_nodes s[N]; // N select nodes
+for ( node in s )
+    register_select( resource, node );
+while( statement not satisfied ) {
+    // try to block
+    for ( resource in waituntil statement )
+        if ( resource is avail ) run code block
+}
+for ( node in s )
+    unregister_select( resource, node );
+\end{cfa}
+These steps give a basic, but mildly inaccurate overview of how the statement works.
+Digging into some parts of the implementation will shed light on more of the specifics and provide some accuracy.
+\subsection{Locks}
+Locks are one of the resources supported in the waituntil statement.
+When a thread waits on multiple locks via a waituntil, it enqueues a @select_node@ in each of the lock's waiting queues.
+When a @select_node@ reaches the front of the queue and gains ownership of a lock, the blocked thread is notified.
+The lock will be held until the node is unregistered.
+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.
+This prevents deadlocks since the waiting thread will never hold a lock while waiting on another resource.
+As such the only nodes unregistered at the end are the ones that have not run.
+\subsection{Timeouts}
+Timeouts in the waituntil take the form of a duration being passed to a @sleep@ or @timeout@ call.
+An example is shown in the following code.
+\begin{cfa}
+waituntil( sleep( 1`ms ) ) {}
+waituntil( timeout( 1`s ) ) {} or waituntil( timeout( 2`s ) ) {}
+waituntil( timeout( 1`ns ) ) {} and waituntil( timeout( 2`s ) ) {}
+\end{cfa}
+The timeout implementation highlights a key part of the waituntil semantics, the expression is evaluated before the waituntil runs.
+As such calls to @sleep@ and @timeout@ do not block, but instead return a type that supports the @is_selectable@ trait.
+This mechanism is needed for types that want to support multiple operations such as channels that support reading and writing.
+\subsection{Channels}\label{s:wu_chans}
+To support both waiting on both reading and writing to channels, the opperators @?<<?@ and @?>>?@ are used to show reading and writing to a channel respectively, where the lefthand operand is the value and the righthand operand is the channel.
+Channels require significant complexity to wait on for a few reasons.
+The first reason is that reading or writing to a channel is a mutating operation.
+What this means is that if a read or write to a channel occurs, the state of the channel has changed.
+In comparison, for standard locks and futures, if a lock is acquired then released or a future is ready but not accessed, the states of the lock and the future are not modified.
+In this way if a waituntil over locks or futures have some resources available that were not consumed, it is not an issue.
+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.
+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.
+As such some channel code blocks may be run as part of the unregister.
+Furthermore if there are both @and@ and @or@ operators, the @or@ operators stop behaving like exclusive-or semantics since this race between operations and unregisters exists.
+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.
+This approach is infeasible in the case where @and@ and @or@ operators are used.
+To show this consider the following waituntil statement.
+\begin{cfa}
+waituntil( i >> A ) {} and waituntil( i >> B ) {}
+or waituntil( i >> C ) {} and waituntil( i >> D ) {}
+\end{cfa}
+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@.
+However, to race before operation completion in this case introduces a race whose complexity increases with the size of the waituntil statement.
+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@.
+Furthermore, the race for the @or@ would also need to be won.
+However, due to TOCTOU issues, one cannot know that all resources are available without acquiring all the internal locks of channels in the subtree.
+This is not a good solution for two reasons.
+It is possible that once all the locks are acquired that the subtree is not satisfied and they must all be released.
+This would incur high cost for signalling threads and also 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 are lost when using both @and@ and @or@ operators since they can not be supported without significant complexity and hits to waituntil statement performance.
+The mechanism by which the predicate of the waituntil is checked is discussed in more detail in Section~\ref{s:wu_guards}.
+Another consideration introduced by channels is that supporting both reading and writing to a channel in a waituntil means that one waituntil clause may be the notifier for another waituntil clause.
+This becomes a problem when dealing with the special-cased @or@ where the clauses need to win a race to operate on a channel.
+When you have both a special-case @or@ inserting on one thread and another special-case @or@ consuming is blocked on another thread there is not one but two races that need to be consolidated by the inserting thread.
+(The race can occur in the opposite case with a blocked producer and signalling consumer too.)
+For them to know that the insert succeeded, they need to win the race for their own waituntil and win the race for the other waituntil.
+Go solves this problem in their select statement by acquiring the internal locks of all channels before registering the select on the channels.
+This eliminates the race since no other threads can operate on the blocked channel since its lock will be held.
+This approach is not used in \CFA since the waituntil is polymorphic.
+Not all types in a waituntil have an internal lock, and when using non-channel types acquiring all the locks incurs extra uneeded overhead.
+Instead this race is consolidated in \CFA in two phases by having an intermediate pending status value for the race.
+This case is detectable, and if detected the thread attempting to signal will first race to set the race flag to be pending.
+If it succeeds, it then attempts to set the consumer's race flag to its success value.
+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.
+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.
+This protocol ensures that signals will not be lost and that the two races can be resolved in a safe manner.
+Channels in \CFA have exception based shutdown mechanisms that the waituntil statement needs to support.
+These exception mechanisms were what brought in the @on_selected@ routine.
+This routine is needed by channels to detect if they are closed upon waking from a waituntil statement, to ensure that the appropriate behaviour is taken.
+\subsection{Guards and Statement Predicate}\label{s:wu_guards}
+Checking for when a synchronous multiplexing utility is done is trivial when it has an or/xor relationship, since any resource becoming available means that the blocked thread can proceed.
+In \uC and \CFA, their \gls{synch_multiplex} utilities involve both an @and@ and @or@ operator, which make the problem of checking for completion of the statement more difficult.
+In the \uC @_Select@ statement, they solve this problem by constructing a tree of the resources, where the internal nodes are operators and the leafs are the resources.
+The internal nodes also store the status of each of the subtrees beneath them.
+When resources become available, their status is modified and the status of the leaf nodes percolate into the internal nodes update the state of the statement.
+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, their subtrees marked as @true@ are effectively pruned and are not touched again.
+To support \uC's @_Select@ statement guards, the tree prunes the branch if the guard is false.
+The \CFA waituntil statement blocks a thread until a set of resources have become available that satisfy the underlying predicate.
+The waiting condition of the waituntil statement can be represented as a predicate over the resources, joined by the waituntil operators, where a resource is @true@ if it is available, and @false@ otherwise.
+In \CFA, this representation is used as the mechanism to check if a thread is done waiting on the waituntil.
+Leveraging the compiler, a routine is generated per waituntil that is passed the statuses of the resources and returns a boolean that is @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 ensure that the predicate function behaves as if that resource is no longer part of the predicate.
+In \uC's @_Select@, it supports operators both inside and outside the clauses of their statement.
+\eg in the following example the code blocks will run once their corresponding predicate inside the round braces is satisfied.
+% C_TODO put this is uC++ code style not cfa-style
+\begin{cfa}
+Future_ISM<int> A, B, C, D;
+_Select( A || B && C ) { ... }
+and _Select( D && E ) { ... }
+\end{cfa}
+This is more expressive that the waituntil statement in \CFA.
+In \CFA, since the waituntil statement supports more resources than just futures, implmenting operators inside clauses was avoided for a few reasons.
+As an example, suppose \CFA supported operators inside clauses and consider the code snippet in Figure~\ref{f:wu_inside_op}.
+\begin{figure}
+\begin{cfa}
+owner_lock A, B, C, D;
+waituntil( A && B ) { ... }
+or waituntil( C && D ) { ... }
+\end{cfa}
+\caption{Example of unsupported operators inside clauses in \CFA.}
+\label{f:wu_inside_op}
+\end{figure}
+If the waituntil in Figure~\ref{f:wu_inside_op} works with the same semantics as described and acquires each lock as it becomes available, it opens itself up to possible deadlocks since it is now holding locks and waiting on other resources.
+As such other semantics would be needed to ensure that this operation is safe.
+One possibility is to use \CC's @scoped_lock@ approach that was described in Section~\ref{s:DeadlockAvoidance}, however the potential for livelock leaves much to be desired.
+Another possibility would be to use resource ordering similar to \CFA's @mutex@ statement, but that alone is not sufficient if the resource ordering is not used everywhere.
+Additionally, using resource ordering could conflict with other semantics of the waituntil statement.
+To show this conflict, consider if the locks in Figure~\ref{f:wu_inside_op} were ordered @D@, @B@, @C@, @A@.
+If all the locks are available, it becomes complex to both respect the ordering of the waituntil in Figure~\ref{f:wu_inside_op} when choosing which code block to run and also respect the lock ordering of @D@, @B@, @C@, @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 won't work due to TOCTOU issues, as it is not possible to ensure that the full set resources are available without holding them all first.
+Operators inside clauses in \CFA could potentially be implemented with careful circumvention of the problems involved, but it was not deemed an important feature when taking into account the runtime cost that would need to be paid to handle these situations.
+The problem of operators inside clauses also becomes a difficult issue to handle when supporting channels.
+If internal operators were supported, it would require some way to ensure that channels with internal operators are modified on if and only if the corresponding code block is run, but that is not feasible due to reasons described in the exclusive-or portion of Section~\ref{s:wu_chans}.
+\section{Waituntil Performance}
+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.
+As such, two microbenchmarks are presented, one for Go and one for \uC to contrast the systems.
+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.
+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 userspace.
+Ada's @select@ only operates on methods, which is done in \CFA via the @waitfor@ utility so it is not feasible to benchmark against the @waituntil@, which cannot wait on the same resource.
+Rust and \CC only offer a busy-wait based approach which is not meaningly comparable to a blocking approach.
+OCaml's @select@ waits on channels that are not comparable with \CFA and Go channels, which makes the OCaml @select@ infeasible to compare it with Go's @select@ and \CFA's @waituntil@.
+Given the differences in features, polymorphism, and expressibility between the 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.
+\subsection{Channel Benchmark}
+The channel microbenchmark compares \CFA's waituntil and Go's select, where the resource being waited on is a set of channels.
+%C_TODO explain benchmark
+%C_TODO show results
+%C_TODO discuss results
+\subsection{Future Benchmark}
+The future benchmark compares \CFA's waituntil with \uC's @_Select@, with both utilities waiting on futures.
+%C_TODO explain benchmark
+%C_TODO show results
+%C_TODO discuss results

doc/theses/colby_parsons_MMAth/thesis.tex

-              r2b78949
+              r8a930c03
     colorlinks=true,        % false: boxed links; true: colored links
     linkcolor=blue,         % color of internal links
     citecolor=blue,        % color of links to bibliography
+    citecolor=blue,         % color of links to bibliography
     filecolor=magenta,      % color of file links
+    urlcolor=cyan           % color of external links
+    urlcolor=cyan,          % color of external links
+    breaklinks=true
+}
 \ifthenelse{\boolean{PrintVersion}}{   % for improved print quality, change some hyperref options
 …
 % \usepackage[acronym]{glossaries}
 \usepackage[automake,toc,abbreviations]{glossaries-extra} % Exception to the rule of hyperref being the last add-on package
+\renewcommand*{\glstextformat}[1]{\textcolor{black}{#1}}
 % If glossaries-extra is not in your LaTeX distribution, get it from CTAN (http://ctan.org/pkg/glossaries-extra),
 % although it's supposed to be in both the TeX Live and MikTeX distributions. There are also documentation and

Context Navigation

Legend:

doc/theses/colby_parsons_MMAth/Makefile

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/balance.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/dynamic.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/executor.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/matrix.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/repeat.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/static.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/plotData.py

doc/theses/colby_parsons_MMAth/benchmarks/channels/plotData.py

doc/theses/colby_parsons_MMAth/benchmarks/mutex_stmt/plotData.py

doc/theses/colby_parsons_MMAth/code/basic_actor_example.cfa

doc/theses/colby_parsons_MMAth/glossary.tex

doc/theses/colby_parsons_MMAth/local.bib

doc/theses/colby_parsons_MMAth/style/style.tex

doc/theses/colby_parsons_MMAth/text/channels.tex

doc/theses/colby_parsons_MMAth/text/waituntil.tex

doc/theses/colby_parsons_MMAth/thesis.tex

Download in other formats: