Changeset 251454a0 for doc/papers/concurrency/Paper.tex
- Timestamp:
- May 25, 2018, 9:42:25 AM (6 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, 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)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/concurrency/Paper.tex
r9b15e05 r251454a0 1179 1179 \begin{cfa} 1180 1180 thread Adder { 1181 int * row, cols, *subtotal; $\C{// communication}$1181 int * row, cols, & subtotal; $\C{// communication}$ 1182 1182 }; 1183 1183 void ?{}( Adder & adder, int row[], int cols, int & subtotal ) { 1184 adder.[ row, cols, subtotal ] = [ row, cols, &subtotal ];1184 adder.[ row, cols, &subtotal ] = [ row, cols, &subtotal ]; 1185 1185 } 1186 1186 void main( Adder & adder ) with( adder ) { 1187 *subtotal = 0;1187 subtotal = 0; 1188 1188 for ( int c = 0; c < cols; c += 1 ) { 1189 *subtotal += row[c];1189 subtotal += row[c]; 1190 1190 } 1191 1191 } … … 1213 1213 1214 1214 Uncontrolled non-deterministic execution is meaningless. 1215 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.1215 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. 1216 1216 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)). 1217 1217 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}). … … 1233 1233 1234 1234 1235 \subsection{Basics} 1236 1237 Non-determinism requires concurrent systems to offer support for mutual-exclusion and synchronization. 1238 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. 1239 On the other hand, synchronization enforces relative ordering of execution and synchronization tools provide numerous mechanisms to establish timing relationships among threads. 1240 1241 1242 \subsubsection{Mutual-Exclusion} 1243 1244 As mentioned above, mutual-exclusion is the guarantee that only a fix number of threads can enter a critical section at once. 1235 \subsection{Mutual Exclusion} 1236 1237 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}. 1238 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. 1239 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. 1240 \newterm{Mutual exclusion} enforces the correction number of threads are using a critical section at the same time. 1241 1245 1242 However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use. 1246 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 orderto improve ease of use.1247 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 correspondingcritical section.1243 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. 1244 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. 1248 1245 For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations (\eg reading/writing large types atomically). 1249 Another challenge with low-level locks is composability.1250 Locks have restricted composability because it takes careful organizing for multiple locks to be used while preventing deadlocks.1251 Easing composability is another feature higher-level mutual-exclusion mechanisms often offer. 1252 1253 1254 \subsubsection{Synchronization} 1255 1256 As with mutual-exclusion, low-level synchronization primitives often offer good performance and good flexibility at the cost of ease of use.1257 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.1246 However, a significant challenge with (low-level) locks is composability because it takes careful organization for multiple locks to be used while preventing deadlock. 1247 Easing composability is another feature higher-level mutual-exclusion mechanisms offer. 1248 1249 1250 \subsection{Synchronization} 1251 1252 Synchronization enforces relative ordering of execution, and synchronization tools provide numerous mechanisms to establish these timing relationships. 1253 Low-level synchronization primitives offer good performance and flexibility at the cost of ease of use. 1254 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. 1258 1255 As mentioned above, synchronization can be expressed as guaranteeing that event \textit{X} always happens before \textit{Y}. 1259 Most of the time, synchronization happens within a critical section, where threads must acquire mutual-exclusion in a certain order. 1260 However, it may also be desirable to guarantee that event \textit{Z} does not occur between \textit{X} and \textit{Y}. 1261 Not satisfying this property is called \textbf{barging}. 1262 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}. 1263 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. 1256 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 1257 If a writer thread is scheduled for next access, but another reader thread acquires the critical section first, the reader has \newterm{barged}. 1258 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. 1264 1259 Preventing or detecting barging is an involved challenge with low-level locks, which can be made much easier by higher-level constructs. 1265 This challenge is often split into two different methods, barging avoidance and barging prevention. 1266 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. 1260 This challenge is often split into two different approaches, barging avoidance and barging prevention. 1261 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. 1262 baton-pass locks~\cite{Andrews89} between threads instead of releasing the locks are said to be using barging prevention. 1267 1263 1268 1264
Note: See TracChangeset
for help on using the changeset viewer.