Index: doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex (revision c0527f8b8b4a922098555b62a30cf6227bddf622) +++ doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex (revision 2d831a1b8696630999d4089e6cd949d11a44ddc7) @@ -30,5 +30,5 @@ When processors are added, they are added alongside the existing processor given to each program. Thus, for $N$ processors, allocate $N-1$ processors. -A thread is implicitly joined at deallocated, either implicitly at block exit for stack allocation or explicitly at @delete@ for heap allocation. +A thread is implicitly joined at deallocation, either implicitly at block exit for stack allocation or explicitly at @delete@ for heap allocation. The thread performing the deallocation must wait for the thread to terminate before the deallocation can occur. A thread terminates by returning from the main routine where it starts. Index: doc/theses/colby_parsons_MMAth/text/CFA_intro.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/CFA_intro.tex (revision c0527f8b8b4a922098555b62a30cf6227bddf622) +++ doc/theses/colby_parsons_MMAth/text/CFA_intro.tex (revision 2d831a1b8696630999d4089e6cd949d11a44ddc7) @@ -10,5 +10,5 @@ Beyond C, it adds productivity features, extended libraries, an advanced type-system, and many control-flow/concurrency constructions. However, \CFA stays true to the C programming style, with most code revolving around @struct@'s and routines, and respects the same rules as C. -\CFA is not object oriented as it has no notion of @this@ (receiver) and no structures with methods, but supports some object oriented ideas including constructors, destructors, and limited containment inheritance. +\CFA is not object oriented as it has no notion of @this@ (receiver) and no structures with methods, but supports some object oriented ideas including constructors, destructors, and limited nominal inheritance. While \CFA is rich with interesting features, only the subset pertinent to this work is discussed. @@ -128,5 +128,5 @@ \section{Polymorphism}\label{s:poly} C supports limited polymorphism, often requiring users to implement polymorphism using a @void *@ (type erasure) approach. -\CFA extends C with generalized overloading polymorphism (see \VRef{s:Overloading}), as well as, parametric polymorphism and limited containment inheritance. +\CFA extends C with generalized overloading polymorphism (see \VRef{s:Overloading}), as well as, parametric polymorphism and limited nominal inheritance. \subsection{Parametric Polymorphism} @@ -180,9 +180,9 @@ \subsection{Inheritance} -Inheritance in \CFA is taken from Plan-9 C's containment inheritance. +Inheritance in \CFA is taken from Plan-9 C's nominal inheritance. In \CFA, @struct@s can @inline@ another struct type to gain its fields and masquerade as that type. -Examples of \CFA containment inheritance are shown in \VRef[Listing]{l:cfa_inherit}. - -\begin{cfa}[caption={Example of \CFA containment inheritance},label={l:cfa_inherit}] +Examples of \CFA nominal inheritance are shown in \VRef[Listing]{l:cfa_inherit}. + +\begin{cfa}[caption={Example of \CFA nominal inheritance},label={l:cfa_inherit}] struct one_d { double x; }; struct two_d { Index: doc/theses/colby_parsons_MMAth/text/actors.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/actors.tex (revision c0527f8b8b4a922098555b62a30cf6227bddf622) +++ doc/theses/colby_parsons_MMAth/text/actors.tex (revision 2d831a1b8696630999d4089e6cd949d11a44ddc7) @@ -673,4 +673,5 @@ \section{Performance}\label{s:actor_perf} +\CAP{I will update the figures to have the larger font size and different line markers once we start editing this chapter.} The performance of \CFA's actor system is tested using a suite of microbenchmarks, and compared with other actor systems. Most of the benchmarks are the same as those presented in \ref{}, with a few additions. Index: doc/theses/colby_parsons_MMAth/text/channels.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/channels.tex (revision c0527f8b8b4a922098555b62a30cf6227bddf622) +++ doc/theses/colby_parsons_MMAth/text/channels.tex (revision 2d831a1b8696630999d4089e6cd949d11a44ddc7) @@ -13,7 +13,8 @@ Both languages are highly restrictive. Kahn's language restricts a reading process to only wait for data on a single channel at a time and different writing processes cannot send data on the same channel. -Hoare's language restricts ... +Hoare's language restricts channels such that both the sender and receiver need to explicitly name the process that is destination of a channel send or the source of a channel receive. +These channel semantics remove the ability to have an anonymous sender or receiver and additionally all channel operations in CSP are synchronous (no buffering). Channels as a programming language feature has been popularized in recent years by the language Go, which encourages the use of channels as its fundamental concurrent feature. -Go's restrictions are ... +Go's restrictions are ... \CAP{The only restrictions in Go but not CFA that I can think of are the closing semantics and the functionality of select vs. waituntil. Is that worth mentioning here or should it be discussed later?} \CFA channels do not have these restrictions. @@ -23,5 +24,5 @@ In the problem, threads interact with a buffer in two ways: producing threads insert values into the buffer and consuming threads remove values from the buffer. In general, a buffer needs protection to ensure a producer only inserts into a non-full buffer and a consumer only removes from a non-empty buffer (synchronization). -As well, a buffer needs protection at each end resulting from concurrent access by multiple producers or consumers attempt to insert or remove simultaneously (MX). +As well, a buffer needs protection from concurrent access by multiple producers or consumers attempt to insert or remove simultaneously (MX). Channels come in three flavours of buffers: @@ -34,5 +35,5 @@ Infinite sized (unbounded) implies the communication is asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty. Since memory is finite, all unbounded buffers are ultimately bounded; -this restrict must be part of its implementation. +this restriction must be part of its implementation. \end{enumerate} @@ -43,5 +44,5 @@ \section{First-Come First-Served} -As pointed out, a bounded buffer requires MX among multiple producers or consumers at either end of the buffer. +As pointed out, a bounded buffer requires MX among multiple producers or consumers. This MX should be fair among threads, independent of the FIFO buffer being fair among values. Fairness among threads is called \gls{fcfs} and was defined by Lamport~\cite[p.~454]{Lamport74}. @@ -64,5 +65,7 @@ \PAB{Discuss the Go channel implementation. Need to tie in FIFO buffer and FCFS locking.} + In this work, all channels are implemented with bounded buffers, so there is no zero-sized buffering. +\CAP{I do have zero size channels implemented, however I don't focus on them since I think they are uninteresting as they are just a thin layer over binary semaphores. Should I mention that I support it but omit discussion or just leave it out?} \section{Safety and Productivity} Index: doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex =================================================================== --- doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex (revision c0527f8b8b4a922098555b62a30cf6227bddf622) +++ doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex (revision 2d831a1b8696630999d4089e6cd949d11a44ddc7) @@ -26,5 +26,5 @@ \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. +\CFA provides a high-level locking object, called a \Newterm{monitor}, an elegant and efficient abstraction for providing 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}. @@ -111,5 +111,5 @@ 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 exact lock implementation 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. @@ -359,9 +359,32 @@ \begin{cfa}[caption={Deadlock avoidance bendchmark pseudo code},label={l:deadlock_avoid_pseudo}] - - -$\PAB{// add pseudo code}$ - - +size_t N_LOCKS; $\C{// number of locks}$ +size_t N_THREADS; $\C{// number of threads}$ +size_t N_GENS; $\C{// number of random orderings (default 100)}$ +size_t total = 0; $\C{// global throughput aggregator}$ +volatile bool done = false; $\C{// termination flag}$ + +test_spinlock locks[N_LOCKS]; +size_t rands[N_THREADS][N_LOCKS * N_GENS]; $\C{// random ordering per thread}$ + +void main( worker & w ) with(w) { $\C{// thread main}$ + size_t count = 0, idx = 0; + while ( !done ) { + idx = (count % N_LOCKS * N_GENS) * N_LOCKS; $\C{// get start of next sequence}$ + mutex(locks[rands[0]], ..., locks[rands[N_LOCKS - 1]]){} $\C{// lock sequence of locks}$ + count++; + } + __atomic_add_fetch(&total, count, __ATOMIC_SEQ_CST); $\C{// atomically add to total}$ +} + +int main( int argc, char * argv[] ) { + gen_orders(); $\C{// generate random orderings}$ + { + worker w[N_THREADS]; + sleep( 10`s ); + done = true; + } + printf( "%lu\n", total ); +} \end{cfa} @@ -379,6 +402,4 @@ 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@.