source: doc/theses/colby_parsons_MMAth/text/channels.tex @ 76a8400

% ======================================================================
% ======================================================================
\chapter{Channels}\label{s:channels}
% ======================================================================
% ======================================================================

Channels were first introduced by Hoare in his paper Communicating Sequentual Processes~\cite{Hoare78}, where he proposes a concurrent language that communicates across processes using input/output channels to send data inbetween processes. Channels are used to perform message passing concurrency, a model of concurrency where threads communicate by sending data to each other, and synchronizing via the passing mechanism. This is an alternative to shared memory concurrency, where threads can communicate directly by changing shared memory state. Most modern concurrent programming languages do not subscribe to just one style of communication between threads, and provide features that support both. 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.

\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.

\section{First-Come First-Served}
The channel implementations that will be discussed are \newterm{First-Come First-Served} (FCFS). This term was defined by Lamport~\cite{Lamport74}. FCFS is defined in relation to a \newterm{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 FCFS, if threads access the shared resource in the order they proceed through the doorway. 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 FCFS can lead to \newterm{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 FCFS may be more performant but that performance comes with the downside of likely introducing starvation and unfairness.

\section{Channel Implementation}
% C_TODO: rewrite to reflect on current impl

\begin{figure}
\begin{lrbox}{\myboxA}
\begin{cfacode}[aboveskip=0pt,belowskip=0pt,basicstyle=\footnotesize]
int size;
int front, back, count;
TYPE * buffer;
cond_var prods, cons;
lock mx;

void insert( TYPE elem ){

    lock(mx);

    // wait if buffer is full
    // insert finished by consumer
    if (count == size){ 
        wait(prods, mx, &elem);
        // no reacquire
        return;
    }




    if (!empty(cons)){
        // do consumer work
        front(cons) = &elem;
        notify_one(cons);
    }


    
    else
        insert_(chan, elem);


    unlock(mx);
}
\end{cfacode}
\end{lrbox}
\begin{lrbox}{\myboxB}
\begin{cfacode}[aboveskip=0pt,belowskip=0pt,basicstyle=\footnotesize]
int size;
int front, back, count;
TYPE * buffer;
thread * chair;
TYPE * chair_elem;
lock c_lock, p_lock, mx;
void insert( TYPE elem ){
    lock(p_lock);
    lock(mx);

    // wait if buffer is full
    // insert finished by consumer
    if (count == size){
        chair = this_thread();
        chair_elem = &elem;
        unlock(mx);
        park();
        unlock(p_lock);
        return;
    }

    if (chair != 0p){
        // do consumer work
        chair_elem = &elem;
        unpark(chair);
        chair = 0p;
        unlock(mx);
        unlock(p_lock);
        return;
    } else 
        insert_(chan, elem);

    unlock(mx);
    unlock(p_lock);
}
\end{cfacode}
\end{lrbox}
\subfloat[Go implementation]{\label{f:GoChanImpl}\usebox\myboxA}
\hspace{5pt}
\vrule
\hspace{5pt}
\subfloat[\CFA implementation]{\label{f:cfaChanImpl}\usebox\myboxB}
\caption{Comparison of channel implementations}
\label{f:ChanComp}
\end{figure}

Go and \CFA have similar channel implementation when it comes to how they solve the producer-consumer problem. Both implementations attempt to minimize double blocking by requiring cooperation from signalling threads. If a consumer or producer is blocked, whichever thread signals it to proceed completes the blocked thread's operation for them so that the blocked thread does not need to acquire any locks. Channels in \CFA go a step further in preventing double blocking. In Figure~\ref{f:ChanComp}, the producer-consumer solutions used by Go and \CFA are presented. Some liberties are taken to simplify the code, such as removing special casing for zero-size buffers, and abstracting the non-concurrent insert into a helper, \code{insert_}. Only the insert routine is presented, as the remove routine is symmetric.
In the Go implementation \ref{f:GoChanImpl}, first mutual exclusion is acquired. Then if the buffer is full the producer waits on a condition variable and releases the mx lock. Note it will not reacquire the lock upon waking. The 3rd argument to \code{wait} is a pointer that is stored per thread on the condition variable. This pointer can be accessed when the waiting thread is at the from of the condition variable's queue by calling \code{front}. This allows arbitrary data to be stored with waiting tasks in the queue, eliminating the need for a second queue just for data. This producer that waits stores a pointer to the element it wanted to insert, so that the consumer that signals them can insert the element for the producer before signalling. If the buffer is not full a producer will proceed to check if any consumers are waiting. If so then the producer puts its value directly into the consumers hands, bypassing the usage of the buffer. If there are no waiting consumers, the producer inserts the value into the buffer and leaves.
The \CFA implementation \ref{f:cfaChanImpl} it follows a similar pattern to the Go implementation, but instead uses three locks and no condition variables. The main idea is that the \CFA implementation forgoes the use of a condition variable by making all producers wait on the outer lock \code{p_lock} once a single producer has to wait inside the critical section. This also happens with consumers. This further reduces double blocking by ensuring that the only threads that can enter the critical section after a producer is blocked are consumers and vice versa. Additionally, entering consumers to not have to contend for the \code{mx} lock once producers are waiting and vice versa. Since only at most one thread will be waiting in the critical section, condition variables are not needed and a barebones thread \code{park} and \code{unpark} will suffice. The operation \code{park} blocks a thread and \code{unpark} is passed a pointer to a thread to wake up. This algorithm can be written using a single condition variable instead of park/unpark, but using park/unpark eliminates the need for any queueing operations. Now with the understanding of park/unpark it is clear to see the similarity between the two algorithms. The main difference being the \code{p_lock} acquisitions and releases. Note that \code{p_lock} is held until after waking from \code{park}, which provides the guarantee than no other producers will enter until the first producer to enter makes progress.

\section{Safety and Productivity}


\section{Performance}