Changeset 2d831a1 for doc/theses
- Timestamp:
- May 8, 2023, 4:53:10 PM (15 months ago)
- Branches:
- ADT, ast-experimental, master
- Children:
- 84018e0
- Parents:
- c0527f8
- Location:
- doc/theses/colby_parsons_MMAth/text
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex
rc0527f8 r2d831a1 30 30 When processors are added, they are added alongside the existing processor given to each program. 31 31 Thus, for $N$ processors, allocate $N-1$ processors. 32 A thread is implicitly joined at deallocat ed, either implicitly at block exit for stack allocation or explicitly at @delete@ for heap allocation.32 A thread is implicitly joined at deallocation, either implicitly at block exit for stack allocation or explicitly at @delete@ for heap allocation. 33 33 The thread performing the deallocation must wait for the thread to terminate before the deallocation can occur. 34 34 A thread terminates by returning from the main routine where it starts. -
doc/theses/colby_parsons_MMAth/text/CFA_intro.tex
rc0527f8 r2d831a1 10 10 Beyond C, it adds productivity features, extended libraries, an advanced type-system, and many control-flow/concurrency constructions. 11 11 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. 12 \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 containmentinheritance.12 \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. 13 13 While \CFA is rich with interesting features, only the subset pertinent to this work is discussed. 14 14 … … 128 128 \section{Polymorphism}\label{s:poly} 129 129 C supports limited polymorphism, often requiring users to implement polymorphism using a @void *@ (type erasure) approach. 130 \CFA extends C with generalized overloading polymorphism (see \VRef{s:Overloading}), as well as, parametric polymorphism and limited containmentinheritance.130 \CFA extends C with generalized overloading polymorphism (see \VRef{s:Overloading}), as well as, parametric polymorphism and limited nominal inheritance. 131 131 132 132 \subsection{Parametric Polymorphism} … … 180 180 181 181 \subsection{Inheritance} 182 Inheritance in \CFA is taken from Plan-9 C's containmentinheritance.182 Inheritance in \CFA is taken from Plan-9 C's nominal inheritance. 183 183 In \CFA, @struct@s can @inline@ another struct type to gain its fields and masquerade as that type. 184 Examples of \CFA containmentinheritance are shown in \VRef[Listing]{l:cfa_inherit}.185 186 \begin{cfa}[caption={Example of \CFA containmentinheritance},label={l:cfa_inherit}]184 Examples of \CFA nominal inheritance are shown in \VRef[Listing]{l:cfa_inherit}. 185 186 \begin{cfa}[caption={Example of \CFA nominal inheritance},label={l:cfa_inherit}] 187 187 struct one_d { double x; }; 188 188 struct two_d { -
doc/theses/colby_parsons_MMAth/text/actors.tex
rc0527f8 r2d831a1 673 673 674 674 \section{Performance}\label{s:actor_perf} 675 \CAP{I will update the figures to have the larger font size and different line markers once we start editing this chapter.} 675 676 The performance of \CFA's actor system is tested using a suite of microbenchmarks, and compared with other actor systems. 676 677 Most of the benchmarks are the same as those presented in \ref{}, with a few additions. -
doc/theses/colby_parsons_MMAth/text/channels.tex
rc0527f8 r2d831a1 13 13 Both languages are highly restrictive. 14 14 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. 15 Hoare's language restricts ... 15 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. 16 These channel semantics remove the ability to have an anonymous sender or receiver and additionally all channel operations in CSP are synchronous (no buffering). 16 17 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. 17 Go's restrictions are ... 18 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?} 18 19 \CFA channels do not have these restrictions. 19 20 … … 23 24 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. 24 25 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). 25 As well, a buffer needs protection at each end resultingfrom concurrent access by multiple producers or consumers attempt to insert or remove simultaneously (MX).26 As well, a buffer needs protection from concurrent access by multiple producers or consumers attempt to insert or remove simultaneously (MX). 26 27 27 28 Channels come in three flavours of buffers: … … 34 35 Infinite sized (unbounded) implies the communication is asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty. 35 36 Since memory is finite, all unbounded buffers are ultimately bounded; 36 this restrict must be part of its implementation.37 this restriction must be part of its implementation. 37 38 \end{enumerate} 38 39 … … 43 44 44 45 \section{First-Come First-Served} 45 As pointed out, a bounded buffer requires MX among multiple producers or consumers at either end of the buffer.46 As pointed out, a bounded buffer requires MX among multiple producers or consumers. 46 47 This MX should be fair among threads, independent of the FIFO buffer being fair among values. 47 48 Fairness among threads is called \gls{fcfs} and was defined by Lamport~\cite[p.~454]{Lamport74}. … … 64 65 65 66 \PAB{Discuss the Go channel implementation. Need to tie in FIFO buffer and FCFS locking.} 67 66 68 In this work, all channels are implemented with bounded buffers, so there is no zero-sized buffering. 69 \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?} 67 70 68 71 \section{Safety and Productivity} -
doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex
rc0527f8 r2d831a1 26 26 27 27 \section{Monitor} 28 \CFA provides a high-level locking object, called a \Newterm{monitor}, an elegant , efficient, high-level mechanisms formutual exclusion and synchronization for shared-memory systems.28 \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. 29 29 First proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}. 30 30 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 111 To increase locking flexibility, some languages introduce a mutex statement. 112 112 \VRef[Figure]{f:ReadersWriter} shows the outline of a reader/writer lock written as a \CFA monitor and mutex statements. 113 (The exact lock implement is irrelevant.)113 (The exact lock implementation is irrelevant.) 114 114 The @read@ and @write@ functions are called with a reader/write lock and any arguments to perform reading or writing. 115 115 The @read@ function is not MX because multiple readers can read simultaneously. … … 359 359 \begin{cfa}[caption={Deadlock avoidance bendchmark pseudo code},label={l:deadlock_avoid_pseudo}] 360 360 361 362 363 $\PAB{// add pseudo code}$ 364 365 361 size_t N_LOCKS; $\C{// number of locks}$ 362 size_t N_THREADS; $\C{// number of threads}$ 363 size_t N_GENS; $\C{// number of random orderings (default 100)}$ 364 size_t total = 0; $\C{// global throughput aggregator}$ 365 volatile bool done = false; $\C{// termination flag}$ 366 367 test_spinlock locks[N_LOCKS]; 368 size_t rands[N_THREADS][N_LOCKS * N_GENS]; $\C{// random ordering per thread}$ 369 370 void main( worker & w ) with(w) { $\C{// thread main}$ 371 size_t count = 0, idx = 0; 372 while ( !done ) { 373 idx = (count % N_LOCKS * N_GENS) * N_LOCKS; $\C{// get start of next sequence}$ 374 mutex(locks[rands[0]], ..., locks[rands[N_LOCKS - 1]]){} $\C{// lock sequence of locks}$ 375 count++; 376 } 377 __atomic_add_fetch(&total, count, __ATOMIC_SEQ_CST); $\C{// atomically add to total}$ 378 } 379 380 int main( int argc, char * argv[] ) { 381 gen_orders(); $\C{// generate random orderings}$ 382 { 383 worker w[N_THREADS]; 384 sleep( 10`s ); 385 done = true; 386 } 387 printf( "%lu\n", total ); 388 } 366 389 367 390 \end{cfa} … … 379 402 380 403 Figure~\ref{f:mutex_bench} shows the results of the benchmark experiments. 381 \PAB{Make the points in the graphs for each line different.382 Also, make the text in the graphs larger.}383 404 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. 384 405 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@.
Note: See TracChangeset
for help on using the changeset viewer.