Changeset 9509d67a for doc/theses/colby_parsons_MMAth/text
- Timestamp:
- Sep 11, 2023, 12:55:43 PM (14 months ago)
- Branches:
- master
- Children:
- c8ec58e
- Parents:
- 3ee8853
- Location:
- doc/theses/colby_parsons_MMAth/text
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex
r3ee8853 r9509d67a 12 12 \VRef[Listing]{l:cfa_thd_init} shows a typical examples of creating a \CFA user-thread type, and then as declaring processor ($N$) and thread objects ($M$). 13 13 \begin{cfa}[caption={Example of \CFA user thread and processor creation},label={l:cfa_thd_init}] 14 @thread@ my_thread { $\C{// user thread type (like structure }$14 @thread@ my_thread { $\C{// user thread type (like structure)}$ 15 15 ... // arbitrary number of field declarations 16 16 }; … … 21 21 @processor@ p[2]; $\C{// add 2 processors = 3 total with starting processor}$ 22 22 { 23 @my_thread@ t[2], * t3 = new(); $\C{// create 3 user threads, running in routine main}$23 @my_thread@ t[2], * t3 = new(); $\C{// create 2 stack allocated, 1 dynamic allocated user threads}$ 24 24 ... // execute concurrently 25 delete( t3 ); $\C{// wait for t hreadto end and deallocate}$26 } // wait for threadsto end and deallocate25 delete( t3 ); $\C{// wait for t3 to end and deallocate}$ 26 } // wait for threads t[0] and t[1] to end and deallocate 27 27 } // deallocate additional kernel threads 28 28 \end{cfa} -
doc/theses/colby_parsons_MMAth/text/CFA_intro.tex
r3ee8853 r9509d67a 9 9 \CFA is a layer over C, is transpiled\footnote{Source to source translator.} to C, and is largely considered to be an extension of C. 10 10 Beyond C, it adds productivity features, extended libraries, an advanced type-system, and many control-flow/concurrency constructions. 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.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 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 here. … … 17 17 References in \CFA are a layer of syntactic sugar over pointers to reduce the number of syntactic ref/deref operations needed with pointer usage. 18 18 Pointers in \CFA differ from C and \CC in their use of @0p@ instead of C's @NULL@ or \CC's @nullptr@. 19 References can contain 0p in \CFA, which is the equivalent of a null reference. 19 20 Examples of references are shown in \VRef[Listing]{l:cfa_ref}. 20 21 … … 64 65 This feature is also implemented in Pascal~\cite{Pascal}. 65 66 It can exist as a stand-alone statement or wrap a routine body to expose aggregate fields. 67 If exposed fields share a name, the type system will attempt to disambiguate them based on type. 68 If the type system is unable to disambiguate the fields then the user must qualify those names to avoid a compilation error. 66 69 Examples of the @with@ statement are shown in \VRef[Listing]{l:cfa_with}. 67 70 -
doc/theses/colby_parsons_MMAth/text/actors.tex
r3ee8853 r9509d67a 7 7 Actors are an indirect concurrent feature that abstracts threading away from a programmer, and instead provides \gls{actor}s and messages as building blocks for concurrency. 8 8 Hence, actors are in the realm of \gls{impl_concurrency}, where programmers write concurrent code without dealing with explicit thread creation or interaction. 9 Actor message-passing is similar to channels, but with more abstraction, so there is no shared data to protect, making actors amenable ina distributed environment.9 Actor message-passing is similar to channels, but with more abstraction, so there is no shared data to protect, making actors amenable to a distributed environment. 10 10 Actors are often used for high-performance computing and other data-centric problems, where the ease of use and scalability of an actor system provides an advantage over channels. 11 11 … … 14 14 15 15 \section{Actor Model} 16 The \Newterm{actor model} is a concurrent paradigm where computation is broken into units of work called actors, and the data for computation is distributed to actors in the form of messages~\cite{Hewitt73}.16 The \Newterm{actor model} is a concurrent paradigm where an actor is used as the fundamental building-block for computation, and the data for computation is distributed to actors in the form of messages~\cite{Hewitt73}. 17 17 An actor is composed of a \Newterm{mailbox} (message queue) and a set of \Newterm{behaviours} that receive from the mailbox to perform work. 18 18 Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors. … … 22 22 For example, mutual exclusion and locking are rarely relevant concepts in an actor model, as actors typically only operate on local state. 23 23 24 An actor does not have a thread. 24 \subsection{Classic Actor System} 25 An implementation of the actor model with a theatre (group) of actors is called an \Newterm{actor system}. 26 Actor systems largely follow the actor model, but can differ in some ways. 27 28 In an actor system, an actor does not have a thread. 25 29 An actor is executed by an underlying \Newterm{executor} (kernel thread-pool) that fairly invokes each actor, where an actor invocation processes one or more messages from its mailbox. 26 30 The default number of executor threads is often proportional to the number of computer cores to achieve good performance. 27 31 An executor is often tunable with respect to the number of kernel threads and its scheduling algorithm, which optimize for specific actor applications and workloads \see{Section~\ref{s:ActorSystem}}. 28 32 29 \subsection{Classic Actor System}30 An implementation of the actor model with a community of actors is called an \Newterm{actor system}.31 Actor systems largely follow the actor model, but can differ in some ways.32 33 While the semantics of message \emph{send} is asynchronous, the implementation may be synchronous or a combination. 33 The default semantics for message \emph{receive} is \gls{fifo}, so an actor receives messages from its mailbox in temporal (arrival) order ;34 however, messages sent among actors arrive in any order.34 The default semantics for message \emph{receive} is \gls{fifo}, so an actor receives messages from its mailbox in temporal (arrival) order. 35 % however, messages sent among actors arrive in any order. 35 36 Some actor systems provide priority-based mailboxes and/or priority-based message-selection within a mailbox, where custom message dispatchers search among or within a mailbox(es) with a predicate for specific kinds of actors and/or messages. 36 Some actor systems provide a shared mailbox where multiple actors receive from a common mailbox~\cite{Akka}, which is contrary to the no-sharing design of the basic actor-model (and requiresadditional locking).37 For non-\gls{fifo} service, some notion of fairness (eventual progress) must exist, otherwise messages have a high latency or starve, \ie never received.38 Finally, some actor systems provide multiple typed-mailboxes, which then lose the actor-\lstinline{become} mechanism \see{Section~\ref{s:SafetyProductivity}}.37 Some actor systems provide a shared mailbox where multiple actors receive from a common mailbox~\cite{Akka}, which is contrary to the no-sharing design of the basic actor-model (and may require additional locking). 38 For non-\gls{fifo} service, some notion of fairness (eventual progress) should exist, otherwise messages have a high latency or starve, \ie are never received. 39 % Finally, some actor systems provide multiple typed-mailboxes, which then lose the actor-\lstinline{become} mechanism \see{Section~\ref{s:SafetyProductivity}}. 39 40 %While the definition of the actor model provides no restrictions on message ordering, actor systems tend to guarantee that messages sent from a given actor $i$ to actor $j$ arrive at actor $j$ in the order they were sent. 40 41 Another way an actor system varies from the model is allowing access to shared global-state. … … 60 61 Figure \ref{f:inverted_actor} shows an actor system designed as \Newterm{message-centric}, where a set of messages are scheduled and run on underlying executor threads~\cite{uC++,Nigro21}. 61 62 This design is \Newterm{inverted} because actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor. 62 Now a message send must quer ies the actor to know which message queue to post the message.63 Now a message send must query the actor to know which message queue to post the message to. 63 64 Again, the simplest design has a single global queue of messages accessed by the executor threads, but this approach has the same contention problem by the executor threads. 64 65 Therefore, the messages (mailboxes) are sharded and executor threads schedule each message, which points to its corresponding actor. … … 176 177 @actor | str_msg | int_msg;@ $\C{// cascade sends}$ 177 178 @actor | int_msg;@ $\C{// send}$ 178 @actor | finished_msg;@ $\C{// send => terminate actor ( deallocation deferred)}$179 @actor | finished_msg;@ $\C{// send => terminate actor (builtin Poison-Pill)}$ 179 180 stop_actor_system(); $\C{// waits until actors finish}\CRT$ 180 181 } // deallocate actor, int_msg, str_msg … … 492 493 Each executor thread iterates over its own message queues until it finds one with messages. 493 494 At this point, the executor thread atomically \gls{gulp}s the queue, meaning it moves the contents of message queue to a local queue of the executor thread. 495 Gulping moves the contents of the message queue as a batch rather than removing individual elements. 494 496 An example of the queue gulping operation is shown in the right side of Figure \ref{f:gulp}, where an executor thread gulps queue 0 and begins to process it locally. 495 497 This step allows the executor thread to process the local queue without any atomics until the next gulp. … … 523 525 524 526 Since the copy queue is an array, envelopes are allocated first on the stack and then copied into the copy queue to persist until they are no longer needed. 525 For many workloads, the copy queues grow in size to facilitate the average number of messages in flight and there are no further dynamic allocations.527 For many workloads, the copy queues reallocate and grow in size to facilitate the average number of messages in flight and there are no further dynamic allocations. 526 528 The downside of this approach is that more storage is allocated than needed, \ie each copy queue is only partially full. 527 529 Comparatively, the individual envelope allocations of a list-based queue mean that the actor system always uses the minimum amount of heap space and cleans up eagerly. … … 562 564 To ensure sequential actor execution and \gls{fifo} message delivery in a message-centric system, stealing requires finding and removing \emph{all} of an actor's messages, and inserting them consecutively in another message queue. 563 565 This operation is $O(N)$ with a non-trivial constant. 564 The only way for work stealing to become practical is to shard each worker's message queue , which also reduces contention, and to steal queues to eliminate queue searching.566 The only way for work stealing to become practical is to shard each worker's message queue \see{Section~\ref{s:executor}}, which also reduces contention, and to steal queues to eliminate queue searching. 565 567 566 568 Given queue stealing, the goal of the presented stealing implementation is to have an essentially zero-contention-cost stealing mechanism. … … 576 578 577 579 The outline for lazy-stealing by a thief is: select a victim, scan its queues once, and return immediately if a queue is stolen. 578 The thief then assumes it normal operation of scanning over its own queues looking for work, where stolen work is placed at the end of the scan.580 The thief then assumes its normal operation of scanning over its own queues looking for work, where stolen work is placed at the end of the scan. 579 581 Hence, only one victim is affected and there is a reasonable delay between stealing events as the thief scans its ready queue looking for its own work before potentially stealing again. 580 582 This lazy examination by the thief has a low perturbation cost for victims, while still finding work in a moderately loaded system. … … 636 638 % Note that a thief never exceeds its $M$/$N$ worker range because it is always exchanging queues with other workers. 637 639 If no appropriate victim mailbox is found, no swap is attempted. 640 Note that since the mailbox checks happen non-atomically, the thieves effectively guess which mailbox is ripe for stealing. 641 The thief may read stale data and can end up stealing an ineligible or empty mailbox. 642 This is not a correctness issue and is addressed in Section~\ref{s:steal_prob}, but the steal will likely not be productive. 643 These unproductive steals are uncommon, but do occur with some frequency, and are a tradeoff that is made to achieve minimal victim contention. 638 644 639 645 \item … … 644 650 \end{enumerate} 645 651 646 \subsection{Stealing Problem} 652 \subsection{Stealing Problem}\label{s:steal_prob} 647 653 Each queue access (send or gulp) involving any worker (thief or victim) is protected using spinlock @mutex_lock@. 648 654 However, to achieve the goal of almost zero contention for the victim, it is necessary that the thief does not acquire any queue spinlocks in the stealing protocol. … … 703 709 None of the work-stealing actor-systems examined in this work perform well on the repeat benchmark. 704 710 Hence, for all non-pathological cases, the claim is made that this stealing mechanism has a (probabilistically) zero-victim-cost in practice. 711 Future work on the work stealing system could include a backoff mechanism after failed steals to further address the pathological cases. 705 712 706 713 \subsection{Queue Pointer Swap}\label{s:swap} … … 709 716 The \gls{cas} is a read-modify-write instruction available on most modern architectures. 710 717 It atomically compares two memory locations, and if the values are equal, it writes a new value into the first memory location. 711 A s oftware implementation of \gls{cas} is:718 A sequential specification of \gls{cas} is: 712 719 \begin{cfa} 713 720 // assume this routine executes atomically … … 755 762 756 763 Either a true memory/memory swap instruction or a \gls{dcas} would provide the ability to atomically swap two memory locations, but unfortunately neither of these instructions are supported on the architectures used in this work. 764 There are lock-free implemetions of DCAS, or more generally K-word CAS (also known as MCAS or CASN)~\cite{Harris02} and LLX/SCX~\cite{Brown14} that can be used to provide the desired atomic swap capability. 765 However, these lock-free implementations were not used as it is advantageous in the work stealing case to let an attempted atomic swap fail instead of retrying. 757 766 Hence, a novel atomic swap specific to the actor use case is simulated, called \gls{qpcas}. 767 Note that this swap is \emph{not} lock-free. 758 768 The \gls{qpcas} is effectively a \gls{dcas} special cased in a few ways: 759 769 \begin{enumerate} … … 766 776 \end{cfa} 767 777 \item 768 The values swapped are never null pointers, so a null pointer can be used as an intermediate value during the swap. 778 The values swapped are never null pointers, so a null pointer can be used as an intermediate value during the swap. As such, null is effectively used as a lock for the swap. 769 779 \end{enumerate} 770 780 Figure~\ref{f:qpcasImpl} shows the \CFA pseudocode for the \gls{qpcas}. … … 862 872 The concurrent proof of correctness is shown through the existence of an invariant. 863 873 The invariant states when a queue pointer is set to @0p@ by a thief, then the next write to the pointer can only be performed by the same thief. 874 This is effictively a mutual exclusion condition for the later write. 864 875 To show that this invariant holds, it is shown that it is true at each step of the swap. 865 876 \begin{itemize} … … 1011 1022 The intuition behind this heuristic is that the slowest worker receives help via work stealing until it becomes a thief, which indicates that it has caught up to the pace of the rest of the workers. 1012 1023 This heuristic should ideally result in lowered latency for message sends to victim workers that are overloaded with work. 1024 It must be acknowledged that this linear search could cause a lot of cache coherence traffic. 1025 Future work on this heuristic could include introducing a search that has less impact on caching. 1013 1026 A negative side-effect of this heuristic is that if multiple thieves steal at the same time, they likely steal from the same victim, which increases the chance of contention. 1014 1027 However, given that workers have multiple queues, often in the tens or hundreds of queues, it is rare for two thieves to attempt stealing from the same queue. … … 1028 1041 \CFA's actor system comes with a suite of safety and productivity features. 1029 1042 Most of these features are only present in \CFA's debug mode, and hence, have zero-cost in no-debug mode. 1030 The suit of features include the following.1043 The suite of features include the following. 1031 1044 \begin{itemize} 1032 1045 \item Static-typed message sends: 1033 If an actor does not support receiving a given message type, the receive call is rejected at compile time, allowing unsupported messages to never besent to an actor.1046 If an actor does not support receiving a given message type, the receive call is rejected at compile time, preventing unsupported messages from being sent to an actor. 1034 1047 1035 1048 \item Detection of message sends to Finished/Destroyed/Deleted actors: … … 1042 1055 1043 1056 \item When an executor is configured, $M >= N$. 1044 That is, each worker must receive at least one mailbox queue, otherwise the worker spins and never does any work.1057 That is, each worker must receive at least one mailbox queue, since otherwise a worker cannot receive any work without a queue pull messages from. 1045 1058 1046 1059 \item Detection of unsent messages: … … 1100 1113 \begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=5pt\parsep=5pt\itemsep=0pt} 1101 1114 \item 1102 Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets ( 48 process\-ing units) 2.2GHz, running Linux v5.8.0--59--generic1103 \item 1104 Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units) 2.0 GHz, running Linux v5.8.0--55--generic1115 Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets (96 process\-ing units), running Linux v5.8.0--59--generic 1116 \item 1117 Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units), running Linux v5.8.0--55--generic 1105 1118 \end{list} 1106 1119 … … 1112 1125 All benchmarks are run 5 times and the median is taken. 1113 1126 Error bars showing the 95\% confidence intervals appear on each point in the graphs. 1127 The confidence intervals are calculated using bootstrapping to avoid normality assumptions. 1114 1128 If the confidence bars are small enough, they may be obscured by the data point. 1115 1129 In this section, \uC is compared to \CFA frequently, as the actor system in \CFA is heavily based off of \uC's actor system. -
doc/theses/colby_parsons_MMAth/text/channels.tex
r3ee8853 r9509d67a 20 20 Neither Go nor \CFA channels have the restrictions of the early channel-based concurrent systems. 21 21 22 Other popular languages and libraries that provide channels include C++ Boost~\cite{boost:channel}, Rust~\cite{rust:channel}, Haskell~\cite{haskell:channel}, and OCaml~\cite{ocaml:channel}.22 Other popular languages and libraries that provide channels include C++ Boost~\cite{boost:channel}, Rust~\cite{rust:channel}, Haskell~\cite{haskell:channel}, OCaml~\cite{ocaml:channel}, and Kotlin~\cite{kotlin:channel}. 23 23 Boost channels only support asynchronous (non-blocking) operations, and Rust channels are limited to only having one consumer per channel. 24 24 Haskell channels are unbounded in size, and OCaml channels are zero-size. 25 25 These restrictions in Haskell and OCaml are likely due to their functional approach, which results in them both using a list as the underlying data structure for their channel. 26 26 These languages and libraries are not discussed further, as their channel implementation is not comparable to the bounded-buffer style channels present in Go and \CFA. 27 Kotlin channels are comparable to Go and \CFA, but unfortunately they were not identified as a comparator until after presentation of this thesis and are omitted due to time constraints. 27 28 28 29 \section{Producer-Consumer Problem} … … 31 32 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. 32 33 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). 33 As well, a buffer needs protection from concurrent access by multiple producers or consumers attempting to insert or remove simultaneously (MX).34 As well, a buffer needs protection from concurrent access by multiple producers or consumers attempting to insert or remove simultaneously, which is often provided by MX. 34 35 35 36 \section{Channel Size}\label{s:ChannelSize} … … 41 42 Fixed sized (bounded) implies the communication is mostly asynchronous, \ie the producer can proceed up to the buffer size and vice versa for the consumer with respect to removal, at which point the producer/consumer would wait. 42 43 \item 43 Infinite sized (unbounded) implies the communication is asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty. 44 Since memory is finite, all unbounded buffers are ultimately bounded; 45 this restriction must be part of its implementation. 44 Infinite sized (unbounded) implies the communication is asymmetrically asynchronous, \ie the producer never waits but the consumer waits when the buffer is empty. 46 45 \end{enumerate} 47 46 … … 50 49 However, like MX, a buffer should ensure every value is eventually removed after some reasonable bounded time (no long-term starvation). 51 50 The simplest way to prevent starvation is to implement the buffer as a queue, either with a cyclic array or linked nodes. 51 While \gls{fifo} is not required for producer-consumer problem correctness, it is a desired property in channels as it provides predictable and often relied upon channel ordering behaviour to users. 52 52 53 53 \section{First-Come First-Served} 54 As pointed out, a bounded buffer requires MX among multiple producers or consumers.54 As pointed out, a bounded buffer implementation often provides MX among multiple producers or consumers. 55 55 This MX should be fair among threads, independent of the \gls{fifo} buffer being fair among values. 56 56 Fairness among threads is called \gls{fcfs} and was defined by Lamport~\cite[p.~454]{Lamport74}. … … 66 66 67 67 \section{Channel Implementation}\label{s:chan_impl} 68 Currently, only the Go and Erlang programming languagesprovide user-level threading where the primary communication mechanism is channels.69 Both Go and Erlanghave user-level threading and preemptive scheduling, and both use channels for communication.70 Go providesmultiple homogeneous channels; each have a single associated type.68 The programming languages Go, Kotlin, and Erlang provide user-level threading where the primary communication mechanism is channels. 69 These languages have user-level threading and preemptive scheduling, and both use channels for communication. 70 Go and Kotlin provide multiple homogeneous channels; each have a single associated type. 71 71 Erlang, which is closely related to actor systems, provides one heterogeneous channel per thread (mailbox) with a typed receive pattern. 72 Go encouragesusers to communicate via channels, but provides them as an optional language feature.72 Go and Kotlin encourage users to communicate via channels, but provides them as an optional language feature. 73 73 On the other hand, Erlang's single heterogeneous channel is a fundamental part of the threading system design; using it is unavoidable. 74 Similar to Go , \CFA's channels are offered as an optional language feature.74 Similar to Go and Kotlin, \CFA's channels are offered as an optional language feature. 75 75 76 76 While iterating on channel implementation, experiments were conducted that varied the producer-consumer algorithm and lock type used inside the channel. … … 83 83 The Go channel implementation utilizes cooperation among threads to achieve good performance~\cite{go:chan}. 84 84 This cooperation only occurs when producers or consumers need to block due to the buffer being full or empty. 85 After a producer blocks it must wait for a consumer to signal it and vice versa. 86 The consumer or producer that signals a blocked thread is called the signalling thread. 85 87 In these cases, a blocking thread stores their relevant data in a shared location and the signalling thread completes the blocking thread's operation before waking them; 86 88 \ie the blocking thread has no work to perform after it unblocks because the signalling threads has done this work. … … 88 90 First, each thread interacting with the channel only acquires and releases the internal channel lock once. 89 91 As a result, contention on the internal lock is decreased; only entering threads compete for the lock since unblocking threads do not reacquire the lock. 90 The other advantage of Go's wait-morphing approach is that it eliminates the bottleneck of waitingfor signalled threads to run.92 The other advantage of Go's wait-morphing approach is that it eliminates the need to wait for signalled threads to run. 91 93 Note that the property of acquiring/releasing the lock only once can also be achieved with a different form of cooperation, called \Newterm{baton passing}. 92 94 Baton passing occurs when one thread acquires a lock but does not release it, and instead signals a thread inside the critical section, conceptually ``passing'' the mutual exclusion from the signalling thread to the signalled thread. … … 94 96 the wait-morphing approach has threads cooperate by completing the signalled thread's operation, thus removing a signalled thread's need for mutual exclusion after unblocking. 95 97 While baton passing is useful in some algorithms, it results in worse channel performance than the Go approach. 96 In the baton-passing approach, all threads need to wait for the signalled thread to reach the front of the ready queue, context switch,and run before other operations on the channel can proceed, since the signalled thread holds mutual exclusion;98 In the baton-passing approach, all threads need to wait for the signalled thread to unblock and run before other operations on the channel can proceed, since the signalled thread holds mutual exclusion; 97 99 in the wait-morphing approach, since the operation is completed before the signal, other threads can continue to operate on the channel without waiting for the signalled thread to run. 98 100 -
doc/theses/colby_parsons_MMAth/text/conclusion.tex
r3ee8853 r9509d67a 20 20 \item Channels with comparable performance to Go, which have safety and productivity features including deadlock detection and an easy-to-use exception-based channel @close@ routine. 21 21 \item An in-memory actor system, which achieves the lowest latency message send of systems tested due to the novel copy-queue data structure. 22 \item As well, the actor system has built-in detection of six common actor errors, with excellent performance compared to other systems across all benchmarks .23 \item A @waituntil@ statement, which tackles the hard problem of allowing a thread to safelywait synchronously for an arbitrary set of concurrent resources.22 \item As well, the actor system has built-in detection of six common actor errors, with excellent performance compared to other systems across all benchmarks presented in this thesis. 23 \item A @waituntil@ statement, which tackles the hard problem of allowing a thread wait synchronously for an arbitrary set of concurrent resources. 24 24 \end{enumerate} 25 25 -
doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex
r3ee8853 r9509d67a 83 83 \end{figure} 84 84 85 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 of other MX functions.85 Like Java, \CFA monitors have \Newterm{multi-acquire} (reentrant locking) semantics so the thread in the monitor may acquire it multiple times without deadlock, allowing recursion and calling of other MX functions. 86 86 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. 87 87 Monitor objects can be passed through multiple helper functions without acquiring mutual exclusion, until a designated function associated with the object is called. … … 104 104 } 105 105 \end{cfa} 106 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. It it important to note that \CFA monitors do not attempt to solve the nested monitor problem~\cite{Lister77}. 106 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 via resource ordering. 107 It it important to note that \CFA monitors do not attempt to solve the nested monitor problem~\cite{Lister77}. 107 108 108 109 \section{\lstinline{mutex} statement} … … 165 166 In detail, the mutex statement has a clause and statement block, similar to a conditional or loop statement. 166 167 The clause accepts any number of lockable objects (like a \CFA MX function prototype), and locks them for the duration of the statement. 167 The locks are acquired in a deadlock free manner and released regardless of how control-flow exits the statement. 168 The locks are acquired in a deadlock-free manner and released regardless of how control-flow exits the statement. 169 Note that this deadlock-freedom has some limitations \see{\VRef{s:DeadlockAvoidance}}. 168 170 The mutex statement provides easy lock usage in the common case of lexically wrapping a CS. 169 171 Examples of \CFA mutex statement are shown in \VRef[Listing]{l:cfa_mutex_ex}. … … 210 212 Like Java, \CFA introduces a new statement rather than building from existing language features, although \CFA has sufficient language features to mimic \CC RAII locking. 211 213 This syntactic choice makes MX explicit rather than implicit via object declarations. 212 Hence, it is eas ier 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.214 Hence, it is easy 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; similar scanning can be done with Java's @synchronized@. 213 215 Furthermore, concurrent safety is provided across an entire program for the complex operation of acquiring multiple locks in a deadlock-free manner. 214 216 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. … … 231 233 thread$\(_2\)$ : sout | "uvw" | "xyz"; 232 234 \end{cfa} 233 any of the outputs can appear , included a segment fault due to I/O buffer corruption:235 any of the outputs can appear: 234 236 \begin{cquote} 235 237 \small\tt … … 260 262 mutex( sout ) { // acquire stream lock for sout for block duration 261 263 sout | "abc"; 262 mutex( sout ) sout | "uvw" | "xyz"; // OK because sout lock is recursive264 sout | "uvw" | "xyz"; 263 265 sout | "def"; 264 266 } // implicitly release sout lock 265 267 \end{cfa} 266 The inner lock acquire is likely to occur through a function call that does a thread-safe print.267 268 268 269 \section{Deadlock Avoidance}\label{s:DeadlockAvoidance} … … 309 310 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; 310 311 for 7 or more locks, insertion sort is used. 311 Since it is extremely rare to hold more than 6 locks at a time, the algorithm is fast and executes in $O(1)$ time. 312 Furthermore, lock addresses are unique across program execution, even for dynamically allocated locks, so the algorithm is safe across the entire program execution. 312 It is assumed to be rare to hold more than 6 locks at a time. 313 For 6 or fewer locks the algorithm is fast and executes in $O(1)$ time. 314 Furthermore, lock addresses are unique across program execution, even for dynamically allocated locks, so the algorithm is safe across the entire program execution, as long as lifetimes of objects are appropriately managed. 315 For example, deleting a lock and allocating another one could give the new lock the same address as the deleted one, however deleting a lock in use by another thread is a programming error irrespective of the usage of the @mutex@ statement. 313 316 314 317 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. … … 338 341 \end{cquote} 339 342 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. 340 The convenience and safety of the @mutex@ statement, \ie guaranteed lock release with exceptions, should encourage programmers to always use it for locking, mitigating any deadlock scenarioversus combining manual locking with the mutex statement.343 The convenience and safety of the @mutex@ statement, \ie guaranteed lock release with exceptions, should encourage programmers to always use it for locking, mitigating most deadlock scenarios versus combining manual locking with the mutex statement. 341 344 Both \CC and the \CFA do not provide any deadlock guarantees for nested @scoped_lock@s or @mutex@ statements. 342 345 To do so would require solving the nested monitor problem~\cite{Lister77}, which currently does not have any practical solutions. … … 344 347 \section{Performance} 345 348 Given the two multi-acquisition algorithms in \CC and \CFA, each with differing advantages and disadvantages, it interesting to compare their performance. 346 Comparison with Java is not possible, since it only takes a single lock.349 Comparison with Java was not conducted, since the synchronized statement only takes a single object and does not provide deadlock avoidance or prevention. 347 350 348 351 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. … … 356 359 Each variation is run 11 times on 2, 4, 8, 16, 24, 32 cores and with 2, 4, and 8 locks being acquired. 357 360 The median is calculated and is plotted alongside the 95\% confidence intervals for each point. 361 The confidence intervals are calculated using bootstrapping to avoid normality assumptions. 358 362 359 363 \begin{figure} … … 388 392 } 389 393 \end{cfa} 390 \caption{Deadlock avoidance benchmark pseudocode}394 \caption{Deadlock avoidance benchmark \CFA pseudocode} 391 395 \label{l:deadlock_avoid_pseudo} 392 396 \end{figure} … … 396 400 % sudo dmidecode -t system 397 401 \item 398 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 compiler402 Supermicro AS--1123US--TR4 AMD EPYC 7662 64--core socket, hyper-threading $\times$ 2 sockets (256 processing units), TSO memory model, running Linux v5.8.0--55--generic, gcc--10 compiler 399 403 \item 400 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 compiler404 Supermicro SYS--6029U--TR4 Intel Xeon Gold 5220R 24--core socket, hyper-threading $\times$ 2 sockets (96 processing units), TSO memory model, running Linux v5.8.0--59--generic, gcc--10 compiler 401 405 \end{list} 402 406 %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). … … 411 415 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. 412 416 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. 413 In Figures~\ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel} there is the counter-intuitive result of the mutexstatement performing better than the baseline.417 In Figures~\ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel} there is the counter-intuitive result of the @mutex@ statement performing better than the baseline. 414 418 At 7 locks and above the mutex statement switches from a hard coded sort to insertion sort, which should decrease performance. 415 419 The hard coded sort is branch-free and constant-time and was verified to be faster than insertion sort for 6 or fewer locks. 416 It is likely the increase in throughput compared to baseline is due to the delay spent in the insertion sort, which decreases contention on the locks. 417 420 Part of the difference in throughput compared to baseline is due to the delay spent in the insertion sort, which decreases contention on the locks. 421 This was verified to be part of the difference in throughput by experimenting with varying NCS delays in the baseline; however it only comprises a small portion of difference. 422 It is possible that the baseline is slowed down or the @mutex@ is sped up by other factors that are not easily identifiable. 418 423 419 424 \begin{figure} -
doc/theses/colby_parsons_MMAth/text/waituntil.tex
r3ee8853 r9509d67a 168 168 Go's @select@ has the same exclusive-or semantics as the ALT primitive from Occam and associated code blocks for each clause like ALT and Ada. 169 169 However, unlike Ada and ALT, Go does not provide guards for the \lstinline[language=go]{case} clauses of the \lstinline[language=go]{select}. 170 As such, the exponential blowup can be seen comparing Go and \uC in Figure~\ label{f:AdaMultiplexing}.170 As such, the exponential blowup can be seen comparing Go and \uC in Figure~\ref{f:AdaMultiplexing}. 171 171 Go also provides a timeout via a channel and a @default@ clause like Ada @else@ for asynchronous multiplexing. 172 172 … … 519 519 In following example, either channel @C1@ or @C2@ must be satisfied but nothing can be done for at least 1 or 3 seconds after the channel read, respectively. 520 520 \begin{cfa}[deletekeywords={timeout}] 521 waituntil( i << C1 ) ; and waituntil( timeout( 1`s ) );522 or waituntil( i << C2 ) ; and waituntil( timeout( 3`s ) );521 waituntil( i << C1 ){} and waituntil( timeout( 1`s ) ){} 522 or waituntil( i << C2 ){} and waituntil( timeout( 3`s ) ){} 523 523 \end{cfa} 524 524 If only @C2@ is satisfied, \emph{both} timeout code-blocks trigger because 1 second occurs before 3 seconds. … … 542 542 Now the unblocked WUT is guaranteed to have a satisfied resource and its code block can safely executed. 543 543 The insertion circumvents the channel buffer via the wait-morphing in the \CFA channel implementation \see{Section~\ref{s:chan_impl}}, allowing @waituntil@ channel unblocking to not be special-cased. 544 Note that all channel operations are fair and no preference is given between @waituntil@ and direct channel operations when unblocking. 544 545 545 546 Furthermore, if both @and@ and @or@ operators are used, the @or@ operations stop behaving like exclusive-or due to the race among channel operations, \eg:
Note: See TracChangeset
for help on using the changeset viewer.