Concurrency #
Independent threads #
Definition: a thread that can’t effect or be affected by any other thread (execution state isn’t shared with other threads)
Properties:
- Deterministic: input state exactly determines results
- Reproducible
- Scheduling order irrelevant
Example: arithmetic operations
In practice: this almost never happens; thread states are almost always shared within the OS
Cooperating threads #
Definition: Cooperating threads have a shared state
Properties:
- Nondeterministic
- Not necessarily reproducible
Example: suppose these are running on different threads
printf("ABC")
printf("CBA")
Possible outputs:
ABCCBA
CBAABC
ACBBCA
ABCBCA
ABCBAC
etc...
Note with ABCCBA
we can’t tell which thread the first C
came from, because we don’t know the interleaving pattern!
Why cooperation? #
- Share resources
- Disk
- Performance
- Read one block of a file while processing previous block
- Subdivide jobs
Not all ordering matters: doesn’t matter if instructions access entirely independent variables/data
But order matters if, for example:
A = B + 1
B = B * 2
are running on separate threads. This is called a race. Result depends on which thread finishes last.
Atomic operations #
Definition: Operation that occurs in its entirety without being interrupted.
Properties:
- Can’t observe internal states
- Single-word (of memory) references and assignments
- Can’t produce atomic operations out of nonatomic operations
- Can use one atomic operation to create others
Example: suppose printf()
was an atomic operation. With the following on separate threads:
printf("ABC")
printf("CBA")
Possible outputs:
ABCCBA
CBAABC
Safety and liveness #
- Safety: things that we don’t want to happen in a system shouldn’t happen
- Liveness: system needs to do something
Robust systems follow safety and liveness properties