# Changeset 251454a0 for doc/papers/concurrency

Ignore:
Timestamp:
May 25, 2018, 9:42:25 AM (5 years ago)
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, with_gc
Children:
b048dc3
Parents:
9b15e05
git-author:
Peter A. Buhr <pabuhr@…> (05/25/18 09:41:16)
git-committer:
Peter A. Buhr <pabuhr@…> (05/25/18 09:42:25)
Message:

more writing

File:
1 edited

### Legend:

Unmodified
 r9b15e05 \begin{cfa} thread Adder { int * row, cols, * subtotal;                        $\C{// communication}$ int * row, cols, & subtotal;                        $\C{// communication}$ }; void ?{}( Adder & adder, int row[], int cols, int & subtotal ) { adder.[ row, cols, subtotal ] = [ row, cols, &subtotal ]; adder.[ row, cols, &subtotal ] = [ row, cols, &subtotal ]; } void main( Adder & adder ) with( adder ) { *subtotal = 0; subtotal = 0; for ( int c = 0; c < cols; c += 1 ) { *subtotal += row[c]; subtotal += row[c]; } } Uncontrolled non-deterministic execution is meaningless. To reestablish meaningful execution requires mechanisms to reintroduce determinism (control non-determinism), called synchronization and mutual exclusion, where \newterm{synchronization} is a timing relationship among threads and \newterm{mutual exclusion} is an access-control mechanism on data shared by threads. To reestablish meaningful execution requires mechanisms to reintroduce determinism (control non-determinism), called synchronization and mutual exclusion, where synchronization is a timing relationship among threads and mutual exclusion is an access-control mechanism on data shared by threads. Since many deterministic challenges appear with the use of mutable shared state, some languages/libraries disallow it (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka~\cite{Akka} (Scala)). In these paradigms, interaction among concurrent objects is performed by stateless message-passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms closely relate to networking concepts (\eg channels~\cite{CSP,Go}). \subsection{Basics} Non-determinism requires concurrent systems to offer support for mutual-exclusion and synchronization. Mutual-exclusion is the concept that only a fixed number of threads can access a critical section at any given time, where a critical section is a group of instructions on an associated portion of data that requires the restricted access. On the other hand, synchronization enforces relative ordering of execution and synchronization tools provide numerous mechanisms to establish timing relationships among threads. \subsubsection{Mutual-Exclusion} As mentioned above, mutual-exclusion is the guarantee that only a fix number of threads can enter a critical section at once. \subsection{Mutual Exclusion} A group of instructions manipulating a specific instance of shared data that must be performed atomically is called an (individual) \newterm{critical-section}~\cite{Dijkstra65}. A generalization is a \newterm{group critical-section}~\cite{Joung00}, where multiple tasks with the same session may use the resource simultaneously, but different sessions may not use the resource simultaneously. The readers/writer problem~\cite{Courtois71} is an instance of a group critical-section, where readers have the same session and all writers have a unique session. \newterm{Mutual exclusion} enforces the correction number of threads are using a critical section at the same time. However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use. Methods range from low-level locks, which are fast and flexible but require significant attention to be correct, to  higher-level concurrency techniques, which sacrifice some performance in order to improve ease of use. Ease of use comes by either guaranteeing some problems cannot occur (\eg being deadlock free) or by offering a more explicit coupling between data and corresponding critical section. Methods range from low-level locks, which are fast and flexible but require significant attention for correctness, to higher-level concurrency techniques, which sacrifice some performance to improve ease of use. Ease of use comes by either guaranteeing some problems cannot occur (\eg deadlock free), or by offering a more explicit coupling between shared data and critical section. For example, the \CC @std::atomic@ offers an easy way to express mutual-exclusion on a restricted set of operations (\eg reading/writing large types atomically). Another challenge with low-level locks is composability. Locks have restricted composability because it takes careful organizing for multiple locks to be used while preventing deadlocks. Easing composability is another feature higher-level mutual-exclusion mechanisms often offer. \subsubsection{Synchronization} As with mutual-exclusion, low-level synchronization primitives often offer good performance and good flexibility at the cost of ease of use. Again, higher-level mechanisms often simplify usage by adding either better coupling between synchronization and data (\eg message passing) or offering a simpler solution to otherwise involved challenges. However, a significant challenge with (low-level) locks is composability because it takes careful organization for multiple locks to be used while preventing deadlock. Easing composability is another feature higher-level mutual-exclusion mechanisms offer. \subsection{Synchronization} Synchronization enforces relative ordering of execution, and synchronization tools provide numerous mechanisms to establish these timing relationships. Low-level synchronization primitives offer good performance and flexibility at the cost of ease of use. Higher-level mechanisms often simplify usage by adding better coupling between synchronization and data (\eg message passing), or offering a simpler solution to otherwise involved challenges, \eg barrier lock. As mentioned above, synchronization can be expressed as guaranteeing that event \textit{X} always happens before \textit{Y}. Most of the time, synchronization happens within a critical section, where threads must acquire mutual-exclusion in a certain order. However, it may also be desirable to guarantee that event \textit{Z} does not occur between \textit{X} and \textit{Y}. Not satisfying this property is called \textbf{barging}. For example, where event \textit{X} tries to effect event \textit{Y} but another thread acquires the critical section and emits \textit{Z} before \textit{Y}. The classic example is the thread that finishes using a resource and unblocks a thread waiting to use the resource, but the unblocked thread must compete to acquire the resource. Often synchronization is used to order access to a critical section, \eg ensuring the next kind of thread to enter a critical section is a reader thread If a writer thread is scheduled for next access, but another reader thread acquires the critical section first, the reader has \newterm{barged}. Barging can result in staleness/freshness problems, where a reader barges ahead of a write and reads temporally stale data, or a writer barges ahead of another writer overwriting data with a fresh value preventing the previous value from having an opportunity to be read. Preventing or detecting barging is an involved challenge with low-level locks, which can be made much easier by higher-level constructs. This challenge is often split into two different methods, barging avoidance and barging prevention. Algorithms that use flag variables to detect barging threads are said to be using barging avoidance, while algorithms that baton-pass locks~\cite{Andrews89} between threads instead of releasing the locks are said to be using barging prevention. This challenge is often split into two different approaches, barging avoidance and barging prevention. Algorithms that allow a barger but divert it until later are avoiding the barger, while algorithms that preclude a barger from entering during synchronization in the critical section prevent the barger completely. baton-pass locks~\cite{Andrews89} between threads instead of releasing the locks are said to be using barging prevention.