Changeset ca8c91ce for doc/theses

Timestamp:

May 4, 2023, 8:54:17 AM (12 months ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, ast-experimental, master

Children:

cb69fba

Parents:

d5c5586

Message:

small changes to channel chapter

Location:

doc/theses/colby_parsons_MMAth

Files:

• style/style.tex (modified) (1 diff)
• text/channels.tex (modified) (10 diffs)

doc/theses/colby_parsons_MMAth/style/style.tex

@@ -7 +7 @@
 
 \newcommand{\code}[1]{\lstinline[language=CFA]{#1}}
+\newcommand{\Go}[1]{\lstinline[language=Go]{#1}}
 \newcommand{\uC}{$\mu$\CC}
 \newcommand{\PAB}[1]{{\color{red}PAB: #1}}

doc/theses/colby_parsons_MMAth/text/channels.tex

@@ -14 +14 @@
 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 as a programming language feature has been popularized in recent years due to the language Go, which encourages the use of channels as its fundamental concurrent feature.
+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 ...
 \CFA channels do not have these restrictions.
@@ -37 +37 @@
 \end{enumerate}
 
-The order values are processed by the consumer does not affect the correctness of the producer-consumer problem.
+In general, the order values are processed by the consumer does not affect the correctness of the producer-consumer problem.
 For example, the buffer can be LIFO, FIFO, or prioritized with respect to insertion and removal.
 However, like MX, a buffer should ensure every value is eventually removed after some reasonable bounded time (no long-term starvation).
@@ -47 +47 @@
 Fairness among threads is called \gls{fcfs} and was defined by Lamport~\cite[p.~454]{Lamport74}.
 \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.
-Given this doorway, a critical section is said to be \gls{fcfs}, if threads access the shared resource in the order they proceed through the doorway.
-A 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 thread to enter the CS ahead of one or more of the waiting threads.
-
-\gls{fcfs} is a fairness property which prevents unequal access to the shared resource and prevents starvation, however it can come at a cost.
-Implementing an algorithm with \gls{fcfs} can lead to double blocking, where entering threads may need to block to allow other threads to proceed first, resulting in blocking both inside and outside the doorway.
-As such algorithms that are not \gls{fcfs} may be more performant but that performance comes with the downside of likely introducing starvation and unfairness.
+Given this doorway, a CS is said to be \gls{fcfs}, if threads access the shared resource in the order they proceed through the doorway.
+A 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.
+
+\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.
+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;
+however, this performance gain comes by introducing unfairness with possible starvation for waiting threads.
 
 \section{Channel Implementation}
 Currently, only the Go programming language~\cite{Go} provides user-level threading where the primary communication mechanism is channels.
-Furthermore, my analysis Go's channel communication is that it is very performant.
-Therefore, the low-level channel implementation in \CFA is largely copied from the Go implementation, but adapted to the \CFA type and runtime systems.
-A number of alternative implementations were tried in \CFA, but the Go implementation always beat other approaches.
-
-\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.
-
 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.
+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.
+
+\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.
 
 \section{Safety and Productivity}
@@ -72 +71 @@
 
 \begin{itemize}
-\item Toggle-able statistic collection on channel behaviour that counts channel operations, and the number of the operations that block.
-Tracking blocking operations helps users tune their channel size or channel usage when the channel is used for buffering, where the aim is to have as few blocking operations as possible.
+\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 any threads are blocked inside the channel when it terminates it is detected and informs the user, as this would cause a deadlock.
-\item A \code{flush} routine that delivers copies of an element to all waiting consumers, flushing the buffer.
+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.
+\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.
-Additionally, the \code{flush} routine is more performant then looping around the \code{insert} operation since it can deliver the elements without having to reacquire mutual exclusion for each element sent.
+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}
 
@@ -92 +91 @@
 % 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.
-Channels in Go have a \code{close} operation and a \code{select} statement that both can be used to help threads terminate.
-The \code{select} statement will be discussed in \ref{}, where \CFA's \code{waituntil} statement will be compared with the Go \code{select} statement.
-The \code{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 \code{close} will panic.
+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 @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 \code{close} calls don't occur and that no sends occur after channels are closed.
+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.
 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.
@@ -106 +105 @@
 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 \code{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 \code{close} only provides its non-blocking feature.
-To avoid \gls{toctou} issues during shutdown, a busy wait with a \code{select} statement is often used to add or remove elements from a channel.
+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.
+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.
 
@@ -116 +115 @@
 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 \code{throw}, allowing the control to continue where it left off.
+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.
@@ -127 +126 @@
 These termination exceptions allow for non-local transfer that can be 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, \code{channel_closed}, has a couple fields to aid in handling the exception.
+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.
@@ -141 +140 @@
 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 \code{close} call since all tasks are both potentially producers and consumers, causing panics on close to be unavoidable.
+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.
 This sentinel value has to be checked at two points.
-Furthermore, an additional flag \code{done} is needed to communicate to threads once they have left the barrier that they are done.
+Furthermore, an additional flag @done@ is needed to communicate to threads once they have left the barrier that they are done.
 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 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.
@@ -272 +271 @@
 
 In Listing~\ref{l:cfa_resume} an example of channel closing with resumption is used.
-This program uses resumption in the \code{Consumer} thread main to ensure that all elements in the channel are removed before the consumer thread terminates.
-The producer only has a \code{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.
+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.