Changeset e9fffb1 for doc/theses/colby_parsons_MMAth/text

Timestamp:

May 2, 2023, 11:14:26 AM (2 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, ast-experimental, master

Children:

7358f65

Parents:

e0e2f02

Message:

start proofreading of channel chapter

File:

• doc/theses/colby_parsons_MMAth/text/channels.tex (modified) (3 diffs)

doc/theses/colby_parsons_MMAth/text/channels.tex ¶

@@ -5 +5 @@
 % ======================================================================
 
-Channels are a concurrent-language feature used to perform \Newterm{message-passing concurrency}: a model of concurrency where threads communicate by sending (mostly nonblocking) data as messages and synchronizing by receiving (blocking) sent data.
+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.
-Most modern concurrent programming languages do not subscribe to just one style of communication among threads and provide features that support multiple approaches.
 
 Channels were first introduced by Kahn~\cite{Kahn74} and extended by Hoare~\cite{Hoare78} (CSP).
@@ -19 +19 @@
 
 \section{Producer-Consumer Problem}
-Most channels in modern programming languages are built on top of a shared memory buffer.
-While it is possible to create a channel that contains an unbounded buffer, most implementations opt to only support a fixed size channel, where the size is given at the time of channel creation.
-This turns the implementation of a channel into the producer-consumer problem.
-The producer-consumer problem, also known as the bounded buffer problem, was introduced by Dijkstra in his book Cooperating Sequential Processes\cite{Dijkstra65}.
-In the problem threads interact with the buffer in two ways, either consuming values by removing them from the buffer, or producing values and inserting them in the buffer.
-The buffer needs to be protected from concurrent access since each item in the buffer should only be produced and consumed once.
-Additionally, a consumer can only remove from a non-empty buffer and a producer can only insert into a non-full buffer.
+A channel is an abstraction for a shared-memory buffer, which turns the implementation of a channel into the producer-consumer problem.
+The producer-consumer problem, also known as the bounded-buffer problem, was introduced by Dijkstra~\cite[\S~4.1]{Dijkstra65}.
+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 at each end resulting from concurrent access by multiple producers or consumers attempt to insert or remove simultaneously (MX).
+
+Channels come in three flavours of buffers:
+\begin{enumerate}
+\item
+Zero 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.
+\item
+Fixed 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.
+\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 restrict must be part of its implementation.
+\end{enumerate}
+
+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).
+The simplest way to prevent starvation is to implement the buffer as a queue, either with a cyclic array or linked nodes.
 
 \section{First-Come First-Served}
-The channel implementations that will be discussed are \gls{fcfs}.
-This term was defined by Lamport~\cite{Lamport74}.
+As pointed out, a bounded buffer requires MX among multiple producers or consumers at either end of the buffer.
+This MX should be fair among threads, independent of the FIFO buffer being fair among values.
+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.
@@ -37 +55 @@
 
 \section{Channel Implementation}
-The channel implementation in \CFA is a near carbon copy of the Go implementation.
-Experimentation was conducted that varied the producer-consumer problem algorithm and lock type used inside the channel.
+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.
 As such the research contributions added by \CFA's channel implementation lie in the realm of safety and productivity features.