Archive for April, 2006

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.

Comments