C01

What is Concurrency?

If there is no external observer who can identify two events as being in strict temporal sequence (one event has fully terminated before the other one started) then these two events are considered concurrent

The study of interleaved execution sequences of atomic instructions of sequential processes

Why Concurrency?

Time is relative
Every system can be considered concurrent
- Real world is concurrent
Concurrent programming required to enhance reactivity of a system

Sources of Concurrency

Overlapped I/O and computation -> (Interrupt programming) Pass off I/O to the OS, when done, can interrupt the process and return I/O value
- Stop and switch to another interrupt
Multi-programming -> Illusion of many programs executing at the same time on a CPU
Multi-tasking -> Multiple interacting processes on one CPU
Multi-processor systems -> Physical/real concurrency
Parallel machines & distributed OSs -> Non-deterministic communication channels added

Types of Architectures

SISD (Single instruction, single data) -> Sequential processors, instruction executed one-by-one.
- Limited to speed of single core

SIMD (Single instruction, multiple data) -> Single instruction loaded, applied to whole array of data at once (Vector processors)
- Very efficient (i.e. GPUs)
- e.g. Add one to every element in an array

MISD (Multiple instruction, single data) -> Single data item loaded, and multiple instructions applied to it
- Good for fault tolerance resistent systems

MIMD (Multiple instruction, multiple data) -> E.g. Multi-proessors or a network

Concurrency and Chaos

Leads to a number of interesting features
- Non-deterministic phenomena -> Can't tell ahead of time, how a particular operation/event will turn out for each run
- Non-observable system states -> For any concurrent system, take the place of an external observer. Allows for detection of things not included in the original model that affect the behaviour.
- Non-reproducible behaviour -> Results can depend on more than just input parameters and starting state. E.g. timing, throughput, load, available resources, signals, ...
Note: Don't fight it, i.e.
- Use non-determinism where underlying system is non-deterministic
- Use non-determinism where precise execution sequence is irrelevant
- Use synchronisation only where necessary

C02

Concurrent Programming Abstraction

What appears sequential on a higher abstraction level, is usually concurrent at a lower abstraction level
- Concurrent OS, not fully visible at higher programming language
Likewise, what appears concurrent on a higher abstraction level, might be sequential at a lower abstraction level
- Multi-processing system, interleaved processes on a single sequential computing node

Atomic Operation

Any operation that completes sucessfully or fails, never half completed.

Interaction

No interaction between system components means we can analyse them individually as pure sequential programs
- Interaction
  - Contention (Implicit interaction) -> Multiple concurrent execution units compete for one shared resource
  - Communication (Explicit interaction) -> Explicit passing of information and/or explicit synchronisation

Time

Physical or logical time
Correctness (Logical Correctness)
- Does not depend on clock speeds / execution times / delays
- Does not depend on particular interleaving
- Hold true for all possible sequences of interaction points

Standard Concepts of Correctness

Partial correctness -> If a program terminates (for a given input), then some output property holds true

Total correctness -> Given a certain input, the program will terminate and the output property holds true

I, O are input and output sets, P is property on input set, Q is relation between input and output sets

Correctness in Non-terminating Systems

Termination could be a failure
Proofs must hold at points in time:
- Safety properties (Always true) -> Something bad will never happen
- Liveness properties (Eventually true) -> Something good will eventually happen

Safety Properties

Given some input and some state of processes, then some property on some output state will always be true

Square Q, means that Q always holds
- Safety property stronger than a liveness property, if something always holds then it already eventually holds true

Examples
- Mutual exclusion (No resource collisions)
- Absence of deadlocks

Liveness Properties

Given some input and some state of processes, then some property on some output state will eventually be true

Diamond Q, means that Q eventually holds and S is the current state of the concurrent system

Examples
- Requests must eventually complete
- State is eventually displayed
Interesting liveness properties can not be safety properties.
- E.g. A state switching between true and false, this can be a liveness property, but not a safety property as it doesn't stay true forever