Context Navigation

-                      r3ee8853
+                      r9509d67a
 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}.
+Other popular languages and libraries that provide channels include C++ Boost~\cite{boost:channel}, Rust~\cite{rust:channel}, Haskell~\cite{haskell:channel}, OCaml~\cite{ocaml:channel}, and Kotlin~\cite{kotlin: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.
+Kotlin channels are comparable to Go and \CFA, but unfortunately they were not identified as a comparator until after presentation of this thesis and are omitted due to time constraints.
 \section{Producer-Consumer Problem}
 …
 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 attempting 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, which is often provided by MX.
 \section{Channel Size}\label{s:ChannelSize}
 …
 Fixed sized (bounded) implies the communication is mostly asynchronous, \ie the producer can proceed up to the buffer size and vice versa for the consumer with respect to removal, at which point the producer/consumer would wait.
 \item
+Infinite sized (unbounded) implies the communication is asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty.
+Since memory is finite, all unbounded buffers are ultimately bounded;
+this restriction must be part of its implementation.
+Infinite sized (unbounded) implies the communication is asymmetrically asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty.
 \end{enumerate}
 …
 However, like MX, a buffer should ensure every value is eventually removed after some reasonable bounded time (no long-term starvation).
 The simplest way to prevent starvation is to implement the buffer as a queue, either with a cyclic array or linked nodes.
+While \gls{fifo} is not required for producer-consumer problem correctness, it is a desired property in channels as it provides predictable and often relied upon channel ordering behaviour to users.
 \section{First-Come First-Served}
 As pointed out, a bounded buffer requires MX among multiple producers or consumers.
+As pointed out, a bounded buffer implementation often provides MX among multiple producers or consumers.
 This MX should be fair among threads, independent of the \gls{fifo} buffer being fair among values.
 Fairness among threads is called \gls{fcfs} and was defined by Lamport~\cite[p.~454]{Lamport74}.
 …
 \section{Channel Implementation}\label{s:chan_impl}
 Currently, only the Go and Erlang programming languages provide user-level threading where the primary communication mechanism is channels.
 Both Go and Erlang have user-level threading and preemptive scheduling, and both use channels for communication.
 Go provides multiple homogeneous channels; each have a single associated type.
+The programming languages Go, Kotlin, and Erlang provide user-level threading where the primary communication mechanism is channels.
+These languages have user-level threading and preemptive scheduling, and both use channels for communication.
+Go and Kotlin provide multiple homogeneous channels; each have a single associated type.
 Erlang, which is closely related to actor systems, provides one heterogeneous channel per thread (mailbox) with a typed receive pattern.
 Go encourages users to communicate via channels, but provides them as an optional language feature.
+Go and Kotlin encourage users to communicate via channels, but provides them as an optional language feature.
 On the other hand, Erlang's single heterogeneous channel is a fundamental part of the threading system design; using it is unavoidable.
 Similar to Go, \CFA's channels are offered as an optional language feature.
+Similar to Go and Kotlin, \CFA's channels are offered as an optional language feature.
 While iterating on channel implementation, experiments were conducted that varied the producer-consumer algorithm and lock type used inside the channel.
 …
 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.
+After a producer blocks it must wait for a consumer to signal it and vice versa.
+The consumer or producer that signals a blocked thread is called the signalling thread.
 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.
 …
 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; only entering threads compete for the lock since 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.
+The other advantage of Go's wait-morphing approach is that it eliminates the need to wait for signalled threads to run.
 Note that 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 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 baton-passing approach, all threads need to wait for the signalled thread to unblock 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.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 9509d67a for doc/theses/colby_parsons_MMAth/text/channels.tex

Legend:

doc/theses/colby_parsons_MMAth/text/channels.tex

Download in other formats: