Index: doc/theses/colby_parsons_MMAth/text/channels.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/channels.tex (revision 84018e0cc39d93f27dd029c87859f0a8717d0b83) +++ doc/theses/colby_parsons_MMAth/text/channels.tex (revision 9f1beb43e8680e0e88365670c20430e1f307fb1b) @@ -7,5 +7,5 @@ Most modern concurrent programming languages do not subscribe to just one style of communication among threads and provide features that support multiple approaches. Channels are a concurrent-language feature used to perform \Newterm{message-passing concurrency}: a model of concurrency where threads communicate by sending data as messages (mostly non\-blocking) and synchronizing by receiving sent messages (blocking). -This model is an alternative to shared-memory concurrency, where threads can communicate directly by changing shared state. +This model is an alternative to shared-memory concurrency, where threads communicate directly by changing shared state. Channels were first introduced by Kahn~\cite{Kahn74} and extended by Hoare~\cite{Hoare78} (CSP). @@ -13,9 +13,10 @@ Both languages are highly restrictive. Kahn's language restricts a reading process to only wait for data on a single channel at a time and different writing processes cannot send data on the same channel. -Hoare's language restricts channels such that both the sender and receiver need to explicitly name the process that is destination of a channel send or the source of a channel receive. -These channel semantics remove the ability to have an anonymous sender or receiver and additionally all channel operations in CSP are synchronous (no buffering). -Channels as a programming language feature has been popularized in recent years by the language Go, which encourages the use of channels as its fundamental concurrent feature. -Go's restrictions are ... \CAP{The only restrictions in Go but not CFA that I can think of are the closing semantics and the functionality of select vs. waituntil. Is that worth mentioning here or should it be discussed later?} -\CFA channels do not have these restrictions. +Hoare's language restricts both the sender and receiver to explicitly name the process that is the destination of a channel send or the source of a channel receive. +These channel semantics remove the ability to have an anonymous sender or receiver. +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 me to implement them in \CFA. +Neither Go nor \CFA channels have the restrictions in early channel-based concurrent systems. \section{Producer-Consumer Problem} @@ -24,6 +25,7 @@ In the problem, threads interact with a buffer in two ways: producing threads insert values into the buffer and consuming threads remove values from the buffer. In general, a buffer needs protection to ensure a producer only inserts into a non-full buffer and a consumer only removes from a non-empty buffer (synchronization). -As well, a buffer needs protection from concurrent access by multiple producers or consumers attempt to insert or remove simultaneously (MX). - +As well, a buffer needs protection from concurrent access by multiple producers or consumers attempting to insert or remove simultaneously (MX). + +\section{Channel Size}\label{s:ChannelSize} Channels come in three flavours of buffers: \begin{enumerate} @@ -52,5 +54,5 @@ \gls{fcfs} is a fairness property that prevents unequal access to the shared resource and prevents starvation, however it comes at a cost. -Implementing an algorithm with \gls{fcfs} can lead to double blocking, where arriving threads block outside the doorway waiting for a thread in the lock entry-protocol and inside the doorway waiting for a thread in the CS. +Implementing an algorithm with \gls{fcfs} can lead to \Newterm{double blocking}, where arriving threads block outside the doorway waiting for a thread in the lock entry-protocol and inside the doorway waiting for a thread in the CS. An analogue is boarding an airplane: first you wait to get through security to the departure gates (short term), and then wait again at the departure gate for the airplane (long term). As such, algorithms that are not \gls{fcfs} (barging) can be more performant by skipping the wait for the CS and entering directly; @@ -58,5 +60,5 @@ \section{Channel Implementation} -Currently, only the Go programming language~\cite{Go} provides user-level threading where the primary communication mechanism is channels. +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. With the exception of non-\gls{fcfs} 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. @@ -66,6 +68,6 @@ \PAB{Discuss the Go channel implementation. Need to tie in FIFO buffer and FCFS locking.} -In this work, all channels are implemented with bounded buffers, so there is no zero-sized buffering. -\CAP{I do have zero size channels implemented, however I don't focus on them since I think they are uninteresting as they are just a thin layer over binary semaphores. Should I mention that I support it but omit discussion or just leave it out?} +In this work, all channel sizes \see{Sections~\ref{s:ChannelSize}} are implemented with bounded buffers. +However, only non-zero-sized buffers are analysed because of their complexity and higher usage. \section{Safety and Productivity} @@ -75,57 +77,67 @@ \begin{itemize} \item Toggle-able statistic collection on channel behaviour that count channel and blocking operations. -Tracking blocking operations helps illustrate usage and then tune the channel size, where the aim is to reduce blocking. -\item Deadlock detection on deallocation of the channel. -If threads are blocked inside the channel when it terminates, this case is detected and the user is informed, as this can cause a deadlock. +Tracking blocking operations helps illustrate usage for tuning the channel size, where the aim is to reduce blocking. + +\item Deadlock detection on channel deallocation. +If threads are blocked inside a channel when it terminates, this case is detected and the user is informed, as this can cause a deadlock. + \item A @flush@ routine that delivers copies of an element to all waiting consumers, flushing the buffer. -Programmers can use this to easily to broadcast data to multiple consumers. +Programmers use this mechanism to broadcast a sentinel value to multiple consumers. Additionally, the @flush@ routine is more performant then looping around the @insert@ operation since it can deliver the elements without having to reacquire mutual exclusion for each element sent. \end{itemize} -The other safety and productivity feature of \CFA channels deals with concurrent termination. +\subsection{Toggle-able Statistics} +\PAB{Discuss toggle-able statistics.} + + +\subsection{Deadlock Detection} +\PAB{Discuss deadlock detection.} + +\subsection{Program Shutdown} +% The other safety and productivity feature of \CFA channels deals with concurrent termination. 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 which need to be handled carefully during shutdown. +The difficulty of graceful termination often arises from the usage of 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 off a channel can block. +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. % C_TODO: add reference to select chapter, add citation to go channels info -Go channels provide a set of tools to help with concurrent shutdown. +\paragraph{Go channels} provide a set of tools to help with concurrent shutdown. Channels in Go have a @close@ operation and a \Go{select} statement that both can be used to help threads terminate. -The \Go{select} statement will be discussed in \ref{}, where \CFA's @waituntil@ statement will be compared with the Go \Go{select} statement. +The \Go{select} statement is discussed in \ref{waituntil}, where \CFA's @waituntil@ statement is compared with the Go \Go{select} statement. + The @close@ operation on a channel in Go changes the state of the channel. -When a channel is closed, sends to the channel will panic and additional calls to @close@ will panic. -Receives are handled differently where receivers will never block on a closed channel and will continue to remove elements from the channel. -Once a channel is empty, receivers can continue to remove elements, but will receive the zero-value version of the element type. -To aid in avoiding unwanted zero-value elements, Go provides the ability to iterate over a closed channel to remove the remaining elements. -These design choices for Go channels enforce a specific interaction style with channels during termination, where careful thought is needed to ensure that additional @close@ calls don't occur and that no sends occur after channels are closed. +When a channel is closed, sends to the channel panic along with additional calls to @close@. +Receives are handled differently where receivers never block on a closed channel and continue to remove elements from the channel. +Once a channel is empty, receivers can continue to remove elements, but receive the zero-value version of the element type. +To avoid unwanted zero-value elements, Go provides the ability to iterate over a closed channel to remove the remaining elements. +These Go design choices enforce a specific interaction style with channels during termination: careful thought is needed to ensure additional @close@ calls do not occur and no sends occur after a channel is closed. These design choices fit Go's paradigm of error management, where users are expected to explicitly check for errors, rather than letting errors occur and catching them. -If errors need to occur in Go, return codes are used to pass error information where they are needed. -Note that panics in Go can be caught, but it is not considered an idiomatic way to write Go programs. +If errors need to occur in Go, return codes are used to pass error information up call levels. +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. -Since both closing and sending panic, once a channel is closed, a user often has to synchronize the senders to a channel 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 that receivers no longer block on the channel, and will receive zero-valued elements. -This can be useful if the zero-typed element is recognized as a sentinel value, but if another sentinel value is preferred, then @close@ only provides its non-blocking feature. +Since both closing and sending panic once a channel is closed, a user often has to synchronize the senders to a channel 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. -In \CFA, exception handling is an encouraged paradigm and has full language support \cite{Beach21}. -As such \CFA uses an exception based approach to channel shutdown that is symmetric for both producers and consumers, and supports graceful shutdown.Exceptions in \CFA support both termination and resumption.Termination exceptions operate in the same way as exceptions seen in many popular programming languages such as \CC, Python and Java. -Resumption exceptions are a style of exception that when caught run the corresponding catch block in the same way that termination exceptions do. -The difference between the exception handling mechanisms arises after the exception is handled. -In termination handling, the control flow continues into the code following the catch after the exception is handled. -In resumption handling, the control flow returns to the site of the @throw@, allowing the control to continue where it left off. -Note that in resumption, since control can return to the point of error propagation, the stack is not unwound during resumption propagation. -In \CFA if a resumption is not handled, it is reraised as a termination. -This mechanism can be used to create a flexible and robust termination system for channels. - -When a channel in \CFA is closed, all subsequent calls to the channel will throw a resumption exception at the caller. -If the resumption is handled, then the caller will proceed to attempt to complete their operation. -If the resumption is not handled it is then rethrown as a termination exception. -Or, if the resumption is handled, but the subsequent attempt at an operation would block, a termination exception is thrown. -These termination exceptions allow for non-local transfer that can be used to great effect to eagerly and gracefully shut down a thread. +\paragraph{\CFA channels} have access to an extensive exception handling mechanism~\cite{Beach21}. +As such \CFA uses an exception-based approach to channel shutdown that is symmetric for both producers and consumers, and supports graceful shutdown. + +Exceptions in \CFA support both termination and resumption. +\Newterm{Termination exception}s perform a dynamic call that unwinds the stack preventing the exception handler from returning to the raise point, such as in \CC, Python and Java. +\Newterm{Resumption exception}s perform a dynamic call that does not unwind the stack allowing the exception handler to return to the raise point. +In \CFA, if a resumption exception is not handled, it is reraised as a termination exception. +This mechanism is used to create a flexible and robust termination system for channels. + +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. +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. @@ -139,10 +151,11 @@ 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. +\section{\CFA / Go channel Examples} To highlight the differences between \CFA's and Go's close semantics, an example program is presented. -The program is a barrier implemented using two channels shown in Listings~\ref{l:cfa_chan_bar} and \ref{l:go_chan_bar}. +The program is a barrier implemented using two channels shown in Figure~\ref{f:ChannelBarrierTermination}. Both of these examples are implemented using \CFA syntax so that they can be easily compared. -Listing~\ref{l:go_chan_bar} uses go-style channel close semantics and Listing~\ref{l:cfa_chan_bar} uses \CFA close semantics. -In this problem it is infeasible to use the Go @close@ call since all tasks are both potentially producers and consumers, causing panics on close to be unavoidable. -As such in Listing~\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. +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 problem 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. +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. Furthermore, an additional flag @done@ is needed to communicate to threads once they have left the barrier that they are done. @@ -152,165 +165,147 @@ 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{cfa}[caption={\CFA channel barrier termination},label={l:cfa_chan_bar}] +\begin{figure} +\centering + +\begin{lrbox}{\myboxA} +\begin{cfa}[aboveskip=0pt,belowskip=0pt] struct barrier { - channel( int ) barWait; - channel( int ) entryWait; + channel( int ) barWait, entryWait; int size; -} -void ?{}(barrier & this, int size) with(this) { - barWait{size}; - entryWait{size}; +}; +void ?{}( barrier & this, int size ) with(this) { + barWait{size}; entryWait{size}; this.size = size; - for ( j; size ) - insert( *entryWait, j ); -} - + for ( i; size ) + insert( entryWait, i ); +} +void wait( barrier & this ) with(this) { + int ticket = remove( entryWait ); + + if ( ticket == size - 1 ) { + for ( i; size - 1 ) + insert( barWait, i ); + return; + } + ticket = remove( barWait ); + + if ( size == 1 || ticket == size - 2 ) { // last ? + for ( i; size ) + insert( entryWait, i ); + } +} void flush(barrier & this) with(this) { - close(barWait); - close(entryWait); -} -void wait(barrier & this) with(this) { - int ticket = remove( *entryWait ); + @close( barWait ); close( entryWait );@ +} +enum { Threads = 4 }; +barrier b{Threads}; + +thread Thread {}; +void main( Thread & this ) { + @try {@ + for () + wait( b ); + @} catch ( channel_closed * ) {}@ +} +int main() { + Thread t[Threads]; + sleep(10`s); + + flush( b ); +} // wait for threads to terminate +\end{cfa} +\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 ( j; size - 1 ) - insert( *barWait, j ); + for ( i; size - 1 ) + insert( barWait, i ); return; } - ticket = remove( *barWait ); - - // last one out - if ( size == 1 || ticket == size - 2 ) { - for ( j; size ) - insert( *entryWait, j ); - } -} -barrier b{Tasks}; - -// thread main -void main(Task & this) { - try { - for ( ;; ) { - wait( b ); - } - } catch ( channel_closed * e ) {} -} - + 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() { - { - Task t[Tasks]; - - sleep(10`s); - flush( b ); - } // wait for tasks to terminate - return 0; -} + Thread t[Threads]; + sleep(10`s); + done = true; + flush( b ); +} // wait for threads to terminate \end{cfa} - -\begin{cfa}[caption={Go channel barrier termination},label={l:go_chan_bar}] - -struct barrier { - channel( int ) barWait; - channel( int ) entryWait; - int size; -} -void ?{}(barrier & this, int size) with(this) { - barWait{size + 1}; - entryWait{size + 1}; - this.size = size; - for ( j; size ) - insert( *entryWait, j ); -} - -void flush(barrier & this) with(this) { - insert( *entryWait, -1 ); - insert( *barWait, -1 ); -} -void wait(barrier & this) with(this) { - int ticket = remove( *entryWait ); - if ( ticket == -1 ) { - insert( *entryWait, -1 ); - return; - } - if ( ticket == size - 1 ) { - for ( j; size - 1 ) - insert( *barWait, j ); - return; - } - ticket = remove( *barWait ); - if ( ticket == -1 ) { - insert( *barWait, -1 ); - return; - } - - // last one out - if ( size == 1 || ticket == size - 2 ) { - for ( j; size ) - insert( *entryWait, j ); - } -} -barrier b; - -bool done = false; -// thread main -void main(Task & this) { - for ( ;; ) { - if ( done ) break; - wait( b ); - } -} - -int main() { - { - Task t[Tasks]; - - sleep(10`s); - done = true; - - flush( b ); - } // wait for tasks to terminate - return 0; -} -\end{cfa} - -In Listing~\ref{l:cfa_resume} an example of channel closing with resumption is used. -This program uses resumption in the @Consumer@ thread main to ensure that all elements in the channel are removed before the consumer thread terminates. -The producer only has a @catch@ so the moment it receives an exception it terminates, whereas the consumer will continue to remove from the closed channel via handling resumptions until the buffer is empty, which then throws a termination exception. -If the same program was implemented in Go it would require explicit synchronization with both producers and consumers by some mechanism outside the channel to ensure that all elements were removed before task termination. +\end{lrbox} + +\subfloat[\CFA style]{\label{l:cfa_chan_bar}\usebox\myboxA} +\hspace*{3pt} +\vrule +\hspace*{3pt} +\subfloat[Go style]{\label{l:go_chan_bar}\usebox\myboxB} +\caption{Channel Barrier Termination} +\label{f:ChannelBarrierTermination} +\end{figure} + +Listing~\ref{l:cfa_resume} is an example of a channel closing with resumption. +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 @removed@ would block is a termination exception raised to stop consuming. +The same program in Go would require explicit synchronization among producers and consumers by a mechanism outside the channel to ensure all elements are removed before threads terminate. \begin{cfa}[caption={\CFA channel resumption usage},label={l:cfa_resume}] channel( int ) chan{ 128 }; - -// Consumer thread main -void main(Consumer & this) { +thread Producer {}; +void main( Producer & this ) { + @try {@ + for ( i; 0~$@$ ) + insert( chan, i ); + @} catch( channel_closed * ) {}@ $\C[3in]{// channel closed}$ +} +thread Consumer {}; +void main( Consumer & this ) { size_t runs = 0; - try { - for ( ;; ) { - remove( chan ); + @try {@ + for () { + int i = remove( chan ); } - } catchResume ( channel_closed * e ) {} - catch ( channel_closed * e ) {} -} - -// Producer thread main -void main(Producer & this) { - int j = 0; - try { - for ( ;;j++ ) { - insert( chan, j ); - } - } catch ( channel_closed * e ) {} -} - -int main( int argc, char * argv[] ) { - { - Consumers c[4]; - Producer p[4]; - - sleep(10`s); - - for ( i; Channels ) - close( channels[i] ); - } - return 0; + @} catchResume( channel_closed * ) {}@ $\C{// remaining item in buffer \(\Rightarrow\) remove it}$ + @catch( channel_closed * ) {}@ $\C{// blocking call to remove \(\Rightarrow\) buffer empty}$ +} +int main() { + enum { Processors = 8 }; + processor p[Processors - 1]; $\C{// one processor per thread, have one processor}$ + Consumer c[Processors / 2]; $\C{// share processors}$ + Producer p[Processors / 2]; + sleep( 10`s ); + @close( chan );@ $\C{// stop producer and consumer}\CRT$ } \end{cfa} @@ -318,13 +313,12 @@ \section{Performance} -Given that the base implementation of the \CFA channels is very similar to the Go implementation, this section aims to show that the performance of the two implementations are comparable. -One microbenchmark is conducted to compare Go and \CFA. -The benchmark is a ten second experiment where producers and consumers operate on a channel in parallel and throughput is measured. +Given that the base implementation of the \CFA channels is very similar to the Go implementation, this section aims to show the performance of the two implementations are comparable. +The microbenchmark for the channel comparison is similar to listing~\ref{l:cfa_resume}, where the number of threads and processors is set from the command line. +The processors are divided equally between producers and consumers, with one producer or consumer owning each core. The number of cores is varied to measure how throughput scales. -The cores are divided equally between producers and consumers, with one producer or consumer owning each core. + The results of the benchmark are shown in Figure~\ref{f:chanPerf}. The performance of Go and \CFA channels on this microbenchmark is comparable. -Note, it is expected for the performance to decline as the number of cores increases as the channel operations all occur in a critical section so an increase in cores results in higher contention with no increase in parallelism. - +Note, the performance should decline as the number of cores increases as the channel operations occur in a critical section, so increasing cores results in higher contention with no increase in parallelism. \begin{figure}