Index: doc/theses/colby_parsons_MMAth/style/style.tex =================================================================== --- doc/theses/colby_parsons_MMAth/style/style.tex (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ doc/theses/colby_parsons_MMAth/style/style.tex (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -3,5 +3,15 @@ \lstset{language=CFA} % default language +\newcommand{\newtermFont}{\emph} +\newcommand{\Newterm}[1]{\newtermFont{#1}} + \newcommand{\code}[1]{\lstinline[language=CFA]{#1}} \newcommand{\uC}{$\mu$\CC} +\newcommand{\PAB}[1]{{\color{red}PAB: #1}} +\newsavebox{\myboxA} % used with subfigure +\newsavebox{\myboxB} + +\lstnewenvironment{java}[1][] +{\lstset{language=java,moredelim=**[is][\protect\color{red}]{@}{@}}\lstset{#1}} +{} Index: doc/theses/colby_parsons_MMAth/text/actors.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/actors.tex (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ doc/theses/colby_parsons_MMAth/text/actors.tex (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -90,31 +90,31 @@ \begin{cfa} struct derived_actor { - inline actor; // Plan-9 C inheritance + inline actor; // Plan-9 C inheritance }; void ?{}( derived_actor & this ) { // Default ctor - ((actor &)this){}; // Call to actor ctor + ((actor &)this){}; // Call to actor ctor } struct derived_msg { - inline message; // Plan-9 C nominal inheritance - char word[12]; + inline message; // Plan-9 C nominal inheritance + char word[12]; }; void ?{}( derived_msg & this, char * new_word ) { // Overloaded ctor - ((message &) this){ Nodelete }; // Passing allocation to ctor - strcpy(this.word, new_word); + ((message &) this){ Nodelete }; // Passing allocation to ctor + strcpy(this.word, new_word); } Allocation receive( derived_actor & receiver, derived_msg & msg ) { - printf("The message contained the string: %s\n", msg.word); - return Finished; // Return finished since actor is done + printf("The message contained the string: %s\n", msg.word); + return Finished; // Return finished since actor is done } int main() { - start_actor_system(); // Sets up executor - derived_actor my_actor; - derived_msg my_msg{ "Hello World" }; // Constructor call - my_actor << my_msg; // Send message via left shift operator - stop_actor_system(); // Waits until actors are finished - return 0; + start_actor_system(); // Sets up executor + derived_actor my_actor; + derived_msg my_msg{ "Hello World" }; // Constructor call + my_actor << my_msg; // Send message via left shift operator + stop_actor_system(); // Waits until actors are finished + return 0; } \end{cfa} @@ -229,5 +229,5 @@ \section{Envelopes}\label{s:envelope} In actor systems messages are sent and received by actors. -When a actor receives a message it executes its behaviour that is associated with that message type. +When a actor receives a message it executes its behaviour that is associated with that message type. However the unit of work that stores the message, the receiving actor's address, and other pertinent information needs to persist between send and the receive. Furthermore the unit of work needs to be able to be stored in some fashion, usually in a queue, until it is executed by an actor. @@ -301,5 +301,5 @@ While other systems are concerned with stealing actors, the \CFA actor system steals queues. This is a result of \CFA's use of the inverted actor system. - The goal of the \CFA actor work stealing mechanism is to have a zero-victim-cost stealing mechanism. +The goal of the \CFA actor work stealing mechanism is to have a zero-victim-cost stealing mechanism. This does not means that stealing has no cost. This goal is to ensure that stealing work does not impact the performance of victim workers. @@ -369,14 +369,14 @@ \begin{cfa} -void swap( uint victim_idx, uint my_idx ) { - // Step 0: - work_queue * my_queue = request_queues[my_idx]; - work_queue * vic_queue = request_queues[victim_idx]; - // Step 2: - request_queues[my_idx] = 0p; - // Step 3: - request_queues[victim_idx] = my_queue; - // Step 4: - request_queues[my_idx] = vic_queue; +void swap( uint victim_idx, uint my_idx ) { + // Step 0: + work_queue * my_queue = request_queues[my_idx]; + work_queue * vic_queue = request_queues[victim_idx]; + // Step 2: + request_queues[my_idx] = 0p; + // Step 3: + request_queues[victim_idx] = my_queue; + // Step 4: + request_queues[my_idx] = vic_queue; } \end{cfa} @@ -389,41 +389,41 @@ // This routine is atomic bool CAS( work_queue ** ptr, work_queue ** old, work_queue * new ) { - if ( *ptr != *old ) - return false; - *ptr = new; - return true; + if ( *ptr != *old ) + return false; + *ptr = new; + return true; } bool try_swap_queues( worker & this, uint victim_idx, uint my_idx ) with(this) { - // Step 0: - // request_queues is the shared array of all sharded queues - work_queue * my_queue = request_queues[my_idx]; - work_queue * vic_queue = request_queues[victim_idx]; - - // Step 1: - // If either queue is 0p then they are in the process of being stolen - // 0p is CForAll's equivalent of C++'s nullptr - if ( vic_queue == 0p ) return false; - - // Step 2: - // Try to set thief's queue ptr to be 0p. - // If this CAS fails someone stole thief's queue so return false - if ( !CAS( &request_queues[my_idx], &my_queue, 0p ) ) - return false; - - // Step 3: - // Try to set victim queue ptr to be thief's queue ptr. - // If it fails someone stole the other queue, so fix up then return false - if ( !CAS( &request_queues[victim_idx], &vic_queue, my_queue ) ) { - request_queues[my_idx] = my_queue; // reset queue ptr back to prev val - return false; - } - - // Step 4: - // Successfully swapped. - // Thief's ptr is 0p so no one will touch it - // Write back without CAS is safe - request_queues[my_idx] = vic_queue; - return true; + // Step 0: + // request_queues is the shared array of all sharded queues + work_queue * my_queue = request_queues[my_idx]; + work_queue * vic_queue = request_queues[victim_idx]; + + // Step 1: + // If either queue is 0p then they are in the process of being stolen + // 0p is CForAll's equivalent of C++'s nullptr + if ( vic_queue == 0p ) return false; + + // Step 2: + // Try to set thief's queue ptr to be 0p. + // If this CAS fails someone stole thief's queue so return false + if ( !CAS( &request_queues[my_idx], &my_queue, 0p ) ) + return false; + + // Step 3: + // Try to set victim queue ptr to be thief's queue ptr. + // If it fails someone stole the other queue, so fix up then return false + if ( !CAS( &request_queues[victim_idx], &vic_queue, my_queue ) ) { + request_queues[my_idx] = my_queue; // reset queue ptr back to prev val + return false; + } + + // Step 4: + // Successfully swapped. + // Thief's ptr is 0p so no one will touch it + // Write back without CAS is safe + request_queues[my_idx] = vic_queue; + return true; } \end{cfa}\label{c:swap} @@ -706,9 +706,9 @@ \label{t:StaticActorMessagePerformance} \begin{tabular}{*{5}{r|}r} - & \multicolumn{1}{c|}{\CFA (100M)} & \multicolumn{1}{c|}{CAF (10M)} & \multicolumn{1}{c|}{Akka (100M)} & \multicolumn{1}{c|}{\uC (100M)} & \multicolumn{1}{c@{}}{ProtoActor (100M)} \\ - \hline - AMD & \input{data/pykeSendStatic} \\ - \hline - Intel & \input{data/nasusSendStatic} + & \multicolumn{1}{c|}{\CFA (100M)} & \multicolumn{1}{c|}{CAF (10M)} & \multicolumn{1}{c|}{Akka (100M)} & \multicolumn{1}{c|}{\uC (100M)} & \multicolumn{1}{c@{}}{ProtoActor (100M)} \\ + \hline + AMD & \input{data/pykeSendStatic} \\ + \hline + Intel & \input{data/nasusSendStatic} \end{tabular} @@ -719,9 +719,9 @@ \begin{tabular}{*{5}{r|}r} - & \multicolumn{1}{c|}{\CFA (20M)} & \multicolumn{1}{c|}{CAF (2M)} & \multicolumn{1}{c|}{Akka (2M)} & \multicolumn{1}{c|}{\uC (20M)} & \multicolumn{1}{c@{}}{ProtoActor (2M)} \\ - \hline - AMD & \input{data/pykeSendDynamic} \\ - \hline - Intel & \input{data/nasusSendDynamic} + & \multicolumn{1}{c|}{\CFA (20M)} & \multicolumn{1}{c|}{CAF (2M)} & \multicolumn{1}{c|}{Akka (2M)} & \multicolumn{1}{c|}{\uC (20M)} & \multicolumn{1}{c@{}}{ProtoActor (2M)} \\ + \hline + AMD & \input{data/pykeSendDynamic} \\ + \hline + Intel & \input{data/nasusSendDynamic} \end{tabular} \end{table} @@ -745,5 +745,5 @@ In the static send benchmark all systems except CAF have static send costs that are in the same ballpark, only varying by ~70ns. In the dynamic send benchmark all systems experience slower message sends, as expected due to the extra allocations. -However, Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA. +However, Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA. This is likely a result of Akka and ProtoActor's garbage collection, which can suffer from hits in performance for allocation heavy workloads, whereas \uC and \CFA have explicit allocation/deallocation. @@ -753,35 +753,27 @@ \begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasusCFABalance-One.pgf}} - \subcaption{AMD \CFA Balance-One Benchmark} - \label{f:BalanceOneAMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pykeCFABalance-One.pgf}} - \subcaption{Intel \CFA Balance-One Benchmark} - \label{f:BalanceOneIntel} - \end{subfigure} - \caption{The balance-one benchmark comparing stealing heuristics (lower is better).} -\end{figure} - -\begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasusCFABalance-Multi.pgf}} - \subcaption{AMD \CFA Balance-Multi Benchmark} - \label{f:BalanceMultiAMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pykeCFABalance-Multi.pgf}} - \subcaption{Intel \CFA Balance-Multi Benchmark} - \label{f:BalanceMultiIntel} - \end{subfigure} - \caption{The balance-multi benchmark comparing stealing heuristics (lower is better).} + \centering + \subfloat[AMD \CFA Balance-One Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFABalance-One.pgf}} + \label{f:BalanceOneAMD} + } + \subfloat[Intel \CFA Balance-One Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFABalance-One.pgf}} + \label{f:BalanceOneIntel} + } + \caption{The balance-one benchmark comparing stealing heuristics (lower is better).} +\end{figure} + +\begin{figure} + \centering + \subfloat[AMD \CFA Balance-Multi Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFABalance-Multi.pgf}} + \label{f:BalanceMultiAMD} + } + \subfloat[Intel \CFA Balance-Multi Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFABalance-Multi.pgf}} + \label{f:BalanceMultiIntel} + } + \caption{The balance-multi benchmark comparing stealing heuristics (lower is better).} \end{figure} @@ -817,18 +809,14 @@ \begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasusExecutor.pgf}} - \subcaption{AMD Executor Benchmark} - \label{f:ExecutorAMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pykeExecutor.pgf}} - \subcaption{Intel Executor Benchmark} - \label{f:ExecutorIntel} - \end{subfigure} - \caption{The executor benchmark comparing actor systems (lower is better).} + \centering + \subfloat[AMD Executor Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusExecutor.pgf}} + \label{f:ExecutorAMD} + } + \subfloat[Intel Executor Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeExecutor.pgf}} + \label{f:ExecutorIntel} + } + \caption{The executor benchmark comparing actor systems (lower is better).} \end{figure} @@ -840,16 +828,14 @@ \begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasusCFAExecutor.pgf}} - \subcaption{AMD \CFA Executor Benchmark}\label{f:cfaExecutorAMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pykeCFAExecutor.pgf}} - \subcaption{Intel \CFA Executor Benchmark}\label{f:cfaExecutorIntel} - \end{subfigure} - \caption{Executor benchmark comparing \CFA stealing heuristics (lower is better).} + \centering + \subfloat[AMD \CFA Executor Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFAExecutor.pgf}} + \label{f:cfaExecutorAMD} + } + \subfloat[Intel \CFA Executor Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFAExecutor.pgf}} + \label{f:cfaExecutorIntel} + } + \caption{Executor benchmark comparing \CFA stealing heuristics (lower is better).} \end{figure} @@ -857,16 +843,14 @@ \begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasusRepeat.pgf}} - \subcaption{AMD Repeat Benchmark}\label{f:RepeatAMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pykeRepeat.pgf}} - \subcaption{Intel Repeat Benchmark}\label{f:RepeatIntel} - \end{subfigure} - \caption{The repeat benchmark comparing actor systems (lower is better).} + \centering + \subfloat[AMD Repeat Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusRepeat.pgf}} + \label{f:RepeatAMD} + } + \subfloat[Intel Repeat Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeRepeat.pgf}} + \label{f:RepeatIntel} + } + \caption{The repeat benchmark comparing actor systems (lower is better).} \end{figure} @@ -881,16 +865,14 @@ \begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasusCFARepeat.pgf}} - \subcaption{AMD \CFA Repeat Benchmark}\label{f:cfaRepeatAMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pykeCFARepeat.pgf}} - \subcaption{Intel \CFA Repeat Benchmark}\label{f:cfaRepeatIntel} - \end{subfigure} - \caption{The repeat benchmark comparing \CFA stealing heuristics (lower is better).} + \centering + \subfloat[AMD \CFA Repeat Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFARepeat.pgf}} + \label{f:cfaRepeatAMD} + } + \subfloat[Intel \CFA Repeat Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFARepeat.pgf}} + \label{f:cfaRepeatIntel} + } + \caption{The repeat benchmark comparing \CFA stealing heuristics (lower is better).} \end{figure} @@ -913,17 +895,17 @@ \begin{table}[t] - \centering - \setlength{\extrarowheight}{2pt} - \setlength{\tabcolsep}{5pt} - - \caption{Executor Program Memory High Watermark} - \label{t:ExecutorMemory} - \begin{tabular}{*{5}{r|}r} - & \multicolumn{1}{c|}{\CFA} & \multicolumn{1}{c|}{CAF} & \multicolumn{1}{c|}{Akka} & \multicolumn{1}{c|}{\uC} & \multicolumn{1}{c@{}}{ProtoActor} \\ - \hline - AMD & \input{data/pykeExecutorMem} \\ - \hline - Intel & \input{data/nasusExecutorMem} - \end{tabular} + \centering + \setlength{\extrarowheight}{2pt} + \setlength{\tabcolsep}{5pt} + + \caption{Executor Program Memory High Watermark} + \label{t:ExecutorMemory} + \begin{tabular}{*{5}{r|}r} + & \multicolumn{1}{c|}{\CFA} & \multicolumn{1}{c|}{CAF} & \multicolumn{1}{c|}{Akka} & \multicolumn{1}{c|}{\uC} & \multicolumn{1}{c@{}}{ProtoActor} \\ + \hline + AMD & \input{data/pykeExecutorMem} \\ + \hline + Intel & \input{data/nasusExecutorMem} + \end{tabular} \end{table} @@ -951,30 +933,30 @@ \begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasusMatrix.pgf}} - \subcaption{AMD Matrix Benchmark}\label{f:MatrixAMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pykeMatrix.pgf}} - \subcaption{Intel Matrix Benchmark}\label{f:MatrixIntel} - \end{subfigure} - \caption{The matrix benchmark comparing actor systems (lower is better).} -\end{figure} - -\begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasusCFAMatrix.pgf}} - \subcaption{AMD \CFA Matrix Benchmark}\label{f:cfaMatrixAMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pykeCFAMatrix.pgf}} - \subcaption{Intel \CFA Matrix Benchmark}\label{f:cfaMatrixIntel} - \end{subfigure} - \caption{The matrix benchmark comparing \CFA stealing heuristics (lower is better).} -\end{figure} + \centering + \subfloat[AMD Matrix Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusMatrix.pgf}} + \label{f:MatrixAMD} + } + \subfloat[Intel Matrix Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeMatrix.pgf}} + \label{f:MatrixIntel} + } + \caption{The matrix benchmark comparing actor systems (lower is better).} +\end{figure} + +\begin{figure} + \centering + \subfloat[AMD \CFA Matrix Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasusCFAMatrix.pgf}} + \label{f:cfaMatrixAMD} + } + \subfloat[Intel \CFA Matrix Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pykeCFAMatrix.pgf}} + \label{f:cfaMatrixIntel} + } + \caption{The matrix benchmark comparing \CFA stealing heuristics (lower is better).} +\end{figure} + +% Local Variables: % +% tab-width: 4 % +% End: % Index: doc/theses/colby_parsons_MMAth/text/channels.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/channels.tex (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ doc/theses/colby_parsons_MMAth/text/channels.tex (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -5,76 +5,76 @@ % ====================================================================== -Channels were first introduced by Hoare in his paper Communicating Sequentual Processes~\cite{Hoare78}, where he proposes a concurrent language that communicates across processes using input/output channels to send data. -Channels are a concurrent language feature used to perform message passing concurrency, a model of concurrency where threads communicate by sending data as messages, and synchronizing via the message passing mechanism. -This is an alternative to shared memory concurrency, where threads can communicate directly by changing shared memory state. -Most modern concurrent programming languages do not subscribe to just one style of communication between threads, and provide features that support both. +Channels were first introduced by Hoare in his paper Communicating Sequentual Processes~\cite{Hoare78}, where he proposes a concurrent language that communicates across processes using input/output channels to send data. +Channels are a concurrent language feature used to perform message passing concurrency, a model of concurrency where threads communicate by sending data as messages, and synchronizing via the message passing mechanism. +This is an alternative to shared memory concurrency, where threads can communicate directly by changing shared memory state. +Most modern concurrent programming languages do not subscribe to just one style of communication between threads, and provide features that support both. Channels as a programming language feature has been popularized in recent years due to the language Go, which encourages the use of channels as its fundamental concurrent feature. \section{Producer-Consumer Problem} -Most channels in modern programming languages are built on top of a shared memory buffer. -While it is possible to create a channel that contains an unbounded buffer, most implementations opt to only support a fixed size channel, where the size is given at the time of channel creation. -This turns the implementation of a channel into the producer-consumer problem. -The producer-consumer problem, also known as the bounded buffer problem, was introduced by Dijkstra in his book Cooperating Sequential Processes\cite{Dijkstra65}. -In the problem threads interact with the buffer in two ways, either consuming values by removing them from the buffer, or producing values and inserting them in the buffer. -The buffer needs to be protected from concurrent access since each item in the buffer should only be produced and consumed once. +Most channels in modern programming languages are built on top of a shared memory buffer. +While it is possible to create a channel that contains an unbounded buffer, most implementations opt to only support a fixed size channel, where the size is given at the time of channel creation. +This turns the implementation of a channel into the producer-consumer problem. +The producer-consumer problem, also known as the bounded buffer problem, was introduced by Dijkstra in his book Cooperating Sequential Processes\cite{Dijkstra65}. +In the problem threads interact with the buffer in two ways, either consuming values by removing them from the buffer, or producing values and inserting them in the buffer. +The buffer needs to be protected from concurrent access since each item in the buffer should only be produced and consumed once. Additionally, a consumer can only remove from a non-empty buffer and a producer can only insert into a non-full buffer. \section{First-Come First-Served} -The channel implementations that will be discussed are \gls{fcfs}. -This term was defined by Lamport~\cite{Lamport74}. -\gls{fcfs} is defined in relation to a doorway~\cite[p.~330]{Lamport86II}, which is the point at which an ordering among threads can be established. -Given this doorway, a critical section is said to be \gls{fcfs}, if threads access the shared resource in the order they proceed through the doorway. -\gls{fcfs} is a fairness property which prevents unequal access to the shared resource and prevents starvation, however it can come at a cost. -Implementing an algorithm with \gls{fcfs} can lead to double blocking, where entering threads may need to block to allow other threads to proceed first, resulting in blocking both inside and outside the doorway. +The channel implementations that will be discussed are \gls{fcfs}. +This term was defined by Lamport~\cite{Lamport74}. +\gls{fcfs} is defined in relation to a doorway~\cite[p.~330]{Lamport86II}, which is the point at which an ordering among threads can be established. +Given this doorway, a critical section is said to be \gls{fcfs}, if threads access the shared resource in the order they proceed through the doorway. +\gls{fcfs} is a fairness property which prevents unequal access to the shared resource and prevents starvation, however it can come at a cost. +Implementing an algorithm with \gls{fcfs} can lead to double blocking, where entering threads may need to block to allow other threads to proceed first, resulting in blocking both inside and outside the doorway. As such algorithms that are not \gls{fcfs} may be more performant but that performance comes with the downside of likely introducing starvation and unfairness. \section{Channel Implementation} -The channel implementation in \CFA is a near carbon copy of the Go implementation. -Experimentation was conducted that varied the producer-consumer problem algorithm and lock type used inside the channel. -With the exception of non-\gls{fcfs} algorithms, no algorithm or lock usage in the channel implementation was found to be consistently more performant that Go's choice of algorithm and lock implementation. +The channel implementation in \CFA is a near carbon copy of the Go implementation. +Experimentation was conducted that varied the producer-consumer problem algorithm and lock type used inside the channel. +With the exception of non-\gls{fcfs} algorithms, no algorithm or lock usage in the channel implementation was found to be consistently more performant that Go's choice of algorithm and lock implementation. As such the research contributions added by \CFA's channel implementation lie in the realm of safety and productivity features. \section{Safety and Productivity} -Channels in \CFA come with safety and productivity features to aid users. +Channels in \CFA come with safety and productivity features to aid users. The features include the following. \begin{itemize} -\item Toggle-able statistic collection on channel behvaiour that counts channel operations, and the number of the operations that block. +\item Toggle-able statistic collection on channel behvaiour that counts channel operations, and the number of the operations that block. Tracking blocking operations helps users tune their channel size or channel usage when the channel is used for buffering, where the aim is to have as few blocking operations as possible. -\item Deadlock detection on deallocation of the channel. +\item Deadlock detection on deallocation of the channel. If any threads are blocked inside the channel when it terminates it is detected and informs the user, as this would cause a deadlock. -\item A \code{flush} routine that delivers copies of an element to all waiting consumers, flushing the buffer. -Programmers can use this to easily to broadcast data to multiple consumers. +\item A \code{flush} routine that delivers copies of an element to all waiting consumers, flushing the buffer. +Programmers can use this to easily to broadcast data to multiple consumers. Additionally, the \code{flush} routine is more performant then looping around the \code{insert} operation since it can deliver the elements without having to reaquire mutual exclusion for each element sent. \end{itemize} -The other safety and productivity feature of \CFA channels deals with concurrent termination. -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 which 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 off a channel can block. +The other safety and productivity feature of \CFA channels deals with concurrent termination. +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 which 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 off 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. % C_TODO: add reference to select chapter, add citation to go channels info -Go channels provide a set of tools to help with concurrent shutdown. -Channels in Go have a \code{close} operation and a \code{select} statement that both can be used to help threads terminate. -The \code{select} statement will be discussed in \ref{}, where \CFA's \code{waituntil} statement will be compared with the Go \code{select} statement. -The \code{close} operation on a channel in Go changes the state of the channel. -When a channel is closed, sends to the channel will panic and additional calls to \code{close} will panic. -Receives are handled differently where receivers will never block on a closed channel and will continue to remove elements from the channel. -Once a channel is empty, receivers can continue to remove elements, but will receive the zero-value version of the element type. -To aid in avoiding unwanted zero-value elements, Go provides the ability to iterate over a closed channel to remove the remaining elements. -These design choices for Go channels enforce a specific interaction style with channels during termination, where careful thought is needed to ensure that additional \code{close} calls don't occur and that no sends occur after channels are closed. -These design choices fit Go's paradigm of error management, where users are expected to explicitly check for errors, rather than letting errors occur and catching them. -If errors need to occur in Go, return codes are used to pass error information where they are needed. +Go channels provide a set of tools to help with concurrent shutdown. +Channels in Go have a \code{close} operation and a \code{select} statement that both can be used to help threads terminate. +The \code{select} statement will be discussed in \ref{}, where \CFA's \code{waituntil} statement will be compared with the Go \code{select} statement. +The \code{close} operation on a channel in Go changes the state of the channel. +When a channel is closed, sends to the channel will panic and additional calls to \code{close} will panic. +Receives are handled differently where receivers will never block on a closed channel and will continue to remove elements from the channel. +Once a channel is empty, receivers can continue to remove elements, but will receive the zero-value version of the element type. +To aid in avoiding unwanted zero-value elements, Go provides the ability to iterate over a closed channel to remove the remaining elements. +These design choices for Go channels enforce a specific interaction style with channels during termination, where careful thought is needed to ensure that additional \code{close} calls don't occur and that no sends occur after channels are closed. +These design choices fit Go's paradigm of error management, where users are expected to explicitly check for errors, rather than letting errors occur and catching them. +If errors need to occur in Go, return codes are used to pass error information where they are needed. Note that panics in Go can be caught, but it is not considered an 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. -Since both closing and sending panic, once a channel is closed, a user often has to synchronize the senders to a channel before the channel can be closed to avoid panics. -However, in doing so it renders the \code{close} operation nearly useless, as the only utilities it provides are the ability to ensure that receivers no longer block on the channel, and will receive zero-valued elements. -This can be useful if the zero-typed element is recognized as a sentinel value, but if another sentinel value is preferred, then \code{close} only provides its non-blocking feature. -To avoid \gls{toctou} issues during shutdown, a busy wait with a \code{select} statement is often used to add or remove elements from a channel. +While Go's channel closing semantics are powerful enough to perform any concurrent termination needed by a program, their lack of ease of use leaves much to be desired. +Since both closing and sending panic, once a channel is closed, a user often has to synchronize the senders to a channel before the channel can be closed to avoid panics. +However, in doing so it renders the \code{close} operation nearly useless, as the only utilities it provides are the ability to ensure that receivers no longer block on the channel, and will receive zero-valued elements. +This can be useful if the zero-typed element is recognized as a sentinel value, but if another sentinel value is preferred, then \code{close} only provides its non-blocking feature. +To avoid \gls{toctou} issues during shutdown, a busy wait with a \code{select} statement is often used to add or remove elements from a channel. Due to Go's asymmetric approach to channel shutdown, separate synchronization between producers and consumers of a channel has to occur during shutdown. @@ -82,72 +82,72 @@ As such \CFA uses an exception based approach to channel shutdown that is symmetric for both producers and consumers, and supports graceful shutdown.Exceptions in \CFA support both termination and resumption.Termination exceptions operate in the same way as exceptions seen in many popular programming languages such as \CC, Python and Java. Resumption exceptions are a style of exception that when caught run the corresponding catch block in the same way that termination exceptions do. -The difference between the exception handling mechanisms arises after the exception is handled. -In termination handling, the control flow continues into the code following the catch after the exception is handled. -In resumption handling, the control flow returns to the site of the \code{throw}, allowing the control to continue where it left off. -Note that in resumption, since control can return to the point of error propagation, the stack is not unwound during resumption propagation. -In \CFA if a resumption is not handled, it is reraised as a termination. +The difference between the exception handling mechanisms arises after the exception is handled. +In termination handling, the control flow continues into the code following the catch after the exception is handled. +In resumption handling, the control flow returns to the site of the \code{throw}, allowing the control to continue where it left off. +Note that in resumption, since control can return to the point of error propagation, the stack is not unwound during resumption propagation. +In \CFA if a resumption is not handled, it is reraised as a termination. This mechanism can be used to create a flexible and robust termination system for channels. -When a channel in \CFA is closed, all subsequent calls to the channel will throw a resumption exception at the caller. -If the resumption is handled, then the caller will proceed to attempt to complete their operation. -If the resumption is not handled it is then rethrown as a termination exception. -Or, if the resumption is handled, but the subsequent attempt at an operation would block, a termination exception is thrown. -These termination exceptions allow for non-local transfer that can be used to great effect to eagerly and gracefully shut down a thread. -When a channel is closed, if there are any blocked producers or consumers inside the channel, they are woken up and also have a resumption thrown at them. -The resumption exception, \code{channel_closed}, has a couple fields to aid in handling the exception. -The 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. -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. +When a channel in \CFA is closed, all subsequent calls to the channel will throw a resumption exception at the caller. +If the resumption is handled, then the caller will proceed to attempt to complete their operation. +If the resumption is not handled it is then rethrown as a termination exception. +Or, if the resumption is handled, but the subsequent attempt at an operation would block, a termination exception is thrown. +These termination exceptions allow for non-local transfer that can be used to great effect to eagerly and gracefully shut down a thread. +When a channel is closed, if there are any blocked producers or consumers inside the channel, they are woken up and also have a resumption thrown at them. +The resumption exception, \code{channel_closed}, has a couple fields to aid in handling the exception. +The 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. +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. -To highlight the differences between \CFA's and Go's close semantics, an example program is presented. -The program is a barrier implemented using two channels shown in Listings~\ref{l:cfa_chan_bar} and \ref{l:go_chan_bar}. -Both of these exaples are implmented using \CFA syntax so that they can be easily compared. -Listing~\ref{l:go_chan_bar} uses go-style channel close semantics and Listing~\ref{l:cfa_chan_bar} uses \CFA close semantics. -In this problem it is infeasible to use the Go \code{close} call since all tasks are both potentially producers and consumers, causing panics on close to be unavoidable. -As such in Listing~\ref{l:go_chan_bar} to implement a flush routine for the buffer, a sentinel value of $-1$ has to be used to indicate to threads that they need to leave the barrier. -This sentinel value has to be checked at two points. -Furthermore, an additional flag \code{done} is needed to communicate to threads once they have left the barrier that they are done. -This use of an additional flag or communication method is common in Go channel shutdown code, since to avoid panics on a channel, the shutdown of a channel often has to be communicated with threads before it occurs. -In the \CFA version~\ref{l:cfa_chan_bar}, the barrier shutdown results in an exception being thrown at threads operating on it, which informs the threads that they must terminate. -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. +To highlight the differences between \CFA's and Go's close semantics, an example program is presented. +The program is a barrier implemented using two channels shown in Listings~\ref{l:cfa_chan_bar} and \ref{l:go_chan_bar}. +Both of these exaples are implmented using \CFA syntax so that they can be easily compared. +Listing~\ref{l:go_chan_bar} uses go-style channel close semantics and Listing~\ref{l:cfa_chan_bar} uses \CFA close semantics. +In this problem it is infeasible to use the Go \code{close} call since all tasks are both potentially producers and consumers, causing panics on close to be unavoidable. +As such in Listing~\ref{l:go_chan_bar} to implement a flush routine for the buffer, a sentinel value of $-1$ has to be used to indicate to threads that they need to leave the barrier. +This sentinel value has to be checked at two points. +Furthermore, an additional flag \code{done} is needed to communicate to threads once they have left the barrier that they are done. +This use of an additional flag or communication method is common in Go channel shutdown code, since to avoid panics on a channel, the shutdown of a channel often has to be communicated with threads before it occurs. +In the \CFA version~\ref{l:cfa_chan_bar}, the barrier shutdown results in an exception being thrown at threads operating on it, which informs the threads that they must terminate. +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{cfa}[tabsize=3,caption={\CFA channel barrier termination},label={l:cfa_chan_bar}] struct barrier { - channel( int ) barWait; - channel( int ) entryWait; - int size; + channel( int ) barWait; + channel( int ) entryWait; + int size; } void ?{}(barrier & this, int size) with(this) { - barWait{size}; - entryWait{size}; - this.size = size; - for ( j; size ) - insert( *entryWait, j ); + barWait{size}; + entryWait{size}; + this.size = size; + for ( j; size ) + insert( *entryWait, j ); } void flush(barrier & this) with(this) { - close(barWait); - close(entryWait); + close(barWait); + close(entryWait); } void wait(barrier & this) with(this) { - int ticket = remove( *entryWait ); - if ( ticket == size - 1 ) { - for ( j; size - 1 ) - insert( *barWait, j ); - return; - } - ticket = remove( *barWait ); - - // last one out - if ( size == 1 || ticket == size - 2 ) { - for ( j; size ) - insert( *entryWait, j ); - } + int ticket = remove( *entryWait ); + if ( ticket == size - 1 ) { + for ( j; size - 1 ) + insert( *barWait, j ); + return; + } + ticket = remove( *barWait ); + + // last one out + if ( size == 1 || ticket == size - 2 ) { + for ( j; size ) + insert( *entryWait, j ); + } } barrier b{Tasks}; @@ -155,19 +155,19 @@ // thread main void main(Task & this) { - try { - for ( ;; ) { - wait( b ); - } - } catch ( channel_closed * e ) {} + try { + for ( ;; ) { + wait( b ); + } + } catch ( channel_closed * e ) {} } int main() { - { - Task t[Tasks]; - - sleep(10`s); - flush( b ); - } // wait for tasks to terminate - return 0; + { + Task t[Tasks]; + + sleep(10`s); + flush( b ); + } // wait for tasks to terminate + return 0; } \end{cfa} @@ -176,42 +176,42 @@ struct barrier { - channel( int ) barWait; - channel( int ) entryWait; - int size; + channel( int ) barWait; + channel( int ) entryWait; + int size; } void ?{}(barrier & this, int size) with(this) { - barWait{size + 1}; - entryWait{size + 1}; - this.size = size; - for ( j; size ) - insert( *entryWait, j ); + barWait{size + 1}; + entryWait{size + 1}; + this.size = size; + for ( j; size ) + insert( *entryWait, j ); } void flush(barrier & this) with(this) { - insert( *entryWait, -1 ); - insert( *barWait, -1 ); + insert( *entryWait, -1 ); + insert( *barWait, -1 ); } void wait(barrier & this) with(this) { - int ticket = remove( *entryWait ); - if ( ticket == -1 ) { - insert( *entryWait, -1 ); - return; - } - if ( ticket == size - 1 ) { - for ( j; size - 1 ) - insert( *barWait, j ); - return; - } - ticket = remove( *barWait ); - if ( ticket == -1 ) { - insert( *barWait, -1 ); - return; - } - - // last one out - if ( size == 1 || ticket == size - 2 ) { - for ( j; size ) - insert( *entryWait, j ); - } + int ticket = remove( *entryWait ); + if ( ticket == -1 ) { + insert( *entryWait, -1 ); + return; + } + if ( ticket == size - 1 ) { + for ( j; size - 1 ) + insert( *barWait, j ); + return; + } + ticket = remove( *barWait ); + if ( ticket == -1 ) { + insert( *barWait, -1 ); + return; + } + + // last one out + if ( size == 1 || ticket == size - 2 ) { + for ( j; size ) + insert( *entryWait, j ); + } } barrier b; @@ -220,26 +220,26 @@ // thread main void main(Task & this) { - for ( ;; ) { - if ( done ) break; - wait( b ); - } + for ( ;; ) { + if ( done ) break; + wait( b ); + } } int main() { - { - Task t[Tasks]; - - sleep(10`s); - done = true; - - flush( b ); - } // wait for tasks to terminate - return 0; + { + Task t[Tasks]; + + sleep(10`s); + done = true; + + flush( b ); + } // wait for tasks to terminate + return 0; } \end{cfa} -In Listing~\ref{l:cfa_resume} an example of channel closing with resumption is used. -This program uses resumption in the \code{Consumer} thread main to ensure that all elements in the channel are removed before the consumer thread terminates. -The producer only has a \code{catch} so the moment it receives an exception it terminates, whereas the consumer will continue to remove from the closed channel via handling resumptions until the buffer is empty, which then throws a termination exception. +In Listing~\ref{l:cfa_resume} an example of channel closing with resumption is used. +This program uses resumption in the \code{Consumer} thread main to ensure that all elements in the channel are removed before the consumer thread terminates. +The producer only has a \code{catch} so the moment it receives an exception it terminates, whereas the consumer will continue to remove from the closed channel via handling resumptions until the buffer is empty, which then throws a termination exception. If the same program was implemented in Go it would require explicit synchronization with both producers and consumers by some mechanism outside the channel to ensure that all elements were removed before task termination. @@ -249,34 +249,34 @@ // Consumer thread main void main(Consumer & this) { - size_t runs = 0; - try { - for ( ;; ) { - remove( chan ); - } - } catchResume ( channel_closed * e ) {} - catch ( channel_closed * e ) {} + size_t runs = 0; + try { + for ( ;; ) { + remove( chan ); + } + } catchResume ( channel_closed * e ) {} + catch ( channel_closed * e ) {} } // Producer thread main void main(Producer & this) { - int j = 0; - try { - for ( ;;j++ ) { - insert( chan, j ); - } - } catch ( channel_closed * e ) {} + int j = 0; + try { + for ( ;;j++ ) { + insert( chan, j ); + } + } catch ( channel_closed * e ) {} } int main( int argc, char * argv[] ) { - { - Consumers c[4]; - Producer p[4]; - - sleep(10`s); - - for ( i; Channels ) - close( channels[i] ); - } - return 0; + { + Consumers c[4]; + Producer p[4]; + + sleep(10`s); + + for ( i; Channels ) + close( channels[i] ); + } + return 0; } \end{cfa} @@ -284,27 +284,29 @@ \section{Performance} -Given that the base implementation of the \CFA channels is very similar to the Go implementation, this section aims to show that the performance of the two implementations are comparable. -One microbenchmark is conducted to compare Go and \CFA. -The benchmark is a ten second experiment where producers and consumers operate on a channel in parallel and throughput is measured. -The number of cores is varied to measure how throughtput scales. -The cores are divided equally between producers and consumers, with one producer or consumer owning each core. -The results of the benchmark are shown in Figure~\ref{f:chanPerf}. -The performance of Go and \CFA channels on this microbenchmark is comparable. +Given that the base implementation of the \CFA channels is very similar to the Go implementation, this section aims to show that the performance of the two implementations are comparable. +One microbenchmark is conducted to compare Go and \CFA. +The benchmark is a ten second experiment where producers and consumers operate on a channel in parallel and throughput is measured. +The number of cores is varied to measure how throughtput scales. +The cores are divided equally between producers and consumers, with one producer or consumer owning each core. +The results of the benchmark are shown in Figure~\ref{f:chanPerf}. +The performance of Go and \CFA channels on this microbenchmark is comparable. Note, it is expected for the performance to decline as the number of cores increases as the channel operations all occur in a critical section so an increase in cores results in higher contention with no increase in parallelism. \begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasus_Channel_Contention.pgf}} - \subcaption{AMD \CFA Channel Benchmark}\label{f:chanAMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pyke_Channel_Contention.pgf}} - \subcaption{Intel \CFA Channel Benchmark}\label{f:chanIntel} - \end{subfigure} - \caption{The channel contention benchmark comparing \CFA and Go channel throughput (higher is better).} - \label{f:chanPerf} + \centering + \subfloat[AMD \CFA Channel Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Channel_Contention.pgf}} + \label{f:chanAMD} + } + \subfloat[Intel \CFA Channel Benchmark]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Channel_Contention.pgf}} + \label{f:chanIntel} + } + \caption{The channel contention benchmark comparing \CFA and Go channel throughput (higher is better).} + \label{f:chanPerf} \end{figure} + +% Local Variables: % +% tab-width: 4 % +% End: % Index: doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -5,163 +5,415 @@ % ====================================================================== -The mutex statement is a concurrent language feature that aims to support easy lock usage. -The mutex statement is in the form of a clause and following statement, similar to a loop or conditional statement. -In the clause the mutex statement accepts a number of lockable objects, and then locks them for the duration of the following statement. -The locks are acquired in a deadlock free manner and released using \gls{raii}. -The mutex statement provides an avenue for easy lock usage in the common case where locks are used to wrap a critical section. -Additionally, it provides the safety guarantee of deadlock-freedom, both by acquiring the locks in a deadlock-free manner, and by ensuring that the locks release on error, or normal program execution via \gls{raii}. - -\begin{cfa}[tabsize=3,caption={\CFA mutex statement usage},label={l:cfa_mutex_ex}] +The mutual exclusion problem was introduced by Dijkstra in 1965~\cite{Dijkstra65,Dijkstra65a}. +There are several concurrent processes or threads that communicate by shared variables and from time to time need exclusive access to shared resources. +A shared resource and code manipulating it form a pairing called a \Newterm{critical section (CS)}, which is a many-to-one relationship; +\eg if multiple files are being written to by multiple threads, only the pairings of simultaneous writes to the same files are CSs. +Regions of code where the thread is not interested in the resource are combined into the \Newterm{non-critical section (NCS)}. + +Exclusive access to a resource is provided by \Newterm{mutual exclusion (MX)}. +MX is implemented by some form of \emph{lock}, where the CS is bracketed by lock procedures @acquire@ and @release@. +Threads execute a loop of the form: +\begin{cfa} +loop of $thread$ p: + NCS; + acquire( lock ); CS; release( lock ); // protected critical section with MX +end loop. +\end{cfa} +MX guarantees there is never more than one thread in the CS. +MX must also guarantee eventual progress: when there are competing threads attempting access, eventually some competing thread succeeds, \ie acquires the CS, releases it, and returns to the NCS. +% Lamport \cite[p.~329]{Lam86mx} extends this requirement to the exit protocol. +A stronger constraint is that every thread that calls @acquire@ eventually succeeds after some reasonable bounded time. + +\section{Monitor} +\CFA provides a high-level locking object, called a \Newterm{monitor}, an elegant, efficient, high-level mechanisms for mutual exclusion and synchronization for shared-memory systems. +First proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}, several concurrent programming languages provide monitors as an explicit language construct: \eg Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, \uC~\cite{Buhr92a} and Java~\cite{Java}. +In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as mutex locks or semaphores to manually implement a monitor. + +Figure~\ref{f:AtomicCounter} shows a \CFA and Java monitor implementing an atomic counter. +A \Newterm{monitor} is a programming technique that implicitly binds mutual exclusion to static function scope by call and return. +Lock mutual exclusion, defined by acquire/release calls, is independent of lexical context (analogous to block versus heap storage allocation). +Restricting acquire and release points in a monitor eases programming, comprehension, and maintenance, at a slight cost in flexibility and efficiency. +Ultimately, a monitor is implemented using a combination of basic locks and atomic instructions. + +\begin{figure} +\centering + +\begin{lrbox}{\myboxA} +\begin{cfa}[aboveskip=0pt,belowskip=0pt] +@monitor@ Aint { + int cnt; +}; +int ++?( Aint & @mutex@ m ) { return ++m.cnt; } +int ?=?( Aint & @mutex@ l, int r ) { l.cnt = r; } +int ?=?(int & l, Aint & r) { l = r.cnt; } + +int i = 0, j = 0; +Aint x = { 0 }, y = { 0 }; $\C[1.5in]{// no mutex}$ +++x; ++y; $\C{// mutex}$ +x = 2; y = i; $\C{// mutex}$ +i = x; j = y; $\C{// no mutex}\CRT$ +\end{cfa} +\end{lrbox} + +\begin{lrbox}{\myboxB} +\begin{java}[aboveskip=0pt,belowskip=0pt] +class Aint { + private int cnt; + public Aint( int init ) { cnt = init; } + @synchronized@ public int inc() { return ++cnt; } + @synchronized@ public void set( int r ) {cnt = r;} + public int get() { return cnt; } +} +int i = 0, j = 0; +Aint x = new Aint( 0 ), y = new Aint( 0 ); +x.inc(); y.inc(); +x.set( 2 ); y.set( i ); +i = x.get(); j = y.get(); +\end{java} +\end{lrbox} + +\subfloat[\CFA]{\label{f:AtomicCounterCFA}\usebox\myboxA} +\hspace*{3pt} +\vrule +\hspace*{3pt} +\subfloat[Java]{\label{f:AtomicCounterJava}\usebox\myboxB} +\caption{Atomic integer counter} +\label{f:AtomicCounter} +\end{figure} + +Like Java, \CFA monitors have \Newterm{multi-acquire} semantics so the thread in the monitor may acquire it multiple times without deadlock, allowing recursion and calling other MX functions. +For robustness, \CFA monitors ensure the monitor lock is released regardless of how an acquiring function ends, normal or exceptional, and returning a shared variable is safe via copying before the lock is released. +Monitor objects can be passed through multiple helper functions without acquiring mutual exclusion, until a designated function associated with the object is called. +\CFA functions are designated MX by one or more pointer/reference parameters having qualifier @mutex@. +Java members are designated MX with \lstinline[language=java]{synchronized}, which applies only to the implicit receiver parameter. +In the example, the increment and setter operations need mutual exclusion, while the read-only getter operation is not MX because reading an integer is atomic. + +As stated, the non-object-oriented nature of \CFA monitors allows a function to acquire multiple mutex objects. +For example, the bank-transfer problem requires locking two bank accounts to safely debit and credit money between accounts. +\begin{cfa} +monitor BankAccount { + int balance; +}; +void deposit( BankAccount & mutex b, int deposit ) with( b ) { + balance += deposit; +} +void transfer( BankAccount & mutex my, BankAccount & mutex your, int me2you ) { + deposit( my, -me2you ); $\C{// debit}$ + deposit( your, me2you ); $\C{// credit}$ +} +\end{cfa} +The \CFA monitor implementation ensures multi-lock acquisition is done in a deadlock-free manner regardless of the number of MX parameters and monitor arguments. + + +\section{\lstinline{mutex} statement} +Restricting implicit lock acquisition to function entry and exit can be awkward for certain problems. +To increase locking flexibility, some languages introduce a mutex statement. +\VRef[Figure]{f:ReadersWriter} shows the outline of a reader/writer lock written as a \CFA monitor and mutex statements. +(The exact lock implement is irrelevant.) +The @read@ and @write@ functions are called with a reader/write lock and any arguments to perform reading or writing. +The @read@ function is not MX because multiple readers can read simultaneously. +MX is acquired within @read@ by calling the (nested) helper functions @StartRead@ and @EndRead@ or executing the mutex statements. +Between the calls or statements, reads can execute simultaneous within the body of @read@. +The @write@ function does not require refactoring because writing is a CS. +The mutex-statement version is better because it has fewer names, less argument/parameter passing, and can possibly hold MX for a shorter duration. + +\begin{figure} +\centering + +\begin{lrbox}{\myboxA} +\begin{cfa}[aboveskip=0pt,belowskip=0pt] +monitor RWlock { ... }; +void read( RWlock & rw, ... ) { + void StartRead( RWlock & @mutex@ rw ) { ... } + void EndRead( RWlock & @mutex@ rw ) { ... } + StartRead( rw ); + ... // read without MX + EndRead( rw ); +} +void write( RWlock & @mutex@ rw, ... ) { + ... // write with MX +} +\end{cfa} +\end{lrbox} + +\begin{lrbox}{\myboxB} +\begin{cfa}[aboveskip=0pt,belowskip=0pt] + +void read( RWlock & rw, ... ) { + + + @mutex@( rw ) { ... } + ... // read without MX + @mutex@{ rw ) { ... } +} +void write( RWlock & @mutex@ rw, ... ) { + ... // write with MX +} +\end{cfa} +\end{lrbox} + +\subfloat[monitor]{\label{f:RWmonitor}\usebox\myboxA} +\hspace*{3pt} +\vrule +\hspace*{3pt} +\subfloat[mutex statement]{\label{f:RWmutexstmt}\usebox\myboxB} +\caption{Readers writer problem} +\label{f:ReadersWriter} +\end{figure} + +This work adds a mutex statement to \CFA, but generalizes it beyond implicit monitor locks. +In detail, the mutex statement has a clause and statement block, similar to a conditional or loop statement. +The clause accepts any number of lockable objects (like a \CFA MX function prototype), and locks them for the duration of the statement. +The locks are acquired in a deadlock free manner and released regardless of how control-flow exits the statement. +The mutex statement provides easy lock usage in the common case of lexically wrapping a CS. +Examples of \CFA mutex statement are shown in \VRef[Listing]{l:cfa_mutex_ex}. + +\begin{cfa}[caption={\CFA mutex statement usage},label={l:cfa_mutex_ex}] owner_lock lock1, lock2, lock3; -int count = 0; -mutex( lock1, lock2, lock3 ) { - // can use block statement - // ... -} -mutex( lock2, lock3 ) count++; // or inline statement +@mutex@( lock2, lock3 ) ...; $\C{// inline statement}$ +@mutex@( lock1, lock2, lock3 ) { ... } $\C{// statement block}$ +void transfer( BankAccount & my, BankAccount & your, int me2you ) { + ... // check values, no MX + @mutex@( my, your ) { // MX is shorter duration that function body + deposit( my, -me2you ); $\C{// debit}$ + deposit( your, me2you ); $\C{// credit}$ + } +} \end{cfa} \section{Other Languages} -There are similar concepts to the mutex statement that exist in other languages. -Java has a feature called a synchronized statement, which looks identical to \CFA's mutex statement, but it has some differences. -The synchronized statement only accepts a single object in its clause. -Any object can be passed to the synchronized statement in Java since all objects in Java are monitors, and the synchronized statement acquires that object's monitor. -In \CC there is a feature in the standard library \code{} header called scoped\_lock, which is also similar to the mutex statement. -The scoped\_lock is a class that takes in any number of locks in its constructor, and acquires them in a deadlock-free manner. -It then releases them when the scoped\_lock object is deallocated, thus using \gls{raii}. -An example of \CC scoped\_lock usage is shown in Listing~\ref{l:cc_scoped_lock}. - -\begin{cfa}[tabsize=3,caption={\CC scoped\_lock usage},label={l:cc_scoped_lock}] -std::mutex lock1, lock2, lock3; -{ - scoped_lock s( lock1, lock2, lock3 ) - // locks are released via raii at end of scope -} +There are similar constructs to the mutex statement in other programming languages. +Java has a feature called a synchronized statement, which looks like the \CFA's mutex statement, but only accepts a single object in the clause and only handles monitor locks. +The \CC standard library has a @scoped_lock@, which is also similar to the mutex statement. +The @scoped_lock@ takes any number of locks in its constructor, and acquires them in a deadlock-free manner. +It then releases them when the @scoped_lock@ object is deallocated using \gls{raii}. +An example of \CC @scoped_lock@ is shown in \VRef[Listing]{l:cc_scoped_lock}. + +\begin{cfa}[caption={\CC \lstinline{scoped_lock} usage},label={l:cc_scoped_lock}] +struct BankAccount { + @recursive_mutex m;@ $\C{// must be recursive}$ + int balance = 0; +}; +void deposit( BankAccount & b, int deposit ) { + @scoped_lock lock( b.m );@ $\C{// RAII acquire}$ + b.balance += deposit; +} $\C{// RAII release}$ +void transfer( BankAccount & my, BankAccount & your, int me2you ) { + @scoped_lock lock( my.m, your.m );@ $\C{// RAII acquire}$ + deposit( my, -me2you ); $\C{// debit}$ + deposit( your, me2you ); $\C{// credit}$ +} $\C{// RAII release}$ \end{cfa} \section{\CFA implementation} -The \CFA mutex statement takes some ideas from both the Java and \CC features. -The mutex statement can acquire more that one lock in a deadlock-free manner, and releases them via \gls{raii} like \CC, however the syntax is identical to the Java synchronized statement. -This syntactic choice was made so that the body of the mutex statement is its own scope. -Compared to the scoped\_lock, which relies on its enclosing scope, the mutex statement's introduced scope can provide visual clarity as to what code is being protected by the mutex statement, and where the mutual exclusion ends. -\CFA's mutex statement and \CC's scoped\_lock both use parametric polymorphism to allow user defined types to work with the feature. -\CFA's implementation requires types to support the routines \code{lock()} and \code{unlock()}, whereas \CC requires those routines, plus \code{try_lock()}. -The scoped\_lock requires an additional routine since it differs from the mutex statement in how it implements deadlock avoidance. - -The parametric polymorphism allows for locking to be defined for types that may want convenient mutual exclusion. -An example of one such use case in \CFA is \code{sout}. -The output stream in \CFA is called \code{sout}, and functions similarly to \CC's \code{cout}. -\code{sout} has routines that satisfy the mutex statement trait, so the mutex statement can be used to lock the output stream while producing output. -In this case, the mutex statement allows the programmer to acquire mutual exclusion over an object without having to know the internals of the object or what locks need to be acquired. -The ability to do so provides both improves safety and programmer productivity since it abstracts away the concurrent details and provides an interface for optional thread-safety. -This is a commonly used feature when producing output from a concurrent context, since producing output is not thread safe by default. -This use case is shown in Listing~\ref{l:sout}. - -\begin{cfa}[tabsize=3,caption={\CFA sout with mutex statement},label={l:sout}] -mutex( sout ) - sout | "This output is protected by mutual exclusion!"; -\end{cfa} - -\section{Deadlock Avoidance} -The mutex statement uses the deadlock prevention technique of lock ordering, where the circular-wait condition of a deadlock cannot occur if all locks are acquired in the same order. -The scoped\_lock uses a deadlock avoidance algorithm where all locks after the first are acquired using \code{try_lock} and if any of the attempts to lock fails, all locks so far are released. -This repeats until all locks are acquired successfully. -The deadlock avoidance algorithm used by scoped\_lock is shown in Listing~\ref{l:cc_deadlock_avoid}. -The algorithm presented is taken directly from the source code of the \code{} header, with some renaming and comments for clarity. - -\begin{cfa}[caption={\CC scoped\_lock deadlock avoidance algorithm},label={l:cc_deadlock_avoid}] +The \CFA mutex statement takes some ideas from both the Java and \CC features. +Like Java, \CFA introduces a new statement rather than building from existing language features. +(\CFA has sufficient language features to mimic \CC RAII locking.) +This syntactic choice makes MX explicit rather than implicit via object declarations. +Hence, it is easier for programmers and language tools to identify MX points in a program, \eg scan for all @mutex@ parameters and statements in a body of code. +Furthermore, concurrent safety is provided across an entire program for the complex operation of acquiring multiple locks in a deadlock-free manner. +Unlike Java, \CFA's mutex statement and \CC's @scoped_lock@ both use parametric polymorphism to allow user defined types to work with this feature. +In this case, the polymorphism allows a locking mechanism to acquire MX over an object without having to know the object internals or what kind of lock it is using. +\CFA's provides and uses this locking trait: +\begin{cfa} +forall( L & | sized(L) ) +trait is_lock { + void lock( L & ); + void unlock( L & ); +}; +\end{cfa} +\CC @scoped_lock@ has this trait implicitly based on functions accessed in a template. +@scoped_lock@ also requires @try_lock@ because of its technique for deadlock avoidance \see{\VRef{s:DeadlockAvoidance}}. + +The following shows how the @mutex@ statement is used with \CFA streams to eliminate unpredictable results when printing in a concurrent program. +For example, if two threads execute: +\begin{cfa} +thread$\(_1\)$ : sout | "abc" | "def"; +thread$\(_2\)$ : sout | "uvw" | "xyz"; +\end{cfa} +any of the outputs can appear, included a segment fault due to I/O buffer corruption: +\begin{cquote} +\small\tt +\begin{tabular}{@{}l|l|l|l|l@{}} +abc def & abc uvw xyz & uvw abc xyz def & abuvwc dexf & uvw abc def \\ +uvw xyz & def & & yz & xyz +\end{tabular} +\end{cquote} +The stream type for @sout@ is defined to satisfy the @is_lock@ trait, so the @mutex@ statement can be used to lock an output stream while producing output. +From the programmer's perspective, it is sufficient to know an object can be locked and then any necessary MX is easily available via the @mutex@ statement. +This ability improves safety and programmer productivity since it abstracts away the concurrent details. +Hence, a programmer can easily protect cascaded I/O expressions: +\begin{cfa} +thread$\(_1\)$ : mutex( sout ) sout | "abc" | "def"; +thread$\(_2\)$ : mutex( sout ) sout | "uvw" | "xyz"; +\end{cfa} +constraining the output to two different lines in either order: +\begin{cquote} +\small\tt +\begin{tabular}{@{}l|l@{}} +abc def & uvw xyz \\ +uvw xyz & abc def +\end{tabular} +\end{cquote} +where this level of safe nondeterministic output is acceptable. +Alternatively, multiple I/O statements can be protected using the mutex statement block: +\begin{cfa} +mutex( sout ) { // acquire stream lock for sout for block duration + sout | "abc"; + mutex( sout ) sout | "uvw" | "xyz"; // OK because sout lock is recursive + sout | "def"; +} // implicitly release sout lock +\end{cfa} +The inner lock acquire is likely to occur through a function call that does a thread-safe print. + +\section{Deadlock Avoidance}\label{s:DeadlockAvoidance} +The mutex statement uses the deadlock avoidance technique of lock ordering, where the circular-wait condition of a deadlock cannot occur if all locks are acquired in the same order. +The @scoped_lock@ uses a deadlock avoidance algorithm where all locks after the first are acquired using @try_lock@ and if any of the lock attempts fail, all acquired locks are released. +This repeats after selecting a new starting point in a cyclic manner until all locks are acquired successfully. +This deadlock avoidance algorithm is shown in Listing~\ref{l:cc_deadlock_avoid}. +The algorithm is taken directly from the source code of the @@ header, with some renaming and comments for clarity. + +\begin{cfa}[caption={\CC \lstinline{scoped_lock} deadlock avoidance algorithm},label={l:cc_deadlock_avoid}] int first = 0; // first lock to attempt to lock do { - // locks is the array of locks to acquire - locks[first].lock(); // lock first lock - for (int i = 1; i < Num_Locks; ++i) { // iterate over rest of locks - const int idx = (first + i) % Num_Locks; - if (!locks[idx].try_lock()) { // try lock each one - for (int j = i; j != 0; --j) // release all locks - locks[(first + j - 1) % Num_Locks].unlock(); - first = idx; // rotate which lock to acquire first - break; - } - } + // locks is the array of locks to acquire + locks[first].lock(); $\C{// lock first lock}$ + for ( int i = 1; i < Num_Locks; i += 1 ) { $\C{// iterate over rest of locks}$ + const int idx = (first + i) % Num_Locks; + if ( ! locks[idx].try_lock() ) { $\C{// try lock each one}$ + for ( int j = i; j != 0; j -= 1 ) $\C{// release all locks}$ + locks[(first + j - 1) % Num_Locks].unlock(); + first = idx; $\C{// rotate which lock to acquire first}$ + break; + } + } // if first lock is still held then all have been acquired -} while (!locks[first].owns_lock()); // is first lock held? -\end{cfa} - -The algorithm in \ref{l:cc_deadlock_avoid} successfully avoids deadlock, however there is a potential livelock scenario. -Given two threads $A$ and $B$, who create a scoped\_lock with two locks $L1$ and $L2$, a livelock can form as follows. -Thread $A$ creates a scoped\_lock with $L1$, $L2$, and $B$ creates a scoped lock with the order $L2$, $L1$. -Both threads acquire the first lock in their order and then fail the try\_lock since the other lock is held. -They then reset their start lock to be their 2nd lock and try again. -This time $A$ has order $L2$, $L1$, and $B$ has order $L1$, $L2$. -This is identical to the starting setup, but with the ordering swapped among threads. -As such, if they each acquire their first lock before the other acquires their second, they can livelock indefinitely. - -The lock ordering algorithm used in the mutex statement in \CFA is both deadlock and livelock free. -It sorts the locks based on memory address and then acquires them. -For locks fewer than 7, it sorts using hard coded sorting methods that perform the minimum number of swaps for a given number of locks. -For 7 or more locks insertion sort is used. -These sorting algorithms were chosen since it is rare to have to hold more than a handful of locks at a time. -It is worth mentioning that the downside to the sorting approach is that it is not fully compatible with usages of the same locks outside the mutex statement. -If more than one lock is held by a mutex statement, if more than one lock is to be held elsewhere, it must be acquired via the mutex statement, or else the required ordering will not occur. -Comparitively, if the scoped\_lock is used and the same locks are acquired elsewhere, there is no concern of the scoped\_lock deadlocking, due to its avoidance scheme, but it may livelock. +} while ( ! locks[first].owns_lock() ); $\C{// is first lock held?}$ +\end{cfa} + +While the algorithm in \ref{l:cc_deadlock_avoid} successfully avoids deadlock, there is a livelock scenario. +Assume two threads, $A$ and $B$, create a @scoped_lock@ accessing two locks, $L1$ and $L2$. +A livelock can form as follows. +Thread $A$ creates a @scoped_lock@ with arguments $L1$, $L2$, and $B$ creates a scoped lock with the lock arguments in the opposite order $L2$, $L1$. +Both threads acquire the first lock in their order and then fail the @try_lock@ since the other lock is held. +Both threads then reset their starting lock to be their second lock and try again. +This time $A$ has order $L2$, $L1$, and $B$ has order $L1$, $L2$, which is identical to the starting setup but with the ordering swapped between threads. +If the threads perform this action in lock-step, they cycle indefinitely without entering the CS, \ie livelock. +Hence, to use @scoped_lock@ safely, a programmer must manually construct and maintain a global ordering of lock arguments passed to @scoped_lock@. + +The lock ordering algorithm used in \CFA mutex functions and statements is deadlock and livelock free. +The algorithm uses the lock memory addresses as keys, sorts the keys, and then acquires the locks in sorted order. +For fewer than 7 locks ($2^3-1$), the sort is unrolled performing the minimum number of compare and swaps for the given number of locks; +for 7 or more locks, insertion sort is used. +Since it is extremely rare to hold more than 6 locks at a time, the algorithm is fast and executes in $O(1)$ time. +Furthermore, lock addresses are unique across program execution, even for dynamically allocated locks, so the algorithm is safe across the entire program execution. + +The downside to the sorting approach is that it is not fully compatible with manual usages of the same locks outside the @mutex@ statement, \ie the lock are acquired without using the @mutex@ statement. +The following scenario is a classic deadlock. +\begin{cquote} +\begin{tabular}{@{}l@{\hspace{30pt}}l@{}} +\begin{cfa} +lock L1, L2; // assume &L1 < &L2 + $\textbf{thread\(_1\)}$ +acquire( L2 ); + acquire( L1 ); + CS + release( L1 ); +release( L2 ); +\end{cfa} +& +\begin{cfa} + + $\textbf{thread\(_2\)}$ +mutex( L1, L2 ) { + + CS + +} +\end{cfa} +\end{tabular} +\end{cquote} +Comparatively, if the @scoped_lock@ is used and the same locks are acquired elsewhere, there is no concern of the @scoped_lock@ deadlocking, due to its avoidance scheme, but it may livelock. +The convenience and safety of the @mutex@ statement, \eg guaranteed lock release with exceptions, should encourage programmers to always use it for locking, mitigating any deadlock scenario. + +\section{Performance} +Given the two multi-acquisition algorithms in \CC and \CFA, each with differing advantages and disadvantages, it interesting to compare their performance. +Comparison with Java is not possible, since it only takes a single lock. + +The comparison starts with a baseline that acquires the locks directly without a mutex statement or @scoped_lock@ in a fixed ordering and then releases them. +The baseline helps highlight the cost of the deadlock avoidance/prevention algorithms for each implementation. + +The benchmark used to evaluate the avoidance algorithms repeatedly acquires a fixed number of locks in a random order and then releases them. +The pseudo code for the deadlock avoidance benchmark is shown in \VRef[Listing]{l:deadlock_avoid_pseudo}. +To ensure the comparison exercises the implementation of each lock avoidance algorithm, an identical spinlock is implemented in each language using a set of builtin atomics available in both \CC and \CFA. +The benchmarks are run for a fixed duration of 10 seconds and then terminate. +The total number of times the group of locks is acquired is returned for each thread. +Each variation is run 11 times on 2, 4, 8, 16, 24, 32 cores and with 2, 4, and 8 locks being acquired. +The median is calculated and is plotted alongside the 95\% confidence intervals for each point. + +\begin{cfa}[caption={Deadlock avoidance bendchmark pseudo code},label={l:deadlock_avoid_pseudo}] + + + +$\PAB{// add pseudo code}$ + + + +\end{cfa} + +The performance experiments were run on the following multi-core hardware systems to determine differences across platforms: +\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=5pt\parsep=5pt\itemsep=0pt} +% sudo dmidecode -t system +\item +Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units) 2.0 GHz, TSO memory model, running Linux v5.8.0--55--generic, gcc--10 compiler +\item +Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets (48 processing units) 2.2GHz, TSO memory model, running Linux v5.8.0--59--generic, gcc--10 compiler +\end{list} +%The hardware architectures are different in threading (multithreading vs hyper), cache structure (MESI or MESIF), NUMA layout (QPI vs HyperTransport), memory model (TSO vs WO), and energy/thermal mechanisms (turbo-boost). +%Software that runs well on one architecture may run poorly or not at all on another. + +Figure~\ref{f:mutex_bench} shows the results of the benchmark experiments. +\PAB{Make the points in the graphs for each line different. +Also, make the text in the graphs larger.} +The baseline results for both languages are mostly comparable, except for the 8 locks results in \ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel}, where the \CFA baseline is slightly slower. +The avoidance result for both languages is significantly different, where \CFA's mutex statement achieves throughput that is magnitudes higher than \CC's @scoped_lock@. +The slowdown for @scoped_lock@ is likely due to its deadlock-avoidance implementation. +Since it uses a retry based mechanism, it can take a long time for threads to progress. +Additionally the potential for livelock in the algorithm can result in very little throughput under high contention. +For example, on the AMD machine with 32 threads and 8 locks, the benchmarks would occasionally livelock indefinitely, with no threads making any progress for 3 hours before the experiment was terminated manually. +It is likely that shorter bouts of livelock occurred in many of the experiments, which would explain large confidence intervals for some of the data points in the \CC data. +In Figures~\ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel} the mutex statement performs better than the baseline. +At 7 locks and above the mutex statement switches from a hard coded sort to insertion sort. +It is likely that the improvement in throughput compared to baseline is due to the time spent in the insertion sort, which decreases contention on the locks. \begin{figure} - \centering - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasus_Aggregate_Lock_2.pgf}} - \subcaption{AMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pyke_Aggregate_Lock_2.pgf}} - \subcaption{Intel} - \end{subfigure} - - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasus_Aggregate_Lock_4.pgf}} - \subcaption{AMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pyke_Aggregate_Lock_4.pgf}} - \subcaption{Intel} - \end{subfigure} - - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/nasus_Aggregate_Lock_8.pgf}} - \subcaption{AMD}\label{f:mutex_bench8_AMD} - \end{subfigure}\hfill - \begin{subfigure}{0.5\textwidth} - \centering - \scalebox{0.5}{\input{figures/pyke_Aggregate_Lock_8.pgf}} - \subcaption{Intel}\label{f:mutex_bench8_Intel} - \end{subfigure} - \caption{The aggregate lock benchmark comparing \CC scoped\_lock and \CFA mutex statement throughput (higher is better).} - \label{f:mutex_bench} + \centering + \subfloat[AMD]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Aggregate_Lock_2.pgf}} + } + \subfloat[Intel]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Aggregate_Lock_2.pgf}} + } + + \subfloat[AMD]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Aggregate_Lock_4.pgf}} + } + \subfloat[Intel]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Aggregate_Lock_4.pgf}} + } + + \subfloat[AMD]{ + \resizebox{0.5\textwidth}{!}{\input{figures/nasus_Aggregate_Lock_8.pgf}} + \label{f:mutex_bench8_AMD} + } + \subfloat[Intel]{ + \resizebox{0.5\textwidth}{!}{\input{figures/pyke_Aggregate_Lock_8.pgf}} + \label{f:mutex_bench8_Intel} + } + \caption{The aggregate lock benchmark comparing \CC \lstinline{scoped_lock} and \CFA mutex statement throughput (higher is better).} + \label{f:mutex_bench} \end{figure} -\section{Performance} -Performance is compared between \CC's scoped\_lock and \CFA's mutex statement. -Comparison with Java is omitted, since it only takes a single lock. -To ensure that the comparison between \CC and \CFA exercises the implementation of each feature, an identical spinlock is implemented in each language using a set of builtin atomics available in both \CFA and \CC. -Each feature is evaluated on a benchmark which acquires a fixed number of locks in a random order and then releases them. -A baseline is included that acquires the locks directly without a mutex statement or scoped\_lock in a fixed ordering and then releases them. -The baseline helps highlight the cost of the deadlock avoidance/prevention algorithms for each implementation. -The benchmarks are run for a fixed duration of 10 seconds and then terminate and return the total number of times the group of locks were acquired. -Each variation is run 11 times on a variety up to 32 cores and with 2, 4, and 8 locks being acquired. -The median is calculated and is plotted alongside the 95\% confidence intervals for each point. - -Figure~\ref{f:mutex_bench} shows the results of the benchmark. -The baseline runs for both languages are mostly comparable, except for the 8 locks results in \ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel}, where the \CFA baseline is slower. -\CFA's mutex statement achieves throughput that is magnitudes higher than \CC's scoped\_lock. -This is likely due to the scoped\_lock deadlock avoidance implementation. -Since it uses a retry based mechanism, it can take a long time for threads to progress. -Additionally the potential for livelock in the algorithm can result in very little throughput under high contention. -It was observed on the AMD machine that with 32 threads and 8 locks the benchmarks would occasionally livelock indefinitely, with no threads making any progress for 3 hours before the experiment was terminated manually. -It is likely that shorter bouts of livelock occured in many of the experiments, which would explain large confidence intervals for some of the data points in the \CC data. -In Figures~\ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel} the mutex statement performs better than the baseline. -At 7 locks and above the mutex statement switches from a hard coded sort to insertion sort. -It is likely that the improvement in throughput compared to baseline is due to the time spent in the insertion sort, which decreases contention on the locks. +% Local Variables: % +% tab-width: 4 % +% End: % Index: doc/theses/colby_parsons_MMAth/thesis.tex =================================================================== --- doc/theses/colby_parsons_MMAth/thesis.tex (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ doc/theses/colby_parsons_MMAth/thesis.tex (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -84,9 +84,10 @@ \usepackage{tikz} % for diagrams and figures \def\checkmark{\tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle;} -\usepackage{subcaption} \usepackage{fullpage,times,comment} \usepackage{textcomp} \usepackage{graphicx} \usepackage{tabularx} +\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt,font=normalsize]{subfig} +\renewcommand\thesubfigure{(\alph{subfigure})} \input{style} Index: src/AST/Convert.cpp =================================================================== --- src/AST/Convert.cpp (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ src/AST/Convert.cpp (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -559,5 +559,5 @@ auto stmt = new SuspendStmt(); stmt->then = get().accept1( node->then ); - switch(node->type) { + switch (node->kind) { case ast::SuspendStmt::None : stmt->type = SuspendStmt::None ; break; case ast::SuspendStmt::Coroutine: stmt->type = SuspendStmt::Coroutine; break; @@ -1683,5 +1683,5 @@ GET_ACCEPT_V(attributes, Attribute), { old->get_funcSpec().val }, - old->type->isVarArgs + (old->type->isVarArgs) ? ast::VariableArgs : ast::FixedArgs }; @@ -1989,5 +1989,5 @@ GET_ACCEPT_1(else_, Stmt), GET_ACCEPT_V(initialization, Stmt), - old->isDoWhile, + (old->isDoWhile) ? ast::DoWhile : ast::While, GET_LABELS_V(old->labels) ); @@ -2131,5 +2131,5 @@ virtual void visit( const SuspendStmt * old ) override final { if ( inCache( old ) ) return; - ast::SuspendStmt::Type type; + ast::SuspendStmt::Kind type; switch (old->type) { case SuspendStmt::Coroutine: type = ast::SuspendStmt::Coroutine; break; Index: src/AST/Decl.cpp =================================================================== --- src/AST/Decl.cpp (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ src/AST/Decl.cpp (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -57,9 +57,9 @@ std::vector>&& params, std::vector>&& returns, CompoundStmt * stmts, Storage::Classes storage, Linkage::Spec linkage, - std::vector>&& attrs, Function::Specs fs, bool isVarArgs) + std::vector>&& attrs, Function::Specs fs, ArgumentFlag isVarArgs ) : DeclWithType( loc, name, storage, linkage, std::move(attrs), fs ), type_params(std::move(forall)), assertions(), params(std::move(params)), returns(std::move(returns)), stmts( stmts ) { - FunctionType * ftype = new FunctionType(static_cast(isVarArgs)); + FunctionType * ftype = new FunctionType( isVarArgs ); for (auto & param : this->params) { ftype->params.emplace_back(param->get_type()); @@ -81,10 +81,10 @@ std::vector>&& params, std::vector>&& returns, CompoundStmt * stmts, Storage::Classes storage, Linkage::Spec linkage, - std::vector>&& attrs, Function::Specs fs, bool isVarArgs) + std::vector>&& attrs, Function::Specs fs, ArgumentFlag isVarArgs ) : DeclWithType( location, name, storage, linkage, std::move(attrs), fs ), type_params( std::move( forall) ), assertions( std::move( assertions ) ), params( std::move(params) ), returns( std::move(returns) ), type( nullptr ), stmts( stmts ) { - FunctionType * type = new FunctionType( (isVarArgs) ? VariableArgs : FixedArgs ); + FunctionType * type = new FunctionType( isVarArgs ); for ( auto & param : this->params ) { type->params.emplace_back( param->get_type() ); Index: src/AST/Decl.hpp =================================================================== --- src/AST/Decl.hpp (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ src/AST/Decl.hpp (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -10,6 +10,6 @@ // Created On : Thu May 9 10:00:00 2019 // Last Modified By : Andrew Beach -// Last Modified On : Thu Nov 24 9:44:00 2022 -// Update Count : 34 +// Last Modified On : Wed Apr 5 10:42:00 2023 +// Update Count : 35 // @@ -122,4 +122,7 @@ }; +/// Function variable arguments flag +enum ArgumentFlag { FixedArgs, VariableArgs }; + /// Object declaration `int foo()` class FunctionDecl : public DeclWithType { @@ -144,5 +147,5 @@ std::vector>&& params, std::vector>&& returns, CompoundStmt * stmts, Storage::Classes storage = {}, Linkage::Spec linkage = Linkage::Cforall, - std::vector>&& attrs = {}, Function::Specs fs = {}, bool isVarArgs = false); + std::vector>&& attrs = {}, Function::Specs fs = {}, ArgumentFlag isVarArgs = FixedArgs ); FunctionDecl( const CodeLocation & location, const std::string & name, @@ -150,5 +153,5 @@ std::vector>&& params, std::vector>&& returns, CompoundStmt * stmts, Storage::Classes storage = {}, Linkage::Spec linkage = Linkage::Cforall, - std::vector>&& attrs = {}, Function::Specs fs = {}, bool isVarArgs = false); + std::vector>&& attrs = {}, Function::Specs fs = {}, ArgumentFlag isVarArgs = FixedArgs ); const Type * get_type() const override; Index: src/AST/Pass.impl.hpp =================================================================== --- src/AST/Pass.impl.hpp (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ src/AST/Pass.impl.hpp (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -2042,5 +2042,4 @@ if ( __visit_children() ) { maybe_accept( node, &TupleType::types ); - maybe_accept( node, &TupleType::members ); } Index: src/AST/Print.cpp =================================================================== --- src/AST/Print.cpp (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ src/AST/Print.cpp (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -739,8 +739,8 @@ virtual const ast::Stmt * visit( const ast::SuspendStmt * node ) override final { os << "Suspend Statement"; - switch (node->type) { - case ast::SuspendStmt::None : os << " with implicit target"; break; - case ast::SuspendStmt::Generator: os << " for generator"; break; - case ast::SuspendStmt::Coroutine: os << " for coroutine"; break; + switch (node->kind) { + case ast::SuspendStmt::None : os << " with implicit target"; break; + case ast::SuspendStmt::Generator: os << " for generator"; break; + case ast::SuspendStmt::Coroutine: os << " for coroutine"; break; } os << endl; Index: src/AST/Stmt.hpp =================================================================== --- src/AST/Stmt.hpp (revision 2b01f8eb0956d35d26d892237add4fca234e1762) +++ src/AST/Stmt.hpp (revision a0854709c4af89b15e20a76740a80ac044d10228) @@ -10,6 +10,6 @@ // Created On : Wed May 8 13:00:00 2019 // Last Modified By : Andrew Beach -// Last Modified On : Wed Apr 20 14:34:00 2022 -// Update Count : 36 +// Last Modified On : Wed Apr 5 10:34:00 2023 +// Update Count : 37 // @@ -205,4 +205,7 @@ }; +// A while loop or a do-while loop: +enum WhileDoKind { While, DoWhile }; + // While loop: while (...) ... else ... or do ... while (...) else ...; class WhileDoStmt final : public Stmt { @@ -212,12 +215,12 @@ ptr else_; std::vector> inits; - bool isDoWhile; + WhileDoKind isDoWhile; WhileDoStmt( const CodeLocation & loc, const Expr * cond, const Stmt * body, - const std::vector> && inits, bool isDoWhile = false, const std::vector