source: doc/theses/colby_parsons_MMAth/text/channels.tex @ 44198fb9

Last change on this file since 44198fb9 was 44198fb9, checked in by Peter A. Buhr <pabuhr@…>, 6 months ago

second proofread of channels chapter

  • Property mode set to 100644
File size: 28.7 KB
1% ======================================================================
2% ======================================================================
4% ======================================================================
5% ======================================================================
7Most modern concurrent programming languages do not subscribe to just one style of communication among threads and provide features that support multiple approaches.
8Channels 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).
9This model is an alternative to shared-memory concurrency, where threads communicate directly by changing shared state.
11Channels were first introduced by Kahn~\cite{Kahn74} and extended by Hoare~\cite{Hoare78} (CSP).
12Both papers present a pseudo (unimplemented) concurrent language where processes communicate using input/output channels to send data.
13Both languages are highly restrictive.
14Kahn'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.
15Hoare'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.
16These channel semantics remove the ability to have an anonymous sender or receiver.
17Additionally all channel operations in CSP are synchronous (no buffering).
18Advanced 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.
19It was the popularity of Go channels that lead to their implementation in \CFA.
20Neither Go nor \CFA channels have the restrictions of the early channel-based concurrent systems.
22\section{Producer-Consumer Problem}
23A channel is an abstraction for a shared-memory buffer, which turns the implementation of a channel into the producer-consumer problem.
24The producer-consumer problem, also known as the bounded-buffer problem, was introduced by Dijkstra~\cite[\S~4.1]{Dijkstra65}.
25In 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.
26In 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).
27As well, a buffer needs protection from concurrent access by multiple producers or consumers attempting to insert or remove simultaneously (MX).
29\section{Channel Size}\label{s:ChannelSize}
30Channels come in three flavours of buffers:
33Zero sized implies the communication is synchronous, \ie the producer must wait for the consumer to arrive or vice versa for a value to be communicated.
35Fixed sized (bounded) implies the communication is asynchronous, \ie the producer can proceed up to the buffer size and vice versa for the consumer with respect to removal.
37Infinite sized (unbounded) implies the communication is asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty.
38Since memory is finite, all unbounded buffers are ultimately bounded;
39this restriction must be part of its implementation.
42In general, the order values are processed by the consumer does not affect the correctness of the producer-consumer problem.
43For example, the buffer can be LIFO, FIFO, or prioritized with respect to insertion and removal.
44However, like MX, a buffer should ensure every value is eventually removed after some reasonable bounded time (no long-term starvation).
45The simplest way to prevent starvation is to implement the buffer as a queue, either with a cyclic array or linked nodes.
47\section{First-Come First-Served}
48As pointed out, a bounded buffer requires MX among multiple producers or consumers.
49This MX should be fair among threads, independent of the FIFO buffer being fair among values.
50Fairness among threads is called \gls{fcfs} and was defined by Lamport~\cite[p.~454]{Lamport74}.
51\gls{fcfs} is defined in relation to a doorway~\cite[p.~330]{Lamport86II}, which is the point at which an ordering among threads can be established.
52Given this doorway, a CS is said to be \gls{fcfs}, if threads access the shared resource in the order they proceed through the doorway.
53A consequence of \gls{fcfs} execution is the elimination of \Newterm{barging}, where barging means a thread arrives at a CS with waiting threads, and the MX protecting the CS allows the arriving thread to enter the CS ahead of one or more of the waiting threads.
55\gls{fcfs} is a fairness property that prevents unequal access to the shared resource and prevents starvation, however it comes at a cost.
56Implementing 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.
57An 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).
58As such, algorithms that are not \gls{fcfs} (barging) can be more performant by skipping the wait for the CS and entering directly;
59however, this performance gain comes by introducing unfairness with possible starvation for waiting threads.
61\section{Channel Implementation}
62Currently, only the Go programming language provides user-level threading where the primary communication mechanism is channels.
63Experiments were conducted that varied the producer-consumer algorithm and lock type used inside the channel.
64With 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.
65Performance of channels can be improved by sharding the underlying buffer \cite{Dice11}.
66However, the FIFO property is lost, which is undesirable for user-facing channels.
67Therefore, the low-level channel implementation in \CFA is largely copied from the Go implementation, but adapted to the \CFA type and runtime systems.
68As such the research contributions added by \CFA's channel implementation lie in the realm of safety and productivity features.
70The Go channel implementation utilizes cooperation among threads to achieve good performance~\cite{go:chan}.
71This cooperation only occurs when producers or consumers need to block due to the buffer being full or empty.
72In 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;
73\ie the blocking thread has no work to perform after it unblocks because the signalling threads has done this work.
74This approach is similar to wait morphing for locks~\cite[p.~82]{Butenhof97} and improves performance in a few ways.
75First, each thread interacting with the channel only acquires and releases the internal channel lock once.
76As a result, contention on the internal lock is decreased, threads only compete for the lock upon entry, as unblocking threads do not reacquire the lock.
77The other advantage of Go's wait-morphing approach is that it eliminates the bottleneck of waiting for signalled threads to run.
78Note, the property of acquiring/releasing the lock only once can also be achieved with a different form of cooperation, called \Newterm{baton passing}.
79Baton 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.
80The baton-passing approach has threads cooperate to pass mutual exclusion without additional lock acquires or releases;
81the 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.
82While baton passing is useful in some algorithms, it results in worse channel performance than the Go approach.
83In 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;
84in 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.
86In this work, all channel sizes \see{Sections~\ref{s:ChannelSize}} are implemented with bounded buffers.
87However, only non-zero-sized buffers are analysed because of their complexity and higher usage.
89\section{Safety and Productivity}
90Channels in \CFA come with safety and productivity features to aid users.
91The features include the following.
94\item Toggle-able statistic collection on channel behaviour that count channel and blocking operations.
95Tracking blocking operations helps illustrate usage for tuning the channel size, where the aim is to reduce blocking.
97\item Deadlock detection on channel deallocation.
98If threads are blocked inside a channel when it terminates, this case is detected and the user is informed, as this can cause a deadlock.
100\item A @flush@ routine that delivers copies of an element to all waiting consumers, flushing the buffer.
101Programmers use this mechanism to broadcast a sentinel value to multiple consumers.
102Additionally, 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.
105\subsection{Toggle-able Statistics}
106As discussed, a channel is a concurrent layer over a bounded buffer.
107To achieve efficient buffering, users should aim for as few blocking operations on a channel as possible.
108Mechanisms to reduce blocking are: change the buffer size, shard a channel into multiple channels, or tweak the number of producer and consumer threads.
109For users to be able to make informed decisions when tuning channel usage, toggle-able channel statistics are provided.
110The statistics are toggled on during the \CFA build by defining the @CHAN_STATS@ macro, which guarantees zero cost when not using this feature.
111When statistics are turned on, four counters are maintained per channel, two for inserting (producers) and two for removing (consumers).
112The two counters per type of operation track the number of blocking operations and total operations.
113In the channel destructor, the counters are printed out aggregated and also per type of operation.
114An example use case is noting that producer inserts are blocking often while consumer removes do not block often.
115This information can be used to increase the number of consumers to decrease the blocking producer operations, thus increasing the channel throughput.
116Whereas, increasing the channel size in this scenario is unlikely to produce a benefit because the consumers can never keep up with the producers.
118\subsection{Deadlock Detection}
119The deadlock detection in the \CFA channels is fairly basic but detects a very common channel mistake during termination.
120That is, it detects the case where threads are blocked on the channel during channel deallocation.
121This case is guaranteed to deadlock since there are no producer threads to supply values needed by the waiting consumer threads.
122Only if a user maintained a separate reference to the consumer threads and manually unblocks them outside the channel could the deadlock be avoid.
123However, without special consumer semantics, this unblocking would generate other runtime errors where the consumer attempts to access non-existing channel data or even a deallocated channel.
124More robust deadlock detection needs to be implemented separate from channels since it requires knowledge about the threading system and other channel/thread state.
126\subsection{Program Shutdown}
127Terminating concurrent programs is often one of the most difficult parts of writing concurrent code, particularly if graceful termination is needed.
128The difficulty for graceful termination often arises from the usage of synchronization primitives that need to be handled carefully during shutdown.
129It is easy to deadlock during termination if threads are left behind on synchronization primitives.
130Additionally, 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.
131\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.
132Channels are a particularly hard synchronization primitive to terminate since both sending and receiving to/from a channel can block.
133Thus, 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.
135\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.
136The \Go{select} statement is discussed in \ref{s:waituntil}, where \CFA's @waituntil@ statement is compared with the Go \Go{select} statement.
138The @close@ operation on a channel in Go changes the state of the channel.
139When a channel is closed, sends to the channel panic along with additional calls to @close@.
140Receives are handled differently.
141Receivers (consumers) never block on a closed channel and continue to remove elements from the channel.
142Once a channel is empty, receivers can continue to remove elements, but receive the zero-value version of the element type.
143To avoid unwanted zero-value elements, Go provides the ability to iterate over a closed channel to remove the remaining elements.
144These 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.
145These 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.
146If errors need to occur in Go, return codes are used to pass error information up call levels.
147Note, panics in Go can be caught, but it is not the idiomatic way to write Go programs.
149While 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.
150Since 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.
151However, 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.
152This 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.
153To 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.
154Hence, due to Go's asymmetric approach to channel shutdown, separate synchronization between producers and consumers of a channel has to occur during shutdown.
156\paragraph{\CFA channels} have access to an extensive exception handling mechanism~\cite{Beach21}.
157As such \CFA uses an exception-based approach to channel shutdown that is symmetric for both producers and consumers, and supports graceful shutdown.
159Exceptions in \CFA support both termination and resumption.
160\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.
161\Newterm{Resumption exception}s perform a dynamic call that does not unwind the stack allowing the exception handler to return to the raise point.
162In \CFA, if a resumption exception is not handled, it is reraised as a termination exception.
163This mechanism is used to create a flexible and robust termination system for channels.
165When a channel in \CFA is closed, all subsequent calls to the channel raise a resumption exception at the caller.
166If the resumption is handled, the caller attempts to complete the channel operation.
167However, if the channel operation would block, a termination exception is thrown.
168If the resumption is not handled, the exception is rethrown as a termination.
169These termination exceptions allow for non-local transfer that is used to great effect to eagerly and gracefully shut down a thread.
170When 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.
171The resumption exception, @channel_closed@, has internal fields to aid in handling the exception.
172The exception contains a pointer to the channel it is thrown from and a pointer to a buffer element.
173For exceptions thrown from @remove@, the buffer element pointer is null.
174For exceptions thrown from @insert@, the element pointer points to the buffer element that the thread attempted to insert.
175This 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.
176Furthermore, due to \CFA's powerful exception system, this data can be used to choose handlers based on which channel and operation failed.
177For 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.
178It is worth mentioning that using exceptions for termination may incur a larger performance cost than the Go approach.
179However, this should not be an issue, since termination is rarely on the fast-path of an application.
180In contrast, ensuring termination can be easily implemented correctly is the aim of the exception approach.
182\section{\CFA / Go channel Examples}
183To highlight the differences between \CFA's and Go's close semantics, three examples are presented.
184The first example is a simple shutdown case, where there are producer threads and consumer threads operating on a channel for a fixed duration.
185Once the duration ends, producers and consumers terminate immediately leaving unprocessed elements in the channel.
186The second example extends the first by requiring the channel to be empty after shutdown.
187Both the first and second example are shown in Figure~\ref{f:ChannelTermination}.
194var channel chan int = make( chan int, 128 )
195var prodJoin chan int = make( chan int, 4 )
196var consJoin chan int = make( chan int, 4 )
197var cons_done, prod_done bool = false, false;
198func producer() {
199        for {
200                if prod_done { break }
201                channel <- 5
202        }
203        prodJoin <- 0 // synch with main thd
206func consumer() {
207        for {
208                if cons_done { break }
209                <- channel
210        }
211        consJoin <- 0 // synch with main thd
215func main() {
216        for j := 0; j < 4; j++ { go consumer() }
217        for j := 0; j < 4; j++ { go producer() }
218        time.Sleep( time.Second * 10 )
219        prod_done = true
220        for j := 0; j < 4 ; j++ { <- prodJoin }
221        cons_done = true
222        close(channel) // ensure no cons deadlock
223        @for elem := range channel {@
224                // process leftover values
225        @}@
226        for j := 0; j < 4; j++ { <- consJoin }
233channel( size_t ) chan{ 128 };
234thread Consumer {};
235thread Producer {};
237void main( Producer & this ) {
238        try {
239                for ()
240                        insert( chan, 5 );
241        } catch( channel_closed * ) {
242                // unhandled resume or full
243        }
245void main( Consumer & this ) {
246        try {
247                for () { int i = remove( chan ); }
248        @} catchResume( channel_closed * ) {@
249                // handled resume => consume from chan
250        } catch( channel_closed * ) {
251                // empty or unhandled resume
252        }
254int main() {
255        Consumer c[4];
256        Producer p[4];
257        sleep( 10`s );
258        close( chan );
270\subfloat[Go style]{\label{l:go_chan_term}\usebox\myboxA}
274\subfloat[\CFA style]{\label{l:cfa_chan_term}\usebox\myboxB}
275\caption{Channel Termination Examples 1 and 2. Code specific to example 2 is highlighted.}
279Figure~\ref{l:go_chan_term} shows the Go solution.
280Since some of the elements being passed through the channel are zero-valued, closing the channel in Go does not aid in communicating shutdown.
281Instead, a different mechanism to communicate with the consumers and producers needs to be used.
282Flag 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.
283Hence, the two flags @cons_done@ and @prod_done@ are used to communicate with the producers and consumers, respectively.
284Furthermore, producers and consumers need separate shutdown channels so 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.
285The producer flag is set first;
286then after all producers terminate, the consumer flag is set and the channel is closed leaving elements in the buffer.
287To purge the buffer, a loop is added (red) that iterates over the closed channel to process any remaining values.
289Figure~\ref{l:cfa_chan_term} shows the \CFA solution.
290Here, shutdown is communicated directly to both producers and consumers via the @close@ call.
291A @Producer@ thread knows to stop producing when the @insert@ call on a closed channel raises exception @channel_closed@.
292If 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.
293If a @Consumer@ thread handles the resumptions exceptions (red), control returns to complete the remove.
294A @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@.
295The \CFA semantics allow users to communicate channel shutdown directly through the channel, without having to share extra state between threads.
296Additionally, 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.
298Figure~\ref{f:ChannelBarrierTermination} shows a final shutdown example using channels to implement a barrier.
299A Go and \CFA style solution are presented but both are implemented using \CFA syntax so they can be easily compared.
300Implementing a barrier is interesting because threads are both producers and consumers on the barrier-internal channels, @entryWait@ and @barWait@.
301The 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.
302After @entryWait@ is empty, arriving threads block when removing from @entryWait@.
303However, the arriving threads that entered the barrier cannot leave the barrier until $N$ threads have arrived.
304Hence, the entering threads block on the @barWait@ channel until the $N$th arriving thread inserts $N-1$ elements into @barWait@ to unblock the $N-1$ threads calling @remove@ on the @barWait@ channel.
305The race between these arriving threads blocking on @barWait@ and the $N$th thread inserting values into @barWait@ does not affect correctness;
306\ie an arriving thread may or may not block on channel @barWait@ to get its value.
308Now, the two channels makes termination synchronization between producers and consumers difficult.
309Interestingly, the shutdown details for this problem are also applicable to other problems with threads producing and consuming from the same channel.
310The 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.
311As 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.
312This sentinel value has to be checked at two points along the fast-path and sentinel values daisy-chained into the buffers.
313Furthermore, an additional flag @done@ is needed to communicate to threads once they have left the barrier that they are done.
314Also 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.
315For 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.
316This 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.
323struct barrier {
324        channel( int ) barWait, entryWait;
325        int size;
327void ?{}( barrier & this, int size ) with(this) {
328        barWait{size + 1};   entryWait{size + 1};
329        this.size = size;
330        for ( i; size )
331                insert( entryWait, i );
333void wait( barrier & this ) with(this) {
334        int ticket = remove( entryWait );
335        @if ( ticket == -1 ) { insert( entryWait, -1 ); return; }@
336        if ( ticket == size - 1 ) {
337                for ( i; size - 1 )
338                        insert( barWait, i );
339                return;
340        }
341        ticket = remove( barWait );
342        @if ( ticket == -1 ) { insert( barWait, -1 ); return; }@
343        if ( size == 1 || ticket == size - 2 ) { // last ?
344                for ( i; size )
345                        insert( entryWait, i );
346        }
348void flush(barrier & this) with(this) {
349        @insert( entryWait, -1 );   insert( barWait, -1 );@
351enum { Threads = 4 };
352barrier b{Threads};
353@bool done = false;@
354thread Thread {};
355void main( Thread & this ) {
356        for () {
357          @if ( done ) break;@
358                wait( b );
359        }
361int main() {
362        Thread t[Threads];
363        sleep(10`s);
364        done = true;
365        flush( b );
366} // wait for threads to terminate
372struct barrier {
373        channel( int ) barWait, entryWait;
374        int size;
376void ?{}( barrier & this, int size ) with(this) {
377        barWait{size};   entryWait{size};
378        this.size = size;
379        for ( i; size )
380                insert( entryWait, i );
382void wait( barrier & this ) with(this) {
383        int ticket = remove( entryWait );
385        if ( ticket == size - 1 ) {
386                for ( i; size - 1 )
387                        insert( barWait, i );
388                return;
389        }
390        ticket = remove( barWait );
392        if ( size == 1 || ticket == size - 2 ) { // last ?
393                for ( i; size )
394                        insert( entryWait, i );
395        }
397void flush(barrier & this) with(this) {
398        @close( barWait );   close( entryWait );@
400enum { Threads = 4 };
401barrier b{Threads};
403thread Thread {};
404void main( Thread & this ) {
405        @try {@
406                for ()
407                        wait( b );
408        @} catch ( channel_closed * ) {}@
410int main() {
411        Thread t[Threads];
412        sleep(10`s);
414        flush( b );
415} // wait for threads to terminate
419\subfloat[Go style]{\label{l:go_chan_bar}\usebox\myboxA}
423\subfloat[\CFA style]{\label{l:cfa_chan_bar}\usebox\myboxB}
424\caption{Channel Barrier Termination}
430Given 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.
431The microbenchmark for the channel comparison is similar to Figure~\ref{f:ChannelTermination}, where the number of threads and processors is set from the command line.
432The processors are divided equally between producers and consumers, with one producer or consumer owning each core.
433The number of cores is varied to measure how throughput scales.
435The results of the benchmark are shown in Figure~\ref{f:chanPerf}.
436The performance of Go and \CFA channels on this microbenchmark is comparable.
437Note, 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.
440        \centering
441        \subfloat[AMD \CFA Channel Benchmark]{
442                \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Channel_Contention.pgf}}
443                \label{f:chanAMD}
444        }
445        \subfloat[Intel \CFA Channel Benchmark]{
446                \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Channel_Contention.pgf}}
447                \label{f:chanIntel}
448        }
449        \caption{The channel contention benchmark comparing \CFA and Go channel throughput (higher is better).}
450        \label{f:chanPerf}
453% Local Variables: %
454% tab-width: 4 %
455% End: %
Note: See TracBrowser for help on using the repository browser.