Concurrent Programming Class Notes

Lecture Notes for Concurrent Programming

Unmediated access to shared state is bad.
- Predicate inference and incorrect executions.
Atomic execution mediates access to shared state.
- One thread at a time access.
Atomic execution doesn't exists at large scales.
- High-level statements aren't atomic.
- Groups of high-level statements aren't atomic.
Notational conventions indicate the need for atomic execution.
- The angle brackets <>.

True atomic execution exists only at low levels.
- At assembly level for code and in the hardware for data.
- Higher-level, general purpose atomicity is too expensive to implement and use.
- Angle brackets are a notational convention.
Sometimes you can fake atomic execution.
- Statements obeying the At-Most-Once property execute as if they were atomic.
- But sometimes you can't.
Angle brackets in designs have to be implemented somehow.

Critical sections are the traditional technique for implementing large-scale atomic execution.
A critical section as a sequence of one or more statements guaranteed to execute atomically
The atomic sequence
```
< S₁ ; S₂ ; . . . ; S_n >
```
is translated into the critical section
```
entry protocol
S₁ ; S₂ ; . . . ; S_n
exit protocol
```
- entry and exit protocol are non-atomic sequences of statements.
- Every computation executes the entry protocol to enter the critical section.
- A computation in the critical section executes the exit protocol to leave the critical section.

A properly implemented critical section exhibits four properties:
1. Mutual exclusion - at most one computation in a critical region at any time.
2. Competitive success - any set of two or more computations competing to enter a critical section produces a winner.
3. Noncompetitive success - a computation without competition should always be able to enter an empty critical section.
4. Eventual entry - every computation that wants into a critical section should eventually succeed.
- "Competing" means "executing the entry protocol at the same time".
The first three properties are safety properties, the fourth is a liveness property.
- Mutual exclusion is the easiest to specify as a global invariant.
- Establishing eventual entry requires knowledge of the scheduler.

Atomic execution is your friend.
- But don't get too friendly.
Angle brackets and await statements need implementations.
- Usually involving fake atomicity.
Critical sections are a general atomicity implementation technique.
Critical sections provide mutual exclusion, winners, expedience, and universality.

This page last modified on 21 June 2003.