source: doc/theses/colby_parsons_MMAth/text/waituntil.tex @ f77f648d

% ======================================================================
% ======================================================================
\chapter{Waituntil}\label{s:waituntil}
% ======================================================================
% ======================================================================

Consider the following motivational problem that we shall title the bathroom problem.
There are @N@ stalls (resources) in a bathroom and there are @M@ people (threads).
Each stall has their own lock since only one person may occupy a stall at a time.
The standard way that humans solve this problem is that they check if the stalls are occupied and if they all are they queue and watch the stalls until one is free and then enter and lock the stall.
This solution is simple in real life, but can be difficult to implement in a concurrent context as it requires the threads to somehow wait on all the stalls at the same time.
The naive solution to this is for each thread to spin indefinitely continually checking the stalls until one is free.
This wastes cycles and also results in no fairness among threads waiting for stalls as a thread will jump in the first stall available without any regard to other waiting threads.
The ability to wait for the first stall available without spinning can be done with concurrent tools that provide \gls{synch_multiplex}, the ability to wait synchronously for a resource or set of resources.

% C_TODO: fill in citations in following section
\section{History of Synchronous Multiplexing}
There is a history of tools that provide \gls{synch_multiplex}.
Some of the most well known include the set or unix system utilities signal(2)\cite{}, poll(2)\cite{}, and epoll(7)\cite{}, and the select statement provided by Go\cite{}.

Before one can examine the history of \gls{synch_multiplex} implementations in detail, the preceding theory must be discussed.
The theory surrounding this topic was largely introduced by Hoare in his 1985 CSP book \cite{Hoare85} and his later work with Roscoe on the theoretical language Occam\cite{Roscoe88}.
Both include guards for communication channels and the ability to wait for a single channel to be ready out of a set of channels.
The work on Occam in \cite{Roscoe88} calls their \gls{synch_multiplex} primitive ALT, which waits for one resource to be available and then executes a corresponding block of code.
Waiting for one resource out of a set of resources can be thought of as a logical exclusive or over the set of resources.
Guards are a conditional operator similar to an @if@, except they apply to the resource being waited on.
If a guard is false then the resource it guards is considered to not be in the set of resources being waited on.
Guards can be simulated using if statements, but to do so requires \[2^N\] if cases, where @N@ is the number of guards.
This transformation from guards to if statements will be discussed further in Section~\ref{}. % C_TODO: fill ref when writing semantics section later

Switching to implementations, it is important to discuss the resources being multiplexed.
While the aforementioned theory discusses waiting on channels, the earliest known implementation of a synchronous multiplexing tool, Unix's select(2), is multiplexed over file descriptors.
The select(2) system call takes in sets of file descriptors to wait on as arguments and an optional timeout.
Select will block until either some subset of file descriptors are available or the timeout expires.
All file descriptors that are ready will be returned.
This early implementation differs from the theory as when the call from select returns it may provide more than one ready file descriptor.
As such select has a logical or multiplexing semantics, whereas the theory described exclusive-or semantics.
This is not a drawback.
A user can easily achieve exclusive-or semantics with select by arbitrarily choosing only one of the returned descriptors to operate on.
Select was followed by poll(2), and later epoll(7), which both improved upon drawbacks in their predecessors.
The syscall poll(2) improved on select by allowing users to monitor descriptors with numbers higher than 1024 which was not supported by select.
Epoll then improved on poll to return the set of file descriptors since poll would only say that some descriptor from the set was ready but not return which ones were ready.

It is worth noting these \gls{synch_multiplex} tools mentioned so far interact directly with the operating system and are often used to communicate between processes.
Later \gls{synch_multiplex} started to appear in user-space to support fast multiplexed concurrent communication between threads.
An early example of \gls{synch_multiplex} is the select statement in Ada.
The select statement in Ada allows a task to multiplex over some subset of its own methods that it would like to @accept@ calls to.
Tasks in Ada can be thought of as threads which are an object of a specific class, and as such have methods, fields, etc.
This statement has the same exclusive-or semantics as ALT from Occam, and supports guards as described in Occam, however it multiplexes over methods on rather than multiplexing over channels.
A code block is associated with each @accept@, and the method that is @accept@ed first has its corresponding code block run after the task unblocks.
In this way the select statement in Ada provides rendezvous points for threads, rather than providing some resource through message passing.
The select statement in Ada also supports an optional timeout with the same semantics as select(2), and provides an @else@.
The @else@ changes the synchronous multiplexing to asynchronous multiplexing.
If an @else@ clause is in a select statement and no calls to the @accept@ed methods are immediately available the code block associated with the @else@ is run and the task does not block.
The most popular example of user-space \gls{synch_multiplex} is Go with their select statement.
Go's select statement operates on channels and has the same exclusive-or semantics as the ALT primitive from Occam, and has associated code blocks for each clause like ALT and Ada.
However, unlike Ada and ALT, Go does not provide any guards for their select statement cases.
Go provides a timeout utility and also provides a @default@ clause which has the same semantics as Ada's @else@ clause.

\section{Other Approaches to Synchronous Multiplexing}
To avoid the need for \gls{synch_multiplex}, all communication between threads/processes has to come from a single source.
One key example is Erlang, in which each process has a single heterogenous mailbox that is the sole source of concurrent communication, removing the need for \gls{synch_multiplex} as there is only one place to wait on resources.
In a similar vein, actor systems circumvent the \gls{synch_multiplex} problem as actors are traditionally non-blocking, so they will only block when waiting for the next message.
While these approaches solve the \gls{synch_multiplex} problem, they introduce other issues.
Consider the case where a thread has a single source of communication (like erlang and actor systems) wants one of a set of @N@ resources.
It requests @N@ resources and waits for responses.
In the meantime the thread may receive other communication, and may either has to save and postpone the related work or discard it.
After the thread receives one of the @N@ resources, it will continue to receive the other ones it requested, even if it does not need them.
If the requests for the other resources need to be retracted, the burden falls on the programmer to determine how to synchronize appropriately to ensure that only one resource is delivered.


\section{\CFA's Waituntil Statement}