Changeset 8a930c03 for doc

doc/bibliography/pl.bib

-              r2b78949
+              r8a930c03
     year        = 2018,
     pages       = {2111-2146},
     note        = {\href{http://dx.doi.org/10.1002/spe.2624}{http://\-dx.doi.org/\-10.1002/\-spe.2624}},
+    optnote     = {\href{http://dx.doi.org/10.1002/spe.2624}{http://\-dx.doi.org/\-10.1002/\-spe.2624}},
+}
 …
     month       = sep,
     year        = 2020,
     note        = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-pub/\-uSystem/uC++.pdf}},
+    note        = {\url{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}},
+}
 …
     number      = 5,
     pages       = {1005-1042},
     note        = {\href{https://onlinelibrary.wiley.com/doi/10.1002/spe.2925}{https://\-onlinelibrary.wiley.com/\-doi/\-10.1002/\-spe.2925}},
+    optnote     = {\href{https://onlinelibrary.wiley.com/doi/10.1002/spe.2925}{https://\-onlinelibrary.wiley.com/\-doi/\-10.1002/\-spe.2925}},
+}
 …
     title       = {Implementing Lock-Free Queues},
     booktitle   = {Seventh International Conference on Parallel and Distributed Computing Systems},
+    organization= {International Society for Computers and Their Applications},
     address     = {Las Vegas, Nevada, U.S.A.},
     year        = {1994},
 …
+}
 @manual{MMTk,
+@misc{MMTk,
     keywords    = {Java memory management},
     contributer = {pabuhr@plg},
 …
     month       = sep,
     year        = 2006,
+    note        = {\href{http://cs.anu.edu.au/~Robin.Garner/mmtk-guide.pdf}
+                  {http://cs.anu.edu.au/\-$\sim$Robin.Garner/\-mmtk-guide.pdf}},
+    howpublished= {\url{http://cs.anu.edu.au/~Robin.Garner/mmtk-guide.pdf}},
+}
 …
+}
+@misc{rpmalloc,
+    author      = {Mattias Jansson},
+    title       = {rpmalloc version 1.4.1},
+    month       = apr,
+    year        = 2022,
+    howpublished= {\href{https://github.com/mjansson/rpmalloc}{https://\-github.com/\-mjansson/\-rpmalloc}},
+}
 @manual{Rust,
     keywords    = {Rust programming language},
 …
     booktitle   = {PLDI '04: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation},
     location    = {Washington DC, USA},
     publisher   = {ACM},
+    organization= {ACM},
     address     = {New York, NY, USA},
     volume      = 39,

doc/papers/llheap/Paper.tex

-              r2b78949
+              r8a930c03
 Dynamic code/data memory is managed by the dynamic loader for libraries loaded at runtime, which is complex especially in a multi-threaded program~\cite{Huang06}.
 However, changes to the dynamic code/data space are typically infrequent, many occurring at program startup, and are largely outside of a program's control.
 Stack memory is managed by the program call/return-mechanism using a simple LIFO technique, which works well for sequential programs.
 For stackful coroutines and user threads, a new stack is commonly created in dynamic-allocation memory.
+Stack memory is managed by the program call/return-mechanism using a LIFO technique, which works well for sequential programs.
+For stackful coroutines and user threads, a new stack is commonly created in the dynamic-allocation memory.
 This work focuses solely on management of the dynamic-allocation memory.
 …
 \begin{enumerate}[leftmargin=*,itemsep=0pt]
 \item
 Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC and \CFA using user-level threads running on multiple kernel threads (M:N threading).
 \item
 Extend the standard C heap functionality by preserving with each allocation: its request size plus the amount allocated, whether an allocation is zero fill, and allocation alignment.
+Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC~\cite{uC++} and \CFA~\cite{Moss18,Delisle21} using user-level threads running on multiple kernel threads (M:N threading).
+\item
+Extend the standard C heap functionality by preserving with each allocation: its request size plus the amount allocated, whether an allocation is zero fill and/or allocation alignment.
 \item
 …
 The following discussion is a quick overview of the moving-pieces that affect the design of a memory allocator and its performance.
 It is assumed that dynamic allocates and deallocates acquire storage for a program variable, referred to as an \newterm{object}, through calls such as @malloc@ and @free@ in C, and @new@ and @delete@ in \CC.
+Dynamic acquires and releases obtain storage for a program variable, called an \newterm{object}, through calls such as @malloc@ and @free@ in C, and @new@ and @delete@ in \CC.
 Space for each allocated object comes from the dynamic-allocation zone.
 …
 Figure~\ref{f:AllocatorComponents} shows the two important data components for a memory allocator, management and storage, collectively called the \newterm{heap}.
+The \newterm{management data} is a data structure located at a known memory address and contains all information necessary to manage the storage data.
+The management data starts with fixed-sized information in the static-data memory that references components in the dynamic-allocation memory.
+The \newterm{management data} is a data structure located at a known memory address and contains fixed-sized information in the static-data memory that references components in the dynamic-allocation memory.
 For multi-threaded programs, additional management data may exist in \newterm{thread-local storage} (TLS) for each kernel thread executing the program.
 The \newterm{storage data} is composed of allocated and freed objects, and \newterm{reserved memory}.
 …
 \ie only the program knows the location of allocated storage not the memory allocator.
 Freed objects (white) represent memory deallocated by the program, which are linked into one or more lists facilitating easy location of new allocations.
 Reserved memory (dark grey) is one or more blocks of memory obtained from the operating system but not yet allocated to the program;
 if there are multiple reserved blocks, they are also chained together, usually internally.
+Reserved memory (dark grey) is one or more blocks of memory obtained from the \newterm{operating system} (OS) but not yet allocated to the program;
+if there are multiple reserved blocks, they are also chained together.
 \begin{figure}
 …
 \end{figure}
 In most allocator designs, allocated objects have management data embedded within them.
+In many allocator designs, allocated objects and reserved blocks have management data embedded within them (see also Section~\ref{s:ObjectContainers}).
 Figure~\ref{f:AllocatedObject} shows an allocated object with a header, trailer, and optional spacing around the object.
 The header contains information about the object, \eg size, type, etc.
 …
 When padding and spacing are necessary, neither can be used to satisfy a future allocation request while the current allocation exists.
 A free object also contains management data, \eg size, pointers, etc.
+A free object often contains management data, \eg size, pointers, etc.
 Often the free list is chained internally so it does not consume additional storage, \ie the link fields are placed at known locations in the unused memory blocks.
 For internal chaining, the amount of management data for a free node defines the minimum allocation size, \eg if 16 bytes are needed for a free-list node, allocation requests less than 16 bytes are rounded up.
 The information in an allocated or freed object is overwritten when it transitions from allocated to freed and vice-versa by new management information and/or program data.
+The information in an allocated or freed object is overwritten when it transitions from allocated to freed and vice-versa by new program data and/or management information.
 \begin{figure}
 …
 \label{s:Fragmentation}
 Fragmentation is memory requested from the operating system but not used by the program;
+Fragmentation is memory requested from the OS but not used by the program;
 hence, allocated objects are not fragmentation.
 Figure~\ref{f:InternalExternalFragmentation} shows fragmentation is divided into two forms: internal or external.
 …
 An allocator should strive to keep internal management information to a minimum.
 \newterm{External fragmentation} is all memory space reserved from the operating system but not allocated to the program~\cite{Wilson95,Lim98,Siebert00}, which includes all external management data, freed objects, and reserved memory.
+\newterm{External fragmentation} is all memory space reserved from the OS but not allocated to the program~\cite{Wilson95,Lim98,Siebert00}, which includes all external management data, freed objects, and reserved memory.
 This memory is problematic in two ways: heap blowup and highly fragmented memory.
 \newterm{Heap blowup} occurs when freed memory cannot be reused for future allocations leading to potentially unbounded external fragmentation growth~\cite{Berger00}.
 Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects, resulting in a checkerboard of adjacent allocated and free areas, where the free blocks have become very small.
+Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects, resulting in a checkerboard of adjacent allocated and free areas, where the free blocks have become to small to service requests.
 % Figure~\ref{f:MemoryFragmentation} shows an example of how a small block of memory fragments as objects are allocated and deallocated over time.
 Heap blowup can occur due to allocator policies that are too restrictive in reusing freed memory (the allocated size cannot use a larger free block) and/or no coalescing of free storage.
 …
 % Memory is highly fragmented when most free blocks are unusable because of their sizes.
 % For example, Figure~\ref{f:Contiguous} and Figure~\ref{f:HighlyFragmented} have the same quantity of external fragmentation, but Figure~\ref{f:HighlyFragmented} is highly fragmented.
 % If there is a request to allocate a large object, Figure~\ref{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while Figure~\ref{f:HighlyFragmented} likely has to request more memory from the operating system.
+% If there is a request to allocate a large object, Figure~\ref{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while Figure~\ref{f:HighlyFragmented} likely has to request more memory from the OS.
 % \begin{figure}
 …
 The first approach is a \newterm{sequential-fit algorithm} with one list of free objects that is searched for a block large enough to fit a requested object size.
 Different search policies determine the free object selected, \eg the first free object large enough or closest to the requested size.
 Any storage larger than the request can become spacing after the object or be split into a smaller free object.
+Any storage larger than the request can become spacing after the object or split into a smaller free object.
 % The cost of the search depends on the shape and quality of the free list, \eg a linear versus a binary-tree free-list, a sorted versus unsorted free-list.
 …
 The third approach is \newterm{splitting} and \newterm{coalescing algorithms}.
 When an object is allocated, if there are no free objects of the requested size, a larger free object may be split into two smaller objects to satisfy the allocation request without obtaining more memory from the operating system.
 For example, in the \newterm{buddy system}, a block of free memory is split into two equal chunks, one of those chunks is again split into two equal chunks, and so on until a block just large enough to fit the requested object is created.
 When an object is deallocated it is coalesced with the objects immediately before and after it in memory, if they are free, turning them into one larger object.
+When an object is allocated, if there are no free objects of the requested size, a larger free object is split into two smaller objects to satisfy the allocation request rather than obtaining more memory from the OS.
+For example, in the \newterm{buddy system}, a block of free memory is split into equal chunks, one of those chunks is again split, and so on until a minimal block is created that fits the requested object.
+When an object is deallocated, it is coalesced with the objects immediately before and after it in memory, if they are free, turning them into one larger block.
 Coalescing can be done eagerly at each deallocation or lazily when an allocation cannot be fulfilled.
 In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays during coalescing.
+In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays.
 While coalescing does not reduce external fragmentation, the coalesced blocks improve fragmentation quality so future allocations are less likely to cause heap blowup.
 % Splitting and coalescing can be used with other algorithms to avoid highly fragmented memory.
 …
 \label{s:Locality}
 The principle of locality recognizes that programs tend to reference a small set of data, called a working set, for a certain period of time, where a working set is composed of temporal and spatial accesses~\cite{Denning05}.
+The principle of locality recognizes that programs tend to reference a small set of data, called a \newterm{working set}, for a certain period of time, composed of temporal and spatial accesses~\cite{Denning05}.
 % Temporal clustering implies a group of objects are accessed repeatedly within a short time period, while spatial clustering implies a group of objects physically close together (nearby addresses) are accessed repeatedly within a short time period.
 % Temporal locality commonly occurs during an iterative computation with a fixed set of disjoint variables, while spatial locality commonly occurs when traversing an array.
 Hardware takes advantage of temporal and spatial locality through multiple levels of caching, \ie memory hierarchy.
+Hardware takes advantage of the working set through multiple levels of caching, \ie memory hierarchy.
 % When an object is accessed, the memory physically located around the object is also cached with the expectation that the current and nearby objects will be referenced within a short period of time.
 For example, entire cache lines are transferred between memory and cache and entire virtual-memory pages are transferred between disk and memory.
+For example, entire cache lines are transferred between cache and memory, and entire virtual-memory pages are transferred between memory and disk.
 % A program exhibiting good locality has better performance due to fewer cache misses and page faults\footnote{With the advent of large RAM memory, paging is becoming less of an issue in modern programming.}.
 …
 \label{s:MutualExclusion}
 \newterm{Mutual exclusion} provides sequential access to the shared management data of the heap.
+\newterm{Mutual exclusion} provides sequential access to the shared-management data of the heap.
 There are two performance issues for mutual exclusion.
 First is the overhead necessary to perform (at least) a hardware atomic operation every time a shared resource is accessed.
 Second is when multiple threads contend for a shared resource simultaneously, and hence, some threads must wait until the resource is released.
 Contention can be reduced in a number of ways:
 ) Using multiple fine-grained locks versus a single lock, spreading the contention across a number of locks.
+) Using multiple fine-grained locks versus a single lock to spread the contention across a number of locks.
 ) Using trylock and generating new storage if the lock is busy, yielding a classic space versus time tradeoff.
 ) Using one of the many lock-free approaches for reducing contention on basic data-structure operations~\cite{Oyama99}.
 …
 a memory allocator can only affect the latter two.
 Assume two objects, object$_1$ and object$_2$, share a cache line.
 \newterm{Program-induced false-sharing} occurs when thread$_1$ passes a reference to object$_2$ to thread$_2$, and then threads$_1$ modifies object$_1$ while thread$_2$ modifies object$_2$.
+Specifically, assume two objects, O$_1$ and O$_2$, share a cache line, with threads, T$_1$ and T$_2$.
+\newterm{Program-induced false-sharing} occurs when T$_1$ passes a reference to O$_2$ to T$_2$, and then T$_1$ modifies O$_1$ while T$_2$ modifies O$_2$.
 % Figure~\ref{f:ProgramInducedFalseSharing} shows when Thread$_1$ passes Object$_2$ to Thread$_2$, a false-sharing situation forms when Thread$_1$ modifies Object$_1$ and Thread$_2$ modifies Object$_2$.
 % Changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
 …
 % \label{f:FalseSharing}
 % \end{figure}
 \newterm{Allocator-induced active false-sharing}\label{s:AllocatorInducedActiveFalseSharing} occurs when object$_1$ and object$_2$ are heap allocated and their references are passed to thread$_1$ and thread$_2$, which modify the objects.
+\newterm{Allocator-induced active false-sharing}\label{s:AllocatorInducedActiveFalseSharing} occurs when O$_1$ and O$_2$ are heap allocated and their references are passed to T$_1$ and T$_2$, which modify the objects.
 % For example, in Figure~\ref{f:AllocatorInducedActiveFalseSharing}, each thread allocates an object and loads a cache-line of memory into its associated cache.
 % Again, changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
 …
 % is another form of allocator-induced false-sharing caused by program-induced false-sharing.
 % When an object in a program-induced false-sharing situation is deallocated, a future allocation of that object may cause passive false-sharing.
 when thread$_1$ passes object$_2$ to thread$_2$, and thread$_2$ subsequently deallocates object$_2$, and then object$_2$ is reallocated to thread$_2$ while thread$_1$ is still using object$_1$.
+when T$_1$ passes O$_2$ to T$_2$, and T$_2$ subsequently deallocates O$_2$, and then O$_2$ is reallocated to T$_2$ while T$_1$ is still using O$_1$.
 …
 \label{s:MultiThreadedMemoryAllocatorFeatures}
+The following features are used in the construction of multi-threaded memory-allocators:
+\begin{enumerate}[itemsep=0pt]
+\item multiple heaps: with or without a global heap, or with or without heap ownership.
+\item object containers: with or without ownership, fixed or variable sized, global or local free-lists.
+\item hybrid private/public heap
+\item allocation buffer
+\item lock-free operations
+\end{enumerate}
+The following features are used in the construction of multi-threaded memory-allocators: multiple heaps, user-level threading, ownership, object containers, allocation buffer, lock-free operations.
 The first feature, multiple heaps, pertains to different kinds of heaps.
 The second feature, object containers, pertains to the organization of objects within the storage area.
 …
 \subsection{Multiple Heaps}
+\subsubsection{Multiple Heaps}
 \label{s:MultipleHeaps}
 A multi-threaded allocator has potentially multiple threads and heaps.
 The multiple threads cause complexity, and multiple heaps are a mechanism for dealing with the complexity.
 The spectrum ranges from multiple threads using a single heap, denoted as T:1 (see Figure~\ref{f:SingleHeap}), to multiple threads sharing multiple heaps, denoted as T:H (see Figure~\ref{f:SharedHeaps}), to one thread per heap, denoted as 1:1 (see Figure~\ref{f:PerThreadHeap}), which is almost back to a single-threaded allocator.
+The spectrum ranges from multiple threads using a single heap, denoted as T:1, to multiple threads sharing multiple heaps, denoted as T:H, to one thread per heap, denoted as 1:1, which is almost back to a single-threaded allocator.
 \begin{figure}
 …
 \end{figure}
 \paragraph{T:1 model} where all threads allocate and deallocate objects from one heap.
 Memory is obtained from the freed objects, or reserved memory in the heap, or from the operating system (OS);
 the heap may also return freed memory to the operating system.
+\paragraph{T:1 model (see Figure~\ref{f:SingleHeap})} where all threads allocate and deallocate objects from one heap.
+Memory is obtained from the freed objects, or reserved memory in the heap, or from the OS;
+the heap may also return freed memory to the OS.
 The arrows indicate the direction memory conceptually moves for each kind of operation: allocation moves memory along the path from the heap/operating-system to the user application, while deallocation moves memory along the path from the application back to the heap/operating-system.
 To safely handle concurrency, a single lock may be used for all heap operations or fine-grained locking for different operations.
 Regardless, a single heap may be a significant source of contention for programs with a large amount of memory allocation.
 \paragraph{T:H model} where each thread allocates storage from several heaps depending on certain criteria, with the goal of reducing contention by spreading allocations/deallocations across the heaps.
+\paragraph{T:H model (see Figure~\ref{f:SharedHeaps})} where each thread allocates storage from several heaps depending on certain criteria, with the goal of reducing contention by spreading allocations/deallocations across the heaps.
 The decision on when to create a new heap and which heap a thread allocates from depends on the allocator design.
 To determine which heap to access, each thread must point to its associated heap in some way.
 …
 An alternative implementation is for all heaps to share one reserved memory, which requires a separate lock for the reserved storage to ensure mutual exclusion when acquiring new memory.
 Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
 Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area, pushing part of the storage management complexity back to the operating system.
+Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area, pushing part of the storage management complexity back to the OS.
 % \begin{figure}
 …
 Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup.
 The external fragmentation experienced by a program with a single heap is now multiplied by the number of heaps, since each heap manages its own free storage and allocates its own reserved memory.
 Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the operating system, which can be expensive.
 Depending on how the operating system provides dynamic storage to an application, returning storage may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix.
 In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused.
+Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the OS (see Section~\ref{s:Ownership}).
+Returning storage to the OS may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix.
+% In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused.
 Adding a \newterm{global heap} (G) attempts to reduce the cost of obtaining/returning memory among heaps (sharing) by buffering storage within the application address-space.
 Now, each heap obtains and returns storage to/from the global heap rather than the operating system.
+Now, each heap obtains and returns storage to/from the global heap rather than the OS.
 Storage is obtained from the global heap only when a heap allocation cannot be fulfilled, and returned to the global heap when a heap's free memory exceeds some threshold.
 Similarly, the global heap buffers this memory, obtaining and returning storage to/from the operating system as necessary.
+Similarly, the global heap buffers this memory, obtaining and returning storage to/from the OS as necessary.
 The global heap does not have its own thread and makes no internal allocation requests;
 instead, it uses the application thread, which called one of the multiple heaps and then the global heap, to perform operations.
 Hence, the worst-case cost of a memory operation includes all these steps.
+With respect to heap blowup, the global heap provides an indirect mechanism to move free memory among heaps, which usually has a much lower cost than interacting with the operating system to achieve the same goal and is independent of the mechanism used by the operating system to present dynamic memory to an address space.
+With respect to heap blowup, the global heap provides an indirect mechanism to move free memory among heaps, which usually has a much lower cost than interacting with the OS to achieve the same goal and is independent of the mechanism used by the OS to present dynamic memory to an address space.
 However, since any thread may indirectly perform a memory operation on the global heap, it is a shared resource that requires locking.
 A single lock can be used to protect the global heap or fine-grained locking can be used to reduce contention.
 In general, the cost is minimal since the majority of memory operations are completed without the use of the global heap.
+\paragraph{1:1 model (thread heaps)} where each thread has its own heap eliminating most contention and locking because threads seldom access another thread's heap (see ownership in Section~\ref{s:Ownership}).
+\paragraph{1:1 model (see Figure~\ref{f:PerThreadHeap})} where each thread has its own heap eliminating most contention and locking because threads seldom access another thread's heap (see Section~\ref{s:Ownership}).
 An additional benefit of thread heaps is improved locality due to better memory layout.
 As each thread only allocates from its heap, all objects are consolidated in the storage area for that heap, better utilizing each CPUs cache and accessing fewer pages.
 …
 Thread heaps can also eliminate allocator-induced active false-sharing, if memory is acquired so it does not overlap at crucial boundaries with memory for another thread's heap.
 For example, assume page boundaries coincide with cache line boundaries, if a thread heap always acquires pages of memory then no two threads share a page or cache line unless pointers are passed among them.
 Hence, allocator-induced active false-sharing cannot occur because the memory for thread heaps never overlaps.
+% Hence, allocator-induced active false-sharing cannot occur because the memory for thread heaps never overlaps.
 When a thread terminates, there are two options for handling its thread heap.
 …
 It is possible to use any of the heap models with user-level (M:N) threading.
 However, an important goal of user-level threading is for fast operations (creation/termination/context-switching) by not interacting with the operating system, which allows the ability to create large numbers of high-performance interacting threads ($>$ 10,000).
+However, an important goal of user-level threading is for fast operations (creation/termination/context-switching) by not interacting with the OS, which allows the ability to create large numbers of high-performance interacting threads ($>$ 10,000).
 It is difficult to retain this goal, if the user-threading model is directly involved with the heap model.
 Figure~\ref{f:UserLevelKernelHeaps} shows that virtually all user-level threading systems use whatever kernel-level heap-model is provided by the language runtime.
 …
 \end{figure}
 Adopting this model results in a subtle problem with shared heaps.
 With kernel threading, an operation that is started by a kernel thread is always completed by that thread.
 For example, if a kernel thread starts an allocation/deallocation on a shared heap, it always completes that operation with that heap even if preempted, \ie any locking correctness associated with the shared heap is preserved across preemption.
+Adopting user threading results in a subtle problem with shared heaps.
+With kernel threading, an operation started by a kernel thread is always completed by that thread.
+For example, if a kernel thread starts an allocation/deallocation on a shared heap, it always completes that operation with that heap, even if preempted, \ie any locking correctness associated with the shared heap is preserved across preemption.
 However, this correctness property is not preserved for user-level threading.
 A user thread can start an allocation/deallocation on one kernel thread, be preempted (time slice), and continue running on a different kernel thread to complete the operation~\cite{Dice02}.
 When the user thread continues on the new kernel thread, it may have pointers into the previous kernel-thread's heap and hold locks associated with it.
 To get the same kernel-thread safety, time slicing must be disabled/\-enabled around these operations, so the user thread cannot jump to another kernel thread.
 However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption does not happen that frequently.
+However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption is infrequent (milliseconds).
 Instead, techniques exist to lazily detect this case in the interrupt handler, abort the preemption, and return to the operation so it can complete atomically.
 Occasionally ignoring a preemption should be benign, but a persistent lack of preemption can result in both short and long term starvation;
 techniques like rollforward can be used to force an eventual preemption.
+Occasional ignoring of a preemption should be benign, but a persistent lack of preemption can result in starvation;
+techniques like rolling forward the preemption to the next context switch can be used.
 …
 % For example, in Figure~\ref{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Thread$_2$'s heap initially.
 % If Thread$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur.
+For thread heaps with ownership, it is possible to combine these approaches into a hybrid approach with both private and public heaps.% (see~Figure~\ref{f:HybridPrivatePublicHeap}).
+The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
+In the hybrid approach, a thread first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
+Similarly, a thread first deallocates an object to its private heap, and second to the public heap.
+Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps.
+% Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap.
+Finally, when a thread frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing thread's private heap for delayed ownership, which does allows the freeing thread to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return.
+% \begin{figure}
+% \centering
+% \input{PrivatePublicHeaps.pstex_t}
+% \caption{Hybrid Private/Public Heap for Per-thread Heaps}
+% \label{f:HybridPrivatePublicHeap}
+% \vspace{10pt}
+% \input{RemoteFreeList.pstex_t}
+% \caption{Remote Free-List}
+% \label{f:RemoteFreeList}
+% \end{figure}
+% As mentioned, an implementation may have only one heap interact with the global heap, so the other heap can be simplified.
+% For example, if only the private heap interacts with the global heap, the public heap can be reduced to a lock-protected free-list of objects deallocated by other threads due to ownership, called a \newterm{remote free-list}.
+% To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage.
+% Since the remote free-list is occasionally cleared during an allocation, this adds to that cost.
+% Clearing the remote free-list is $O(1)$ if the list can simply be added to the end of the private-heap's free-list, or $O(N)$ if some action must be performed for each freed object.
+% If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking.
+% In this scenario, the private heap must deallocate storage after reaching a certain threshold to the public heap (and then eventually to the global heap from the public heap) or heap blowup can occur.
+% If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations.
+% The main disadvantage of each thread having both a private and public heap is the complexity of managing two heaps and their interactions in an allocator.
+% Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used.
+% In many case, the hybrid approach is actually being used, but the simpler heap is just folded into the complex heap, even though the operations logically belong in separate heaps.
+% For example, a remote free-list is actually a simple public-heap, but may be implemented as an integral component of the complex private-heap in an allocator, masking the presence of a hybrid approach.
 …
 \subsection{Object Containers}
+\subsubsection{Object Containers}
 \label{s:ObjectContainers}
 …
 \eg an object is accessed by the program after it is allocated, while the header is accessed by the allocator after it is free.
 The alternative factors common header data to a separate location in memory and organizes associated free storage into blocks called \newterm{object containers} (\newterm{superblocks} in~\cite{Berger00}), as in Figure~\ref{f:ObjectContainer}.
+An alternative approach factors common header data to a separate location in memory and organizes associated free storage into blocks called \newterm{object containers} (\newterm{superblocks}~\cite{Berger00}), as in Figure~\ref{f:ObjectContainer}.
 The header for the container holds information necessary for all objects in the container;
 a trailer may also be used at the end of the container.
 …
 \subsubsection{Container Ownership}
+\paragraph{Container Ownership}
 \label{s:ContainerOwnership}
 …
 Additional restrictions may be applied to the movement of containers to prevent active false-sharing.
 For example, if a container changes ownership through the global heap, then when a thread allocates an object from the newly acquired container it is actively false-sharing even though no objects are passed among threads.
+For example, if a container changes ownership through the global heap, then a thread allocating from the newly acquired container is actively false-sharing even though no objects are passed among threads.
 Note, once the thread frees the object, no more false sharing can occur until the container changes ownership again.
 To prevent this form of false sharing, container movement may be restricted to when all objects in the container are free.
 One implementation approach that increases the freedom to return a free container to the operating system involves allocating containers using a call like @mmap@, which allows memory at an arbitrary address to be returned versus only storage at the end of the contiguous @sbrk@ area, again pushing storage management complexity back to the operating system.
+One implementation approach that increases the freedom to return a free container to the OS involves allocating containers using a call like @mmap@, which allows memory at an arbitrary address to be returned versus only storage at the end of the contiguous @sbrk@ area, again pushing storage management complexity back to the OS.
 % \begin{figure}
 …
 \subsubsection{Container Size}
+\paragraph{Container Size}
 \label{s:ContainerSize}
 …
 However, with more objects in a container, there may be more objects that are unallocated, increasing external fragmentation.
 With smaller containers, not only are there more containers, but a second new problem arises where objects are larger than the container.
 In general, large objects, \eg greater than 64\,KB, are allocated directly from the operating system and are returned immediately to the operating system to reduce long-term external fragmentation.
+In general, large objects, \eg greater than 64\,KB, are allocated directly from the OS and are returned immediately to the OS to reduce long-term external fragmentation.
 If the container size is small, \eg 1\,KB, then a 1.5\,KB object is treated as a large object, which is likely to be inappropriate.
 Ideally, it is best to use smaller containers for smaller objects, and larger containers for medium objects, which leads to the issue of locating the container header.
 …
 \subsubsection{Container Free-Lists}
+\paragraph{Container Free-Lists}
 \label{s:containersfreelists}
 …
+\subsubsection{Hybrid Private/Public Heap}
+\label{s:HybridPrivatePublicHeap}
+Section~\ref{s:Ownership} discusses advantages and disadvantages of public heaps (T:H model and with ownership) and private heaps (thread heaps with ownership).
+For thread heaps with ownership, it is possible to combine these approaches into a hybrid approach with both private and public heaps (see~Figure~\ref{f:HybridPrivatePublicHeap}).
+The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
+In the hybrid approach, a thread first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
+Similarly, a thread first deallocates an object to its private heap, and second to the public heap.
+Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps.
+Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap.
+Finally, when a thread frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing thread's private heap for delayed ownership, which allows the freeing thread to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return.
+\begin{figure}
+\centering
+\input{PrivatePublicHeaps.pstex_t}
+\caption{Hybrid Private/Public Heap for Per-thread Heaps}
+\label{f:HybridPrivatePublicHeap}
+% \vspace{10pt}
+% \input{RemoteFreeList.pstex_t}
+% \caption{Remote Free-List}
+% \label{f:RemoteFreeList}
+\end{figure}
+As mentioned, an implementation may have only one heap interact with the global heap, so the other heap can be simplified.
+For example, if only the private heap interacts with the global heap, the public heap can be reduced to a lock-protected free-list of objects deallocated by other threads due to ownership, called a \newterm{remote free-list}.
+To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage.
+Since the remote free-list is occasionally cleared during an allocation, this adds to that cost.
+Clearing the remote free-list is $O(1)$ if the list can simply be added to the end of the private-heap's free-list, or $O(N)$ if some action must be performed for each freed object.
+If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking.
+In this scenario, the private heap must deallocate storage after reaching a certain threshold to the public heap (and then eventually to the global heap from the public heap) or heap blowup can occur.
+If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations.
+The main disadvantage of each thread having both a private and public heap is the complexity of managing two heaps and their interactions in an allocator.
+Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used.
+In many case, the hybrid approach is actually being used, but the simpler heap is just folded into the complex heap, even though the operations logically belong in separate heaps.
+For example, a remote free-list is actually a simple public-heap, but may be implemented as an integral component of the complex private-heap in an allocator, masking the presence of a hybrid approach.
+\subsection{Allocation Buffer}
+\subsubsection{Allocation Buffer}
 \label{s:AllocationBuffer}
 An allocation buffer is reserved memory (see Section~\ref{s:AllocatorComponents}) not yet allocated to the program, and is used for allocating objects when the free list is empty.
 That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later.
 Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or operating system, respectively.
+Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or OS, respectively.
 The allocation buffer reduces contention and the number of global/operating-system calls.
 For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations.
 …
 Allocation buffers may increase external fragmentation, since some memory in the allocation buffer may never be allocated.
 A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or operating system.
+A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or OS.
 The allocation buffer also slightly increases internal fragmentation, since a pointer is necessary to locate the next free object in the buffer.
 …
 For example, when a container is created, rather than placing all objects within the container on the free list, the objects form an allocation buffer and are allocated from the buffer as allocation requests are made.
 This lazy method of constructing objects is beneficial in terms of paging and caching.
 For example, although an entire container, possibly spanning several pages, is allocated from the operating system, only a small part of the container is used in the working set of the allocator, reducing the number of pages and cache lines that are brought into higher levels of cache.
 \subsection{Lock-Free Operations}
+For example, although an entire container, possibly spanning several pages, is allocated from the OS, only a small part of the container is used in the working set of the allocator, reducing the number of pages and cache lines that are brought into higher levels of cache.
+\subsubsection{Lock-Free Operations}
 \label{s:LockFreeOperations}
 …
 % A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}\label{p:SeriallyReusable}
 % \end{quote}
 % If a KT is preempted during an allocation operation, the operating system can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
+% If a KT is preempted during an allocation operation, the OS can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
 % Note, the serially-reusable problem can occur in sequential programs with preemption, if the signal handler calls the preempted function, unless the function is serially reusable.
 % Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the operating system is providing the second thread via the signal handler.
+% Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the OS is providing the second thread via the signal handler.
+%
 % Library @librseq@~\cite{librseq} was used to perform a fast determination of the CPU and to ensure all memory operations complete on one CPU using @librseq@'s restartable sequences, which restart the critical subsection after undoing its writes, if the critical subsection is preempted.
 …
 A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}\label{p:SeriallyReusable}
 \end{quote}
 If a KT is preempted during an allocation operation, the operating system can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
+If a KT is preempted during an allocation operation, the OS can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
 Note, the serially-reusable problem can occur in sequential programs with preemption, if the signal handler calls the preempted function, unless the function is serially reusable.
 Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the operating system is providing the second thread via the signal handler.
+Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the OS is providing the second thread via the signal handler.
 Library @librseq@~\cite{librseq} was used to perform a fast determination of the CPU and to ensure all memory operations complete on one CPU using @librseq@'s restartable sequences, which restart the critical subsection after undoing its writes, if the critical subsection is preempted.
 …
 For the T:H=CPU and 1:1 models, locking is eliminated along the allocation fastpath.
 However, T:H=CPU has poor operating-system support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs.
 More operating system support is required to make this model viable, but there is still the serially-reusable problem with user-level threading.
+More OS support is required to make this model viable, but there is still the serially-reusable problem with user-level threading.
 So the 1:1 model had no atomic actions along the fastpath and no special operating-system support requirements.
 The 1:1 model still has the serially-reusable problem with user-level threading, which is addressed in Section~\ref{s:UserlevelThreadingSupport}, and the greatest potential for heap blowup for certain allocation patterns.
 …
 A primary goal of llheap is low latency, hence the name low-latency heap (llheap).
 Two forms of latency are internal and external.
 Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the operating system.
+Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the OS.
 Ideally latency is $O(1)$ with a small constant.
 …
 The mitigating factor is that most programs have well behaved allocation patterns, where the majority of allocation operations can be $O(1)$, and heap blowup does not occur without coalescing (although the allocation footprint may be slightly larger).
 To obtain $O(1)$ external latency means obtaining one large storage area from the operating system and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation.
+To obtain $O(1)$ external latency means obtaining one large storage area from the OS and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation.
 Excluding real-time operating-systems, operating-system operations are unbounded, and hence some external latency is unavoidable.
 The mitigating factor is that operating-system calls can often be reduced if a programmer has a sense of the storage high-watermark and the allocator is capable of using this information (see @malloc_expansion@ \pageref{p:malloc_expansion}).
 …
 headers per allocation versus containers,
 no coalescing to minimize latency,
 global heap memory (pool) obtained from the operating system using @mmap@ to create and reuse heaps needed by threads,
+global heap memory (pool) obtained from the OS using @mmap@ to create and reuse heaps needed by threads,
 local reserved memory (pool) per heap obtained from global pool,
 global reserved memory (pool) obtained from the operating system using @sbrk@ call,
+global reserved memory (pool) obtained from the OS using @sbrk@ call,
 optional fast-lookup table for converting allocation requests into bucket sizes,
 optional statistic-counters table for accumulating counts of allocation operations.
 …
 Each heap uses segregated free-buckets that have free objects distributed across 91 different sizes from 16 to 4M.
 All objects in a bucket are of the same size.
 The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation using @mallopt( M_MMAP_THRESHOLD )@, \ie small objects managed by the program and large objects managed by the operating system.
+The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation using @mallopt( M_MMAP_THRESHOLD )@, \ie small objects managed by the program and large objects managed by the OS.
 Each free bucket of a specific size has two lists.
 ) A free stack used solely by the KT heap-owner, so push/pop operations do not require locking.
 …
 Algorithm~\ref{alg:heapObjectAlloc} shows the allocation outline for an object of size $S$.
 First, the allocation is divided into small (@sbrk@) or large (@mmap@).
 For large allocations, the storage is mapped directly from the operating system.
+For large allocations, the storage is mapped directly from the OS.
 For small allocations, $S$ is quantized into a bucket size.
 Quantizing is performed using a binary search over the ordered bucket array.
 …
 heap's local pool,
 global pool,
 operating system (@sbrk@).
+OS (@sbrk@).
 \begin{algorithm}
 …
 Algorithm~\ref{alg:heapObjectFreeOwn} shows the de-allocation (free) outline for an object at address $A$ with ownership.
 First, the address is divided into small (@sbrk@) or large (@mmap@).
 For large allocations, the storage is unmapped back to the operating system.
+For large allocations, the storage is unmapped back to the OS.
 For small allocations, the bucket associated with the request size is retrieved.
 If the bucket is local to the thread, the allocation is pushed onto the thread's associated bucket.
 …
 \textsf{pt3} is the only memory allocator where the total dynamic memory goes down in the second half of the program lifetime when the memory is freed by the benchmark program.
 It makes pt3 the only memory allocator that gives memory back to the operating system as it is freed by the program.
+It makes pt3 the only memory allocator that gives memory back to the OS as it is freed by the program.
 % FOR 1 THREAD

doc/papers/llheap/figures/AllocatorComponents.fig

-              r2b78949
+              r8a930c03
 -2
 2
-1275 2025 2700 2625
 2400 2025 2700 2625
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 …
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2025 2700 2325 2400 2325 2400 2025 2700 2025
--6
-2 0 50 -1 2 11 0.0000 2 165 1005 2325 2400 Management\001
 -6
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 …
 2 0 1 0 7 60 -1 13 0.000 0 0 -1 0 0 5
 2700 6300 2700 6300 3000 3300 3000 3300 2700
 0 0 50 -1 2 11 0.0000 2 165 585 3300 1725 Storage\001
+0 0 50 -1 2 11 0.0000 2 165 1005 3300 1725 Storage Data\001
 2 0 50 -1 0 11 0.0000 2 165 810 3000 1875 free objects\001
 2 0 50 -1 0 11 0.0000 2 135 1140 3000 2850 reserve memory\001
 1 0 50 -1 0 11 0.0000 2 120 795 2325 1500 Static Zone\001
 1 0 50 -1 0 11 0.0000 2 165 1845 4800 1500 Dynamic-Allocation Zone\001
+2 0 50 -1 2 11 0.0000 2 165 1005 2325 2325 Management\001
+2 0 50 -1 2 11 0.0000 2 135 375 2325 2525 Data\001

doc/theses/colby_parsons_MMAth/Makefile

r2b78949	r8a930c03
98	98
99	99	${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${DATA} \
100		style/style.tex ${Macros}/common.tex ${Macros}/indexstyle local.bib ../../bibliography/pl.bib \| ${Build}
	100	glossary.tex style/style.tex ${Macros}/common.tex ${Macros}/indexstyle local.bib ../../bibliography/pl.bib \| ${Build}
101	101	# Must have *.aux file containing citations for bibtex
102	102	if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/balance.cfa

-              r2b78949
+              r8a930c03
 d_actor ** actor_arr;
 Allocation receive( d_actor & this, start_msg & msg ) with( this ) {
+allocation receive( d_actor & this, start_msg & msg ) with( this ) {
     for ( i; Set ) {
         *actor_arr[i + gstart] << shared_msg;
 …
+}
 Allocation receive( d_actor & this, d_msg & msg ) with( this ) {
+allocation receive( d_actor & this, d_msg & msg ) with( this ) {
     if ( recs == rounds ) return Delete;
     if ( recs % Batch == 0 ) {
 …
+}
 Allocation receive( filler & this, d_msg & msg ) { return Delete; }
+allocation receive( filler & this, d_msg & msg ) { return Delete; }
 int main( int argc, char * argv[] ) {

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/dynamic.cfa

r2b78949	r8a930c03
24	24
25	25	uint64_t start_time;
26		Allocation receive( derived_actor & receiver, derived_msg & msg ) {
	26	allocation receive( derived_actor & receiver, derived_msg & msg ) {
27	27	if ( msg.cnt >= Times ) {
28	28	printf("%.2f\n", ((double)(bench_time() - start_time)) / ((double)Times) ); // ns

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/executor.cfa

r2b78949	r8a930c03
25	25	struct d_msg { inline message; } shared_msg;
26	26
27		Allocation receive( d_actor & this, d_msg & msg ) with( this ) {
	27	allocation receive( d_actor & this, d_msg & msg ) with( this ) {
28	28	if ( recs == rounds ) return Finished;
29	29	if ( recs % Batch == 0 ) {

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/matrix.cfa

r2b78949	r8a930c03
24	24	}
25	25
26		Allocation receive( derived_actor & receiver, derived_msg & msg ) {
	26	allocation receive( derived_actor & receiver, derived_msg & msg ) {
27	27	for ( unsigned int i = 0; i < yc; i += 1 ) { // multiply X_row by Y_col and sum products
28	28	msg.Z[i] = 0;

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/repeat.cfa

-              r2b78949
+              r8a930c03
 Client * cl;
 Allocation receive( Server & this, IntMsg & msg ) { msg.val = 7; *cl << msg; return Nodelete; }
 Allocation receive( Server & this, CharMsg & msg ) { msg.val = 'x'; *cl << msg; return Nodelete; }
 Allocation receive( Server & this, StateMsg & msg ) { return Finished; }
+allocation receive( Server & this, IntMsg & msg ) { msg.val = 7; *cl << msg; return Nodelete; }
+allocation receive( Server & this, CharMsg & msg ) { msg.val = 'x'; *cl << msg; return Nodelete; }
+allocation receive( Server & this, StateMsg & msg ) { return Finished; }
 void terminateServers( Client & this ) with(this) {
 …
+}
 Allocation reset( Client & this ) with(this) {
+allocation reset( Client & this ) with(this) {
     times += 1;
     if ( times == Times ) { terminateServers( this ); return Finished; }
 …
+}
 Allocation process( Client & this ) with(this) {
+allocation process( Client & this ) with(this) {
     this.results++;
     if ( results == 2 * Messages ) { return reset( this ); }
 …
+}
 Allocation receive( Client & this, IntMsg & msg ) { return process( this ); }
 Allocation receive( Client & this, CharMsg & msg ) { return process( this ); }
 Allocation receive( Client & this, StateMsg & msg ) with(this) {
+allocation receive( Client & this, IntMsg & msg ) { return process( this ); }
+allocation receive( Client & this, CharMsg & msg ) { return process( this ); }
+allocation receive( Client & this, StateMsg & msg ) with(this) {
     for ( i; Messages ) {
         servers[i] << intmsg[i];

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/static.cfa

r2b78949	r8a930c03
23	23
24	24	uint64_t start_time;
25		Allocation receive( derived_actor & receiver, derived_msg & msg ) {
	25	allocation receive( derived_actor & receiver, derived_msg & msg ) {
26	26	if ( msg.cnt >= Times ) {
27	27	printf("%.2f\n", ((double)(bench_time() - start_time)) / ((double)Times) ); // ns

doc/theses/colby_parsons_MMAth/benchmarks/actors/plotData.py

r2b78949	r8a930c03
160	160
161	161	if currVariant == numVariants:
162		fig, ax = plt.subplots()
	162	fig, ax = plt.subplots(layout='constrained')
163	163	plt.title(name + " Benchmark")
164	164	plt.ylabel("Runtime (seconds)")

doc/theses/colby_parsons_MMAth/benchmarks/channels/plotData.py

r2b78949	r8a930c03
124	124
125	125	if currVariant == numVariants:
126		fig, ax = plt.subplots()
	126	fig, ax = plt.subplots(layout='constrained')
127	127	plt.title(name + " Benchmark")
128	128	plt.ylabel("Throughput (channel operations)")

doc/theses/colby_parsons_MMAth/benchmarks/mutex_stmt/plotData.py

r2b78949	r8a930c03
97	97
98	98	if currVariant == numVariants:
99		fig, ax = plt.subplots()
	99	fig, ax = plt.subplots(layout='constrained')
100	100	plt.title(name + " Benchmark: " + str(currLocks) + " Locks")
101	101	plt.ylabel("Throughput (entries)")

doc/theses/colby_parsons_MMAth/code/basic_actor_example.cfa

r2b78949	r8a930c03
19	19	}
20	20
21		Allocation receive( derived_actor & receiver, derived_msg & msg ) {
	21	allocation receive( derived_actor & receiver, derived_msg & msg ) {
22	22	printf("The message contained the string: %s\n", msg.word);
23	23	return Finished; // Return allocation status of Finished now that the actor is done work

doc/theses/colby_parsons_MMAth/glossary.tex

-              r2b78949
+              r8a930c03
 % Examples from template above
 \newabbreviation{raii}{RAII}{Resource Acquisition Is Initialization}
 \newabbreviation{rtti}{RTTI}{Run-Time Type Information}
 \newabbreviation{fcfs}{FCFS}{First Come First Served}
 \newabbreviation{toctou}{TOCTOU}{time-of-check to time-of-use}
+\newabbreviation{raii}{RAII}{\Newterm{resource acquisition is initialization}}
+\newabbreviation{rtti}{RTTI}{\Newterm{run-time type information}}
+\newabbreviation{fcfs}{FCFS}{\Newterm{first-come first-served}}
+\newabbreviation{toctou}{TOCTOU}{\Newterm{time-of-check to time-of-use}}
 \newglossaryentry{actor}

doc/theses/colby_parsons_MMAth/local.bib

-              r2b78949
+              r8a930c03
 @misc{go:select,
   author = "The Go Programming Language",
   title = "src/runtime/chan.go",
+  title = "src/runtime/select.go",
   howpublished = {\href{https://go.dev/src/runtime/select.go}},
   note = "[Online; accessed 23-May-2023]"
+}
+@misc{go:selectref,
+  author = "The Go Programming Language Specification",
+  title = "Select statements",
+  howpublished = {\href{https://go.dev/ref/spec#Select\_statements}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{boost:channel,
+  author = "Boost C++ Libraries",
+  title = "experimental::basic\_concurrent\_channel",
+  howpublished = {\href{https://www.boost.org/doc/libs/master/doc/html/boost\_asio/reference/experimental\__basic\_concurrent\_channel.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{rust:channel,
+  author = "The Rust Standard Library",
+  title = "std::sync::mpsc::sync\_channel",
+  howpublished = {\href{https://doc.rust-lang.org/std/sync/mpsc/fn.sync\_channel.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{rust:select,
+  author = "The Rust Standard Library",
+  title = "Macro futures::select",
+  howpublished = {\href{https://docs.rs/futures/latest/futures/macro.select.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{ocaml:channel,
+  author = "The OCaml Manual",
+  title = "OCaml library : Event",
+  howpublished = {\href{https://v2.ocaml.org/api/Event.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{haskell:channel,
+  author = "The Haskell Package Repository",
+  title = "Control.Concurrent.Chan",
+  howpublished = {\href{https://hackage.haskell.org/package/base-4.18.0.0/docs/Control-Concurrent-Chan.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{linux:select,
+  author = "Linux man pages",
+  title = "select(2) — Linux manual page",
+  howpublished = {\href{https://man7.org/linux/man-pages/man2/select.2.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{linux:poll,
+  author = "Linux man pages",
+  title = "poll(2) — Linux manual page",
+  howpublished = {\href{https://man7.org/linux/man-pages/man2/poll.2.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@misc{linux:epoll,
+  author = "Linux man pages",
+  title = "epoll(7) — Linux manual page",
+  howpublished = {\href{https://man7.org/linux/man-pages/man7/epoll.7.html}},
+  note = "[Online; accessed 23-May-2023]"
+}
+@article{Ichbiah79,
+  title={Preliminary Ada reference manual},
+  author={Ichbiah, Jean D},
+  journal={ACM Sigplan Notices},
+  volume={14},
+  number={6a},
+  pages={1--145},
+  year={1979},
+  publisher={ACM New York, NY, USA}
+}
+@misc{cpp:whenany,
+  author = "C++ reference",
+  title = "std::experimental::when\_any",
+  howpublished = {\href{https://en.cppreference.com/w/cpp/experimental/when\_any}},
+  note = "[Online; accessed 23-May-2023]"
+}

doc/theses/colby_parsons_MMAth/style/style.tex

-              r2b78949
+              r8a930c03
 \newsavebox{\myboxB}
+\lstnewenvironment{Golang}[1][]
+{\lstset{language=Go,literate={<-}{\makebox[2ex][c]{\textless\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}}2,
+        moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}
+{}
 \lstnewenvironment{java}[1][]
 {\lstset{language=java,moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}}

doc/theses/colby_parsons_MMAth/text/channels.tex

-              r2b78949
+              r8a930c03
 Additionally all channel operations in CSP are synchronous (no buffering).
 Advanced channels as a programming language feature has been popularized in recent years by the language Go~\cite{Go}, which encourages the use of channels as its fundamental concurrent feature.
 It was the popularity of Go channels that lead to their implemention in \CFA.
+It was the popularity of Go channels that lead to their implementation in \CFA.
 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}.
+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.
 \section{Producer-Consumer Problem}
 …
 \section{Channel Implementation}
 Currently, only the Go programming language provides user-level threading where the primary communication mechanism is channels.
 Experiments were conducted that varied the producer-consumer problem algorithm and lock type used inside the channel.
+Experiments were conducted that varied the producer-consumer algorithm and lock type used inside the channel.
 With the exception of non-\gls{fcfs} or non-FIFO 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.
 Performance of channels can be improved by sharding the underlying buffer \cite{Dice11}.
 In doing so the FIFO property is lost, which is undesireable for user-facing channels.
+However, the FIFO property is lost, which is undesirable for user-facing channels.
 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.
+The Go channel implementation utilitizes cooperation between threads to achieve good performance~\cite{go:chan}.
+The cooperation between threads only occurs when producers or consumers need to block due to the buffer being full or empty.
+In these cases the blocking thread stores their relevant data in a shared location and the signalling thread will complete their operation before waking them.
+This helps improve performance in a few ways.
+First, each thread interacting with the channel with only acquire and release the internal channel lock exactly once.
+This decreases contention on the internal lock, as only entering threads will compete for the lock since signalled threads never reacquire the lock.
+The other advantage of the cooperation approach is that it eliminates the potential bottleneck of waiting for signalled threads.
+The property of acquiring/releasing the lock only once can be achieved without cooperation by \Newterm{baton passing} the lock.
+Baton passing is 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 to the signalled thread.
+While baton passing is useful in some algorithms, it results in worse performance than the cooperation approach in channel implementations since all entering threads then need to wait for the blocked thread to reach the front of the ready queue and run before other operations on the channel can proceed.
+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.
+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.
+This approach is similar to wait morphing for locks~\cite[p.~82]{Butenhof97} and improves performance in a few ways.
+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, as only entering threads compete for the lock as 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.
+Note, 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 baton-passing approach has threads cooperate to pass mutual exclusion without additional lock acquires or releases;
+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 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.
 In this work, all channel sizes \see{Sections~\ref{s:ChannelSize}} are implemented with bounded buffers.
 …
 \subsection{Toggle-able Statistics}
 As discussed, a channel is a concurrent layer over a bounded buffer.
 To achieve efficient buffering users should aim for as few blocking operations on a channel as possible.
 Often to achieve this users may change the buffer size, shard a channel into multiple channels, or tweak the number of producer and consumer threads.
 Fo users to be able to make informed decisions when tuning channel usage, toggle-able channel statistics are provided.
 The statistics are toggled at compile time via the @CHAN_STATS@ macro to ensure that they are entirely elided when not used.
 When statistics are turned on, four counters are maintained per channel, two for producers and two for consumers.
+To achieve efficient buffering, users should aim for as few blocking operations on a channel as possible.
+Mechanisms to reduce blocking are: change the buffer size, shard a channel into multiple channels, or tweak the number of producer and consumer threads.
+For users to be able to make informed decisions when tuning channel usage, toggle-able channel statistics are provided.
+The statistics are toggled on during the \CFA build by defining the @CHAN_STATS@ macro, which guarantees zero cost when not using this feature.
+When statistics are turned on, four counters are maintained per channel, two for inserting (producers) and two for removing (consumers).
 The two counters per type of operation track the number of blocking operations and total operations.
+In the channel destructor the counters are printed out aggregated and also per type of operation.
+An example use case of the counters follows.
+A user is buffering information between producer and consumer threads and wants to analyze channel performance.
+Via the statistics they see that producers block for a large percentage of their operations while consumers do not block often.
+They then can use this information to adjust their number of producers/consumers or channel size to achieve a larger percentage of non-blocking producer operations, thus increasing their channel throughput.
+In the channel destructor, the counters are printed out aggregated and also per type of operation.
+An example use case is noting that producer inserts are blocking often while consumer removes do not block often.
+This information can be used to increase the number of consumers to decrease the blocking producer operations, thus increasing the channel throughput.
+Whereas, increasing the channel size in this scenario is unlikely to produce a benefit because the consumers can never keep up with the producers.
 \subsection{Deadlock Detection}
+The deadlock detection in the \CFA channels is fairly basic.
+It only detects the case where threads are blocked on the channel during deallocation.
+This case is guaranteed to deadlock since the list holding the blocked thread is internal to the channel and will be deallocated.
+If a user maintained a separate reference to a thread and unparked it outside the channel they could avoid the deadlock, but would run into other runtime errors since the thread would access channel data after waking that is now deallocated.
+More robust deadlock detection surrounding channel usage would have to be implemented separate from the channel implementation since it would require knowledge about the threading system and other channel/thread state.
+The deadlock detection in the \CFA channels is fairly basic but detects a very common channel mistake during termination.
+That is, it detects the case where threads are blocked on the channel during channel deallocation.
+This case is guaranteed to deadlock since there are no other threads to supply or consume values needed by the waiting threads.
+Only if a user maintained a separate reference to the blocked threads and manually unblocks them outside the channel could the deadlock be avoid.
+However, without special semantics, this unblocking would generate other runtime errors where the unblocked thread attempts to access non-existing channel data or even a deallocated channel.
+More robust deadlock detection needs to be implemented separate from channels since it requires knowledge about the threading system and other channel/thread state.
 \subsection{Program Shutdown}
 Terminating concurrent programs is often one of the most difficult parts of writing concurrent code, particularly if graceful termination is needed.
 The difficulty of graceful termination often arises from the usage of synchronization primitives that need to be handled carefully during shutdown.
+Graceful termination can be difficult to achieve with synchronization primitives that need to be handled carefully during shutdown.
 It is easy to deadlock during termination if threads are left behind on synchronization primitives.
 Additionally, most synchronization primitives are prone to \gls{toctou} issues where there is race between one thread checking the state of a concurrent object and another thread changing the state.
 \gls{toctou} issues with synchronization primitives often involve a race between one thread checking the primitive for blocked threads and another thread blocking on it.
 Channels are a particularly hard synchronization primitive to terminate since both sending and receiving to/from a channel can block.
+Thus, improperly handled \gls{toctou} issues with channels often result in deadlocks as threads trying to perform the termination may end up unexpectedly blocking in their attempt to help other threads exit the system.
+\paragraph{Go channels} provide a set of tools to help with concurrent shutdown~\cite{go:chan}.
+Channels in Go have a @close@ operation and a \Go{select} statement that both can be used to help threads terminate.
+Thus, improperly handled \gls{toctou} issues with channels often result in deadlocks as threads performing the termination may end up unexpectedly blocking in their attempt to help other threads exit the system.
+\paragraph{Go channels} provide a set of tools to help with concurrent shutdown~\cite{go:chan} using a @close@ operation in conjunction with the \Go{select} statement.
 The \Go{select} statement is discussed in \ref{s:waituntil}, where \CFA's @waituntil@ statement is compared with the Go \Go{select} statement.
 …
 Note, panics in Go can be caught, but it is not the idiomatic way to write Go programs.
 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.
+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 (producers) before the channel can be closed to avoid panics.
 However, in doing so it renders the @close@ operation nearly useless, as the only utilities it provides are the ability to ensure receivers no longer block on the channel and receive zero-valued elements.
 This functionality is only useful if the zero-typed element is recognized as a sentinel value, but if another sentinel value is necessary, then @close@ only provides the 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.
+Hence, due to Go's asymmetric approach to channel shutdown, separate synchronization between producers and consumers of a channel has to occur during shutdown.
 \paragraph{\CFA channels} have access to an extensive exception handling mechanism~\cite{Beach21}.
 …
 When a channel in \CFA is closed, all subsequent calls to the channel raise a resumption exception at the caller.
 If the resumption is handled, the caller attempts to complete the channel operation.
 However, if channel operation would block, a termination exception is thrown.
+However, if the channel operation would block, a termination exception is thrown.
 If the resumption is not handled, the exception is rethrown as a termination.
 These termination exceptions allow for non-local transfer that is 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, @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.
+In the case of insert the element pointer points to the element that the thread attempted to insert.
+The resumption exception, @channel_closed@, has internal fields to aid in handling the exception.
+The exception contains a pointer to the channel it is thrown from and a pointer to a buffer element.
+For exceptions thrown from @remove@, the buffer element pointer is null.
+For exceptions thrown from @insert@, the element pointer points to the buffer element that the thread attempted to insert.
+Utility routines @bool is_insert( channel_closed & e );@ and @bool is_remove( channel_closed & e );@ are provided for convenient checking of the element pointer.
 This element pointer allows the handler to know which operation failed and also allows the element to not be lost on a failed insert since it can be moved elsewhere in the handler.
+Furthermore, due to \CFA's powerful exception system, this data can be used to choose handlers based which channel and operation failed.
+Exception handlers in \CFA have an optional predicate after the exception type which can be used to optionally trigger or skip handlers based on the content of an exception.
+It is worth mentioning that the approach of exceptions for termination may incur a larger performance cost during termination that the approach used in Go.
+This should not be an issue, since termination is rarely an fast-path of an application and ensuring that termination can be implemented correctly with ease is the aim of the exception approach.
+Furthermore, due to \CFA's powerful exception system, this data can be used to choose handlers based on which channel and operation failed.
+For example, exception handlers in \CFA have an optional predicate which can be used to trigger or skip handlers based on the content of the matching exception.
+It is worth mentioning that using exceptions for termination may incur a larger performance cost than the Go approach.
+However, this should not be an issue, since termination is rarely on the fast-path of an application.
+In contrast, ensuring termination can be easily implemented correctly is the aim of the exception approach.
 \section{\CFA / Go channel Examples}
 To highlight the differences between \CFA's and Go's close semantics, three examples will be presented.
+To highlight the differences between \CFA's and Go's close semantics, three examples are presented.
 The first example is a simple shutdown case, where there are producer threads and consumer threads operating on a channel for a fixed duration.
 Once the duration ends, producers and consumers terminate without worrying about any leftover values in the channel.
 The second example extends the first example by requiring the channel to be empty upon shutdown.
+Once the duration ends, producers and consumers terminate immediately leaving unprocessed elements in the channel.
+The second example extends the first by requiring the channel to be empty after shutdown.
 Both the first and second example are shown in Figure~\ref{f:ChannelTermination}.
-First the Go solutions to these examples shown in Figure~\ref{l:go_chan_term} are discussed.
-Since some of the elements being passed through the channel are zero-valued, closing the channel in Go does not aid in communicating shutdown.
-Instead, a different mechanism to communicate with the consumers and producers needs to be used.
-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 this example, a flag is used to communicate with producers and another flag is used for consumers.
-Producers and consumers need separate avenues of communication both so that producers terminate before the channel is closed to avoid panicking, and to avoid the case where all the consumers terminate first, which can result in a deadlock for producers if the channel is full.
-The producer flag is set first, then after producers terminate the consumer flag is set and the channel is closed.
-In the second example where all values need to be consumed, the main thread iterates over the closed channel to process any remaining values.
-In the \CFA solutions in Figure~\ref{l:cfa_chan_term}, shutdown is communicated directly to both producers and consumers via the @close@ call.
-In the first example where all values do not need to be consumed, both producers and consumers do not handle the resumption and finish once they receive the termination exception.
-The second \CFA example where all values must be consumed highlights how resumption is used with channel shutdown.
-The @Producer@ thread-main knows to stop producing when the @insert@ call on a closed channel raises exception @channel_closed@.
-The @Consumer@ thread-main knows to stop consuming after all elements of a closed channel are removed and the call to @remove@ would block.
-Hence, the consumer knows the moment the channel closes because a resumption exception is raised, caught, and ignored, and then control returns to @remove@ to return another item from the buffer.
-Only when the buffer is drained and the call to @remove@ would block, a termination exception is raised to stop consuming.
-The \CFA semantics allow users to communicate channel shutdown directly through the channel, without having to share extra state between threads.
-Additionally, when the channel needs to be drained, \CFA provides users with easy options for processing the leftover channel values in the main thread or in the consumer threads.
-If one wishes to consume the leftover values in the consumer threads in Go, extra synchronization between the main thread and the consumer threads is needed.
 \begin{figure}
 …
 \begin{lrbox}{\myboxA}
+\begin{Golang}[aboveskip=0pt,belowskip=0pt]
+var channel chan int = make( chan int, 128 )
+var prodJoin chan int = make( chan int, 4 )
+var consJoin chan int = make( chan int, 4 )
+var cons_done, prod_done bool = false, false;
+func producer() {
+        for {
+                if prod_done { break }
+                channel <- 5
+        }
+        prodJoin <- 0 // synch with main thd
+}
+func consumer() {
+        for {
+                if cons_done { break }
+                <- channel
+        }
+        consJoin <- 0 // synch with main thd
+}
+func main() {
+        for j := 0; j < 4; j++ { go consumer() }
+        for j := 0; j < 4; j++ { go producer() }
+        time.Sleep( time.Second * 10 )
+        prod_done = true
+        for j := 0; j < 4 ; j++ { <- prodJoin }
+        cons_done = true
+        close(channel) // ensure no cons deadlock
+        @for elem := range channel {@
+                // process leftover values
+        @}@
+        for j := 0; j < 4; j++ { <- consJoin }
+}
+\end{Golang}
+\end{lrbox}
+\begin{lrbox}{\myboxB}
 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
+channel( size_t ) Channel{ ChannelSize };
+channel( size_t ) chan{ 128 };
 thread Consumer {};
+thread Producer {};
+void main( Producer & this ) {
+        try {
+                for ()
+                        insert( chan, 5 );
+        } catch( channel_closed * ) {
+                // unhandled resume or full
+        }
+}
 void main( Consumer & this ) {
+    try {
+        for ( ;; )
+            remove( Channel );
+    @} catchResume( channel_closed * ) { @
+    // handled resume => consume from chan
+    } catch( channel_closed * ) {
+        // empty or unhandled resume
+    }
+}
+thread Producer {};
+void main( Producer & this ) {
+    size_t count = 0;
+    try {
+        for ( ;; )
+            insert( Channel, count++ );
+    } catch ( channel_closed * ) {
+        // unhandled resume or full
+    }
+}
+int main( int argc, char * argv[] ) {
+    Consumer c[Consumers];
+    Producer p[Producers];
+    sleep(Duration`s);
+    close( Channel );
+    return 0;
+}
+        try {
+                for () { int i = remove( chan ); }
+        @} catchResume( channel_closed * ) {@
+                // handled resume => consume from chan
+        } catch( channel_closed * ) {
+                // empty or unhandled resume
+        }
+}
+int main() {
+        Consumer c[4];
+        Producer p[4];
+        sleep( 10`s );
+        close( chan );
+}
 \end{cfa}
 \end{lrbox}
+\begin{lrbox}{\myboxB}
+\begin{cfa}[aboveskip=0pt,belowskip=0pt]
+var cons_done, prod_done bool = false, false;
+var prodJoin chan int = make(chan int, Producers)
+var consJoin chan int = make(chan int, Consumers)
+func consumer( channel chan uint64 ) {
+    for {
+        if cons_done { break }
+        <-channel
+    }
+    consJoin <- 0 // synch with main thd
+}
+func producer( channel chan uint64 ) {
+    var count uint64 = 0
+    for {
+        if prod_done { break }
+        channel <- count++
+    }
+    prodJoin <- 0 // synch with main thd
+}
+func main() {
+    channel = make(chan uint64, ChannelSize)
+    for j := 0; j < Consumers; j++ {
+        go consumer( channel )
+    }
+    for j := 0; j < Producers; j++ {
+        go producer( channel )
+    }
+    time.Sleep(time.Second * Duration)
+    prod_done = true
+    for j := 0; j < Producers ; j++ {
+        <-prodJoin // wait for prods
+    }
+    cons_done = true
+    close(channel) // ensure no cons deadlock
+    @for elem := range channel { @
+        // process leftover values
+    @}@
+    for j := 0; j < Consumers; j++{
+        <-consJoin // wait for cons
+    }
+}
+\end{cfa}
+\end{lrbox}
+\subfloat[\CFA style]{\label{l:cfa_chan_term}\usebox\myboxA}
+\subfloat[Go style]{\label{l:go_chan_term}\usebox\myboxA}
 \hspace*{3pt}
 \vrule
 \hspace*{3pt}
 \subfloat[Go style]{\label{l:go_chan_term}\usebox\myboxB}
+\subfloat[\CFA style]{\label{l:cfa_chan_term}\usebox\myboxB}
 \caption{Channel Termination Examples 1 and 2. Code specific to example 2 is highlighted.}
 \label{f:ChannelTermination}
 \end{figure}
+The final shutdown example uses channels to implement a barrier.
+It is shown in Figure~\ref{f:ChannelBarrierTermination}.
+The problem of implementing a barrier is chosen since threads are both producers and consumers on the barrier-internal channels, which removes the ability to easily synchronize producers before consumers during shutdown.
+As such, while the shutdown details will be discussed with this problem in mind, they are also applicable to other problems taht have individual threads both producing and consuming from channels.
+Both of these examples are implemented using \CFA syntax so that they can be easily compared.
+Figure~\ref{l:cfa_chan_bar} uses \CFA-style channel close semantics and Figure~\ref{l:go_chan_bar} uses Go-style close semantics.
+In this example it is infeasible to use the Go @close@ call since all threads are both potentially producers and consumers, causing panics on close to be unavoidable without complex synchronization.
+As such in Figure~\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.
+Figure~\ref{l:go_chan_term} shows the Go solution.
+Since some of the elements being passed through the channel are zero-valued, closing the channel in Go does not aid in communicating shutdown.
+Instead, a different mechanism to communicate with the consumers and producers needs to be used.
+Flag variables are common in Go-channel shutdown-code to avoid panics on a channel, meaning the channel shutdown has to be communicated with threads before it occurs.
+Hence, the two flags @cons_done@ and @prod_done@ are used to communicate with the producers and consumers, respectively.
+Furthermore, producers and consumers need to shutdown separately to ensure that producers terminate before the channel is closed to avoid panicking, and to avoid the case where all the consumers terminate first, which can result in a deadlock for producers if the channel is full.
+The producer flag is set first;
+then after all producers terminate, the consumer flag is set and the channel is closed leaving elements in the buffer.
+To purge the buffer, a loop is added (red) that iterates over the closed channel to process any remaining values.
+Figure~\ref{l:cfa_chan_term} shows the \CFA solution.
+Here, shutdown is communicated directly to both producers and consumers via the @close@ call.
+A @Producer@ thread knows to stop producing when the @insert@ call on a closed channel raises exception @channel_closed@.
+If a @Consumer@ thread ignores the first resumption exception from the @close@, the exception is reraised as a termination exception and elements are left in the buffer.
+If a @Consumer@ thread handles the resumptions exceptions (red), control returns to complete the remove.
+A @Consumer@ thread knows to stop consuming after all elements of a closed channel are removed and the consumer would block, which causes a termination raise of @channel_closed@.
+The \CFA semantics allow users to communicate channel shutdown directly through the channel, without having to share extra state between threads.
+Additionally, when the channel needs to be drained, \CFA provides users with easy options for processing the leftover channel values in the main thread or in the consumer threads.
+Figure~\ref{f:ChannelBarrierTermination} shows a final shutdown example using channels to implement a barrier.
+A Go and \CFA style solution are presented but both are implemented using \CFA syntax so they can be easily compared.
+Implementing a barrier is interesting because threads are both producers and consumers on the barrier-internal channels, @entryWait@ and @barWait@.
+The outline for the barrier implementation starts by initially filling the @entryWait@ channel with $N$ tickets in the barrier constructor, allowing $N$ arriving threads to remove these values and enter the barrier.
+After @entryWait@ is empty, arriving threads block when removing.
+However, the arriving threads that entered the barrier cannot leave the barrier until $N$ threads have arrived.
+Hence, the entering threads block on the empty @barWait@ channel until the $N$th arriving thread inserts $N-1$ elements into @barWait@ to unblock the $N-1$ threads calling @remove@.
+The race between these arriving threads blocking on @barWait@ and the $N$th thread inserting values into @barWait@ does not affect correctness;
+\ie an arriving thread may or may not block on channel @barWait@ to get its value.
+Finally, the last thread to remove from @barWait@ with ticket $N-2$, refills channel @entryWait@ with $N$ values to start the next group into the barrier.
+Now, the two channels makes termination synchronization between producers and consumers difficult.
+Interestingly, the shutdown details for this problem are also applicable to other problems with threads producing and consuming from the same channel.
+The Go-style solution cannot use the Go @close@ call since all threads are both potentially producers and consumers, causing panics on close to be unavoidable without complex synchronization.
+As such in Figure \ref{l:go_chan_bar}, a flush routine is needed to insert a sentinel value, @-1@, to inform threads waiting in the buffer they need to leave the barrier.
+This sentinel value has to be checked at two points along the fast-path and sentinel values daisy-chained into the buffers.
 Furthermore, an additional flag @done@ is needed to communicate to threads once they have left the barrier that they are done.
 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.
+Also note that in the Go version~\ref{l:go_chan_bar}, the size of the barrier channels has to be larger than in the \CFA version to ensure that the main thread does not block when attempting to clear the barrier.
+For The \CFA solution~\ref{l:cfa_chan_bar}, the barrier shutdown results in an exception being thrown at threads operating on it, to inform waiting threads they must leave the barrier.
 This avoids the need to use a separate communication method other than the barrier, and avoids extra conditional checks on the fast path of the barrier implementation.
-Also note that in the Go version~\ref{l:go_chan_bar}, the size of the barrier channels has to be larger than in the \CFA version to ensure that the main thread does not block when attempting to clear the barrier.
 \begin{figure}
 …
 \begin{lrbox}{\myboxA}
+\begin{cfa}[aboveskip=0pt,belowskip=0pt]
+struct barrier {
+        channel( int ) barWait, entryWait;
+        int size;
+};
+void ?{}( barrier & this, int size ) with(this) {
+        barWait{size + 1};   entryWait{size + 1};
+        this.size = size;
+        for ( i; size )
+                insert( entryWait, i );
+}
+void wait( barrier & this ) with(this) {
+        int ticket = remove( entryWait );
+        @if ( ticket == -1 ) { insert( entryWait, -1 ); return; }@
+        if ( ticket == size - 1 ) {
+                for ( i; size - 1 )
+                        insert( barWait, i );
+                return;
+        }
+        ticket = remove( barWait );
+        @if ( ticket == -1 ) { insert( barWait, -1 ); return; }@
+        if ( size == 1 || ticket == size - 2 ) { // last ?
+                for ( i; size )
+                        insert( entryWait, i );
+        }
+}
+void flush(barrier & this) with(this) {
+        @insert( entryWait, -1 );   insert( barWait, -1 );@
+}
+enum { Threads = 4 };
+barrier b{Threads};
+@bool done = false;@
+thread Thread {};
+void main( Thread & this ) {
+        for () {
+          @if ( done ) break;@
+                wait( b );
+        }
+}
+int main() {
+        Thread t[Threads];
+        sleep(10`s);
+        done = true;
+        flush( b );
+} // wait for threads to terminate
+\end{cfa}
+\end{lrbox}
+\begin{lrbox}{\myboxB}
 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
 struct barrier {
 …
 \end{lrbox}
+\begin{lrbox}{\myboxB}
+\begin{cfa}[aboveskip=0pt,belowskip=0pt]
+struct barrier {
+        channel( int ) barWait, entryWait;
+        int size;
+};
+void ?{}( barrier & this, int size ) with(this) {
+        barWait{size + 1};   entryWait{size + 1};
+        this.size = size;
+        for ( i; size )
+                insert( entryWait, i );
+}
+void wait( barrier & this ) with(this) {
+        int ticket = remove( entryWait );
+        @if ( ticket == -1 ) { insert( entryWait, -1 ); return; }@
+        if ( ticket == size - 1 ) {
+                for ( i; size - 1 )
+                        insert( barWait, i );
+                return;
+        }
+        ticket = remove( barWait );
+        @if ( ticket == -1 ) { insert( barWait, -1 ); return; }@
+        if ( size == 1 || ticket == size - 2 ) { // last ?
+                for ( i; size )
+                        insert( entryWait, i );
+        }
+}
+void flush(barrier & this) with(this) {
+        @insert( entryWait, -1 );   insert( barWait, -1 );@
+}
+enum { Threads = 4 };
+barrier b{Threads};
+@bool done = false;@
+thread Thread {};
+void main( Thread & this ) {
+        for () {
+          @if ( done ) break;@
+                wait( b );
+        }
+}
+int main() {
+        Thread t[Threads];
+        sleep(10`s);
+        done = true;
+        flush( b );
+} // wait for threads to terminate
+\end{cfa}
+\end{lrbox}
+\subfloat[\CFA style]{\label{l:cfa_chan_bar}\usebox\myboxA}
+\subfloat[Go style]{\label{l:go_chan_bar}\usebox\myboxA}
 \hspace*{3pt}
 \vrule
 \hspace*{3pt}
 \subfloat[Go style]{\label{l:go_chan_bar}\usebox\myboxB}
+\subfloat[\CFA style]{\label{l:cfa_chan_bar}\usebox\myboxB}
 \caption{Channel Barrier Termination}
 \label{f:ChannelBarrierTermination}

doc/theses/colby_parsons_MMAth/text/waituntil.tex

-              r2b78949
+              r8a930c03
 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{}.
+Some of the most well known include the set of unix system utilities: select(2)\cite{linux:select}, poll(2)\cite{linux:poll}, and epoll(7)\cite{linux:epoll}, and the select statement provided by Go\cite{go:selectref}.
 Before one can examine the history of \gls{synch_multiplex} implementations in detail, the preceding theory must be discussed.
 …
 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
+The equivalence between guards and exponential if statements comes from an Occam ALT statement rule~\cite{Roscoe88}, which is presented in \CFA syntax in Figure~\ref{f:wu_if}.
+Providing guards allows for easy toggling of waituntil clauses without introducing repeated code.
+\begin{figure}
+\begin{cfa}
+when( predicate ) waituntil( A ) {}
+or waituntil( B ) {}
+// ===
+if ( predicate ) {
+    waituntil( A ) {}
+    or waituntil( B ) {}
+} else {
+    waituntil( B ) {}
+}
+\end{cfa}
+\caption{Occam's guard to if statement equivalence shown in \CFA syntax.}
+\label{f:wu_if}
+\end{figure}
 Switching to implementations, it is important to discuss the resources being multiplexed.
 …
 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.
+An early example of \gls{synch_multiplex} is the select statement in Ada~\cite[\S~9.7]{Ichbiah79}.
 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.
 …
 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.
+A popular example of user-space \gls{synch_multiplex} is Go with their select statement~\cite{go:selectref}.
 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.
+\uC provides \gls{synch_multiplex} over futures with their @_Select@ statement and Ada-style \gls{synch_multiplex} over monitor methods with their @_Accept@ statement~\cite{uC++}.
+Their @_Accept@ statement builds upon the select statement offered by Ada, by offering both @and@ and @or@ semantics, which can be used together in the same statement.
+These semantics are also supported for \uC's @_Select@ statement.
+This enables fully expressive \gls{synch_multiplex} predicates.
+There are many other languages that provide \gls{synch_multiplex}, including Rust's @select!@ over futures~\cite{rust:select}, OCaml's @select@ over channels~\cite{ocaml:channe}, and C++14's @when_any@ over futures~\cite{cpp:whenany}.
+Note that while C++14 and Rust provide \gls{synch_multiplex}, their implemetations leave much to be desired as they both rely on busy-waiting polling to wait on multiple resources.
 \section{Other Approaches to Synchronous Multiplexing}
 …
 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}
+The new \CFA \gls{synch_multiplex} utility introduced in this work is the @waituntil@ statement.
+There is a @waitfor@ statement in \CFA that supports Ada-style \gls{synch_multiplex} over monitor methods, so this @waituntil@ focuses on synchronizing over other resources.
+All of the \gls{synch_multiplex} features mentioned so far are monomorphic, only supporting one resource to wait on, select(2) supports file descriptors, Go's select supports channel operations, \uC's select supports futures, and Ada's select supports monitor method calls.
+The waituntil statement in \CFA is polymorphic and provides \gls{synch_multiplex} over any objects that satisfy the trait in Figure~\ref{f:wu_trait}.
+\begin{figure}
+\begin{cfa}
+forall(T & | sized(T))
+trait is_selectable {
+    // For registering a waituntil stmt on a selectable type
+    bool register_select( T &, select_node & );
+    // For unregistering a waituntil stmt from a selectable type
+    bool unregister_select( T &, select_node & );
+    // on_selected is run on the selecting thread prior to executing the statement associated with the select_node
+    void on_selected( T &, select_node & );
+};
+\end{cfa}
+\caption{Trait for types that can be passed into \CFA's waituntil statement.}
+\label{f:wu_trait}
+\end{figure}
+Currently locks, channels, futures and timeouts are supported by the waituntil statement, but this will be expanded as other use cases arise.
+The waituntil statement supports guarded clauses, like Ada, and Occam, supports both @or@, and @and@ semantics, like \uC, and provides an @else@ for asynchronous multiplexing. An example of \CFA waituntil usage is shown in Figure~\ref{f:wu_example}. In Figure~\ref{f:wu_example} the waituntil statement is waiting for either @Lock@ to be available or for a value to be read from @Channel@ into @i@ and for @Future@ to be fulfilled. The semantics of the waituntil statement will be discussed in detail in the next section.
+\begin{figure}
+\begin{cfa}
+future(int) Future;
+channel(int) Channel;
+owner_lock Lock;
+int i = 0;
+waituntil( Lock ) { ... }
+or when( i == 0 ) waituntil( i << Channel ) { ... }
+and waituntil( Future ) { ... }
+\end{cfa}
+\caption{Example of \CFA's waituntil statement}
+\label{f:wu_example}
+\end{figure}
+\section{Waituntil Semantics}
+There are two parts of the waituntil semantics to discuss, the semantics of the statement itself, \ie @and@, @or@, @when@ guards, and @else@ semantics, and the semantics of how the waituntil interacts with types like channels, locks and futures.
+To start, the semantics of the statement itself will be discussed.
+\subsection{Waituntil Statement Semantics}
+The @or@ semantics are the most straightforward and nearly match those laid out in the ALT statement from Occam, the clauses have an exclusive-or relationship where the first one to be available will be run and only one clause is run.
+\CFA's @or@ semantics differ from ALT semantics in one respect, instead of randomly picking a clause when multiple are available, the clause that appears first in the order of clauses will be picked.
+\eg in the following example, if @foo@ and @bar@ are both available, @foo@ will always be selected since it comes first in the order of waituntil clauses.
+\begin{cfa}
+future(int) bar;
+future(int) foo;
+waituntil( foo ) { ... }
+or waituntil( bar ) { ... }
+\end{cfa}
+The @and@ semantics match the @and@ semantics used by \uC.
+When multiple clauses are joined by @and@, the waituntil will make a thread wait for all to be available, but will run the corresponding code blocks \emph{as they become available}.
+As @and@ clauses are made available, the thread will be woken to run those clauses' code blocks and then the thread will wait again until all clauses have been run.
+This allows work to be done in parallel while synchronizing over a set of resources, and furthermore gives a good reason to use the @and@ operator.
+If the @and@ operator waited for all clauses to be available before running, it would not provide much more use that just acquiring those resources one by one in subsequent lines of code.
+The @and@ operator binds more tightly than the @or@ operator.
+To give an @or@ operator higher precedence brackets can be used.
+\eg the following waituntil unconditionally waits for @C@ and one of either @A@ or @B@, since the @or@ is given higher precendence via brackets.
+\begin{cfa}
+(waituntil( A ) { ... }
+or waituntil( B ) { ... } )
+and waituntil( C ) { ... }
+\end{cfa}
+The guards in the waituntil statement are called @when@ clauses.
+The @when@ clause is passed a boolean expression.
+All the @when@ boolean expressions are evaluated before the waituntil statement is run.
+The guards in Occam's ALT effectively toggle clauses on and off, where a clause will only be evaluated and waited on if the corresponding guard is @true@.
+The guards in the waituntil statement operate the same way, but require some nuance since both @and@ and @or@ operators are supported.
+When a guard is false and a clause is removed, it can be thought of as removing that clause and its preceding operator from the statement.
+\eg in the following example the two waituntil statements are semantically the same.
+\begin{cfa}
+when(true) waituntil( A ) { ... }
+or when(false) waituntil( B ) { ... }
+and waituntil( C ) { ... }
+// ===
+waituntil( A ) { ... }
+and waituntil( C ) { ... }
+\end{cfa}
+The @else@ clause on the waituntil has identical semantics to the @else@ clause in Ada.
+If all resources are not immediately available and there is an @else@ clause, the @else@ clause is run and the thread will not block.
+\subsection{Waituntil Type Semantics}
+As described earlier, to support interaction with the waituntil statement a type must support the trait shown in Figure~\ref{f:wu_trait}.
+The waituntil statement expects types to register and unregister themselves via calls to @register_select@ and @unregister_select@ respectively.
+When a resource becomes available, @on_selected@ is run.
+Many types may not need @on_selected@, but it is provided since some types may need to check and set things before the resource can be accessed in the code block.
+The register/unregister routines in the trait return booleans.
+The return value of @register_select@ is @true@ if the resource is immediately available, and @false@ otherwise.
+The return value of @unregister_select@ is @true@ if the corresponding code block should be run after unregistration and @false@ otherwise.
+The routine @on_selected@, and the return value of @unregister_select@ were needed to support channels as a resource.
+More detail on channels and their interaction with waituntil will be discussed in Section~\ref{s:wu_chans}.
+\section{Waituntil Implementation}
+The waituntil statement is not inherently complex, and can be described as a few steps.
+The complexity of the statement comes from the consideration of race conditions and synchronization needed when supporting various primitives.
+The basic steps that the waituntil statement follows are the following.
+First the waituntil statement creates a @select_node@ per resource that is being waited on.
+The @select_node@ is an object that stores the waituntil data pertaining to one of the resources.
+Then, each @select_node@ is then registered with the corresponding resource.
+The thread executing the waituntil then enters a loop that will loop until the entire waituntil statement being satisfied.
+In each iteration of the loop the thread attempts to block.
+If any clauses are satified the block will fail and the thread will proceed, otherwise the block succeeds.
+After proceeding past the block all clauses are checked for completion and the completed clauses have their code blocks run.
+Once the thread escapes the loop, the @select_nodes@ are unregistered from the resources.
+In the case where the block suceeds, the thread will be woken by the thread that marks one of the resources as available.
+Pseudocode detailing these steps is presented in the following code block.
+\begin{cfa}
+select_nodes s[N]; // N select nodes
+for ( node in s )
+    register_select( resource, node );
+while( statement not satisfied ) {
+    // try to block
+    for ( resource in waituntil statement )
+        if ( resource is avail ) run code block
+}
+for ( node in s )
+    unregister_select( resource, node );
+\end{cfa}
+These steps give a basic, but mildly inaccurate overview of how the statement works.
+Digging into some parts of the implementation will shed light on more of the specifics and provide some accuracy.
+\subsection{Locks}
+Locks are one of the resources supported in the waituntil statement.
+When a thread waits on multiple locks via a waituntil, it enqueues a @select_node@ in each of the lock's waiting queues.
+When a @select_node@ reaches the front of the queue and gains ownership of a lock, the blocked thread is notified.
+The lock will be held until the node is unregistered.
+To prevent the waiting thread from holding many locks at once and potentially introducing a deadlock, the node is unregistered right after the corresponding code block is executed.
+This prevents deadlocks since the waiting thread will never hold a lock while waiting on another resource.
+As such the only nodes unregistered at the end are the ones that have not run.
+\subsection{Timeouts}
+Timeouts in the waituntil take the form of a duration being passed to a @sleep@ or @timeout@ call.
+An example is shown in the following code.
+\begin{cfa}
+waituntil( sleep( 1`ms ) ) {}
+waituntil( timeout( 1`s ) ) {} or waituntil( timeout( 2`s ) ) {}
+waituntil( timeout( 1`ns ) ) {} and waituntil( timeout( 2`s ) ) {}
+\end{cfa}
+The timeout implementation highlights a key part of the waituntil semantics, the expression is evaluated before the waituntil runs.
+As such calls to @sleep@ and @timeout@ do not block, but instead return a type that supports the @is_selectable@ trait.
+This mechanism is needed for types that want to support multiple operations such as channels that support reading and writing.
+\subsection{Channels}\label{s:wu_chans}
+To support both waiting on both reading and writing to channels, the opperators @?<<?@ and @?>>?@ are used to show reading and writing to a channel respectively, where the lefthand operand is the value and the righthand operand is the channel.
+Channels require significant complexity to wait on for a few reasons.
+The first reason is that reading or writing to a channel is a mutating operation.
+What this means is that if a read or write to a channel occurs, the state of the channel has changed.
+In comparison, for standard locks and futures, if a lock is acquired then released or a future is ready but not accessed, the states of the lock and the future are not modified.
+In this way if a waituntil over locks or futures have some resources available that were not consumed, it is not an issue.
+However, if a thread modifies a channel on behalf of a thread blocked on a waituntil statement, it is important that the corresponding waituntil code block is run, otherwise there is a potentially erroneous mismatch between the channel state and associated side effects.
+As such, the @unregister_select@ routine has a boolean return that is used by channels to indicate when the operation was completed but the block was not run yet.
+As such some channel code blocks may be run as part of the unregister.
+Furthermore if there are both @and@ and @or@ operators, the @or@ operators stop behaving like exclusive-or semantics since this race between operations and unregisters exists.
+It was deemed important that exclusive-or semantics were maintained when only @or@ operators were used, so this situation has been special-cased, and is handled by having all clauses race to set a value \emph{before} operating on the channel.
+This approach is infeasible in the case where @and@ and @or@ operators are used.
+To show this consider the following waituntil statement.
+\begin{cfa}
+waituntil( i >> A ) {} and waituntil( i >> B ) {}
+or waituntil( i >> C ) {} and waituntil( i >> D ) {}
+\end{cfa}
+If exclusive-or semantics were followed, this waituntil would only run the code blocks for @A@ and @B@, or the code blocks for @C@ and @D@.
+However, to race before operation completion in this case introduces a race whose complexity increases with the size of the waituntil statement.
+In the example above, for @i@ to be inserted into @C@, to ensure the exclusive-or it must be ensured that @i@ can also be inserted into @D@.
+Furthermore, the race for the @or@ would also need to be won.
+However, due to TOCTOU issues, one cannot know that all resources are available without acquiring all the internal locks of channels in the subtree.
+This is not a good solution for two reasons.
+It is possible that once all the locks are acquired that the subtree is not satisfied and they must all be released.
+This would incur high cost for signalling threads and also heavily increase contention on internal channel locks.
+Furthermore, the waituntil statement is polymorphic and can support resources that do not have internal locks, which also makes this approach infeasible.
+As such, the exclusive-or semantics are lost when using both @and@ and @or@ operators since they can not be supported without significant complexity and hits to waituntil statement performance.
+The mechanism by which the predicate of the waituntil is checked is discussed in more detail in Section~\ref{s:wu_guards}.
+Another consideration introduced by channels is that supporting both reading and writing to a channel in a waituntil means that one waituntil clause may be the notifier for another waituntil clause.
+This becomes a problem when dealing with the special-cased @or@ where the clauses need to win a race to operate on a channel.
+When you have both a special-case @or@ inserting on one thread and another special-case @or@ consuming is blocked on another thread there is not one but two races that need to be consolidated by the inserting thread.
+(The race can occur in the opposite case with a blocked producer and signalling consumer too.)
+For them to know that the insert succeeded, they need to win the race for their own waituntil and win the race for the other waituntil.
+Go solves this problem in their select statement by acquiring the internal locks of all channels before registering the select on the channels.
+This eliminates the race since no other threads can operate on the blocked channel since its lock will be held.
+This approach is not used in \CFA since the waituntil is polymorphic.
+Not all types in a waituntil have an internal lock, and when using non-channel types acquiring all the locks incurs extra uneeded overhead.
+Instead this race is consolidated in \CFA in two phases by having an intermediate pending status value for the race.
+This case is detectable, and if detected the thread attempting to signal will first race to set the race flag to be pending.
+If it succeeds, it then attempts to set the consumer's race flag to its success value.
+If the producer successfully sets the consumer race flag, then the operation can proceed, if not the signalling thread will set its own race flag back to the initial value.
+If any other threads attempt to set the producer's flag and see a pending value, they will wait until the value changes before proceeding to ensure that in the case that the producer fails, the signal will not be lost.
+This protocol ensures that signals will not be lost and that the two races can be resolved in a safe manner.
+Channels in \CFA have exception based shutdown mechanisms that the waituntil statement needs to support.
+These exception mechanisms were what brought in the @on_selected@ routine.
+This routine is needed by channels to detect if they are closed upon waking from a waituntil statement, to ensure that the appropriate behaviour is taken.
+\subsection{Guards and Statement Predicate}\label{s:wu_guards}
+Checking for when a synchronous multiplexing utility is done is trivial when it has an or/xor relationship, since any resource becoming available means that the blocked thread can proceed.
+In \uC and \CFA, their \gls{synch_multiplex} utilities involve both an @and@ and @or@ operator, which make the problem of checking for completion of the statement more difficult.
+In the \uC @_Select@ statement, they solve this problem by constructing a tree of the resources, where the internal nodes are operators and the leafs are the resources.
+The internal nodes also store the status of each of the subtrees beneath them.
+When resources become available, their status is modified and the status of the leaf nodes percolate into the internal nodes update the state of the statement.
+Once the root of the tree has both subtrees marked as @true@ then the statement is complete.
+As an optimization, when the internal nodes are updated, their subtrees marked as @true@ are effectively pruned and are not touched again.
+To support \uC's @_Select@ statement guards, the tree prunes the branch if the guard is false.
+The \CFA waituntil statement blocks a thread until a set of resources have become available that satisfy the underlying predicate.
+The waiting condition of the waituntil statement can be represented as a predicate over the resources, joined by the waituntil operators, where a resource is @true@ if it is available, and @false@ otherwise.
+In \CFA, this representation is used as the mechanism to check if a thread is done waiting on the waituntil.
+Leveraging the compiler, a routine is generated per waituntil that is passed the statuses of the resources and returns a boolean that is @true@ when the waituntil is done, and false otherwise.
+To support guards on the \CFA waituntil statement, the status of a resource disabled by a guard is set to ensure that the predicate function behaves as if that resource is no longer part of the predicate.
+In \uC's @_Select@, it supports operators both inside and outside the clauses of their statement.
+\eg in the following example the code blocks will run once their corresponding predicate inside the round braces is satisfied.
+% C_TODO put this is uC++ code style not cfa-style
+\begin{cfa}
+Future_ISM<int> A, B, C, D;
+_Select( A || B && C ) { ... }
+and _Select( D && E ) { ... }
+\end{cfa}
+This is more expressive that the waituntil statement in \CFA.
+In \CFA, since the waituntil statement supports more resources than just futures, implmenting operators inside clauses was avoided for a few reasons.
+As an example, suppose \CFA supported operators inside clauses and consider the code snippet in Figure~\ref{f:wu_inside_op}.
+\begin{figure}
+\begin{cfa}
+owner_lock A, B, C, D;
+waituntil( A && B ) { ... }
+or waituntil( C && D ) { ... }
+\end{cfa}
+\caption{Example of unsupported operators inside clauses in \CFA.}
+\label{f:wu_inside_op}
+\end{figure}
+If the waituntil in Figure~\ref{f:wu_inside_op} works with the same semantics as described and acquires each lock as it becomes available, it opens itself up to possible deadlocks since it is now holding locks and waiting on other resources.
+As such other semantics would be needed to ensure that this operation is safe.
+One possibility is to use \CC's @scoped_lock@ approach that was described in Section~\ref{s:DeadlockAvoidance}, however the potential for livelock leaves much to be desired.
+Another possibility would be to use resource ordering similar to \CFA's @mutex@ statement, but that alone is not sufficient if the resource ordering is not used everywhere.
+Additionally, using resource ordering could conflict with other semantics of the waituntil statement.
+To show this conflict, consider if the locks in Figure~\ref{f:wu_inside_op} were ordered @D@, @B@, @C@, @A@.
+If all the locks are available, it becomes complex to both respect the ordering of the waituntil in Figure~\ref{f:wu_inside_op} when choosing which code block to run and also respect the lock ordering of @D@, @B@, @C@, @A@ at the same time.
+One other way this could be implemented is to wait until all resources for a given clause are available before proceeding to acquire them, but this also quickly becomes a poor approach.
+This approach won't work due to TOCTOU issues, as it is not possible to ensure that the full set resources are available without holding them all first.
+Operators inside clauses in \CFA could potentially be implemented with careful circumvention of the problems involved, but it was not deemed an important feature when taking into account the runtime cost that would need to be paid to handle these situations.
+The problem of operators inside clauses also becomes a difficult issue to handle when supporting channels.
+If internal operators were supported, it would require some way to ensure that channels with internal operators are modified on if and only if the corresponding code block is run, but that is not feasible due to reasons described in the exclusive-or portion of Section~\ref{s:wu_chans}.
+\section{Waituntil Performance}
+The two \gls{synch_multiplex} utilities that are in the realm of comparability with the \CFA waituntil statement are the Go @select@ statement and the \uC @_Select@ statement.
+As such, two microbenchmarks are presented, one for Go and one for \uC to contrast the systems.
+The similar utilities discussed at the start of this chapter in C, Ada, Rust, \CC, and OCaml are either not meaningful or feasible to benchmark against.
+The select(2) and related utilities in C are not comparable since they are system calls that go into the kernel and operate on file descriptors, whereas the waituntil exists solely in userspace.
+Ada's @select@ only operates on methods, which is done in \CFA via the @waitfor@ utility so it is not feasible to benchmark against the @waituntil@, which cannot wait on the same resource.
+Rust and \CC only offer a busy-wait based approach which is not meaningly comparable to a blocking approach.
+OCaml's @select@ waits on channels that are not comparable with \CFA and Go channels, which makes the OCaml @select@ infeasible to compare it with Go's @select@ and \CFA's @waituntil@.
+Given the differences in features, polymorphism, and expressibility between the waituntil and @select@, and @_Select@, the aim of the microbenchmarking in this chapter is to show that these implementations lie in the same realm of performance, not to pick a winner.
+\subsection{Channel Benchmark}
+The channel microbenchmark compares \CFA's waituntil and Go's select, where the resource being waited on is a set of channels.
+%C_TODO explain benchmark
+%C_TODO show results
+%C_TODO discuss results
+\subsection{Future Benchmark}
+The future benchmark compares \CFA's waituntil with \uC's @_Select@, with both utilities waiting on futures.
+%C_TODO explain benchmark
+%C_TODO show results
+%C_TODO discuss results

doc/theses/colby_parsons_MMAth/thesis.tex

-              r2b78949
+              r8a930c03
     colorlinks=true,        % false: boxed links; true: colored links
     linkcolor=blue,         % color of internal links
     citecolor=blue,        % color of links to bibliography
+    citecolor=blue,         % color of links to bibliography
     filecolor=magenta,      % color of file links
+    urlcolor=cyan           % color of external links
+    urlcolor=cyan,          % color of external links
+    breaklinks=true
+}
 \ifthenelse{\boolean{PrintVersion}}{   % for improved print quality, change some hyperref options
 …
 % \usepackage[acronym]{glossaries}
 \usepackage[automake,toc,abbreviations]{glossaries-extra} % Exception to the rule of hyperref being the last add-on package
+\renewcommand*{\glstextformat}[1]{\textcolor{black}{#1}}
 % If glossaries-extra is not in your LaTeX distribution, get it from CTAN (http://ctan.org/pkg/glossaries-extra),
 % although it's supposed to be in both the TeX Live and MikTeX distributions. There are also documentation and

doc/user/figures/EHMHierarchy.fig

-              r2b78949
+              r8a930c03
 1 1.00 60.00 90.00
 1950 4950 1725
 1 0 50 -1 0 13 0.0000 2 135 225 1950 1650 IO\001
 1 0 50 -1 0 13 0.0000 2 135 915 4950 1650 Arithmetic\001
 1 0 50 -1 0 13 0.0000 2 150 330 1350 2100 File\001
 1 0 50 -1 0 13 0.0000 2 135 735 2550 2100 Network\001
 1 0 50 -1 0 13 0.0000 2 180 1215 3750 2100 DivideByZero\001
 1 0 50 -1 0 13 0.0000 2 150 810 4950 2100 Overflow\001
 1 0 50 -1 0 13 0.0000 2 150 915 6000 2100 Underflow\001
 1 0 50 -1 0 13 0.0000 2 180 855 3450 1200 Exception\001
+1 0 50 -1 0 12 0.0000 2 135 225 1950 1650 IO\001
+1 0 50 -1 0 12 0.0000 2 135 915 4950 1650 Arithmetic\001
+1 0 50 -1 0 12 0.0000 2 150 330 1350 2100 File\001
+1 0 50 -1 0 12 0.0000 2 135 735 2550 2100 Network\001
+1 0 50 -1 0 12 0.0000 2 180 1215 3750 2100 DivideByZero\001
+1 0 50 -1 0 12 0.0000 2 150 810 4950 2100 Overflow\001
+1 0 50 -1 0 12 0.0000 2 150 915 6000 2100 Underflow\001
+1 0 50 -1 0 12 0.0000 2 180 855 3450 1200 Exception\001

doc/user/user.tex

-              r2b78949
+              r8a930c03
 %% Created On       : Wed Apr  6 14:53:29 2016
 %% Last Modified By : Peter A. Buhr
 %% Last Modified On : Mon Aug 22 23:43:30 2022
 %% Update Count     : 5503
+%% Last Modified On : Mon Jun  5 21:18:29 2023
+%% Update Count     : 5521
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 …
 \huge \CFA Team (past and present) \medskip \\
 \Large Andrew Beach, Richard Bilson, Michael Brooks, Peter A. Buhr, Thierry Delisle, \smallskip \\
 \Large Glen Ditchfield, Rodolfo G. Esteves, Aaron Moss, Colby Parsons, Rob Schluntz, \smallskip \\
 \Large Fangren Yu, Mubeen Zulfiqar
+\Large Glen Ditchfield, Rodolfo G. Esteves, Jiada Liang, Aaron Moss, Colby Parsons \smallskip \\
+\Large Rob Schluntz, Fangren Yu, Mubeen Zulfiqar
 }% author
 …
 Like \Index*[C++]{\CC{}}, there may be both old and new ways to achieve the same effect.
 For example, the following programs compare the C, \CFA, and \CC I/O mechanisms, where the programs output the same result.
 \begin{flushleft}
 \begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}}
 \multicolumn{1}{@{}c@{\hspace{1em}}}{\textbf{C}}        & \multicolumn{1}{c}{\textbf{\CFA}}     & \multicolumn{1}{c@{}}{\textbf{\CC}}   \\
+\begin{center}
+\begin{tabular}{@{}lll@{}}
+\multicolumn{1}{@{}c}{\textbf{C}}       & \multicolumn{1}{c}{\textbf{\CFA}}     & \multicolumn{1}{c@{}}{\textbf{\CC}}   \\
 \begin{cfa}[tabsize=3]
 #include <stdio.h>$\indexc{stdio.h}$
 …
 \end{cfa}
 \end{tabular}
 \end{flushleft}
+\end{center}
 While \CFA I/O \see{\VRef{s:StreamIOLibrary}} looks similar to \Index*[C++]{\CC{}}, there are important differences, such as automatic spacing between variables and an implicit newline at the end of the expression list, similar to \Index*{Python}~\cite{Python}.
 …
 still works.
 Nevertheless, reversing the default action would have a non-trivial effect on case actions that compound, such as the above example of processing shell arguments.
 Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called \Indexc{choose}, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword \Indexc{fallthrough}/\Indexc{fallthru}, \eg:
+Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called \Indexc{choose}, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword \Indexc{fallthrough}/\-\Indexc{fallthru}, \eg:
 \begin{cfa}
 ®choose® ( i ) {
 …
 \end{cfa}
 \end{itemize}
 \R{Warning}: specifying the down-to range maybe unexcepted because the loop control \emph{implicitly} switches the L and H values (and toggles the increment/decrement for I):
+\R{Warning}: specifying the down-to range maybe unexpected because the loop control \emph{implicitly} switches the L and H values (and toggles the increment/decrement for I):
 \begin{cfa}
 for ( i; 1 ~ 10 )       ${\C[1.5in]{// up range}$
 …
 for ( i; ®10 -~ 1® )    ${\C{// \R{WRONG down range!}}\CRT}$
 \end{cfa}
 The reason for this sematics is that the range direction can be toggled by adding/removing the minus, ©'-'©, versus interchanging the L and H expressions, which has a greater chance of introducing errors.
+The reason for this semantics is that the range direction can be toggled by adding/removing the minus, ©'-'©, versus interchanging the L and H expressions, which has a greater chance of introducing errors.
 …
 Days days = Mon; // enumeration type declaration and initialization
 \end{cfa}
+The set of enums are injected into the variable namespace at the definition scope.
+Hence, enums may be overloaded with enum/variable/function names.
+\begin{cfa}
+The set of enums is injected into the variable namespace at the definition scope.
+Hence, enums may be overloaded with variable, enum, and function names.
+\begin{cfa}
+int Foo;                        $\C{// type/variable separate namespaces}$
 enum Foo { Bar };
 enum Goo { Bar };       $\C[1.75in]{// overload Foo.Bar}$
-int Foo;                        $\C{// type/variable separate namespace}$
 double Bar;                     $\C{// overload Foo.Bar, Goo.Bar}\CRT$
 \end{cfa}
 …
 Hence, the value of enum ©Mon© is 0, ©Tue© is 1, ...\,, ©Sun© is 6.
 If an enum value is specified, numbering continues by one from that value for subsequent unnumbered enums.
 If an enum value is an expression, the compiler performs constant-folding to obtain a constant value.
+If an enum value is a \emph{constant} expression, the compiler performs constant-folding to obtain a constant value.
 \CFA allows other integral types with associated values.
 …
 \begin{cfa}
 // non-integral numeric
 enum( ®double® ) Math { PI_2 = 1.570796, PI = 3.141597,  E = 2.718282 }
+enum( ®double® ) Math { PI_2 = 1.570796, PI = 3.141597, E = 2.718282 }
 // pointer
 enum( ®char *® ) Name { Fred = "Fred",  Mary = "Mary",  Jane = "Jane" };
+enum( ®char *® ) Name { Fred = "Fred",  Mary = "Mary", Jane = "Jane" };
 int i, j, k;
 enum( ®int *® ) ptr { I = &i,  J = &j,  K = &k };
 enum( ®int &® ) ref { I = i,  J = j,  K = k };
+enum( ®int &® ) ref { I = i,   J = j,   K = k };
 // tuple
 enum( ®[int, int]® ) { T = [ 1, 2 ] };
 …
 \begin{cfa}
 enum( char * ) Name2 { ®inline Name®, Jack = "Jack", Jill = "Jill" };
 enum ®/* inferred */®  Name3 { ®inline Name2®, Sue = "Sue", Tom = "Tom" };
+enum ®/* inferred */® Name3 { ®inline Name2®, Sue = "Sue", Tom = "Tom" };
 \end{cfa}
 Enumeration ©Name2© inherits all the enums and their values from enumeration ©Name© by containment, and a ©Name© enumeration is a subtype of enumeration ©Name2©.
 …
                                    "[ output-file (default stdout) ] ]";
                 } // choose
         } catch( ®Open_Failure® * ex; ex->istream == &in ) {
+        } catch( ®open_failure® * ex; ex->istream == &in ) { $\C{// input file errors}$
                 ®exit® | "Unable to open input file" | argv[1];
         } catch( ®Open_Failure® * ex; ex->ostream == &out ) {
+        } catch( ®open_failure® * ex; ex->ostream == &out ) { $\C{// output file errors}$
                 ®close®( in );                                          $\C{// optional}$
                 ®exit® | "Unable to open output file" | argv[2];
 …
 \item
 \Indexc{sepDisable}\index{manipulator!sepDisable@©sepDisable©} and \Indexc{sepEnable}\index{manipulator!sepEnable@©sepEnable©} toggle printing the separator.
+\Indexc{sepDisable}\index{manipulator!sepDisable@©sepDisable©} and \Indexc{sepEnable}\index{manipulator!sepEnable@©sepEnable©} globally toggle printing the separator.
 \begin{cfa}[belowskip=0pt]
 sout | sepDisable | 1 | 2 | 3; $\C{// turn off implicit separator}$
 …
 \item
 \Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} toggle printing the separator with respect to the next printed item, and then return to the global separator setting.
+\Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} locally toggle printing the separator with respect to the next printed item, and then return to the global separator setting.
 \begin{cfa}[belowskip=0pt]
 sout | 1 | sepOff | 2 | 3; $\C{// turn off implicit separator for the next item}$
 …
 \end{cfa}
 Note, a terminating ©nl© is merged (overrides) with the implicit newline at the end of the ©sout© expression, otherwise it is impossible to to print a single newline
+Note, a terminating ©nl© is merged (overrides) with the implicit newline at the end of the ©sout© expression, otherwise it is impossible to print a single newline
 \item
 \Indexc{nlOn}\index{manipulator!nlOn@©nlOn©} implicitly prints a newline at the end of each output expression.

Context Navigation

Legend:

doc/bibliography/pl.bib

doc/papers/llheap/Paper.tex

doc/papers/llheap/figures/AllocatorComponents.fig

doc/theses/colby_parsons_MMAth/Makefile

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/balance.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/dynamic.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/executor.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/matrix.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/repeat.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/cfa/static.cfa

doc/theses/colby_parsons_MMAth/benchmarks/actors/plotData.py

doc/theses/colby_parsons_MMAth/benchmarks/channels/plotData.py

doc/theses/colby_parsons_MMAth/benchmarks/mutex_stmt/plotData.py

doc/theses/colby_parsons_MMAth/code/basic_actor_example.cfa

doc/theses/colby_parsons_MMAth/glossary.tex

doc/theses/colby_parsons_MMAth/local.bib

doc/theses/colby_parsons_MMAth/style/style.tex

doc/theses/colby_parsons_MMAth/text/channels.tex

doc/theses/colby_parsons_MMAth/text/waituntil.tex

doc/theses/colby_parsons_MMAth/thesis.tex

doc/user/figures/EHMHierarchy.fig

doc/user/user.tex

Download in other formats: