Ignore:
Timestamp:
Mar 30, 2023, 8:48:02 PM (14 months ago)
Author:
caparsons <caparson@…>
Branches:
ADT, ast-experimental, master
Children:
3d08cea, eb47a80
Parents:
c7f6786
Message:

did more editing, finished first draft of mutex stmt and channel chapters, added brief intro

Location:
doc/theses/colby_parsons_MMAth
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/colby_parsons_MMAth/Makefile

    rc7f6786 r6e83384  
    4646        figures/nasus_Aggregate_Lock_4  \
    4747        figures/nasus_Aggregate_Lock_8  \
     48        figures/nasus_Channel_Contention \
     49        figures/pyke_Channel_Contention \
    4850}
    4951

  • doc/theses/colby_parsons_MMAth/glossary.tex

    rc7f6786 r6e83384  
    99% \textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
    1010% }
    11 
     11% C_TODO: replace usages of these acronyms with \acrshort{name}
    1212\newacronym{tls}{TLS}{Thread Local Storage}
    1313\newacronym{api}{API}{Application Program Interface}
    … …  
    1616\newacronym{rtti}{RTTI}{Run-Time Type Information}
    1717\newacronym{fcfs}{FCFS}{First Come First Served}
     18\newacronym{toctou}{TOCTOU}{time-of-check to time-of-use}

  • doc/theses/colby_parsons_MMAth/local.bib

    rc7f6786 r6e83384  
    4747  publisher={ACM New York, NY, USA}
    4848}
     49
     50@mastersthesis{Beach21,
     51author={{Beach, Andrew James}},
     52title={Exception Handling in C∀},
     53year={2021},
     54publisher="UWSpace",
     55url={http://hdl.handle.net/10012/17617}
     56}

  • doc/theses/colby_parsons_MMAth/text/actors.tex

    rc7f6786 r6e83384  
    334334
    335335\section{Safety and Productivity}
    336 \CFA's actor system comes with a suite of safety and productivity features. Most of these features are present in \CFA's debug mode, but are removed when code is compiled in nodebug mode. Some of the features include:
     336\CFA's actor system comes with a suite of safety and productivity features. Most of these features are present in \CFA's debug mode, but are removed when code is compiled in nodebug mode. The suit of features include the following.
    337337
    338338\begin{itemize}

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

    rc7f6786 r6e83384  
    55% ======================================================================
    66
    7 Channels were first introduced by Hoare in his paper Communicating Sequentual Processes~\cite{Hoare78}, where he proposes a concurrent language that communicates across processes using input/output channels to send data inbetween processes. Channels are used to perform message passing concurrency, a model of concurrency where threads communicate by sending data to each other, and synchronizing via the passing mechanism. This is an alternative to shared memory concurrency, where threads can communicate directly by changing shared memory state. Most modern concurrent programming languages do not subscribe to just one style of communication between threads, and provide features that support both. Channels as a programming language feature has been popularized in recent years due to the language Go, which encourages the use of channels as its fundamental concurrent feature.
     7Channels 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.
    88
    99\section{Producer-Consumer Problem}
    … …  
    1414
    1515\section{Channel Implementation}
    16 % C_TODO: rewrite to reflect on current impl
     16The 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-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.
     17
     18\section{Safety and Productivity}
     19Channels in \CFA come with safety and productivity features to aid users. The features include the following.
     20
     21\begin{itemize}
     22\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.
     23\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.
     24\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.
     25\end{itemize}
     26
     27The 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 time-of-check to time-of-use (TOCTOU) issues where there is race between one thread checking the state of a concurrent object and another thread changing the state. 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 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.
     28
     29% C_TODO: add reference to select chapter, add citation to go channels info
     30Go 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.
     31
     32While 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 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.
     33
     34In \CFA, exception handling is an encouraged paradigm and has full language support \cite{}.
     35% \cite{Beach21}. TODO: this citation breaks when compiled. Need to fix and insert above
     36As 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.
     37Resumption exceptions are a style of exception that when caught run the corresponding catch block in the same way that termination exceptions do.
     38The 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.
     39
     40When 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.
     41
     42To 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.
     43
     44\begin{cfacode}[tabsize=3,caption={\CFA channel barrier termination},label={l:cfa_chan_bar}]
     45struct barrier {
     46    channel( int ) barWait;
     47    channel( int ) entryWait;
     48    int size;
     49}
     50void ?{}(barrier & this, int size) with(this) {
     51    barWait{size};
     52    entryWait{size};
     53    this.size = size;
     54    for ( j; size )
     55        insert( *entryWait, j );
     56}
     57
     58void flush(barrier & this) with(this) {
     59    close(barWait);
     60    close(entryWait);
     61}
     62void wait(barrier & this) with(this) {
     63    int ticket = remove( *entryWait );
     64    if ( ticket == size - 1 ) {
     65        for ( j; size - 1 )
     66            insert( *barWait, j );
     67        return;
     68    }
     69    ticket = remove( *barWait );
     70
     71    // last one out
     72    if ( size == 1 || ticket == size - 2 ) {
     73        for ( j; size )
     74            insert( *entryWait, j );
     75    }
     76}
     77barrier b{Tasks};
     78
     79// thread main
     80void main(Task & this) {
     81    try {
     82        for ( ;; ) {
     83            wait( b );
     84        }
     85    } catch ( channel_closed * e ) {}
     86}
     87
     88int main() {
     89    {
     90        Task t[Tasks];
     91
     92        sleep(10`s);
     93        flush( b );
     94    } // wait for tasks to terminate
     95    return 0;
     96}
     97\end{cfacode}
     98
     99\begin{cfacode}[tabsize=3,caption={Go channel barrier termination},label={l:go_chan_bar}]
     100
     101struct barrier {
     102    channel( int ) barWait;
     103    channel( int ) entryWait;
     104    int size;
     105}
     106void ?{}(barrier & this, int size) with(this) {
     107    barWait{size + 1};
     108    entryWait{size + 1};
     109    this.size = size;
     110    for ( j; size )
     111        insert( *entryWait, j );
     112}
     113
     114void flush(barrier & this) with(this) {
     115    insert( *entryWait, -1 );
     116    insert( *barWait, -1 );
     117}
     118void wait(barrier & this) with(this) {
     119    int ticket = remove( *entryWait );
     120    if ( ticket == -1 ) {
     121        insert( *entryWait, -1 );
     122        return;
     123    }
     124    if ( ticket == size - 1 ) {
     125        for ( j; size - 1 )
     126            insert( *barWait, j );
     127        return;
     128    }
     129    ticket = remove( *barWait );
     130    if ( ticket == -1 ) {
     131        insert( *barWait, -1 );
     132        return;
     133    }
     134
     135    // last one out
     136    if ( size == 1 || ticket == size - 2 ) {
     137        for ( j; size )
     138            insert( *entryWait, j );
     139    }
     140}
     141barrier b;
     142
     143bool done = false;
     144// thread main
     145void main(Task & this) {
     146    for ( ;; ) {
     147        if ( done ) break;
     148        wait( b );
     149    }
     150}
     151
     152int main() {
     153    {
     154        Task t[Tasks];
     155
     156        sleep(10`s);
     157        done = true;
     158
     159        flush( b );
     160    } // wait for tasks to terminate
     161    return 0;
     162}
     163\end{cfacode}
     164
     165In 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.
     166
     167\begin{cfacode}[tabsize=3,caption={\CFA channel resumption usage},label={l:cfa_resume}]
     168channel( int ) chan{ 128 };
     169
     170// Consumer thread main
     171void main(Consumer & this) {
     172    size_t runs = 0;
     173    try {
     174        for ( ;; ) {
     175            remove( chan );
     176        }
     177    } catchResume ( channel_closed * e ) {}
     178    catch ( channel_closed * e ) {}
     179}
     180
     181// Producer thread main
     182void main(Producer & this) {
     183    int j = 0;
     184    try {
     185        for ( ;;j++ ) {
     186            insert( chan, j );
     187        }
     188    } catch ( channel_closed * e ) {}
     189}
     190
     191int main( int argc, char * argv[] ) {
     192    {
     193        Consumers c[4];
     194        Producer p[4];
     195
     196        sleep(10`s);
     197
     198        for ( i; Channels )
     199            close( channels[i] );
     200    }
     201    return 0;
     202}
     203\end{cfacode}
     204
     205\section{Performance}
     206
     207Given 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.
     208
    17209
    18210\begin{figure}
    19 \begin{lrbox}{\myboxA}
    20 \begin{cfacode}[aboveskip=0pt,belowskip=0pt,basicstyle=\footnotesize]
    21 int size;
    22 int front, back, count;
    23 TYPE * buffer;
    24 cond_var prods, cons;
    25 lock mx;
    26 
    27 void insert( TYPE elem ){
    28 
    29     lock(mx);
    30 
    31     // wait if buffer is full
    32     // insert finished by consumer
    33     if (count == size){
    34         wait(prods, mx, &elem);
    35         // no reacquire
    36         return;
    37     }
    38 
    39 
    40 
    41 
    42     if (!empty(cons)){
    43         // do consumer work
    44         front(cons) = &elem;
    45         notify_one(cons);
    46     }
    47 
    48 
    49    
    50     else
    51         insert_(chan, elem);
    52 
    53 
    54     unlock(mx);
    55 }
    56 \end{cfacode}
    57 \end{lrbox}
    58 \begin{lrbox}{\myboxB}
    59 \begin{cfacode}[aboveskip=0pt,belowskip=0pt,basicstyle=\footnotesize]
    60 int size;
    61 int front, back, count;
    62 TYPE * buffer;
    63 thread * chair;
    64 TYPE * chair_elem;
    65 lock c_lock, p_lock, mx;
    66 void insert( TYPE elem ){
    67     lock(p_lock);
    68     lock(mx);
    69 
    70     // wait if buffer is full
    71     // insert finished by consumer
    72     if (count == size){
    73         chair = this_thread();
    74         chair_elem = &elem;
    75         unlock(mx);
    76         park();
    77         unlock(p_lock);
    78         return;
    79     }
    80 
    81     if (chair != 0p){
    82         // do consumer work
    83         chair_elem = &elem;
    84         unpark(chair);
    85         chair = 0p;
    86         unlock(mx);
    87         unlock(p_lock);
    88         return;
    89     } else
    90         insert_(chan, elem);
    91 
    92     unlock(mx);
    93     unlock(p_lock);
    94 }
    95 \end{cfacode}
    96 \end{lrbox}
    97 \subfloat[Go implementation]{\label{f:GoChanImpl}\usebox\myboxA}
    98 \hspace{5pt}
    99 \vrule
    100 \hspace{5pt}
    101 \subfloat[\CFA implementation]{\label{f:cfaChanImpl}\usebox\myboxB}
    102 \caption{Comparison of channel implementations}
    103 \label{f:ChanComp}
     211    \centering
     212    \begin{subfigure}{0.5\textwidth}
     213        \centering
     214        \scalebox{0.5}{\input{figures/nasus_Channel_Contention.pgf}}
     215        \subcaption{AMD \CFA Channel Benchmark}\label{f:chanAMD}
     216    \end{subfigure}\hfill
     217    \begin{subfigure}{0.5\textwidth}
     218        \centering
     219        \scalebox{0.5}{\input{figures/pyke_Channel_Contention.pgf}}
     220        \subcaption{Intel \CFA Channel Benchmark}\label{f:chanIntel}
     221    \end{subfigure}
     222    \caption{The channel contention benchmark comparing \CFA and Go channel throughput (higher is better).}
     223    \label{f:chanPerf}
    104224\end{figure}
    105 
    106 Go and \CFA have similar channel implementation when it comes to how they solve the producer-consumer problem. Both implementations attempt to minimize double blocking by requiring cooperation from signalling threads. If a consumer or producer is blocked, whichever thread signals it to proceed completes the blocked thread's operation for them so that the blocked thread does not need to acquire any locks. Channels in \CFA go a step further in preventing double blocking. In Figure~\ref{f:ChanComp}, the producer-consumer solutions used by Go and \CFA are presented. Some liberties are taken to simplify the code, such as removing special casing for zero-size buffers, and abstracting the non-concurrent insert into a helper, \code{insert_}. Only the insert routine is presented, as the remove routine is symmetric.
    107 In the Go implementation \ref{f:GoChanImpl}, first mutual exclusion is acquired. Then if the buffer is full the producer waits on a condition variable and releases the mx lock. Note it will not reacquire the lock upon waking. The 3rd argument to \code{wait} is a pointer that is stored per thread on the condition variable. This pointer can be accessed when the waiting thread is at the from of the condition variable's queue by calling \code{front}. This allows arbitrary data to be stored with waiting tasks in the queue, eliminating the need for a second queue just for data. This producer that waits stores a pointer to the element it wanted to insert, so that the consumer that signals them can insert the element for the producer before signalling. If the buffer is not full a producer will proceed to check if any consumers are waiting. If so then the producer puts its value directly into the consumers hands, bypassing the usage of the buffer. If there are no waiting consumers, the producer inserts the value into the buffer and leaves.
    108 The \CFA implementation \ref{f:cfaChanImpl} it follows a similar pattern to the Go implementation, but instead uses three locks and no condition variables. The main idea is that the \CFA implementation forgoes the use of a condition variable by making all producers wait on the outer lock \code{p_lock} once a single producer has to wait inside the critical section. This also happens with consumers. This further reduces double blocking by ensuring that the only threads that can enter the critical section after a producer is blocked are consumers and vice versa. Additionally, entering consumers to not have to contend for the \code{mx} lock once producers are waiting and vice versa. Since only at most one thread will be waiting in the critical section, condition variables are not needed and a barebones thread \code{park} and \code{unpark} will suffice. The operation \code{park} blocks a thread and \code{unpark} is passed a pointer to a thread to wake up. This algorithm can be written using a single condition variable instead of park/unpark, but using park/unpark eliminates the need for any queueing operations. Now with the understanding of park/unpark it is clear to see the similarity between the two algorithms. The main difference being the \code{p_lock} acquisitions and releases. Note that \code{p_lock} is held until after waking from \code{park}, which provides the guarantee than no other producers will enter until the first producer to enter makes progress.
    109 
    110 \section{Safety and Productivity}
    111 
    112 
    113 \section{Performance}

  • doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex

    rc7f6786 r6e83384  
    1818
    1919\section{Other Languages}
    20 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 one item 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 \code{<mutex>} 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 RAII. An example of \CC scoped\_lock usage is shown in Listing~\ref{l:cc_scoped_lock}.
     20There 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{<mutex>} 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 RAII. An example of \CC scoped\_lock usage is shown in Listing~\ref{l:cc_scoped_lock}.
    2121
    2222\begin{cppcode}[tabsize=3,caption={\CC scoped\_lock usage},label={l:cc_scoped_lock}]
    … …  
    2929
    3030\section{\CFA implementation}
    31 The \CFA mutex statement can be seen as a combination of the similar featurs in Java and \CC. It can acquire more that one lock in a deadlock-free manner, and releases them via 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.
     31The \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 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.
    3232
    33 The parametric polymorphism allows for locking to be defined for types that may want convenient mutual exclusion. An example is \CFA's \code{sout}. \code{sout} is \CFA's output stream, similar to \CC's \code{cout}. \code{sout} has routines that match 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 it needs to acquire. 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}.
     33The 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}.
    3434
    3535\begin{cfacode}[tabsize=3,caption={\CFA sout with mutex statement},label={l:sout}]
    36     mutex( sout )
    37         sout | "This output is protected by mutual exclusion!";
     36mutex( sout )
     37    sout | "This output is protected by mutual exclusion!";
    3838\end{cfacode}
    3939
    4040\section{Deadlock Avoidance}
    41 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 straight from the \code{<mutex>} header source, with some renaming and comments for clarity.
     41The 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{<mutex>} header, with some renaming and comments for clarity.
    4242
    4343\begin{cppcode}[tabsize=3,caption={\CC scoped\_lock deadlock avoidance algorithm},label={l:cc_deadlock_avoid}]
    … …  
    5959\end{cppcode}
    6060
    61 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$ in that order, $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.
     61The 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.
     62
    6263The 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.
    6364

  • doc/theses/colby_parsons_MMAth/thesis.tex

    rc7f6786 r6e83384  
    113113%----------------------------------------------------------------------
    114114
    115 % \input{intro}
     115\input{intro}
    116116
    117 % \input{CFA_intro}
     117\input{CFA_intro}
    118118
    119 % \input{CFA_concurrency}
     119\input{CFA_concurrency}
    120120
    121 % \input{mutex_stmt}
     121\input{mutex_stmt}
    122122
    123123\input{channels}
    124124
    125 % \input{actors}
     125\input{actors}
    126126
    127127\clearpage
Note: See TracChangeset for help on using the changeset viewer.