Multithread 多线程
* Multithreaded, Parallel, and Distributed Programming
* Basic concepts
** Solution Patterns
- Iterative Parallelism: Matrix multiplication
- Recursive Parallelism: Adaptive quadrature
- Producers and Consumers (piplines): Unix pipes
- Clients and Servers: File Systems
- Interacting Peers: Distributed matrix multiplication
* Processes and synchronization
- **atomic actions**, unconditional and conditional,
- **independence of parallel processes**;
- **at-most-once property**;
- **safety property**, **liveness prpperty**;
- **unconditional fairness**, **weak fairness**, **strong fairness**;
** Techniques for avoiding interference
One process **interferes** with another if it executes an assignment that invalidates an assertion in the other process.
- disjoint variables
- weakened assertions
- global invariants
- synchronization
* Critical sections and locks (3.1-3.3)
** critical section problem
Entry and exit protocols satisfy:
- mutual exclusion
- absence of deadlock (livelock)
- absence of unnessary delay
- eventuall entry
Solutions:
- mutex: not (in1 and in2)
- lock == ( in1 or in2). require strongly fiar scheduler to ensure eventual entry.
- test and set: TS(bool lock){bool initial=lock; lock=true; return initial;}
Three fair solutions depend only on a weakly fair scheduler
- tie-breaker algorithm
- ticket algorithm
- bakery algorithm
* Barriers, data parallel algorithms, bag of tasks — Sections 3.4 to 3.6
* Parallel programming concepts and applications — intro to Part 3 and parts of Chapter 11
* Semaphores and Pthreads library — Chapter 4
* CSCI B524
** Independence
the write set is disjoint from both the read and write sets of the other part.
** Critical Reference
A Critical Reference in an expression is reference to a variable that is changed by another process.
** At-Most-Once Property
An assignment **x=e** satisfies the at-most-once property if either
- **e** contains at most one critical reference and **x** is not read by another process, or
- **e** contains no *critical references*, in which case **x** may be read by other processes.
** Glossary
- busy waiting, spinning.